Hola AI Padawans,

Hoy hablaremos de un algoritmo muy utilizado en la inteligencia artificial, el A* o ‘a estrella’. Mediante este algoritmo pretendemos realizar una búsqueda en nuestro espacio de soluciones de una forma más eficaz, es decir, con conocimiento de causa.

En primer lugar a grandes rasgos comentar que para que el algoritmo funcione se debe poder establecer un valor de calidad a la solución parcial actual, es decir, un estimador o heurístico. Cada nueva solución propuesta tendrá su propio valor de calidad, lo que determinará el orden en el que la evaluaremos y continuaremos buscando.

De este modo, el algoritmo A* utiliza una función de evaluación f(n) = g(n) + h‘(n), donde h‘(n) representa el valor heurístico del nodo a evaluar desde el actual, n, hasta el final, y g(n), el coste real del camino recorrido para llegar a dicho nodo, n.

A* mantiene dos estructuras de datos auxiliares, que podemos denominar nodos abiertos, implementado como una cola de prioridad (ordenada por el valor f(n) de cada nodo), y nodos 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 f(n) de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.

En resumen, buscamos primero en los más prometedores teniendo en cuenta lo que nos cuesta llegar a la solución parcial y lo que estimamos que nos costará llegar a la solución final.

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 de camino de búsqueda cada vez que existen nodos más prometedores.

El pseudocódigo será:

ABIERTOS := [INICIAL] 	   //inicialización
CERRADOS := []
f'(INICIAL) := h'(INICIAL)
repetir
   si ABIERTOS = [] entonces FALLO
   si no                           // quedan nodos
      extraer MEJORNODO de ABIERTOS con f' mí­nima
         // cola de prioridad
      mover MEJORNODO de ABIERTOS a CERRADOS
      si MEJORNODO contiene estado_objetivo entonces
         SOLUCION_ENCONTRADA := TRUE
      si no
         generar SUCESORES de MEJORNODO
         para cada SUCESOR hacer TRATAR_SUCESOR
hasta SOLUCION_ENCONTRADA o FALLO

Qué tiene que ver el Super Mario en todo esto. Pues bien para ver el ejemplo práctico de aplicación hay que ver algo que nos convenza de la utilidad y de la aplicación práctica del mismo. Con este propósito se muestra la Mario AI Competition, un concurso de desarrolladores de IA para juegos donde la finalidad es generar un Mario Inteligente capaz de sortear a los enemigos.

ABIERTOS := [INICIAL] 	   //inicialización
CERRADOS := []
f'(INICIAL) := h'(INICIAL)
repetir
   si ABIERTOS = [] entonces FALLO
   si no                           // quedan nodos
      extraer MEJORNODO de ABIERTOS con f' mí­nima
         // cola de prioridad
      mover MEJORNODO de ABIERTOS a CERRADOS
      si MEJORNODO contiene estado_objetivo entonces
         SOLUCION_ENCONTRADA := TRUE
      si no
         generar SUCESORES de MEJORNODO
         para cada SUCESOR hacer TRATAR_SUCESOR
hasta SOLUCION_ENCONTRADA o FALLO

Como veis las lineas rojas son las estimaciones de posición futura. En la pasada edición el algoritmo A* ganó la convocatoria. Se trata de calcular sobre el modelo de Mario en Java un agente o entidad inteligente capaz de hacer que Mario llegue lo más rápido y lejos posible.

En este último documento se incluye la presentación del evento, de sus participantes y de sus estrategias predefinidas. Entre ellas una gran descripción de la utilizada por el ganador, Robin Baumgarten, el A Estrella.

>> GIC2009Competition

Veremos más detalles más adelante!

Hasta la próxima!