5.6.1 The Basic Method

Once again, let $ {\cal G}(V,E)$ represent a topological graph in which $ V$ is a set of vertices and $ E$ is the set of paths that map into $ {\cal C}_{free}$. Under the multiple-query philosophy, motion planning is divided into two phases of computation:

  1. [] Preprocessing Phase: During the preprocessing phase, substantial effort is invested to build $ {\cal G}$ in a way that is useful for quickly answering future queries. For this reason, it is called a roadmap, which in some sense should be accessible from every part of $ {\cal C}_{free}$.
  2. [] Query Phase: During the query phase, a pair, $ {q_{I}}$ and $ {q_{G}}$, is given. Each configuration must be connected easily to $ {\cal G}$ using a local planner. Following this, a discrete search is performed using any of the algorithms in Section 2.2 to obtain a sequence of edges that forms a path from $ {q_{I}}$ to $ {q_{G}}$.

Figure 5.25: The basic construction algorithm for sampling-based roadmaps. Note that $ i$ is not incremented if $ {\alpha }(i)$ is in collision. This forces $ i$ to correctly count the number of vertices in the roadmap.
\begin{figure}BUILD\_ROADMAP \\
1 & ${\cal G}$.init(); $i \...
...25in}}${\cal G}$.add\_edge(${\alpha}(i),q$); \\
\end{tabular} \\\end{figure}

Figure 5.26: The sampling-based roadmap is constructed incrementally by attempting to connect each new sample, $ {\alpha }(i)$, to nearby vertices in the roadmap.

Steven M LaValle 2012-04-20