Cell Decompositions

Section 6.2.2 introduced the vertical cell decomposition to solve the motion plan- ning problem when obs is polygonal. It is important to understand, however, that this is just one choice among many for the decomposition. Some of these choices may not be preferable in 2D; however, they might generalize better to higher dimensions. Therefore, other cell decompositions are covered in this section, to provide a smoother transition from vertical cell decomposition to cylindrical alge- braic decomposition in Section 6.4, which solves the motion planning problem in any dimension for any semi-algebraic model. Along the way, a cylindrical decom- position will appear in Section 6.3.4 for the special case of a line-segment robot in

C

W = R2.

• • 1. General Definitions

In this section, the term complex refers to a collection of cells together with their boundaries. A partition into cells can be derived from a complex, but the complex contains additional information that describes how the cells must fit together. The term cell decomposition still refers to the partition of the space into cells, which is derived from a complex.

It is tempting to define complexes and cell decompositions in a very general manner. Imagine that any partition of Cfree could be called a cell decomposition.

A cell could be so complicated that the notion would be useless. Even free itself could be declared as one big cell. It is more useful to build decompositions out of simpler cells, such as ones that contain no holes. Formally, this requires that every k-dimensional cell is homeomorphic to Bk Rk, an open k-dimensional unit ball. From a motion planning perspective, this still yields cells that are quite complicated, and it will be up to the particular cell decomposition method to enforce further constraints to yield a complete planning algorithm.

C

⊂

Two different complexes will be introduced. The simplicial complex is explained because it is one of the easiest to understand. Although it is useful in many applications, it is not powerful enough to represent all of the complexes that arise in motion planning. Therefore, the singular complex is also introduced. Although it is more complicated to define, it encompasses all of the cell complexes that are of interest in this book. It also provides an elegant way to represent topological spaces. Another important cell complex, which is not covered here, is the CW- complex [439].

Simplicial Complex For this definition, it is assumed that X = Rn. Let p1, p2,

. . ., pk+1, be k + 1 linearly independent5 points in Rn. A k-simplex, [p1, . . . , pk+1], is formed from these points as

（ k+1 I

• αi_p_i ∈ Rn II αi ≥ 0 for all i and

i=1

[p1, . . . , pk+1] =

k+1 _

, (6.3)

[p1, . . . , pk+1] =

, (6.3)

in which αi_p_i is the scalar multiplication of αi by each of the point coordinates. Another way to view (6.3) is as the convex hull of the k + 1 points (i.e., all ways to linearly interpolate between them). If k = 2, a triangular region is obtained. For k = 3, a tetrahedron is produced.

• αi = 1

i=1

For any k-simplex and any i such that 1 i k + 1, let αi = 0. This yields a (k 1)-dimensional simplex that is called a face of the original simplex. A 2- simplex has three faces, each of which is a 1-simplex that may be called an edge. Each 1-simplex (or edge) has two faces, which are 0-simplexes called vertices.

−

×

≤ ≤

≤ ×

5Form k vectors by subtracting p1 from the other k points for some positive integer k such that k n. Arrange the vectors into a k n matrix. For linear independence, there must be at least one k k cofactor with a nonzero determinant. For example, if k = 2, then the three points cannot be collinear.

Not a simplicial complex A simplicial complex

Figure 6.15: To become a simplicial complex, the simplex faces must fit together nicely.

To form a complex, the simplexes must fit together in a nice way. This yields a high-dimensional notion of a triangulation, which in R2 is a tiling composed of triangular regions. A simplicial complex, , is a finite set of simplexes that satisfies the following:

K

• • • 1. Any face of a simplex in K is also in K.
      2. The intersection of any two simplexes in is either a common face of both of them or the intersection is empty.

K

Figure 6.15 illustrates these requirements. For k > 0, a k-cell of K is defined to be interior, int([p1, . . . , pk+1]), of any k-simplex. For k = 0, every 0-simplex is a 0-cell. The union of all of the cells forms a partition of the point set covered by

. This therefore provides a cell decomposition in a sense that is consistent with Section 6.2.2.

K

Singular complex Simplicial complexes are useful in applications such as ge- ometric modeling and computer graphics for computing the topology of models. Due to the complicated topological spaces, implicit, nonlinear models, and de- composition algorithms that arise in motion planning, they are insufficient for the most general problems. A singular complex is a generalization of the simplicial

