提出可保证完成性的窗口化多智能体路径规划框架
Windowed MAPF with Completeness Guarantees
- 基于单步规划与启发式更新，实现窗口化路径规划
- 在现有方法易死锁的场景下仍能成功求解
- 适合需要快速重规划的实时多智能体系统
传统多智能体路径规划（MAPF）方法试图计算完整的起止路径，但完整路径计算耗时过长，难以满足快速重规划需求。现有窗口化方法仅规划有限时间窗口内的路径，虽提升效率却牺牲了完备性，可能导致死锁或活锁。本文提出WinC-MAPF框架，首次实现窗口化MAPF的完备性。该框架融合单智能体实时启发式搜索的启发式更新策略与多智能体路径规划中的代理独立性思想。进一步设计了单步CBS（SS-CBS），通过每步仅规划一步并动态更新启发式函数，在无需全局规划的情况下有效解决复杂场景。实验表明，相比现有窗口化方法，SS-CBS在高冲突、高密度场景中具备更强鲁棒性与求解能力。
原文摘要 · Abstract (English)
Traditional multi-agent path finding (MAPF) methods try to compute entire start-goal paths which are collision free. However, computing an entire path can take too long for MAPF systems where agents need to replan fast. Methods that address this typically employ a "windowed" approach and only try to find collision free paths for a small windowed timestep horizon. This adaptation comes at the cost of incompleteness; all current windowed approaches can become stuck in deadlock or livelock. Our main contribution is to introduce our framework, WinC-MAPF, for Windowed MAPF that enables completeness. Our framework uses heuristic update insights from single-agent real-time heuristic search algorithms as well as agent independence ideas from MAPF algorithms. We also develop Single-Step CBS (SS-CBS), an instantiation of this framework using a novel modification to CBS. We show how SS-CBS, which only plans a single step and updates heuristics, can effectively solve tough scenarios where existing windowed approaches fail.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。