Multi-Agent Path Finding: A New Boolean Encoding

Simple item page
dc.contributor.authorAsin Acha, Roberto
dc.contributor.authorLopez, Rodrigo
dc.contributor.authorHagedorn, Sebastian
dc.contributor.authorBaier, Jorge A.
dc.date.accessioned2025-01-20T21:01:47Z
dc.date.available2025-01-20T21:01:47Z
dc.date.issued2022
dc.description.abstractMulti-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 been shown to outperform heuristic-search-based approaches, such as conflict-based search (CBS). In this paper, we propose a new Boolean encoding for MAPF, and show how to implement it in ASP and MaxSAT. A feature that distinguishes our encoding from existing ones is that swap and follow conflicts are encoded using binary clauses, which can be exploited by current conflict -driven clause learning (CDCL) solvers. In addition, the number of clauses used to encode swap and follow conflicts do not depend on the number of agents, allowing us to scale better. For MaxSAT, we study different ways in which we may combine the MSU3 and LSU algorithms for maximum performance. In our experimental evaluation, we used square grids, ranging from 20 x 20 to 50 x 50 cells, and warehouse maps, with a varying number of agents and obstacles. We compared against representative solvers of the state-of-the-art, including the search-based algorithm CBS, the ASP-based solver ASP-MAPF, and the branch-and-cut-and-price hybrid solver, BCP. We observe that the ASP implementation of our encoding, ASP-MAPF2 outperforms other solvers in most of our experiments. The MaxSAT implementation of our encoding, MtMS shows best performance in relatively small warehouse maps when the number of agents is large, which are the instances with closer resemblance to hard puzzle-like problems.
dc.fuente.origenWOS
dc.identifier.eissn1943-5037
dc.identifier.issn1076-9757
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/92955
dc.identifier.wosidWOS:000865010600004
dc.language.isoen
dc.pagina.final350
dc.pagina.inicio323
dc.revistaJournal of artificial intelligence research
dc.rightsacceso restringido
dc.subject.ods11 Sustainable Cities and Communities
dc.subject.odspa11 Ciudades y comunidades sostenibles
dc.titleMulti-Agent Path Finding: A New Boolean Encoding
dc.typeartículo
dc.volumen75
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas