Further Reading

Unlike the last two chapters, the material of Chapter 5 is a synthesis of very recent research results. Some aspects of sampling-based motion planning are still evolving. Early approaches include [70,144,193,280,282,329,330,658,760]. The Gilbert-Johnson-Keerthi algorithm [388] is an early collision detection approach that helped inspire sampling-based motion planning; see [472] and [588] for many early references. In much of the early work, randomization appeared to be the main selling point; however, more recently it has been understood that deterministic sampling can work at least as well while obtaining resolution completeness. For a more recent survey of sampling-based motion planning, see [640].

Section 5.1 is based on material from basic mathematics books. For a summary of basic theorems and numerous examples of metric spaces, see [696]. More material appears in basic point-set topology books (e.g., [451,496]) and analysis books (e.g., [346]). Metric issues in the context of sampling-based motion planning are discussed in [21,609]. Measure theory is most often introduced in the context of real analysis [346,425,546,836,837]. More material on Haar measure appears in [425].

Section 5.2 is mainly inspired by literature on Monte Carlo and quasi-Monte Carlo methods for numerical integration and optimization. An excellent source of material is [738]. Other important references for further reading include [191,540,682,937,938]. Sampling issues in the context of motion planning are considered in [380,559,600,639,987]. Comprehensive introductions to pure Monte Carlo algorithms appear in [341,502]. The original source for the Monte Carlo method is [695]. For a survey on algorithms that compute Voronoi diagrams, see [54].

For further reading on collision detection (beyond Section 5.3), see the surveys in [488,637,638,703]. Hierarchical collision detection is covered in [406,638,702]. The incremental collision detection ideas in Section 5.3.3 were inspired by the algorithm [636] and V-Clip [247,702]. Distance computation is covered in [167,306,387,406,413,702,807]. A method suited for detecting self-collisions of linkages appears in [653]. A combinatorial approach to collision detection for motion planning appears in [855]. Numerous collision detection packages are available for use in motion planning research. One of the most widely used is PQP because it works well for any mess of 3D triangles [948].

The incremental sampling and searching framework was synthesized by unifying ideas from many planning methods. Some of these include grid-based search [71,548,620] and probabilistic roadmaps (PRMs) [516]. Although the PRM was developed for multiple queries, the single-query version developed in [125] helped shed light on the connection to earlier planning methods. This even led to grid-based variants of PRMs [123,600]. Another single-query variant is presented in [845].

RDTs were developed in the literature mainly as RRTs, and were introduced in [598,610]. RRTs have been used in several applications, and many variants have been developed [82,138,150,200,224,244,265,362,393,495,499,498,528,631,641,642,918,919,949,979,986]. Originally, they were developed for planning under differential constraints, but most of their applications to date have been for ordinary motion planning. For more information on efficient nearest-neighbor searching, see the recent survey [475], and [46,47,48,52,99,230,365,476,538,758,908,989].

Section 5.6 is based mainly on the PRM framework [516]. The ``probabilistic'' part is not critical to the method; thus, it was referred to here as a sampling-based roadmap. A related precursor to the PRM was proposed in [390,391]. The PRM has been widely used in practice, and many variants have been proposed [1,23,61,62,125,161,181,244,479,544,600,627,628,740,784,792,885,900,950,971,979,995]. An experimental comparison of many of these variants appears in [380]. Some analysis of PRMs appears in [69,467,573]. In some works, the term PRM has been applied to virtually any sampling-based planning algorithm (e.g., [467]); however, in recent years the term has been used more consistently with its original meaning in [516].

Many other methods and issues fall outside of the scope of this chapter. Several interesting methods based on approximate cell decomposition [144,328,646,658] can be considered as a form of sampling-based motion planning. A sampling-based method of developing global potential functions appears in [124]. Other sampling-based planning algorithms appear in [194,348,417,418,463]. The algorithms of this chapter are generally unable to guarantee that a solution does not exist for a motion planning problem. It is possible, however, to use sampling-based techniques to establish in finite time that no solution exists [75]. Such a result is called a disconnection proof. Parallelization issues have also been investigated in the context of sampling-based motion planning [82,177,183,257,795].