Solving a motion planning problem

Cylindrical algebraic decomposition is also capable of solving any of the motion planning problems formulated in Chapter 4. First assume that $ {\cal C}= {\mathbb{R}}^n$. As for other decompositions, a roadmap is formed in which every vertex is an $ n$-cell and edges connect every pair of adjacent $ n$-cells by traveling through an $ (n-1)$-cell. It is straightforward to determine adjacencies inside of a cylinder, but there are several technical details associated with determining adjacencies of cells from different cylinders (pages 152-154 of [77] present an example that illustrates the problem). The cells of dimension less than $ n-1$ are not needed for motion planning purposes (just as vertices were not needed for the vertical decomposition in Section 6.2.2). The query points $ {q_{I}}$ and $ {q_{G}}$ are connected to the roadmap depending on the cell in which they lie, and a discrete search is performed.

If $ {\cal C}\subset {\mathbb{R}}^n$ and its dimension is $ k$ for $ k < n$, then all of the interesting cells are of lower dimension. This occurs, for example, due to the constraints on the matrices to force them to lie in $ SO(2)$ or $ SO(3)$. This may also occur for problems from Section 4.4, in which closed chains reduce the degrees of freedom. The cylindrical algebraic decomposition method can still solve such problems; however, the exact root representation problem becomes more complicated when determining the cell adjacencies. A discussion of these issues appears in [852]. For the case of $ SO(2)$ and $ SO(3)$, this complication can be avoided by using stereographic projection to map $ {\mathbb{S}}^1$ or $ {\mathbb{S}}^3$ to $ {\mathbb{R}}$ or $ {\mathbb{R}}^3$, respectively. This mapping removes a single point from each, but the connectivity of $ {\cal C}_{free}$ remains unharmed. The antipodal identification problem for unit quaternions represented by $ {\mathbb{S}}^3$ also does not present a problem; there is a redundant copy of $ {\cal C}$, which does not affect the connectivity.

The running time for cylindrical algebraic decomposition depends on many factors, but in general it is polynomial in the number of polynomials in $ {\cal F}_n$, polynomial in the maximum algebraic degree of the polynomials, and doubly exponential in the dimension. Complexity issues are covered in more detail in Section 6.5.3.

Steven M LaValle 2012-04-20