cs.AINov 5, 2026

Goal-Branching LaCAM: Temporary Goals as Search Branches in Dense Multi-Agent Pathfinding

Authors: Stephen Chang, Daniel Harabor

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

Explore similar work

CardsList
  1. ITA-LaCAM: A Complete and Scalable TAPF Solver via Assignment-Aware Configuration-Space Search

    Sep 13, 2026Yimin Tang, Han Zhang, Shao-Hung Chan +4Multi-Agent Path FindingMulti-Robot Task Allocation

  2. A Lightweight Traffic Map for Efficient Anytime LaCAM*

    Mar 9, 2026Bojie Shen, Yue Zhang, Zhe Chen +1Multi-Agent Path Finding