Expansive-space planner

This method [467,844] generates samples in a way that attempts to explore new parts of the space. In this sense, it is similar to the explore mode of the Ariadne's Clew algorithm. Furthermore, the planner is made more efficient by borrowing the bidirectional search idea from discrete search algorithms, as covered in Section 2.2.3. The VSM selects a vertex, $v_e$, from ${\cal G}$ with a probability that is inversely proportional to the number of other vertices of ${\cal G}$ that lie within a predetermined neighborhood of $v_e$. Thus, ``isolated'' vertices are more likely to be chosen. The LPM generates a new vertex $v_n$ at random within a predetermined neighborhood of $v_e$. It will decide to insert $v_n$ into ${\cal G}$ with a probability that is inversely proportional to the number of other vertices of ${\cal G}$ that lie within a predetermined neighborhood of $v_n$. For a fixed number of iterations, the VSM repeatedly chooses the same vertex, until moving on to another vertex. The resulting planner is able to solve many interesting problems by using a surprisingly simple criterion for the placement of points. The main drawbacks are that the planner requires substantial parameter tuning, which is problem-specific (or at least specific to a similar family of problems), and the performance tends to degrade if the query requires systematically searching a long labyrinth. Choosing the radius of the predetermined neighborhoods essentially amounts to determining the appropriate resolution.