A New Boolean Encoding for MAPF and its Performance with ASP and MaxSAT Solvers

Authors

  • Roberto Asín Achá Universidad de Concepción
  • Rodrigo López Pontificia Universidad Católica de Chile
  • Sebastián Hagedorn Pontificia Universidad Católica de Chile
  • Jorge A. Baier Pontificia Universidad Católica de Chile Instituto Milenio Fundamentos de los Datos

Keywords:

Combinatorial Optimization, Combinatorial Puzzles

Abstract

Multi-agent pathfinding (MAPF) is an NP-hard problem. As such, dense maps may be very hard to solve optimally. In such scenarios, compilation-based approaches, via Boolean satisfiability (SAT) and answer set programming (ASP), have proven to be most effective. In this paper, we propose a new encoding for MAPF, which we implement and solve using both ASP and MaxSAT solvers. Our encoding builds on a recent ASP encoding for MAPF but changes the way agent moves are encoded. This allows to represent swap and follow conflicts with binary clauses, which are known to work well along with conflict-based clause learning. For MaxSAT, we study different ways in which we may combine the MSU3 and LSU algorithms for maximum performance. Our results, over grid and warehouse maps, show that the ASP solver scales better when the number of agents is increased on grids with few obstacles, while the MaxSAT solver performs better in scenarios with more obstacles and fewer agents.

Downloads

Published

2021-07-21