Overview

Different Planners described in chapter 5 build roadmaps in the free (or semi-free) configuration space. Each of these methods relies on an explicit representation of the geometry of . Because of this, as the dimension of the configuration space grows, these planners become impractical. Figure 7.1 shows a path-planning problem that cannot be solved in a reasonable amount of time with the methods presented in chapter 5, but can be solved with the sampling-based methods described in this chapter. Sampling-based methods employ a variety of strategies for generating samples (collision-free configurations of the robot) and for connecting the samples with paths to obtain solutions to path-planning problems.

Figure 7.1: Snapshots along a path of a planar manipulator with ten degrees of freedom. The manipulator has a fixed base and its first three links have prismatic joints-they can extend to one and a half times their original length. (From Kavraki [221].)

Figures 7.2(a) and (b) show two typical examples from industrial automation that sampling-based planners can routinely solve. Sampling-based planners can also be used to address problems that extend beyond classic path planning. Figure 7.2(c) shows a CAD (computer-aided design) model of an aircraft engine. A planner can be used to determine if a part can be removed from that engine. Such information is extremely important for the correct design of the engine, as certain parts need to be removable for maintainability purposes. In this case, the planner considers the part to be separated as a robot that can...