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
Figure 1: Worked example (Goal-Branching with the random rule). Circles are agents and Gi is the goal of agent Ai . (a) Start. (b) The swap technique pulls A2 out of the pocket at t=3 , but at t=4 the highest-priority agent A1 pushes it back, so the step returns to an explored configuration. (c) Goal-Branching gives A2 the temporary goal Y with pusher A1 . (d) A2 leads, A1 steps into the pocket Z , and A2 passes to Y . (e) A1 reaches its goal and τ2 is released. (f) Final solved configuration.
Figure 2: Dense bottleneck maps: success rate (top), time to first solution (middle) and sum of costs relative to the lower bound (bottom) against density, with agent counts along the top. Time and cost are medians over solved runs, shown where at least 5 runs were solved; the dotted line is the 30 s time limit. 125 runs per point (25 scenarios, five seeds). Error bars: range of the per-seed success rate (top) and interquartile range (middle, bottom).
Figure 3: Runs solved against time to first solution, pooled over the three bottleneck maps (2,625 runs per solver). A point at (x,y) means the solver solved x runs within y seconds; the legend gives the number solved within 30 s.
Solved (%)
Speed-up
Cost
Map
L ∗
L3
GB-r
GB-c
GB-r
GB-c
GB-r
GB-c
maze-2
30±1
28±1
86±2
87±2
13.8 ×
9.7 ×
1.36
1.30
maze-4
53±2
27±3
80±1
80±1
1.9 ×
2.0 ×
1.26
1.14
room-4
50±1
45±2
100±0
100±0
10.6 ×
9.7 ×
1.10
1.08
all
44±1
33±1
89±1
89±1
5.7 ×
5.2 ×
1.22
1.15
Table 1: Dense bottleneck maps, 60–90% density, 875 runs per map; maze-2, maze-4 and room-4 are maze-32-32-2, maze-32-32-4 and room-32-32-4. L ∗ /L3: LaCAM ∗ /LaCAM3; GB-r/GB-c: Goal-Branching with the random/corridor rule. Speed-up and cost relative to LaCAM ∗ (speed-up >1 is faster): geometric mean over runs that both LaCAM ∗ and the GB variant solved. Subscripts: standard deviation of the solved % across the five seeds. GB-r solved 1,161 runs that LaCAM ∗ did not, and LaCAM ∗ none that GB-r did not.
Speed-up
Identical plans
Map
GB-r
GB-c
GB-r
GB-c
random-32-32-10
0.99±0.01
0.99±0.01
84%
84%
random-32-32-20
1.16±0.04
1.15±0.04
29%
28%
empty-32-32
0.98±0.01
0.98±0.01
91%
91%
Table 2: Open maps, 70–95% density, 750 runs per map. All solvers solve 98–100% of runs. Speed-up: LaCAM ∗ ’s time to first solution over Goal-Branching’s, on runs both solved (geometric mean with SD across seeds; >1 is faster); cost is within 0.96–1.00. Identical plans: runs where Goal-Branching returns exactly LaCAM ∗ ’s plan.
Variant
Solved
Δ
p
Speed-up
Cost
Goal-Branching (default)
622
–
–
1.00
1.00
No immediate branches
594
−28
< .001
0.51
1.31
K=1
619
−3
.70
0.97
1.02
K=5
614
−8
.22
1.00
1.01
P=1
619
−3
.74
0.98
1.01
P=8
616
−6
.39
1.00
1.03
Table 3: Ablation on 675 dense runs (maze-32-32-2, maze-32-32-4, room-32-32-4; three densities each). Default: random rule, K=3 , P=4 , H=64 . No immediate branches: a jammed node’s goal branches are tried only when the search returns to it. Δ : solved relative to the default, or for the indented rows, relative to the row above; p : McNemar exact test; Speed-up: time to first solution of the reference over the variant’s ( >1 is faster); Cost: sum of costs relative to the reference. Speed-up and cost are geometric means over runs both solved.
Combined Target Assignment and Path Finding (TAPF) requires assigning targets for agents while simultaneously planning collision-free paths. We present ITA-LaCAM, a complete and scalable TAPF solver inspired by LaCAM and ITA-CBS. In ITA-LaCAM, each joint-configuration node carries an agent-to-target matching. When a successor is generated, ITA-LaCAM incrementally repairs the matching for the agents that moved and uses the targets to guide PIBT successor generation. This design enables adaptive reassignment without explicitly enumerating the combinatorial assignment space, while preserving LaCAM's completeness and scalability. Across 9,760 benchmark instances on eight maps with 5--200 agents, ITA-LaCAM solved 100% of the instances, compared with 95.6% for IR-TAPF configured with DBS-Hungarian. ITA-LaCAM found an initial solution faster in 84.0% of the comparisons and achieved a lower sum of costs in 65.0% of the instances solved by both methods.
Yimin Tang, Han Zhang, Shao-Hung Chan +4
Thomas Lord Department of Computer Science, University of Southern California · Symbotic · Department of Computer Science, University of California Irvine
Multi-Agent Path Finding (MAPF) aims to compute collision-free paths for multiple agents and has a wide range of practical applications. LaCAM*, an anytime configuration-based solver, currently represents the state of the art. Recent work has explored the use of guidance paths to steer LaCAM* toward configurations that avoid traffic congestion, thereby improving solution quality. However, existing approaches rely on Frank-Wolfe-style optimization that repeatedly invokes single-agent search before executing LaCAM*, resulting in substantial computational overhead for large-scale problems. Moreover, the guidance path is static and primarily beneficial for finding the first solution in LaCAM*. To address these limitations, we propose a new approach that leverages LaCAM*'s ability to construct a dynamic, lightweight traffic map during its search. Experimental results demonstrate that our method achieves higher solution quality than state-of-the-art guidance-path approaches across two MAPF variants.
Bojie Shen, Yue Zhang, Zhe Chen +1
Monash University, Faculty of Information Technology
Anonymous Multi-Agent Path Finding (AMAPF) admits polynomial-time network-flow algorithms for several objectives, including makespan, total distance, and sum-of-costs (SoC) when agents disappear upon reaching goals. We show that standard goal-staying AMAPF is fundamentally different. We first formulate SoC minimization by augmenting the standard time-expanded flow model with goal-settlement constraints and show that the resulting linear programming relaxation is non-integral. We then prove that minimizing SoC in goal-staying AMAPF is NP-hard via a reduction from 3-SAT. Together with the polynomial-time result for the disappearing variant, this establishes a sharp complexity boundary determined by whether completed agents remain at their goals.