complex. Instead of being limited to Rn, a singular complex can be defined on any manifold, X (it can even be defined on any Hausdorff topological space). The main difference is that, for a simplicial complex, each simplex is a subset of Rn; however, for a singular complex, each singular simplex is actually a homeomorphism from a (simplicial) simplex in Rn to a subset of X.

To help understand the idea, first consider a 1D singular complex, which hap-

pens to be a topological graph (as introduced in Example 4.6). The interval [0, 1] is a 1-simplex, and a continuous path τ : [0, 1] X is a singular 1-simplex be- cause it is a homeomorphism of [0, 1] to the image of τ in X. Suppose (V, E) is a topological graph. The cells are subsets of X that are defined as follows. Each

G

→

point v ∈ V is a 0-cell in X. To follow the formalism, each is considered as the

image of a function f : {0} → X, which makes it a singular 0-simplex, because

{0} is a 0-simplex. For each path τ ∈ E, the corresponding 1-cell is

{x ∈ X | τ (s) = x for some s ∈ (0, 1)}. (6.4)

Expressed differently, it is τ ((0, 1)), the image of the path τ , except that the endpoints are removed because they are already covered by the 0-cells (the cells must form a partition).

These principles will now be generalized to higher dimensions. Since all balls and simplexes of the same dimension are homeomorphic, balls can be used instead of a simplex in the definition of a singular simplex. Let Bk Rk denote a closed,

⊂

• 1. imensional unit ball,

Dk = {x ∈ Rn | IxI ≤ 1}, (6.5)

in which is the Euclidean norm. A singular k-simplex is a continuous mapping σ : Dk X. Let int(Dk) refer to the interior of Dk. For k 1, the k-cell, C, corresponding to a singular k-simplex, σ, is the image C = σ(int(Dk)) X. The 0-cells are obtained directly as the images of the 0 singular simplexes. Each singular 0-simplex maps to the 0-cell in X. If σ is restricted to int(Dk), then it actually defines a homeomorphism between Dk and C. Note that both of these are open sets if k > 0.

⊆

→ ≥

I· I

A simplicial complex requires that the simplexes fit together nicely. The same

concept is applied here, but topological concepts are used instead because they are more general. Let K be a set of singular simplexes of varying dimensions. Let

Sk denote the union of the images of all singular i-simplexes for all i k.

≤

A collection of singular simplexes that map into a topological space X is called a singular complex if:

• • 1. For each dimension k, the set Sk X must be closed. This means that the cells must all fit together nicely.

⊆

• • 1. Each k-cell is an open set in the topological subspace Sk. Note that 0-cells are open in S0, even though they are usually closed in X.

Example 6.1 (Vertical Decomposition) The vertical decomposition of Sec- tion 6.2.2 is a nice example of a singular complex that is not a simplicial complex because it contains trapezoids. The interior of each trapezoid and triangle forms a 2-cell, which is an open set. For every pair of adjacent 2-cells, there is a 1-cell on

their common boundary. There are no 0-cells because the vertices lie in Cobs, not in Cfree. The subspace S2 is formed by taking the union of all 2-cells and 1-cells to yield S2 = Cfree. This satisfies the closure requirement because the complex is built in Cfree only; hence, the topological space is Cfree. The set S2 = Cfree is both

open and closed. The set S1 is the union of all 1-cells. This is also closed because the 1-cell endpoints all lie in obs. Each 1-cell is also an open set.

C

One way to avoid some of these strange conclusions from the topology restricted to Cfree is to build the vertical decomposition in cl(Cfree), the closure of Cfree. This

can be obtained by starting with the previously defined vertical decomposition and adding a new 1-cell for every edge of obs and a 0-cell for every vertex of obs. Now

C C

S3 = cl( free), which is closed in R2. Likewise, S2, S1, and S0, are closed in the

C

usual way. Each of the individual k-dimensional cells, however, is open in the

topological space Sk. The only strange case is that the 0-cells are considered open, but this is true in the discrete topological space S0. ．

• • 1. 2D Decompositions

