Goal-Branching LaCAM：用临时目标分支求解高密度多智能体路径规划
Goal-Branching LaCAM: Temporary Goals as Search Branches in Dense Multi-Agent Pathfinding
AI 导读
论文提出 Goal-Branching 方法，为 LaCAM 多智能体路径规划求解器中的阻塞智能体设置临时目标，作为搜索的额外分支，并证明任意选目标规则下完整性保持不变。
正文 · 原文
Abstract:LaCAM is a search-based solver for multi-agent pathfinding (MAPF) that runs a depth-first search over joint configurations, using PIBT to generate successors and lazily adding single-agent constraints to explore alternatives. Although LaCAM is complete, it can struggle on dense, corridor-heavy instances because extracting blocking agents from deadlocks requires coordinated moves of several agents, often away from their goals, which PIBT's greedy one-step successors rarely propose and which LaCAM can only reach by enumerating constraints one agent at a time. This paper proposes Goal-Branching, where blocking agents are given temporary goals, each tried as an additional branch of LaCAM's search. We examine random and corridor-aware rules for choosing these temporary goals and show that completeness is preserved for any such rule. On dense instances (60-90% of free cells occupied) of three maze and room maps, Goal-Branching solves 89% of instances against 44% for LaCAM*, and, on instances both solve, it finds a first solution 10-14x faster on maze-32-32-2 and room-32-32-4, and nearly 200x faster in median time at 75% density on room-32-32-4. Solution cost increases by 15-22% on instances both solve, while on open maps and the full MovingAI benchmark its solutions cost no more than those of LaCAM* and it is at most 3% slower.
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.07528 [cs.AI] |
| (or arXiv:2611.07528v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2611.07528 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Stephen Chang [view email]
[v1]
Thu, 5 Nov 2026 06:39:06 UTC (184 KB)
来源：arXiv cs.AI · arxiv.org