4.3.3 Explicitly Modeling : The General Case

Unfortunately, the cases in which is polygonal or polyhedral are quite limited. Most problems yield extremely complicated C-space obstacles. One good point is that can be expressed using semi-algebraic models, for any robots and obstacles defined using semi-algebraic models, even after applying any of the transformations from Sections 3.2 to 3.4. It might not be true, however, for other kinds of transformations, such as warping a flexible material [32,577].

Consider the case of a convex polygonal robot and a convex polygonal obstacle in a 2D world. Assume that any transformation in may be applied to ; thus, and . The task is to define a set of algebraic primitives that can be combined to define . Once again, it is important to distinguish between Type EV and Type VE contacts. Consider how to construct the algebraic primitives for the Type EV contacts; Type VE can be handled in a similar manner.

For the translation-only case, we were able to determine all of the Type EV contacts by sorting the edge normals. With rotation, the ordering of edge normals depends on . This implies that the applicability of a Type EV contact depends on , the robot orientation. Recall the constraint that the inward normal of must point between the outward normals of the edges of that contain the vertex of contact, as shown in Figure 4.21. This constraint can be expressed in terms of inner products using the vectors and . The statement regarding the directions of the normals can equivalently be formulated as the statement that the angle between and , and between and , must each be less than . Using inner products, this implies that and . As in the translation case, the condition is required for contact. Observe that now depends on . For any , if , , and , then . Let denote the set of configurations that satisfy these conditions. These conditions imply that a point is in . Furthermore, any other Type EV and Type VE contacts could imply that more points are in . Ordinarily, , which implies that the complement, , is a superset of (thus, ). Let . Using the primitives

 (4.39)

 (4.40)

and

 (4.41)

let .

It is known that , but may contain points in . The situation is similar to what was explained in Section 3.1.1 for building a model of a convex polygon from half-planes. In the current setting, it is only known that any configuration outside of must be in . If is intersected with all other corresponding sets for each possible Type EV and Type VE contact, then the result is . Each contact has the opportunity to remove a portion of from consideration. Eventually, enough pieces of are removed so that the only configurations remaining must lie in . For any Type EV contact, . A similar statement can be made for Type VE contacts. A logical predicate, similar to that defined in Section 3.1.1, can be constructed to determine whether in time that is linear in the number of primitives.

One important issue remains. The expression is not a polynomial because of the and terms in the rotation matrix of . If polynomials could be substituted for these expressions, then everything would be fixed because the expression of the normal vector (not a unit normal) and the inner product are both linear functions, thereby transforming polynomials into polynomials. Such a substitution can be made using stereographic projection (see [588]); however, a simpler approach is to use complex numbers to represent rotation. Recall that when is used to represent rotation, each rotation matrix in is represented as (4.18), and the homogeneous transformation matrix becomes

 (4.42)

Using this matrix to transform a point results in the point coordinates . Thus, any transformed point on is a linear function of , , , and .

This was a simple trick to make a nice, linear function, but what was the cost? The dependency is now on and instead of . This appears to increase the dimension of from 3 to 4, and . However, an algebraic primitive must be added that constrains and to lie on the unit circle.

By using complex numbers, primitives in are obtained for each Type EV and Type VE contact. By defining , the following algebraic primitives are obtained for a Type EV contact:

 (4.43)

 (4.44)

and

 (4.45)

This yields . To preserve the correct topology of , the set

 (4.46)

is intersected with . The set remains fixed over all Type EV and Type VE contacts; therefore, it only needs to be considered once.

Example 4..16 (A Nonlinear Boundary for )   Consider adding rotation to the model described in Example 4.15. In this case, all possible contacts between pairs of edges must be considered. For this example, there are Type EV contacts and Type VE contacts. Each contact produces algebraic primitives. With the inclusion of , this simple example produces primitives! Rather than construct all of these, we derive the primitives for a single contact. Consider the Type VE contact between and -. The outward edge normal remains fixed at . The vectors and are derived from the edges adjacent to , which are - and -. Note that each of , , and depend on the configuration. Using the 2D homogeneous transformation (3.35), at configuration is . Using to represent rotation, the expression of becomes . The expressions of and are and , respectively. It follows that and . Note that and depend only on the orientation of , as expected. Assume that is drawn from to . This yields . The inner products , , and can easily be computed to form , , and as algebraic primitives.

One interesting observation can be made here. The only nonlinear primitive is . Therefore, can be considered as a linear polytope (like a polyhedron, but one dimension higher) in that is intersected with a cylinder.

Subsections
Steven M LaValle 2012-04-20