#### Defining the roadmap

To handle motion planning queries, a roadmap is constructed from the vertical cell decomposition. For each cell , let denote a designated sample point such that . The sample points can be selected as the cell centroids, but the particular choice is not too important. Let be a topological graph defined as follows. For every cell, , define a vertex . 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 is derived directly from the cell decomposition, which also preserves the connectivity of . Once the roadmap is constructed, the cell information is no longer needed for answering planning queries.

Steven M LaValle 2012-04-20