Further Reading

Most of the literature on combinatorial planning is considerably older than the sampling-based planning literature. A nice collection of early papers appears in [854]; this includes [460,748,749,817,851,852,853]. The classic motion planning textbook of Latombe [588] covers most of the methods presented in this chapter. The coverage here does not follow [588], 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 [403].

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 [264]. Other sources for computational geometry include [129,302,806]. To understand the difficulties in computing optimal decompositions of polygons, see [757]. 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 [834]. In computational geometry, various kinds of cell decompositions arise. Some of the most widely studied decompositions are triangulations [90] and arrangements [426], 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 [854]. A survey of computational topology appears in [954].

The most modern and complete reference for the material in Section 6.4 is [77]. A gentle introduction to computational algebraic geometry is given in [250]. For details regarding algebraic computations with polynomials, see [704]. A survey of computational algebraic geometry appears in [705]. In addition to [77], 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 [173]. 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 [77]. A potential function-based extension of Canny's roadmap algorithm is developed in [176].

For further reading on the complexity of motion planning, consult the numerous references given in Section 6.5.