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:

1. 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.
2. 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.
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, , is solved by connecting each query point to the roadmap and then performing a discrete graph search on . To maintain completeness, the first condition ensures that any query can be connected to , and the second condition ensures that the search always succeeds if a solution exists.

Steven M LaValle 2020-08-14