用结构语义地图加速多机器人路径规划,提升效率与实用性。
Multi-Agent Path Finding Using Conflict-Based Search and Structural-Semantic Topometric Maps
- 将冲突搜索基于稀疏拓扑语义地图,而非密集网格图。
- 计算效率显著提升,冲突处理量减少,支持连续时间规划。
- 适合非完整机器人在真实场景中应用,尤其走廊对称情况表现更好。
随着工业领域大规模机器人车队的采用,高效、实用且无冲突的多机器人路径规划需求日益迫切。冲突基搜索(CBS)因其完备性和最优性成为多智能体路径规划(MAPF)的常用方法,但其计算开销大,且依赖难以实现的假设,限制了实际应用。本文提出一种新方案,利用结构-语义拓扑地图克服CBS的计算挑战与实用性问题。不再在大型网格地图上运行CBS,而是将其应用于包含表示交叉口、路径和死胡同的结构-语义单元的稀疏拓扑地图。该方法显著加速了MAPF过程,减少了CBS需处理的冲突数量,并支持连续时间规划。在该方法中,机器人被分配在拓扑区域间移动的时间区间,突破了传统CBS中单步可到达任意邻接单元的假设。通过真实世界多机器人路径规划实验与基准仿真验证,结果表明该方法可应用于真实非完整机器人,在计算效率上显著优于传统CBS,且在走廊对称场景下提升了冲突检测与解决能力。
原文摘要 · Abstract (English)
As industries increasingly adopt large robotic fleets, there is a pressing need for computationally efficient, practical, and optimal conflict-free path planning for multiple robots. Conflict-Based Search (CBS) is a popular method for multi-agent path finding (MAPF) due to its completeness and optimality; however, it is often impractical for real-world applications, as it is computationally intensive to solve and relies on assumptions about agents and operating environments that are difficult to realize. This article proposes a solution to overcome computational challenges and practicality issues of CBS by utilizing structural-semantic topometric maps. Instead of running CBS over large grid-based maps, the proposed solution runs CBS over a sparse topometric map containing structural-semantic cells representing intersections, pathways, and dead ends. This approach significantly accelerates the MAPF process and reduces the number of conflict resolutions handled by CBS while operating in continuous time. In the proposed method, robots are assigned time ranges to move between topometric regions, departing from the traditional CBS assumption that a robot can move to any connected cell in a single time step. The approach is validated through real-world multi-robot path-finding experiments and benchmarking simulations. The results demonstrate that the proposed MAPF method can be applied to real-world non-holonomic robots and yields significant improvement in computational efficiency compared to traditional CBS methods while improving conflict detection and resolution in cases of corridor symmetries.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。