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.

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

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