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.

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.