Adaptive Anytime Multi-Agent Path Finding with Density and Delay in Large Neighborhood Search

The Multi-Agent Path Finding (MAPF) problem is to find a set of collision-free paths for multiple agents within a shared environment while minimizing the total time spent. In MAPF, finding an optimal solution is NP-hard. And in some cases, finding suboptimal solutions is also NP-hard, with severe limitations imposed by the scale of the problem. Anytime multi-agent path planning (MAPF) is a promising method for path optimization in large-scale multi-agent systems. Large Neighborhood Search (LNS) is the foundation of the state-of-the-art anytime MAPF and can even perform well for large-scale issues. It discovers a fast solution at first, and then iteratively plans paths for subsets of agents produced via de-structive heuristic techniques to gradually enhance the quality of the solution until it approaches optimality. In this paper, we propose a subset selection algorithm based on maximum latency and density, which improves upon the subset selection rule of the existing state-of-the-art solver, MAPF-LNS. We conducted tens of thousands of experiments on multiple maps of the MAPF benchmark set with larger numbers of agents. Our experimental results indicate that our solver, MAPF-DD-LNS, significantly outperforms MAPF-LNS in both the quality of the final solution and the speed of resolution.