AAAI Publications, Ninth Annual Symposium on Combinatorial Search

Font Size: 
An Empirical Comparison of the Hardness of Multi-Agent Path Finding under the Makespan and the Sum of Costs Objectives
Pavel Surynek, Ariel Felner, Roni Stern, Eli Boyarski

Last modified: 2016-06-20


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.


multi-agent path-finding; optimization; sum-of-costs; makespan; search; satisfiability

Full Text: PDF