Compilación en programación de conjuntos de respuestas para el problema de búsqueda de caminos con múltiples agentes
| dc.contributor.advisor | Baier Aranda, Jorge Andrés | |
| dc.contributor.author | Gómez Araya, Rodrigo Nicolás Teófilo | |
| dc.contributor.other | Pontificia Universidad Católica de Chile. Escuela de Ingeniería | |
| dc.date.accessioned | 2021-03-15T14:17:58Z | |
| dc.date.available | 2021-03-15T14:17:58Z | |
| dc.date.issued | 2020 | |
| dc.description | Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2020 | |
| dc.description.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. | |
| dc.format.extent | xiii, 88 páginas | |
| dc.identifier.doi | 10.7764/tesisUC/ING/52726 | |
| dc.identifier.uri | https://doi.org/10.7764/tesisUC/ING/52726 | |
| dc.identifier.uri | https://repositorio.uc.cl/handle/11534/52726 | |
| dc.language.iso | es | |
| dc.nota.acceso | Contenido completo | |
| dc.rights | acceso abierto | |
| dc.subject.ddc | 005.115 | |
| dc.subject.dewey | Ciencias de la computación | es_ES |
| dc.subject.other | Programación heurística | es_ES |
| dc.subject.other | Programación lógica | es_ES |
| dc.title | Compilación en programación de conjuntos de respuestas para el problema de búsqueda de caminos con múltiples agentes | es_ES |
| dc.type | tesis de maestría | |
| sipa.codpersvinculados | 9477 | |
| sipa.codpersvinculados | 203748 |