The vertical decomposition method of Section 6.2.2 is just one choice of many cell decomposition methods for solving the problem when obs is polygonal. It provides a nice balance between the number of cells, computational efficiency, and implementation ease. It is usually possible to decompose obs into far fewer convex cells. This would be preferable for multiple-query applications because the roadmap would be smaller. It is unfortunately quite difficult to optimize the number of cells. Determining the decomposition of a polygonal obs with holes that uses the smallest number of convex cells is NP-hard [519, 645]. Therefore, we are willing to tolerate nonoptimal decompositions.

C

C

C

Triangulation One alternative to the vertical decomposition is to perform a

triangulation, which yields a simplicial complex over Cfree. Figure 6.16 shows an

example. Since free is an open set, there are no 0-cells. Each 2-simplex (triangle) has either one, two, or three faces, depending on how much of its boundary is shared with obs. A roadmap can be made by connecting the samples for 1-cells and 2-cells as shown in Figure 6.17. Note that there are many ways to triangulate free for a given problem. Finding good triangulations, which for example means trying to avoid thin triangles, is given considerable attention in computational geometry [129, 264, 302].

C

C

C

Figure 6.16: A triangulation of Cfree.

Figure 6.17: A roadmap obtained from the triangulation.

How can the triangulation be computed? It might seem tempting to run the vertical decomposition algorithm of Section 6.2.2 and split each trapezoid into two triangles. Even though this leads to triangular cells, it does not produce a simplicial complex (two triangles could abut the same side of a triangle edge). A naive approach is to incrementally split faces by attempting to connect two vertices of a face by a line segment. If this segment does not intersect other segments, then the split can be made. This process can be iteratively performed over all vertices of faces that have more than three vertices, until a triangulation is eventually obtained. Unfortunately, this results in an O(n3) time algorithm because O(n2) pairs must be checked in the worst case, and each check requires O(n) time to determine whether an intersection occurs with other segments. This can be easily

reduced to O(n2 lg n) by performing radial sweeping. Chapter 3 of [264] presents an algorithm that runs in O(n lg n) time by first partitioning Cfree into monotone

polygons, and then efficiently triangulating each monotone polygon. If free is simply connected, then, surprisingly, a triangulation can be computed in linear time [190]. Unfortunately, this algorithm is too complicated to use in practice (there are, however, simpler algorithms for which the complexity is close to O(n); see [90] and the end of Chapter 3 of [264] for surveys).

C

Cylindrical decomposition The cylindrical decomposition is very similar to the vertical decomposition, except that when any of the cases in Figure 6.2 occurs, then a vertical line slices through all faces, all the way from y = to y = . The result is shown in Figure 6.18, which may be considered as a singular complex. This may appear very inefficient in comparison to the vertical decomposition; however, it is presented here because it generalizes nicely to any dimension, any C-space topology, and any semi-algebraic model. Therefore, it is presented here to ease

−∞ ∞

b

0 1 2 3 4 5 6 7 8 9 10 11 12 13

Figure 6.18: The cylindrical decomposition differs from the vertical decomposition in that the rays continue forever instead of stopping at the nearest edge. Compare this figure to Figure 6.6.

the transition to more general decompositions. The most important property of

the cylindrical decomposition is shown in Figure 6.19. Consider each vertical strip between two events. When traversing a strip from y = −∞ to y = ∞, the points alternate between being Cobs and Cfree. For example, between events 4 and 5, the points below edge f are in Cfree. Points between f and g lie in Cobs. Points between g and h lie in Cfree, and so forth. The cell decomposition can be defined so that

2D cells are also created in obs. Let S(x, y) denote the logical predicate (3.6) from Section 3.1.1. When traversing a strip, the value of S(x, y) also alternates. This behavior is the main reason to construct a cylindrical decomposition, which will become clearer in Section 6.4.2. Each vertical strip is actually considered to be a cylinder, hence, the name cylindrical decomposition (i.e., there are not necessarily any cylinders in the 3D geometric sense).

C

• • 1. 3D Vertical Decomposition

It turns out that the vertical decomposition method of Section 6.2.2 can be ex- tended to any dimension by recursively applying the sweeping idea. The method requires, however, that obs is piecewise linear. In other words, obs is represented as a semi-algebraic model for which all primitives are linear. Unfortunately, most of the general motion planning problems involve nonlinear algebraic primitives because of the nonlinear transformations that arise from rotations. Recall the

C C

b

0 1 2 3 4 5 6 7 8 9 10 11 12 13

Figure 6.19: The cylindrical decomposition produces vertical strips. Inside of a strip, there is a stack of collision-free cells, separated by Cobs.

