GPU Parallelization of Policy Iteration RRT#

Richard Connor Lawson, Linda Wills, Panagiotis Tsiotras

TL;DR

This paper introduces a GPU-accelerated version of the PI-RRT# motion planner and a novel variant called Batched-Extension RRT# (BERRT#). By parallelizing the path-optimization phase and loosening the synchronization between adding samples and updating the graph, the authors achieve up to a 77.9% reduction in overall planning time.

What Problem Does This Paper Address?

Motion planning—finding a collision-free path for a robot—is increasingly difficult as robots become more complex (higher "dimensions"). Sampling-based planners like RRT* are the gold standard because they explore these spaces efficiently. However, most optimal planners are strictly sequential: they add one sample ("exploration"), then immediately update the entire path tree to ensure optimality ("exploitation").

This "tight synchronization" creates a massive bottleneck. Even though modern hardware (GPUs) is great at doing many things at once, these algorithms can't easily use that power because they stop to "think" after every single new data point. The authors aim to break this bottleneck by parallelizing the math and decoupling the exploration and exploitation phases.

Methods

The authors focus on Policy Iteration RRT# (PI-RRT#), a specific algorithm that uses "policy iteration" (a technique from reinforcement learning) to find shortest paths.

1. GPU Parallelization

They implemented the most expensive part of the algorithm—the Replan procedure—on a GPU.

  • Improve Kernel: Uses Jacobi relaxation to update the "cost-to-come" for vertices in parallel. Each CUDA thread handles one vertex.
  • Evaluate Kernel: Performs a parallel breadth-first search (BFS) to propagate cost changes through the tree.
  • Data Structure Optimization: They experimented with different graph formats, eventually choosing a Coordinate List for the CPU (fast for adding new edges) and converting it to Compressed Sparse Row (CSR) on the GPU (fast for searching neighbors).

2. Batched-Extension RRT# (BERRT#)

The authors realized that even with a fast GPU, replanning after every sample is wasteful. They introduced BERRT#, which allows the user to set a batch size ($S$). The algorithm adds $S$ samples to the graph before triggering a single, massive replanning step. This allows for a tunable balance between how "optimal" the current path is and how fast the algorithm runs.

Datasets

The algorithms were evaluated on a simulated 2D environment with polygonal obstacles. While 2D might seem simple, the authors used very high sample counts (up to 70,000) to test how the parallelization scales as the problem size grows.

Key Insights and Ideas

  • The GPU Overhead Threshold: Parallelization isn't free. For small problems (fewer samples), the time spent moving data from the CPU to the GPU actually makes the planner slower than a serial CPU version. The GPU only becomes "worth it" after a specific threshold ($N_0 \approx 6,200$ samples in their tests).
  • Synchronization is the Real Enemy: The biggest performance gains didn't come from the GPU's raw math power, but from batching. By reducing how often the algorithm had to stop and synchronize, they achieved order-of-magnitude speedups.
  • One-Way Dataflow: Because the "exploration" phase creates edges that the "exploitation" phase only reads (never modifies), the authors could optimize data transfers to be one-way, significantly reducing communication overhead.

Key Results

  • Exploitation Speedup: The GPU implementation achieved a 3–4× speedup in the replanning phase compared to a serial implementation.
  • Overall Time Reduction: For large problems, the GPU version decreased total planning time by an average of 77.9%.
  • Batching Gains: Increasing the batch size from 1 to 100 resulted in a 12.97× speedup for the serial version and a 12.54× speedup for the parallel version.
  • Peak Performance: The highest mean speedup for the exploitation phase specifically was 3.74× at roughly 42,600 samples.

Limitations and Future Work

  • Memory Access Patterns: In the Evaluate kernel (the BFS), as the graph grows more complex and random, the GPU's memory access becomes less efficient, leading to a slight "tapering off" of speedup at extremely high sample counts.
  • Static Environments: The current work was tested on a static 2D map. Future work could explore how these parallel structures handle dynamic environments where obstacles move.
  • True Asynchrony: While BERRT# batches samples, the exploration and exploitation still happen one after the other. The authors suggest a future "asynchronous" version where the GPU optimizes the current graph while the CPU is already busy adding the next set of samples.

Summary updated

Abstract

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-4× 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.97× and 12.54× speedups under serial and parallel exploitation, respectively.
BibTeX
@inproceedings{lawson2020gpu,
  author = {Richard Connor Lawson and Linda Wills and Panagiotis Tsiotras},
  title = {{GPU Parallelization of Policy Iteration RRT\#}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2020},
  doi = {10.1109/iros45743.2020.9341411},
}

Loading related content...

Figure