Defining the roadmap

Figure 6.4: The roadmap derived from the vertical cell decomposition.
\begin{figure}\centerline{\psfig{file=figs/vertical6.idr,width=4.5in}}\end{figure}

Figure 6.5: An example solution path.
\begin{figure}\centerline{\psfig{file=figs/vertical4.eps,width=3.5in}}\end{figure}

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.

Steven M LaValle 2020-08-14