complicated algebraic obs model constructed in Section 4.3.3. To handle generic algebraic models, powerful techniques from computational algebraic geometry are needed. This will be covered in Section 6.4.

C

One problem for which Cobs is piecewise linear is a polyhedral robot that can translate in R3, and the obstacles in W are polyhedra. Since the transformation equations are linear in this case, Cobs ⊂ R3 is polyhedral. The polygonal faces of

obs are obtained by forming geometric primitives for each of the Type FV, Type VF, and Type EE cases of contact between and , as mentioned in Section 4.3.2.

A O

C

Figure 6.20 illustrates the algorithm that constructs the 3D vertical decompo- sition. Compare this to the algorithm in Section 6.2.2. Let (x, y, z) denote a point in = R3. The vertical decomposition yields convex 3-cells, 2-cells, and 1-cells. Neglecting degeneracies, a generic 3-cell is bounded by six planes. The cross sec- tion of a 3-cell for some fixed x value yields a trapezoid or triangle, exactly as in the 2D case, but in a plane parallel to the yz plane. Two sides of a generic 3-cell are parallel to the yz plane, and two other sides are parallel to the xz plane. The

C

3-cell is bounded above and below by two polygonal faces of Cobs.

Initially, sort the obs vertices by their x coordinate to obtain the events. Now consider sweeping a plane perpendicular to the x-axis. The plane for a fixed value of x produces a 2D polygonal slice of obs. Three such slices are shown at the bottom of Figure 6.20. Each slice is parallel to the yz plane and appears to look exactly like a problem that can be solved by the 2D vertical decomposition method.

C

C

z

x

z z z

y y y

Figure 6.20: In higher dimensions, the sweeping idea can be applied recursively.

The 2-cells in a slice are actually slices of 3-cells in the 3D decomposition. The only places in which these 3-cells can critically change is when the sweeping plane stops at some x value. The center slice in Figure 6.20 corresponds to the case in which a vertex of a convex polyhedron is encountered, and all of the polyhedron lies to right of the sweep plane (i.e., the rest of the polyhedron has not been encountered yet). This corresponds to a place where a critical change must occur in the slices. These are 3D versions of the cases in Figure 6.2, which indicate how the vertical decomposition needs to be updated. The algorithm proceeds by first building the 2D vertical decomposition at the first x event. At each event, the 2D vertical decomposition must be updated to take into account the critical changes. During this process, the 3D cell decomposition and roadmap can be incrementally constructed, as in the 2D case.

The roadmap is constructed by placing a sample point in the center of each 3-cell and 2-cell. The vertices are the sample points, and edges are added to the roadmap by connecting the sample points for each case in which a 3-cell is adjacent to a 2-cell.

This same principle can be extended to any dimension, but the applications to

Figure 6.21: Motion planning for a line segment that can translate and rotate in a 2D world.

motion planning are limited because the method requires linear models (or at least it is very challenging to adapt to nonlinear models; in some special cases, this can be done). See [426] for a summary of the complexity of vertical decompositions for various geometric primitives and dimensions.

• • 1. A Decomposition for a Line-Segment Robot

This section presents one of the simplest cell decompositions that involves nonlin- ear models, yet it is already fairly complicated. This will help to give an appreci-

ation of the difficulty of combinatorial planning in general. Consider the planning problem shown in Figure 6.21. The robot, A, is a single line segment that can translate or rotate in W = R2. The dot on one end of A is used to illustrate its origin and is not part of the model. The C-space, C, is homeomorphic to R2 × S1. Assume that the parameterization R2 × [0, 2π]/ ∼ is used in which the identification equates θ = 0 and θ = 2π. A point in C is represented as (x, y, θ).

An approximate solution First consider making a cell decomposition for the

case in which the segment can only translate. The method from Section 4.3.2 can be used to compute Cobs by treating the robot-obstacle interaction with Type EV and Type VE contacts. When the interior of A touches an obstacle vertex, then Type EV is obtained. An endpoint of A touching an object interior yields Type

VE. Each case produces an edge of obs, which is polygonal. Once this is repre- sented, the vertical decomposition can be used to solve the problem. This inspires a reasonable numerical approach to the rotational case, which is to discretize θ

C

