Parallel Multi-Tree Graph: A Parallel Generalized Free Space Structuring Method and Efficient Path Planning Strategy

Jinyuan Liu

doi:10.1109/tase.2026.3715832

2026-07-22

PRE

DOI：10.1109/tase.2026.3715832

原文链接

原文求助

摘要

En 中文

在高维、复杂环境中的路径规划是机器人学中的一个关键且具有挑战性的任务。传统的图搜索方法和基于采样的规划器在计算效率和收敛速度方面经常面临限制。基于几何的空间预处理技术可以显著提高规划器效率。然而，它们不适合高维和复杂的构型空间。本文介绍了并行多树图（PMTG），一种使用随机树在任意维度中划分自由空间的路径规划框架。PMTG形成环境的高层拓扑表示。这种方法允许每棵树在其局部空间内通过并行计算独立扩展和优化，促进快速空间结构和高效的初始路径搜索。基于边优先级队列的同步机制确保了树之间一致的扩展速度，保持了空间划分的质量。此外，PMTG通过引导非均匀采样过程加速规划阶段的路径改进。仿真和实际实验表明，PMTG的性能可与当前最先进的路径规划算法相媲美。通过利用并行计算预先构建构型空间，PMTG在路径规划中实现了显著的实际时钟加速，尤其是在有限的计算时间预算下。尽管受到与所有基于采样的方法相同的维度限制，PMTG在广泛任务中始终保持着具有竞争力的或更优的实用效率，特别是在复杂现实机器人系统的典型维度范围内表现尤为出色。实践者说明——本文介绍了并行多树图（PMTG），一种旨在提高高维和复杂构型空间中操作代理的路径规划性能的方法。传统的基于采样的规划器在具有高维自由空间的挑战性环境中可能计算密集且收敛缓慢。PMTG通过使用多棵随机树划分自由空间并创建其结构化表示来解决这些问题，从而实现高效、并行化的路径搜索。该方法包含一个同步机制，以保持多棵树之间的一致扩展，从而提高规划效率和准确性。尽管PMTG在高维任务中表现良好，但在非常大的空间中实时构建PMTG的计算需求可能很高。在静态或主要静态的环境中，PMTG可以预先构建一次并从内存中加载，实现毫秒级响应的实时规划。当环境发生永久性、大规模的结构变化（例如建筑翻新）时，建议重新执行完整的构建阶段。对于局部变化，仅需重新连接受影响的子树或数值更新其树间边成本，无需完全重建。瞬态动态障碍物最好由专门的局部规划器处理，不需要PMTG重构。该方法已被证明是概率完备且几乎肯定渐近最优的。仿真和实际实验表明，它在各种高维和复杂的路径规划任务中实现了卓越的效率，特别是在计算资源有限和主要静态环境的应用中显示出巨大的潜力。

Keyword:

Space structuring

parallel multi-tree graph

robotics

sampling-based planners