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^\prime$, in the plane. It is assumed that a $1$-cell (critical curve) in ${\mathbb{R}}^2$ separates them. The task is to connect together $3$-cells in the cylinders above $R$ and $R^\prime$. If neighboring cells share the same feature pair, then they are connected. This means that $\{R,[f_i,f_{i+1}]\}$ and $\{R^\prime,[f_i,f_{i+1}]\}$ must be connected. In some cases, one feature may change, while the interval of orientations remains unchanged. This may happen, 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^\prime$, 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 ${\cal C}_{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.

Figure 6.29: The roadmap corresponding to the example in Figure 6.26.

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 ${\mathbb{R}}^2$ 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].