Búsqueda Ciega 1

Solución de problemas por Búsqueda

Capítulo 3

Búsqueda Ciega 2

Reseña

Soluciones de problemas de agentes Tipos de problemas Formulación de problemas Problemas de ejemplo Algoritmos de búsqueda básicos

Búsqueda Ciega 3

Agente Resolvedor de Problemas

Búsqueda Ciega 4

Ejemplo: Rumania

Estado actual: en Arad Meta: en Bucarest Problema:

estados: Ciudades diversas acciones: Conducir entre ciudades

Solución: Secuencia de ciudades, e.g., Arad, Sibiu, Fagaras, Bucarest

Búsqueda Ciega 5

Ejemplo: Rumania

Búsqueda Ciega 6

Tipos de Problemas

Determinístico, completamente observable condición única del problema

El agente sabe exactamente en qué condición estará No-observable sin sensores El agente puede no tiene idea dónde está No deterministico y/o parcialmente observable problema

de contingencia Las percepciones proveen información nueva acerca

de la condición actual A menudo intercala búsqueda, ejecución Estado en el espacio desconocido Problema de

exploración

Búsqueda Ciega 7

Ejemplo: El mundo de aspiradora

Estado único, comienza en #5. Solución?

Búsqueda Ciega 8

Ejemplo: El mundo de aspiradora

Estado único, comienza en #5. Solución?[Derecho, Aspirar]

Sensorless, comienza sobre{ 1,2,3,4,5,6,7,8 } e.g., Derecho hacia { 2,4,6,8 }¿Solución?

Búsqueda Ciega 9

Ejemplo: El mundo de aspiradora

Sin Sensores, comienza sobre{ 1,2,3,4,5,6,7,8 } v.g., Derecho hacia { 2,4,6,8 }¿Solución?

Solución? [Derecho, Aspirar, Izquierdo, Aspirar]

Contingencia No determinístico: Aspirar puede

Ensuciar una alfombra limpia

Parcialmente observable: La posición, la suciedad en la posición actual.

Percepción: [L, Limpio], i.e., Empiece en #5 o #7¿Solución?

Búsqueda Ciega 10

Ejemplo: El mundo de aspiradora

Sin Sensores, comienza sobre{ 1,2,3,4,5,6,7,8 } v.g., Derecho hacia { 2,4,6,8 }¿Solución?

Solución? [Derecho, Aspirar, Izquierdo, Aspirar]

Contingencia No determinístico: Aspirar puede

Ensuciar una alfombra limpia

Parcialmente observable: La posición, la suciedad en la posición actual.

Percepción: [L, Limpio], i.e., Empiece en #5 o #7¿Solución? [Derecho, si esta sucio entonces aspirar]

Búsqueda Ciega 11

Formulación de estado único

Un problema está definido por cuatro cosas:

1. Estado Inicial v.g., “en Arad"2. Acciones o función sucesor S(x) = conjunto de pares acción-

estado v.g., S (Arad) = {<Arad Zerind, Zerind>, … }

3. Prueba de Meta explícitamente, v.g., x = "at Bucharest" implícitamente, v.g., Checkmate (x)

4. Costo solución (aditivo) v.g., La suma de distancias, número de acciones ejecutadas, etc.

C(x, a, y) es el costo por paso, C(x, a, y) ≥ 0

Una solución es una secuencia de acciones desde el estado inicial hasta un estado meta

Búsqueda Ciega 12

Espacio de Estado

El mundo real es absurdamente complejo espacio de estado abstracto

Estado (Abstracto) = conjunto de estados reales Acción (Abstracta) = combinación compleja de

acciones reales v.g., "Arad Zerind" Representa un conjunto de rutas

posibles, desvíos, áreas de descanso, etc. Una acción debe llevar de cualquier estado real "en Arad" a

algún estado real "en Zerind" Solución (Abstracta) = conjunto de caminos reales

que son soluciones en el mundo real Cada acción abstracta debería ser "más fácil" que el

problema original

Búsqueda Ciega 13

Espacio de Estado del mundo de aspiradora

estados? acciones? prueba final? costo del camino?

Búsqueda Ciega 14

Espacio de Estado del mundo de aspiradora

estados? La suciedad de entero y la posición automatizada

acciones? Derecho Izquierdo, Aspirar prueba final? Ninguna suciedad en todas las posiciones costo del camino? 1 por acción

Búsqueda Ciega 15

Ejemplo: El rompecabezas-8

estados? acciones? prueba final? costo del camino?

Búsqueda Ciega 16

Ejemplo: El rompecabezas-8

estados? Posiciones de las tejas acciones? Mover el espacio prueba final? = estado final (dado) costo del camino? 1 por movimiento

Búsqueda Ciega 17

Ejemplo: Ensamblaje robótico

estados? Coordenadas de valores reales automatizados de ángulos de juntura de las partes del objeto a ser ensambladas

acciones? Los movimientos continuos de articulaciones del robot

prueba final? Ensamblaje completo costo del camino? Tiempo a ejecutar

Búsqueda Ciega 18

Algoritmos de árbol de búsqueda

Idea básica: Fuera de línea, la exploración simulada del

espacio de estado genera sucesores de condiciones ya exploradas

(a.k.a.~ expandir estados)

Búsqueda Ciega 19

