TY - JOUR AU - Gómez, Rodrigo N. AU - Hernández, Carlos AU - Baier, Jorge A. PY - 2020/04/03 Y2 - 2024/03/28 TI - Solving Sum-of-Costs Multi-Agent Pathfinding with Answer-Set Programming JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 34 IS - 06 SE - AAAI Technical Track: Planning, Routing, and Scheduling DO - 10.1609/aaai.v34i06.6540 UR - https://ojs.aaai.org/index.php/AAAI/article/view/6540 SP - 9867-9874 AB - <p>Solving a Multi-Agent Pathfinding (MAPF) problem involves finding non-conflicting paths that lead a number of agents to their goal location. In the sum-of-costs variant of MAPF, one is also required to minimize the total number of moves performed by agents before stopping at the goal. Not surprisingly, since MAPF is combinatorial, a number of compilations to Satisfiability solving (SAT) and Answer Set Programming (ASP) exist. In this paper, we propose the first family of compilations to ASP that solve sum-of-costs MAPF over 4-connected grids. Unlike existing compilations to ASP that we are aware of, our encoding is the first that, after grounding, produces a number of clauses that is <em>linear</em> on the number of agents. In addition, the representation of the optimization objective is also carefully written, such that its size after grounding does not depend on the size of the grid. In our experimental evaluation, we show that our approach outperforms search- and SAT-based sum-of-costs MAPF solvers when grids are congested with agents.</p> ER -