On SAT-Based Approaches for Multi-Agent Path Finding with the Sum-of-Costs Objective

Abstract

Multi-agent path finding (MAPF) deals with the problem of finding collision-free paths for a set of agents. Each agent moves from its start location to its destination location in a shared environment represented by a graph. Reduction-based solving approaches for MAPF, for example reduction to SAT, exploit a time-expended layered graph, where each layer corresponds to specific time. Hence, these approaches are natural for minimizing makespan (the shortest time till all agents reach their destinations). Modeling the other frequently used objective, namely Sum of Costs (SOC; sum of paths lengths of all agents) is more difficult as the solution with the smallest SOC may not be reached in the time-expended graph with the smallest makespan. In this paper we suggest two novel approaches to estimate the makespan, that guarantees existence of a SOC-optimal solution. The approaches are empirically compared with an existing reduction-based method as well as with the state-of-the-art search-based optimal MAPF solver.