Kino-PAX: Highly Parallel Kinodynamic Sampling-based Planner¶
Authors: Nicolas Perrault, Qi Heng Ho, Morteza Lahijanian
Published: 2024 (Journal Paper)
Source: IEEE Robotics and Automation Letters (RA-L)
Algorithm: Kino-PAX
arXiv: 2409.06807
DOI: 10.1109/LRA.2025.3531152
Summary¶
GPU-native kinodynamic sampling-based planner that decomposes the traditionally serial RRT tree-growth process into three massively parallel subroutines. The design aligns with GPU execution hierarchies: independent threads, balanced workloads, low-latency shared memory.
Abstract¶
Sampling-based motion planners (SBMPs) are effective for planning with complex kinodynamic constraints in high-dimensional spaces, but they still struggle to achieve real-time performance, which is mainly due to their serial computation design. We present Kinodynamic Parallel Accelerated eXpansion (Kino-PAX), a novel highly parallel kinodynamic SBMP designed for parallel devices such as GPUs. Kino-PAX grows a tree of trajectory segments directly in parallel. Our key insight is how to decompose the iterative tree growth process into three massively parallel subroutines. Kino-PAX is designed to align with the parallel device execution hierarchies, through ensuring that threads are largely independent, share equal workloads, and take advantage of low-latency resources while minimizing high-latency data transfers and process synchronization. This design results in a very efficient GPU implementation. We prove that Kino-PAX is probabilistically complete and analyze its scalability with compute hardware improvements. Empirical evaluations demonstrate solutions in the order of 10 ms on a desktop GPU and in the order of 100 ms on an embedded GPU, representing up to 1000× improvement compared to coarse-grained CPU parallelization of state-of-the-art sequential algorithms over a range of complex environments and systems.
Links¶
Primary
Standard
Alternate
Tags¶
-
Motion planning
-
Sampling-based planning
-
Kinodynamic planning
-
GPU
-
Parallelized
-
Real-time planning