Now we are prepared to explain the cell decomposition in more detail. Imagine traveling along a path in 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 into maximal -cells over which no critical changes occur. Each one of these -cells, , represents the projection of a strip of -cells in . Each -cell is defined as follows. Let denote the 3D region in for which and places the segment between contacts and . The cylinder of cells above is given by for each interval in the circular ordering representation, (6.6). If any orientation is possible because never contacts an obstacle while in , then we write .
What are the positions in 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 . 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 -cells in . Let 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 is within 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 and being able to touch . 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 of each other, then a linear critical curve is generated because is no longer able to touch when crossing it from right to left. Bitangents always produce curves in pairs; the curve above is not shown. The final case, shown in Figure 6.25, is the most complicated. It is a fourth-degree algebraic curve called the Conchoid of Nicomedes, which arises from being in simultaneous contact between and . Inside of the teardrop-shaped curve, can contact but not . Just outside of the curve, it can touch . If the coordinate frame is placed so that is at , then the equation of the curve is
Putting all of the curves together generates a cell decomposition of . There are noncritical regions, over which there is no change in (6.6); these form the -cells. The boundaries between adjacent -cells are sections of the critical curves and form -cells. There are also 0-cells at places where critical curves intersect. Figure 6.26 shows an example adapted from . Note that critical curves are not drawn if their corresponding configurations are all in . The method still works 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 , in addition to . Since 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 . 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.
After the cell decomposition has been constructed in , it needs to be lifted into . This generates a cylinder of -cells above each 2D noncritical region, . The roadmap could easily be defined to have a vertex for every -cell and -cell, which would be consistent with previous cell decompositions; however, vertices at -cells are not generated here to make the coming example easier to understand. Each -cell, , corresponds to the vertex in a roadmap. The roadmap edges connect neighboring -cells that have a -cell as part of their common boundary. This means that in they share a one-dimensional portion of a critical curve.
Steven M LaValle 2012-04-20