Pathfinding o pathing es la búsqueda, 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 .
Pathfinding está estrechamente relacionado con el problema del camino más corto , dentro de la teoría de grafos , que examina cómo identificar el camino que mejor cumple con algunos criterios (el más corto, el más barato, el más rápido, etc.) entre dos puntos de una gran red.
En esencia, un método de búsqueda de rutas busca en un gráfico comenzando en un vértice y explorando nodos adyacentes hasta llegar al 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 suficiente tiempo, otros métodos, que "exploran" el gráfico, tenderían a llegar al destino antes. Una analogía sería una persona caminando por una habitación; en lugar de examinar todas las rutas posibles de antemano, la persona generalmente camina en la dirección del destino y sólo se desvía del camino para evitar una obstrucción, y hace 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; comenzando desde el nodo dado, itera sobre todas las rutas potenciales hasta llegar al nodo de destino. Estos algoritmos se ejecutan en tiempo lineal, o 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 algoritmo de Bellman-Ford , que produce una complejidad temporal 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 caminos estratégicamente, ya sea mediante heurística o mediante programación dinámica . Al eliminar caminos imposibles, estos algoritmos pueden lograr complejidades de tiempo tan bajas como . [1]
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 rutas de viaje, se pueden lograr complejidades temporales aún mejores mediante algoritmos que pueden preprocesar el gráfico para lograr un mejor rendimiento. [2] Uno de esos algoritmos son las jerarquías de contracción .
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 inicial 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 un camino hacia el destino. Dado que los nodos de menor distancia se examinan primero, la primera vez que se encuentre el destino, el camino hacia él será el más corto. [3]
El algoritmo de Dijkstra falla si hay un peso de borde negativo . En la situación hipotética donde los nodos A, B y C forman un gráfico no dirigido conectado con aristas AB = 3, AC = 4 y BC = −2, el camino óptimo de A a C cuesta 1, y el camino óptimo de A a C 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 pesos de borde 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 medida adecuado para el propósito de encontrar rutas.
A* es una variante del algoritmo de Dijkstra comúnmente utilizado en juegos. A* asigna un peso a cada nodo abierto igual al peso del borde de ese nodo más la distancia aproximada entre ese nodo y el acabado. Esta distancia aproximada se encuentra mediante la heurística y representa la distancia mínima posible entre ese nodo y el final. Esto le permite eliminar caminos más largos una vez que se encuentra un camino inicial. Si hay un camino 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. [4]
A* utiliza esta heurística para mejorar el comportamiento relativo al algoritmo de Dijkstra. Cuando la heurística se evalúa como 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 caminos óptimos, pero corre más rápido (al examinar menos nodos). Cuando el valor de la heurística es exactamente la distancia real, 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 llegar al mismo resultado de comparación usando cálculos más simples, por ejemplo, usando la distancia de Chebyshev sobre la distancia euclidiana en un espacio bidimensional ). Cuando 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.
Chris Crawford en 1982 describió cómo "pasó una gran cantidad de tiempo" tratando de resolver un problema de búsqueda de caminos en Tanktics , en el que los tanques de computadora quedaban atrapados en tierra dentro de lagos en forma de U. "Después de mucho esfuerzo inútil, descubrí una solución mejor: eliminar los lagos en forma de U del mapa", dijo. [5]
La idea fue descrita por primera vez por la industria de los videojuegos , que necesitaba planificar mapas grandes con una cantidad baja de tiempo de CPU . El concepto de uso de abstracción y heurística es más antiguo y se mencionó por primera vez con el nombre ABSTRIPS (Abstraction-Based STRIPS ) [6] , que se utilizó para buscar eficientemente los espacios de estado de los juegos de lógica. [7] Una técnica similar son las mallas de navegación (navmesh), que se utilizan para la planificación geométrica en juegos y la planificación del transporte multimodal que se utiliza en problemas de viajantes de comercio con más de un vehículo de transporte.
Un mapa se separa en grupos . En la capa de alto nivel, se planifica el camino entre los grupos. Una vez encontrado el plano, se planifica un segundo camino dentro de un grupo en el nivel inferior. [8] 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 ruta jerárquico es difícil de implementar. [9]
Un mapa tiene un tamaño de 3000x2000 nodos. Planificar una ruta sobre una base de nodos llevaría mucho tiempo. Incluso un algoritmo eficiente necesitará calcular muchos gráficos posibles. La razón es que un mapa así contendría 6 millones de nodos en total y las posibilidades de explorar el espacio geométrico son extremadamente grandes. El primer paso para un planificador de rutas jerárquico es dividir el mapa en submapas más pequeños. Cada clúster tiene un tamaño de 300x200 nodos. El número total de grupos es 10x10=100. En el gráfico recién creado la cantidad de nodos es pequeña, es posible navegar entre los 100 clusters, 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 nodos de 300x200 que pueden ser manejados fácilmente por un planificador de ruta A* normal .
La búsqueda de rutas de múltiples agentes consiste en encontrar rutas para múltiples agentes desde sus ubicaciones actuales hasta sus ubicaciones de destino sin chocar entre sí, y al mismo tiempo optimizar una función de costo, como la suma de las longitudes de las rutas de todos los agentes. Es una generalización de la búsqueda de caminos. Muchos algoritmos de búsqueda de rutas multiagente se generalizan a partir de A* o se basan en la reducción a otros problemas bien estudiados, como la programación lineal entera. [10] Sin embargo, estos algoritmos suelen ser incompletos; en otras palabras, no se ha demostrado que produzca una solución en un tiempo polinomial. Algunos enfoques paralelos, como la Difusión Colaborativa , se basan en algoritmos vergonzosamente paralelos que difunden la búsqueda de rutas de múltiples agentes en estructuras de cuadrícula computacional, por ejemplo, células similares a autómatas celulares . Una categoría diferente de algoritmos sacrifica la optimización en aras del rendimiento al hacer uso de patrones de navegación conocidos (como el flujo de tráfico) o la topología del espacio del problema. [11]
{{cite conference}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: CS1 maint: multiple names: authors list (link){{cite journal}}: CS1 maint: multiple names: authors list (link)