Most of the literature on combinatorial planning is considerably older than the sampling-based planning literature. A nice collection of early papers appears in ; this includes [460,748,749,817,851,852,853]. The classic motion planning textbook of Latombe  covers most of the methods presented in this chapter. The coverage here does not follow , which makes separate categories for cell decomposition methods and roadmap methods. A cell decomposition is constructed to produce a roadmap; hence, they are unified in this chapter. An excellent reference for material in combinatorial algorithms, computational geometry, and complete algorithms for motion planning is the collection of survey papers in .
Section 6.2 follows the spirit of basic algorithms from computational geometry. For a gentle introduction to computational geometry, including a nice explanation of vertical composition, see . Other sources for computational geometry include [129,302,806]. To understand the difficulties in computing optimal decompositions of polygons, see . See [650,709,832] for further reading on computing shortest paths.
Cell decompositions and cell complexes are very important in computational geometry and algebraic topology. Section 6.3 provided a brief perspective that was tailored to motion planning. For simplicial complexes in algebraic topology, see [496,535,834]; for singular complexes, see . In computational geometry, various kinds of cell decompositions arise. Some of the most widely studied decompositions are triangulations  and arrangements , which are regions generated by a collection of primitives, such as lines or circles in the plane. For early cell decomposition methods in motion planning, see . A survey of computational topology appears in .
The most modern and complete reference for the material in Section 6.4 is . A gentle introduction to computational algebraic geometry is given in . For details regarding algebraic computations with polynomials, see . A survey of computational algebraic geometry appears in . In addition to , other general references to cylindrical algebraic decomposition are [40,232]. For its use in motion planning, see [588,852]. The main reference for Canny's roadmap algorithm is . Alternative high-level overviews to the one presented in Section 6.4.3 appear in [220,588]. Variations and improvements to the algorithm are covered in . A potential function-based extension of Canny's roadmap algorithm is developed in .
For further reading on the complexity of motion planning, consult the numerous references given in Section 6.5.
Steven M LaValle 2012-04-20