Publication

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.