Pathfinding - Pathfinding

Para otros usos, consulte Pathfinder (desambiguación) .
Algoritmos de búsqueda de gráficos y árboles
Listados
Temas relacionados
Rutas equivalentes entre A y B en un entorno 2D

Pathfinding o ruta es el trazado, mediante una aplicación informática, de la ruta más corta entre dos puntos. Es una variante más práctica para resolver laberintos . Este campo de investigación se basa en gran medida en el algoritmo de Dijkstra para encontrar el camino más corto en un gráfico ponderado .

La búsqueda de rutas está estrechamente relacionada con el problema de la ruta más corta , dentro de la teoría de grafos , que examina cómo identificar la ruta que mejor cumple con algunos criterios (más corta, más barata, más rápida, etc.) entre dos puntos en una red grande.

Algoritmos

En esencia, un método de búsqueda de rutas busca en un gráfico comenzando en un vértice y explorando los nodos adyacentes hasta que se alcanza el nodo de destino, generalmente con la intención de encontrar la ruta más barata. Aunque los métodos de búsqueda de gráficos, como la búsqueda en amplitud , encontrarían una ruta si se les diera el tiempo suficiente, otros métodos, que "exploran" el gráfico, tenderían a llegar antes al destino. Una analogía sería una persona que cruza una habitación; en lugar de examinar todas las rutas posibles de antemano, la persona generalmente caminaría en la dirección del destino y solo se desviaría del camino para evitar una obstrucción y hacer las desviaciones lo más pequeñas posible.

Dos problemas principales de la búsqueda de rutas son (1) encontrar una ruta entre dos nodos en un gráfico ; y (2) el problema del camino más corto: encontrar el camino más corto óptimo . Los algoritmos básicos, como la búsqueda en amplitud y en profundidad, abordan el primer problema agotando todas las posibilidades; a partir del nodo dado, recorren todas las rutas potenciales hasta llegar al nodo de destino. Estos algoritmos se ejecutan en tiempo lineal, donde V es el número de vértices y E es el número de aristas entre vértices.

El problema más complicado es encontrar el camino óptimo. El enfoque exhaustivo en este caso se conoce como el algoritmo de Bellman-Ford , que produce una complejidad de tiempo de , o tiempo cuadrático. Sin embargo, no es necesario examinar todos los caminos posibles para encontrar el óptimo. Algoritmos como A * y el algoritmo de Dijkstra eliminan estratégicamente las rutas, ya sea mediante heurística o mediante programación dinámica . Al eliminar rutas imposibles, estos algoritmos pueden lograr complejidades de tiempo tan bajas como .

Los algoritmos anteriores se encuentran entre los mejores algoritmos generales que operan en un gráfico sin preprocesamiento. Sin embargo, en los sistemas prácticos de enrutamiento de viajes, se pueden lograr incluso mejores complejidades de tiempo mediante algoritmos que pueden preprocesar el gráfico para lograr un mejor rendimiento. Uno de esos algoritmos son las jerarquías de contracción .

Algoritmo de Dijkstra

Un ejemplo común de un algoritmo de búsqueda de rutas basado en gráficos es el algoritmo de Dijkstra . Este algoritmo comienza con un nodo de inicio y un "conjunto abierto" de nodos candidatos. En cada paso, se examina el nodo del conjunto abierto con la distancia más baja desde el inicio. El nodo se marca como "cerrado" y todos los nodos adyacentes a él se agregan al conjunto abierto si aún no se han examinado. Este proceso se repite hasta que se encuentra una ruta al destino. Dado que los nodos de menor distancia se examinan primero, la primera vez que se encuentra el destino, el camino hacia él será el más corto.

El algoritmo de Dijkstra falla si hay un peso de borde negativo . En la situación hipotética en la que los nodos A, B y C forman un gráfico no dirigido conectado con aristas AB = 3, AC = 4 y BC = −2, la ruta óptima de A a C cuesta 1 y la ruta óptima de A a B cuesta 2. El algoritmo de Dijkstra a partir de A examinará primero B, ya que es el más cercano. Le asignará un costo de 3 y lo marcará como cerrado, lo que significa que su costo nunca será reevaluado. Por lo tanto, Dijkstra no puede evaluar los pesos de los bordes negativos. Sin embargo, dado que para muchos propósitos prácticos nunca habrá un peso de borde negativo, el algoritmo de Dijkstra es en gran parte adecuado para el propósito de búsqueda de rutas.

