5.6.2 Visibility Roadmap

One of the most useful variations of sampling-based roadmaps is the visibility roadmap [885]. The approach works very hard to ensure that the roadmap representation is small yet covers ${\cal C}_{free}$ well. The running time is often greater than the basic algorithm in Figure 5.25, but the extra expense is usually worthwhile if the multiple-query philosophy is followed to its fullest extent.

The idea is to define two different kinds of vertices in ${\cal G}$:

1. [] Guards: To become a guard, a vertex, $q$ must not be able to see other guards. Thus, the visibility region, $V(q)$, must be empty of other guards.
2. [] Connectors: To become a connector, a vertex, $q$, must see at least two guards. Thus, there exist guards $q_1$ and $q_2$, such that $q \in V(q_1) \cap V(q_2)$.

The roadmap construction phase proceeds similarly to the algorithm in Figure 5.25. The neighborhood function returns all vertices in ${\cal G}$. Therefore, for each new sample ${\alpha }(i)$, an attempt is made to connect it to every other vertex in ${\cal G}$.

The main novelty of the visibility roadmap is using a strong criterion to determine whether to keep $\alpha(i)$ and its associated edges in ${\cal G}$. There are three possible cases for each $\alpha(i)$:

1. The new sample, $\alpha(i)$, is not able to connect to any guards. In this case, $\alpha(i)$ earns the privilege of becoming a guard itself and is inserted into ${\cal G}$.
2. The new sample can connect to guards from at least two different connected components of ${\cal G}$. In this case, it becomes a connector that is inserted into ${\cal G}$ along with its associated edges, which connect it to these guards from different components.
3. Neither of the previous two conditions were satisfied. This means that the sample could only connect to guards in the same connected component. In this case, $\alpha(i)$ is discarded.

The final condition causes a dramatic reduction in the number of roadmap vertices.

One problem with this method is that it does not allow guards to be deleted in favor of better guards that might appear later. The placement of guards depends strongly on the order in which samples appear in ${\alpha }$. The method may perform poorly if guards are not positioned well early in the sequence. It would be better to have an adaptive scheme in which guards could be reassigned in later iterations as better positions become available. Accomplishing this efficiently remains an open problem. Note the algorithm is still probabilistically complete using random sampling or resolution complete if ${\alpha }$ is dense, even though many samples are rejected.