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
2021Proceedings of the International Symposium on Combinatorial Search25 citationsDOIOpen Access PDF
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.
Topics & Concepts
Job shop schedulingPath (computing)Task (project management)Mathematical optimizationComputer scienceMathematicsEconomicsScheduleManagementProgramming languageOperating systemRobotic Path Planning AlgorithmsRobotics and Sensor-Based LocalizationAI-based Problem Solving and Planning