Kino-PAX+实现高维机器人运动规划的近最优并行计算，速度提升百倍以上。
Kino-PAX$^+$: Near-Optimal Massively Parallel Kinodynamic Sampling-based Motion Planner
- 将串行采样步骤拆分为三个并行子程序，构建动态可行轨迹稀疏树。
- 在局部邻域聚焦优质节点，使解的质量显著提升，成本低于现有方法。
- 适用于需要实时响应与高质量路径的复杂机器人系统规划场景。
基于采样的运动规划器（SBMP）广泛用于高维空间中具有复杂动力学约束的机器人运动规划，但其串行计算设计导致难以实现实时性能。尽管近期并行化尝试显著加快了可行解的搜索速度，却无法保证目标函数的优化。本文提出Kino-PAX⁺，一种具有渐近近最优保证的大规模并行动力学采样规划器。该算法通过将传统串行操作分解为三个大规模并行子程序，构建动态可行轨迹的稀疏树。算法聚焦于局部邻域内最有希望的节点进行传播与精炼，从而快速改善解的成本。我们证明，在保持概率δ-鲁棒完备性的前提下，对优质节点的重点计算可确保渐近δ-鲁棒近最优性。实验结果表明，Kino-PAX⁺相比现有串行方法，求解速度提升高达三个数量级，并且解的成本低于当前最先进的基于GPU的规划器。
原文摘要 · Abstract (English)
Sampling-based motion planners (SBMPs) are widely used for robot motion planning with complex kinodynamic constraints in high-dimensional spaces, yet they struggle to achieve \emph{real-time} performance due to their serial computation design. Recent efforts to parallelize SBMPs have achieved significant speedups in finding feasible solutions; however, they provide no guarantees of optimizing an objective function. We introduce Kino-PAX$^{+}$, a massively parallel kinodynamic SBMP with asymptotic near-optimal guarantees. Kino-PAX$^{+}$ builds a sparse tree of dynamically feasible trajectories by decomposing traditionally serial operations into three massively parallel subroutines. The algorithm focuses computation on the most promising nodes within local neighborhoods for propagation and refinement, enabling rapid improvement of solution cost. We prove that, while maintaining probabilistic $δ$-robust completeness, this focus on promising nodes ensures asymptotic $δ$-robust near-optimality. Our results show that Kino-PAX$^{+}$ finds solutions up to three orders of magnitude faster than existing serial methods and achieves lower solution costs than a state-of-the-art GPU-based planner.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。