An Emprical Comparison of the Hardness of Multi-agent Path Finding under the Makespan and the Sum of Costs Objectives

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 em- pirically 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 experi- mental evaluation shows that MAPF under the makespan ob- jective is easier across all the tested solvers and domains

Keywords

• Emprical Comparison
• Multi-agent Path Finding
• Makespan
• Sum Costs Objectives