Browsing by Author "Gómez Araya, Rodrigo Nicolás Teófilo"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
- ItemA Compact Answer Set Programming Encoding of Multi-Agent Pathfinding(IEEE, 2021) Gómez Araya, Rodrigo Nicolás Teófilo; Hernández, Carlos; Baier Aranda, Jorge AndrésMulti-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.
- ItemCompilación en programación de conjuntos de respuestas para el problema de búsqueda de caminos con múltiples agentes(2020) Gómez Araya, Rodrigo Nicolás Teófilo; Baier Aranda, Jorge Andrés; Pontificia Universidad Católica de Chile. Escuela de IngenieríaLa búsqueda de caminos con múltiples agentes (MAPF por sus siglas en inglés) es el problema de encontrar k caminos libres de conflictos que conecten k posiciones iniciales con k posiciones objetivos en un mapa dado. En su variante de suma de costos, se minimiza el número total de acciones realizadas por los agentes. Dado que MAPF es un problema combinatorio, existan distintas compilaciones a Satisfacción Booleana (SAT) y Programación de Conjuntos de Respuestas (ASP). En esta tesis, describimos en detalle la primera familia de compilaciones a ASP que resuelven la variante de suma de costos de MAPF sobre grillas 4-conectadas. En comparación con otras compilaciones existentes de ASP, nuestra compilación se diferencia en que el número de cláusulas totales (después de la instanciación) crece linealmente con el número de agentes, mientras que las compilaciones existentes crecen de forma cuadrática. Además, el objetivo de optimización es tal que su tamaño después de la instanciación no depende del tamaño de la grilla. Nuestra evaluación experimental muestra que nuestro enfoque supera al estado del arte cuando las grillas están congestionadas con agentes. Finalmente, mostramos una variante online de nuestra compilación que permite solucionar problemas de mayor tamaño y número de agentes.