Exploiting direction in grid graphs to build a fast and lighter subgoal graph

Simple item page
dc.contributor.advisorBaier Aranda, Jorge Andrés
dc.contributor.authorMarín Barrera, Bruno
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2022-04-13T21:19:15Z
dc.date.available2022-04-13T21:19:15Z
dc.date.issued2022
dc.descriptionTesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2022
dc.description.abstractEn el problema de path planning sobre grafos tipo grilla, una de las principales técnicas de preprocesamiento del estado del arte son los subgoal graphs. Estos grafos consisten en un subconjunto de nodos importantes denominados subgoals que son conectados mediante una relación de alcanzabilidad. Al momento de resolver un problema se conecta el nodo origen y el nodo destino al subgoal graph, se realiza una búsqueda en el grafo y se refina el camino obtenido en un camino en el grafo original. En esta tesis, presentamos Directed Subgoal Graphs (DSG), un nuevo subgoal graph que se construye sobre una grilla aumentada con la dirección de incidencia para eliminar caminos que no sean óptimos. La relación de alcanzabilidad asegura que todos los caminos óptimos y el comienzo de algún camino diagonal-first entre dos subgoals sean válidos. En DSG la conexión entre subgoals se realiza en un orden cardinal-first. El proceso de conexión muestra ser el más rápido respecto al de todos los otros subgoal graphs, al mismo tiempo que necesita la mínima cantidad de memoria para esta etapa. Cuando DSG es potenciado con Contraction Hierarchies (CH), mejora el rendimiento del estado del arte en varias instancias del grupo de benchmarks MovingAI. En mapas tipo juegos, nuestro algoritmo es hasta 3.0% mas rápido que el mejor de los otros subgoal graphs utilizando un 47% menos memoria. Gran parte de los beneficios se obtienen mayoritariamente en mapas grandes cuyo espacio transitable permite movimientos diagonales amplios donde también hay una gran cantidad de islas de obstáculos. Cuando esto sucede, DSG es hasta un 27% mas rápido. Además, entregamos mejoras para el conjunto de subgoal graphs, que incluye la extensión de la evitabilidad de subgoals poco importantes y una nueva técnica para reducir atajos redundantes generados por CH.
dc.format.extentxii, 81 páginas
dc.fuente.origenSRIA
dc.identifier.doi10.7764/tesisUC/ING/63666
dc.identifier.urihttps://doi.org/10.7764/tesisUC/ING/63666
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/63666
dc.information.autorucEscuela de Ingeniería ; Baier Aranda, Jorge Andrés ; 0000-0002-6280-5619 ; 9477
dc.information.autorucEscuela de Ingeniería ; Marín Barrera, Bruno ; S/I ; 232745
dc.language.isoen
dc.nota.accesoContenido completo
dc.rightsacceso abierto
dc.subjectPath planninges_ES
dc.subjectPreprocessing based path planninges_ES
dc.subjectGrid graphses_ES
dc.subjectSubgoal graphses_ES
dc.subjectJump point graphses_ES
dc.subjectContraction hierarchieses_ES
dc.subject.ddc658.4012
dc.subject.deweyAdministraciónes_ES
dc.subject.otherPlanificación - Modelos matemáticoses_ES
dc.titleExploiting direction in grid graphs to build a fast and lighter subgoal graphes_ES
dc.typetesis de maestría
sipa.codpersvinculados9477
sipa.codpersvinculados232745
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TESIS_BMarín_Firma Final.pdf
Size:
983.06 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.98 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
3.01 Tesis magíster