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 subproblems 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.