Exploiting direction in grid graphs to build a fast and lighter subgoal graph
Loading...
Date
2022
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2022
Keywords
Path planning, Preprocessing based path planning, Grid graphs, Subgoal graphs, Jump point graphs, Contraction hierarchies