For each grid point $ q$ we need to define the set of nearby grid points for which an edge may be constructed. Special care must be given to defining the neighborhood of a boundary grid point to ensure that identifications and the C-space boundary (if it exists) are respected. If $ q$ is not a boundary grid point, then the 1-neighborhood is defined as

$\displaystyle N_1(q) = \{ q + \Delta q_1, \ldots, q + \Delta q_n, q - \Delta q_1, \ldots, q - \Delta q_n \} .$ (5.37)

For an $ n$-dimensional C-space there at most $ 2n$ $ 1$-neighbors. In two dimensions, this yields at most four $ 1$-neighbors, which can be thought of as ``up,'' ``down,'' ``left,'' and ``right.'' There are at most four because some directions may be blocked by the obstacle region.

A 2-neighborhood is defined as

$\displaystyle N_2(q) = \{ q \pm \Delta q_i \pm \Delta q_j \;\; \vert \;\; 1 \leq i,j \leq n,\; i \not = j \} \cup N_1(q).$ (5.38)

Similarly, a $ k$-neighborhood can be defined for any positive integer $ k \leq n$. For an $ n$-neighborhood, there are at most $ 3^n-1$ neighbors; there may be fewer due to boundaries or collisions. The definitions can be easily extended to handle the boundary points.

Figure 5.14: A topological graph can be constructed during the search and can successfully solve a motion planning problem using very few samples.
...earch4.idr,width=2.1in} \\
(c) & (d) \\

Steven M LaValle 2012-04-20