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

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 2012-04-20