From days to seconds: A scalable parallel algorithm for motion planning?

Sam Ade Jacobs, Nancy M. Amato

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

Abstract

Tliis work presents a scalable framework for parallelizing sampling ha,sed motion planning algorithms. The frame work subdivides the configuration, space (C-space) into re gions and uses (sequential) sampling-based planners to build roadmaps in each region. The regional roadraaps are later connected lo form a roadmap of the entire free space. By subdividing the space, we reduce ike work and inter-processor conumnheation associated with nearest neighbor ealeula-tion, a critical drawback and bottleneck to scalability in existing parallel motion planning methods. We show that our method is general enough to handle a ?variety of planning schemes, including the popular Probabilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algoritluns. We compare our approach to two other existing parallel algorithms and demonstrate thai our approach achieves better and more scalable performance. Our approach achieves almost linear scalability to hundreds of processors on a 2400-eore Linux cluster and over a thousand core on a. Cray XE6 petaseale machine.

Original languageEnglish (US)
Title of host publicationSC'11 - Proceedings of the 2011 High Performance Computing Networking, Storage and Analysis Companion, Co-located with SC'11
Pages109-110
Number of pages2
DOIs
StatePublished - Dec 1 2011
Externally publishedYes
Event2011 High Performance Computing Networking, Storage and Analysis, SC'11, Co-located with SC'11 - Seattle, WA, United States
Duration: Nov 12 2011Nov 18 2011

Publication series

NameSC'11 - Proceedings of the 2011 High Performance Computing Networking, Storage and Analysis Companion, Co-located with SC'11

Other

Other2011 High Performance Computing Networking, Storage and Analysis, SC'11, Co-located with SC'11
Country/TerritoryUnited States
CitySeattle, WA
Period11/12/1111/18/11

Keywords

  • High Performance Computing
  • Motion Pl arming
  • Robotics

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'From days to seconds: A scalable parallel algorithm for motion planning?'. Together they form a unique fingerprint.

Cite this