Local Randomization in Neighbor Selection Improves PRM Roadmap Quality



Journal Title

Journal ISSN

Volume Title



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.