Tema 2: Juegos unipersonales

Resumen: 2. Juegos unipersonales 2.1. Representación básica 2.2. Juegos con información completa 2.3. Recursos limitados en juegos con información completa 2.4. Juegos con información incompleta

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Juegos unipersonales • Juegos sin contrario (pasatiempos) • Ejemplos: – n-Puzzle:

- Laberinto:

1

2

6

4

8

7

3

S

5

A

– n Reinas:

• El agente es el único jugador –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Componentes que definen un problema Problema: – Descripción de los estados (posibles situaciones) – Descripción de los operadores (acciones) • determina en que condiciones (estados) se puede aplicar una acción • determina el resultado de realizar una acción (el estado resultante)

– Función de coste que asigna un coste a cada acción ( o secuencia de acciones) – Descripción de la solución • un estado objetivo (4 reinas) • una acción (laberinto) • una secuencia de acciones (8-puzzle)

Instanciación del problema: – Estado meta – Estado inicial (situación actual) –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejemplo: 8-Puzzle Problema:

Instanciación: Estado inicial

• Estados: – posición de cada una de las piezas

• Acciones: – mover pieza adyacente a la posición del “hueco” – de 2 a 4 operadores aplicables, según el estado

1

2

3

7

8

4

6

5

Estado meta

• Coste: – La aplicación de cada operador vale una unidad

• Solución:

1

2

8 7

3 4

6

5

– secuencia de acciones que lleva de un estado inicial al estado meta –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Representación de problemas / búsqueda en el espacio de estados Ejemplo con 3-Puzzle 2 1

1

3

Solución óptima

2

1

3

3

2

1 3

1 2

3

2

3

1

estado inicial 2 1

3

2

Instanciación estado meta

2 1

3

2

3 1

2

3

3

1

2

–2–

3 1

1

2

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en espacios de estados Espacio de estados: modelo del mundo representado por un grafo mundo situacion acción y sus efectos solución

modelo estado operador plan (secuencia de acciones); acción; estado

representación nodo arco camino; arco; nodo

Problema de búsqueda: espacio de estados + actitud del agente actitud estados meta eficiencia de un plan estado inicial

representación conjunto de nodos coste de un camino nodo inicial

Objetivo: encontrar el plan más eficiente que lleve del estado inicial a un estado meta –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Formalización del problema • Ejemplo 3-Puzzle: – Representación (eficiente) de estados

– Estado inicial

1,2  0,3  

– Estado meta

3,1  2,0  

 x11 , x12  x , x   21 22 

– Coste de un operador: 1 para todos los operadores

– Coste de un plan: suma de los costes de los operadores

– Tipo de solución: plan –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Formalización del problema • Ejemplo 3-Puzzle:

– Operadores:

OP1: OP2: OP3: OP4:

0, x   y, z    0, x   y, z   

 x,0   y, z     y, x  0, z   

 x,0   y, z     x,0   y, z   

0, x   y, z     x, z   y,0   

–2–

OP4: OP5: OP6: OP7:

 y, x  0, z     y, x  0, z   

 y, x   z ,0    0, x   y, z   

 x, z   y,0     x, z   y,0   

 x, z  0, y     x,0   y, z   

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejercicio 2.1 Problema de búsqueda / formalización: En una mesa se encuentran dos jarras, una con una capacidad de 3 litros (llamada Tres), y la otra con una capacidad de 4 litros (llamada Cuatro). Inicialmente, Tres y Cuatro están vacías. Cualquiera de ellas puede llenarse con el agua de un grifo G. Asimismo, el contenido tanto de Tres como de Cuatro puede vaciarse en una pila P. Es posible echar todo el agua de una jarra a la otra. No se dispone de dispositivos de medición adicionales. Se trata de encontrar una secuencia de operadores que deje exactamente dos litros de agua en Cuatro. a) Modele este problema como un problema de búsqueda. Con tal fin, defina una representación eficiente de los estados, el estado inicial, el conjunto de estados meta, los operadores con precondiciones y postcondiciones, tipo de solución, así como el coste de cada operador. b) Encuentre una solución al problema.

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejercicio 2.2 Problema de búsqueda / formalización: Modela el problema de las Torres de Hanoi A

B

C

Objetivo: • Trasladar los discos de la aguja A a B en el mismo orden A

Restricción: • un disco mayor nunca debe reposar sobre uno de menor tamaño

–2–

B

C

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Método general de búsqueda Arbol de búsqueda:

Método de búsqueda: • estrategia para explorar el espacio de estados • en cada paso se expande un estado • se desarrolla sucesivamente un árbol de búsqueda

1 2 3 1 2 3

2 1 3 2 1 3

1 2 3

1 2 3

1 3 2 1 2 3

Método general de búsqueda: 1. seleccionar nodo hoja 2. comprobar si es nodo meta 3. expandir este nodo hoja

1 3 2

–2–

1 3 2

3 1 2

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Algoritmo general de búsqueda Elementos del algoritmo • el árbol se representa en base a un registro del tipo nodo • s0 estado inicial • abierta es una lista de nodos, con las hojas actuales del árbol • vacía? determina si una lista es vacía • primero quita el primer elemento de una lista • ordInsertar añade un nodo a una lista, según una función de orden (determina el método de búsqueda)

{búsqueda general} abierta ← s0 Repetir Si vacía?(abierta) entonces devolver(negativo) nodo ← primero(abierta) Si meta?(nodo) entonces devolver(nodo) sucesores ← expandir(nodo) Para cada n∈sucesores hacer n.padre ← nodo ordInsertar(n,abierta,) Fin {repetir}

• expandir devuelve los hijos de un nodo

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Conocimientos mínimos a priori de un agente • Conocimientos mínimos a priori de un agente de búsqueda en el espacio de estados: – s0

Estado inicial

– expandir: s  {si1, ..., sin}

Aplica los posibles operadores a s y devuelve todos los posibles estados succesores

– meta?: s  verdad | falso

Compara el estado s con los estados meta y devuelve verdad si s es un estado meta

– c: (si, sj )  v, v∈ℵ

Coste de un operador

(

)

n −1

(

c si1 si2  sin = ∑ c sik , sik +1

)

Coste de un plan

k =1

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Estados repetidos Problema: • el mismo estado puede repetirse varias veces en el árbol de búsqueda • puede generarse el mismo subárbol varias veces

Soluciones: • ignorarlo • evitar ciclos simples: – no añadir el padre de un nodo al conjunto de sucesores

• evitar ciclos generales: – no añadir un antecesor de un nodo al conjunto de sucesores

• evitar todos los estados repetidos: – no añadir ningún nodo existente en el árbol al conjunto de sucesores

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Clasificación de métodos de búsqueda

Características: • Completitud: se encuentra una solución si existe • Optimalidad: se encuentra la mejor solución si hay varias • Complejidad en tiempo: ¿cuánto se tarda en encontrar la solución? • Complejidad en espacio: ¿cuánta memoria se utiliza en la búsqueda?

Tipos de métodos de búsqueda: • no informados: utilizan sólo los conocimientos a priori • heurísticos: además utilizan información aproximada, y específica del problema, para guiar la búsqueda

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Métodos de búsqueda para juegos unipersonales Juegos con información completa: – Búsqueda en amplitud y en profundidad – Búsqueda de profundización iterativa – Búsqueda bidireccional

Recursos limitados – – – – –

Búsqueda voraz Búsqueda A* Búsqueda con subobjetivos Búsqueda por ascenso de colinas Búsqueda con horizonte

Juegos con información incompleta – Búsqueda A* en tiempo real – Búsqueda con aprendizaje del A* en tiempo real

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Tema 2: Juegos unipersonales

