Dublin Core
Title
Compilación en programación de conjuntos de respuestas para el problema de búsqueda de caminos con múltiples agentes
Subject
005.115
Ciencias de la computación
Programación heurística
Programación lógica
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2020
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.
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.
Creator
Gómez Araya, Rodrigo Nicolás Teófilo
Date
2021-03-15T14:17:58Z
2021-03-15T14:17:58Z
2020
Contributor
Baier Aranda, Jorge Andrés
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
xiii, 88 páginas
application/pdf
Language
es
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/52726
https://doi.org/10.7764/tesisUC/ING/52726
https://repositorio.uc.cl/handle/11534/52726