Computing smooth feedback plans over cylindrical algebraic decompositions

Stephen R. Lindemann, Steven M. LaValle

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper, we construct smooth feedback plans over cylindrical algebraic decompositions. Given a cylindrical algebraic decomposition on Rn, a goal state xg, and a connectivity graph of cells reachable from the goal cell, we construct a vector field that is smooth everywhere except on a set of measure zero and the integral curves of which are smooth (i.e., Ca) and arrive at a neighborhood of the goal state in finite time. We call a vector field with these properties a smooth feedback plan. The smoothness of the integral curves guarantees that they can be followed by a system with finite acceleration inputs: Âx = u. We accomplish this by defining vector fields for each cylindrical cell and face and smoothly interpolating between them. Schwartz and Sharir showed that cylindrical algebraic decompositions can be used to solve the generalized piano movers' problem, in which multiple (possibly linked) robots described as semi-algebraic sets must travel from their initial to goal configurations without intersecting each other or a set of semi-algebraic obstacles. Since we build a vector field over the decomposition, this implies that we can obtain smooth feedback plans for the generalized piano movers' problem.

Original languageEnglish (US)
Title of host publicationRobotics
Subtitle of host publicationScience and Systems II
EditorsGaurav S. Sukhatme, Stefan Schaal, Stefan Schaal, Wolfram Burgard, Dieter Fox
PublisherMIT Press Journals
Number of pages8
ISBN (Print)9780262693486
StatePublished - 2007
Event2nd International Conference on Robotics Science and Systems, RSS 2006 - Philadelphia, United States
Duration: Aug 16 2006Aug 19 2006

Publication series

NameRobotics: Science and Systems
ISSN (Electronic)2330-765X


Other2nd International Conference on Robotics Science and Systems, RSS 2006
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Artificial Intelligence
  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Computing smooth feedback plans over cylindrical algebraic decompositions'. Together they form a unique fingerprint.

Cite this