A Compact Answer Set Programming Encoding of Multi-Agent Pathfinding

Simple item page
dc.contributor.authorGómez Araya, Rodrigo Nicolás Teófilo
dc.contributor.authorHernández, Carlos
dc.contributor.authorBaier Aranda, Jorge Andrés
dc.date.accessioned2022-05-18T14:04:51Z
dc.date.available2022-05-18T14:04:51Z
dc.date.issued2021
dc.description.abstractMulti-agent pathfinding (MAPF) is the problem of finding k non-colliding paths connecting k given initial positions with k given goal positions on a given map. In its sum-of-costs variant, the total number of moves and wait actions performed by agents before they definitely reach the goal is minimized. Not surprisingly, since MAPF is combinatorial, a number of compilations to Boolean Satisfiability (SAT) and Answer Set Programming (ASP) exist. In this article, we describe in detail the first family of compilations to ASP that solve sum-of-costs MAPF over 4-connected grids. Compared to existing ASP compilations, a distinguishing feature of our compilation is that the number of total clauses (after grounding) grow linearly with the number of agents, while existing compilations grow quadratically. In addition, the optimization objective is 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-based sum-of-costs MAPF solvers when grids are congested with agents. We also show that our approach is competitive with a SAT-based approach when follow conflicts are taken into account. We also explore the potential of our solver when finding makespanoptimal solutions, in which makespan is minimized first and then cost is minimized. Our results show that makespan-optimal solutions are slightly suboptimal in most benchmarks. Moreover, our MAPF solver, when run in that mode, is faster and scales better.
dc.fechaingreso.objetodigital2024-04-17
dc.fuente.origenIEEE
dc.identifier.doi10.1109/ACCESS.2021.3053547
dc.identifier.eissn2169-3536
dc.identifier.urihttps://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9333548
dc.identifier.urihttps://doi.org/10.1109/ACCESS.2021.3053547
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/64120
dc.information.autorucEscuela de ingeniería ; Gómez Araya, Rodrigo Nicolás Teófilo ; S/I ; 203748
dc.information.autorucEscuela de ingeniería ; Baier Aranda, Jorge Andrés ; S/I ; 9477
dc.language.isoen
dc.nota.accesoContenido completo
dc.pagina.final26901
dc.pagina.inicio26886
dc.publisherIEEE
dc.revistaIEEE Access
dc.rightsacceso abierto
dc.subjectProgramming
dc.subjectEncoding
dc.subjectOptimization
dc.subjectGrounding
dc.subjectStandards
dc.subjectRobots
dc.subjectLicenses
dc.titleA Compact Answer Set Programming Encoding of Multi-Agent Pathfinding
dc.typeartículo
dc.volumen9
sipa.codpersvinculados203748
sipa.codpersvinculados9477
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
A_Compact_Answer_Set_Programming_Encoding_of_Multi-Agent_Pathfinding.pdf
Size:
1.96 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas