Kino-PAX让运动规划速度提升千倍，专为GPU设计实现毫秒级响应。
Kino-PAX: Highly Parallel Kinodynamic Sampling-based Planner
- 并行生成轨迹段树，分解为三个可大规模并行的子任务
- 在桌面GPU上达10毫秒级解，嵌入式GPU上100毫秒，提速千倍
- 适合实时机器人路径规划，尤其对高维复杂系统有效
基于采样的运动规划器（SBMPs）在高维空间中处理复杂运动学动力学约束时表现良好，但受限于串行计算架构，难以实现实时性能。本文提出一种新型高度并行的运动学动力学采样规划器——Kino-PAX，专为GPU等并行设备设计。Kino-PAX直接在并行设备上并行生长轨迹段树，其核心思想是将迭代树扩展过程分解为三个可大规模并行的子任务。该设计与并行硬件执行层次对齐，确保线程间独立、负载均衡，并充分利用低延迟资源，同时最小化高延迟数据传输与进程同步开销。该设计实现了高效的GPU实现。我们证明了Kino-PAX具有概率完备性，并分析了其随计算硬件提升的可扩展性。实验表明，在桌面级GPU上求解时间约为10毫秒，在嵌入式GPU上约为100毫秒，相比现有串行算法的粗粒度CPU并行化，性能提升最高达1000倍，适用于多种复杂环境与系统。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。