Study Finds MAPF Decomposition Efficient Under Low Agent Density

This study evaluates the computational impact of decomposing Multi-Agent Path Finding (MAPF) instances into subproblems. Across 22,300 benchmark instances, decomposition generally adds minimal overhead—under 1 second and less than 1 MB of memory—while significantly reducing problem size in maps with abundant free grids. However, as agent density increases and free space narrows, decomposition becomes less effective, often collapsing back into a single unsplit problem. The results show decomposition is highly practical for sparse environments but limited in densely packed scenarios.