PDF de programación - Tema 2 - Búsquedas - Inteligencia Artificial

g

Inteligencia
Artificial

Tema 2
Búsquedas

q

Ivan Olmos Pineda

Contenido

Estructura General de un PSA
Formulación de un PSA
Algoritmos de Búsqueda de Soluciones
Aplicaciones

BUAP

Inteligencia Artificial

2

1

Introducción

Agentes

Como actúan para alcanzar la meta
Como actúan para alcanzar la meta

Secuencia de acciones para alcanzarla
Agentes para la solución de problemas

Problema, se define como:

Una meta
Conjunto de medios que permiten alcanzarla

Búsqueda

Procedimiento de exploración para determinar que es lo

que se puede obtener

BUAP

Inteligencia Artificial

Introducción

Formulación de metas

j

t d

d l

U

Una meta es un conjunto de estados del mundo
d
A través de las acciones, un agente pasa de un

t d

t

estado a otro

Acciones

Causantes de la transición de un estado a otro
El agente tiene que determinar que acciones

permiten obtener el estado de la meta

BUAP

Inteligencia Artificial

3

4

2

Formulación de un Problema

Proceso que consiste en decidir que

acciones y estados habrán de considerarse
acciones y estados habrán de considerarse

¿Qué condiciones son necesarias?

¿Qué sucede si no hay forma de discernir que

camino nos lleva a la meta?

¿Qué decisión tomar en tal situación?

BUAP

Inteligencia Artificial

5

Búsquedas

En términos generales, cuando un agente
tiene ante si diversas opciones cuyo valor
tiene ante si diversas opciones cuyo valor
ignora, éstas se tienen que evaluar de alguna
forma
Evaluar las diversas secuencias de acciones que

le conducen a estados cuyo valor se conoce

Búsquedas

BUAP

Inteligencia Artificial

6

3

Búsquedas

Algoritmo de búsqueda

bl

E t d

Entrada: un problema
Salida: solución que adopta la forma de una

secuencia de acciones

Una vez encontrada una solución, se

procede a ejecutar las acciones

BUAP

Inteligencia Artificial

Búsquedas

BUAP

Inteligencia Artificial

7

8

4

Agentes que Resuelven Problemas

Formular: decidir que acciones y estados
Formular: decidir que acciones y estados
deberán considerarse

Buscar: proceso para hallar las secuencias

de acciones que conduzcan a una meta

Ejecutar: fase donde se llevan a cabo las

acciones que conducen a la meta

BUAP

Inteligencia Artificial

9

Agentes que Resuelven Problemas

función AGENTE-SENCILLO-RESOLVENTE-PROBLEMAS(percepción) devuelve una acción

entradas: percepción, una percepción
estático: sec, una secuencia de acciones, vacía inicialmente

estado, una descripción del estado actual del mundo
objetivo, un objetivo inicialmente nulo
problema, una formulación del problema

estado ← ACTUALIZAR-ESTADO(estado, percepción)
si sec está vacía entonces hacer

objetivo ← FORMULAR OBJETIVO(estado)
problema ← FORMULAR-PROBLEMA(estado, objetivo)
sec ← BÚSQUEDA(problema)
)
acción ← PRIMERO(secuencia)
sec ← RESTO(secuencia)

