Compiling Cost-Optimal Multi-Agent Pathfinding to ASP

Multi-Agent Pathfinding (MAPF) over grids is the problem of finding n non-conflicting paths that lead n agents from a given initial cell to a given goal cell. Cost-optimal MAPF in addition minimizes the total number of actions performed by each agent before stopping at the goal. Being a combinatorial problem in nature, a number of compilations from MAPF to Answer Set Programming (ASP) exist. In this paper we propose a new one, which unlike existing ASP approaches (1) produces cost-optimal solutions, (2) exploits information that can be pre-computed quickly using Dijkstra

Authors

• Rodrigo N. Gómez
• Carlos Hernández Ulloa
• Jorge A. Baier

Keywords

No keywords are indexed for this paper.