View
22
Download
0
Category
Preview:
Citation preview
21/03/2012 ( 1
Resolución de problemas mediante Búsqueda (a ciegas)
21/03/2012 ( 2
Temario Introducción a los agentes resolvedores de
problemasFormulación de problemasAlgoritmo general de búsquedaEstrategias de búsqueda a ciegas:
Búsqueda primero en anchura/profundidad Búsqueda de costo uniforme Búsqueda PP con profundidad iterativa Comparación estrategias de búsqueda Búsqueda evitando estados repetidos
21/03/2012 3
Repaso
Función del agente: proyecta un historial depercepciones dada una acción.
Programa del agente: implementación de lafunción del agente.
Un agente es cualquier cosa capaz de percibir su medioambiente con la ayuda de sensores y actuar en ese medio utilizando actuadores.
Un agente es cualquier cosa capaz de percibir su medioambiente con la ayuda de sensores y actuar en ese medio utilizando actuadores.
21/03/2012 4
Repaso (cont.)
Agente racional: aquel que hace lo correcto.Medida de rendimiento: determina el éxito
del agente, es decir, le permite hacer locorrecto.
Un agente racional es aquel que, basado en su historial de percepciones, emprende aquella acción que maximiza su medida de rendimiento.
Un agente racional es aquel que, basado en su historial de percepciones, emprende aquella acción que maximiza su medida de rendimiento.
21/03/2012 5
Agentes basados en objetivos
Los agentes resolvedores de problemas sonuna clase de agentes basados en objetivos.
Agente basado en objetivos equivalente aagente con medida de rendimiento binaria:
0 si el estado del mundo no es el objetivo 1 si el estado del mundo es un objetivo.
De esta manera, maximiza rendimiento si ysolo si (sii) alcanza el objetivo.
21/03/2012 6
Agentes resolvedores de problemas Los agentes resolvedores de problemas son
una clase de agentes basados en objetivos.
Tarea: encontrar secuencia de acciones quealcanza algún estado objetivo.
Ventaja: Pueden descartar toda acción que noalcanzará el objetivo (simplificando así el problema demaximización de rendimiento).
21/03/2012 7
<formular,buscar,ejecutar> Formulación del problema: Proceso de decidir
acciones, estados posibles del agente y del entorno Costo de las acciones. objetivo: basado en situación actual y medida de rendimiento.
Búsqueda: Proceso de hallar la secuencia deacciones que llevan al objetivo. Entrada: formulación problema Devuelve: secuencia de acciones solución.
Ejecución: tras encontrar la solución, el agenteprocede a ejecutar las acciones que esta recomienda.
21/03/2012 8
Formulación del problema (KE)
Estado inicial Acciones
Función sucesor (SUCESOR-FN(x)): conjunto de pares ordenados <acción,sucesor> de acciones legales en (alcanzables desde) x.
Espacio de estados: estado inicial + función sucesor.
Test objetivo Determina si un estado es un estado objetivo.
Costo de camino: Además de encontrar el estado de mayorrendimiento (i.e., estado objetivo), se busca el menor costo númericode cada sucesión de acciones. Refleja medida de utilidad (que estado del agente es mejor), no medida de
rendimiento (que estado del entorno es mejor). Se asume g(x,a,y) ≥ 0.
Solución: camino desde estado inicial al objetivo. Solución óptima: Tiene costo de camino mínimo.
21/ 03/ 2012 9
Tipos de entorno resolubles por medio de búsquedas
Estático: Formulación y búsqueda se realizan sinprestar atención a cambios en el entorno.
Observable: Agente conoce estado inicial, y puededetectar si un estado es objetivo o no.
Discreto: numero fínito de acciones y estados. Determinista: la función sucesor es determinista. Secuencial. Agente individual.
A excepción de secuencial, todas las otras caracteristicas son las mas simples de resolver.
21/03/2012 10
Ejemplo: Vacaciones en Rumania
Problema: Encontrar secuencia de acciones que lleven al agente desde Arad a Bucarest.
21/ 03/ 2012 11
Formulación del problema.
Estados: Ciudades.Estado inicial:
Función sucesor:
Para x = Sibiu : {<Ir(Arad), En(Arad)>,<Ir(Oradea, En(Oradea)>, <Ir(Fagaras), En(Fagaras)>,<Ir(Rimnicu Vilcea), En(Rimnicu Vilcea)>}
{En(Arad)}
{En(Arad), En(Sibiu, …)}
21/ 03/ 2012 12
{En(Bucarest)}
Test objetivo: Determina si un estado es unestado objetivo.
Costo de camino: Costo númerico de cadacamino. Refleja medida de rendimiento. Se asume g(x,a,y) ≥ 0.
Solución: camino desde estado inicial al objetivo.Solución óptima: Tiene costo de camino mínimo.
Vacaciones en Rumania Formulación del problema.
g(camino) = Σa∈camino g(x,a,y)g(x,a,y) : distancia en kms desde x a y.
21/03/2012 13
Espacio de estados Vacaciones en Rumania
Estado inicial
Estado objetivo
Función sucesor desde En(Sibiu)
UnaSolución
21/03/2012 14
Mundo de la aspiradora
Estados: del mundo 22,del agente 23 = 8 Estado inicial: cualquier estado puede designarse
como inicial. Test objetivo: todos
cuadrados limpios? Costo camino:
costo de acción es 1.
21/03/2012 15
Mundo de la aspiradora
Función sucesor para acciones: Izquierda (L),Derecha (R), Aspirar (S)
Espacio de estados
21/03/2012 16
8-puzzle
Estados: un estado esta determinado por laposición de cada una de las fichas.
Estado inicial: cualquier estado puede designarsecomo inicial.
Función sucesor: genera estados que resultan deaplicar acciones: mover blanco Izq, Der, Arr, Abajo.
Test objetivo: Ver figura. Costo camino:
costo de acción es 1.
21/03/2012 17
8-puzzle El espacio de estados contiene aproximadamente
(n+1)! estados:
8-puzzle: 9! = 362880
15-puzzle: 16! = 1,3 trillones (resoluble en pocos ms)
24-puzzle: 25! ~1025 (dificil de resolver hoy en día)
21/03/2012 18
Problemas del mundo real Algoritmos de búsqueda en rutas: rutas en redes
de computadoras, planificación viajes lineas aéreas Problema del viajante de comercio: visitar cada
ciudad una ves, utilizando el camino mas corto. Distribución VLSI: colocación de millones de
componentes y conexiones en un chip: minimizando área minimizando el circuito minimizando capacidades electricas
Búsqueda en internet (sin indexadores): gŕafo denodos conectadas por arcos.
21/03/2012 19
<formular,buscar,ejecutar> Búsqueda (de un estado objetivo) en el espacio de
estados. Aquí, búsqueda por medio de la generación de un árbol
de busqueda (ojo, != espacio de estados): Nodo Raíz: estado inicial Frontera: nodos hoja del árbol parcialmente expandido. Nodos internos generados usando función sucesor para
expandir un nodo frontera. Estrategia de búsqueda: determina orden en que se
expanden los nodos frontera.
Acaso mismo estado no puede visitarse dos veces?Gráfos de búsqueda (después).
21/03/2012 20
Nodo ≠ Estado
Nodo: <estado, nodo-padre, acción, costo de camino, profundidad>
NODO-PADRE
NODO
ACCIÓN = derecha
PROFUNDIDAD = 6
COSTO DEL CAMINO = g(NODO) = 6En(Arad)
21/03/2012 21
Arbol de búsqueda. Ejemplo
21/03/2012 22
Arbol de búsqueda. Ejemplo
21/03/2012 23
Arbol de búsqueda. Ejemplo
21/03/2012 24
Búsqueda en árboles. Algoritmo simple
funcion BUSQUEDA-ARBOLES(problema, estrategia) return una solución o fallo1 Inicializa el árbol de búsqueda usando el estado inicial del problema. 2 loop3 if no hay candidatos para expandir then return fallo4 elegir un nodo hoja para expandir de acuerdo a la estrategia 5 if nodo contiene estado objetivo then return solución6 else expandir el nodo y añadir nodos resultantes al árbol de búsqueda7 fin loop
21/03/2012 25
Estrategia: Frontera
Utilizaremos como estratégia a la frontera:
Definición: La frontera, conjunto de nodos hoja (nodos generados pero no expandidos, i.e., sin hijos). Se implementa como una cola.
21/03/2012 26
Operaciones de Cola HACERCOLA(elemento,...) crea cola con elementos
dados. VACIA?(cola) devuelve verdadero si no hay elementos
en cola. PRIMERO(cola) devuelve primer elemento de la cola BORRARPRIMERO(cola) devuelve PRIMERO(cola) y
lo borra de la cola. INSERTA(elemento, cola) inserta un elemento en la
cola y devuelve la cola resultante (tipos diferentes de colainsertan elementos en órdenes distintos)
INSERTATODO(elementos, cola) inserta conjuntode elemntos en la cola y devuelve la cola resultado.
21/03/2012 27
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
Inicializa el árbol de búsqueda usando el estado inicial del problema. bucle
si no hay candidatos para expandir entonces devolver fallo elegir un nodo hoja para expandir de acuerdo a la estrategia si nodo contiene estado objetivo
entonces devolver solución de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 28
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
Inicializa el árbol de búsqueda usando el estado inicial del problema. bucle
si no hay candidatos para expandir entonces devolver fallo elegir un nodo hoja para expandir de acuerdo a la estrategia si nodo contiene estado objetivo
entonces devolver solución de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 29
Algoritmo de búsqueda en arboles. función BUSQUEDA-ARBOLES(problema,frontera) devuelve una
solución o fallofrontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema]),frontera)
bucle si no hay candidatos para expandir entonces devolver fallo elegir un nodo hoja para expandir de acuerdo a la estrategia si nodo contiene estado objetivo entonces devolver solución de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 30
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si no hay candidatos para expandir entonces devolver fallo elegir un nodo hoja para expandir de acuerdo a la estrategia si nodo contiene estado objetivo entonces devolver solución de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 31
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si VACIA?(frontera) entonces devolver fallo elegir un nodo hoja para expandir de acuerdo a la estrategia si nodo contiene estado objetivo entonces devolver solución de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 32
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si VACIA?(frontera) entonces devolver fallo elegir un nodo hoja para expandir de acuerdo a la estrategia si nodo contiene estado objetivo entonces devolver solución de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 33
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si VACIA?(frontera) entonces devolver fallo nodo ← BORRAR-PRIMERO(frontera) si nodo contiene estado objetivo entonces devolver solución de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 34
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si VACIA?(frontera) entonces devolver fallo nodo ← BORRAR-PRIMERO(frontera) si nodo contiene estado objetivo entonces devolver solución de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 35
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si VACIA?(frontera) entonces devolver fallo nodo ← BORRAR-PRIMERO(frontera) si TEST-OBJETIVO[problema] aplicado a ESTADO[nodo] es cierto
entonces devolver SOLUCION(nodo) de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 36
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si VACIA?(frontera) entonces devolver fallo nodo ← BORRAR-PRIMERO(frontera) si TEST-OBJETIVO[problema] aplicado a ESTADO[nodo] es cierto
entonces devolver SOLUCION(nodo) de lo contrario expandir el nodo y añadir nodos resultantes al
árbol de búsquedafin bucle
21/03/2012 37
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si VACIA?(frontera) entonces devolver fallo nodo ← BORRAR-PRIMERO(frontera) si TEST-OBJETIVO[problema] aplicado a ESTADO[nodo] es cierto
entonces devolver SOLUCION(nodo) frontera← INSERTAR-TODOS(EXPANDIR(nodo, problema), frontera)
fin bucle
21/03/2012 38
Algoritmo de búsqueda en arboles.
función BUSQUEDA-ARBOLES(problema,frontera) devuelve una solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si VACIA?(frontera) entonces devolver fallo nodo ← BORRAR-PRIMERO(frontera) si TEST-OBJETIVO[problema] aplicado a ESTADO[nodo] es cierto
entonces devolver SOLUCION(nodo) frontera← INSERTAR-TODOS(EXPANDIR(nodo, problema), frontera)
fin bucle
Operaciones de la cola:INSERTA, VACIA?, BORRAR-PRIMERO, INSERTAR-TODOS
21/ 03/ 2012 39
Algoritmo de búsqueda en arboles.
función EXPANDIR(nodo,problema) devuelve conjunto de nodossucesores← conjunto vacíopara cada <acción, resultado> en
SUCESOR-FN[problema](ESTADO[nodo]) hacer s ← un NODO nuevo ESTADO[s] ← resultado NODO-PADRE[s] ← nodo ACCION[s] ← acción COSTO-CAMINO[s] ← COSTO-CAMINO[nodo] + g(nodo, acción,s) PROFUNDIDAD[s] ← PROFUNDIDAD[nodo]+1 añadir s a sucesores
devolver sucesores
Añade un nodo por cada estado sucesor de nodo.
21/03/2012 (c) Facundo Bromberg 40
Y la estrategia?
La estrategia es definida seleccionando orden enque se insertan los nodos expandidos en la cola:
En lo que resta se presentan varios algoritmos que varian en cuanto a la estrategia utilizada:
frontera← INSERTAR-TODOS(EXPANDIR(nodo, problema), frontera)
Búsqueda primero en anchuraBúsqueda primero en profundidadBúsqueda de costo uniformeBúsqueda de profundidad limitadaBúsqueda primero en profundidad
con profundidad iterativaBúsqueda bi-direccional
Búsqueda primero el mejor Búsqueda voraz Búsqueda A*.
Estrategias de búsqueda a ciegas Estrategias de búsqueda informada
• Búsqueda IDA*
21/03/2012 41
Estrategias de búsqueda a ciegas.
Utilizan solamente la información disponible en ladefinición del problema (expandiendo y testeandoestado objetivo).
Estrategias que saben si un estado (no objetivo) es masprometedor que otro se llaman búsqueda informada.
21/03/2012 (c) Facundo Bromberg 42
Estrategias de búsqueda a ciegas. Presentamos tres estrategias “ciegas” y tres
“extensiones”.Implementación de la frontera:Estrategias
Búsqueda primero en anchura
Búsqueda primero en profundidad
Búsqueda de costo uniforme
FIFO (first-in first-out): primero engenerarse, primero en expandirse.
LIFO (last-in first-out): último engenerarse, primero en expandirse.
Expande primero el nodo con menorcosto de cámino.
Detalles:Extensiones
Primero en profundidad conprofundidad limitada
Primero en profundidad conprofundidad iterativa
Búsqueda Bidireccional.
A partir de cierta profundidad, nodosgenerados excluidos de la frontera.
Profundidad limite se expandesistematicamente.
Búsqueda desde inicio y desdeobjetivo.
21/03/2012 43
Búsqueda primero en anchura
A
B C
D E F G
FRONTERA: [A]
A
B C
D E F G
FRONTERA: [B,C]
A
B C
D E F G
FRONTERA: [C,D,E]
A
B C
D E F G
FRONTERA: [D,E,F,G]
FRONTERA implementada como cola FIFOFRONTERA implementada como cola FIFO
21/03/2012 44
Rendimiento de algoritmos resolvedores de problemas.
NOTA: No confundir con redimiento del agente.
El rendimiento de un resolvedor de problemas se mide de cuatromaneras: Completitud: Encuentra siempre una solución si esta existe? Optimalidad: Encuentra siempre la solución de menor costo de camino? Complejidad en tiempo: Número de nodos generados/expandidos. Complejidad en espacio: Número de nodos almacenados en memoria
durante la búsqueda.
La complejidad en tiempo y espacio se miden con respecto a: b – factor de ramificación, o máximo número de sucesores de cualquier
nodo. d – profundidad del nodo objetivo mas superficial. m – máxima profundidad del espacio (árbol) de búsqueda (puede ser ∞)
21/03/2012 45
Búsqueda primero en anchuraCompletitud
Encuentra siempre una solución si esta existe?
21/03/2012 46
Búsqueda primero en anchuraCompletitud
Encuentra siempre una solución si esta existe?
SI, la búsqueda encontrará el objetivo siempre y cuando:Nodo objetivo mas superficial se encuentra a profundidad
finita d.Factor de ramificación b sea finito.
21/03/2012 47
Búsqueda primero en anchuraOptimalidad
El nodo objetivo mas superficial no es necesariamente elóptimo.
Óptima solo si:Todas las acciones de un cierto nivel tienen el mismo costo.
21/03/2012 48
Búsqueda primero en anchuraComplejidad en tiempo
Supongamos:espacio de estados donde cada estado tiene b
sucesores.Solución se encuentra a profundidad d.Peor caso: estado objetivo es último nodo del nivel d.Número de nodos generados:
1 + b+b2+b3.. .+bd
bd+1−b =Obd+1
21/03/2012 49
Complejidad en espacio
Quien debe permanecer en memoria?Todo nodo en la frontera:
Para el correcto funcionamiento del alg.Todo antecesor de algún nodo en la
frontera: Porque cada nodo en la frontera es
potencialmente un objetivo, y por lo tanto sucamino a la raiz debe recordarse parareconstruir la solución.
21/03/2012 50
Búsqueda primero en anchuraComplejidad en espacio
En BPA todo nodo generado debe permaneceren memoria:Porque pertenece a la frontera, o es un
antecesor de algún nodo en la frontera.La complejidad espacial es por lo tanto:
Obd+1
21/03/2012 51
Búsqueda primero en anchura
Dos lecciones: Requerimientos de memoria son un mayor problema que
tiempo de ejecución. Problemas de búsqueda de complejidad exponencial, no
pueden resolverse por métodos sin información.
1 exabyte3523 años101514
10 petabytes35 años101312
101 terabytes129 días101110
1 terabyte31 horas1098
10 gigabytes19 minutos1076
106 megabytes11 segundos1111004
1 megabyte0.11 segundos11002
MEMORIATIEMPONODOSPROFUNDIDAD
21/03/2012 52
Búsqueda de costo uniforme
A
B C
D E F G
A
B C
D E F G
FRONTERA: [B(1),C(2)]
A
B C
D E F G
FRONTERA: [C(2),D(2,5),E(3,5)]
A
B C
D E F G
FRONTERA ordenada por costo de camino g(n) (ver definición de g(n) en la próxima diapositiva)
FRONTERA ordenada por costo de camino g(n) (ver definición de g(n) en la próxima diapositiva)
1 2
1,52,5 1 1,3
1 2
1,52,5 1 1,3
1 2
1,52,5 1 1,3
1 2
1,52,5 1 1,3
FRONTERA: [D(2,5),F(3), E(3,5) G(3,3)]
FRONTERA: [A(0)]
21/03/2012 53
Función de costo g(n)
g(n) = costo (real) de alcanzar el nodo,
i.e., costo del camino desde el nodo inicial hasta n.
A
B C
D E F G
1 2
1,52,5 1 1,3
g(A) = 0g(C) = 2g(G) = 3,3
Por ejemplo:
21/ 03/ 2012 54
Búsqueda de costo uniformeAnálisis
Completo? SI, si el costo mínimo de todas las accioneses ε >0. De esta manera no hay ciclos infinitos (entre losnodos conectados por el costo nulo).
Óptimo? Si.
Demostración: Suponamos, por contradicción, que el algoritmo no es óptimo, es decir, que el algoritmo retorna nodo A como solución (con costo g(A)), pero que existe un nodo objetivo B tal que g(B) < g(A). Pero si asi fuera, la definición del algoritmo nos asegura que B esta primero en la frontera, y por lo tanto debería haber sido expandido primero, y por ende testeado primero.
21/ 03/ 2012 55
Búsqueda de costo uniformeComplejidad en tiempo y espacio
En el algoritmo de BPA, la complejidad temporal yespacial se definión en función de b y d.
En BCU puede ocurrir que la solución no sea elobjetivo menos profundo como en BPA.
Si G* es el costo de la solución, y asumimos el peorcaso en el que el costo de cada acción fue el mínimoε, entonces:
d = G*/εLas complejidades en tiempo y espacio son entonces:
O(bG*/ε)
21/03/2012 56
Búsqueda primero en profundidad
FRONTERA implementada como cola LIFO (o pila)FRONTERA implementada como cola LIFO (o pila)
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
A
B C
D E F G
OH I J K L M N
[M,G][C][E,C][D,E,C]
[L,M,G][K,C][I,E,C][B,C]
[F,G][J,K,C][H,I,E,C][A]
21/03/2012 57
Encuentra siempre una solución si esta existe?
Búsqueda primero en profundidadCompletitud
3
21/03/2012 58
Encuentra siempre una solución si esta existe?
NO, a menos que espacio de estados sea finito y no hayciclos.
Búsqueda primero en profundidadCompletitud
3
21/ 03/ 2012 59
Búsqueda primero en profundidadComplejidad en tiempo
Supongamos: factor de ramificación uniforme b.Profundidad del arbol m (potencialmente >> d hasta infinito!).
Entonces, en el peor caso, nro de nodos generados:
Terrible si m es mucho mayor que d.Ejemplo: C es el único estado objetivo.
Pero, si existen muchas soluciones, entonces masrapido que primero en anchura.
Ejemplo: si H también es solución se generaron bm estados solamente.
Obm
21/03/2012 60
Búsqueda primero en profundidadComplejidad en espacio
Obm+1
No es mas exponencial, pero igual ojo, m != dSi nodo objetivo esta en último nivel, o bien a la izq,
se reduce de 10 petabytes a 118 Kb para d=12.De donde proviene tal reducción?Nodos cuyo sub-arbol ha sido generado puede
eliminarse de memoria (ni el, ni ninguno de sus descendientes pertenecen a la frontera).
Puede reducirse a (m+1) con búsqueda hacia atrás.
21/03/2012 61
Búsqueda de profundidad limitada
BPP es mejor que BPA siempre y cuando m seapequeño (con respecto a d).
Se puede aliviar el problema de m infinito aplicando BPPcon límite de profundidad l (predeterminado x usuario):
•Es decir, nodos a profundidad l se asumen hoja.
21/03/2012 62
Búsqueda de profundidad limitada
Completitud? NO cuando l<d.Optimalidad? NO. (mismas razones que BPP)Complejidad en tiempo:Complejidad en espacio:BPP es equivalente a BPL con l = infinito.
Ob l
Obl
2 r1/03et/2ur012n sucesores 63
Búsqueda de profundidad limitada
Puede implementarse modificando función EXPANDIR(libro propone otro algoritmo, recursivo).
funcion EXPANDIR(nodo,problema,limite) return conjunto de nodos
if PROFUNDIDAD[nodo] = limite then return conjunto vacíosucesores← conjunto vacíofor each <acción, resultado>
in SUCESOR-FN[problema](ESTADO[nodo]) do s ← un NODO nuevo ESTADO[s] ← resultado NODO-PADRE[s] ← nodo ACCION[s] ← acción COSTO-CAMINO[s] ← COSTO-CAMINO[nodo] + c(nodo, acción,s) PROFUNDIDAD[s] ← PROFUNDIDAD[nodo]+1 añadir s a sucesores
21/03/2012 64
Búsqueda de profundidad limitada
Util solo cuando se conoce número de estados odiámetro del espacio de estados, porque ninguna solución puede ser mas larga que estos valores.
Ejemplo, mapa de Rumania:Nro de estados: 20 ciudades.Diámetro: 9 ciudades.
Entonces, BPL con l=9 es completo.
21/03/2012 65
Búsqueda de profundidad iterativa
Encuentra el mejor limite de profundidad l.Estrategia: aumentar gradualmente l hasta encontrar
un objetivo, osea, cuando l=d.
funcion BUSQUEDA-PROFUNDIDAD-ITERATIVA(problema)
for limite 0 to infinito do
resultado <- BUSQUEDA-PROFUNDIDAD-LIMITADA(problema, limite)
if resultado != fallo_por_corte return resultado
21/03/2012 66
Búsqueda de profundidad iterativa
Combina lo mejor de BPA y BPP:Completo? SIOptimo? SI (cuando coste de camino no disminuye con
la profundidad del nodo)Complejidad en tiempo? (d, no m Y d, no d+1)Complejidad en espacio? (d, no m)Preferido para espacio estados grande y no se conoce d.
Obd
Obd
21/03/2012 67
Búsqueda Bidireccional
Dos búsquedas simultaneas desde inicio y desde objetivo.– Motivación: Complejidad temporal es
• Previo a expansión, requiere chequear si nodo pertenece al otro árbol,osea, debe almacenar el arbol completo: Complejidad espacial es entonces
Cuando hay mas de un estado objetivo: crear nodo ficticio con todos losobjetivos como predecesores.
Completo y óptimo si ambas búsquedas son BPA.
bd /2+bd /2≪bd
Inicio objetivo
bd /2
21/03/2012 68
Búsqueda Bidireccional
Inicio objetivo
El/los predecesores de cada nodo deben poder computarse eficientemente:– Por ejemplo, cuando las acciones son reversibles.
21/03/2012 69
Comparación de estrategias de búsqueda a ciegas
SIsi costos son iguales y usa
BPA
bd/2
bd/2
SI*Si b finita
Si usa BPA
Bidireccional
NO
bm
bm
NO
Primero enprofundidad
SIsi costos son descendientes
NOSISI*si costos son
iguales
Optimo?
bdblbC*/ebd+1Espacio
bdblbC*/ebd+1Tiempo
SISI, si l ≥ d
SI*Si b es finita
Si g(x,a,y) > 0
SI*Si b finita
Completo?
Produndidad iterativa
Profundidad-limitada
Costo-uniforme
Primero en anchura
Criterio
2su 1/ 03/s2012ub-árbol). 70
Estados repetidosHasta ahora ignoramos importante complicación:
expansión de estados ya visitados.Cuando ocurre? Cuando espacio de estados no es
un árbol (recuerden: árbol es un grafo acíclico)Inevitable cuando acciones son reversibles (e.g.,
búsqueda en rutas, puzzles que deslizan piezas).problemas? Árboles de búsqueda exponenciales o
infinitos (ciclos).Evitable si “podamos” del árbol los nodos con
estados ya visitados (incluyendo su sucesores, i.e.,
21/03/2012 71
Estados repetidos exponencialidad del arbol de búsqueda
El mejor caso es donde cada estado es visitado unaves (i.e., existe a lo sumo un nodo por estado).
El peor caso es visitar cada nodo del espacio deestados un número exponencial de veces:
Espacio de estados: Árbol de búsqueda:
21/03/2012 72
Solución: evitar estados repetidos
La solución es comparar el estado de cada nuevo nodoa expandir con aquellos ya expandidos.
Problema: requiere recordar todos los estados yaexpandidos → BPP se vuelve nuevamente ineficienteen memoria.
• Una opción intermedia para BPP es testear ciclossolamente: evita árboles infinitos, pero no explosión exponencial.
Si efectivamente se recuerda cada estado expandido,la búsqueda puede verse como una exploración delgrafo de estados.
21/03/2012 73
Búsqueda en grafos.
Entonces ...recordar qué se visitó:• insertar cada estado visitado en lista cerrada, y ...
No visitarlo nuevamente• Antes de insertar en la frontera verificar que noeste en lista cerrada.
21/03/2012 74
Búsqueda en grafos.
función BUSQUEDA-GRAFOS(problema,frontera) devuelve una solución o fallo cerrado ← conjunto vacío
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera) bucle
si VACIA?(frontera) entonces devolver fallonodo ← BORRAR-PRIMERO(frontera)si TEST-OBJETIVO[problema] aplicado a ESTADO[nodo] es cierto
entonces devolver SOLUCION(nodo)si ESTADO[nodo] no está en cerrado entonces
añadir ESTADO[nodo] a cerrado frontera← INSERTAR-TODO(EXPANDIR(nodo, problema), frontera)
fin bucle
Entonces ...recordar qué se visitó:
• insertar cada estado visitado en lista cerrada, y ...
No visitarlo nuevamente• Antes de insertar en la frontera verificar que no este en lista cerrada.
21/03/2012 75
Optimalidad en grafosdesecha último camino repetido descubierto! Pero si es mejor?
• Para costos constantes, esto no puede ocurriren búsquedas PA y costo uniforme
-> PA y CU son OPTIMOS en gráfos
• En BPP y BPI es posible que encuentre primero elcamino sub-óptimo
-> NO OPTIMOS en gráfos.
21/03/2012 76
Búsqueda en grafos.Posible, aunque problemática, solucion para BPP y BPI:
desechar el peor de ambos.
• Supongamos dos nodos n1 y n
2 que representan a un
mismo estado.
• Si n1 fue generado antes que n
2, puede que no solo n
1
sino que gran parte de su sub-arbol ya ha sido expandido.
• Desechar el peor implicaría que si n2 es mejor, es decir
f(n2) < f(n
1), hay que reemplazar a n
1 por n
2, y ello implica
actualizar los costos de camino de todos los descendientes de n
1 ya generados con los nuevos valores que trae n
2.
21/03/2012 77
Búsqueda con información parcial. (omitido de EV0)Hasta ahora asumimos que:el entorno es totalmente observable y
determinista, yagente conoce efectos de cada acción
Osea, agente:Puede calcular estado resultado de cualquier
secuencia de acciones.Siempre sabe en que estado esta.
Percepción no le proporciona nueva info.
21/03/2012 78
Búsqueda con información parcial.
Que pasa si relajamos estas suposiciones?Problemas sin sensores: No sabe donde esta.Problemas de contingencia: ocurre cuando
entorno parcialmente observable y accionesinciertas:
•En este caso, percepciones proporcionan nuevainfo después de cada acción.
21/03/2012 79
Problemas sin sensoresAgente no sabe en que estado esta, pero sí en que
estados no esta:creencia: conjunto de estados posibles.
Inicialmente agente sabe que
esta en {1,2,3,4,5,6,7,8}.Secuencia: Derecha, Aspirar,
Izquierda, Aspirar lo lleva a estados
de creencia: {2,4,6,8}, {4,8}, {3,7} y
finalmente al estado objetivo {7}.
21/03/2012 80
Problemas sin sensores
Se resuelven mediante búsquedas en espacio decreencias. Aqui, acciones aplican un estado de creencia en otro.
ANTES:Espacio de estados
físicos
Se resuelven mediante búsquedas en espacio decreencias. Aqui, acciones aplican un estado de creencia en otro.
21/03/2012 81
Problemas sin sensores
Se resuelven mediante búsquedas en espacio decreencias. Aqui, acciones aplican un estado de creencia en otro.
ANTES:Espacio de estados
físicos
Se resuelven mediante búsquedas en espacio decreencias. Aqui, acciones aplican un estado de creencia en otro.
21/03/2012 82
Problemas sin sensores
Se resuelven mediante
búsquedas en espacio de
creencias. Aqui, acciones
aplican un estado de
creencia en otro.
Puede ver ahora las soluciones?
21/03/2012 83
Problemas sin sensores
DIFICULTAD: si espacio de estados físico contiene n estados, espacio estados de creencia contiene 2n.
Puede extenderse a acciones no deterministas. Simplemente seguir agregando estados a los estados de creencia.
21/03/2012 84
Problemas de contingencia+ Ley de Murphy: Aspirar puede ensuciar. + Percepción local.
– Percepción inicial:
– [I,Sucio] = {1,3}
– Secuencia de acciones:
– [Aspirar] = {5,7}
– [Derecha] ={6,8}
– [Aspirar] en {6}={8} (Success)
– PERO [Aspirar] en {8} = fallo (x Ley de Murphy)
Solución?? – Relajar requerimiento de secuancia rígida de acciones sin
percepciones:
[Aspirar, Derecha, si [D,sucio] entonces Aspirar]
– Osea, intercalar percepciones (e.g., [D,sucio]) la ejecución,osea, contemplar contingencias.
– Acciones posibles se amplian con percepciones (capçítulo 12).
21/03/2012 85
Repaso
Repaso (cont.)
Agentes basados en objetivos
Agentes resolvedores de problemas
<formular,buscar,ejecutar>
Formulación del problema (KE)
Tipos de entorno resolubles por medio de búsquedas
Ejemplo: Vacaciones en Rumania
Vacaciones en Rumania Formulación del problema.
Vacaciones en Rumania Formulación del problema.
Espacio de estados Vacaciones en Rumania
Mundo de la aspiradora
Mundo de la aspiradora
8-puzzle
8-puzzle
Problemas del mundo real
<formular,buscar,ejecutar>
Nodo ≠ Estado
Arbol de búsqueda. Ejemplo
Arbol de búsqueda. Ejemplo
Arbol de búsqueda. Ejemplo
Búsqueda en árboles. Algoritmo simple
Estrategia: Frontera
Operaciones de Cola
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Algoritmo de búsqueda en arboles.
Y la estrategia?
Estrategias de búsqueda a ciegas.
Estrategias de búsqueda a ciegas.
Búsqueda primero en anchura
Rendimiento de algoritmos resolvedores de problemas.
Búsqueda primero en anchuraCompletitud
Búsqueda primero en anchuraCompletitud
Búsqueda primero en anchuraOptimalidad
Búsqueda primero en anchuraComplejidad en tiempo
Complejidad en espacio
Búsqueda primero en anchuraComplejidad en espacio
Búsqueda primero en anchura
Búsqueda de costo uniforme
Función de costo g(n)
Búsqueda de costo uniformeAnálisis
Búsqueda de costo uniformeComplejidad en tiempo y espacio
Búsqueda primero en profundidad
Búsqueda primero en profundidadComplejidad en tiempo
Búsqueda primero en profundidadComplejidad en espacio
Búsqueda de profundidad limitada
Búsqueda de profundidad limitada
Búsqueda de profundidad limitada
Búsqueda de profundidad limitada
Búsqueda de profundidad iterativa
Búsqueda de profundidad iterativa
Búsqueda Bidireccional
Búsqueda Bidireccional
Comparación de estrategias de búsqueda a ciegas
Estados repetidos
Estados repetidos exponencialidad del arbol de búsqueda
Solución: evitar estados repetidos
Búsqueda en grafos.
Búsqueda en grafos.
Optimalidad en grafos
Búsqueda en grafos.
Búsqueda con información parcial. (omitido de EV0)
Búsqueda con información parcial.
Problemas sin sensores
Problemas sin sensores
Problemas sin sensores
Problemas sin sensores
Problemas sin sensores
Problemas de contingencia
Recommended