Chapter 5
Sampling-Based Motion Planning
There are two main philosophies for addressing the motion planning problem, in Formulation 4.1 from Section 4.3.1. This chapter presents one of the philosophies, sampling-based motion planning, which is outlined in Figure 5.1. The main idea is to avoid the explicit construction of obs, as described in Section 4.3, and instead conduct a search that probes the C-space with a sampling scheme. This probing is enabled by a collision detection module, which the motion planning algorithm considers as a “black box.” This enables the development of planning algorithms that are independent of the particular geometric models. The collision detection module handles concerns such as whether the models are semi-algebraic sets, 3D triangles, nonconvex polyhedra, and so on. This general philosophy has been very successful in recent years for solving problems from robotics, manufacturing, and biological applications that involve thousands and even millions of geometric prim-
C
itives. Such problems would be practically impossible to solve using techniques that explicitly represent Cobs.
Notions of completeness It is useful to define several notions of complete- ness for sampling-based algorithms. These algorithms have the drawback that they result in weaker guarantees that the problem will be solved. An algorithm is considered complete if for any input it correctly reports whether there is a so-
Figure 5.1: The sampling-based planning philosophy uses collision detection as a “black box” that separates the motion planning from the particular geometric and kinematic models. C-space sampling and discrete planning (i.e., searching) are performed.
185
lution in a finite amount of time. If a solution exists, it must return one in finite time. The combinatorial motion planning methods of Chapter 6 will achieve this. Unfortunately, such completeness is not achieved with sampling-based planning. Instead, weaker notions of completeness are tolerated. The notion of denseness becomes important, which means that the samples come arbitrarily close to any configuration as the number of iterations tends to infinity. A deterministic ap- proach that samples densely will be called resolution complete. This means that if a solution exists, the algorithm will find it in finite time; however, if a solution does not exist, the algorithm may run forever. Many sampling-based approaches are based on random sampling, which is dense with probability one. This leads to algorithms that are probabilistically complete, which means that with enough points, the probability that it finds an existing solution converges to one. The most relevant information, however, is the rate of convergence, which is usually very difficult to establish.
Section 5.1 presents metric and measure space concepts, which are fundamen- tal to nearly all sampling-based planning algorithms. Section 5.2 presents general sampling concepts and quality criteria that are effective for analyzing the perfor- mance of sampling-based algorithms. Section 5.3 gives a brief overview of collision detection algorithms, to gain an understanding of the information available to a planning algorithm and the computation price that must be paid to obtain it. Section 5.4 presents a framework that defines algorithms which solve motion planning problems by integrating sampling and discrete planning (i.e., searching) techniques. These approaches can be considered single query in the sense that a single pair, (qI , qG), is given, and the algorithm must search until it finds a solution (or it may report early failure). Section 5.5 focuses on rapidly exploring random trees (RRTs) and rapidly exploring dense trees (RDTs), which are used to develop efficient single-query planning algorithms. Section 5.6 covers multiple-query algo- rithms, which invest substantial preprocessing effort to build a data structure that
is later used to obtain efficient solutions for many initial-goal pairs. In this case, it is assumed that the obstacle region O remains the same for every query.