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 de la resolución de 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 grafo 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 algunos criterios (más corta, más barata, más rápida, etc.) entre dos puntos en una red grande.
En esencia, un método de búsqueda de rutas busca en un grafo comenzando en un vértice y explorando los 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 grafos, como la búsqueda en amplitud, encontrarían una ruta si se les diera suficiente tiempo, otros métodos, que "exploran" el grafo, tenderían a llegar al destino antes. Una analogía sería la de una persona que camina por 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 un obstáculo y haría las desviaciones lo menos posibles.
Dos problemas principales de la búsqueda de rutas son (1) encontrar una ruta entre dos nodos en un grafo ; y (2) el problema de la ruta más corta : encontrar la ruta más corta óptima . Los algoritmos básicos, como la búsqueda en amplitud y la búsqueda en profundidad, abordan el primer problema agotando todas las posibilidades; comenzando desde el nodo dado, iteran sobre todas las rutas potenciales hasta que llegan al nodo de destino. Estos algoritmos se ejecutan en , 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 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 a través de heurísticas o mediante programación dinámica . Al eliminar caminos imposibles, estos algoritmos pueden lograr complejidades temporales 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 sistemas prácticos de planificación 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 estos algoritmos son las jerarquías de contracción .
Un ejemplo común de un algoritmo de búsqueda de rutas basado en grafos 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 haya encontrado una ruta hacia el destino. Dado que los nodos de menor distancia se examinan primero, la primera vez que se encuentra el destino, la ruta hacia él será la más corta. [3]
El algoritmo de Dijkstra falla si hay un peso de arista negativo . En la situación hipotética donde los nodos A, B y C forman un grafo 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 que comienza desde 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 arista negativos. Sin embargo, dado que para muchos propósitos prácticos nunca habrá un peso de arista negativo, el algoritmo de Dijkstra es en gran medida adecuado para el propósito de búsqueda de rutas.
A* es una variante del algoritmo de Dijkstra con una amplia variedad de casos de uso. 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 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 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, ese nodo no necesita ser examinado. [4]
A* utiliza esta heurística para mejorar el comportamiento en relación con el algoritmo de Dijkstra. Cuando la heurística 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 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 real, ya que a menudo se puede llegar al mismo resultado de comparación utilizando cálculos más simples; por ejemplo, utilizando la distancia de Chebyshev sobre la distancia euclidiana en el espacio bidimensional ). A medida que aumenta el valor de la heurística, 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.
La búsqueda de caminos tiene un historial de ser incluida en videojuegos con objetos en movimiento o NPC. Chris Crawford en 1982 describió cómo "gastó una gran cantidad de tiempo" tratando de resolver un problema con la búsqueda de caminos en Tanktics , en el que los tanques de computadora quedaron atrapados en tierra dentro de lagos con forma de U. "Después de mucho esfuerzo desperdiciado descubrí una mejor solución: eliminar los lagos con forma de U del mapa", dijo. [5]
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 baja cantidad 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 (Abstraction-Based STRIPS ) [6] que se usaba para buscar de manera eficiente los espacios de estado de los juegos de lógica. [7] Una técnica similar son las mallas de navegación (navmesh), que se usan para la planificación geométrica en juegos y la planificación de transporte multimodal que se utiliza en problemas de 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 la ruta entre los grupos. Una vez que se encuentra el plan, se planifica una segunda ruta dentro de un grupo en el nivel inferior. [8] Esto significa que la planificación se realiza en dos pasos, lo 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. [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ía calcular muchos gráficos posibles. La razón es que un mapa de este tipo 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 grupo 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 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 nodos que pueden ser manejados por un planificador de rutas A* normal fácilmente.
La búsqueda de rutas multiagente consiste en encontrar las rutas de múltiples agentes desde sus ubicaciones actuales hasta sus ubicaciones de destino sin colisionar entre sí, mientras que al mismo tiempo se optimiza 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 rutas. 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 produzcan 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 multiagente en estructuras de cuadrícula computacionales, por ejemplo, celdas similares a los autómatas celulares . Una categoría diferente de algoritmos sacrifica la optimalidad por el 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}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite journal}}: CS1 maint: multiple names: authors list (link){{cite journal}}: CS1 maint: multiple names: authors list (link)