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
from which the roadmap is consequently derived. Other
methods directly construct a roadmap without the consideration of
cells.

Let be a topological graph (defined in Example
4.6) that maps into
. Furthermore, let
be the swath, which is set of all points reached by
, as defined in (5.40). The graph is called
a *roadmap* if it satisfies two important conditions:

**Accessibility:**From any , it is simple and efficient to compute a path such that and , in which may be any point in . Usually, is the closest point to , assuming is a metric space.**Connectivity-preserving:**Using the first condition, it is always possible to connect some and to some and , respectively, in . The second condition requires that if there exists a path such that and , then there also exists a path , such that and . Thus, solutions are not missed because fails to capture the connectivity of . This ensures that complete algorithms are developed.

Steven M LaValle 2012-04-20