Local randomization in neighbor selection improves PRM roadmap quality

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations


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.
Original languageEnglish (US)
Title of host publication2012 IEEE/RSJ International Conference on Intelligent Robots and Systems
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages8
ISBN (Print)9781467317368
StatePublished - Oct 2012
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): KUS-C1-016-04
Acknowledgements: This research supported in part by NSF awards CRI-0551685, CCF-0833199, CCF-0830753, IIS-096053, IIS-0917266, by THECB NHARPaward 000512-0097-2009, by Chevron, IBM, Intel, Oracle/Sun and byAward KUS-C1-016-04, made by King Abdullah University of Science andTechnology (KAUST). Tapia supported in part by NIH Grant P20RR018754.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.


Dive into the research topics of 'Local randomization in neighbor selection improves PRM roadmap quality'. Together they form a unique fingerprint.

Cite this