LaCAM is a search‑based solver for multi‑agent pathfinding (MAPF) that performs a depth‑first search over joint configurations, uses PIBT to generate successors, and lazily adds single‑agent constraints to explore alternatives. Although LaCAM is complete, it struggles on dense, corridor‑heavy instances because extracting blocking agents from deadlocks requires coordinated moves that often depart from their goals, and PIBT’s greedy one‑step successors rarely propose such moves; LaCAM can only reach them by enumerating constraints one agent at a time. This paper introduces Goal‑Branching, which assigns temporary goals to blocking agents and treats each temporary goal as an additional branch in LaCAM’s search. We evaluate random and corridor‑aware rules for selecting temporary goals and prove that completeness is preserved for any rule. Experiments on three maze and room maps with 60%–90% occupancy show that Goal‑Branching solves 89% of instances versus 44% for LaCAM, and on instances solved by both it finds the first solution 10–14× faster, with a median speedup of nearly 200× at 75% density on room‑32‑32‑4. Solution cost rises by 15%–22% on jointly solved instances, while on open maps and the full MovingAI benchmark costs are no higher than LaCAM and runtime is at most 3% slower.
Review