6.4.3 Canny's Roadmap Algorithm

The doubly exponential running time of cylindrical algebraic decomposition inspired researchers to do better. It has been shown that quantifier elimination requires doubly exponential time [262]; however, motion planning is a different problem. Canny introduced a method that produces a roadmap directly from the semi-algebraic set, rather than constructing a cell decomposition along the way. Since there are doubly exponentially many cells in the cylindrical algebraic decomposition, avoiding this construction pays off. The resulting roadmap method of Canny solves the motion planning problem in time that is again polynomial in the number of polynomials and polynomial in the algebraic degree, but it is only singly exponential in dimension [170,173]; see also [77].

Much like the other combinatorial motion planning approaches, it is based on finding critical curves and critical points. The main idea is to construct linear mappings from ${\mathbb{R}}^n$ to ${\mathbb{R}}^2$ that produce silhouette curves of the semi-algebraic sets. Performing one such mapping on the original semi-algebraic set yields a roadmap, but it might not preserve the original connectivity. Therefore, linear mappings from ${\mathbb{R}}^{n-1}$ to ${\mathbb{R}}^2$ are performed on some $(n-1)$-dimensional slices of the original semi-algebraic set to yield more roadmap curves. This process is applied recursively until the slices are already one-dimensional. The resulting roadmap is formed from the union of all of the pieces obtained in the recursive calls. The resulting roadmap has the same connectivity as the original semi-algebraic set [173].

Suppose that ${\cal C}= {\mathbb{R}}^n$. Let ${\cal F}= \{f_1,\ldots,f_m\}$ denote the set of polynomials that define the semi-algebraic set, which is assumed to be a disjoint union of manifolds. Assume that each $f_i \in {\mathbb{Q}}[x_1,\ldots,x_n]$. First, a small perturbation to the input polynomials ${\cal F}$ is performed to ensure that every sign-invariant set of ${\mathbb{R}}^n$ is a manifold. This forces the polynomials into a kind of general position, which can be achieved with probability one using random perturbations; there are also deterministic methods to solve this problem. The general position requirements on the input polynomials and the 2D projection directions are fairly strong, which has stimulated more recent work that eliminates many of the problems [77]. From this point onward, it will be assumed that the polynomials are in general position.

Recall the sign-assignment function from Section 6.4.1. Each sign-invariant set is a manifold because of the general position assumption. Canny's method computes a roadmap for any $k$-dimensional manifold for $k < n$. Such a manifold has precisely $n-k$ signs that are 0 (which means that points lie precisely on the zero sets of $n-k$ polynomials in ${\cal F}$). At least one of the signs must be 0, which means that Canny's roadmap actually lies in $\partial{\cal C}_{free}$ (this technically is not permitted, but the algorithm nevertheless correctly decides whether a solution path exists through ${\cal C}_{free}$).

Recall that each $f_i$ is a function, $f_i: {\mathbb{R}}^n \rightarrow {\mathbb{R}}$. Let $x$ denote $(x_1,\ldots, x_n) \in {\mathbb{R}}^n$. The $k$ polynomials that have zero signs can be put together sequentially to produce a mapping ${\psi}: {\mathbb{R}}^n \rightarrow {\mathbb{R}}^k$. The $i$th component of the vector ${\psi}(x)$ is ${\psi}_i(x) = f_i(x)$. This is closely related to the sign assignment function of Section 6.4.1, except that now the real value from each polynomial is directly used, rather than taking its sign.

