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}$.