Publication

P. Surynek, A. Felner, R. Stern and E. Boyarski. Boolean Satisfiability Approach to Optimal Multi-Agent Path Finding under the Sum of Costs Objective. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1435-1436, 2016.

Abstract: This paper focuses on finding optimal solutions to the multi-agent path finding (MAPF) problem over undirected graphs where the task is to find non-colliding paths for multiple agents, each with a different start and goal position. An encoding of MAPF to Boolean satisfiability (SAT) is already known to the makespan optimal variant of the problem. In this paper we present the first SAT-solver for minimizing the sum of costs enabled by introducing cardinality constraints into the SAT encoding. An experimental evaluation on grid graphs indicate promising performance of the new SAT-based method in comparison with the best variants of previous sum-of-costs search solvers.

Download the paper in pdf.