Resumen: 2. Juegos unipersonales 2.1. Representación básica 2.2. Juegos con información completa Búsqueda en amplitud Búsqueda en profundidad Búsqueda en profundidad limitada Búsqueda de profundización iterativa Búsqueda bidireccional 2.3. Recursos limitados en juegos con información completa 2.4. Juegos con información incompleta

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejemplo base: 8-Puzzle Problema:

Instanciación: Estado inicial

• Estados: – posición de cada una de las piezas

• Acciones: – mover pieza adyacente a la posición del “hueco” – de 2 a 4 operadores aplicables, según el estado

1

2

3

7

8

4

6

5

Estado meta

• Coste: – La aplicación de cada operador vale una unidad

• Solución:

1

2

8 7

3 4

6

5

– secuencia de acciones que lleva de un estado inicial al estado meta –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en amplitud Búsqueda en amplitud: • inglés: breadth first search • Estrategia: – generar el árbol por niveles de profundidad – expandir todos los nodos de nivel i, antes de expandir nodos de nivel i+1

• Resultado: – considera primero todos los caminos de longitud 1, después los caminos de longitud 2, etc. – Se encuentra el estado meta de menor profundidad –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Árbol de búsqueda en amplitud (evitando ciclos simples) 1 2 3 7 8 4 6 5

Nivel 1 1 2 3 7 4 6 8 5

Nivel 2

Nivel 3

1 2 3 7 4 6 8 5

1 2 3 6 7 4 8 5

1 2 3 7 4 6 8 5

3 1 7 2 4 6 8 5

1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

1 2 3 8 4 6 5 7

1 2 3 7 8 6 5 4

2 3 1 7 4 6 8 5

1 2 3 7 4 5 6 8

1 2 7 4 3 6 8 5

1 3 7 2 4 6 8 5

1 3 7 2 4 6 8 5

2 3 1 8 4 7 6 5

...

...

...

...

...

...

1 2 3 8 4 7 6 5

1 2 3 8 7 6 5 4

1 2 7 8 3 6 5 4

Nivel 4

... Nivel 5

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Algoritmo para búsqueda en amplitud {búsqueda en amplitud} abierta ← s0 Repetir Si vacía?(abierta) entonces devolver(negativo) nodo ← primero(abierta) Si meta?(nodo) entonces devolver(nodo) sucesores ← expandir(nodo) Para cada n∈ sucesores hacer n.padre ← nodo ordInsertar(n,abierta,final) Fin {repetir}

Algoritmo: • usar el algoritmo general de búsqueda • añadir nuevos sucesores al final de la lista abierta • abierta funciona como cola – inserción al final – recuperación desde la cabeza

• estructura FIFO: – siempre expandir primero el nodo más antiguo (es decir: menos profundo)

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Árbol de búsqueda en amplitud 1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

1 2 3 7 4 6 8 5

1 2 3 7 4 6 8 5

1 2 3 7 4 6 8 5

3 1 7 2 4 6 8 5

1 2 3 2 3 6 7 4 1 7 4 8 5 6 8 5

1 3 7 2 4 6 8 5

... ...

... ...

1 2 3 7 4 5 6 8

1 2 7 4 3 6 8 5

... ...

1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

1 2 3 8 4 7 6 5

1 2 3 7 8 6 5 4

1 3 7 2 4 6 8 5

2 3 1 8 4 7 6 5

1 2 3 8 7 6 5 4

1 2 7 8 3 6 5 4

1 2 3 8 4 7 6 5

Lista abierta:

1 2 3 7 4 6 8 5

1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

1 2 3 7 4 6 8 5

1 2 3 7 8 4 6 5

1 2 3 7 4 6 8 5

1 2 3 7 4 6 8 5

... ...

3 1 7 2 4 6 8 5

1 2 3 7 4 6 8 5

1 2 3 7 4 6 8 5 3 1 7 2 4 6 8 5

1 2 3 7 4 6 8 5

3 1 7 2 4 6 8 5

1 2 3 8 4 7 6 5

1 2 3 7 8 6 5 4

1 3 7 2 4 6 8 5

2 3 1 8 4 7 6 5

1 2 3 8 4 7 6 5

1 3 7 2 4 6 8 5

2 3 1 8 4 7 6 5

1 2 3 8 4 7 6 5

1 2 3 8 7 6 5 4

1 2 7 8 3 6 5 4

...

...

... 1 2 3 8 4 7 6 5

... –2–

1 2 3 8 4 7 6 5

1 2 3 8 7 6 5 4

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

1 2 7 8 3 6 5 4

Complejidad Complejidad en espacio: • proporcional al número de nodos abiertos Complejidad en tiempo: • proporcional al número de nodos expandidos Suponemos que en el árbol de búsqueda • el factor de ramificación es b • el mejor nodo meta tiene profundidad d Mejor caso Caso medio 0 1

d–1 d

0

0 1

...

d–2

Peor caso 1

...

d–1

d–1

d

d

d+1

d+1

...

espacio:

1+b+...+bd-1 +bd ∈ O(bd) 1+b+...+bd +bd+1/2 ∈ O(bd)

1+b+...+bd + bd+1-b ∈ O(bd)

tiempo:

1+b+...+bd-1 ∈ O(bd)

1+b+...+bd -1 ∈ O(bd)

1+b+...+bd /2 ∈ O(bd) –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Requerimientos de tiempo y memoria

Requerimientos de recursos de una búsqueda en amplitud exponencial • factor de ramificación efectivo: 10 • tiempo: 1000 nodos/segundo • memoria: 1000 bytes/nodo profundidad 0 2 4 6 8 10 12 14

tiempo

nodos (abiertos) 1 111 11.111 106 108 1010 1012 1014

1 100 11 18 31 128 35 3500

–2–

ms ms s min horas días años años

memoria 100 11 1 111 11 1 111 11.111

Bytes KB MB MB GB TB TB TB

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en amplitud: análisis

Ventajas: • completo: – siempre se encuentra un nodo meta si existe

• óptimo (para operadores de coste uno): – siempre se encuentra el nodo meta menos profundo

Problemas: • complejidad – exponencial incluso en el mejor caso – los problemas de espacio son aún más graves que los problemas de tiempo

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejercicio 2.3 Búsqueda en amplitud: El grafo que se muestra al lado determina un problema de búsqueda. Cada nodo representa un estado; los arcos modelan la aplicación de operadores. Suponga que A es el estado inicial y que K y E son estados meta a) desarrolle el árbol de búsqueda que genera la búsqueda en amplitud. ¿Cuál de los nodos meta se encuentra primero? b) indique el orden en que se expanden los nodos c) ponga el estado de la lista abierta en cada paso del algoritmo

–2–

A D

G

F

H

C

B

K

E Z

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

W

Búsqueda en profundidad Búsqueda en profundidad: • inglés: depth first search • Estrategia: – expandir el árbol de “izquierda a derecha” (los nodos más profundos primero) – si se llega a un nodo sin sucesores, dar vuelta atrás y expandir el siguiente nodo más profundo

• Resultado: – el método va explorando un “camino actual” – no siempre se encuentra el nodo de profundidad mínima

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Árbol de búsqueda en profundidad (evitando ciclos simples) 1 2 3 7 8 4 6 5 1 2 3 7 8 4 6 5

1 2 3 7 4 6 8 5 1 2 3 7 4 6 8 5 1 2 3 6 7 4 8 5

1 2 3 7 4 6 8 5

1 2 3 7 8 4 6 5

1 2 3 8 4 7 6 5

3 1 7 2 4 6 8 5

1 2 3 8 4 7 6 5

2 3 1 7 4 6 8 5

1 2 3 6 7 4 5 8

Solución óptima

1 2 3 6 4 8 7 5

