Abordamos para terminar esta serie de artículos referentes al Pathfinding,
una solución casi óptima al problema propuesta por el Dr. Daniel Harabor.
En ella se propone hacer una búsqueda de caminos similar a la que hariamos
las personas buscando en primer lugar caminos rápidos para largas distancias
y ajustando la búsqueda una vez nos encontramos cerca del objetivo.
Nuestro problema es, por lo tanto, definir una abstracción donde a un nivel
superior se represente el mapa de una forma rápida y abordable por los algoritmos
de búsqueda. Una vez tenemos esta abstracción utilizar un procedimiento más preciso
para llegar al punto correcto. Dividiremos el mapa en sectores.
La forma en la que nos abstraemos de una forma adecuada será la siguiente:
1. En primer lugar dividimos el mapa anotado en un set de clusters adyacentes conectados por Entradas.Veremos más en detalle como.
2. En segundo lugar compactamos el grafo generado usando algunas técnicas para mejorar el resultado eliminando innecesarios con la finalidad de tener los nodos mínimos.
3. Por último describimos el Algoritmo A* Jerárquico Anotado HAA* (Hierarchical Annotated A*) algorithm (HAA*).
El objetivo de manejar varios terrenos y abstraernos del mapa se ha conseguido pero con
el coste de disponer de mucha información redundante.
> Primer paso. Definir Sectores y entradas
Ahora que hemos visto el procedimiento a realizar a grandes pasos, vamos
por partes. Crearemos los sectores y definiremos las entradas. Esto se puede
hacer de forma jerárquica definiendo varios niveles por ejemplo doblando el
tamaño de los sectores.
-Buscamos los valores del grafo:
En el ejemplo de autor identificamos dos tipos de terreno, tierra (ground) y agua
(water) la capacidad queda marcada como capability y el grado de claridad como clearance.
En función del espacio libre el valor de claridad será mayor.
Vemos los valores a marcar en el algoritmo entre los sectores C1 y C3.
-Identificamos las entradas entre clusters
Una entrada queda definida como un área libre de obstáculos con el máximo
tamaño que existe entre el borde de los clusters. Se representa con un
punto de transición que marca que un agente de tamaño menor o igual puede
pasar al sector concreto. Se marca como una arista de peso 1 y con un tipo
concreto y una claridad concreta. La nueva representación será por tanto
una lista de aristas a modo de grafo donde cada una tendrá las transiciones
de un sector a otro y la claridad y tipo de terreno asociado.
En la foto superior se aprecia que hay gran cantidad de aristas redundantes.
> Segundo paso. Eliminar información redundante.
Este segundo paso pretende compactar la información para reducir el volumen
de datos que se está manejando y hacer por lo tanto que los algoritmos de búsqueda
sean más rápidos a la hora de encontrar una solución.
Para ello vamos a aplicar dos técnicas diferentes propuestas por el autor.
- Dominancia fuerte. Si dos aristas de longitud igual conectan el mismo par
de nodos y los dos son travesables por la mismas unidades solo es necesaria
la de claridad mayor. Esto se llama así porque una de las aristas, la de mayor
claridad, domina a la otra. En la foto inferior de la derecha vemos el resultado.
- Dominancia débil. En este caso se tratará de minimizar el número de transiciones
entre sectores. Para conseguir esto analizaremos cada par de aristas internas del
sectores probando que si eliminamos una de ellas el mapa sigue representando la
misma información. Solo las aristas que son travesables por el mayor número de
agentes son retenidas, el resto se eliminarán. El resultado se aprecia en la foto
superior de la izquierda.
El resultado de aplicar los dos procedimientos es el que vemos en la figura
inferior.
El resultado de aplicar estas técnicas puede suponer de un 3 a un 10% de incremento
en la longitud de los caminos encontrados pero sin embargo disminuye en un 50% de media
el tamaño de la memoria requerida para almacenar los mapas y el desempeño del algoritmo
aumenta considerablemente.
> Tercero. Aplicamos el algoritmo A* Jerárquico Anotado
El proceso de encontrar el camino será directo. Como detalle general
se distinguen dos procesos.
1. Insertamos dos nodos temporales en el grafo abstracto que representen
el inicio y final del camino. Conectamos el grafo con estos dos nodos
buscando un camino desde las dos posiciones a cada transición en el
sector local.
2. Utilimos A* para encontrar el camino más corto en el grafo abstracto
que hemos generado. Al final de la búsqueda eliminamos ambos nodos que
hemos incluido.
Se incluye en el algoritmo los conceptos de tamaño del agente y de capacidad
que expresa las vias que puede recorrer el agente en cuestión.
Este algoritmo nos permite generar de forma rápida caminos para los entornos
que nos propongamos de una forma mediante la que generando una correcta abstracción
del mundo, nos acercamos a la forma en la que los seres humanos planificamos la
búsqueda de caminos, es decir, partiendo de bloques más grandes conectados y afinando
la precisión conforme nos acercamos al destino.
Se ofrece el código fuente completo, agradeciendo el material al Dr. Daniel Harabor:
Leave a Reply