TY - GEN
T1 - Local randomization in neighbor selection improves PRM roadmap quality
AU - McMahon, Troy
AU - Jacobs, Sam
AU - Boyd, Bryan
AU - Tapia, Lydia
AU - Amato, Nancy M.
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84872359774&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84872359774&partnerID=8YFLogxK
U2 - 10.1109/IROS.2012.6386061
DO - 10.1109/IROS.2012.6386061
M3 - Conference contribution
AN - SCOPUS:84872359774
SN - 9781467317375
T3 - IEEE International Conference on Intelligent Robots and Systems
SP - 4441
EP - 4448
BT - 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2012
T2 - 25th IEEE/RSJ International Conference on Robotics and Intelligent Systems, IROS 2012
Y2 - 7 October 2012 through 12 October 2012
ER -