## 5.4.2 Adapting Discrete Search Algorithms

One of the most convenient and straightforward ways to make sampling-based planning algorithms is to define a grid over and conduct a discrete search using the algorithms of Section 2.2. The resulting planning problem actually looks very similar to Example 2.1. Each edge now corresponds to a path in . Some edges may not exist because of collisions, but this will have to be revealed incrementally during the search because an explicit representation of is too expensive to construct (recall Section 4.3).

Assume that an -dimensional C-space is represented as a unit cube, , in which indicates that identifications of the sides of the cube are made to reflect the C-space topology. Representing as a unit cube usually requires a reparameterization. For example, an angle would be replaced with to make the range lie within . If quaternions are used for , then the upper half of must be deformed into .

Subsections
Steven M LaValle 2012-04-20