A New Method for Decomposing MAPF Problems Into Solvable Subproblems

This article introduces a structured methodology for decomposing Multi-Agent Pathfinding (MAPF) instances into smaller, solvable subproblems. The process begins by identifying agent dependencies and forming clusters through relevance graphs. These clusters are iteratively bipartitioned using unavoidable-agent analysis to minimize subproblem size while preserving solvability. Further refinement introduces levels based on solving-order constraints derived from directed graphs and strongly connected components. Finally, the approach outlines how to independently solve and safely merge subproblems using serial or parallel MAPF methods. While not guaranteed to achieve optimal decomposition, the framework progressively reduces complexity and maintains conflict-free feasibility.