Vertex enhancement [516]

This heuristic strategy focuses effort on vertices that were difficult to connect to other vertices in the roadmap construction algorithm in Figure 5.25. A probability distribution, $P(v)$, is defined over the vertices $v \in V$. A number of iterations are then performed in which a vertex is sampled from $V$ according to $P(v)$, and then some random motions are performed from $v$ to try to reach new configurations. These new configurations are added as vertices, and attempts are made to connect them to other vertices, as selected by the NEIGHBORHOOD function in an ordinary iteration of the algorithm in Figure 5.25. A recommended heuristic [516] for defining $P(v)$ is to define a statistic for each $v$ as $n_f/(n_t+1)$, in which $n_t$ is the total number of connections attempted for $v$, and $n_f$ is the number of times these attempts failed. The probability $P(v)$ is assigned as $n_f/(n_t+1) m$, in which $m$ is the sum of the statistics over all $v \in V$ (this normalizes the statistics to obtain a valid probability distribution).

Figure 5.29: (a) To obtain samples along the boundary, binary search is used along random directions from a sample in ${\cal C}_{obs}$. (b) The bridge test finds narrow corridors by examining a triple of nearby samples along a line.