# Robotics: Science and Systems II

### Computing Smooth Feedback Plans Over Cylindrical Algebraic Decompositions

*S. Lindemann, S. LaValle*

**Abstract:** 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., C1) 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.

**Bibtex:**

@INPROCEEDINGS{ Lindemann-RSS-06, AUTHOR = {S. Lindemann and S. LaValle}, TITLE = {Computing Smooth Feedback Plans Over Cylindrical Algebraic Decompositions}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2006}, ADDRESS = {Philadelphia, USA}, MONTH = {August}, DOI = {10.15607/RSS.2006.II.027} }