Divide and Collapse: MAPF-Collapse via Exact Decomposition into Independent Sub-Instances

Oren Salzman

cs.AISep 30, 2026

Divide and Collapse: MAPF-Collapse via Exact Decomposition into Independent Sub-Instances

Authors: Oren Salzman

Organizations: Technion – Israel Institute of Technology

Abstract

In this work we study the problem of MAPFC, a post-optimization step for Multi-Agent Path Finding (MAPF) plans where we are given a feasible plan produced by a modern MAPF solver and are tasked with removing avoidable moves while preserving feasibility. This NP-hard problem naturally arises when using learning-based state-of-the-art (SOTA) solvers which construct plans that contain redundant moves that can be removed. Recently, Tang et al. presented Judgelight, which uses Integer Linear Programming (ILP) to solve MAPFC. Importantly, the ILP is constructed over all agents jointly, so its cost is governed by the full instance rather than by the small coupled residue that actually requires joint reasoning. Our key insight, motivating this work, is that MAPFC instances naturally decompose into independent sub-problems, most of which involve a single agent and can be solved without any inter-agent reasoning. To this end, we first identify which agents need to coordinate their motion and partition the instance into sub-problems accordingly. For the cases where no coordination is required, we introduce an extremely lightweight solver that is $\approx\!1{,}900\times$ faster than Judgelight. For cases where coordination is required, Judgelight can be used but we introduce an alternative CBS-like solver which is more efficient on easier problems. The resulting framework is exact, uses no commercial ILP solver, and matches Judgelight's quality while running substantially faster on the coordination-light majority of instances; on the coordination-heavy instances we propose a regime-aware hybrid planner that falls back to Judgelight. Over all benchmarks tested, this planner achieves a median $10.5\times$ per-instance speedup over Judgelight.

Figures & tables

Panel of Figure 1 — Figure 1: MAPF-Collapse problem. (a,b) Input graph $G$ and plan $M$ of cost $8$ . The problem calls for applying the Collapse operator (c) which replaces a closed walk that returns to a vertex, here $b\to c\to b$ , by waiting at $b$ . (d) Applying collapses yields the optimum $\Pi^{\star}$ of cost $4$ ; teal cells are moves turned into waits. Noteworthy is that agents $1$ and $2$ contend for $b$ and form one coupled component solved jointly, whereas agent $3$ never interacts which is the structure our framework exploits.

Panel of Figure 2 — Figure 2: Reach-set for the running example. Each cell $(v,t)$ is labeled with the agents whose reach set $\Reach^{i}$ includes it; an empty cell is in no reach set. The shaded cells form the intersection $\Reach^{1}\cap\Reach^{2}$ that witnesses the interaction edge $\{1,2\}$ of $H$ (Fig. 3 ). Agent $3$ ’s column (row $d$ ) is disjoint from the others, so $\{3\}$ is a singleton component.

Panel of Figure 3 — Figure 3: The interaction graph $H$ for the running example. Component $\{1,2\}$ is non-trivial (witnessed by $(b,1),(b,2),(b,3)\in\Reach^{1}\cap\Reach^{2}$ , the shaded cells of Fig. 2 ); agent $3$ is a singleton.

Panel of Figure 4 — Figure 4: The Collapse DAG $D_{G,\pi}$ for the plan $\pi=\langle a,b,c,b,e\rangle$ on the running-example graph. Above each node $t$ is the position $\pi(t)$ . Solid arrows are trace arcs (cost $\mathds{1}[\pi(t)\neq\pi(t{+}1)]$ ); the dashed arrow is the unique collapse arc at anchor $b$ . The minimum-cost path from $0$ to $4$ is $0\!\to\!1\!\to\!3\!\to\!4$ , has cost $2$ and uses the collapse arc.

Panel of Figure 5 — Figure 5: The C-CBS constraint tree of Ex. 6 on component $I_{1}=\{1,2\}$ . The root’s optimal plans collide at $(b,2)$ ; each child adds one negative constraint. Both children tie at LB $=4$ , but child A’s plans still collide at $(b,1)$ and $(b,3)$ , so the search returns child B’s conflict-free plan regardless of tie-breaking.

Family	Mean $\#$ agents	Singleton %	Median $H$ -build
01-random	$32$	$45.0\%$	$1.5$ ms
02-mazes	$32$	$37.9\%$	$1.8$ ms
03-warehouse	$112$	$32.6\%$	$10.5$ ms
04-movingai	$160$	$37.7\%$	$15.5$ ms
05-puzzles	$3$	$75.9\%$	$0.12$ ms
Overall	–	$43.8\%$	$3.0$ ms

