Búsqueda de caminos

Búsqueda de caminos Concepto: Es la forma en que una entidad en movimiento encuentra un camino alrededor de un obstáculo.

Búsqueda de caminos. Los algoritmos de búsqueda de caminos son usados para encontrar una ruta de navegación entre un punto de inicio y otro objetivo. Esta ruta es generalmente un pequeño subconjunto del mundo.

Breve reseña histórica

Con el gran avance que ha tenido el conocimiento del hombre a través del devenir de los años hay momentos que marcan pautas en el desarrollo de la Inteligencia Artificial, fue en la década del 50 donde se utilizó este término y logró captar la atención de muchos para su posterior evolución. La Inteligencia Artificial atiende una rama muy importante y ésta es la búsqueda de caminos. Las raíces de los algoritmos de búsqueda de caminos hay que asociarlos a la constante evolución de los videojuegos ya que es una de las aplicaciones prácticas más interesantes en este entorno, son algoritmos por los cuales nuestro objetivo es capaz de eludir los obstáculos y llegar de un punto A a un punto B. Es a partir de 1959 donde se empieza a buscar variantes para la problemática de la búsqueda de caminos en video-juegos, este proceso ha sido verdaderamente evolutivo ya que se comenzó con algoritmos como Dijkstra, también llamado algoritmo de caminos mínimos luego siguió el algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) éste fue introducido por primera vez en el año 1977 cuando Slate y Atkin presentaron un programa de ajedrez. Con la constante optimización de los algoritmos de búsqueda aparece el algoritmo de búsqueda de caminos A*, éste fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística. En Cuba comienza a lograrse un avance en este sentido, los video-juegos y simuladores son un campo reciente y por tanto, conllevan una simulación inteligente mucho más real y necesitan algoritmos más fuertes y de un nivel superior.

En entornos virtuales

Una de las problemáticas más vistas en el mundo de los juegos es cómo encontrar el camino mínimo entre dos puntos, este estudio ha comenzado desde los métodos de búsqueda heurística tradicionales que en la mayoría de los casos son incapaces de resolver problemas donde el agente tiene un tiempo limitado para calcular una solución en un entorno inicialmente desconocido hasta los métodos de búsqueda heurística en tiempo real. Existen algoritmos capaces de solucionar el problema de búsqueda de caminos de manera eficiente, mediante algoritmos de búsqueda heurística en tiempo real. Se presentan varios algoritmos que mejoran el rendimiento de las aproximaciones existentes. Estos se evalúan considerando varias medidas de desempeño, las más importantes son: el coste de la solución, el tiempo total de búsqueda y el tiempo por etapa de planificación

Aplicaciones de los algoritmos de búsqueda

La investigación de algoritmos tanto exactos como heurísticos para resolver problemas de optimización tiene una vigencia inusualmente importante en estos días, de esta forma, actualmente es acuciante la necesidad de algoritmos muy eficientes que puedan dar respuesta en tiempo real a problemas del usuario o del sistema, y que permitan trabajar con los nuevos sistemas operativos y máquinas. En el mundo de los video-juegos existen muchas aplicaciones para los algoritmos de búsqueda de caminos. Como todos sabemos una de las formas más comunes en las que se aplican estos algoritmos es en los juegos de estrategia y de rol, donde les decimos a las tropas donde deben moverse y ellas se las apañan para alcanzar ese punto a través del terreno. Pero también cuando el ordenador necesita mover un enemigo de un punto a otro del escenario necesitará de uno de estos algoritmos. Los algoritmos de búsqueda de caminos tienen otras tantas aplicaciones muy útiles para el mundo actual, por ejemplo, algo que tiene mucho éxito en nuestros días son los GPS que poseen los carros de alta tecnología de hoy en día que se utilizan para ayudar al conductor a hallar caminos y sugerir los atajos o caminos más cortos. Esto resulta ser de gran utilidad para el turista que se encuentre en una cuidad desconocida para él. En el mundo de la medicina también existen aplicaciones para estos algoritmos, los grandes programas hechos para realizar cirugías a pacientes están pensados para hallar el camino más corto y seguro considerando todos los factores como flujos sanguíneos, obstáculos y otros, para llegar a algún lugar decidido previamente por el cirujano dada una entrada. Parte importante de esta técnica está en la definición de la distancia heurística que debe recorrer.

Conceptos para entender la búsqueda en árboles y grafos

Para entender a cabalidad todo lo relacionado con los algoritmos de búsqueda es necesario conocer algunos conceptos que le serán de gran ayuda, por ejemplo, en problemas de este tipo se utiliza mucho el término búsqueda. Las estrategias de búsqueda son criterios que determinan cual es el próximo estado a expandir.

¿Qué es búsqueda?

Método computacional para resolver problemas, cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de Pathfinding de un único agente. En la realidad existen tres tipos de búsquedas: la búsqueda a ciegas, la búsqueda heurística y la búsqueda heurística en tiempo real.

Estructuras de datos para la búsqueda de camino

