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 $ {\cal C}$ 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 $ {\cal C}_{free}$. Some edges may not exist because of collisions, but this will have to be revealed incrementally during the search because an explicit representation of $ {\cal C}_{obs}$ is too expensive to construct (recall Section 4.3).

Assume that an $ n$-dimensional C-space is represented as a unit cube, $ {\cal C}= [0,1]^n {/\sim}$, in which $ \sim$ indicates that identifications of the sides of the cube are made to reflect the C-space topology. Representing $ {\cal C}$ as a unit cube usually requires a reparameterization. For example, an angle $ \theta \in [0,2 \pi)$ would be replaced with $ \theta / 2 \pi$ to make the range lie within $ [0,1]$. If quaternions are used for $ SO(3)$, then the upper half of $ {\mathbb{S}}^3$ must be deformed into $ [0,1]^3 {/\sim}$.

Steven M LaValle 2012-04-20