Inteligencia Artificial

Bsqueda informada y exploracin

Primavera 2007
profesor: Luigi Ceccaroni

Introduccin
La bsqueda informada utiliza el conocimiento especfico del problema. Puede encontrar soluciones de una manera ms eficiente. Una funcin heurstica, h(n), mide el coste estimado ms barato desde el nodo n a un nodo objetivo. h(n) se utiliza para guiar el proceso haciendo que en cada momento se seleccione el estado o las operaciones ms prometedores.
2

Importancia del estimador

A H G F E D C B Estado inicial H1 = 4 H2 = -28 H G F E D C B A Estado final H1 = 8 H2 = 28 (= 7+6+5+4+3+2+1) Estimador H2: - si la estructura de apoyo es correcta sumar 1 por cada bloque de dicha estructura - si la estructura de apoyo no es correcta restar 1 por cada bloque de dicha estructura Estimador H1: - sumar 1 por cada bloque que est colocado sobre el bloque que debe - restar 1 si el bloque no est colocado sobre el que debe Operaciones: - situar un bloque libre en la mesa - situar un bloque libre sobre otro bloque libre

A H G F E D C B Estado inicial H1 = 4 H2 = -28 A H G F E D C B A G F E D C B H

H1 = ? H2 = ?

H1 = ? H2 = ?

G F E D H A C B

H1 = ? H2 = ?

A H G F E D C B Estado inicial H1 = 4 H2 = -28 A H G F E D C B A G F E D C B H

H1 = 6 H2 = -21

H1 = 4 H2 = -15

G F E D H A C B

H1 = 4 H2 = -16

Estrategias de bsqueda informada (heursticas)

No siempre se garantiza encontrar una solucin (de existir sta). No siempre se garantiza encontrar la solucin ms prxima (la que se encuentra a una distancia, nmero de operaciones, menor). BB (Branch & Bound), Bsqueda primero el mejor A, A* A*PI Bsqueda local: ascensin de colinas temple simulado algoritmos genticos bsqueda en lnea

Bsqueda con ramificacin y acotacin (Branch & Bound)

Generaliza BPA y BPP. Se guarda para cada estado el coste de llegar desde el estado inicial a dicho estado: g(n) Guarda el coste mnimo global hasta el momento. Deja de explorar una rama cuando su coste es mayor que el mnimo actual. Si el coste de los nodos es uniforme equivale a una bsqueda por niveles.

Bsqueda voraz primero el mejor

La bsqueda voraz primero el mejor expande el nodo ms cercano al objetivo.
Probablemente conduce rpidamente a una solucin.

Evala los nodos utilizando solamente la funcin heurstica, que, en general, se minimiza, porque se refiere a un coste:
f(n) = h(n)

La minimizacin de h(n) es susceptible de ventajas falsas. 8

Bsqueda voraz primero el mejor

Algoritmo Greedy Best First Est_abiertos.insertar(Estado inicial) Actual= Est_abiertos.primero() Mientras no es_final?(Actual) y no Est_abiertos.vaca?() hacer Est_abiertos.borrar_primero() Est_cerrados.insertar(Actual) hijos= generar_sucesores(Actual) hijos= tratar_repetidos (Hijos, Est_cerrados, Est_abiertos) Est_abiertos.insrtar (Hijos) Actual= Est_abiertos.primero() fMientras fAlgoritmo

La estructura de abiertos es una cola con prioridad. La prioridad la marca la funcin heurstica (coste estimado del camino que falta hasta la solucin). En cada iteracin se escoge el nodo ms cercano a la solucin (el primero de la cola). Esto provoca que no se garantice la solucin ptima.

Funciones heursticas
estado inicial 2 1 7 8 6 3 4 5 Posibles heursticos (estimadores del coste a la solucin) h(n) = w(n) = #desclasificados h(n) = p(n) = suma de distancias a la posicin final h(n) = p(n) + 3 s(n) donde s(n) se obtiene recorriendo las posiciones no centrales y si una ficha no va seguida por su sucesora, sumar 2 si hay ficha en el centro, sumar 1

1 8 7

3 4

estado final

Costes
ni ni C1 ni C2 ... Cl nj nj nj Coste de un arco Coste de un camino Coste del camino mnimo

