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

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

Path planning

Preprocessing based path planning

Grid graphs

Subgoal graphs

Jump point graphs

Contraction hierarchies

658.4012

Administración

Planificación - Modelos matemáticos

Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2022

En 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.

Marín Barrera, Bruno

2022-04-13T21:19:15Z

2022-04-13T21:19:15Z

2022

Baier Aranda, Jorge Andrés

Pontificia Universidad Católica de Chile. Escuela de Ingeniería

acceso abierto

xii, 81 páginas

application/pdf

en

tesis de maestría

10.7764/tesisUC/ING/63666

https://doi.org/10.7764/tesisUC/ING/63666

https://repositorio.uc.cl/handle/11534/63666