(p

devolver acción

BUAP

Inteligencia Artificial

10

5

Ejemplo

Imagine un agente en la ciudad de Arad, Rumanía,
disfrutando de un viaje de vacaciones. Mañana sale
a a a sa e
d s uta do de u
un vuelo a Bucarest.

aje de acac o es

Formulación del objetivo:

estar en Bucarest

Formulación del problema:

estados: varias ciudades
acciones: conducir entre las ciudades

i d d

t

i

d i
Encontrar solución:

l

secuencia de ciudades, por ejemplo, Arad, Sibiu,
Fagaras, Bucarest.

BUAP

Inteligencia Artificial

11

Ejemplo

BUAP

Inteligencia Artificial

12

6

Ejemplo de una Aspiradora

Estado simple, estado inicial 5. ¿Solución?

BUAP

Inteligencia Artificial

13

Ejemplo de una Aspiradora

Estado simple, estado inicial 5. ¿Solución?
[Derecha, Aspirar]

Estado múltiple, estado inicial
{1, 2, 3, 4, 5, 6, 7, 8}
Por ejemplo, Derecha produce {2, 4, 6, 8}.
¿Solución?

BUAP

Inteligencia Artificial

14

7

Ejemplo de una Aspiradora

Estado simple, estado inicial 5. ¿Solución?
[Derecha, Aspirar]

Conformado, estado inicial
{1, 2, 3, 4, 5, 6, 7, 8}
Por ejemplo, Derecha produce {2, 4, 6, 8}.
¿Solución?
[Derecha, Aspirar, Izquierda, Aspirar]

Contingencia, estado inicial 5.
Ley de Murphy: Aspirar a veces deposita
suciedad en la alfombra.
Sensores locales: suciedad,
sólo en el lugar.
¿Solución?

BUAP

Inteligencia Artificial

15

Ejemplo de una Aspiradora

Estado simple, estado inicial 5. ¿Solución?
[Derecha, Aspirar]
Conformado estado inicial
Conformado, estado inicial
{1, 2, 3, 4, 5, 6, 7, 8}
Por ejemplo, Derecha produce {2, 4, 6, 8}.
¿Solución?
[Derecha, Aspirar, Izquierda, Aspirar]
Contingencia, estado inicial 5.
Ley de Murphy: Aspirar a veces deposita
suciedad en la alfombra
suciedad en la alfombra.
Sensores locales: suciedad,
sólo en el lugar.
¿Solución?
[Derecha, si suciedad entonces Aspirar]

BUAP

Inteligencia Artificial

16

8

Problemas Bien Definidos

Un problema se define por cuatro elementos:
estado inicial por ejemplo, “Estoy en Arad”
función sucesor S(x) = conjunto de pares acción-estado

por ejemplo, S(Arad) = {<Arad → Zerind, Zerind>,...}

Prueba de meta, descripción para decidir si se trata de un edo meta

explícito, por ejemplo, x = “en Bucarest”
implícito, por ejemplo, en ajedrez, el estado jaque mate

costo del camino, se asignan costos a una ruta

por ejemplo suma de distancias número de acciones
por ejemplo, suma de distancias, número de acciones
ejecutadas, etc.

Una solución es una secuencia de acciones que parten desde un

estado inicial hasta alcanzar un estado objetivo.

BUAP

Inteligencia Artificial

17

Costos

Mediante una ruta se conectan los conjuntos de

estados
estados
La solución es una ruta que conduce a estados meta

Espacio de conjunto de estados

¿cuál es el mejor camino?

¿Permite encontrar una solución? (decisión)
¿Es una buena solución? (optimización)
¿Cuál es el costo de búsqueda correspondiente al tiempo y

memoria necesarios para encontrar la solución?

BUAP

Inteligencia Artificial

18

9

Costos

Costo total

C.T. = Costo del Camino + Costo de la Búsqueda

BUAP

Inteligencia Artificial

19

Ejemplo: Espacio de Estados Aspiradora

¿Estados?
¿Acciones?
¿Prueba de meta?
¿Costo del camino?

BUAP

Inteligencia Artificial

20

10

Ejemplo: Espacio de Estados Aspiradora

¿Estados? Suciedad completa y localizaciones de robot (ignorar cantidades de suciedad)
¿Acciones? Izquierda, Derecha, Aspirar, NoOp
¿Prueba de meta? No suciedad
¿Costo del camino? 1 por acción (0 por NoOp)

BUAP

Inteligencia Artificial

21

Ejemplo: el 8-puzzle

E d ?
¿Estados?
¿Acciones?
¿Prueba de meta?
¿Costo del camino?

BUAP

Inteligencia Artificial

22

11

Ejemplo: el 8-puzzle

li

i

l

t

d l

E t d ? L
)
¿Estados? Localizaciones completas de las piezas (ignorar las posiciones intermedias)
¿Acciones? Mover el negro a la izquierda, derecha, arriba, abajo (ignorar los atascos, etc.)
¿Prueba de meta? = estado objetivo (proporcionado)
¿Costo del camino? 1 por movimiento
[Nota: solución óptima de la familia del n-puzzle es NP-C]

di

i

i

i

t

i

(i

l

BUAP

Inteligencia Artificial

23

Búsquedas
Árboles
Idea general: Explorar las diferentes ramas de un

árbol con el objetivo de encontrar un camino desde
árbol, con el objetivo de encontrar un camino desde
la raíz a una hoja que represente un estado final

función BÚSQUEDA-ÁRBOLES(problema,estrategia) devuelve una solución o fallo

inicializa el árbol de búsqueda usando el estado inicial del problema
Hacer ciclo

si no hay candidatos para expandir entonces devolver fallo
escoger, de acuerdo a la estrategia, un nodo hoja para expandir
si el nodo contiene un estado objetivo entonces devolver la correspondiente solución
en otro caso expandir el nodo y añadir los nodos resultado al árbol de búsqueda

BUAP

Inteligencia Artificial

24

12

Búsquedas en Árboles

Búsqueda a lo ancho

Búsqueda en Profundidad primero

Búsqueda ancho-profundo

Búsqueda en profundidad limitada

BUAP

Inteligencia Artificial

25

Búsqueda primero en anchura

Se expande primero el nodo raíz, a continuación, se expanden todos

los sucesores del nodo raíz, después sus sucesores, etc.


Implementación:

Usa una estructura FIFO, es decir, los nuevos sucesores van al

final.

BUAP

Inteligencia Artificial

26

13

Búsqueda primero en anchura

Se expande primero el nodo raíz, a continuación, se expanden todos

los sucesores del nodo raíz, después sus sucesores, etc.


Implementación:

Usa una estructura FIFO, es decir, los nuevos sucesores van al

final.

BUAP

Inteligencia Artificial

27

Búsqueda primero en anchura

Se expande primero el nodo raíz, a continuación, se expanden todos

los sucesores del nodo raíz, después sus sucesores, etc.


Implementación:

Usa una estructura FIFO, es decir, los nuevos sucesores van al

final.

BUAP

Inteligencia Artificial

28

14

Búsqueda primero en anchura

Se expande primero el nodo raíz, a continuación, se expanden todos

los sucesores del nodo raíz, después sus sucesores, etc.


Implementación:

Usa una estructura FIFO, es decir, los nuevos sucesores van al

final.

BUAP

Inteligencia Artificial

29

Propiedades de la búsqueda primero en
anchura
¿Completa? Sí

t

d

b f
b: factor de ramificación.
d: profundidad de solución.

ió

ifi

¿Tiempo? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1)

¿Espacio? O(bd+1) (mantiene todos los nodos

en la memoria)

BUAP

Inteligencia Artificial

30

15

Búsqueda primero en profundidad

Se expande el nodo no expandido más profundo.
Implementación: