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.

Steven M LaValle 2012-04-20