PDF de programación - Búsqueda en Inteligencia Artificial

Búsqueda en Inteligencia Artificial
Búsqueda en Inteligencia Artificial
© Fernando Berzal, [email protected]
© Fernando Berzal,
[email protected]

Búsqueda en I.A.
Búsqueda en I.A.

Introducción
 Introducción
 Espacios de búsqueda
Espacios de búsqueda
Agentes de búsqueda
 Agentes de búsqueda
Uso de información en el proceso de búsqueda
 Uso de información en el proceso de búsqueda
 Búsqueda sin información (a ciegas)
 Búsqueda sin información (a ciegas)
Búsqueda sin información (a ciegas)
Búsqueda sin información (a ciegas)
 Búsqueda con información (heurística)
Búsqueda con información (heurística)
 Estrategias de control
Estrategias de control
Estrategias irrevocables
 Estrategias irrevocables
 Estrategias tentativas
Estrategias tentativas
Características de los problemas de búsqueda
 Características de los problemas de búsqueda
 Problemas “
ignorables” (monótonos y reversibles)
” (monótonos y reversibles)
 Problemas “no
 Caso práctico: Búsqueda en juegos con adversario
Caso práctico: Búsqueda en juegos con adversario

Problemas “ignorables
Problemas “no ignorables

ignorables” o irrecuperables
” o irrecuperables

11

Introducción
Introducción

Problemas NP--difíciles
Problemas NP
difíciles

Definición informal:
Definición informal:

Problemas que, para resolverlos de forma exacta,
Problemas que, para resolverlos de forma exacta,
requieren
requieren la realización de una búsqueda en un
requieren
requieren la realización de una búsqueda en un
la realización de una búsqueda en un
la realización de una búsqueda en un
espacio que es de tamaño exponencial.
espacio que es de tamaño exponencial.

 Nadie sabe como evitar esa búsqueda.
Nadie sabe como evitar esa búsqueda.

 No se espera que nadie lo consiga nunca…
No se espera que nadie lo consiga nunca…

Introducción
Introducción

Problemas NP--difíciles
Problemas NP
difíciles

 Si un problema es NP

Todos los problemas de los que se ocupa la I.A. son
 Todos los problemas de los que se ocupa la I.A. son
NPNP--difíciles (si existe un algoritmo rápido para un
difíciles (si existe un algoritmo rápido para un
problema, difícilmente consideraremos que el
problema, difícilmente consideraremos que el
problema, difícilmente consideraremos que el
problema, difícilmente consideraremos que el
problema requiere inteligencia).
problema requiere inteligencia).
Si un problema es NP--difícil y tenemos un algoritmo
difícil y tenemos un algoritmo
que encuentra la solución de forma rápida y casi
que encuentra la solución de forma rápida y casi
siempre correcta, podemos considerar que el
siempre correcta, podemos considerar que el
algoritmo es “inteligente”.
algoritmo es “inteligente”.
 La I.A. implica que la búsqueda está sujeta a errores.
La I.A. implica que la búsqueda está sujeta a errores.

22

33

Introducción
Introducción

Problema
Problema típico

típico en I.A.
en I.A.

Descripción

inicial

del sistema

¿?

Descripción

final

del sistema

Estado 1

Estado 2

…

Estado n

representa la aplicación de algún operador
representa la aplicación de algún operador
o transformación del sistema.
o transformación del sistema.

¿Cómo se selecciona, en cada momento,
¿Cómo se selecciona, en cada momento,
el operador que se debería aplicar?
el operador que se debería aplicar?

44

Introducción
Introducción

Ejemplo: : Ajedrez
Ejemplo
Ajedrez

¿?

Mate del tonto

 Se dispone de varios operadores (movimientos legales).
Se dispone de varios operadores (movimientos legales).
Se ha de elegir cuál es el más adecuado en cada
 Se ha de elegir cuál es el más adecuado en cada
momento (¿qué pieza movemos y a dónde?).
momento (¿qué pieza movemos y a dónde?).
 No tiene sentido aplicar (ejecutar) el primer operador
No tiene sentido aplicar (ejecutar) el primer operador
que sea válido, sino que se debe realizar un proceso
que sea válido, sino que se debe realizar un proceso
previo de
previo de búsqueda
búsqueda del mejor operador, tras lo cual
del mejor operador, tras lo cual
se procederá a su aplicación.
se procederá a su aplicación.

55

Espacios de de búsqueda
Espacios
búsqueda

 La búsqueda la realiza un programa (o agente).
La búsqueda la realiza un programa (o agente).

El espacio de búsqueda será un grafo dirigido en el
 El espacio de búsqueda será un grafo dirigido en el
que cada nodo representa un posible estado del
que cada nodo representa un posible estado del
que cada nodo representa un posible estado del
que cada nodo representa un posible estado del
sistema.
sistema.

NNOTAOTA: Dependiendo del problema, cada nodo
: Dependiendo del problema, cada nodo
incluirá una descripción completa del sistema,
incluirá una descripción completa del sistema,
o bien sólo las modificaciones necesarias para
o bien sólo las modificaciones necesarias para
pasar de un nodo padre a su hijo.
pasar de un nodo padre a su hijo.

66

Espacios de búsqueda
Espacios de búsqueda

