MAPF-Collapse takes an already feasible joint MAPF plan and seeks to replace removable motion, such as an excursion that returns to a vertex, with waiting while preserving collision freedom. The problem is motivated by fast modern MAPF solvers, especially learning-based systems, which may produce feasible schedules containing redundant moves rather than minimum-cost schedules. A plan is defined on an undirected graph, with agents waiting or traversing edges over time, and feasibility requires avoiding vertex collisions and edge swaps. The paper's central observation is that only a limited subset of agents often needs joint reasoning after collapse. Thus, the difficult part can be a small coupled residue rather than the full fleet.
The main contribution is an exact decomposition of MAPF-Collapse into connected components of an interaction graph derived from agents' relevant motion and reachability. For singleton components, the paper introduces 1-MAPFC, which computes an optimal collapsed plan in time linear in the input plan length. For non-trivial components, it provides Collapse-CBS, an exact CBS-like solver, while also allowing Judgelight to be applied separately to each component. The resulting framework uses no commercial ILP solver, preserves the quality of Judgelight, and can choose a solver regime according to component difficulty. This turns coordination-light cases into collections of cheap independent solves while retaining an exact joint fallback for harder residue.
The framework first identifies which agents could interact after collapse and builds an interaction graph whose connected components define self-contained sub-instances. A structural property of collision-free input plans is used: collapse operations cannot create a new edge collision, so the decomposition mainly has to enforce vertex-collision avoidance. A singleton is sent to 1-MAPFC, which represents possible collapses as a Collapse-DAG and finds a minimum-cost path through that graph. The resulting plan waits at an anchor across selected collapse arcs and follows the original plan elsewhere. A non-singleton is solved jointly, either with Judgelight or with Collapse-CBS, whose low-level search uses constrained single-agent planning and whose high level resolves collisions lazily by branching. Component solutions are then combined into the global plan.
The experiments use MAPF-Collapse instances derived from the POGEMA suite, covering the Random, Maze, Warehouse, MovingAI city tiles, and Puzzle families. Following the prior evaluation setup, each input schedule is generated with POGEMA's BatchAStarAgent, and the principal baseline is the ILP-based Judgelight of Tang, Koenig, and Biyik. The study measures solver cost, runtime, success rate, the fraction of singleton components, the sizes of non-trivial components, and the comparison between Collapse-CBS and Judgelight. It uses Python implementations and the public release of Judgelight. The supplied excerpt omits many exact scenario counts and detailed per-row experimental values, so those facts cannot be established here.
The decomposition is valuable because it moves joint optimization out of the large population of agents that never need to coordinate. The reported singleton primitive is approximately 1,900 times faster than Judgelight, while the hybrid planner can use Collapse-CBS on coupled components and fall back to Judgelight when a component is dense or difficult. This advantage is conditional: the framework depends on a small-component structure, and Collapse-CBS can still develop a prohibitive search tree when a component is large. The paper therefore presents the method as a regime-aware exact framework rather than a universally faster replacement for joint optimization. Future directions include adapting interval constraints and mutex propagation, and reusing information across repeated planning episodes in lifelong or online MAPF.
Multi-agent path finding plans collision-free routes for multiple agents on a shared graph and is relevant to automated warehouses, robotic fulfillment, and large logistics fleets. Search-based and learned MAPF solvers increasingly prioritize producing feasible schedules quickly at fleet and horizon scales where optimal search is difficult. Such schedules can contain oscillations or other movements that do not contribute to the final objective. MAPF-Collapse formalizes the subsequent cleanup step: apply valid collapse operations that convert redundant motion into waits. The task is computationally hard, which motivates exploiting structure in the particular input plan.
The input consists of an undirected graph and a collision-free joint plan for several agents. Each single-agent plan is a time sequence in which every step is either a wait or a move along an edge, and its cost is its number of moves. A collapse replaces a closed walk that returns to an anchor vertex with waiting at that anchor over the corresponding interval. The goal is to select collapses so that the resulting joint plan remains feasible and has minimum total move cost. The prior Judgelight formulation models all agents jointly, even when only a small subset has dependencies.
The interaction graph partitions the instance into connected components that can be solved independently. For collision-free input, the paper establishes that collapse does not introduce edge conflicts, allowing the decomposition to focus on vertex conflicts. The singleton solver reduces one-agent optimization to a shortest-path problem in a Collapse-DAG and supplies a per-agent lower bound for global search. Judgelight encodes candidate collapses and their dependencies in an ILP, whereas Collapse-CBS discovers the relevant coupling lazily within each non-trivial component. The paper notes that even after Judgelight's reductions, candidate construction can be quartic in an agent's plan length in the worst case.
The evaluation asks four questions: how expensive 1-MAPFC is, how interaction components look in practice, how Collapse-CBS compares with Judgelight on non-trivial components, and how the complete Divide-and-Collapse framework compares with Judgelight. POGEMA-derived schedules provide the test inputs across the five named families. NoCollapse is used as an untouched-plan reference, while IndepLB sums isolated-agent optima and serves as a bound rather than a solver because those optima may be jointly infeasible. The excerpt does not establish the exact number of scenarios, all cutoff settings, or every component-level result.
The paper reports that 1-MAPFC runs in linear time in the single-agent plan length and is approximately 1,900 times faster than Judgelight for singleton components. Divide-and-Collapse matches Judgelight's solution quality, and the framework is exact on every component solved by Collapse-CBS; it does not return a costlier plan than Judgelight. Across all reported benchmarks, the regime-aware hybrid achieves a median 10.5x per-instance speedup over Judgelight. On coordination-heavy instances, Collapse-CBS may become impractical, so the planner falls back to Judgelight for the difficult portion described by the paper.
The paper concludes that MAPF-Collapse should be decomposed according to actual agent interaction rather than optimized as one global problem by default. Linear-time singleton processing plus exact joint solving for the coupled residue preserves optimality while substantially reducing runtime when the interaction structure is favorable. The reported POGEMA evaluation supports this design on the tested benchmark families. Large coupled components remain an unresolved performance bottleneck.
The speedup relies on the small-component hypothesis: many singleton agents and relatively small non-trivial components. Collapse-CBS still suffers from search-tree growth on large components, so the proposed framework is not uniformly fast across all instance structures. The evaluation is based on POGEMA-derived schedules and the five listed families; the excerpt does not establish behavior for other schedule generators, online replanning systems, or different MAPF variants. Because several exact benchmark counts and detailed conditions are missing from the supplied evidence, the numerical results should not be generalized beyond what is explicitly reported.
This work contributes a structural way to make exact MAPF plan cleanup practical without requiring a commercial ILP solver. It is especially relevant when a learned or fast feasible planner repeatedly emits redundant motion that can be removed after planning. Concentrating expensive coordination reasoning on the coupled residue may improve the scalability of post-processing for large fleets. The approach also connects MAPF post-optimization with interaction-based decomposition and CBS-style search.
The paper is recommended for researchers studying MAPF-Collapse, MAPF schedule post-optimization, agent-interaction decomposition, and CBS-like exact search. It is also useful for work on learned or lifelong MAPF where feasible plans must be cleaned up repeatedly without sacrificing feasibility. Readers interested in the conditions behind large speedups, and in the remaining bottleneck of dense coupled components, will find the paper particularly relevant.