提出实时防死锁的多智能体导航算法，避免事后修正带来的延迟。
Cooperative-ORCA*: Real-Time Proactive Deadlock Avoidance for Continuous-Space Multi-Agent Navigation
- 基于全局轨迹预测提前预防死锁，而非事后处理
- 解决率、运行时间和流程延迟均优于现有最优方法
- 适合需要高实时性与协同效率的机器人团队场景
多智能体路径规划（MAPF）要求为一组智能体从起始位置规划到目标位置的无碰撞路径，广泛应用于需协同工作的机器人团队。ORCA* 是一种实时 MAPF 求解器，每时刻为每个智能体分配速度。由于其实时性，会忽略当前决策引发的未来死锁。ORCA*-MAPF 通过检测死锁后引入回退机制来弥补这一缺陷，但事后干预常导致显著的流程延迟。本文提出 C-ORCA* 与 C-ORCA*-MAPF，为连续空间下的 MAPF 算法，通过考虑智能体的完整空间轨迹及其空间依赖关系，主动预防死锁发生，从而避免了 ORCA*-MAPF 中高开销的事后修正。实验表明，C-ORCA* 系列算法在求解率、运行时间与流程延迟方面均显著优于先前最先进方法。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) is a problem that requires computing collision-free paths for a set of agents from their start locations to designated goal locations. The problem has broad applications in domains where teams of robots must operate in a coordinated manner. ORCA* is a real time MAPF solver that assigns for each timestep a velocity for each agent. Due to its real time nature, it is myopic to future deadlocks that result from current decisions. ORCA*-MAPF attempts to remedy this limitation by introducing fallback mechanisms when deadlocks are detected. However, post hoc interventions often introduce significant flowtime overhead. In this paper, we introduce C-ORCA* and C-ORCA*-MAPF, continuous space MAPF algorithms that incorporate agents' entire spatial trajectory and their spatial dependencies to proactively prevent deadlocks from occurring, thus avoiding the high flowtime overhead associated with post hoc corrections in ORCA*-MAPF. The C-ORCA* family of algorithms significantly outperform previous state-of-the-art in terms of solve rate, runtime, and flowtime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。