Búsqueda en un espacio de estados
Búsqueda en un espacio de estados

 Espacio de estados
Espacio de estados::

Representación del problema a través de las (posibles)
Representación del problema a través de las (posibles)
acciones del agente.
acciones del agente.
acciones del agente.
acciones del agente.

 Búsqueda en el espacio de estados

Búsqueda en el espacio de estados: :

Resolución del problema mediante la proyección de las
Resolución del problema mediante la proyección de las
distintas acciones del agente.
distintas acciones del agente.

77

Espacios de búsqueda
Espacios de búsqueda

Posibles acciones del agente (operadores)
Posibles acciones del agente (operadores)

Espacios de búsqueda
Espacios de búsqueda

Búsqueda en un espacio de estados
Búsqueda en un espacio de estados
Grafo implícito
Grafo implícito

Grafo teórico que representa todas las posibles
 Grafo teórico que representa todas las posibles
transformaciones del sistema aplicando todos los
transformaciones del sistema aplicando todos los
transformaciones del sistema aplicando todos los
transformaciones del sistema aplicando todos los
operadores posibles recursivamente.
operadores posibles recursivamente.

 Debido a su complejidad exponencial, que requeriría
Debido a su complejidad exponencial, que requeriría
una cantidad inviable de memoria y tiempo, el grafo
una cantidad inviable de memoria y tiempo, el grafo
implícito no puede generarse por completo.
implícito no puede generarse por completo.

88

99

Espacios de búsqueda
Espacios de búsqueda

Espacios de búsqueda
Espacios de búsqueda

Búsqueda en un espacio de estados
Búsqueda en un espacio de estados
Grafo explícito
Grafo explícito

Debido a la complejidad exponencial del grafo
 Debido a la complejidad exponencial del grafo
implícito, se irá generando, paso a paso, una porción
implícito, se irá generando, paso a paso, una porción
implícito, se irá generando, paso a paso, una porción
implícito, se irá generando, paso a paso, una porción
del grafo conforme avance el proceso de búsqueda.
del grafo conforme avance el proceso de búsqueda.

 El El grafo explícito

grafo explícito es el

es el subgrafo

subgrafo del grafo implícito
del grafo implícito

que se va generando durante el proceso de búsqueda
que se va generando durante el proceso de búsqueda
de una secuencia de operadores que resuelva nuestro
de una secuencia de operadores que resuelva nuestro
problema (camino solución) .
problema (camino solución) .

1010

1111

Espacios de búsqueda
Espacios de búsqueda

Espacios de búsqueda
Espacios de búsqueda

Búsqueda en un espacio de estados
Búsqueda en un espacio de estados
Grafo explícito
Grafo explícito

Condiciones de parada
Condiciones de parada

 Se ha encontrado la solución.
Se ha encontrado la solución.

 Se ha acabado el tiempo disponible.
Se ha acabado el tiempo disponible.

 Se ha llegado a un nivel de profundidad determinado.
Se ha llegado a un nivel de profundidad determinado.

1212

1313

Espacios de búsqueda
Espacios de búsqueda

Ejemplo: 8--puzzle
Ejemplo: 8
puzzle

2

1

7
7

8

6

3

4

5
5

1

8

7
7

2

6
6

3

4

5
5

En el problema del 8--puzzle hay que encontrar
En el problema del 8
puzzle hay que encontrar

un camino desde la configuración inicial
un camino desde la configuración inicial
hasta una determinada configuración final.
hasta una determinada configuración final.

Espacios de búsqueda
Espacios de búsqueda

Ejemplo: 8--puzzle
Ejemplo: 8
puzzle

2

1

7

2

1

7

2

1

7

8

6

8

6

8

6

3

4

5

3

4

5

3

4

5

2

1

7

2

1

7

8

6

5

8

4

6

3

4

3

5

2

1

2

7

8

6

7

8

1

6

3

4

5

3

4

5

2

8

6

2

8

6

2

6

3

4

5

3

4

5

3

4

5

1

7

1

7

1

8

7

1414

2

1

7

3

8

6

4

5

1

7

2

8

6

3

4

5

1515

Espacios de búsqueda
Espacios de búsqueda

Ejercicio: Problema del mono y los plátanos
Ejercicio: Problema del mono y los plátanos

Un mono está en la puerta de una habitación. En el
Un mono está en la puerta de una habitación. En el
centro de la habitación hay un plátano colgado del
centro de la habitación hay un plátano colgado del
techo, pero no puede alcanzarle desde el suelo. En la
techo, pero no puede alcanzarle desde el suelo. En la
ventana de la habitación hay una caja, que el mono
ventana de la habitación hay una caja, que el mono
ventana de la habitación hay una caja, que el mono
ventana de la habitación hay una caja, que el mono
puede mover y a la que puede encaramarse para
puede mover y a la que puede encaramarse para
alcanzar el plátano. El mono puede realizar las
alcanzar el plátano. El mono puede realizar las
siguientes acciones: desplazarse de la puerta al
siguientes acciones: desplazarse de la puerta al
centro, del centro a la ventana y viceversa; empujar la
centro, del centro a la ventana y viceversa; empujar la
caja a la vez que se desplaza; subirse y bajarse de la
caja a la vez que se desplaza; subirse y bajarse de la
caja; coger el plátano.
caja; coger el plátano.

El probl