Using load balancing to scalably parallelize sampling-based motion planning algorithms

Adam Fidel, Sam Ade Jacobs, Shishir Sharma, Nancy M. Amato, Lawrence Rauchwerger

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

Abstract

Motion planning, which is the problem of computing feasible paths in an environment for a movable object, has applications in many domains ranging from robotics, to intelligent CAD, to protein folding. The best methods for solving this PSPACE-hard problem are so-called sampling-based planners. Recent work introduced uniform spatial subdivision techniques for parallelizing sampling-based motion planning algorithms that scaled well. However, such methods are prone to load imbalance, as planning time depends on region characteristics and, for most problems, the heterogeneity of the sub problems increases as the number of processors increases. In this work, we introduce two techniques to address load imbalance in the parallelization of sampling-based motion planning algorithms: an adaptive work stealing approach and bulk-synchronous redistribution. We show that applying these techniques to representatives of the two major classes of parallel sampling-based motion planning algorithms, probabilistic roadmaps and rapidly-exploring random trees, results in a more scalable and load-balanced computation on more than 3,000 cores.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE 28th International Parallel and Distributed Processing Symposium, IPDPS 2014
PublisherIEEE Computer Society
Pages573-582
Number of pages10
ISBN (Print)9780769552071
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event28th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2014 - Phoenix, AZ, United States
Duration: May 19 2014May 23 2014

Publication series

NameProceedings of the International Parallel and Distributed Processing Symposium, IPDPS
ISSN (Print)1530-2075
ISSN (Electronic)2332-1237

Other

Other28th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2014
CountryUnited States
CityPhoenix, AZ
Period5/19/145/23/14

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'Using load balancing to scalably parallelize sampling-based motion planning algorithms'. Together they form a unique fingerprint.

  • Cite this

    Fidel, A., Jacobs, S. A., Sharma, S., Amato, N. M., & Rauchwerger, L. (2014). Using load balancing to scalably parallelize sampling-based motion planning algorithms. In Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium, IPDPS 2014 (pp. 573-582). [6877290] (Proceedings of the International Parallel and Distributed Processing Symposium, IPDPS). IEEE Computer Society. https://doi.org/10.1109/IPDPS.2014.66