← News

Agents & MCPSources: arXiv · 6 Nov 2026

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.