Local randomization in neighbor selection improves PRM roadmap quality Conference Paper uri icon


  • 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. In this paper, we propose 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. We provide a methodology for selecting the parameters k and K'. We perform an experimental comparison which shows that for both rigid and articulated robots, LocalRand results in roadmaps that are better connected than the traditional k-closest policy or a purely random neighbor selection policy. The cost required to achieve these results is shown to be comparable to k-closest. 2012 IEEE.

name of conference

  • 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2012)

published proceedings

  • 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems

author list (cited authors)

  • McMahon, T., Jacobs, S., Boyd, B., Tapia, L., & Amato, N. M.

citation count

  • 7

complete list of authors

  • McMahon, Troy||Jacobs, Sam||Boyd, Bryan||Tapia, Lydia||Amato, Nancy M

publication date

  • October 2012