1 2 3 6 7 4 8 5

1 2 3 6 4 8 7 5

1 2 3 6 4 8 7 5

3 1 6 2 4 8 7 5

... 1 2 3 8 4 7 6 5

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en profundidad Algoritmo: • usar el algoritmo general de búsqueda • añadir nuevos sucesores en la cabeza de la lista abierta • abierta funciona como pila – inserción en la cabeza de la lista – recuperación desde la cabeza

• estructura LIFO: – siempre expandir primero el nodo más reciente (es decir: el más profundo)

• al guardar todos los sucesores de un nodo expandido en abierta, se permite la “vuelta atrás” –2–

{búsqueda en profundidad} abierta ← s0 Repetir Si vacía?(abierta) entonces devolver(negativo) nodo ← primero(abierta) Si meta?(nodo) entonces devolver(nodo) sucesores ← expandir(nodo) Para cada n∈ sucesores hacer n.padre ← nodo ordInsertar(n,abierta,cabeza) Fin {repetir}

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Árbol de búsqueda en profundidad 1 2 3 7 8 4 6 5 1 2 3 7 8 4 6 5

1 2 3 7 4 6 8 5 1 2 3 7 4 6 8 5 1 2 3 6 7 4 8 5

1 2 3 7 4 6 8 5

1 2 3 7 8 4 6 5 1 2 3 7 8 4 6 5

3 1 7 2 4 6 8 5

1 2 3 6 7 4 5 8 1 2 3 6 4 8 7 5

1 2 3 6 7 4 8 5

1 2 3 6 4 8 7 5

1 2 3 6 4 8 7 5

3 1 6 2 4 8 7 5

1 2 3 7 8 4 6 5

1 2 3 7 4 6 8 5

3 1 2 3 1 2 3 1 2 3 1 7 4 7 2 4 7 8 4 7 8 4 6 5 6 5 6 8 5 6 8 5 2 3 1 2 3 1 3 1 2 3 1 2 1 7 4 7 4 7 2 4 7 8 4 7 8 6 8 5 6 8 5 6 8 5 6 5 6 5 2 3 1 2 3 1 3 1 2 3 1 2 1 7 4 7 4 7 2 4 7 8 4 7 8 6 8 5 6 8 5 6 8 5 6 5 6 5

1 2 3 1 2 3 6 4 6 7 4 8 7 5 8 5

2 3 1 7 4 6 8 5

1 2 3 1 2 3 6 4 6 4 8 7 5 8 7 5

3 1 6 2 4 8 7 5

1 7 6 1 6 8

3 1 6 2 4 8 7 5

1 2 3 6 7 4 8 5

2 4 8 2 7 5

3 5 3 4

3 1 7 2 4 6 8 5 2 3 1 7 4 6 8 5

3 4 3 4

1 2 3 7 8 4 6 5

...

1 2 3 7 8 4 6 5 1 2 3 7 8 4 6 5

...

... 1 2 3 8 4 7 6 5

1 2 3 7 8 4 6 5

1 2 3 7 4 6 8 5

1 2 3 6 7 4 8 5 1 2 3 6 7 4 5 8

2 3 1 7 4 6 8 5

Lista abierta:

1 2 3 8 4 7 6 5 –2–

1 2 3 6 4 8 7 5

2 3 1 7 4 6 8 5

...

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

1 2 3 7 8 4 6 5

Límites de profundidad Problema: • si existen caminos infinitos sin nodo meta, es posible que la búsqueda en profundidad no termine • la búsqueda en profundidad sólo es completa: – en el caso de árboles de búsqueda finitos – para espacios de búsqueda finitos; si se controla nodos repetidos en la misma rama del árbol

Solución: • búsqueda en profundidad limitada: – – – –

inglés: depth limited search búsqueda en profundidad con límite de profundidad d* antes de expandir un nodo, compruebe su profundidad expandir sólo nodos con profundidad d0) f* f *(nm2)

f

*(n

Nodo meta no óptimo: g(nm2)>g(nm1)

Mejor nodo meta: f *(nm1)=h*(nm)+g(nm1)=g(nm1)=f(nm1)

m1)

Camino infinito: Tiene que cruzar f*(nm1) an algún punto ninicial

nm –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Calidad de las Funciones Heurísticas Definición: Sean h1* y h2* dos funciones heurísticas optimistas. h1* es más informada que h2*, si para todo nodo n se cumple que h1*(n ) ≥ h2*(n ) Ejemplo: • en el 8-puzzle, hc* es más informada que ha* – las piezas bien colocadas no cuenta en ha* ni en hc* – la distancia Manhattan de cada pieza descolocada es al menos 1 – en consecuencia, en toda posible configuración n del 8-puzzle la suma de las distancias es igual o mayor que la suma de piezas descolocadas – para todas las configuraciones n se cumple hc*(n ) ≥ ha*(n )

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Complejidad de A* El número de nodos expandidos por A* depende de la calidad de h*: • Para dos funciones heurísticas h1* y h2* : – Si h1* es más informada que h2*, entones A*(h1* ) expande el mismo número o menos nodos que A*(h2* )

• La complejidad es más baja si h* es más informada: – si h*(n) = h(n) para todos los nodos n: • información completa: complejidad lineal (sin contar la complejidad de computar h*!) • calcular h*(n) suele equivaler a resolver el problema completo – si h*(n) = 0 para todos los nodos n: • A* degenera a la búsqueda por amplitud

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Resultados experimentales Comparación experimental: • número de nodos expandidos en el problema del 8-puzzle • varias profundidades d de la solución • media sobre 100 instancias del problema

d

prof. iterativa

2 4 6 8 10 12 14 16 18 20 22 24

10 112 680 6.384 47.127 3.644.035 — — — — — —

A*(ha) 6 13 20 39 93 227 539 1.301 3.056 7.276 18.094 39.135 –2–

A*(hc) 6 12 18 25 39 73 113 211 363 676 1.219 1.641 Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejercicio 2.10 Algoritmo A* :

A

Suponga el juego de las torres de Hanoi con el estado inicial que se presenta al lado. El objetivo consiste en pasar la torre bien a la aguja B o bien a la aguja C. Se filtren todos los estados repetidos y equivalentes (dos estados se consideran equivalentes, si están los mismos discos en la aguja A mientras que los discos de las agujas B y C están intercambiadas).

A

B

B

C

C

a)Defina una función heurística para este problema. b)Desarrolle el árbol de búsqueda que genera el algoritmo A*, incluyendo los valores de g, h *, y f * de cada nodo. Indique el orden en que se expanden los nodos.

A

B

C

c)¿Su función heurística es optimista? Argumente su respuesta. –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por Subobjetivos Idea: • reducir la anchura del árbol al subdividir el problema en varios problemas más pequeños • determinar una secuencia de estados intermedios i1,i2,...,in que “muy posiblemente” están en el camino óptimo • realizar búsquedas con un método base (amplitud, prof., prof. iterativa, ...) desde el estado inicial s0 a i1, de i1 a i2,…, e de in al estado meta sm • se aplica la heurística para elegir los estados intermedios Ejemplo 8-Puzzle: obtener filas correctas 3 1 7 2 4 6 8 5

s0 estado inicial

1 2 3 8 4 ? ? ?

1 2 3 ? ? ? ? ? ?

i2

i1 estados intermedios –2–

1 2 3 8 4 7 6 5

sm estado meta Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por subobjetivos (evitando ciclos simples) Método base: búsqueda en amplitud camino de s0 a i1: s0

i1

3 1 7 2 4 6 8 5

1 2 3 7 4 6 8 5

1 3 7 2 4 6 8 5

–2–

1 3 7 2 4 6 8 5

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por subobjetivos (evitando ciclos simples) camino de i1 a i2:

1 2 3 7 4 6 8 5

i1

1 2 3 7 4 6 8 5

1 2 3 7 8 4 6 5

1 2 3 7 4 6 8 5

3 1 7 2 4 6 8 5

2 3 1 7 4 6 8 5

1 2 3 6 7 4 8 5

1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

1 2 7 4 3 6 8 5

1 2 3 7 4 5 6 8

1 3 7 2 4 6 8 5

1 3 7 2 4 6 8 5

3 2 1 7 4 6 8 5

1 2 3 6 7 4 8 5

1 2 3 7 8 6 5 4

1 2 3 8 4 7 6 5

2 1 3 7 4 6 8 5

1 2 3 7 4 5 6 8

7 1 3 2 4 6 8 5

1 3 4 7 2 6 8 5

2 7 3 4 1 6 8 5

...

1 2 3 8 7 6 5 4

2 3 1 7 4 6 8 5

...

1 2 3 4 6 8 7 5

1 2 3 6 7 4 8 5

...

...

...

1 4 2 3 7 6 8 5

1 2 7 8 3 6 5 4

...

2 3 1 8 4 7 6 5

1 2 3 8 4 7 6 5

i2=sm

–2–

1 2 7 4 3 6 8 5 1 2 3 5 7 6 4 8

7 1 3 2 4 6 8 5 1 2 3 7 4 5 6 8

7 1 3 6 2 4 8 5 1 3 4 7 2 6 8 5

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

1 3 4 7 2 5 6 8

Búsqueda por subojetivos: complejidad • Complejidad en espacio: proporcional al número de nodos abiertos • Complejidad en tiempo: proporcional al número de nodos expandidos • En general se obtiene una mejora de la complejidad respecto a los métodos de búsqueda no informados que se usan como base – basado en: la suma de varias búsquedas pequeñas es más eficiente que una búsqueda global – depende de la selección inicial de los subojetivos – condición necesaria para una mejora: los caminos entre los pares de subojetivos están “más cortos” que la solución global

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por subojetivos: Ejemplo complejidad General:

método base: búsqueda en amplitud; factor de ramificación efectivo: b; profundidad de la mejor solución: d; x subojetivos intermedios; profundidad de los caminos mínimos entre los subobjetivos: d’

Ejemplo:

b=3; d=20; x=4; d’=5 (el camino encontrado tiene una longitud de 25)

General Bús. prof. Bús. subob. mejor caso: - tiempo:

bd −1 b −1

d +1 b −1 - espacio: b −1

bd ' − 1 ( x + 1) * b −1 b d '+1 − 1 ( x + 1) * b −1

Ejemplo Bús. prof. Bús. subob. 1.743.392.200

605

5.230.176.601

1820

b d +1 − 1 peor caso: - tiempo: −1 b −1

 b d '+1 − 1  ( x + 1) *  − 1  b −1 

5.230.176.600

1815

d +2 b −1 - espacio: −b b −1

 b d '+2 − 1   ( x + 1) *  − b   b −1 

15.690.529.801

5450

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por subojetivos: análisis Análisis: • Es completo si: – El método base es completo, y – Los subobjetivos están en (por lo menos) un camino que lleva del estado inicial a la meta

• Es óptimo si: – El método base es óptimo, y – Los subobjetivos están en este orden en el camíno mínimo desde el estado inicial a la meta

Comentarios: • Es posible utilizar búsquedas heurísticas como método base (p.e. búsqueda voraz) • Es posible modificar el método para realizar búsquedas jerárquicas: – Aplicar la búsqueda a distintos niveles jerárquicas – Por ejemplo: buscar un camino (en coche/barco) desde Madrid a Buenos Aires –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejercicio 2.11 Problema de las 5 reinas: Resuelve el problema de las 5 reinas (del ejercicio 2.9) con la búsqueda por subobjetivos a) Utilizando como estado inicial el estado descrito en el ejercicio 2.9, define una serie de estados intermedios. b) Realiza los árboles de la búsqueda por subobjetivos, utilizando como método base la búsqueda por profundidad limitada. Determina un limite de profundidad adecuado. c) Analizar los árboles obtenidos y el árbol del ejercicio 2.9, para comparar la complejidad de los dos métodos.

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas (hill climbing) • Idea subyacente: – Reducir profundidad del árbol expandido (“on line search”)

– Realizar siempre la acción más prometedora – Expandir el árbol sólo un nivel y realizar la acción hacía el “mejor” nodo – Repetir el ciclo percepción/acción de forma continua

Repetir: 1. percibir estado 2. expandir nodo 3. elegir nodo más prometedor 4. realizar acción Fin repetir Solución óptima

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Algoritmo búsqueda por ascenso de colinas {búsqueda ascenso de colinas} Repetir h*: función heurística que estima la nodo ← percibir(entorno) distancia al nodo meta más cercano Si meta?(nodo) entonces percibir(entorno): devuelve el estado actual del problema devolver(positivo) evaluar(n,h*): calcula el valor de la sucesores ← expandir(nodo) función heurística h* para el nodo n Si vacia?(sucesores) entonces – debería comprobar si n es nodo meta – en este caso debería devolver el mínimo devolver(negativo) * valor posible mejor ← arg min evaluar ( n, h ) acción(n,m):devuelve la acción que lleva n∈sucesores de n a m a ←acción(n,mejor) ejecutar(a, entorno): efectúa la acción a ejecutar(a, entorno) en el entorno Fin {repetir}

Algoritmo: • • •

• •

[

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

]

Búsqueda por ascenso de colinas: Ejemplo Función heurística: ha* (piezas descolocadas) 3 1 7 2 4 6 8 5

ha* = 3

*

ha = 3

1 2 3 7 4 6 8 5

*

ha = 3

1 2 3 4 7 6 8 5

ha = 3

2 3 1 7 4 6 8 5

ha = 4

ha* = 3

1 2 3 6 7 4 5 8

1 2 3 7 4 6 8 5

ha* = 3

ha* = 3

1 2 3 6 4 8 7 5

1 2 3 6 7 4 8 5

*

1 2 3 7 4 6 8 5

1 2 3 7 8 4 6 5

1 2 3 6 7 4 8 5

*

ha* = 4

1 3 7 2 4 6 8 5

1 2 3 7 4 6 8 5

ha* = 3

1 2 3 6 7 4 8 5

ha* = 3 –2–

ha* = 4

3 1 7 2 4 6 8 5

ha* = 5

1 3 7 2 4 6 8 5

ha* = 5

ha* = 4

¡No se evitan ciclos simples! Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas: Ejemplo (cont.) Función heurística: ha* (piezas descolocadas) 1 2 3 6 4 8 7 5

ha* = 3

ha* = 4

*

1 2 3 8 6 4 7 5

2 3 1 6 4 8 7 5

ha = 3

1 2 3 6 4 8 7 5

1 2 3 6 4 8 7 5

1 2 3 6 4 8 7 5

ha* = 2

1 2 3 8 6 4 7 5

ha* = 2 1 2 3 8 6 4 7 5

1 2 3 6 4 8 7 5

ha* = 4

3 1 6 2 4 8 7 5

*

ha = 4

1 2 3 6 7 4 5 8

ha* = 3

ha* = 3

ha* = 1 1 2 3 8 4 7 6 5

ha* = 0

1 2 3 8 6 4 7 5

ha* = 2

¡No es la solución óptima! –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas: complejidad • Proporcional al número de nodos abiertos/expandidos • d profundidad de la mejor solución, b factor de ramificación efectivo • Complejidad en espacio: – O(b) solo se mantiene en memoria los hijos de un nodo