En los algoritmos de búsqueda de caminos las estructuras de datos más adecuadas para representar el espacio de búsqueda son los grafos y los árboles.

Clasificación de algoritmos

Según la búsqueda los algoritmos se pueden clasificar en dos clases:

Los métodos off-line

Este método sigue el siguiente esquema, primero calculan el plan o ruta de mínimo coste de un problema mediante la búsqueda en el espacio de estados y luego ejecutan el plan realizando las acciones o secuencia de operaciones en el entorno. Este esquema, a menudo considerado de forma implícita, supone que ejecutar la solución en el mundo real es un proceso directo y no presenta ninguna dificultad, o sea, primero se realiza una búsqueda completa en el espacio de estados y luego se ejecuta una secuencia de acciones u operaciones en el entorno. En la siguiente figura se muestra su funcionamiento. Un ejemplo típico de aplicación de los métodos off-line es la búsqueda de rutas. La búsqueda de rutas consiste en encontrar una ruta en un grafo desde el nodo inicial hasta el nodo objetivo.

Los métodos on-line

En cambio, los métodos on-line intercalan planificación (mediante búsqueda local) y ejecución del plan mientras resuelven un problema. Debido a la propiedad on-line, los métodos tienen una gran flexibilidad para operar en entornos desconocidos y dinámicos. Además, no requieren conocer a-priori todo el espacio de estados, pueden adaptarse a objetos cambiantes y operar en entornos no determinados. Este modo de operación denominado on-line da lugar a los algoritmos de búsqueda en tiempo real. En la siguiente figura se representa el modo de operar de la búsqueda on-line.

Criterios para evaluar las estrategias de búsqueda

Cada algoritmo de búsqueda de caminos tiene una serie de características que lo identifican los cuales son:

• Completitud.
• Complejidad en tiempo.
• Complejidad en espacio.
• Optimización.

Análisis de algoritmos

Depth-First o búsqueda en profundidad (LIFO)

Esta búsqueda se centra en expandir un único camino desde la raíz. Siempre se expande el nodo más profundo en la frontera actual. En el caso de llegar a un “callejón sin salida” se retrocede hasta el nodo más cercano (siguiendo al nodo padre) donde se puede tomar una rama alternativa para poder seguir avanzando. Se puede implementar, mediante el Algoritmo General, considerando la lista, como una pila (cuyas operaciones funcionan en forma LIFO). De esta manera el siguiente nodo a expandir siempre será el último que se haya colocado en la pila de ese nivel, garantizando esto que la expansión vaya aumentando en la profundidad de los nodos. Es común aplicar esta estrategia mediante un algoritmo recursivo que recorra el árbol en Pre-Orden. Tiene modestos requisitos de memoria. Sólo necesita almacenar un camino, junto con los hermanos restantes no expandidos en cada nodo. De aquí surge otro importante algoritmo, “el backtracking”

Breadth-First search (búsqueda a lo ancho)

La búsqueda en anchura (BFS o Breadth-First search) es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol. Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución. El algoritmo no usa ninguna estrategia heurística. Este algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente, este algoritmo tiene como ventaja que, al expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles. Su principal desventaja es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables y que además requiere de mucha memoria. Básicamente tiene que guardar la parte completa de la red que está explorando. También el tiempo es un factor importante. Fundamentalmente problemas de búsqueda de complejidad exponencial no se pueden resolver, salvo para sus instancias más pequeñas. La forma de implementarlo es poner los sucesores de cada nodo al final de una cola o agenda, por lo que OPEN (lista de nodos por explorar) se implementa como un stack.

Búsqueda bidireccional

En la búsqueda bidireccional se llevan a la vez dos búsquedas, una descendente desde el nodo inicial y otra ascendente desde el nodo meta. Al menos una de estas dos búsquedas, debe ser en anchura para que los recorridos ascendente y descendente puedan encontrarse en algún momento. (Tener en cuenta que si tanto el recorrido descendente como el ascendente fueran en profundidad, podría pasar que nunca se cruzaran o encontraran, con lo cual no tendría sentido realizar la búsqueda bidireccional). Por lo demás este método no tiene ninguna dificultad, naturalmente, se podría realizar una búsqueda descendente del nodo meta en anchura y una búsqueda ascendente del nodo inicial en profundidad, alternando la expansión de los nodos entre un tipo de búsqueda y el otro. Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba. El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.

Búsqueda de profundidad limitada

Para evitar caer en caminos de profundidad muy grande, a la mayoría de los algoritmos que usan depth-first se les impone un límite de profundidad máxima. Por tanto es similar a la estrategia de Primero en Profundidad, pero se trata de eliminar el problema de que se puedan generar árboles “ilimitados”. Para ello se establece un límite L a la profundidad del árbol. Todo nodo cuya profundidad sea L, no es expandido (se considera sin sucesores). El problema que puede pasar es si escogemos un valor de L menor que la profundidad del objetivo, en cuyo caso no llegaríamos a la solución. Si se sabe la profundidad de alguna meta, el algoritmo puede ser completo, pero sigue sin ser óptimo.

