One of the most useful variations of sampling-based roadmaps is the visibility roadmap . The approach works very hard to ensure that the roadmap representation is small yet covers 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 :
The main novelty of the visibility roadmap is using a strong criterion to determine whether to keep and its associated edges in . There are three possible cases for each :
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 . 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 is dense, even though many samples are rejected.
Steven M LaValle 2012-04-20