跳转至

文章背景与核心概要

终身多智能体路径规划（LMAPF）是在严格的实时约束下，为大规模智能体机群生成无碰撞路径的关键技术。现有的主流方法往往面临两难境地：诸如 PIBT 和 EPIBT 的反应式框架扩展性强，但存在严重的“时间短视”问题；而像 RHCR 这样采用多步视界的规划器则计算开销巨大，难以扩展；另有一些方法（如 TP）虽然缓解了计算压力，但严格依赖于高度结构化的地图。

为了突破这些限制，本文提出了全新的人工智能与机器人领域规划器 —— PUSH（Path Updates over Staggered Horizons，基于错时视界的路径更新）。PUSH 巧妙融合了 PIBT、RHCR 和 TP 三者的核心优势，通过引入错时规划窗口（staggered planning windows）大幅降低了计算复杂度，支持通用地图而无须苛刻的假设，并集成了优先级继承、回溯以及随时优化（anytime improvement）机制。实验表明，PUSH 能够在秒级内协调数千个智能体，在支持超大规模智能体负载（如 10,000 个智能体）的同时，系统吞吐量远超现有基线算法。

Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF

Authors: Vaibhav Sanjay, Jiaoyang Li
Subjects: Multiagent Systems (cs.MA); Artificial Intelligence (cs.AI); Robotics (cs.RO)
arXiv Identifier: arXiv:2608.06702 [cs.MA]
Submitted: August 7, 2026

Authors: Vaibhav Sanjay, Jiaoyang Li
Subjects: Multiagent Systems (cs.MA); Artificial Intelligence (cs.AI); Robotics (cs.RO)
arXiv Identifier: arXiv:2608.06702 [cs.MA]
Submitted: August 7, 2026

Summary

Lifelong Multi-Agent Path Finding (LMAPF) requires generating collision-free paths for large agent fleets under strict real-time constraints. Existing methods either suffer from temporal myopia (such as reactive frameworks like PIBT and EPIBT) or incur substantial planning overheads that hurt scalability (such as RHCR), while others are restricted to highly structured maps (like TP).

To overcome these limitations, this paper proposes PUSH (Path Updates over Staggered Horizons), a novel LMAPF planner capable of coordinating thousands of agents in under a second while performing multi-step horizon planning on general maps. PUSH combines the strengths of PIBT, RHCR, and TP by utilizing staggered planning windows to reduce computational complexity, avoiding restrictive map assumptions, and integrating priority inheritance, backtracking, and anytime improvements. Empirical evaluations demonstrate that PUSH scales effectively to massive agent loads (e.g., 10,000 agents) while achieving significantly higher system throughput than existing baselines.

终身多智能体路径规划（LMAPF）需要在严格的实时约束下，为大规模智能体机群生成无碰撞的路径。现有的方法要么存在时间短视问题（例如 PIBT 和 EPIBT 等反应式框架），要么产生巨大的规划开销从而损害可扩展性（例如 RHCR），而其他方法则受限于高度结构化的地图（例如 TP）。

为了克服这些局限性，本文提出了 PUSH（Path Updates over Staggered Horizons）。这是一种新颖的 LMAPF 规划器，能够在不到一秒的时间内协调数千个智能体，同时在通用地图上执行多步视界规划。PUSH 结合了 PIBT、RHCR 和 TP 的优势：利用错时规划窗口降低计算复杂度，避免严苛的地图假设，并集成了优先级继承、回溯和随时优化机制。实证评估表明，PUSH 可以有效地扩展到大规模智能体负载（例如 10,000 个智能体），同时实现比现有基线显著更高的系统吞吐量。

Abstract

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: * Subset Planning: Like TP, PUSH reduces computational complexity by planning only a subset of agents at each timestep using staggered planning windows. * General Map Support: Unlike TP, PUSH plans RHCR-style windowed paths in general maps without relying on restrictive map assumptions. * High Throughput in Congested Environments: PUSH 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.

终身多智能体路径规划（LMAPF）需要在严格的实时约束下为大规模智能体机群生成无碰撞路径。诸如 PIBT 和增强型 PIBT（EPIBT）等反应式框架通过基于规则的逐步协调，可以轻松扩展到数千个智能体，但它们遭受严重的时间短视，这使得它们在需要长远视界推理的场景中效率低下。

RHCR 在多步视界上规划窗口路径，但会产生阻碍可扩展性的巨大规划开销。TP 通过在每个时间步仅规划智能体的子集来应对这两项挑战，但其适用性受限于高度结构化的地图。为了在通用地图上实现大规模的长远视界规划，我们提出了基于错时视界的路径更新（PUSH），这是一种 LMAPF 规划器，能够在不到一秒的时间内协调数千个智能体，同时进行多步视界规划。

PUSH 结合了 PIBT、RHCR 和 TP 的核心优势： * 子集规划（Subset Planning）： 与 TP 类似，PUSH 通过使用错时规划窗口在每个时间步仅规划智能体的子集，从而降低了计算复杂度。 * 通用地图支持（General Map Support）： 与 TP 不同，PUSH 在通用地图中规划 RHCR 风格的窗口路径，而不依赖于限制性的地图假设。 * 拥挤环境中的高吞吐量（High Throughput in Congested Environments）： PUSH 将受 EPIBT 启发的优先级继承、回溯和随时优化机制集成到其窗口规划中。

两个需要长远视界推理的真实 MAPF 场景的实证评估表明，PUSH 能够扩展到与 EPIBT 相同的大规模智能体负载（例如 1 万个智能体），同时实现比所有基线显著更高的系统吞吐量。

Additional Metadata