Ejemplo A*

FUNDAMENTOS DE INTELIGENCIA ARTIFICIAL

Práctica 2 Búsqueda Heurística A*

Realizado por: Francisco José Bueno Nieves

1.

Implementación de práctica
En esta práctica hemos realizado la implementación de la A* de la siguiente forma: 1º He creado una clase Nodo: donde guardaremos la posición x e y, un nodo padre que nos dirá cuál es el nodo anterior de que el nuevo procede, en el casodel Nodo inicial este nodo padre será null. También guardaremos los valores g y h de cada nodo. El valor f no está como atributo sino que simplemente lo devolvemos en un método como la suma de g y h. Después ya en el método AEstrella creo un objeto nodo inicial con la posición x e y del inicio y cuya g=0 y la h es la distancia manhattan entre el punto de inicio y el punto destino. Y a partir de aquícopio el nodo inicio en la lista frontera que junto con la lista interior son ArrayList y ya finalmente sigo el algoritmo A* expuesto en el enunciado.
Alg A* listaInterior = vacio listaFrontera = inicio mientras listaFrontera no esté vacía n = obtener nodo de listaFrontera con menor f(n) = g(n) + h(n) listaFrontera.del(n) listaInterior.add(n) si n es meta devolver reconstruir camino desde lameta al inicio siguiendo los punteros fsi para cada hijo m de n que no esté en listaInterior g’(m) = n.g + c(n, m) //g del nodo a explorar m si m no está en listaFrontera almacenar la f, g y h del nodo en (m.f, m.g, m.h) m.padre = n listaFrontera.add(m) sino si g’(m) es mejor que m.g //Verif. si el nuevo camino es mejor m.padre = n recalcular f y g del nodo m fsi fpara fmientras devolver no haysolución

falg

En el A* destacamos tres elementos como claves en el algoritmo: G*(n): Coste del camino de coste mínimo desde el nodo inicial s al nodo n. H*(n): Coste del camino de coste mínimo de todos los caminos desde el nodo n a cualquier estado solución tj. h*(n) = min k(n, tj). F*(n): Es la suma de G(n)+H(n).

Para obtener el camino solución simplemente voy explorando los nodos padres unavez que hemos llegado al destino:
If (n.x==destino && n.y==tamaño-2) { camino[n.x][n.y]='X'; while(n.padre != null) { camino[n.padre.x][n.padre.y]='X'; n=n.padre; } }

Para marcar los nodos explorados en cada iteración hacemos esto:
if(expandidos[n.x][n.y]==-1) { expandidos[n.x][n.y]=cont; cont++; //Empezando desde 0 }

También he añadido tres métodos más en la clase MiRobot, uno que nos dala distancia manhattan entre dos puntos, otro método que nos da un ArrayList de los hijos posibles de un nodo para que después en el A* los recorramos y por último he creado un método para que me dé el nodo de una lista cuyo F(n) sea el menor.

2.

Función heurística
Diremos que el algoritmo A* es admisible. Es decir, no sólo encuentra la solución sino que la que encuentra es la óptima si secumple la siguiente condición: Para todo n h(n) es menor o igual que h*(n), es decir, si la función heurística que estima la distancia a la meta nunca puede superar la distancia real existente entonces A* garantiza encontrar la solución óptima. Cuanto más correctamente estimemos h(n) menos nodos de búsqueda generaremos. En nuestro caso la función heurística óptima es la función de la distanciamanhattan ya que ningún h(n) es mayor que la distancia real. Distancia Manhattan=|x2-x1|+|y2-y1| //Heurística óptima Vemos que con esta distancia explora en mi caso 82 nodos:

Distancia euclidea= sqrt((x2-x1)2+(y2-y1)2) //Heurística no óptima Como observamos abajo en este caso se exploran muchos más nodos. Aunque en el ejemplo dado consiga el camino óptimo no se trata de una solución no óptima.3.

Funcionamiento A*
A continuación vamos a realizar una traza para comprobar el correcto funcionamiento del algoritmo. Hemos utilizado el siguiente mapa:

A continuación vamos ir comentado los valores de cada atributo que interviene en el algoritmo. Declaramos el Nodo inicio con los siguientes valores: inicio.x=origen = (valor que se extrae de la segunda línea del mundo que se pasa como...