Chang and Harabor propose Goal-Branching LaCAM for dense multi-agent pathfinding

Chang and Harabor propose Goal-Branching LaCAM for dense multi-agent pathfinding

Authors Stephen Chang and Daniel Harabor propose Goal-Branching for multi-agent pathfinding (MAPF), where a solver searches for paths for multiple agents sharing a space. They say LaCAM can struggle in dense, corridor-heavy instances because resolving deadlocks may require several agents to move together, sometimes away from their goals. Their approach gives blocking agents temporary goals and tries each as an additional branch of LaCAM’s search; they report that completeness is preserved for any rule used to choose those goals. On dense instances across three maze and room maps, the authors report that Goal-Branching solves 89% of instances, compared with 44% for LaCAM*. On instances both methods solve, they report first solutions 10–14 times faster on two named maps, and nearly 200 times faster in median time at 75% density on one map. They also report a trade-off: solution cost is 15–22% higher on instances both methods solve. On open maps and the full MovingAI benchmark, they report no higher solution cost than LaCAM* and at most a 3% slowdown. These results describe the tested maps and benchmark; the abstract does not establish how the approach performs on other dense maps or in real-world deployments.

Publication: ceacea5f-c1a2-4fa3-8acd-441c254c85ae

attribution — pass: The proposal, the completeness result and all benchmark figures are attributed to authors Stephen Chang and Daniel Harabor. Nothing is presented as independently verified.

Authors:Stephen Chang, Daniel Harabor

summary — uncertain: The summary explains MAPF, but it never says LaCAM is an existing search-based MAPF solver that the paper modifies. It also does not distinguish LaCAM from LaCAM*, the baseline used in comparisons. Smallest repair: add one clause that LaCAM is an existing search-based solver (a tooltip for LaCAM* would also help). The terms completeness and solution cost need term-library tooltips. A minor softening also appears: the source says coordinated moves are needed and are often away from goals; the draft says they 'may' be needed and are 'sometimes' away from goals. The draft could restore 'often'.

LaCAM is a search-based solver for multi-agent pathfinding (MAPF) that runs a depth-first search over joint configurations

date — pass: The originalPublished date of 2026-11-05 matches the arXiv v1 submission date. It does not use the later feed date.

[Submitted on 5 Nov 2026]

support — pass: Each claim matches the abstract: the 89% versus 44% solve rates, the 10-14x and nearly 200x speedups, the 15-22% cost increase and the at most 3% slowdown. The limitations and the question correctly note scope (three maps, benchmark only, abstract only). The draft adds no invented benefits or deployments.

Goal-Branching solves 89% of instances against 44% for LaCAM*

media — pass: The selected media is the verified direct link to the arXiv abstract page for this paper.