Roadmaps

Virtually all combinatorial motion planning approaches construct a roadmap along the way to solving queries. This notion was introduced in Section 5.6, but in this chapter stricter requirements are imposed in the roadmap definition because any algorithm that constructs one needs to be complete. Some of the algorithms in this chapter first construct a cell decomposition of ${\cal C}_{free}$ from which the roadmap is consequently derived. Other methods directly construct a roadmap without the consideration of cells.

Let ${\cal G}$ be a topological graph (defined in Example 4.6) that maps into ${\cal C}_{free}$. Furthermore, let $S \subset {\cal C}_{free}$ be the swath, which is set of all points reached by ${\cal G}$, as defined in (5.40). The graph ${\cal G}$ is called a roadmap if it satisfies two important conditions:

1. Accessibility: From any $q \in {\cal C}_{free}$, it is simple and efficient to compute a path $\tau: [0,1] \rightarrow {\cal C}_{free}$ such that $\tau(0) = q$ and $\tau(1) = s$, in which $s$ may be any point in $S$. Usually, $s$ is the closest point to $q$, assuming ${\cal C}$ is a metric space.
2. Connectivity-preserving: Using the first condition, it is always possible to connect some ${q_{I}}$ and ${q_{G}}$ to some $s_1$ and $s_2$, respectively, in $S$. The second condition requires that if there exists a path $\tau: [0,1] \rightarrow {\cal C}_{free}$ such that $\tau(0) = {q_{I}}$ and $\tau(1) = {q_{G}}$, then there also exists a path $\tau^\prime: [0,1] \rightarrow S$, such that $\tau^\prime(0) = s_1$ and $\tau^\prime(1) = s_2$. Thus, solutions are not missed because ${\cal G}$ fails to capture the connectivity of ${\cal C}_{free}$. This ensures that complete algorithms are developed.

By satisfying these properties, a roadmap provides a discrete representation of the continuous motion planning problem without losing any of the original connectivity information needed to solve it. A query, $({q_{I}},{q_{G}})$, is solved by connecting each query point to the roadmap and then performing a discrete graph search on ${\cal G}$. To maintain completeness, the first condition ensures that any query can be connected to ${\cal G}$, and the second condition ensures that the search always succeeds if a solution exists.