Kino-PAX: Highly Parallel Kinodynamic Sampling-based Planner
<|reference_start|>Kino-PAX: Highly Parallel Kinodynamic Sampling-based Planner: 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 times improvement compared to coarse-grained CPU parallelization of state-of-the-art sequential algorithms over a range of complex environments and systems.<|reference_end|>
@article{perrault2024kino-pax:,
    title={Kino-PAX: Highly Parallel Kinodynamic Sampling-based Planner},
    author={Nicolas Perrault, Qi Heng Ho, Morteza Lahijanian},
    journal={arXiv preprint arXiv:2409.06807},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.06807},
    primaryClass={cs.RO cs.DC cs.PF}
}