##

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