• Complejidad en tiempo: – depende de la función heurística – hay que contar la complejidad de calcular h* – si h*(n)=h(n): • la búsqueda “va directamente a la solución” • caso irreal, ya que significa que se conozca la solución • complejidad en tiempo: O(d)

– otros casos: • puede ser mayor que en la búsqueda por amplitud (si la función heurística es mala) –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas: análisis Análisis: • Suele obtener buenos resultados en algunos casos, especialmente: – si no hay ciclos – la función heurística es muy buena

• En general, no se puede asegurar optimalidad ni completitud • No se puede evitar ciclos simples • Si h* es ideal (h*=h), entonces es óptimo y completo • Se puede conseguir completitud: – Si el conjunto de posibles estados es finito – Si se guardan todos los estados a los que se ha ido en el pasado: • cada vez que se llega a un estado repetido, se elige una acción que no se ha elegido anteriormente • pero, para eso hay que guardar todo el árbol y la ganancia en complejidad se pierde –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda por ascenso de colinas: comentarios Comentarios: • Aplicable en entornos inaccesibles o dinámicos – Ejemplos: Laberinos, Robot moviéndose en un entorno real, … • Útil en tareas de optimización, donde se quiere mejorar el estado continuamente – Ejemplo: Controlar los parámetros de procesos industriales Posibles modificaciones: • Se podría evitar ciclos simples guardando el último estado conocido • Buscar un camino completo: – Realizar el algoritmo “off line” – Solo simular las acciones pero no efectuarlas en el entorno – No intercalar la búsqueda con el ciclo percepción/acción – No es posible en entornos inaccesibles o dinámicos

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejercicio 2.12 Búsqueda por ascenso de colinas Al lado se muestra el plano de una habitación. El agente (A) tiene que encontrar un camino a la salida (S). En cada acción, el agente puede moverse a un cuadro adyacente (no diagonal), si no existe un obstáculo que lo impida. El agente conoce todo el plano de antemano. a) Resuelve el problema mediante la búsqueda por ascenso de colinas (evitando ciclos simples). b) Resuelve el problema mediante la búsqueda voraz (evitando ciclos simples). c) Suponiendo que se evitan ciclos simples, ¿Qué diferencias hay entre estos dos métodos? d) ¿Qué ocurre (en ambos métodos) si no se evitan los ciclos simples?

–2–

S A

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte • Idea subyacente: – la primera acción de un plan que lleva a un nodo con una evaluación heurística óptima, tiene una buena probabilidad de pertenecer al camino óptimo – Reducir profundidad del árbol expandido (“on line search”)

– Expandir el árbol hasta un nivel k (horizonte) y realizar la acción hacía el “mejor” nodo en el nivel k – Repetir el ciclo percepción/acción de forma continua

• Algoritmo general: – Percibir el estado actual s – Aplicar un método de búsqueda no informado hasta el nivel k y nodos metas. – Sea H el conjunto de nodos hoja hasta el nivel k: * * • Utilizar h* para determinar el “mejor” nodo hoja n*∈H: n ← arg min[h (n)] n∈H – Ejecutar la primera acción a* en el camino que lleva a n* – Repetir hasta que el agente se encuentra en un estado meta

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: Ejemplo método base: búsqueda en profundidad limitada estado actual =

3 1 7 2 4 6 8 5

horizonte k = 3 filtrando ciclos simples h*=ha* (piezas descolocadas)

3 1 7 2 4 6 8 5 1 2 3 7 4 6 8 5

1 2 3 7 4 6 8 5 2 3 1 7 4 6 8 5

k=3 h *=4 a

1 2 3 6 7 4 8 5

ha*=3

1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

ha*=4

1 2 3 7 8 4 6 5

ha*=2

1 2 3 7 4 6 8 5 1 2 7 4 3 6 8 5

ha*=6

–2–

1 2 3 7 4 5 6 8

ha*=5

1 3 7 2 4 6 8 5

1 3 7 2 4 6 8 5

7 1 3 2 4 6 8 5

1 3 4 7 2 6 8 5

7 1 3 2 4 6 8 5

ha*=5

7 1 3 6 2 4 8 5

ha*=5

1 3 4 7 2 6 8 5

ha*=6

1 3 4 7 2 5 6 8

ha*=7

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: Ejemplo método base: búsqueda en profundidad limitada estado actual =

1 2 3 7 4 6 8 5 1 2 3 7 4 6 8 5

horizonte k = 3 filtrando ciclos simples h*=ha* (piezas descolocadas) 1 2 3 7 4 6 8 5

k=3

1 2 3 7 8 4 6 5

1 2 3 7 4 6 8 5

3 1 7 2 4 6 8 5

2 3 1 7 4 6 8 5

1 2 3 6 7 4 8 5

1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

1 2 7 4 3 6 8 5

1 2 3 7 4 5 6 8

1 3 7 2 4 6 8 5

1 3 7 2 4 6 8 5

3 2 1 7 4 6 8 5

1 2 3 6 7 4 8 5

1 2 3 7 8 6 5 4

1 2 3 8 4 7 6 5

2 1 7 4 3 6 8 5

1 2 3 7 4 5 6 8

7 1 3 2 4 6 8 5

1 3 4 7 2 6 8 5

ha*=5

ha*=6

ha*=5

ha*=3

ha*=5

ha*=1

–2–

ha*=6

ha*=5

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: Ejemplo método base: búsqueda en profundidad limitada estado actual =

1 2 3 7 8 4 6 5

horizonte k = 3 filtrando ciclos simples h*=ha* (piezas descolocadas) 1 2 3 7 8 4 6 5

1 2 3 7 8 4 6 5

1 2 3 7 8 6 5 4

1 2 3 8 4 7 6 5

1 2 3 8 7 6 5 4

k=3

1 2 3 7 8 4 6 5

ha*=5

1 2 7 8 3 6 5 4

1 2 3 8 4 7 6 5

ha*=6

ha*=0

–2–

1 2 3 7 4 6 8 5

2 3 1 8 4 7 6 5

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: complejidad • Proporcional al número de nodos abiertos/expandidos • b factor de ramificación efectivo, k limite de profundidad • Método base: búsqueda en profundidad limitada • Complejidad en espacio: – (k*b)+1∈ O(b*k) (solo se mantiene el camino explorado y sus vecinos en la memoria)

• Complejidad en tiempo: – el encontrar un nodo meta y su profundidad depende de la función heurística – hay que contar la complejidad de calcular h*

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: complejidad Complejidad en tiempo: • si se encuentra una solución con profundidad d≤k : – igual que en la búsqueda en profundidad limitada: – mejor caso: d∈ O(d) – peor caso: 1+b+...+bk-1∈ O(bk)

• si se encuentra una solución con profundidad d>k : – primero hay que realizar d-k búsquedas en profundidad limitadas completos – en el siguiente paso se encuentra la solución en la profundidad k – mejor caso: (d − k )(1 + b + b +  + b 2

k −1

(b k − 1) ) + k = (d − k ) +k b −1

– peor caso: (d − k + 1)(1 + b + b +  + b 2

–2–

k −1

(b k − 1) ) = (d − k + 1) b −1

∈ O(d ⋅ b k ) ∈ O(d ⋅ b k )

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte : análisis Análisis: • En general, no se puede asegurar optimalidad ni completitud – depende de la función heurística

