Probabilistic Roadmap Methods (PRMs) are one of the most used classes of motion planning methods. These sampling-based methods generate robot configurations (nodes)
and then connect them to form a graph (roadmap) containing representative feasible pathways. A key step in PRM roadmap construction involves identifying a set of candidate
neighbors for each node. Traditionally, these candidates are chosen to be the k-closest nodes based on a given distance metric. This work proposes a new neighbor selection policy
called LocalRand(k, k'), that first computes the k' closest nodes to a specified node and then selects k of those nodes at random. Intuitively, LocalRand attempts to benefit
from random sampling while maintaining the higher levels of local planner success inherent to selecting more local neighbors. A methodology for selecting the parameters k and
k' is provided, and an experimental comparison for both rigid and articulated robots show that LocalRand results in roadmaps that are better connected than the traditional k-closest or a purely random neighbor selection policy. The cost required to achieve these results is shown to be comparable to the cost of k-closest.
- Amato, Nancy Professor - Term Appointment