Goal-Branching LaCAM: Temporary Goals as Search Branches in Dense Multi-Agent Pathfinding
Organizations: Monash University, Australia
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.
Figures & tables
| Solved (%) | Speed-up | Cost | ||||||
|---|---|---|---|---|---|---|---|---|
| Map | L ∗ | L3 | GB-r | GB-c | GB-r | GB-c | GB-r | GB-c |
| maze-2 | 13.8 | 9.7 | 1.36 | 1.30 | ||||
| maze-4 | 1.9 | 2.0 | 1.26 | 1.14 | ||||
| room-4 | 10.6 | 9.7 | 1.10 | 1.08 | ||||
| all | 5.7 | 5.2 | 1.22 | 1.15 | ||||
| Speed-up | Identical plans | |||
|---|---|---|---|---|
| Map | GB-r | GB-c | GB-r | GB-c |
| random-32-32-10 | 84% | 84% | ||
| random-32-32-20 | 29% | 28% | ||
| empty-32-32 | 91% | 91% | ||
| Variant | Solved | Speed-up | Cost | ||
| Goal-Branching (default) | 622 | – | – | 1.00 | 1.00 |
| No immediate branches | 594 | .001 | 0.51 | 1.31 | |
| 619 | .70 | 0.97 | 1.02 | ||
| 614 | .22 | 1.00 | 1.01 | ||
| 619 | .74 | 0.98 | 1.01 | ||
| 616 | .39 | 1.00 | 1.03 |
Multi-Agent Path Finding
Multi-agent path finding (MAPF) plans collision-free routes for multiple agents sharing an environment.
See all 100 papers