• Si h* es ideal (h*=h), entonces es óptimo y completo • La búsqueda por ascenso de colinas es un caso especial de la búsqueda con horizonte (horizonte = 1) • Aumentar el horizonte k: – permite evitar ciclos de longitud k o menor – se trata mejor el caso en los que varias acciones tienen el mismo valor heurístico (ver ejemplo)

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda online y optimización La búsqueda online (horizonte/ascenso de colinas) es aplicable a problemas de optimización. Problema de optimización: • El objetivo es encontrar el mejor estado según una función objetivo • No necesariamente se busca un estado exacto, sino uno que se acerca al máximo al objetivo • El camino para llegar al estado buscado puede ser irrelevante (coste 0) • Ejemplos: juegos lógicos y de configuración, n-Reinas Funciones heurísticas para problemas de optimización: • Funciones que estimen el coste del camino hasta el nodo meta más próximo (todos los que hemos visto hasta ahora) • Funciones que miden la calidad de un nodo respecto a la función objetivo • Muchas funciones heurísticas estiman las dos cosas a la vez • A veces es más fácil definir una heurística que estime la “calidad” de los nodos

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda online y optimización: El juego de las cifras El juego de las cifras: • Combinar una serie de CIFRAS mediante las operaciones de suma y multiplicación de tal forma que el resultado se acerca lo máximo a un número dado (EXACTO). • Ejemplo: CIFRAS: 6 2 5 25 EXACTO: 420 • El objetivo consiste en encontrar una secuencia de operaciones, que aplicadas sobre (algunas de) las cifras de entrada, y sobre los resultados intermedios, permiten obtener un número lo más próximo a EXACTO. Cada cifra se puede utilizar sólo una vez.

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda online y optimización: El juego de las cifras • Formalización del problema: – Representación (eficiente) de estados: (,)

– – – – –

Estado inicial: (0,[6,2,5,25]) Estado meta: (x,y) tal que x es lo más cerca posible de 420 Operadores: aplicar la suma/multiplicación Coste de un operador: 0 Tipo de solución: estado

• Se puede resolver el problema con un método de búsqueda no informado usando como estado meta (420,y), pero ¿Que pasa si no hay ninguna solución exacta? • Mejor utilizar la búsqueda online: – Función heurística: h*((x,y))=|420-x| • mide la similitud del estado al objetivo, no mide el coste del camino restante

– Modificar los algoritmos: • se termina cuando el estado elegido como más prometedor tiene un valor de h* mayor que el estado actual –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: El juego de las cifras método base: búsqueda en profundidad limitada estado actual = (0,[6,2,5,25]) horizonte k = 2 (6,[2,5,25]) (8,[5,25]) (6+2)

(31,[2,5]) (6+25)

(11,[2,25]) (12,[5,25]) (6+5) (6*2) (150,[2,5]) (30,[2,25]) (6*25) (6*5)

(0,[6,2,5,25])

(2,[6,5,25])

(8,[5,25]) (2+6)

h*=420

(5,[6,2,25])

(27,[6,5]) (2+25)

(25,[6,2,5,25])

(11,[2,25]) (30,[6,2]) (5+6) (5+25)

(7,[6,25]) (12,[5,25]) (7,[6,25]) (30,[2,25]) (2+5) (2*6) (5+2) (5*6) (50,[6,5]) (10,[6,25]) (125,[6,2]) (10,[6,25]) (2*25) (2*5) (5*25) (5*2)

(31,[5,2]) (25+6)

(27,[6,5]) (25+2)

(30,[6,2]) (150,[5,2]) (25+5) (25*6) (50,[6,5]) (125,[6,2]) (25*2) (25*5)

h*=270 k=2

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: El juego de las cifras método base: búsqueda en profundidad limitada estado actual = (6,[2,5,25]) horizonte k = 2 (8,[5,25])

(31,[2,5])

(6,[2,5,25])

h*=414

(11,[2,25])

(12,[5,25])

(150,[2,5])

(30,[2,25])

(13,[25]) (8+5)

(36,[2]) (31+5)

(36,[2]) (11+25)

(37,[5]) (12+25)

(152,[5]) (150+2)

(55,[2]) (30+25)

(40,[25]) (8*5) (33,[5]) (8+25) (200,[5]) (8*25)

(155,[2]) (31*5) (33,[5]) (31+2) (62,[5]) (31*2)

(275,[2]) (11*25) (13,[25]) (11+2) (22,[25]) (11*2)

(300,[5]) (12*25) (17,[25]) (12+5) (60,[25]) (12*5)

(300,[5]) (150*2) (155,[2]) (150+5) (750,[2]) (150*5)

(750,[2]) (30*25) (32,[25]) (30+2) (60,[25]) (30*2)

h*=120 k=2 –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: El juego de las cifras método base: búsqueda en profundidad limitada estado actual = (12,[5,25]) horizonte k = 2 (37,[5])

(12,[5,25])

h*=408

(300,[5])

(17,[25])

(60,[25])

(185,[]) (37*5)

(1500,[]) (300*5)

(425,[]) (17*25)

(1500,[]) (60*25)

(42,[]) (37+5)

(305,[]) (300+5)

(42,[]) (17+25)

(85,[]) (60+25)

h*=5 k=2 –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: El juego de las cifras método base: búsqueda en profundidad limitada estado actual = (17,[25]) horizonte k = 2

(17,[25]) (42,[])

h*=403 ( 425,[])

h*=5

k=2 –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda con horizonte: El juego de las cifras método base: búsqueda en profundidad limitada estado actual = (425,[]) horizonte k = 2

(425,[])

k=2 –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejercicio 2.13 Búsqueda online para optimización: Juego de las cifras • La búsqueda online para optimización (parando cuando no se obtiene ninguna mejora) es muy útil en problemas de optimización con un número infinito de estados. • Aplica la búsqueda por ascenso de colinas a la siguiente instanciación del juego de las cifras: CIFRAS: 2, 3, 5, 7, 8 EXACTO: 163 • En este caso, se usan los operadores suma, resta, multiplicación y división. Solo se puede aplicar un operador si el resultado es entero positivo. Cada cifra se puede utilizar varias veces.

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Tema 2: Juegos unipersonales

Resumen: 2. Juegos unipersonales 2.1. Representación básica 2.2. Juegos con información completa 2.3. Recursos limitados en juegos con información completa 2.4. Juegos con información incompleta Búsqueda en tiempo real Búsqueda A* con aprendizaje en tiempo real

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Características de problemas con información incompleta • Entorno: – – – –

secuencial (acciones se efectúan de forma secuencial) discreto (número finito de acciones en cada estado) determinista (resultados de las acciones son estados definidos) accesible (se puede percibir el estado actual y comprobar si es estado meta)

• Agente: – Es capaz de percibir el estado en el que se encuentra – Conoce las acciones que puede aplicar en el estado actual • Pero no conoce los estados sucesores de un estado hasta que no ha probado las acciones correspondientes (no puede prever los estados resultantes de las aciones)

– Tiene un objetivo (estado meta) – Suposiciones: • Las acciones son deterministas (el resultado de una acción, aunque no es previsible, está claramente definido y no cambia) • El agente puede reconocer siempre un estado que ha visitado anteriormente –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Conocimientos mínimos a priori de un agente • Conocimientos mínimos a priori de un agente de búsqueda en el espacio de estados: – s0

Estado inicial

– acciones: s  {a1, ..., an}

Devuelve una lista de acciones permitidas en el estado s

– meta?: s  verdad | falso

Compara el estado s con los estados meta y devuelve verdad si s es un estado meta

– c: (si, a, sj )  v, v∈ℵ

Coste del operador a para ir de si a sj solo se puede aplicar si se conoce sj

(

)

n −1

(

c si1 si2  sin = ∑ c sik , ak , sik +1

)

Coste de un plan

k =1

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejemplo base: Laberinto Problema:

Instanciación: Estado inicial

• Estados:

S

– posición del agente en el laberinto

• Acciones: – el agente (A) se puede mover a una posición adyacente si no hay un obstáculo

A

• Coste: – La aplicación de cada operador vale una unidad

