There have been many works that analyze the performance of
sampling-based roadmaps. The basic idea from one of them
[69] is briefly presented here. Consider
problems such as the one in Figure 5.27, in which the CONNECT method will mostly likely fail in the thin tube, even though
a connection exists. The higher dimensional versions of these
problems are even more difficult. Many planning problems involve
moving a robot through an area with tight clearance. This generally
causes narrow channels to form in
, which leads to a
challenging planning problem for the sampling-based roadmap algorithm.
Finding the escape of a bug trap is also challenging, but for the
roadmap methods, even traveling through a single corridor is hard
(unless more sophisticated LPMs are used
[479]).
Figure 5.27:
An example such as this is difficult for
sampling-based roadmaps (in higher dimensional C-spaces) because
some samples must fall along many points in the curved tube. Other
methods, however, may be able to easily solve it.
|
Figure 5.28:
(a) is the set of points reachable
by the LPM from . (b) A visibility
roadmap has two kinds of vertices: guards, which are shown in black,
and connectors, shown in white. Guards are not allowed to see other
guards. Connectors must see at least two guards.
|
Let denote the set of all configurations that can be connected
to using the CONNECT method. Intuitively, this is
considered as the set of all configurations that can be ``seen'' using
line-of-sight visibility, as shown in Figure 5.28a
The -goodness of
is defined as
|
(5.41) |
in which represents the measure. Intuitively,
represents the small fraction of
that is
visible from any point. In terms of and the number of
vertices in , bounds can be established that yield the probability
that a solution will be found [69]. The main
difficulties are that the -goodness concept is very
conservative (it uses worst-case analysis over all configurations),
and -goodness is defined in terms of the structure of
, which cannot be computed efficiently. This result and other
related results help to gain a better understanding of sampling-based
planning, but such bounds are difficult to apply to particular
problems to determine whether an algorithm will perform well.
Steven M LaValle
2020-08-14