El Algoritmo A* y sus límites

 La Inteligencia Artificial es una herramienta de gran utilidad para la resolución de múltiples y variados tipos de problemas. Uno de los ejemplos más mediáticos fue el que hace décadas protagonizó un ordenador de IBM para ganar al campeón del mundo Kasparov jugando al ajedrez. Pero técnicas de IA pueden también conseguir que robots desarrollen trabajos que hasta ahora sólo hacían humanos. O pueden realizar diagnósticos médicos a partir de imágenes. Otro de los campos de aplicación es el de la investigación científica, donde son necesarias grandes cantidades de cálculos que el cerebro humano no puede realizar de forma eficiente. La IA también es muy útil para el reconocimiento facial en ámbitos como el de la delincuencia o la seguridad. Y en el ámbito de lo cotidiano quién no utiliza aplicaciones como Maps para determinar el trayecto más corto para llegar a un destino.

No obstante, aunque todos ellos formen parte de la familia de problemas de Inteligencia Artificial cada uno de ellos es abordado de diferente forma, utilizando algoritmos y tecnologías muy diferentes.

Vayamos al último ejemplo que ponía, el problema de la búsqueda del camino geográfico más corto entre dos puntos. Esta casuística se puede resolver mediante tecnología basada en el Algoritmo A*. Pero, ¿ funciona este algoritmo para todos los problemas de IA ? Pues no, este algoritmo funciona únicamente para esta casuística concreta de búsqueda de caminos óptimos. Y para que funcione se tienen que dar 3 condiciones:

• El problema debe poder simularse mediante una red de nodos interconectados.
• El problema debe consistir en la búsqueda del camino más corto entre un punto origen y un punto destino determinados.
• Las características de la red deben permitir establecer una función de evaluación heurística. ¿ Pero qué es esto de la heurística ? Lo explicaré a continuación.

Por lo tanto ya observamos de entrada que la filosofía del Algoritmo A* es muy útil para tecnologías como la aplicación Maps, pero no para una partida de ajedrez de un ordenador, o para el diagnóstico de enfermedades vía Inteligencia Artificial.

Pero sigamos explicando como funciona el Algoritmo A* y qué es eso de la función de evaluación eurística.

El Algoritmo A*, tal y como he anticipado, parte de un punto inicio dentro de una red de nodos interconectados. De forma que cada nodo está ligado a una serie de nodos colindantes. Cada una de estas ligaduras tendrá asociada un valor de distancia ( por ejemplo ). 

Imaginemos que el algoritmo se sitúa en un punto “ i “ de la red. Y que este punto “ i “ linda con los puntos “ a “, “ b “ y “ c”. El algoritmo estima la longitud del camino entre el punto origen y el punto de destino final para cada una de estas tres variantes de camino posibles: el camino que pasa por “ a “ desde “ i “, el camino que pasa por “ b“ desde “ i “ y el camino que pasa por “ c “ desde “ i “. A cada una de estas distancias estimadas le llamaremos función de evaluación ( f(n)…f(a), f(b), f(c)….)

Así, por ejemplo, la distancia del camino que pasa por “ a “ desde “ i “ , f(a), la calculará de la siguiente forma: la distancia total será la suma de la distancia desde el origen hasta “ a “ más una estimación de la distancia entre el punto “ a “ y el punto destino del problema.

f (a) = g (a) + h(a)

A esta última estimación es a la que denominamos función de evaluación heurística, h(a). Es una función estimativa, no exacta. Y puede obedecer a diferentes criterios: puede ser la distancia horizontal entre el punto “a” en cuestión y el punto destino, puede ser la distancia vertical entre el punto “ a “ y el destino, puede ser la distancia física ( combinación de x e y ),…o cualquier otro criterio estimativo que creamos oportuno.

Así el algoritmo calculará las 3 opciones f (a), f (b) y f(c). Elegirá la más corta de las 3, y llevará el punto “ i “ a ese nodo que da la distancia estimada más corta. En ese nuevo punto el algoritmo comenzaría el proceso de nuevo entre sus nodos próximos. Y así iríamos guardando la información de los puntos que definen el camino óptimo hasta llegar al punto destino.

Ahora que hemos explicado el funcionamiento básico del algoritmo entendemos por qué el Algoritmo A* requiere de poder establecer una función de evaluación heurística. Si tuviéramos una red de nodos en los que fuera imposible adoptar una función heurística el Algoritmo A* no nos podría ayudar.

Pero ahora que sabemos que el “ ADN del Algoritmo A* “ radica en la función heurística del que lo dotemos nos hacemos una pregunta: ¿ vale cualquier función heurística ? La respuesta es que no. Para que el Algoritmo A* sea capaz de resolver un determinado problema de forma óptima la función heurística del que lo dotemos tiene que ser admisible. Y decimos que una función heurística es admisible si para todos los puntos de la red la estimación de la distancia al punto destino nunca es mayor que la distancia real más corta posible.

Podemos concluir por tanto que el Algoritmo A* , además de solamente dar solución a unos problemas muy específicos dentro del campo de la IA, también requiere unas condiciones determinadas para su cerebro interno, para su función heurística, esta tiene que ser admisible.