Table 1: Per-family decomposition statistics. Mean #agents is the mean number of agents per instance, Singleton % is the per-instance mean of the agent singleton fraction, and Median

H

-build the median wall-clock to construct the interaction graph

H

(Alg. 1 ).

Figure 6: Per-family component-size distribution over the

3{,}296

instances: the fraction of components in each size bucket, on a log-scale

y

-axis, with singletons in the leftmost (size-

1

) bucket.

Component size $\|I_{\ell}\|$	$n$	C-CBS success rate	JL success rate	C-CBS med.	JL med.	Speedup	Mean saving
$[2,4]$	$5{,}236$	$100\%$	$100\%$	$\mathbf{0.26}$ ms	$4.37$ ms	$17.0\times$	$0.271$
$[5,9]$	$890$	$100\%$	$100\%$	$\mathbf{2.52}$ ms	$13.65$ ms	$5.4\times$	$0.389$
$[10,19]$	$542$	$99.8\%$	$100\%$	$\mathbf{20.14}$ ms	$43.59$ ms	$2.2\times$	$0.438$
$[20,29]$	$260$	$99.6\%$	$100\%$	$\mathbf{57.19}$ ms	$95.60$ ms	$1.7\times$	$0.438$
$[30,39]$	$223$	$96.9\%$	$100\%$	$\mathbf{124.49}$ ms	$149.24$ ms	$1.2\times$	$0.456$
$[40,50]$	$171$	$93.6\%$	$100\%$	$323.84$ ms	$\mathbf{250.22}$ ms	$0.8\times$	$0.493$

Table 2: Per-component statistics by size over all

8{,}291

non-trivial components;

n

is the number of components per bucket and success rate the fraction solved within the

5

-second per-component budget. Speedup is the ratio of the two medians shown; mean saving is the mean optimal per-component saving ratio

1-\OPT(I_{\ell})/\cost(M_{I_{\ell}})

over the components solved by both. The faster of the two medians is set in bold. The bottom row aggregates the

969

components larger than

50

agents: C-CBS exceeds the budget on

61.8\%

of them, so its median is reported as

>\!5

s; Speedup and Mean saving , both defined over the components solved by both, are omitted.

Figure 7: Runtime distribution over the

3{,}296

instances: cumulative fraction solved against the per-instance wall-clock budget (log scale).

Reference bounds
Configuration	Mean saving	Median time	Success rate
NoCollapse	$0.000$	$0.0$ ms	–
IndepLB (cost LB)	$0.393$	$1.6$ ms	–
Solvers
Judgelight	$0.359$	$420.9$ ms	$99.9\%$
DnC+JL	$0.359$	$421.3$ ms	$99.9\%$

Table 3: Aggregate metrics over the

3{,}296

instances under the

30

-second time limit. Mean saving is averaged over the instances a configuration solves; median time and success rate are over all

3{,}296

, so the two populations coincide for every row except those that do not solve all instances: DnC+C-CBS (

2{,}815/3{,}296

), Judgelight (

3{,}294/3{,}296

), and DnC+JL (

3{,}295/3{,}296

); Judgelight and DnC+JL still return a plan on the instances they exceed the limit on. The first two rows are reference bounds, not solvers: NoCollapse is the untouched input (zero saving) and IndepLB sums the per-agent optima, an upper bound on achievable saving that is generally jointly infeasible; a success rate is therefore undefined for them.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 8: Ablation of C-CBS ’s MAPF -based optimizations. Left: median high-level nodes expanded by component size (log scale). Right: success rate within the

5

s per-component budget.

	Judgelight		DnC+C-CBS $\rightarrow$ JL		No routing
Family	Saving	Median	Saving	Median	Median
01-random	$0.376$	$344.0$	$0.378$	$16.5$	$18.3$
02-mazes	$0.463$	$377.9$	$0.464$	$33.0$	$39.1$
03-warehouse	$0.273$	$1{,}490.8$	$0.273$	$1{,}011.8$	$1{,}432.5$
04-movingai	$0.170$	$640.8$	$0.170$	$594.4$	$2{,}080.9$
05-puzzles	$0.507$	$283.2$	$0.507$	$0.2$	$0.2$

Appendix

Table 4: Per-family comparison of Judgelight and the recommended DnC+C-CBS

\rightarrow

JL : mean saving ratio and median wall-clock (ms) over the full

3{,}296

-instance suite. The final column gives the median wall-clock of the regime-agnostic hybrid (every component sent through C-CBS first); the regime-aware hybrid leads Judgelight on every family, whereas the regime-agnostic variant is

