Goal-Branching extends LaCAM pathfinding solver on dense maze maps
A new arXiv paper proposes giving blocking agents temporary goals as extra search branches, reporting large speedups on dense instances at some cost in solution quality.
In plain words
Multi-agent pathfinding means planning collision-free routes for many agents at once. The paper adds a change to the LaCAM solver: when agents block each other, the solver tries temporary goals for them as new search branches. The authors report this unlocks dense, maze-like cases LaCAM handles poorly, though planned routes get longer.
What was announced
LaCAM, a search-based multi-agent pathfinding solver, runs a depth-first search over joint configurations and uses PIBT to generate successors, adding single-agent constraints lazily. According to the paper, its completeness does not prevent struggles on dense, corridor-heavy instances: freeing blocked agents requires coordinated moves, often away from agents' goals, which PIBT's greedy one-step successors rarely propose and which LaCAM reaches only by enumerating constraints one agent at a time.
Goal-Branching, the proposed change, gives blocking agents temporary goals, each tried as an additional search branch, with random and corridor-aware rules for choosing them; the authors state completeness is preserved for any such rule. On dense instances with 60-90% of free cells occupied across three maze and room maps, they report an 89% solve rate versus 44% for LaCAM*, first solutions 10-14x faster on maze-32-32-2 and room-32-32-4, and nearly 200x faster median time at 75% density on room-32-32-4. The trade-off: solution costs rose 15-22% on instances both solvers completed, though on open maps and the full MovingAI benchmark costs matched LaCAM* with at most 3% slowdown.
What it does not show
- Evidence is limited to the paper's abstract; the full method, experiments and implementation details were not reviewed, and the reported results are the authors' own, not independently confirmed.
Sources
Source-support review completed 13 Nov 2026. This story was drafted with AI assistance and checked against retained source passages. Automated checking is not independent verification.
Coverage: arXiv: abstract.
Updates and corrections
No corrections so far.
First published 13 Nov 2026
New to the subject? AI from the Ground Up starts from the beginning.