首个实时完整可证明的多智能体路径规划方法，毫秒级响应仍保成功率。
Real-Time LaCAM for Real-Time MAPF
- 增量式调用LaCAM，实现实时规划与完整保证
- 毫秒级截止时间下成功率与全时域方案持平
- 适用于实时系统和学习型路径策略
大多数具有完备性保证的多智能体路径规划（MAPF）方法需要规划全时域路径，但这类方法耗时过长，在真实场景中不实用。相比之下，实时规划与执行——即规划器在有限时间内规划并执行、再规划——更符合实际需求。尽管已有若干实时规划方法，但均无完备性保证，可能导致活锁或死锁。本文提出首个具备可证明完备性的实时MAPF方法：Real-Time LaCAM。该方法通过增量式应用LaCAM（Okumura, 2023）实现。实验表明，在毫秒级截止时间内，该方法仍能保持与全时域LaCAM相同的路径求解成功率，适用于拥堵环境。此外，该方法还可与单步学习型MAPF策略结合使用。
原文摘要 · Abstract (English)
The vast majority of Multi-Agent Path Finding (MAPF) methods with completeness guarantees require planning full-horizon paths. However, planning full-horizon paths can take too long and be impractical in real-world applications. Instead, real-time planning and execution, which only allows the planner a finite amount of time before executing and replanning, is more practical for real-world multi-agent systems. Several methods utilize real-time planning schemes but none are provably complete, which leads to livelock or deadlock. Our main contribution is Real-Time LaCAM, the first Real-Time MAPF method with provable completeness guarantees. We do this by leveraging LaCAM (Okumura 2023) in an incremental fashion. Our results show how we can iteratively plan for congested environments with a cutoff time of milliseconds while still maintaining the same success rate as full-horizon LaCAM. We also show how it can be used with a single-step learned MAPF policy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。