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

arXiv: https://arxiv.org/abs/2609.39559 · HTML: https://mlsanity.com/paper/2609.39559/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 36 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 11 of 11)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [SCRIMP: Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2303.00605/) (2023)
- [Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning](https://mlsanity.com/paper/2310.01207/) (2023)
- [POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding](https://mlsanity.com/paper/2407.14931/) (2024)
- [Multi-Agent Path Finding with Delay Probabilities](https://mlsanity.com/paper/1612.05309/) (2016)
- [Iterative Refinement for Real-Time Multi-Robot Path Planning](https://mlsanity.com/paper/2102.12331/) (2021)
- [RAILGUN: A Unified Convolutional Policy for Multi-Agent Path Finding Across Different Environments and Tasks](https://mlsanity.com/paper/2503.02992/) (2025)
- [Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing](https://mlsanity.com/paper/2601.19388/) (2026)

## Abstract (arXiv)

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 ≈!1,900× 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× per-instance speedup over Judgelight.