On Improving the Quality of Solutions in Large-Scale Cooperative Multi-Agent Pathfinding

Abstract

Scaling up the number of simultaneously moving units in pathfinding problems to hundreds, or even thousands, is well beyond the capability of theoretically optimal algorithms in practice, which is consistent with existing intractability results. Significant scalability can be achieved by trading off solution optimality, which motivates evaluating the quality of suboptimal solutions, especially in instances much larger than can be handled by optimal algorithms. We consider pathfinding in uniform cost grid maps, and we study the solution quality using the three most common quality criteria, total travel distance, sum of actions, and makespan. We focus on MAPP, which has been shown as state-of-the-art in terms of scalability and success ratio (i.e., percentage of solved units) on realistic game grid maps. Until now, the quality of MAPP's solutions had not been as extensively analyzed. We introduced enhancements that significantly improve MAPP's solution quality. For example, its sum of actions is cut to half on average. MAPP becomes competitive in terms of solution quality with FAR and WHCA*, two successful algorithms from the literature. To evaluate the quality of suboptimal solutions in instances beyond the capability of optimal algorithms, we use lower bounds of optimal values to show our solutions have a reasonable quality. For example, MAPP's average total travel distance is 19 percent longer than the lower bound.