1 Solución de problemas por BúsquedaCapítulo 3 Búsqueda Ciega

2 Reseña Soluciones de problemas de agentes Tipos de problemasFormulación de problemas Problemas de ejemplo Algoritmos de búsqueda básicos Búsqueda Ciega

3 Agente Resolvedor de ProblemasBú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 aspiradoraEstado único, comienza en #5. Solución? Búsqueda Ciega

8 Ejemplo: El mundo de aspiradoraEstado ú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 aspiradoraSin 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 aspiradoraSin 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 únicoUn problema está definido por cuatro cosas: Estado Inicial v.g., “en Arad" Acciones o función sucesor S(x) = conjunto de pares acción-estado v.g., S (Arad) = {, … } Prueba de Meta explícitamente, v.g., x = "at Bucharest" implícitamente, v.g., Checkmate (x) 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 aspiradoraestados? acciones? prueba final? costo del camino? Búsqueda Ciega

14 Espacio de Estado del mundo de aspiradoraestados? 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-8estados? acciones? prueba final? costo del camino? Búsqueda Ciega

16 Ejemplo: El rompecabezas-8estados? 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óticoestados? 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úsquedaIdea 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úsquedaBúsqueda Ciega

20 Ejemplo de árbol de búsquedaBúsqueda Ciega

21 Ejemplo de árbol de búsquedaBúsqueda Ciega

22 Implementación: árbol de búsquedaBúsqueda Ciega

23 Implementación: estados vs. nodosEstado = (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úsquedaUna 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 CiegaUsan 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 expandidoImplementación: La orilla es una cola, i.e., Los sucesores nuevos van al final Búsqueda Ciega

27 Propiedades de búsqueda a lo anchoCompleta? 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 uniformeExpandir 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(bC*/ ε) donde C * es el costo de la solución óptima ¿Espacio? # de nodos con g ≤ costo de solución óptima, O(bC*/ ε) ¿Ó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 expandidoImplementació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 iteradaBú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 Busqueda de profundidad iteradaEl 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 = , , ,000 = 111,111 NIDS = , , ,000 = 123,456 Overhead = (123, ,111)/111,111 = 11% 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 Búsqueda Ciega