Computational Algebraic Geometry
This section presents algorithms that are so general that they solve any problem of Formulation 4.1 and even the closed-chain problems of Section 4.4. It is amazing that such algorithms exist; however, it is also unfortunate that they are both ex- tremely challenging to implement and not efficient enough for most applications. The concepts and tools of this section were mostly developed in the context of com- putational real algebraic geometry [77, 250]. They are powerful enough to conquer numerous problems in robotics, computer vision, geometric modeling, computer-
{R_1, [_e_1, e3]} {_R_2, [_e_1, e3]} {_R_3, [_e_1, e3]} {_R_4, [_e_1, e3]} {_R_9, [_e_1, e3]} {_R_10, [_v_1, e_3]}
{R_4, [_e_4, v1]} {_R_9, [_e_4, e2]} {_R_10, [_e_4, e2]} {_R_11, [_e_4, e2]} {_R_12 , [_e_4, e2]} {_R_13, [_e_4, e_2]}
{R_13, [_e_2, e_4]}
{R_12 , [_v_1, e_4]}
{R_11 , [_e_3, e_4]}
{R_10 , [_e_3, e_4]}
{R_9, [_e_3, e_4]}
Figure 6.29: The roadmap corresponding to the example in Figure 6.26.
aided design, and geometric theorem proving. One of these problems happens to be motion planning, for which the connection to computational algebraic geometry was first recognized in [852].
- Basic Definitions and Concepts
This section builds on the semi-algebraic model definitions from Section 3.1 and the polynomial definitions from Section 4.4.1. It will be assumed that Rn, which could for example arise by representing each copy of SO(2) or SO(3) in its
C ⊆
- 2 or 3 3 matrix form. For example, in the case of a 3D rigid body, we know that = R3 RP3, which is a six-dimensional manifold, but it can be embedded in R12, which is obtained from the Cartesian product of R3 and the set of all
C ×
× ×
- 3 matrices. The constraints that force the matrices to lie in SO(2) or SO(3)
×
are polynomials, and they can therefore be added to the semi-algebraic models of obs and free. If the dimension of is less than n, then the algorithm presented below is sufficient, but there are some representation and complexity issues that motivate using a special parameterization of to make both dimensions the same while altering the topology of to become homeomorphic to Rn. This is discussed briefly in Section 6.4.2.
C
C
C C C
Suppose that the models in Rn are all expressed using polynomials from Q[x1, . . . , xn], the set of polynomials6 over the field of rational numbers Q. Let f Q[x1, . . . , xn] denote a polynomial.
∈
6It will be explained shortly why Q[x1, . . . , xn] is preferred over R[x1, . . . , xn].
Tarski sentences Recall the logical predicates that were formed in Section 3.1. They will be used again here, but now they are defined with a little more flexibility. For any f Q[x1, . . . , xn], an atom is an expression of the form f ⊲⊳ 0, in which ⊲⊳
{ / ≤ ≥}
∈
may be any relation in the set =, =, <, >, , . In Section 3.1, such expressions
were used to define logical predicates. Here, we assume that relations other than
n
≤ can be used and that the vector of polynomial variables lies in R .
A quantifier-free formula, φ(x1, . . . , xn), is a logical predicate composed of
atoms and logical connectives, “and,” “or,” and “not,” which are denoted by
, , and , respectively. Each atom itself is considered as a logical predicate
∧ ∨ ¬
that yields true if and only if the relation is satisfied when the polynomial is evaluated at the point (x1, . . . , xn) ∈ Rn.
Example 6.2 (An Example Predicate) Let φ be a predicate over R3, defined as
φ(x1, x2, x3) = (x2x3 − x4 < 0) ∨ （¬(3x2x3 /= 0) ∧ (2x2 − x1x2x3 + 2 ≥ 0)）. (6.8)
1
2
3
The precedence order of the connectives follows the laws of Boolean algebra. ．
Let a quantifier be either of the symbols, , which means “for all,” or , which means “there exists.” A Tarski sentence Φ is a logical predicate that may additionally involve quantifiers on some or all of the variables. In general, a Tarski sentence takes the form
Q ∀ ∃
Φ(x1, . . . , xn−k) = (Qz1)(Qz2) . . . (Qzk) φ(z1, . . . , zk, x1, . . . , xn−k), (6.9)
in which the zi are the quantified variables, the xi are the free variables, and φ is a quantifier-free formula. The quantifiers do not necessarily have to appear at the left to be a valid Tarski sentence; however, any expression can be manipulated into an equivalent expression that has all quantifiers in front, as shown in (6.9). The procedure for moving quantifiers to the front is as follows [705]: 1) Eliminate any redundant quantifiers; 2) rename some of the variables to ensure that the same variable does not appear both free and bound; 3) move negation symbols as far inward as possible; and 4) push the quantifiers to the left.
Example 6.3 (Several Tarski Sentences) Tarski sentences that have no free variables are either true or false in general because there are no arguments on which the results depend. The sentence
Φ = ∀x∃y (x2 − y < 0), (6.10)
is true because for any x ∈ R, some y ∈ R can always be chosen so that y > x2. In the general notation of (6.9), this example becomes z1 = x, z2 = y, and φ(z1, z2) = (x2 y < 0).
−
Q ∀ Q ∃
Swapping the order of the quantifiers yields the Tarski sentence
Φ = ∃y∀x (x2 − y < 0), (6.11)
which is false because for any y, there is always an x such that x2 > y.
Now consider a Tarski sentence that has a free variable:
Φ(z) = ∃y∀x (x − zx − y < 0). (6.12) This yields a function Φ : R → {true, false}, in which
2 2
true if z 1
Φ(z) = （ ≥
false if z < 1.
(6.13)
An equivalent quantifier-free formula φ can be defined as φ(z) = (z > 1), which takes on the same truth values as the Tarski sentence in (6.12). This might make you wonder whether it is always possible to make a simplification that eliminates
the quantifiers. This is called the quantifier-elimination problem, which will be explained shortly. ．
The decision problem The sentences in (6.10) and (6.11) lead to an interesting problem. Consider the set of all Tarski sentences that have no free variables. The subset of these that are true comprise the first-order theory of the reals. Can an algorithm be developed to determine whether such a sentence is true? This is called the decision problem for the first-order theory of the reals. At
first it may appear hopeless because Rn is uncountably infinite, and an algorithm must work with a finite set. This is a familiar issue faced throughout motion
planning. The sampling-based approaches in Chapter 5 provided one kind of solution. This idea could be applied to the decision problem, but the resulting lack of completeness would be similar. It is not possible to check all possible points in Rn by sampling. Instead, the decision problem can be solved by constructing a combinatorial representation that exactly represents the decision problem by partitioning Rn into a finite collection of regions. Inside of each region, only one
point needs to be checked. This should already seem related to cell decompositions
in motion planning; it turns out that methods developed to solve the decision problem can also conquer motion planning.
The quantifier-elimination problem Another important problem was exem- plified in (6.12). Consider the set of all Tarski sentences of the form (6.9), which may or may not have free variables. Can an algorithm be developed that takes a Tarski sentence Φ and produces an equivalent quantifier-free formula φ? Let
x1, . . . , xn denote the free variables. To be equivalent, both must take on the same true values over Rn, which is the set of all assignments (x1, . . . , xn) for the free variables.
Given a Tarski sentence, (6.9), the quantifier-elimination problem is to find a quantifier-free formula φ such that
Φ(x1, . . . , xn) = φ(x1, . . . , xn) (6.14)
for all (x1, . . . , xn) Rn. This is equivalent to constructing a semi-algebraic model because φ can always be expressed in the form
∈
k
I
φ(x1, . . . , xn) =
i=1
mi
(fi,j (x1, . . . , xn) ⊲⊳ 0) , (6.15)
I\
j=1
in which ⊲⊳ may be either <, =, or >. This appears to be the same (3.6), except that (6.15) uses the relations <, =, and > to allow open and closed semi-algebraic
sets, whereas (3.6) only used ≤ to construct closed semi-algebraic sets for O and
A.
Once again, the problem is defined on Rn, which is uncountably infinite, but an algorithm must work with a finite representation. This will be achieved by the
cell decomposition technique presented in Section 6.4.2.
Semi-algebraic decomposition As stated in Section 6.3.1, motion planning in- side of each cell in a complex should be trivial. To solve the decision and quantifier- elimination problems, a cell decomposition was developed for which these problems become trivial in each cell. The decomposition is designed so that only a single point in each cell needs to be checked to solve the decision problem.
The semi-algebraic set Y ⊆ Rn that is expressed with (6.15) is
k
I
Y =
i=1
mi
{(x1, . . . , xn) ∈ Rn | sgn(fi,j (x1, . . . , xn)) = si,j } , (6.16)
n
j=1
in which sgn is the sign function, and each si,j 1, 0, 1 , which is the range of sgn. Once again the nice relationship between set-theory and logic, which was
∈ {− }
described in Section 3.1, appears here. We convert from a set-theoretic description to a logical predicate by changing ∪ and ∩ to ∨ and ∧, respectively.
Let F denote the set of m = 寸k mi polynomials that appear in (6.16). A sign
i=1
assignment with respect to F is a vector-valued function, sgnF : Rn → {−1, 0, 1}m. Each f ∈ F has a corresponding position in the sign assignment vector. At
this position, the sign, sgn(f(x1, . . . , xn)) 1, 0, 1 , appears. A semi-algebraic decomposition is a partition of Rn into a finite set of connected regions that are each sign invariant. This means that inside of each region, sgnF must remain constant. The regions will not be called cells because a semi-algebraic decomposition is not
∈ {− }
necessarily a singular complex as defined in Section 6.3.1; the regions here may contain holes.
Example 6.4 (Sign assignment) Recall Example 3.1 and Figure 3.4 from Sec-
tion 3.1.2. Figure 3.4a shows a sign assignment for a case in which there is only one polynomial, F = {x + y − 4}. The sign assignment is defined as
2 2
−1 if x2 + y2 − 4 < 0
sgnF (x, y) =
0 if x2 + y2 − 4 = 0
1 if x2 + y2 − 4 > 0.
(6.17)
(−1, −1, 1, 1) (−1, 1, −1, 1)
(−1, 0, 1, 1)
(−1, 1, 0, 1)
(−1, 1, 1, 0)
(−1, 1, 1, 1)
(0, 1, 1, 1)
(−1, 1, 1, −1)
(1, 1, 1, 1)
Figure 6.30: A semi-algebraic decomposition of the gingerbread face yields 9 sign- invariant regions.
Now consider the sign assignment sgnF , shown in Figure 6.30 for the gin- gerbread face of Figure 3.4b. The polynomials of the semi-algebraic model are
= f1, f2, f3, f4 , as defined in Example 3.1. In order, these are the “head,” “left eye,” “right eye,” and “mouth.” The sign assignment produces a four-dimensional vector of signs. Note that if (x, y) lies on one of the zeros of a polynomial in
F { }
, then a 0 appears in the sign assignment. If the curves of two or more of the polynomials had intersected, then the sign assignment would produce more than one 0 at the intersection points.
F
For the semi-algebraic decomposition for the gingerbread face in Figure 6.30, there are nine regions. Five 2D regions correspond to: 1) being outside of the face, 2)inside of the left eye, 3) inside of the right eye, 4) inside of the mouth, and 5) inside of the face but outside of the mouth and eyes. There are four 1D regions, each of which corresponds to points that lie on one of the zero sets of a
polynomial. The resulting decomposition is not a singular complex because the (−1, 1, 1, 1) region contains three holes. ．
A decomposition such as the one in Figure 6.30 would not be very useful for motion planning because of the holes in the regions. Further refinement is needed for motion planning, which is fortunately produced by cylindrical algebraic decomposition. On the other hand, any semi-algebraic decomposition is quite useful for solving the decision problem. Only one point needs to be checked inside of each region to determine whether some Tarski sentence that has no free variables is true. Why? If the polynomial signs cannot change over some region, then the true/false value of the corresponding logical predicate, Φ, cannot change. Therefore, it sufficient only to check one point per sign-invariant region.
- Cylindrical Algebraic Decomposition
Cylindrical algebraic decomposition is a general method that produces a cylindrical decomposition in the same sense considered in Section 6.3.2 for polygons in R2 and also the decomposition in Section 6.3.4 for the line-segment robot. It is also referred to as Collins decomposition after its original developer [40, 232, 233]. The decomposition in Figure 6.19 can even be considered as a cylindrical algebraic decomposition for a semi-algebraic set in which every geometric primitive is a linear polynomial. In this section, such a decomposition is generalized to any semi-algebraic set in Rn.
The idea is to develop a sequence of projections that drops the dimension of the
semi-algebraic set by one each time. Initially, the set is defined over Rn, and after one projection, a semi-algebraic set is obtained in Rn−1. Eventually, the projection reaches R, and a univariate polynomial is obtained for which the zeros are at the critical places where cell boundaries need to be formed. A cell decomposition of 1-cells (intervals) and 0-cells is formed by partitioning R. The sequence is then reversed, and decompositions are formed from R2 up to Rn. Each iteration starts with a cell decomposition in Ri and lifts it to obtain a cylinder of cells in Ri+1. Figure 6.35 shows how the decomposition looks for the gingerbread example; since
n = 2, it only involves one projection and one lifting.
Semi-algebraic projections are semi-algebraic The following is implied by the Tarski-Seidenberg Theorem [77]:
A projection of a semi-algebraic set from dimension n to dimension
n − 1 is a semi-algebraic set.
This gives a kind of closure of semi-algebraic sets under projection, which is re- quired to ensure that every projection of a semi-algebraic set in Ri leads to a semi-algebraic set in Ri−1. This property is actually not true for (real) algebraic varieties, which were introduced in Section 4.4.1. Varieties are defined using only
the = relation and are not closed under the projection operation. Therefore, it is a good thing (not just a coincidence!) that we are using semi-algebraic sets.
Real algebraic numbers As stated previously, the sequence of projections ends with a univariate polynomial over R. The sides of the cells will be defined based on the precise location of the roots of this polynomial. Furthermore, representing a sample point for a cell of dimension k in a complex in Rn for k < n requires perfect precision. If the coordinates are slightly off, the point will lie in a different
cell. This raises the complicated issue of how these roots are represented and manipulated in a computer.
For univariate polynomials of degree 4 or less, formulas exist to compute all of the roots in terms of functions of square roots and higher order roots. From Galois theory [469, 769], it is known that such formulas and nice expressions for roots do not exist for most higher degree polynomials, which can certainly arise
in the complicated semi-algebraic models that are derived in motion planning. The roots in R could be any real number, and many real numbers require infinite representations.
One way of avoiding this mess is to assume that only polynomials in Q[x1, . . . , xn] are used, instead of the more general R[x1, . . . , xn]. The field Q is not alge- braically closed because zeros of the pol√ynomials√lie outside of Q . For example, if
n
f(x1) = x2 − 2, then f = 0 for x1 = ± 2, and 2 /∈ Q. However, some elements
1
of R can never be roots of a polynomial in Q[x1, . . . , xn].
The set A of all real roots to all polynomials in Q[x] is called the set of real algebraic numbers. The set A R actually represents a field (recall from Section 4.4.1). Several nice algorithmic properties of the numbers in A are 1) they all have finite representations, 2) addition and multiplication operations on elements of A can be computed in polynomial time, and 3) conversions between different representations of real algebraic numbers can be performed in polynomial time.
⊂
This means that all operations can be computed efficiently without resorting to some kind of numerical approximation. In some applications, such approximations are fine; however, for algebraic decompositions, they destroy critical information by potentially confusing roots (e.g., how can we know for sure whether a polynomial has a double root or just two roots that are very close together?).
The details are not presented here, but there are several methods for rep- resenting real algebraic numbers and the corresponding algorithms for manipu- lating them efficiently. The running time of cylindrical algebraic decomposition ultimately depends on this representation. In practice, a numerical root-finding method that has a precision parameter, ǫ, can be used by choosing ǫ small enough to ensure that roots will not be confused. A sufficiently small value can be de- termined by applying gap theorems, which give lower bounds on the amount of real root separation, expressed in terms of the polynomial coefficients [173]. Some methods avoid requiring a precision parameter. One well-known example is the derivation of a Sturm sequence of polynomials based on the given polynomial. The polynomials in the Sturm sequence are then used to find isolating intervals for each of the roots [77]. The polynomial, together with its isolating interval, can be considered as an exact root representation. Algebraic operations can even be performed using this representation in time O(d lg2 d), in which d is the degree of the polynomial [852]. See [77, 173, 852] for detailed presentations on the exact representation and calculation with real algebraic numbers.
One-dimensional decomposition To explain the cylindrical algebraic decom- position method, we first perform a semi-algebraic decomposition of R, which is the final step in the projection sequence. Once this is explained, then the multi-
dimensional case follows more easily.
Let F be a set of m univariate polynomials,
F = {fi ∈ Q[x] | i = 1, . . . , m}, (6.18)
which are used to define some semi-algebraic set in R. The polynomials in F could
R
Figure 6.31: Two parabolas are used to define the semi-algebraic set [1, 2].
R (−∞, 0)
[0, 0]
(0, 1)
[1, 1]
(1, 2)
[2, 2]
(2, 3)
[3, 3]
(3, ∞)
0 1 2 3
Figure 6.32: A semi-algebraic decomposition for the polynomials in Figure 6.31.
come directly from a quantifier-free formula φ (which could even appear inside of a Tarski sentence, as in (6.9)).
Define a single polynomial as f = n
m
i=1
roots, which are sorted in increasing order:
fi. Suppose that f has k distinct, real
− ∞ < β1 < β2 < · · · < βi−1 < βi < βi+1 < · · · < βk < ∞. (6.19)
The one-dimensional semi-algebraic decomposition is given by the following sequence of alternating 1-cells and 0-cells:
(−∞, β1), [β1, β1], (β1, β2), . . . , (βi−1, βi), [βi, βi],
(βi, βi+1), . . . , [βk, βk], (βk, ∞).
(6.20)
Any semi-algebraic set that can be expressed using the polynomials in can also be expressed as the union of some of the 0-cells and 1-cells given in (6.20). This can also be considered as a singular complex (it can even be considered as a simplicial complex, but this does not extend to higher dimensions).
F
Sample points can be generated for each of the cells as follows. For the un- bounded cells [−∞, β1) and (βk, ∞], valid samples are β1 − 1 and βk + 1, respec-
tively. For each finite 1-cell, (βi, βi+1), the midpoint (βi + βi+1)/2 produces a sample point. For each 0-cell, [βi, βi], the only choice is to use βi as the sample point.
Example 6.5 (One-Dimensional Decomposition) Figure 6.31 shows a semi- algebraic subset of R that is defined by two polynomials, f1(x) = x2 − 2x and f2(x) = x2 − 4x + 3. Here, F = {f1, f2}. Consider the quantifier-free formula
φ(x) = (x2 − 2x ≥ 0) ∧ (x2 − 4x + 3 ≥ 0). (6.21)
Folding over Intersection
Figure 6.33: Critical points occur either when the surface folds over in the vertical direction or when surfaces intersect.
The semi-algebraic decomposition into five 1-cells and four 0-cells is shown in Figure 6.32. Each cell is sign invariant. The sample points for the 1-cells are 1, 1/2, 3/2, 5/2, and 4, respectively. The sample points for the 0-cells are 0, 1, 2, and 3, respectively.
−
A decision problem can be nicely solved using the decomposition. Suppose a Tarski sentence that uses the polynomials in has been given. Here is one possibility:
F
Φ = ∃x[(x − 2x ≥ 0) ∧ (x − 4x + 3 ≥ 0)] (6.22)
2 2
The sample points alone are sufficient to determine whether Φ is true or false. Once x = 1 is attempted, it is discovered that Φ is true. The quantifier- elimination problem cannot yet be considered because more dimensions are needed.
．
The inductive step to higher dimensions Now consider constructing a cylin- drical algebraic decomposition for Rn (note the decomposition is actually semi- algebraic). Figure 6.35 shows an example for R2. First consider how to iteratively project the polynomials down to R to ensure that when the decomposition of Rn is constructed, the sign-invariant property is maintained. The resulting decompo-
sition corresponds to a singular complex.
There are two cases that cause cell boundaries to be formed, as shown in Figure
6.33. Let n denote the original set of polynomials in Q[x1, . . . , xn] that are used to define the semi-algebraic set (or Tarski sentence) in Rn. Form a single polynomial
F
f = n
m
i=1
fi. Let f′ = ∂f/∂xn, which is also a polynomial. Let g = GCD(f, f′),
which is the greatest common divisor of f and f′. The set of zeros of g is the set of
all points that are zeros of both f and f′. Being a zero of f′ means that the surface given by f = 0 does not vary locally when perturbing xn. These are places where a cell boundary needs to be formed because the surface may fold over itself in the xn direction, which is not permitted for a cylindrical decomposition. Another
place where a cell boundary needs to be formed is at the intersection of two or more polynomials in Fn. The projection technique from Rn to Rn−1 generates a set, Fn−1, of polynomials in Q[x1, . . . , xn−1] that satisfies these requirements.
The polynomials Fn−1 have the property that at least one contains a zero point below every point in x ∈ Rn for which f(x) = 0 and f′(x) = 0, or polynomials
in n intersect. The projection method that constructs n−1 involves computing principle subresultant coefficients, which are covered in [77, 853]. Resultants, of which the subresultants are an extension, are covered in [250].
F F
The polynomials in Fn−1 are then projected to Rn−2 to obtain Fn−2. This process continues until F1 is obtained, which is a set of polynomials in Q[x1]. A
one-dimensional decomposition is formed, as defined earlier. From 1, a single polynomial is formed by taking the product, and R is partitioned into 0-cells and 1-cells. We next describe the process of lifting a decomposition over Ri−1 up to Ri. This technique is applied iteratively until Rn is reached.
F
Assume inductively that a cylindrical algebraic decomposition has been com- puted for a set of polynomials Fi−1 in Q[x1, . . . , xi−1]. The decomposition consists of k-cells for which 0 ≤ k ≤ i. Let p = (x1, . . . , xi−1) ∈ Ri−1. For each one of the
- ells Ci−1, a cylinder over Ci−1 is defined as the (k + 1)-dimensional set
{(p, xi) ∈ R | p ∈ Ci−1}. (6.23)
i
The cylinder is sliced into a strip of k-dimensional and k + 1-dimensional cells by using polynomials in Fi. Let fj denote one of the ℓ slicing polynomials in the
cylinder, sorted in increasing xi order as f1, f2, . . ., fj , fj+1, . . ., fℓ. The following kinds of cells are produced (see Figure 6.34):
- Lower unbounded sector:
{(p, xi) ∈ R | p ∈ Ci−1 and xi < f1(p) }. (6.24)
i
- Section:
i
{(p, xi) ∈ R | p ∈ Ci−1 and xi = fj (p) }. (6.25)
- Bounded sector:
{(p, xi) ∈ R | p ∈ Ci−1 and fj (p) < xi < fj+1(p) }. (6.26)
i
- Upper unbounded sector:
{(p, xi) ∈ R | p ∈ Ci−1 and fℓ(p) < xi }. (6.27)
i
There is one degenerate possibility in which there are no slicing polynomials and the cylinder over Ci−1 can be extended into one unbounded cell. In general, the sample points are computed by picking a point in p Ci−1 and making a vertical
∈
column of samples of the form (p, xi). A polynomial in Q[xi] can be generated, and the samples are placed using the same assignment technique that was used
for the one-dimensional decomposition.
Figure 6.34: A cylinder over every k-cell Ci−1 is formed. A sequence of poly- nomials, f1, . . ., fℓ, slices the cylinder into k-dimensional sections and (k + 1)- dimensional sectors.
Example 6.6 (Mutilating the Gingerbread Face) Figure 6.35 shows a cylin- drical algebraic decomposition of the gingerbread face. Observe that the resulting
complex is very similar to that obtained in Figure 6.19. ．
Note that the cells do not necessarily project onto a rectangular set, as in the case of a higher dimensional vertical decomposition. For example, a generic n-cell Cn for a decomposition of Rn is described as the open set of (x1, . . . , xn) Rn such that
∈
- C0 < xn < C0′ for some 0-cells C0, C0′ ∈ R, which are roots of some f, f′ ∈ F1.
- (xn−1, xn) lies between C1 and C1′
some f, f′ ∈ F2.
...
for some 1-cells C1, C1′ , which are zeros of
- (xn−i+1, . . . , xn) lies between Ci−1 and Ci′ 1 for some i-cells Ci−1, Ci′
1, which
− −
are zeros of some f, f′ ∈ Fi.
...
1 37
R
Figure 6.35: A cylindrical algebraic decomposition of the gingerbread face. There are 37 2-cells, 64 1-cells, and 28 0-cells. The straight 1-cells are intervals of the vertical lines, and the curved ones are portions of the zero set of a polynomial in
- The decomposition of R is also shown.
- (x1, . . . , xn) lies between Cn−1 and Cn′ −1 for some (n − 1)-cells Cn−1, Cn′ −1, which are zeros of some f, f′ ∈ Fn.
The resulting decomposition is sign invariant, which allows the decision and quantifier-elimination problems to be solved in finite time. To solve a decision problem, the polynomials in n are evaluated at every sample point to deter- mine whether one of them satisfies the Tarski sentence. To solve the quantifier-
F
elimination problem, note that any semi-algebraic sets that can be constructed from Fn can be defined as a union of some cells in the decomposition. For the
given Tarski sentence, n is formed from all polynomials that are mentioned in the sentence, and the cell decomposition is performed. Once obtained, the sign information is used to determine which cells need to be included in the union. The resulting union of cells is designed to include only the points in Rn at which the Tarski sentence is true.
F
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 C = Rn. 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 deter- mining 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 qI and qG are connected to the roadmap depending on the cell in which they lie, and a discrete search is performed.
−
−
If Rn 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
C ⊂
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 S1 or S3 to R or R3, respectively. This mapping removes a single point from each, but the connectivity of free remains unharmed. The antipodal identification problem for unit quaternions represented by S3 also does not present a problem;
C
there is a redundant copy of C, which does not affect the connectivity.
The running time for cylindrical algebraic decomposition depends on many fac- tors, but in general it is polynomial in the number of polynomials in 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.
F
- Canny’s Roadmap Algorithm
The doubly exponential running time of cylindrical algebraic decomposition in- spired 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 de- composition, 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 Rn to R2 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 Rn−1 to R2 are performed on some (n − 1)-dimensional slices of the orig-
inal 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 = Rn. Let = f1, . . . , fm denote the set of polynomials that define the semi-algebraic set, which is assumed to be a disjoint union of manifolds. Assume that each fi Q[x1, . . . , xn]. First, a small perturbation to the input polynomials is performed to ensure that every sign-invariant set of Rn is a manifold. This forces the polynomials into a kind of general position, which
F
∈
C F { }
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 F). At least one of the signs must be 0,
which means that Canny’s roadmap actually lies in ∂ free (this technically is not permitted, but the algorithm nevertheless correctly decides whether a solution
C
path exists through Cfree).
Recall that each fi is a function, fi : Rn R. Let x denote (x1, . . . , xn) Rn. The k polynomials that have zero signs can be put together sequentially to produce a mapping ψ : Rn Rk. The ith component of the vector ψ(x) is ψi(x) = fi(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 : Rn Rj , 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 : Rn → Rk+j denote a mapping constructed directly from ψ and g as follows. For the ith component, if i ≤ k, then hi(x) = ψi(x) = fi(x). Assume that k + j ≤ n. If i > k, then hi(x) = gi−k(x). Let Jx(h) denote the Jacobian of h and
be defined at x as
∂f1(x)
∂x
∂f1(x)
∂x
· · ·
.
. 1
..
. n
.
∂h1(x)
∂x1 · · ·
..
J
(h) =
∂h1(x)
∂xn
..
∂fk(x)
=
∂x1
.
∂fk(x)
· · ·
∂xn
. (6.28)
x .
∂h
.
∂h
(x)
m+k
(x)
∂x1
· · ·
m+k
∂xn
1
∂x1
∂g (x)
∂g (x)
.
.
.
.
∂g (x)
· · ·
1
∂xn
.
.
∂g (x)
j
∂x1
· · ·
j
∂xn
A point x ∈ Rn at which Jx(h) is singular is called a critical point. The matrix is defined to be singular if every (m+k)×(m+k) subdeterminant is zero. Each of the
first k rows of Jx(h) calculates the surface normal to fi(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 f1 define a 2D subset of R3. Let f1 be the unit sphere, S2, defined as the zeros of the polynomial
f1(x1, x2, x3) = x2 + x2 + x2 − 1. (6.29)
1
2
3
Suppose that g : R3 R is defined as g(x1, x2, x3) = x1. The Jacobian, (6.28), becomes
→
（ ＼
2x1 2x2 2x3 (6.30)
1 0 0
and is singular when all three of the possible 2 × 2 subdeterminants are zero. This
occurs if and only if x2 = x3 = 0. This yields the critical points ( 1, 0, 0) and (1, 0, 0) on S2. Note that this is precisely when the surface normals of S2 are parallel to the vector [1 0 0].
−
Now suppose that j = 2 to obtain g : R3 → R2, and suppose g(x1, x2, x3) =
(x1, x2). In this case, (6.28) becomes
2x1 2x2 2x3
1 0 0 , (6.31)
0 1 0
which is singular if and only if x3 = 0. The critical points are therefore the x1x2
plane intersected with S3, which yields the equator points (all (x1, x2) ∈ R2 such
that x2 + x2 = 1). In this case, more points are generated because the matrix
1 2
becomes degenerate for any surface normal of S2 that is parallel to [1 0 0], [0 1 0] 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 S2. Now consider generalizing this example to obtain the
→
full algorithm for general n and k. A linear mapping g : Rn R2 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 g1 denote the
first component of g, which yields a mapping g1 : Rn → R. Forming (6.28) using
g1 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 ∈ Rn, an n − 1-dimensional hyperplane through x is chosen for
which the g1 row of (6.28) is the normal (hence it is perpendicular in some sense to the flow of g1). Inside of this hyperplane, a new g mapping is formed. This time a new direction is chosen, and the mapping takes the form g : Rn−1 R2. 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 R4 and higher involve two or more 2D projections and would therefore be more interesting. An example over R3 is presented here, even though it unfortunately has only one projection; see
[173] for another example over R3.
Example 6.8 (Canny’s Algorithm on a Torus) Consider the 3D algebraic set shown in Figure 6.36. After defining the mapping g(x1, x2, x3) = (x1, x2), the roadmap shown in Figure 6.37 is obtained. The silhouettes are obtained from g, and the critical points are obtained from g1 (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 x2x3 plane and for which the x1 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. ．
To solve a planning problem, the query points qI and qG are artificially declared to be critical points in the top level of recursion. This forces the algorithm to
_x_1
Figure 6.36: Suppose that the semi-algebraic set is a solid torus in R3.
Figure 6.37: The projection into the x1x2 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 x2x3 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.
generate curves that connect them to the rest of the roadmap.
The completeness of the method requires very careful analysis, which is thor- oughly covered in [77, 173]. The main elements of the analysis are showing that:
- the polynomials can be perturbed and g can be chosen to ensure general po- sition, 2) the singularity conditions on (6.28) 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 Cfree (actually it is shown
for ∂ 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].
C