6. Combinatorial Motion Planning

Combinatorial approaches to motion planning find paths through the
continuous configuration space without resorting to approximations.
Due to this property, they are alternatively referred to as *exact* algorithms. This is in contrast to the sampling-based motion
planning algorithms from Chapter 5.

- 6.1 Introduction
- Representation is important
- Reasons to study combinatorial methods
- Warning: Some methods are impractical
- Roadmaps

- 6.2 Polygonal Obstacle Regions
- 6.2.1 Representation
- 6.2.2 Vertical Cell Decomposition
- 6.2.3 Maximum-Clearance Roadmaps
- 6.2.4 Shortest-Path Roadmaps

- 6.3 Cell Decompositions
- 6.3.1 General Definitions
- 6.3.2 2D Decompositions
- 6.3.3 3D Vertical Decomposition
- 6.3.4 A Decomposition for a Line-Segment Robot

- 6.4 Computational Algebraic Geometry
- 6.4.1 Basic Definitions and Concepts
- 6.4.2 Cylindrical Algebraic Decomposition
- 6.4.3 Canny's Roadmap Algorithm

- 6.5 Complexity of Motion Planning

Steven M LaValle 2012-04-20