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
to
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
to
are performed on some
-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 . Let denote the set of polynomials that define the semi-algebraic set, which is assumed to be a disjoint union of manifolds. Assume that each . First, a small perturbation to the input polynomials is performed to ensure that every sign-invariant set of 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 -dimensional manifold for . Such a manifold has precisely signs that are 0 (which means that points lie precisely on the zero sets of polynomials in ). At least one of the signs must be 0, which means that Canny's roadmap actually lies in (this technically is not permitted, but the algorithm nevertheless correctly decides whether a solution path exists through ).

Recall that each is a function, . Let denote . The polynomials that have zero signs can be put together sequentially to produce a mapping . The th component of the vector is . 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 , in which either or (the general concepts presented below work for other values of , but and are the only values needed for Canny's method). The function serves the same purpose as a projection in cylindrical algebraic decomposition, but note that immediately drops from dimension to dimension or , instead of dropping to as in the case of cylindrical projections.

Let
denote a mapping constructed
directly from and as follows. For the th component,
if , then
. Assume that
. If , then
. Let
denote the *Jacobian* of and be defined at
as

A point at which is singular is called a

(6.29) |

Suppose that is defined as . The Jacobian, (6.28), becomes

(6.30) |

and is singular when all three of the possible subdeterminants are zero. This occurs if and only if . This yields the critical points and on . Note that this is precisely when the surface normals of are parallel to the vector .

Now suppose that to obtain , and suppose . In this case, (6.28) becomes

(6.31) |

which is singular if and only if . The critical points are therefore the plane intersected with , which yields the equator points (all such that ). In this case, more points are generated because the matrix becomes degenerate for any surface normal of that is parallel to , or any linear combination of these.

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
. Now
consider generalizing this example to obtain the full algorithm for
general and . A linear mapping
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
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 denote the first component of , which yields a mapping
. Forming
using
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 , an -dimensional hyperplane through is chosen for which the row of is the normal (hence it is perpendicular in some sense to the flow of ). Inside of this hyperplane, a new mapping is formed. This time a new direction is chosen, and the mapping takes the form . 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 .

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

To solve a planning problem, the query points and 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 can be chosen to ensure general position, 2) the singularity
conditions on
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
(actually it is shown for
). 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].

Steven M LaValle 2012-04-20