• Solución: – se busca un camino (más corto) a la salida (S)

Estado meta A S

• Suposición: – el agente no conoce el laberinto – es capaz de recordar estados visitados anteriormente –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda (en profundidad) en tiempo real Idea: • Realizar una búsqueda en profundidad creando un mapa del problema • Se crea sucesivamente el grafo del problema de búsqueda guardando el grafo en memoria • Si se llega a un estado que ya se ha llegado antes, se explora otros caminos no explorados • Si se llega a un estado en el que se han explorado todas las acciones se vuelve (físicamente) atrás

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en tiempo real Algoritmo: • G: es el grafo etiquetado y dirigido del problema que se genera al explorar el espacio; inicialmente vacío • ha: es una lista de los estados recorridos, necesario para realizar una vuelta atrás • añade(s,G): añade el nodo s al grafo G y añade sus acciones como arcos “abiertos” • conecta(sa,a,s,G): conecta el arco con etiqueta a del nodo sa al nodo s • sa y a: estado anterior y última acción • arc_ab[s]: lista de arcos “abiertos” de s • Primero(l): devuelve el primer elemento de una lista y lo quita de la lista • percibir(entorno) y realizar(a): percibe el estado actual y realizar la acción a

{búsqueda en profundidad en TR} sa=null Repetir s ← percibir(entorno) Si meta?(s) entonces devolver(parar) Si nuevo?(s) entonces añade(s,G) Si sa no es nulo entonces conecta(sa,a,s,G) añade sa al principio de ha Si vacio?(arc_ab[s]) entonces Si vacio?(ha) entonces devolver(parar) En caso contrario a ← acción que va de s a Primero(ha) sa ←nulo En caso contrario a ← Primero(arc_ab[s]) sa ←s entorno ← realizar(a) Fin {repetir} –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en tiempo real: Ejemplo Movimientos del agente S

S A

S

A

ar

grafo G S

de

ab A

A

iz

ar S A

A

ab

AS

S

ab

ha

A

S

ar

AS A

ab

A

iz S A

S

ar

vuelta atrás

S

A

A

ab

AS

S

ab ar S A

de

A

S A

S S

ar

iz

S

A

de

A

Orden de realizar los movimientos si hay varias posibilidades: - arriba, abajo, izquierda, derecha

S S

A S A –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en tiempo real: Ejemplo Movimientos del agente S

S A

S

A

ar

grafo G S

de

ab A

S

A

iz

ar S A

A

AS

S

ab

ab

A

S

ar

S

A

de

A

S

de

A ar

S

A

A

A

ar S A

A

ab ar

S A

ab S A

de

ar

S

A

ab ar

iz

S A

de

iz

A

S A

Orden de realizar los movimientos si hay varias posibilidades: - arriba, abajo, izquierda, derecha

S S

ar A

S

AS

S A

ab ar

A S

S A

AS

ab

iz S

ha

S S

A S A –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en tiempo real: Ejemplo S

Árbol expandido:

A S A S A S A

A AS

A

S

S A

S

• Exploración por profundidad • No se evitan ciclos • Tratamiento de estados repetidos: – si hay un estado repetido se realiza la acción que no se ha probado todavía – si no hay acciones sin probar vuelve atrás

S

S

A

A S A S A

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en tiempo real: Ejemplo Camino del agente el el laberinto: • los números en rojo indican el camino del agente

A

iz

S

de

A

ab 2 S A

ab 6

S

5 ar A

1 ab 7 ar 8 iz de 3 9

S A

AS

S

S

12 ar S A

4 ar A

ab

ab iz

11 ar S A

de 10

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en tiempo real: Analisis Complejidad: • • • •

n número de estados posibles; b factor de ramificación en espacio: espacio requerido para el grafo G y la lista ha – peor caso: (n-1)(b+1)+(n-1)b=2nb+n - 2b -1∈O(nb) en tiempo: número de movimientos del agente – peor caso: O(nb) en el peor caso b=n y la complejidad en tiempo y espacio podría ser

O(n2) • O(n2) puede ser un problema, especialmente respecto al espacio

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda en tiempo real: Analisis Completitud: •

es completo: en espacios finitos y si de todos los nodos a que se puede llegar existe un camino al nodo meta

Optimalidad: • •

No es óptimo Índice competitivo del agente (coste camino real/coste camino óptimo) – puede ser infinito si hay acciones irreversibles o el espacio es infinito – puede ser arbitrariamente largo si todas las acciones son reversibles y el espacio es limitado

•

Ningún algoritmo puede evitar callejones sin salida en todos los espacios de estados

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejercicio 2.14 Búsqueda en profundidad en tiempo real: Considera el laberinto dibujado abajo. A es el agente cuyo objetivo es llegar a S. M es un monstruo que come el agente si llega a el. a) Realiza la búsqueda por profundidad en tiempo real. Si en un estado hay varios acciones sin explorar, elige las acciones en el siguiente orden: izquierda, arriba, derecha, abajo. Dibuja el grafo que genera el agente e indica sus movimientos. b) Realiza la búsqueda por profundidad en tiempo real. Si en un estado hay varios acciones sin explorar, elige las acciones en el siguiente orden: derecha, arriba, izquierda, abajo. Dibuja el grafo que genera el agente e indica sus movimientos. c) Suponiendo un coste de cada movimiento de 1, calcula el índice competitivo del agente para ambos casos y compáralos.

M

S

A

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda A* con aprendizaje en tiempo real Problema: • La búsqueda en profundidad en tiempo real es esencialmente ciega: – El agente intenta caminos al azar y evita caminos ya explorados • Se podría utilizar funciones heurísticas: – para explorar las acciones más prometedoras primero – Pero, ¿Qué heurística se puede usar si no se conoce mucho del problema?

Idea: generar información heurística “sobre la marcha” • Crear el mapa del problema y aprender al mismo tiempo los valores de h* para cada estado (y durante varias búsquedas sucesivas) • Inicialmente, se inicializa h*(s) = 0 para todos los nodos s • Después de realizar una acción en el estado sa se actualiza h*(sa) al coste mínimo para ir de sa al estado meta, según lo que se sabe en este momento • Estando en un estado s, se elige aquella acción permitida b que lleva a un estado s’ tal que h*(s’)+c(s,b,s’) es mínimo –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda A* con aprendizaje en tiempo real Algoritmo: • G: es el grafo etiquetado y dirigido del problema que se genera al explorar el espacio; inicialmente vacío; contiene un valor h* para cada nodo • añade(s,G): añade el nodo s al grafo G y añade sus acciones como arcos “abiertos”; inicializa h*(s) a 0 • conecta(sa,a,s,G): conecta el arco con etiqueta a del nodo sa al nodo s • sa y a: estado anterior y última acción; son variables globales • estado[s,b]: estado al que se llega del estado s con la acción b (puede ser no definido) • funcion costo (s,s’,b): {calcula el coste estimado para ir de s al nodo meta más cercano a través de s’ } Si nodefinido?(s’) entonces devolver 0 en otro caso devolver c(s,b,s’)+H[s’]

{búsqueda con aprendizaje en TR} sa=null Repetir s ← percibir(entorno) Si nuevo?(s) entonces añade(s,G) Si sa no es nulo entonces conecta(sa,a,s,G) h*[sa] ←

min

b∈acciones(s a )

(costo(sa , estado[s a ,b], b))

Si meta?(s) entonces devolver(parar) a ← acción b de acciones(s) que minimiza costo(s,estado[s,b],b) entorno ← realizar(a) sa ←s Fin {repetir} –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Coste estimado mínimo para ir de un estado a la meta Elegir acción desde s: Actualizar h* de s:

Caso 1: (s tiene acciones sin explorar) coste=?

