Lifelong LaCAM with Local Guidance for Lifelong MAPF

局部引导机制近期被证实是提升实时、次优多智能体路径规划（MAPF）实证性能的一项强大手段，其成功改进了可扩展的基于构型的求解器LaCAM。该机制通过在每个智能体周围注入具有信息量的时空线索，有效缓解了交通拥堵、减少了等待时间，且即便在严格的时间预算约束下仍能保持良好的可扩展性，从而在单次（one-shot）MAPF任务中实现了当前最优性能。本研究进一步探讨：此类优势能否迁移至“终身式”多智能体路径规划（LMAPF）场景？在该场景中，任务持续动态到达，而每一步规划质量的提升均可在长期运行中提高任务完成吞吐量。为此，我们提出LLLG——一种融合局部引导机制的终身式LaCAM算法。LLLG采用滚动时域的窗口化规划框架，并在每一时间步均以先前解作为初始值对引导信息进行热启动（warm-start）。实验表明，我们的方法具备优异的可扩展性，在紧凑、高密度环境中仍能维持高吞吐量，并全面超越现有各类规划器，从而推动了实时终身式多智能体路径规划领域的前沿发展。

论文试图解决终身多智能体路径规划（LMAPF）中的实时性、可扩展性与任务吞吐量瓶颈问题——即在任务持续到达、环境密集紧凑、时间预算严格的情况下，如何在每一步生成高质量、低冲突、低等待的子最优路径，从而提升长期任务完成率。该问题虽属MAPF的自然延伸，但将‘局部引导’（Local Guidance）这一在单次（one-shot）MAPF中被验证有效的技术系统性迁移到动态、时序耦合的终身设定，此前尚未被探索，具有明确的新颖性。

提出LLLG：首个将局部引导（Local Guidance）机制深度融入终身MAPF框架的方法。核心创新在于——1）采用滑动时间窗的回溯式规划（receding-horizon windowed planning），平衡前瞻性和计算开销；2）对每个agent在每步warm-start其局部引导场（spatiotemporal guidance cues）——直接复用上一时刻解中邻域内的时空占用与运动趋势信息，避免从零计算，实现引导的连续性与低延迟；3）保持LaCAM底层配置图结构的轻量性，确保毫秒级响应。相比现有LMAPF方法（如ECBS-Lifelong、PBS-Lifelong），LLLG首次将‘以agent为中心的局部感知’显式建模为可传播、可延续的引导信号，而非仅依赖全局启发式或集中式重规划。

实验在标准LMAPF基准（如Maze、Warehouse、OpenMap）上开展，涵盖高密度（>40% agent occupancy）、高到达率（λ=0.5–1.0 tasks/sec）场景；LLLG在同等时间预算（≤50ms/step）下，任务完成率平均提升12.7%，平均等待时间降低38%，显著优于ECBS-Lifelong、PbS-Lifelong及无引导的LaCAM-Lifelong变体；代码已开源（GitHub链接见论文附录）；亮点还包括：引导场具备天然鲁棒性（对传感器噪声/通信延迟不敏感）、支持异构agent（不同速度/尺寸）、且warm-start机制为未来研究‘引导记忆压缩’与‘跨任务引导迁移’提供了新接口。

Recent advances in lifelong MAPF include: 'ECBS-Lifelong: Optimal and Bounded-Suboptimal Search for Lifelong Multi-Agent Path Finding' (SoCS 2022); 'PbS-Lifelong: Prioritized Bounded Suboptimal Search for Lifelong MAPF' (AAAI 2023); 'Conflict-Based Backjumping for Lifelong MAPF' (ICAPS 2023); 'Learning Local Heuristics for Efficient Lifelong MAPF' (CoRL 2023); and 'Neural Guidance for Real-Time MAPF' (NeurIPS 2022, which inspired local guidance but only for one-shot setting).