High-dimensional planning on the GPU

Kider, Joseph T; Henderson, Mark; Likhachev, Maxim; Safonova, Alla · 2010 · OpenAlex-citations

DOI: 10.1109/robot.2010.5509470

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of scaling optimal heuristic search algorithms, such as A*, to high-dimensional planning problems. While A* is effective for low-dimensional tasks like 2D pathfinding, it fails to scale for complex scenarios involving robotic arm motion planning, non-holonomic vehicle trajectories, or humanoid motion synthesis. The authors focus on R* search, a randomized variant of A* that trades deterministic optimality for probabilistic sub-optimality guarantees to achieve scalability. The primary contribution is demonstrating that R* is well-suited for parallel implementation on Graphics Processing Units (GPUs), resulting in a new algorithm called R*GPU. This implementation preserves the theoretical properties of R*, including its probabilistic bounds on solution sub-optimality, while significantly improving performance metrics. The methodology involves decomposing the single-shot A* search into a series of short-range, easy-to-solve searches guided by a heuristic function toward randomly chosen goals. R* constructs a sparse graph of states connected by edges, where each edge represents a path in the original graph. Instead of expanding all immediate successors, R* generates random states at a specific distance from the current state. The parallelization strategy leverages the independence of these short-range searches; the main scheduling loop runs on the CPU, while individual searches execute in parallel threads on the GPU using CUDA. This approach minimizes memory usage, allowing multiple searches to share states in GPU DRAM and eliminating costly memory transfers, as each search discards its memory upon completion. Experimental results evaluate R*GPU against the CPU-based R* algorithm in two settings: 53 randomly generated 2D gridworlds with varying obstacle densities and a simulated 6-degree-of-freedom (DOF) robotic arm with a state space exceeding 3 billion states. In the 2D environments, R*GPU outperformed the CPU version as obstacle density increased and as edge cost computations became more time-consuming. In the 6DOF robot arm experiments, R*GPU consistently produced lower-cost solutions. Within a five-minute planning window, R*GPU executed over 38 times more successful R* searches and over 64 times more weighted A* searches than the CPU version. Figure 1 illustrates that R*GPU generated a motion with a cost of 78, compared to a cost of 101 for standard R* after 30 seconds of planning. The significance of this work lies in demonstrating that GPU acceleration can substantially enhance the efficiency of high-dimensional planning algorithms. By preserving the theoretical guarantees of R* while achieving superior speed, memory scalability, and solution quality, R*GPU offers a robust method for complex motion planning tasks. The findings suggest that decomposing search problems into parallelizable short-range tasks is an effective strategy for leveraging GPU architecture in artificial intelligence and robotics applications.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• visual search