MAPF-Collapse separates independent agents to remove unnecessary moves

A collision-free multi-agent plan can still contain unnecessary movement. An agent might leave a location, make a detour, and return even though waiting would have worked. Divide and Collapse, a paper by Oren Salzman, studies how to remove such movement without introducing conflicts between agents.
The starting point is an existing feasible plan. The method does not search freely for new routes: it replaces eligible sections of an agent's walk with waits at an anchor position. That restricted operation makes it possible to reason precisely about which agents can be optimized independently.

Fewer moves on the same timeline

MAPF-Collapse minimizes the number of moves, rather than the time needed to finish the plan. Turning a detour into waits preserves the original time steps and the agent's endpoints. Other agents continue following their own timelines.
That distinction matters when interpreting the improvement. A simplified plan can require less movement while keeping the same completion schedule. The paper does not establish corresponding measurements of energy savings or physical robot performance.
A change that looks harmless for one agent can still create a collision. Waiting at a location might put it in another agent's path at a later time. The problem therefore needs to identify genuine independence before separating the work.

An interaction graph limits joint reasoning

The framework computes the position-and-time cells each agent could occupy under allowed collapses. Overlap between these reach sets defines an interaction graph. Agents in different connected components cannot collide through the permitted changes, so their optimization problems can be solved separately.
Combining optimal component plans gives a global optimum for the MAPF-Collapse problem. That guarantee applies to the restricted set of collapses of the input plan, not to all possible multi-agent paths.
Isolated agents use a linear-time solver. Components that still require coordination need a joint solver. The paper introduces Collapse Conflict-Based Search, or C-CBS, which focuses on conflicts between collapsed plans. It also describes using the existing ILP-based Judgelight solver for harder components.

Reported gains depend on the coordination regime

The authors report an approximately 1,900-fold speedup over Judgelight for cases requiring no coordination. This is the lightweight isolated-agent solver's comparison, not a claim that the whole navigation pipeline becomes that much faster.
For the tested benchmarks, a regime-aware hybrid reports a median 10.5-fold per-instance speedup. It uses the decomposition and selects a solver for the remaining coupled work, including a Judgelight fallback. The standalone decomposition approach should therefore not be confused with a claim that every hybrid run avoids ILP.
The practical contribution is a way to stop treating every agent as part of one equally difficult optimization problem. Its benefit depends on how much of the original plan is truly independent and how large the remaining coordination components are.