Algoritmo DFID (primero en profundidad con profundidad iterativa)

El algoritmo de búsqueda DFID (Depth-First Iterative-Deepening) fue introducido por primera vez cuando Slate y Atkin presentaron un programa de ajedrez. El algoritmo combina la estrategia de Primero en Profundidad con la de Profundidad Limitada, comenzando con límite igual a 0, aumentándolo de 1 en 1 hasta encontrar el objetivo. Combina las ventajas de las dos estrategias Para asegurar el completamiento del algoritmo, el DFID introduce un límite de profundidad en cada una de sus iteraciones. El desarrollo del algoritmo es el siguiente: En cada iteración el algoritmo realiza una búsqueda limitada en profundidad. Si en dicha iteración no se alcanza la solución óptima, entonces se incrementa dicho límite en una unidad de profundidad y se vuelve a realizar la búsqueda

Backtracking simple (Vuelta atrás) = Fuerza bruta

Backtracking es una versión de Depth-First. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en los años 1950s. Es un método de búsqueda en profundidad que termina encontrando la primera solución sin embargo garantiza encontrar la solución de mínimo coste (óptima), el problema es el tiempo que toma en hacerlo. Su gran desventaja es el no poder incluir información para evaluar cual de los sucesores es el mejor. A veces los algoritmos de tipo backtracking se usan para encontrar una solución, pero otras veces interesa que las revisen todas (por ejemplo, para encontrar la más corta) .Este método no utiliza información heurística para elegir el sucesor a expandir aunque existe una variante llamada Backtracking Ordenado que sí utiliza información heurística. Es un método sistemático que itera a través de todas las combinaciones posibles del espacio de búsqueda. Es una técnica general que debe ser adaptada para cada aplicación particular. El algoritmo backtracking se aplica en la implementación de los lenguajes de programación, tales como, lenguaje de programación Planner y Prolog. Además, se usa en los análisis sintácticos de los compiladores.

Búsqueda en profundidad Branch and Bound (Ramificación y Límite)

Este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Este método imagina el espacio de búsqueda como un árbol de decisión, en cada paso del algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos prometedoras. Branch and Bound procede de la forma siguiente: se establece una cota inferior a la posible solución (o superior, si se trata de minimizar), se va siguiendo una rama del árbol, hasta que se encuentra que la solución parcial es menor que esa cota, en ese caso, se descarta la rama completa. Además de ramificar una solución padre (branch) en hijos, se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound), o sea, utiliza la poda para eliminar las ramas del árbol que no conducen a una solución óptima. La forma de acotar es un arte que depende de cada problema. La acotación reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los subárboles de descendientes costosos. Puede seguir un recorrido en anchura (estrategia FIFO), profundidad (estrategia LIFO) o cálculo de funciones de coste para seleccionar el nodo más prometedor. Es un algoritmo muy dependiente de la función heurística. En este algoritmo se manejan términos cómo:

• Nodos vivos, que no es más que un nodo factible y prometedor del que no se han generado todos sus hijos.
• Nodo muerto, es aquel del que no se generan más hijos porque ya se han generado todos sus hijos o no es factible ni prometedor.
• Nodo en expansión, es aquel del que se están generando todos sus hijos en ese instante.

El método funciona de la siguiente forma:

• Se selecciona un nodo del conjunto de nodos vivos.
• Se construyen los posibles nodos hijos del nodo seleccionado anteriormente
• Se eliminan algunos de los nodos creados anteriormente reduciendo así el espacio de búsqueda.

El método finaliza cuando se encuentra la solución o cuando se terminan los nodos vivos.

Algoritmo de Dijkstra

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959. Este algoritmo permite computar el camino de costo mínimo de un nodo dado al resto de los nodos de un grafo. El algoritmo de Dijkstra utiliza una técnica de diseño de algoritmos conocida como greedy (también llamados algoritmos ávidos). Su correcto funcionamiento requiere que los costos asociados a los arcos sean no negativos. La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, cuando se obtiene el camino más corto desde el vértice origen al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

El algoritmo de búsqueda A*

Se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, A* es un algoritmo de búsqueda heurística y es óptimo siempre y cuando no se sobreestime la heurística. Este es un algoritmo de búsqueda de caminos para encontrar el camino más corto entre dos nodos, mientras intenta evitar obstáculos. El algoritmo A* además de encontrar el nodo objetivo, nos asegura que es el camino más corto. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor f(n) de cada nodo), y cerrados, donde se guarda la información de los nodos que ya han sido visitados. En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la función f(n) de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados. El ciclo en el algoritmo A* consiste en:

• Buscar el nodo más prometedor.
• Analizar a sus nodos adyacentes.
• Poner el nodo analizado en la lista de cerrados.

El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad, mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia el camino en la búsqueda cada vez que existen nodos más prometedores.

Fuente

• Fernández, M. O. (2003). "Algoritmos de búsqueda heurística en tiempo real. Aplicación a la navegación en los vídeos juegos"