Algoritmo A *

A * es una variante del algoritmo de Dijkstra que se usa comúnmente en los juegos. A * asigna un peso a cada nodo abierto igual al peso del borde a ese nodo más la distancia aproximada entre ese nodo y el final. Esta distancia aproximada se encuentra mediante la heurística y representa una distancia mínima posible entre ese nodo y el final. Esto le permite eliminar rutas más largas una vez que se encuentra una ruta inicial. Si hay una ruta de longitud x entre el inicio y el final, y la distancia mínima entre un nodo y el final es mayor que x, no es necesario examinar ese nodo.

A * usa esta heurística para mejorar el comportamiento relativo al algoritmo de Dijkstra. Cuando la heurística se evalúa a cero, A * es equivalente al algoritmo de Dijkstra. A medida que la estimación heurística aumenta y se acerca a la distancia real, A * continúa encontrando rutas óptimas, pero se ejecuta más rápido (en virtud de examinar menos nodos). Cuando el valor de la heurística es exactamente la distancia verdadera, A * examina la menor cantidad de nodos. (Sin embargo, generalmente no es práctico escribir una función heurística que siempre calcule la distancia verdadera, ya que a menudo se puede alcanzar el mismo resultado de comparación usando cálculos más simples, por ejemplo, usando la distancia de Manhattan sobre la distancia euclidiana en un espacio bidimensional ). El valor de la heurística aumenta, A * examina menos nodos pero ya no garantiza una ruta óptima. En muchas aplicaciones (como los videojuegos) esto es aceptable e incluso deseable, para mantener el algoritmo funcionando rápidamente.

Algoritmo de muestra

Este es un algoritmo de búsqueda de rutas bastante simple y fácil de entender para mapas basados ​​en mosaicos. Para empezar, tienes un mapa, una coordenada de inicio y una coordenada de destino. El mapa se verá así, Xsiendo paredes, Ssiendo el inicio, Osiendo el final y _siendo espacios abiertos, los números a lo largo de los bordes superior y derecho son los números de columna y fila: 

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X

Primero, cree una lista de coordenadas, que usaremos como cola. La cola se inicializará con una coordenada, la coordenada final. Cada coordenada también tendrá una variable de contador adjunta (el propósito de esto pronto se hará evidente). Por lo tanto, la cola comienza como ((3,8,0)).

Luego, revise todos los elementos de la cola, incluidos los elementos nuevos agregados al final durante el transcurso del algoritmo, y para cada elemento, haga lo siguiente:

  1. Cree una lista de las cuatro celdas adyacentes, con una variable de contador de la variable de contador del elemento actual + 1 (en nuestro ejemplo, las cuatro celdas son ((2,8,1), (3,7,1), (4, 8,1), (3,9,1)))
  2. Verifique todas las celdas en cada lista para las siguientes dos condiciones:
    1. Si la celda es una pared, elimínela de la lista
    2. Si hay un elemento en la lista principal con la misma coordenada, elimínelo de la lista de celdas
  3. Agregue todas las celdas restantes de la lista al final de la lista principal
  4. Ir al siguiente elemento de la lista

Así, después del turno 1, la lista de elementos es la siguiente: ((3,8,0), (2,8,1), (4,8,1))

  • Después de 2 turnos: ((3,8,0), (2,8,1), (4,8,1), (1,8,2), (4,7,2))
  • Después de 3 turnos: (... (1,7,3), (4,6,3), (5,7,3))
  • Después de 4 turnos: (... (1,6,4), (3,6,4), (6,7,4))
  • Después de 5 turnos: (... (1,5,5), (3,5,5), (6,6,5), (6,8,5))
  • Después de 6 turnos: (... (1,4,6), (2,5,6), (3,4,6), (6,5,6), (7,8,6))
  • Después de 7 turnos: (... (1,3,7)) - problema resuelto, finalice esta etapa del algoritmo - tenga en cuenta que si tiene varias unidades persiguiendo el mismo objetivo (como en muchos juegos - el enfoque de meta a comienzo de el algoritmo tiene la intención de hacer esto más fácil), puede continuar hasta que se tome todo el mapa, se alcancen todas las unidades o se alcance un límite de contador establecido