C(ni,nj)

Si nj es un nodo terminal Si ni es un nodo inicial Si existen varios nodos terminales T={t1, ,tl} Si existen varios nodos iniciales S={s1, ,sl}

h(ni)= k(ni,nj) g(nj)=k(ni,nj) h(ni)=min K(ni,tk) g(nj)=min K(sk,nj)

k=1 k=1 l l

Algoritmos A y A*
La funcin de evaluacin tiene dos componentes: 1) 2) Coste mnimo para ir desde el (un) inicio al nodo actual Coste mnimo (estimado) para ir desde el nodo actual a una solucin

f(n) = g(n) + h(n)

- f es un valor estimado del coste total. - h (funcin heurstica) es un valor estimado de lo que falta por llegar al (a un) objetivo. - g es un coste real: lo gastado por el camino ms corto conocido hasta el momento. - Preferencia siempre al nodo con menor f - En caso de empate, preferencia al nodo con una menor h - h es una estimacin del verdadero coste de alcanzar el objetivo (h*). - Cuanto ms se aproxime h al verdadero coste mejor.

A*

Si h(n) nunca sobrestima el coste real, es decir n h(n) h*(n) se puede demostrar que el algoritmo encontrar (de haberlo) un camino ptimo.

Algoritmo A*
1. 2. 3. 4. 5.
Put the start node S on the nodes list, called OPEN If OPEN is empty, exit with failure Remove from OPEN and place on CLOSED a node n for which f(n) is minimum If n is a goal node, exit (trace back pointers from n to S) Expand n, generating all its successors and attach to them pointers back to n. For each successor n' of n
1. 2.
If n' is not already on OPEN or CLOSED estimate h(n'), g(n')=g(n)+ c(n,n'), f(n')=g(n')+h(n'), and place it on OPEN. If n' is already on OPEN or CLOSED, then check if g(n') is lower for the new version of n'. If so, then:
(i) Redirect pointers backward from n' along path yielding lower g(n'). (ii) Put n' on OPEN.

If g(n') is not lower for the new version, do nothing.

3.

Goto 2

Algoritmo A*
La estructura de abiertos es una cola con prioridad. La prioridad la marca la funcin de estimacin f(n)=g(n)+h(n). En cada iteracin se escoge el mejor camino estimado (el primero de la cola). A* es una instancia de la clase de algoritmos de bsqueda primero el mejor. A* es completo cuando el factor de ramificacin es finito y cada operador tiene un coste positivo fijo.

Tratamiento de repetidos
Si es un repetido que est en la estructura de abiertos:
Si su nuevo coste (g) es menor substituimos el coste por el nuevo; esto podr variar su posicin en la estructura de abiertos Si su nuevo coste (g) es igual o mayor nos olvidamos del nodo

Si es un repetido que est en la estructura de cerrados

Si su nuevo coste (g) es menor reabrimos el nodo insertndolo en la estructura de abiertos con el nuevo coste Atencin! No hacemos nada con sus sucesores; ya se reabrirn si hace falta Si su nuevo coste (g) es mayor o igual nos olvidamos del nodo

Ejemplo: encontrar una ruta en Rumana

Ejemplo de bsqueda A*

Ejemplo de bsqueda A*

Ejemplo de bsqueda A*

Ejemplo de bsqueda A*

Ejemplo de bsqueda A*

Ejemplo de bsqueda A*

A*: admisibilidad
El algoritmo A, dependiendo de la heurstica, encontrar o no una solucin ptima. Si la heurstica es admisible (y se utiliza el algoritmo de bsqueda en rboles), la optimizacin est asegurada. Una heurstica es admisible si se cumple la siguiente propiedad: n 0 h(n) h*(n) Por lo tanto, h(n) ha de ser un estimador optimista, nunca ha de sobreestimar h*(n). Usar una heurstica admisible garantiza que un nodo en el camino ptimo no pueda parecer tan malo como para no considerarlo nunca.

Ejemplo: no admisibilidad
h=3 /\ / \ h=2 h=4 | | | | h=1 h=1 | | | | h=1 goal | | h=1 | | goal

Condicin de consistencia (o monotona)

ni k(ni , nj) nj h(ni) h(nj)

Esta condicin asegura la optimizacin tambin cundo se utiliza el algoritmo de bsqueda en grafos. El nodo n es sucesor de n h(n) = coste estimado desde n a t h(n) cumple la desigualdad triangular: h(ni) k(ni , nj) + h(nj)

h(ni) - h(nj) k(ni , nj)

h(n) consistente estimador uniforme del coste

Condicin de Consistencia
ni k(ni , nj) = 4 nj h(ni) = 10 h(nj) = 8 t Consistente h(ni) h(nj) k(ni , nj) Si h(nj) = 4, la estimacin de h(n) no es uniforme y la heurstica no es consistente.

Condicin de Consistencia
Se puede demostrar que toda heurstica consistente es tambin admisible.

A* utilizando la bsqueda en grafos es ptimo si la h(n) es consistente. La consistencia es una exigencia ms estricta que la admisibilidad. Sin embargo, es difcil crear heursticas que sean admisibles, pero no consistentes. Si h(n) es consistente, entonces los valores de f(n), a lo largo de cualquier camino, no disminuyen.

Optimality of A*
A* expands nodes in order of increasing f value: si h(n) es consistente, entonces los valores de f(n), a lo largo de cualquier camino, no disminuyen. Gradually adds "f-contours" of nodes. Contour i has all nodes with f=fi, where fi < fi+1.

Algoritmos ms o menos informados

Dado un problema, existen tantos A* para resolverlo como heursticas podamos definir.

A1*, A2* admisibles nfinal: 0 h2(n) < h1(n) h*(n) A1* ms informado que A2*

Algoritmos ms informados
A1* ms informado que A2*

n expandido por A1* n expandido por A2*

A1* expande menor nmero de nodos que A2*

En principio interesan algoritmos ms informados

Algoritmos ms informados
Compromiso entre:
Tiempo de clculo
h1(n) requiere ms tiempo de clculo que h2(n) !

Nmero de reexpansiones
A1* puede que re-expanda ms nodos que A2* !
Si A1* es consistente seguro que no Si se trabaja con rboles (y no grafos) seguro que no

Perdida de admisibilidad
Puede interesar trabajar con heursticas no admisibles para ganar rapidez.

Rompecabezas de 8 piezas
(coste operaciones = 1)
1 8 7 6 3 2 4 5 1 8 7 6 2 3 4 5

h0(n)=0 anchura prioritaria, A0* admisible, muchas generaciones y expansiones h1(n)=# piezas mal colocadas A1* admisible, A1* mas informado que A0*

h2(n)=i[1,8]di
di distancia entre posicin de la pieza i y su posicin final (suponiendo camino libre) distancia nmero mnimo de movimientos para llevar la pieza de una posicin a otra A2* admisible. Estadsticamente se comprueba que A2* es mejor que A1*, pero no se puede decir que sea ms informado.

h3(n)=i[1,8]di + 3 S(n) si =

S(n)=i[1,8]si

0 si pieza i no en el centro y sucesora correcta 1 si pieza i en el centro 2 si pieza i no en el centro y sucesora incorrecta

1 8 7 2 6

3 4 5

h3(n)=1+3(2+1)=10 h*(n)=1

A3* no admisible

A3* no se puede comparar con A1* o A2* pero va ms rpido (aunque la h a calcular requiera ms tiempo).

ptimo con limitacin de memoria

El algoritmo A* resuelve problemas en los que es necesario encontrar la mejor solucin. Su coste en espacio y tiempo en el caso medio es mejor que los algoritmos de bsqueda ciega si el heurstico es adecuado. Existen problemas en los que la dimensin del espacio de bsqueda no permite su solucin con A*. Existen algoritmos que permiten obtener el ptimo limitando la memoria usada: A*PI Primero el mejor recursivo A* con limitacin de memoria (MA*)

A*PI
A* en profundidad iterativa es similar a PI (es decir iteracin de bsqueda en profundidad con un lmite en la bsqueda). En PI el lmite lo daba una cota mxima en la profundidad. En A*PI el lmite lo da una cota mxima sobre el valor de la funcin f. Ojo! La bsqueda es una BPP normal y corriente, el heurstico f slo se utiliza para podar. Empezamos con corte = f (inicial) 0+2 g + h (orden de expansin)

1+1 2+1 3+1 4+1 5+0 Objetivo

1+2 2+1 3+1 4+0 Objetivo

A*PI
A* en profundidad iterativa es similar a PI (es decir iteracin de bsqueda en profundidad con un lmite en la bsqueda). En PI el lmite lo daba una cota mxima en la profundidad. En A*PI el lmite lo da una cota mxima sobre el valor de la funcin f. Ojo! La bsqueda es una BPP normal y corriente, el heurstico f slo se utiliza para podar. Empezamos con corte = f (inicial) 0+2 (2,4,9) 1+1 (5,10) (11) 2+1 3+1 4+1 5+0 Objetivo 1+2 2+1 3+1 4+0 (1,3,8) (6,12) (7,13) (14) (15) g + h (orden de expansin)

Objetivo

Algoritmo A*PI
Algoritmo IDA* prof=f(Estado_inicial) Mientras no es_final?(Actual) hacer Est_abiertos.insertar(Estado_inicial) Actual= Est_abiertos.primero() Mientras no es_final?(Actual) y no Est_abiertos.vaca?() hacer Est_abiertos.borrar_primero() Est_cerrados.insertar(Actual) Hijos= generar_sucesores(Actual, prof) Hijos= tratar_repetidos(Hijos, Est_cerrados, Est_abiertos) Est_abiertos.insertar(Hijos) Actual= Est_abiertos.primero() fMientras prof=prof+1 Est_abiertos.incializa() fMientras fAlgoritmo

La funcin generar_sucesores slo genera aquellos con una f menor o igual a la del limite de la iteracin. La estructura de abiertos es ahora una pila (bsqueda en profundidad). Tener en cuenta que si se tratan los nodos repetidos el ahorro en espacio es nulo. Slo se guarda en memoria el camino (la rama del rbol) actual.

Otros algoritmos con limitacin de memoria

Las reexpansiones de A*PI pueden suponer un elevado coste temporal. Hay algoritmos que, en general, re-expanden menos nodos. Su funcionamiento se basa en eliminar los nodos menos prometedores y guardar informacin que permita re-expandirlos (si fuera necesario). Ejemplos: Primero el mejor recursivo A* con limitacin de memoria (MA*)

Primero el mejor recursivo

Es una implementacin recursiva de Primero el mejor con coste lineal en espacio O(rp). Olvida una rama cuando su coste supera la mejor alternativa. El coste de la rama olvidada se almacena en el padre como su nuevo coste. La rama es re-expandida si su coste vuelve a ser el mejor.
Se regenera toda la rama olvidada.

Por lo general re-expande menos nodos que A*PI. Al no poder controlar los repetidos su coste en tiempo puede elevarse si hay ciclos. 40

Primero el mejor recursivo: algoritmo

Accion BPM-recursivo (nodo, c_alternativo, ref nuevo_coste, ref solucion) si es_solucion?(nodo) entonces solucion.aadir(nodo) si no sucesores= genera_sucesores(nodo) si sucesores.vacio?() entonces nuevo_coste=+; solucion.vacio() si no fin=falso mientras no fin hacer mejor= sucesores.mejor_nodo() si mejor.coste() > c_alternativo entonces fin=cierto; solucion.vacio(); nuevo_coste=mejor.coste() si no segundo=sucesores.segundo_mejor_nodo() BPM-recursivo(mejor,min(c_alternativo, segundo.coste()), nuevo_coste, solucion) si solucion.vacio?() entonces mejor.coste(nuevo_coste) si no solucion.aadir(mejor); fin=cierto fsi fsi fmientras fsi fsi faccion

Primero el mejor recursivo Ejemplo

Primero el mejor recursivo Ejemplo

A* con memoria limitada (MA*)

Impone un lmite de memoria (nmero de nodos que se pueden almacenar). Se explora usando A* y se almacenan nodos mientras quepan en la memoria. Cuando no quepan se eliminan los peores guardando el mejor coste de los descendientes olvidados. Se re-expande si los nodos olvidados son mejores. El algoritmo es completo si el camino solucin cabe en memoria.