webmaster: Sven Koenig

Learn all about Multi-Agent Path Finding (MAPF)


P. Surynek, A. Felner, R. Stern and E. Boyarski. An Empirical Comparison of the Hardness of Multi-Agent Path Finding under the Makespan and the Sum of Costs Objectives. In Proceedings of the Symposium on Combinatorial Search (SoCS), pages 145-147, 2016.

Abstract: In the multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. Recently, existing makespan optimal SAT-based solvers for MAPF have been modified for the sum-of-costs objective. In this paper, we empirically compare the hardness of solving MAPF with SAT-based and search-based solvers under the makespan and the sum-of-costs objectives in a number of domains. The experimental evaluation shows that MAPF under the makespan objective is easier across all the tested solvers and domains.

Download the paper in pdf.

(last updated in 2022)