coste=6

s4

h*=1

h*=2

coste=7

s coste=3

coste=3

s3

s1

Caso 2: (s ha explorado todas las acciones)

s2

h*=3

s3

coste=? coste=3

s3

h*=3

h*=1

s coste=3

s2

h*=3

h*(s)←0 coste=6

coste=6

coste=3 h*=2

s1

h*=2

h*(s)←5

s1

s4

h*=1

h*=2

coste=7

s coste=3

s2

coste=3

s3

h*=2

coste mínimo esperado =0

h*=3

coste=6

s1

h*=1

s coste=3

s2

h*=2

coste mínimo esperado=5 –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda A* con aprendizaje en tiempo real: Ejemplo Movimientos del agente S

S A

ar e=0 S

A

S

A

ab A e=0

A

ab e=0

S

de e=0 AS

S

ab e=0

grafo G

iz0 0

AS

A

ar e=0 A

ab

S

ar e=0

iz e=0

ar

01 S

A

A

ab

S

00 1

ab

S A

ar S

• Orden de realizar los movimientos si hay varias posibilidades: - arriba, abajo, izquierda, derecha • e es el costo estimado de la acción para ir a la meta

A

001

de

ar

iz

S A

00 0

de

• en rojo los valores de h* • el coste de cada acción es 1 –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda A* con aprendizaje en tiempo real: Ejemplo Movimientos del agente S

S A

ar e=0 S

A

S

A

ab A e=0

A

de e=0

ab e=0

ab e=0

S

AS

S

grafo G

iz0 0

ar e=0 A

S

A

de e=1

ar

01

ar e=0

S

A

A

ab S A

S

de e=0

A ar

e=0

0

ab

ab

iz e=0 S

S A

AS

12 movimientos

A

S A

S

ar S A

00 1

00

ab

ab

S A

ar e=0

ar S

• Orden de realizar los movimientos si hay varias posibilidades: - arriba, abajo, izquierda, derecha • e es el costo estimado de la acción para ir a la meta

A

001 1

de

ar

iz

S A

00 01

de

iz

ar S A

00

• en rojo los valores de h* • el coste de cada acción es 1 –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda A* con aprendizaje en tiempo real: Analisis Aprendizaje de h*: • los valores de h* aprendidos sirven para nuevas instanciaciones del problema: – el estado meta tiene que ser el mismo – el estado inicial puede ser distinto

•

después de un número suficiente de búsquedas sucesivas con el mismo estado meta, h* converge a h – se convierte en una estimación exacta del coste de un nodo a la meta

Problemas: • En situaciones donde el estado meta puede cambiar, los valores de h* aprendidos no sirven para nuevas búsquedas

–2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Nueva búsqueda (con h* aprendido; mismo estado meta /otro estado inicial) Movimientos del agente S

A

AS

AS

iz e=0

de e=0

A

grafo G

S

02

ar e=1

A

de

S

S

ab e=2

de e=1

A

A iz

iz A e=2 ar

A

e=0

e=2 S A

S

S

ar e=1

A de

e=2

S

S

de A e=3

A

ab e=3

A ar

e=2

ar S

A

A

ab

S A

1 12

011

ab

ab

S A

S A

ar e=1

S

ar

A

ar S A

ab

ab

13

ab e=0 S

0

S

S

S

S A

AS

S

ab e=2 A

iz0 1 2

123

de

S A

1 12 2

• Condiciones: igual que antes (sólo cambia el estado inicial) –2–

ar

iz

de

iz

ar S A

01 12 16 movimientos Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Nueva búsqueda (con h* aprendido; mismo estado meta / estado inicial que antes) Movimientos del agente S

A

AS

AS

iz e=3

de e=4

A

grafo G

S

24

ar e=3

A

de

S

S

ab e=3

A

S

de e=3

A ar

S A

e=2

S A

AS

S

ab e=4 A

iz2 3 4

0

ab

ab

S A

ar e=1

ar

3 S

A

A

ab

ar S A

de

11

ab

ar

iz

S A

23

S A

233

ab

8 movimientos

3

S

ar

de

iz

ar S A

22

• Condiciones: igual que antes –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Nueva búsqueda ( búsqueda inicial con h* aprendido) Movimientos del agente S

S A

S

A

ar e=4

ab A e=5 S A

ab e=1

S

de e=4 S A

grafo G

4 A

A

iz4

S

de e=3

de

S A

AS

0

ab

ab

S

ar e=2

A

6 movimientos (comparado con los 12 de la primera búsqueda)

ar

35 S

A

A

ab

S

S A

3 44

de

11

ab

ar

iz

S A

33

S A

3

ab

ar

ar

de

iz

ar S A

22

• Condiciones: igual que antes –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Búsqueda A* con aprendizaje en tiempo real: Analisis Complejidad: •

espacio: la misma que en la búsqueda en profundidad en tiempo real: O(n•b)

(para guardar el grafo) •

tiempo: – –

inicialmente igual que en la búsqueda en profundidad en tiempo real: O(n2) (peor caso) mejora con el tiempo al ser la función heurística h* cada vez más exacta

Completitud: •

es completo: en espacios finitos y si de todos los nodos a que se puede llegar existe un camino al nodo meta

Optimalidad: • •

No se es óptimo Se convierte en óptimo, cuando h*(n)=h(n) para todos los nodos n

Problemas: • •

Los requerimientos de espacio son importantes, especialmente para problemas con un número grande de estados distintos Ejemplo: el 8-Puzzle tiene 9!/2=181440 estados (15-Puzzle: 1013estados) –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

Ejercicio 2.15 Búsqueda A* con aprendizaje en tiempo real: Imagínate el siguiente escenario. Un agente tiene que realizar una carrera de la ciudad A a la ciudad B (ver mapa de carreteras con ciudades y kilómetros). La peculiaridad de la carrera consiste en que el agente no conoce el mapa. Una vez que el agente llega a una ciudad, se le dice el nombre de esta ciudad, las carreteras que salen y la longitud de la carretera que acaba de recorrer. 55 G O

a) Aplique el algoritmo de búsqueda A* con Z 71 aprendizaje en tiempo real a este problema. Si 75 151 no hay ningun criterio mejor, el agente prefiere A S carreteras que van al norte y luego 99 140 F sucesivamente los que van al este, sur y oeste. 118 80 R b) Repite la misma búsqueda con los valores de la T 97 211 función heuristica aprendido anteriormente. 181 P c) Que cambiaría si, al llegar a una ciudad nueva, 101 146 no sólo se le dice al agente las carreteras que M salen, sino también los kilómetros que hay 138 75 hasta la siguiente ciudad para cada una de estas 120 D C carreteras (pero no a que ciudades se llegan). –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf

B

Ejercicio 2.16 Aprendizaje de la función heurística en problemas con información completa: El mecanismo de aprendizaje puede aplicarse igual si se conoce el grafo de antemano (problemas con información completa). De hecho, una vez que se haya obtenido el grafo completo, se hace eso. Además, en vez de inicializar los valores de la función heurística a 0, se puede utilizar como valores iniciales los de una función heurística conocida. a) Implemente el algoritmo de aprendizaje para el 8-puzzle. Para inicializar los valores de la función heurística para cada estado utiliza la función hc*. b) Genere 100 estados iniciales aleatorios y busque una solución con el algoritmo implementado, y aprendiendo (mejorando) la función heurística a lo largo de estas 100 búsquedas. Utilice como estado meta el estado meta utilizado en los ejemplos. c) Genera un gráfico que indica el número de movimientos realizados en cada búsqueda en función del número de búsquedas realizados anteriormente. Comenta este gráfico. –2–

Fundamentos de Inteligencia Artificial 3º Ing. Sup. Inf