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.