Defining the roadmap

Figure 6.4: The roadmap derived from the vertical cell decomposition.

Figure 6.5: An example solution path.

To handle motion planning queries, a roadmap is constructed from the vertical cell decomposition. For each cell $C_i$, let $q_i$ denote a designated sample point such that $q_i \in C_i$. The sample points can be selected as the cell centroids, but the particular choice is not too important. Let ${\cal G}(V,E)$ be a topological graph defined as follows. For every cell, $C_i$, define a vertex $q_i \in V$. There is a vertex for every 1-cell and every 2-cell. For each 2-cell, define an edge from its sample point to the sample point of every 1-cell that lies along its boundary. Each edge is a line-segment path between the sample points of the cells. The resulting graph is a roadmap, as depicted in Figure 6.4. The accessibility condition is satisfied because every sample point can be reached by a straight-line path thanks to the convexity of every cell. The connectivity condition is also satisfied because ${\cal G}$ is derived directly from the cell decomposition, which also preserves the connectivity of ${\cal C}_{free}$. Once the roadmap is constructed, the cell information is no longer needed for answering planning queries.