Using Load Balancing to Scalably Parallelize Sampling-Based Motion Planning Algorithms
2014
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 planningalgorithms 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 planningalgorithms: an adaptive
work stealingapproach and bulk-synchronous redistribution. We show that applying these techniques to representatives of the two major classes of parallel sampling-based
motion planningalgorithms,
probabilistic roadmapsand
rapidly-exploring random trees, results in a more scalable and
load-balanced computationon more than 3,000 cores.
Keywords:
-
Correction
-
Source
-
Cite
-
Save
-
Machine Reading By IdeaReader
28
References
4
Citations
NaN
KQI