8.5.1.3 A sampling-based approach

There are numerous alternative ways to construct a cover. To illustrate the ideas, an approach called the sampling-based neighborhood graph is presented here [983]. Suppose that $X = {\cal C}_{free}$, which is a subset of some configuration space. As introduced in Section 5.4, let ${\alpha }$ be a dense, infinite sequence of samples in $X$. Assume that a collision detection algorithm is available that returns the distance, (5.28), between the robot and obstacles in the world. Such algorithms were described in Section 5.3.

An incremental algorithm is given in Figure 8.17. Initially, ${\cal O}$ is empty. In each iteration, if ${\alpha}(i) \in {\cal C}_{free}$ and it is not already contained in some neighborhood, then a new neighborhood is added to ${\cal O}$. The two main concerns are 1) how to define a new neighborhood, $O$, such that $O \subset {\cal C}_{free}$, and 2) when to terminate. At any given time, the cover is approximate. The union of all neighborhoods is ${\tilde{X}}$, which is a strict subset of $X$. In comparison to Figure 8.15, the cover is a special case in which the neighborhoods do not extend beyond ${\tilde{X}}$.

Figure 8.17: The cover is incrementally extended by adding new neighborhoods that are guaranteed to be collision-free.