into K values, i∆θ, for 0 ≤ i ≤ K, and ∆θ = 2π/K [20]. The obstacle region,

obs, is polygonal for each case, and we can imagine having a stack of K polyg- onal regions. A roadmap can be formed by connecting sampling points inside of a slice in the usual way, and also by connecting samples between corresponding cells in neighboring slices. If K is large enough, this strategy works well, but the method is not complete because a sufficient value for K cannot be determined in

C

_v_1

_e_2

1. (b)

Figure 6.22: Fix (x, y) and swing the segment around for all values of θ

∈

[0, 2π]/ . (a) Note the vertex and edge features that are hit by the segment.

∼

1. Record orientation intervals over which the robot is not in collision.

advance. The method is actually an interesting hybrid between combinatorial and sampling-based motion planning. A resolution-complete version can be imagined.

In the limiting case, as K tends to infinity, the surfaces of obs become curved along the θ direction. The conditions in Section 4.3.3 must be applied to gen- erate the actual obstacle regions. This is possible, but it yields a semi-algebraic representation of obs in terms of implicit polynomial primitives. It is no easy task to determine an explicit representation in terms of simple cells that can be used for motion planning. The method of Section 6.3.3 cannot be used because obs is not polyhedral. Therefore, special analysis is warranted to produce a cell decomposition.

C

C

C

The general idea is to construct a cell decomposition in R2 by considering only the translation part, (x, y). Each cell in R2 is then lifted into by considering θ as a third axis that is “above” the xy plane. A cylindrical decomposition results in

C

which each cell in the xy plane produces a cylindrical stack of cells for different θ values. Recall the cylinders in Figures 6.18 and 6.19. The vertical axis corresponds to θ in the current setting, and the horizontal axis is replaced by two axes, x and y.

To construct the decomposition in R2, consider the various robot-obstacle con- tacts shown in Figure 6.22. In Figure 6.22a, the segment swings around from a fixed (x, y). Two different kinds of contacts arise. For some orientation (value of θ), the segment contacts v1, forming a Type EV contact. For three other orienta- tions, the segment contacts an edge, forming Type VE contacts. Once again using the feature concept, there are four orientations at which the segment contacts a

feature. Each feature may be either a vertex or an edge. Between the two contacts with e2 and e3, the robot is not in collision. These configurations lie in Cfree. Also,

configurations for which the robot is between contacts e3 (the rightmost contact) and v1 are also in Cfree. All other orientations produce configurations in Cobs. Note

that the line segment cannot get from being between e2 and e3 to being between

• 1. (b)

Figure 6.23: If x is increased enough, a critical change occurs in the radar map because v1 can no longer be reached by the robot.

e3 and v1, unless the (x, y) position is changed. It therefore seems sensible that these must correspond to different cells in whatever decomposition is made.

Radar maps Figure 6.22b illustrates which values of θ produce collision. We will refer to this representation as a radar map. The four contact orientations are indicated by the contact feature. The notation [e3, v1] and [e2, e3] identifies the two intervals for which (x, y, θ) free. Now imagine changing (x, y) by a small amount, to obtain (x′, y′). How would the radar map change? The precise angles at which the contacts occur would change, but the notation [e3, v1] and [e2, e3], for configurations that lie in free, remains unchanged. Even though the angles change, there is no interesting change in terms of the contacts; therefore, it makes sense to declare (x, y, θ) and (x, y, θ′) to lie in the same cell in free because θ and θ′ both place the segment between the same contacts. Imagine a column of two 3-cells above a small area around (x, y). One 3-cell is for orientations in [e3, v1], and the other is for orientations in [e2, e3]. These appear to be 3D regions in free because each of x, y, and θ can be perturbed a small amount without leaving the cell.

C

C

C

∈ C

Of course, if (x, y) is changed enough, then eventually we expect a dramatic change to occur in the radar map. For example, imagine e3 is infinitely long, and the x value is gradually increased in Figure 6.22a. The black band between v1 and e2 in Figure 6.22b shrinks in length. Eventually, when the distance from (x′, y′) to v1 is greater than the length of , the black band disappears. This situation is shown in Figure 6.23. The change is very important to notice because after that region vanishes, any orientation θ′ between e3 and e3, traveling the long way around the circle, produces a configuration (x′, y′, θ′) free. This seems very important because it tells us that we can travel between the original two cells by moving the robot further way from v1, rotating the robot, and then moving back. Now move from the position shown in Figure 6.23 into the positive y direction. The remaining black band begins to shrink and finally disappears when the distance

