1

InteligenciagArtificial

Tema 2Búsquedasq

Ivan Olmos Pineda

Contenido

Estructura General de un PSAFormulación de un PSAAlgoritmos de Búsqueda de SolucionesAplicaciones

BUAP Inteligencia Artificial 2

2

Introducción

AgentesComo actúan para alcanzar la metaComo actúan para alcanzar la meta

Secuencia de acciones para alcanzarlaAgentes para la solución de problemas

Problema, se define como:Una metaConjunto de medios que permiten alcanzarla

BUAP Inteligencia Artificial 3

BúsquedaProcedimiento de exploración para determinar que es lo que se puede obtener

Introducción

Formulación de metasU t j t d t d d l dUna meta es un conjunto de estados del mundoA través de las acciones, un agente pasa de un estado a otro

Acciones

BUAP Inteligencia Artificial 4

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

permiten obtener el estado de la meta

3

Formulación de un Problema

Proceso que consiste en decidir que acciones y estados habrán de considerarseacciones 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?

BUAP Inteligencia Artificial 5

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

Búsquedas

En términos generales, cuando un agente tiene ante si diversas opciones cuyo valortiene 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

BUAP Inteligencia Artificial 6

Búsquedas

4

Búsquedas

Algoritmo de búsquedaE t d blEntrada: un problemaSalida: solución que adopta la forma de una secuencia de acciones

Una vez encontrada una solución, se

BUAP Inteligencia Artificial 7

procede a ejecutar las acciones

Búsquedas

BUAP Inteligencia Artificial 8

5

Agentes que Resuelven Problemas

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

Buscar: proceso para hallar las secuencias de acciones que conduzcan a una meta

BUAP Inteligencia Artificial 9

Ejecutar: fase donde se llevan a cabo las acciones que conducen a la meta

Agentes que Resuelven Problemasfunció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)

BUAP Inteligencia Artificial 10

(p )

acción ← PRIMERO(secuencia)

sec ← RESTO(secuencia)

devolver acción

6

Ejemplo

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

Formulación del objetivo:estar en BucarestFormulación del problema:estados: varias ciudades

i d i t l i d d

BUAP Inteligencia Artificial 11

acciones: conducir entre las ciudadesEncontrar solución:secuencia de ciudades, por ejemplo, Arad, Sibiu, Fagaras, Bucarest.

Ejemplo

BUAP Inteligencia Artificial 12

7

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

8

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 depositasuciedad en la alfombra.

BUAP Inteligencia Artificial 15

Sensores locales: suciedad,sólo en el lugar.¿Solución?

Ejemplo de una Aspiradora

Estado simple, estado inicial 5. ¿Solución?[Derecha, Aspirar]Conformado estado inicialConformado, 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 depositasuciedad en la alfombra

BUAP Inteligencia Artificial 16

suciedad en la alfombra.Sensores locales: suciedad,sólo en el lugar.¿Solución?[Derecha, si suciedad entonces Aspirar]

9

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 rutapor ejemplo suma de distancias número de acciones

BUAP Inteligencia Artificial 17

por ejemplo, suma de distancias, número de accionesejecutadas, etc.

Una solución es una secuencia de acciones que parten desde un estado inicial hasta alcanzar un estado objetivo.

Costos

Mediante una ruta se conectan los conjuntos de estadosestados

La solución es una ruta que conduce a estados metaEspacio de conjunto de estados

¿cuál es el mejor camino?¿Permite encontrar una solución? (decisión)¿Es una buena solución? (optimización)

BUAP Inteligencia Artificial 18

¿Cuál es el costo de búsqueda correspondiente al tiempo y memoria necesarios para encontrar la solución?

10

Costos

Costo total

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

BUAP Inteligencia Artificial 19

Ejemplo: Espacio de Estados Aspiradora

BUAP Inteligencia Artificial 20

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

11

Ejemplo: Espacio de Estados Aspiradora

BUAP Inteligencia Artificial 21

¿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)

Ejemplo: el 8-puzzle

E d ?

BUAP Inteligencia Artificial 22

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

12

Ejemplo: el 8-puzzle

E t d ? L li i l t d l i (i l i i i t di )

BUAP Inteligencia Artificial 23

¿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]

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

BUAP Inteligencia Artificial 24

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

13

Búsquedas en Árboles

Búsqueda a lo ancho

Búsqueda en Profundidad primero

Búsqueda ancho-profundo

BUAP Inteligencia Artificial 25

Búsqueda en profundidad limitada

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

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 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

15

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í b f t d ifi iób: factor de ramificación.d: profundidad de solución.

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

BUAP Inteligencia Artificial 30

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

16

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 31

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 32

17

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 33

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 34

18

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 35

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 36

19

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 37

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 38

20

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 39

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 40

21

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 41

Búsqueda primero en profundidad

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

Usa una estructura LIFO, es decir, los sucesores se ponen delante. Suponiendo M como nodo objetivo.

BUAP Inteligencia Artificial 42

22

Propiedades de la búsqueda primero en profundidad

¿Completa? SiCompleta en espacios finitos.

¿Tiempo? O(bm): terrible si m es mucho mayor que d.m: máxima profundidad.

Pero si las soluciones son densas, puede ser mucho más rápida que la búsqueda primero en anchura.

¿Espacio? O(bm) es decir espacio lineal

BUAP Inteligencia Artificial 43

¿Espacio? O(bm), es decir, espacio lineal.

Actividad

Implementar un programa que determine la ruta más corta entre un par de ciudadesruta más corta entre un par de ciudades

Entrada: Mapa (conjunto de ciudades, conjunto de carreteras que unen a ciudades, distancia entre las ciudades), Origen, DestinoSalida: Secuencia de ciudades a visitar (desde el origen hasta el destino). En caso de no existir un camino, reportarlo

BUAP Inteligencia Artificial 44

reportarlo.