Local Guidance for Configuration-Based Multi-Agent Pathfinding¶

会议: AAAI 2026
arXiv: 2510.19072
代码: https://github.com/allegorywrite/lg_lacam
领域: 优化/理论 / 多智能体路径规划
关键词: MAPF, 局部引导, LaCAM, 拥塞缓解, 时空搜索

一句话总结¶

提出局部引导（Local Guidance）概念改进 LaCAM 的多智能体路径规划，通过在每个配置生成步为每个智能体构造局部时空路径来缓解拥塞，最高可将解的代价降低 50%，同时保持 1000 智能体下几秒内完成。

领域现状：MAPF（多智能体路径规划）追求在图上为所有智能体找到无碰撞路径。LaCAM 等基于配置的求解器可快速处理上千智能体，但解的质量高度次优。

现有痛点：已有的"引导"方法（guidance）通过全局考虑整个环境和所有智能体来缓解拥塞，但全局引导是时间无关的，丢失了时空信息，在瓶颈区域效果有限。

核心矛盾：全局引导太粗糙——知道"哪条路不堵"但不知道"什么时候哪里堵"；精确解太昂贵——考虑完整碰撞约束计算量爆炸。

切入角度：局部引导位于两者之间——在每个智能体周围的局部时空窗口内构建引导路径，比全局引导更精确（有时空感知），比精确解更轻量。

在 LaCAM 框架内，每次配置生成时调用局部引导构造：为每个智能体在窗口 \(w\) 内规划一条避免碰撞的短期路径 \(\Phi[i]\)，然后用 \(\Phi[i][1]\)（第一步目标位置）指导 PIBT 的偏好排序。

局部引导构造 (Algorithm 1):
- 功能：为每个智能体独立规划 \(w\) 步的短期路径，考虑与其他智能体路径的碰撞
- 核心思路：每个智能体执行基于代价的 windowed space-time A*，代价函数为 \(c(\pi[t], \pi[t+1]) = \langle 1 + \alpha \cdot \mathsf{Ind}[\chi > 0], \chi \rangle\)，其中 \(\chi\) 是与其他路径的碰撞数，\(\alpha=3\) 为碰撞惩罚权重
- 设计动机：软碰撞约束而非硬约束，允许一定碰撞但给予惩罚，使智能体在拥塞区域找到折衷路径
路径缓存与初始化 (Algorithm 2):
- 功能：利用上一步的引导路径初始化当前步，避免从头重新规划
- 核心思路：如果智能体 \(i\) 当前位置与上一步引导路径的第一步一致，则简单左移路径 \(\Phi_k[i][t] \leftarrow \Phi_{k-1}[i][t+1]\)
- 设计动机：将计划迭代需求从 2 次降至 1 次，大幅节省计算开销
智能体排序:
- 功能：按上一轮碰撞数降序排序智能体的规划顺序
- 核心思路：碰撞最多的智能体先规划，获得更自由的路径选择
- 设计动机：缓解顺序规划中的不公平性——先规划者约束少，后规划者约束多
全局+局部引导融合:
- 核心思路：修改代价函数加入全局引导偏移 \(c = \langle 1 + \alpha \cdot \mathsf{Ind}[\chi > 0], \delta(\pi[t+1]), \chi \rangle\)，其中 \(\delta(v)\) 是到全局引导路径的距离

单次引导构造：\(O(nw|V|\log(w|V|))\)，其中 \(n\) 为智能体数、\(w\) 为窗口大小、\(|V|\) 为图顶点数。

方法	maze-128	random-64	warehouse	den312d	平均降幅
LaCAM	baseline	baseline	baseline	baseline	—
GG (全局引导)	-14%	-8%	-15%	-12%	~12%
LG (局部引导)	-38%	-20%	-12%	-25%	~24%
LG+GG	-40%	-22%	-18%	-28%	~27%
LNS2	-30%	-15%	-10%	failed	—