Neighborhoods

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

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

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