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.
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