A

∈ C

to e3 is further than the robot length. This represents another critical change.

The radar map can be characterized by specifying a circular ordering

([f1, f2], [f3, f4], [f5, f6], . . . , [f2k−1, f2k]), (6.6)

when there are k orientation intervals over which the configurations lie in Cfree. For the radar map in Figure 6.22b, this representation yields ([e3, v1], [e2, e3]). Each fi is a feature, which may be an edge or a vertex. Some of the fi may be identical; the representation for Figure 6.23b is ([e3, e3]). The intervals are specified in counterclockwise order around the radar map. Since the ordering is circular, it does not matter which interval is specified first. There are two degenerate cases.

If (x, y, θ) ∈ Cfree for all θ ∈ [0, 2π), then we write () for the ordering. On the other hand, if (x, y, θ) ∈ Cobs for all θ ∈ [0, 2π), then we write ∅.

Critical changes in cells Now we are prepared to explain the cell decompo- sition in more detail. Imagine traveling along a path in R2 and producing an animated version of the radar map in Figure 6.22b. We say that a critical change occurs each time the circular ordering representation of (6.6) changes. Changes occur when intervals: 1) appear, 2) disappear, 3) split apart, 4) merge into one, or 5) when the feature of an interval changes. The first task is to partition R2 into

maximal 2-cells over which no critical changes occur. Each one of these 2-cells, R, represents the projection of a strip of 3-cells in Cfree. Each 3-cell is defined as follows. Let {R, [fi, fi+1]} denote the 3D region in Cfree for which (x, y) ∈ R and

θ places the segment between contacts fi and fi+1. The cylinder of cells above R is given by R, [fi, fi+1] for each interval in the circular ordering representation, (6.6). If any orientation is possible because never contacts an obstacle while in R, then we write R .

{ }

A

{ }

What are the positions in R2 that cause critical changes to occur? It turns out that there are five different cases to consider, each of which produces a set of critical curves in R2. When one of these curves is crossed, a critical change occurs. If none of these curves is crossed, then no critical change can occur. Therefore, these curves precisely define the boundaries of the desired 2-cells in R2. Let L denote the length of the robot (which is the line segment).

Consider how the five cases mentioned above may occur. Two of the five cases have already been observed in Figures 6.22 and 6.23. These appear in Figures 6.24a and Figures 6.24b, and occur if (x, y) is within L of an edge or a vertex. The third and fourth cases are shown in Figures 6.24c and 6.24d, respectively. The third case occurs because crossing the curve causes to change between being able to touch e and being able to touch v. This must be extended from any edge at an endpoint that is a reflex vertex (interior angle is greater than π). The fourth case is actually a return of the bitangent case from Figure 6.10, which arose for the shortest path graph. If the vertices are within L of each other, then a linear

A

critical curve is generated because A is no longer able to touch v2 when crossing it

from right to left. Bitangents always produce curves in pairs; the curve above v2 is not shown. The final case, shown in Figure 6.25, is the most complicated. It is a

(a) (b)

(c) (d)

Figure 6.24: Four of the five cases that produce critical curves in R2. fourth-degree algebraic curve called the Conchoid of Nicomedes, which arises from

being in simultaneous contact between v and e. Inside of the teardrop-shaped curve, can contact e but not v. Just outside of the curve, it can touch v. If the xy coordinate frame is placed so that v is at (0, 0), then the equation of the curve is

A

A

(x2 − y2)(y + d)2 − y2L2 = 0, (6.7)

in which d is the distance from v to e.

Putting all of the curves together generates a cell decomposition of R2. There are noncritical regions, over which there is no change in (6.6); these form the 2- cells. The boundaries between adjacent 2-cells are sections of the critical curves

Figure 6.25: The fifth case is the most complicated. It results in a fourth-degree algebraic curve called the Conchoid of Nicomedes.

_R_5 _x_2

Figure 6.26: The critical curves form the boundaries of the noncritical regions in

R2.

and form 1-cells. There are also 0-cells at places where critical curves intersect. Figure 6.26 shows an example adapted from [588]. Note that critical curves are not drawn if their corresponding configurations are all in obs. The method still works

C

