提出PUSH框架，让上万智能体在复杂地图中实时规划长时路径。
Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF
- 分批交错规划：每步只处理部分智能体，降低计算开销。
- 支持复杂地图：在非规则地图上实现多步前瞻，吞吐量超基线数倍。
- 适合大规模动态场景：适用于物流、交通等需长期协同的系统。
终身多智能体路径规划（LMAPF）需在严格实时约束下为大规模智能体群生成无碰撞路径。反应式框架如PIBT和增强型PIBT（EPIBT）通过规则逐步协调，可扩展至数千智能体，但存在严重的时间短视问题，难以应对需长时推理的场景。RHCR虽能规划多步窗口路径，但计算开销大，难以扩展。TP通过每步仅规划部分智能体缓解负担，但仅适用于高度结构化地图。为在一般地图上实现大规模长时规划，我们提出路径交错窗口更新（PUSH），可在1秒内协调上万智能体并进行多步前瞻规划。PUSH融合PIBT、RHCR与TP优势：类似TP，采用交错规划窗口降低复杂度；不同于TP，能在一般地图上规划类似RHCR的窗口路径，无需地图限制。为保障拥堵环境下的高吞吐，还引入类EPIBT的优先级继承、回溯与任意时间改进机制。在两个需长时推理的真实场景中评估显示，PUSH在规模上达到与EPIBT相当（如10,000智能体），同时系统吞吐显著优于所有基线。
原文摘要 · Abstract (English)
Lifelong Multi-Agent Path Finding (LMAPF) requires generating collision-free paths for large agent fleets under strict real-time constraints. Reactive frameworks such as PIBT and Enhanced PIBT (EPIBT) scale effortlessly to thousands of agents through rule-based, step-by-step coordination but suffer from severe temporal myopia, making them ineffective in scenarios where long-horizon reasoning is essential. RHCR plans windowed paths over multi-step horizons but incurs substantial planning overheads that hinder scalability. TP tackles both challenges by planning only subsets of agents at each timestep, yet its applicability is restricted to highly structured maps. To achieve long-horizon planning at scale across general maps, we propose Path Updates over Staggered Horizons (PUSH), a LMAPF planner capable of coordinating thousands of agents in under a second while planning over multi-step horizons. PUSH combines the key advantages of PIBT, RHCR, and TP. Like TP, PUSH reduces computational complexity by planning only a subset of agents at each timestep using staggered planning windows. Unlike TP, however, PUSH plans RHCR-style windowed paths in general maps without relying on restrictive map assumptions. To maintain high throughput in congested environments, PUSH further integrates EPIBT-inspired priority inheritance, backtracking, and anytime improvements into its windowed planning. Empirical evaluations across two realistic MAPF scenarios requiring long-horizon reasoning show that PUSH scales to the same massive agent loads as EPIBT (e.g., 10k agents) while achieving significantly higher system throughput than all baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。