Resolviendo Problemas Buscando Soluciones
Contenidos• Agentes que resuelven problemas• Tipos de problemas• Formulación de problemas• Ejemplos de problemas• Algoritmos básicos de búsqueda
Resolviendo Problemas Buscando Soluciones
Contenidos• Agentes que resuelven problemas• Tipos de problemas• Formulación de problemas• Ejemplos de problemas• Algoritmos básicos de búsqueda
Tipos de problemas
• Deterministico, completamente observable � problema con un estado (single-state)– Agente sabe exactamente en que estado esta; solución es una
secuencia• No-observable � problema sin sensores (conformant
problem)– Agente puede no saber donde esta; solución es una secuencia
• No deterministico y/o parcialmente observable �
problema de contingencia– Percepciones proveen nueva información sobre el estado actual– Muchas veces se intercala: búsqueda, ejecución
• Espacio de estados desconocido � problema de exploración
Ejemplo: Rumania
• En vacaciones en Rumania; actualmente en Arad.
• El vuelo sale mañana desde Bucharest • Formular objetivo:
– Estar en Bucharest • Formular problema:
– Estados: las ciudades– Zcciones : manejar entre ciudades
• Encontrar solución:– Secuencia de ciudades, e.g., Arad, Sibiu, Fagaras,
Bucharest
Resolviendo Problemas Buscando Soluciones
Contenidos• Agentes que resuelven problemas• Tipos de problemas• Formulación de problemas• Ejemplos de problemas• Algoritmos básicos de búsqueda
Formulación de problemas
Un problema se define por cuatro ítems:
1. Estado inicial e.g ., “en Arad"2. Función de acciones o sucesor S(x) = set de pares acción-estado
– e.g., S(Arad) = {<Arad � Zerind, Zerind>, … }3. Test de objetivo, puede ser
– explicito, e.g., x = “en Bucharest"– implícito, e.g., Jaquemate(x)
4. Costo de ruta (aditivo)– e.g., suma de distancias, numero de acciones ejecutadas, etc.– c(x,a,y) es el costo de paso, se asume ≥ 0
• Una solución es una secuencia de acciones que llevan de estado inicial al estado objetivo
Seleccionando un espacio de estados
• El mundo real es demasiado complejo�espacio de estados debe ser abstraído (i.e.
simplificado) para resolver problemas�e.g., "Arad � Zerind" representa un complejo
conjunto de rutas, desvíos, paradas, etc• Para que sea realizable, cualquier estado real
“en Arad“ debe llevar a un estado real “en Zerind"
• Solución (abstracta) = – set de rutas reales que son soluciones en la vida real
• Cada acción abstracta debería ser mas “simple” que el problema original
Resolviendo Problemas Buscando Soluciones
Contenidos• Agentes que resuelven problemas• Tipos de problemas• Formulación de problemas• Ejemplos de problemas• Algoritmos básicos de búsqueda
Ejemplo: vacuum world
• Un estado, parte en #5. Solución? [Derecha, Aspirar]
• Sin sensores, parte en {1,2,3,4,5,6,7,8}e.g., Derecha va a {2,4,6,8}
Solución?
Ejemplo: vacuum world
• Sin sensores, parte en {1,2,3,4,5,6,7,8} e.g., Derecha va a {2,4,6,8} Solución?
[Derecha,Aspirar,Izq.,Aspirar]
• Contingencia– No deterministico: Aspirar puede
ensuciar una alfombra limpia– Parcialmente observable: ubicación, mugre en ubicación actual.– Percepción: [Izq., Limpio], i.e., parte en #5 o #7
Solución?
Ejemplo: vacuum world
• Sin sensores, parte en{1,2,3,4,5,6,7,8} e.g., Derecha va a {2,4,6,8} Solución?
[Derecha,Aspirar,Isq.,Aspirar]
• Contingencia– No deterministico: Aspirar puede
ensuciar una alfombra limpia– Parcialmente observable: ubicación, mugre en ubicación actual.– Percepción: [Izq., Limpio], i.e., parte en #5 o #7
Solución? [Der., if Sucio then Aspirar]
Grafo de espacio de estados en Vacuum world
• estados? entero con ubicación de polvo y robot• acciones? Izquierda, Derecha, Aspirar• test objetivo? no hay polvo en ninguna ubicación• costo ruta? 1 por acción
Ejemplo: ensamblador robótico
• estados?: coordenadas flotantes de los segmentos robóticos a las partes siendo ensambladas
• acciones? : movimientos continuos de los segmentos• test objetivo?: completar ensamblaje• costo ruta?: tiempo de ejecución
Resolviendo Problemas Buscando Soluciones
Contenidos• Agentes que resuelven problemas• Tipos de problemas• Formulación de problemas• Ejemplos de problemas• Algoritmos básicos de búsqueda
Algoritmos basados en árboles
• Idea básica:– offline, exploración simulada del espacio de estados
al generar sucesores de estados ya explorados (i.e.~expandiendo estados )
Implementación: búsqueda genérica basada en árbol
• Un estado es una representación de una configuración física
• Un nodo es una estructura de datos que constituye parte de una búsqueda vía árboles incluyendo estado, nodo padre, acción, costo de ruta g(x), profundidad
• Fringe es una cola que tiene nodos sucesores no explorados
• Una función Expand crea nuevos nodos, llenando los varios campos y usando la función SuccessorFn del problema para crear los estados correspondientes.
Estrategias de búsqueda
• Una estrategia de búsqueda se define al seleccionar un orden de expansión de nodos
• Las estrategias se evalúan de acuerdo a :– completitud: siempre encuentra una solución si alguna existe?– complejidad temporal: numero de nodos generados– complejidad espacial: numero máximo de nodos en memoria– optimalidad : siempre encuentra una solución de mínimo costo?
• Complejidad de tiempo y espacio se mide en termino de– b: máximo factor del numero de ramas del árbol de búsqueda– d: profundidad de solución de mínimo costo– m: profundidad máxima del espacio de estados (puede ser ∞)
Estrategias de búsqueda no informadas
• Estrategias de búsqueda no informadas usan solo la información disponible en la
definición del problema – Búsqueda al ancho primero (i.e. Breadth-
first )– Búsqueda de costo uniforme– Búsqueda en profundidad primero– Búsqueda en profundidad limitada– Búsqueda iterativa en profundidad
Búsqueda al ancho primero• Expandir nodo no expandido menos
profundo• Implementación:
– fringe es cola FIFO, i.e., nuevos sucesores van al final
Búsqueda al ancho primero
• Expandir nodo no expandido menos profundo
• Implementación:– fringe es cola FIFO, i.e., nuevos sucesores van al
final
Búsqueda al ancho primero
• Expandir nodo no expandido menos profundo
• Implementación:– fringe es cola FIFO, i.e., nuevos sucesores
van al final
Búsqueda al ancho primero
• Expandir nodo no expandido menos profundo
• Implementación:– fringe es cola FIFO, i.e., nuevos sucesores
van al final
Propiedades de búsqueda al ancho primero
• Completo? Si (si b es finito)• Tiempo? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1 )• Espacio? O(bd+1) (mantiene cada nodo en
memoria)• Optimo? Si (si costo = 1 por paso)
• Espacio es el mayor problema (mas que tiempo)– Ejemplo: b=10, 10000 nodos/sec, 1000 bytes/nodo– D=2 : Nodos=1100 , Tiempo=.11secs, Mem=1 MB– D=6 : Nodos=107 , Tiempo=19 min, Mem=10 GB– D=10: Nodos=1011 , Tiempo=129 dias, Mem=101 TB
Búsqueda de costo uniforme
• Búsqueda al ancho es optimo si todos los costos son iguales porque expande siempre el nodo menos profundo.
• Por simple extensión encontramos este algoritmo para árboles con costos no iguales:
– Expandir nodo no expandido de mínimo costo• Implementación:
– fringe = cola ordenada por costo de ruta• Equivalente a búsqueda al ancho si todos los costos son iguales• Completo? Si, si costo de paso ≥ ε
• Tiempo? # nodos con g ≤ costo de solución optima, O(bceiling(C*/ ε)) en el cual C*
es el costo de la solución optima• Espacio? # nodos con g ≤ costo de solución optima, O(bceiling(C*/ ε)) • Optimo? Si – nodos expandidos en orden incremental de g(n)
• Esta búsqueda en el pero caso puede ser mucho peor que bd porque al buscar grandes árboles de pasos de costo g pequeño pierde explorar rutas de pasos largos (y posiblemente útiles).
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Búsqueda en profundidad
• Expandir nodo mas profundo
• Implementación:– fringe es cola LIFO, i.e., poner sucesores al frente
Propiedades de búsqueda en profundidad
• Completo? No: falla en espacios de profundidad infinita, espacios con loops– Modificar para evitar espacios repetidos en el camino
� completo en espacios finitos
• Tiempo? O(bm): terrible si m mas grande que d– Pero si las soluciones son densas puede ser mucho
mas rápido que búsqueda al ancho
• Espacio? O(bm), i.e., lineal en espacio!• Optimo? No
Búsqueda limitada en profundidad
• Igual a búsqueda en profundidad con un limite li.e., nodos en profundidad l no tienen sucesores
• Implementación recursiva:
Búsqueda iterada en profundidad
• Numero de nodos generados en una búsqueda limitada en profundidad (DLS) hasta profundidad d con un branching factor b:
NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd
• Numero de nodos generado en una búsqueda iterada en profundidad hasta profundidad d con un branching factor 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
• Saldo adicional = (123,456 - 111,111)/111,111 = 11%
Propiedades de búsqueda iterada en profundidad
• Completo? Si
• Tiempo? (d+1)b0 + d b1 + (d-1)b2 + … + bd
= O(bd)
• Espacio? O(bd)
• Optimo? Si, si costo de paso = 1
Estados repetidos
• No se detectar estados repetidos causa que un problema lineal se puede tornar exponencial!
Búsqueda con memoria de estados visitados
•Para recordar los nodos ya expandidos se almacenan en la closed list
Resumen
• La formulación del problema requiere generalmente abstraer detalles del mundo real para definir un estado de espacios que puede ser factiblemente explorado
• Hay una variedad de estrategias de búsqueda no informadas (i.e. uninformed search strategies )
• Búsqueda iterativa en profundidad utiliza espacio lineal y no mucho mas tiempo que otros algoritmos no informados