![]() |
![]() |
A maximum-clearance roadmap tries to keep as far as possible
from
, as shown for the corridor in Figure 6.8.
The resulting solution paths are sometimes preferred in mobile
robotics applications because it is difficult to measure and control
the precise position of a mobile robot. Traveling along the
maximum-clearance roadmap reduces the chances of collisions due to
these uncertainties. Other names for this roadmap are generalized Voronoi diagram and retraction method
[749]. It is considered as a generalization of the Voronoi
diagram (recall from Section 5.2.2) from the case of
points to the case of polygons. Each point along a roadmap edge is
equidistant from two points on the boundary of
. Each roadmap
vertex corresponds to the intersection of two or more roadmap edges
and is therefore equidistant from three or more points along the
boundary of
.
The retraction term comes from topology and provides a nice intuition
about the method. A subspace is a deformation retract of a
topological space
if the following continuous homotopy,
, can be defined as follows [451]:
To construct the maximum-clearance roadmap, the concept of features from Section 5.3.3 is used again. Let the
feature set refer to the set of all edges and vertices of
. Candidate paths for the roadmap are produced by every pair
of features. This leads to a naive
time algorithm as
follows. For every edge-edge feature pair, generate a line as shown
in Figure 6.9a. For every vertex-vertex pair, generate
a line as shown in Figure 6.9b. The maximum-clearance
path between a point and a line is a parabola. Thus, for every
edge-point pair, generate a parabolic curve as shown in Figure
6.9c. The portions of the paths that actually lie on
the maximum-clearance roadmap are determined by intersecting the
curves. Several algorithms exist that provide better asymptotic
running times [616,626], but they are considerably more
difficult to implement. The best-known algorithm runs in
time in which
is the number of roadmap curves [865].
Steven M LaValle 2020-08-14