3.2\times

slower on 04-movingai.

Explore similar work

Mar 24, 2026cs.MA

Planning over MAPF Agent Dependencies via Multi-Dependency PIBT

Modern Multi-Agent Path Finding (MAPF) algorithms must plan for hundreds to thousands of agents in congested environments within a second, requiring highly efficient algorithms. Priority Inheritance with Backtracking (PIBT) is a popular algorithm capable of effectively planning in such situations. However, PIBT, and its variants like Enhanced PIBT (EPIBT), is constrained by its rule-based planning procedure and lacks generality because it restricts its search to paths that collide with at most one other agent. In this paper, we describe a new perspective on solving MAPF by planning over agent dependencies. Taking inspiration from PIBT's priority inheritance logic, we define the concept of agent dependencies and propose Multi-Dependency PIBT (MD-PIBT) that searches over agent dependencies. MD-PIBT is a general framework where specific parameterizations can reproduce PIBT and EPIBT. At the same time, alternative configurations generalize PIBT and EPIBT to multi-step planning capable of reasoning paths that collide with more than one other agent. Our experiments demonstrate that MD-PIBT effectively plans for as many as 10,000 homogeneous agents under various kinodynamic constraints, including pebble motion, rotation motion, and differential drive robots with speed and acceleration limits. We perform thorough evaluations on different variants of MAPF and find that MD-PIBT is particularly effective in MAPF with large agents. Our code is available at https://github.com/lunjohnzhang/MD-PIBT.

Zixiang Jiang, Yulun Zhang, Rishi Veerapaneni +1

University Of Melbourne · Robotics Institute, Carnegie Mellon University

Multi-Agent Path Finding Planning Prioritization

Ask PDF

Aug 8, 2026cs.MA

AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding

Many research fields share a common structure: a set of agents, each pursuing its own goal, whose actions must be coordinated so that no two of them conflict. Multi-Agent Path Finding (MAPF) is a concrete instance of this structure, with applications from warehouses to road traffic and airports. Much of MAPF research assumes discrete time, circular agents sharing one spatial graph, a single goal per agent, and that an agent must remain at its goal once reached, precluding heterogeneous fleets, non-geometric conflicts, task sequences, and agents that move on after completing them. We generalise the MAPF formulation to lift these assumptions, and present Anytime-Optimal Continuous-time Conflict-Based Search (AOC-CBS), an exact and solution-complete solver for it. AOC-CBS guarantees the eventual return of an optimal solution, while reporting an incumbent with a known optimality gap upper bound throughout its runtime; it is configurable with a portfolio of repair functions, one of which we introduce (Tier-Prioritized Safe Interval Path Planning), and can exploit multiple processor cores. We demonstrate AOC-CBS on a mixed fleet of non-convex agents moving along smooth, kinodynamically feasible trajectories. Preliminary experiments against the exact solver OC-CBS, on well-known benchmarks and roadmaps we sample from them, show AOC-CBS is comparable at finding optimal solutions while extending scalability from the tens to the hundreds of agents when a bounded optimality gap is accepted.

Alvin Combrink, Sabino Francesco Roselli, Martin Fabian

Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden.

Multi-Agent Path Finding Path Planning

Ask PDF

May 8, 2026cs.AI

Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding

Multi-agent pathfinding (MAPF) is a widely used abstraction for multi-robot trajectory planning problems, where multiple homogeneous agents move simultaneously within a shared environment. Although solving MAPF optimally is NP-hard, scalable and efficient solvers are critical for real-world applications such as logistics and search-and-rescue. To this end, the research community has proposed various decentralized suboptimal MAPF solvers that leverage machine learning. Such methods frame MAPF (from a single agent perspective) as a Dec-POMDP where at each time step an agent has to decide an action based on the local observation and typically solve the problem via reinforcement learning or imitation learning. We follow the same approach but additionally introduce a learnable communication module tailored to enhance cooperation between agents via efficient feature sharing. We present the Local Communication for Multi-agent Pathfinding (LC-MAPF), a generalizable pre-trained model that applies multi-round communication between neighboring agents to exchange information and improve their coordination. Our experiments show that the introduced method outperforms the existing learning-based MAPF solvers, including IL and RL-based approaches, across diverse metrics in a diverse range of (unseen) test scenarios. Remarkably, the introduced communication mechanism does not compromise LC-MAPF's scalability, a common bottleneck for communication-based MAPF solvers.

Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk +5

CogAI Lab, Moscow, Russia

Multi-Agent Path Finding Multi-Robot Motion Planning Imitation Learning

Ask PDF