A scalable method for parallelizing sampling-based motion planning algorithms

Sam Ade Jacobs, Kasra Manavi, Juan Burgos, Jory Denny, Shawna Thomas, Nancy M. Amato

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

Abstract

This paper describes a scalable method for parallelizing sampling-based motion planning algorithms. It subdivides configuration space (C-space) into (possibly overlapping) regions and independently, in parallel, uses standard (sequential) sampling-based planners to construct roadmaps in each region. Next, in parallel, regional roadmaps in adjacent regions are connected to form a global roadmap. By subdividing the space and restricting the locality of connection attempts, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We show that our method is general enough to handle a variety of planning schemes, including the widely used Probabilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algorithms. We compare our approach to two other existing parallel algorithms and demonstrate that our approach achieves better and more scalable performance. Our approach achieves almost linear scalability on a 2400 core LINUX cluster and on a 153,216 core Cray XE6 petascale machine.

Original languageEnglish (US)
Title of host publication2012 IEEE International Conference on Robotics and Automation, ICRA 2012
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2529-2536
Number of pages8
ISBN (Print)9781467314039
DOIs
StatePublished - 2012
Externally publishedYes
Event 2012 IEEE International Conference on Robotics and Automation, ICRA 2012 - Saint Paul, MN, United States
Duration: May 14 2012May 18 2012

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729

Other

Other 2012 IEEE International Conference on Robotics and Automation, ICRA 2012
Country/TerritoryUnited States
CitySaint Paul, MN
Period5/14/125/18/12

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A scalable method for parallelizing sampling-based motion planning algorithms'. Together they form a unique fingerprint.

Cite this