correctly if they are included, but unnecessary cell boundaries are made. Just for fun, they could be used to form a nice cell decomposition of Cobs, in addition to

free. Since obs is avoided, is seems best to avoid wasting time on decomposing it. These unnecessary cases can be detected by imagining that is a laser with range L. As the laser sweeps around, only features that are contacted by the laser are relevant. Any features that are hidden from view of the laser correspond to unnecessary boundaries.

A

C C

After the cell decomposition has been constructed in R2, it needs to be lifted into R2 [0, 2π]/ . This generates a cylinder of 3-cells above each 2D noncritical region, R. The roadmap could easily be defined to have a vertex for every 3-cell

× ∼

and 2-cell, which would be consistent with previous cell decompositions; however, vertices at 2-cells are not generated here to make the coming example easier to understand. Each 3-cell, R, [fi, fi+1] , corresponds to the vertex in a roadmap. The roadmap edges connect neighboring 3-cells that have a 2-cell as part of their common boundary. This means that in R2 they share a one-dimensional portion of a critical curve.

{ }

Constructing the roadmap The problem is to determine which 3-cells are actually adjacent. Figure 6.27 depicts the cases in which connections need to be made. The xy plane is represented as one axis (imagine looking in a direction parallel to it). Consider two neighboring 2-cells (noncritical regions), R and R′, in the plane. It is assumed that a 1-cell (critical curve) in R2 separates them. The

R R′

xy plane

Figure 6.27: Connections are made between neighboring 3-cells that lie above neighboring noncritical regions.

task is to connect together 3-cells in the cylinders above R and R′. If neighbor- ing cells share the same feature pair, then they are connected. This means that R, [fi, fi+1] and R′, [fi, fi+1] must be connected. In some cases, one feature may change, while the interval of orientations remains unchanged. This may hap- pen, for example, when the robot changes from contacting an edge to contacting a vertex of the edge. In these cases, a connection must also be made. One case illustrated in Figure 6.27 is when a splitting or merging of orientation intervals occurs. Traveling from R to R′, the figure shows two regions merging into one. In this case, connections must be made from each of the original two 3-cells to the merged 3-cell. When constructing the roadmap edges, sample points of both the 3-cells and 2-cells should be used to ensure collision-free paths are obtained, as in the case of the vertical decomposition in Section 6.2.2. Figure 6.28 depicts the cells for the example in Figure 6.26. Each noncritical region has between one and three cells above it. Each of the various cells is indicated by a shortened robot that points in the general direction of the cell. The connections between the cells are also shown. Using the noncritical region and feature names from Figure 6.26, the resulting roadmap is depicted abstractly in Figure 6.29. Each vertex represents a 3-cell in free, and each edge represents the crossing of a 2-cell between adjacent 3-cells. To make the roadmap consistent with previous roadmaps, we could insert a vertex into every edge and force the path to travel through the sample point of the corresponding 2-cell.

C

{ } { }

Once the roadmap has been constructed, it can be used in the same way as other roadmaps in this chapter to solve a query. Many implementation details have been neglected here. Due to the fifth case, some of the region boundaries in R2 are

fourth-degree algebraic curves. Ways to prevent the explicit characterization of

every noncritical region boundary, and other implementation details, are covered in [56]. Some of these details are also summarized in [588].

_R_5 _x_2

Figure 6.28: A depiction of the 3-cells above the noncritical regions. Sample rod orientations are shown for each cell (however, the rod length is shortened for clarity). Edges between cells are shown in Figure 6.29.

Complexity How many cells can there possibly be in the worst case? First count the number of noncritical regions in R2. There are O(n) different ways to generate critical curves of the first three types because each corresponds to a single feature. Unfortunately, there are O(n2) different ways to generate bitangents and the Conchoid of Nicomedes because these are based on pairs of features. Assuming

no self-intersections, a collection of O(n2) curves in R2, may intersect to generate at most O(n4) regions. Above each noncritical region in R2, there could be a cylinder of O(n) 3-cells. Therefore, the size of the cell decomposition is O(n5) in the worst

case. In practice, however, it is highly unlikely that all of these intersections will occur, and the number of cells is expected to be reasonable. In [851], an O(n5)-time algorithm is given to construct the cell decomposition. Algorithms that have much better running time are mentioned in Section 6.5.3, but they are more complicated to understand and implement.