Ahora, mapee los contadores en el mapa, obteniendo esto: 

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X 6 X 6 _ X _ _ _ X 4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X

Ahora, comience en S (7) y vaya a la celda cercana con el número más bajo (las celdas no marcadas no se pueden mover). La ruta trazada es (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> ( 1,8,2) -> (2,8,1) -> (3,8,0). En el caso de que dos números sean igualmente bajos (por ejemplo, si S estaba en (2,5)), elija una dirección aleatoria; las longitudes son las mismas. El algoritmo ahora está completo.

En videojuegos

Chris Crawford en 1982 describió cómo "dedicó una gran cantidad de tiempo" a tratar de resolver un problema con la búsqueda de caminos en Tanktics , en el que tanques de computadoras quedaron atrapados en tierra dentro de lagos en forma de U. "Después de mucho esfuerzo desperdiciado, descubrí una mejor solución: eliminar los lagos en forma de U del mapa", dijo.

Búsqueda de ruta jerárquica

Quadtrees se pueden utilizar para encontrar rutas jerárquicas

La idea fue descrita por primera vez por la industria de los videojuegos , que tenía la necesidad de planificar en mapas grandes con una cantidad baja de tiempo de CPU . El concepto de usar abstracción y heurística es más antiguo y se mencionó por primera vez con el nombre ABSTRIPS (abstracción-based STRIPS ) que se usó para buscar de manera eficiente los espacios de estado de los juegos de lógica. Una técnica similar son las mallas de navegación (navmesh), que se utilizan para la planificación geométrica en los juegos y la planificación del transporte multimodal que se utiliza en los problemas de los vendedores ambulantes con más de un vehículo de transporte.

Un mapa se divide en grupos . En la capa de alto nivel, se planifica el camino entre los clústeres. Una vez encontrado el plan, se planifica una segunda ruta dentro de un grupo en el nivel inferior. Es decir, la planificación se realiza en dos pasos, que es una búsqueda local guiada en el espacio original. La ventaja es que el número de nodos es menor y el algoritmo funciona muy bien. La desventaja es que un planificador de rutas jerárquico es difícil de implementar.

Ejemplo

Un mapa tiene un tamaño de 3000x2000 píxeles . La planificación de una ruta en una base de píxeles llevaría mucho tiempo. Incluso un algoritmo eficiente necesitará calcular muchos gráficos posibles. La razón es que dicho mapa contendría 6 millones de píxeles en total y las posibilidades de explorar el espacio geométrico son excesivamente grandes. El primer paso para un planificador de rutas jerárquicas es dividir el mapa en submapas más pequeños. Cada grupo tiene un tamaño de 300x200 píxeles. El número total de clústeres es 10x10 = 100. En el gráfico recién creado, la cantidad de nodos es pequeña, es posible navegar entre los 100 grupos, pero no dentro del mapa detallado. Si se encontró una ruta válida en el gráfico de alto nivel, el siguiente paso es planificar la ruta dentro de cada grupo. El submapa tiene 300x200 píxeles que un planificador de rutas A * normal puede manejar fácilmente.

Algoritmos utilizados en la búsqueda de rutas

Pathfinding de múltiples agentes

La búsqueda de rutas de múltiples agentes consiste en encontrar las rutas para múltiples agentes desde sus ubicaciones actuales hasta sus ubicaciones objetivo sin chocar entre sí, mientras que al mismo tiempo se optimiza una función de costo, como la suma de las longitudes de ruta de todos los agentes. Es una generalización de la búsqueda de caminos. Muchos algoritmos de búsqueda de rutas de múltiples agentes se generalizan a partir de A *, o se basan en la reducción a otros problemas bien estudiados, como la programación lineal de enteros. Sin embargo, estos algoritmos suelen estar incompletos; en otras palabras, no se ha demostrado que produzca una solución dentro del tiempo polinomial. Una categoría diferente de algoritmos sacrifica la optimización del rendimiento al hacer uso de patrones de navegación conocidos (como el flujo de tráfico) o la topología del espacio problemático.

Ver también

Referencias

enlaces externos