Now introduce a function $g : {\mathbb{R}}^n \rightarrow {\mathbb{R}}^j$, in which either $j=1$ or $j=2$ (the general concepts presented below work for other values of $j$, but $1$ and $2$ are the only values needed for Canny's method). The function $g$ serves the same purpose as a projection in cylindrical algebraic decomposition, but note that $g$ immediately drops from dimension $n$ to dimension $2$ or $1$, instead of dropping to $n-1$ as in the case of cylindrical projections.

Let ${h}: {\mathbb{R}}^n \rightarrow {\mathbb{R}}^{k+j}$ denote a mapping constructed directly from ${\psi}$ and $g$ as follows. For the $i$th component, if $i \leq k$, then ${h}_i(x) = {\psi}_i(x) = f_i(x)$. Assume that $k+j \leq n$. If $i > k$, then ${h}_i(x) = g_{i-k}(x)$. Let $J_x({h})$ denote the Jacobian of ${h}$ and be defined at $x$ as

$$J_x({h}) = \begin{pmatrix}\displaystyle\strut \frac{\partial {h}_... ...s & \displaystyle\strut \frac{\partial g_j(x)}{\partial x_n} \end{pmatrix} .$$ (6.28)

A point $x \in {\mathbb{R}}^n$ at which $J_x({h})$ is singular is called a critical point. The matrix is defined to be singular if every $(m+k) \times (m+k)$ subdeterminant is zero. Each of the first $k$ rows of $J_x({h})$ calculates the surface normal to $f_i(x) = 0$. If these normals are not linearly independent of the directions given by the last $j$ rows, then the matrix becomes singular. The following example from [169] nicely illustrates this principle.

Example 6..7 (Canny's Roadmap Algorithm)   Let $n=3$, $k=1$, and $j=1$. The zeros of a single polynomial $f_1$ define a 2D subset of ${\mathbb{R}}^3$. Let $f_1$ be the unit sphere, ${\mathbb{S}}^2$, defined as the zeros of the polynomial

$$f_1(x_1,x_2,x_3) = x_1^2 + x_2^2 + x_3^2 - 1 .$$ (6.29)

Suppose that $g: {\mathbb{R}}^3 \rightarrow {\mathbb{R}}$ is defined as $g(x_1,x_2,x_3) = x_1$. The Jacobian, (6.28), becomes

$$\begin{pmatrix}2x_1 & 2x_2 & 2x_3 \\ 1 & 0 & 0 \\ \end{pmatrix}$$ (6.30)

and is singular when all three of the possible $2 \times 2$ subdeterminants are zero. This occurs if and only if $x_2 = x_3 = 0$. This yields the critical points $(-1,0,0)$ and $(1,0,0)$ on ${\mathbb{S}}^2$. Note that this is precisely when the surface normals of ${\mathbb{S}}^2$ are parallel to the vector $[1 \; 0 \; 0]$.

Now suppose that $j=2$ to obtain $g: {\mathbb{R}}^3 \rightarrow {\mathbb{R}}^2$, and suppose $g(x_1,x_2,x_3) = (x_1,x_2)$. In this case, (6.28) becomes

$$\begin{pmatrix}2x_1 & 2x_2 & 2x_3 1 & 0 & 0 0 & 1 & 0 \end{pmatrix} ,$$ (6.31)

which is singular if and only if $x_3 = 0$. The critical points are therefore the $x_1x_2$ plane intersected with ${\mathbb{S}}^3$, which yields the equator points (all $(x_1,x_2) \in {\mathbb{R}}^2$ such that $x_1^2 + x_2^2 = 1$). In this case, more points are generated because the matrix becomes degenerate for any surface normal of ${\mathbb{S}}^2$ that is parallel to $[1 \; 0 \; 0]$, $[0 \; 1\; 0]$ or any linear combination of these. $\blacksquare$

The first mapping in Example 6.7 yielded two isolated critical points, and the second mapping yielded a one-dimensional set of critical points, which is referred to as a silhouette. The union of the silhouette and the isolated critical points yields a roadmap for ${\mathbb{S}}^2$. Now consider generalizing this example to obtain the full algorithm for general $n$ and $k$. A linear mapping $g:{\mathbb{R}}^n \rightarrow {\mathbb{R}}^2$ is constructed that might not be axis-aligned as in Example 6.7 because it must be chosen in general position (otherwise degeneracies might arise in the roadmap). Define ${\psi}$ to be the set of polynomials that become zero on the desired manifold on which to construct a roadmap. Form the matrix (6.28) and determine the silhouette. This is accomplished in general using subresultant techniques that were also needed for cylindrical algebraic decomposition; see [77,173] for details. Let $g_1$ denote the first component of $g$, which yields a mapping $g_1 : {\mathbb{R}}^n \rightarrow {\mathbb{R}}$. Forming $(\ref{eqn:canmat})$ using $g_1$ yields a finite set of critical points. Taking the union of the critical points and the silhouette produces part of the roadmap.

So far, however, there are no guarantees that the connectivity is preserved. To handle this problem, Canny's algorithm proceeds recursively. For each of the critical points $x \in {\mathbb{R}}^n$, an $n-1$-dimensional hyperplane through $x$ is chosen for which the $g_1$ row of $(\ref{eqn:canmat})$ is the normal (hence it is perpendicular in some sense to the flow of $g_1$). Inside of this hyperplane, a new $g$ mapping is formed. This time a new direction is chosen, and the mapping takes the form $g : {\mathbb{R}}^{n-1} \rightarrow {\mathbb{R}}^2$. Once again, the silhouettes and critical points are found and added to the roadmap. This process is repeated recursively until the base case in which the silhouettes and critical points are directly obtained without forming $g$.

It is helpful to consider an example. Since the method involves a sequence of 2D projections, it is difficult to visualize. Problems in ${\mathbb{R}}^4$ and higher involve two or more 2D projections and would therefore be more interesting. An example over ${\mathbb{R}}^3$ is presented here, even though it unfortunately has only one projection; see [173] for another example over ${\mathbb{R}}^3$.

Example 6..8 (Canny's Algorithm on a Torus)   Consider the 3D algebraic set shown in Figure 6.36. After defining the mapping $g(x_1,x_2,x_3) = (x_1,x_2)$, the roadmap shown in Figure 6.37 is obtained. The silhouettes are obtained from $g$, and the critical points are obtained from $g_1$ (this is the first component of $g$). Note that the original connectivity of the solid torus is not preserved because the inner ring does not connect to the outer ring. This illustrates the need to also compute the roadmap for lower dimensional slices. For each of the four critical points, the critical curves are computed for a plane that is parallel to the $x_2$$x_3$ plane and for which the $x_1$ position is determined by the critical point. The slice for one of the inner critical points is shown in Figure 6.38. In this case, the slice already has two dimensions. New silhouette curves are added to the roadmap to obtain the final result shown in Figure 6.39. $\blacksquare$

Figure 6.36: Suppose that the semi-algebraic set is a solid torus in ${\mathbb{R}}^3$.

Figure 6.37: The projection into the $x_1x_2$ plane yields silhouettes for the inner and outer rings and also four critical points.

Figure 6.38: A slice taken for the inner critical points is parallel to the $x_2x_3$ plane. The roadmap for the slice connects to the silhouettes from Figure 6.37, thereby preserving the connectivity of the original set in Figure 6.36.

Figure 6.39: All of the silhouettes and critical points are merged to obtain the roadmap.

To solve a planning problem, the query points ${q_{I}}$ and ${q_{G}}$ are artificially declared to be critical points in the top level of recursion. This forces the algorithm to generate curves that connect them to the rest of the roadmap.

The completeness of the method requires very careful analysis, which is thoroughly covered in [77,173]. The main elements of the analysis are showing that: 1) the polynomials can be perturbed and $g$ can be chosen to ensure general position, 2) the singularity conditions on $(\ref{eqn:canmat})$ lead to algebraic sets (varieties), and 3) the resulting roadmap has the required properties mentioned in Section 6.1 of being accessible and connectivity-preserving for ${\cal C}_{free}$ (actually it is shown for $\partial{\cal C}_{free}$). The method explained above computes the roadmap for each sign-invariant set, but to obtain a roadmap for the planning problem, the roadmaps from each sign-invariant set must be connected together correctly; fortunately, this has been solved via the Linking Lemma of [169]. A major problem, however, is that even after knowing the connectivity of the roadmap, it is a considerable challenge to obtain a parameterization of each curve on the roadmap. For this and many other technical reasons, no general implementation of Canny's algorithm appears to exist at present. Another problem is the requirement of a Whitney stratification (which can be fixed by perturbation of the input). The Basu-Pollack-Roy roadmap algorithm overcomes this problem [77].