  Sampling-based planning has become a de facto standard for complex robots
given its superior ability to rapidly explore high-dimensional configuration
spaces. Most existing optimal sampling-based planning algorithms are sequential
in nature and cannot take advantage of wide parallelism available on modern
computer hardware. Further, tight synchronization of exploration and
exploitation phases in these algorithms limits sample throughput and planner
performance. Policy Iteration RRT# (PI-RRT#) exposes fine-grained parallelism
during the exploitation phase, but this parallelism has not yet been evaluated
using a concrete implementation. We first present a novel GPU implementation of
PI-RRT#'s exploitation phase and discuss data structure considerations to
maximize parallel performance. Our implementation achieves 3-4x speedup over a
serial PI-RRT# implementation for a 77.9% decrease in overall planning time on
average. As a second contribution, we introduce the Batched-Extension RRT#
algorithm, which loosens the synchronization present in PI-RRT# to realize
independent 12.97x and 12.54x speedups under serial and parallel exploitation,
respectively.

Robotics