arXiv cs.AI· Stephen Chang, Daniel Harabor·· 11 小时前AI 评分26
Goal-Branching LaCAM：以临时目标作为搜索分支的密集多智能体路径规划
Goal-Branching LaCAM: Temporary Goals as Search Branches in Dense Multi-Agent Pathfinding
AI 导读
论文提出 Goal-Branching 方法，将阻塞智能体的临时目标作为 LaCAM 搜索的额外分支，并证明任意临时目标选择规则下算法仍保持完备性。
正文 · AI 翻译
摘要：LaCAM 是一种基于搜索的多智能体路径规划（MAPF）求解器，它在联合配置上运行深度优先搜索，使用 PIBT 生成后继节点，并惰性地添加单智能体约束以探索替代方案。尽管 LaCAM 是完备的，但它在密集、走廊众多的实例上可能表现不佳，因为从死锁中解出阻塞智能体需要多个智能体的协同移动，且往往要远离它们的目标，而 PIBT 的贪心单步后继很少提出这样的移动，LaCAM 只能通过逐个智能体枚举约束来达到。本文提出 Goal-Branching，即为阻塞智能体赋予临时目标，每个临时目标作为 LaCAM 搜索的一个额外分支进行尝试。我们研究了选择这些临时目标的随机规则和走廊感知规则，并证明对任何此类规则完备性都得以保持。在三个迷宫和房间地图的密集实例（60-90% 的空闲单元格被占用）上，Goal-Branching 求解了 89% 的实例，而 LaCAM* 为 44%；在两者都能求解的实例上，它在 maze-32-32-2 和 room-32-32-4 上找到首个解的速度快 10-14 倍，在 room-32-32-4 上 75% 密度时的中位时间快近 200 倍。在两者都能求解的实例上，解的成本增加 15-22%，而在开放地图和完整的 MovingAI 基准上，其解的成本不高于 LaCAM*，且速度最多慢 3%。
| 学科： | 人工智能（cs.AI） |
| 引用为： | arXiv:2611.07528 [cs.AI] |
| （或 arXiv:2611.07528v1 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.07528 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Stephen Chang [查看电子邮件]
[v1]
2026年11月5日星期四 06:39:06 UTC（184 KB）
来源：arXiv cs.AI · arxiv.org