Ejemplo de árbol de búsqueda

Búsqueda Ciega 20

Ejemplo de árbol de búsqueda

Búsqueda Ciega 21

Ejemplo de árbol de búsqueda

Búsqueda Ciega 22

Implementación: árbol de búsqueda

Búsqueda Ciega 23

Implementación: estados vs. nodos

Estado = (representación de) configuración física Nodo = estructura de datos - incluye estado, nodo padre,

acción, costo del camino g(x), profundidad, etc.

La función Expand crea nodos nuevos, rellenando los campos diversos y usando al SuccessorFn del problema para crear los estados correspondientes.

Búsqueda Ciega 24

Estrategias de Búsqueda

Una estrategia de búsqueda define el orden de expansión de los nodos

Las estrategias son evaluadas en las siguientes dimensiones:

Seguridad: ¿Encuentra siempre una solución si existe? Complejidad en tiempo: Número de nodos generados Complejidad en espacio: Número máximo de nodos en

memoria Optimalidad: ¿Encuentra siempre la solución menos

costosa? La complejidad en tiempo y espacio son medidas en

términos de: b: El factor máximo de ramaje del árbol de búsqueda d: La profundidad de la solución menos costosa m: La profundidad máxima del espacio de estado

Búsqueda Ciega 25

Estrategias de Búsqueda Ciega

Usan sólo la información disponible en la definición del problema

A lo ancho De costo uniforme A lo profundo De profundidad limitada De profundidad iterada

Búsqueda Ciega 26

Búsqueda a lo ancho

Expándase el nodo menos hondo no expandido

Implementación: La orilla es una cola, i.e., Los sucesores

nuevos van al final

Búsqueda Ciega 27

Propiedades de búsqueda a lo ancho

Completa? Sí (si b es finito) Tiempo? 1+b+b2+b3+… +bd + b(bd-1) =

O(bd+1) Espacio? O(bd+1) (Guarda cada nodo en

memoria) Optima? Sí (si cost = 1 por paso)

El espacio es el problema

Búsqueda Ciega 28

Búsqueda de costo uniforme

Expandir el nodo no expandido de menor costo Implementación: Orilla = cola ordenada por costo del camino El equivalente a búsqueda primaria a lo ancho si los

pasos cuestan igual Completo? Sí, si el paso cost ≥ ε ¿Tiempo? # nodos con g ≤ costo de solución óptima

O(bC*/ ε) donde C * es el costo de la solución óptima

¿Espacio? # de nodos con g ≤ costo de solución óptima, O(bC*/ ε)

¿Óptimo? Sí – nodos expandidos en orden creciente de g(n)

Búsqueda Ciega 29

Búsqueda a lo profundo

Expanda más profundo nodo no expandido Implementación: Orilla = Cola LIFO, i.e., Poner los sucesores en frente

Búsqueda Ciega 30

Propiedades de Búsqueda a lo profundo

¿Completa? No. Falla en espacios de profundidad infinita, espacios con ciclos. Modificar para evitar repetir estados a lo largo del

camino Completo en espacios finitos

¿Tiempo? O(bm): terrible si m es mucho mas grande que d Pero si las soluciones son densas, puede ser

mucho más rápido que búsqueda a lo ancho ¿Espacio? O(bm) - espacio lineal! ¿Optima? No

Búsqueda Ciega 31

Busqueda de profundidad limitada

= Búsqueda a lo profundo parando a cierta profundidad limitada - nodos de profundidad límite no tienen sucesores

Implementación recursiva:

Búsqueda Ciega 32

Busqueda de profundidad iterada

Búsqueda Ciega 33

Busqueda de profundidad iterada (1)

Búsqueda Ciega 34

Busqueda de profundidad iterada (2)

Búsqueda Ciega 35

Busqueda de profundidad iterada (3)

Búsqueda Ciega 36

Busqueda de profundidad iterada (4)

Búsqueda Ciega 37

El número de nodos generados en una búsqueda de profundidad limitada para una profundidad d con factor de ramaje b:

NLDS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd

El número de nodos generados en una búsqueda de profundidad iteratda para una profundidad d con factor de ramaje b : NIDS = (d+1)b0 + d b^1 + (d-1)b^2 + … + 3bd-2 +2bd-1 + 1bd

For b = 10, d = 5, NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111 NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

Overhead = (123,456 - 111,111)/111,111 = 11%

Busqueda de profundidad iterada

Búsqueda Ciega 38

Propiedades de búsqueda de profundidad iterada

¿Completo? Si ¿Tiempo? (d+1)b0 + d b1 + (d-1)b2 + …

+ bd = O(bd) ¿Espacio? O(bd) ¿Optimo? Si, Si costo por paso = 1

Búsqueda Ciega 39

Resumen de algoritmos

Búsqueda Ciega 40

Estados repetidos

¡El no detectar estados repetidos puede convertir un problema lineal en uno exponencial!

Búsqueda Ciega 41

Búsqueda en Grafos

Búsqueda Ciega 42

Resumen

La formulación del problema usualmente requiere abstraer detalles del mundo real para definir un espacio de estados que pueda ser explorado

Variedad de estrategias de búsqueda ciegas

La búsqueda de profundidad iterada usa sólo espacio lineal y no mucho más tiempo que otros algoritmos ciegos