  Generally, the calculation and memory space required for multi-agent path
finding (MAPF) grows exponentially as the number of agents increases. This
often results in some MAPF instances being unsolvable under limited
computational resources and memory space, thereby limiting the application of
MAPF in complex scenarios. Hence, we propose a decomposition approach for MAPF
instances, which breaks down instances involving a large number of agents into
multiple isolated subproblems involving fewer agents. Moreover, we present a
framework to enable general MAPF algorithms to solve each subproblem
independently and merge their solutions into one conflict-free final solution,
without compromising on solvability. Unlike existing works that propose
isolated methods aimed at reducing the time cost of MAPF, our method is
applicable to all MAPF methods. In our results, we apply decomposition to
multiple state-of-the-art MAPF methods using a classic MAPF benchmark
(https://movingai.com/benchmarks/mapf.html). The decomposition of MAPF
instances is completed on average within 1s, and its application to seven MAPF
methods reduces the memory usage and time cost significantly, particularly for
serial methods. To facilitate further research within the community, we have
made the source code of the proposed algorithm publicly available
(https://github.com/JoeYao-bit/LayeredMAPF).
