Some analysis

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 $ {\cal C}_{free}$, 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) $ V(q)$ is the set of points reachable by the LPM from $ q$. (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.
% latex2html id marker 21492
...y definition & (b) Visibility roadmap \\

Let $ V(q)$ denote the set of all configurations that can be connected to $ q$ 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 $ \epsilon$-goodness of $ {\cal C}_{free}$ is defined as

$\displaystyle \epsilon({\cal C}_{free}) = \min_{q \in {\cal C}_{free}} \bigg\{ \frac{\mu(V(q))}{\mu({\cal C}_{free})} \bigg\},$ (5.41)

in which $ \mu$ represents the measure. Intuitively, $ \epsilon({\cal C}_{free})$ represents the small fraction of $ {\cal C}_{free}$ that is visible from any point. In terms of $ \epsilon$ and the number of vertices in $ {\cal G}$, bounds can be established that yield the probability that a solution will be found [69]. The main difficulties are that the $ \epsilon$-goodness concept is very conservative (it uses worst-case analysis over all configurations), and $ \epsilon$-goodness is defined in terms of the structure of $ {\cal C}_{free}$, 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 2012-04-20