Compilación en programación de conjuntos de respuestas para el problema de búsqueda de caminos con múltiples agentes
Loading...
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
La 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.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2020