Métodos de búsqueda heuristica

Tema 2: Métodos de búsqueda heurística• • • • • Búsqueda sin información Métodos de escalada Búsqueda primero el mejor Descomposición de problemas Heurísticas sobre el proceso de búsqueda Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Búsqueda sin información • • • • Búsqueda en anchura Búsqueda en profundidad Búsqueda con costos Problemas descomponibles Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Sistemas de Búsqueda Operadores Base de Datos Estrategia de Control Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística Representación de un problema Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística end Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . until DATOS satisface la condición de terminación do 3.Procedimiento Búsqueda 1. select alguna regla R en el conjunto de reglas que pueda ser aplicada a DATOS 5. begin 4. DATOS resultado de aplicar R a DATOS 6. DATOS base de datos inicial 2. Estrategias de control • Estrategias irrevocables • Estrategias tentativas – Retroactivas – Búsqueda en grafos Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . 13. DATOS PRIMER(LISTABD) If MIEMBRO(DATOS.Modelo de estrategia retroactiva BACKTRACK(LISTABD) 1. 7.LISTABD) CAMINO BACKTRACK(RLISTABD) If CAMINO=FALLO go CICLO return CONS(R. 2. 9. 5. 12. 3.CAMINO) Tema 2: Métodos de búsqueda heurística Inteligencia Artificial e Ingeniería del Conocimiento .SUPR(LISTABD)) return FALLO If TERM(DATOS) return NADA If SINSALIDA(DATOS) return FALLO If LONGITUD(LISTABD) > LIMITE return FALLO REGLAS APLIREGL(DATOS) CICLO: if NOHAY(REGLAS) return FALLO R PRIMER(REGLAS) REGLAS SUPR(REGLAS) RDATOS R(DATOS) RLISTABD CONS(RDATOS. 14. 10. 6. 4. 8. 11. Búsqueda en profundidad retroactiva 0 1 2 3 4 5 2 8 3 1 6 4 7 5 2 8 3 6 4 1 7 5 8 3 2 6 4 1 7 5 8 3 2 6 4 1 7 5 8 3 2 6 4 1 7 5 2 8 3 1 6 4 7 5 0 1 2 3 4 2 8 3 1 6 4 7 5 2 8 3 6 4 1 7 5 8 3 2 6 4 1 7 5 8 3 2 6 4 1 7 5 2 8 3 1 6 4 7 5 0 1 2 7 2 8 3 6 4 1 7 5 2 8 3 1 6 4 7 5 2 8 3 6 4 1 7 5 2 8 3 1 6 4 7 5 7 8 2 3 6 8 4 1 7 5 2 3 6 8 4 1 7 5 2 8 3 6 4 1 7 5 6 (b) 8 6 3 2 4 1 7 5 Discarded before generating node 7 9 (c) (a) © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . 880 Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística .Búsqueda en grafos • Imposibilidad de representar el problema mediante un grafo implícito • Problema del 8-puzzle: 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 © 1998 Morgan Kaufman Publishers • El conjunto de nodos del grado de estados para esta representación del 8-puzzle es 9!=362. Búsqueda en grafos • Formulación de los problemas para poder aplicar sobre ellos los métodos de búsqueda • Métodos que nos permitan representar grandes espacios de búsqueda mediante grafos implícitos • Métodos eficientes de búsqueda en grafos de gran tamaño Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Búsqueda en grafos • Descripción para etiquetar el nodo inicial • Las funciones para transformar las descripciones de los estados: operadores • Una condición de éxito Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Aplicar la regla para generar un nuevo estado 2. Crear una variable llamada LISTA-NODOS y asignarle el estado inicial 2. Si LISTA-NODOS está vacía. Para cada regla que se empareje con el estado descrito en E hacer: 1. Si el nuevo estado es un estado objetivo. terminar 2.Búsqueda en anchura 1. Hasta que se encuentre un estado objetivo o LISTA-NODOS esté vacía. añadir el nuevo estado al final de LISTANODO Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . En caso contrario. Eliminar el primer elemento de LISTA-NODOS y llamarlo E. hacer: 1. terminar y devolver este estado 3. Búsqueda en anchura 19 9 2 8 3 1 6 7 5 4 2 8 1 6 3 7 5 4 2 8 1 6 3 7 5 4 2 8 3 1 5 6 7 4 2 3 1 8 6 7 5 4 2 8 3 1 6 7 5 4 2 8 3 1 4 5 7 6 2 8 1 4 3 7 6 5 2 3 4 1 8 7 6 5 1 2 3 7 8 4 6 5 18 2 8 3 1 6 7 5 4 4 2 8 3 1 6 4 7 5 17 8 2 8 3 1 4 7 6 5 2 8 3 1 4 5 7 6 16 2 8 1 4 3 7 6 5 15 Start node 1 2 8 3 1 6 4 7 5 3 2 8 3 1 4 7 6 5 7 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 27 1 2 3 8 4 7 6 5 2 8 3 7 1 4 6 5 2 8 3 7 4 6 1 5 8 1 3 2 4 7 6 5 8 3 2 1 4 7 6 5 2 8 3 6 7 4 1 5 2 8 3 6 7 4 1 5 2 8 3 6 4 5 1 7 2 8 6 4 3 1 7 5 2 3 6 8 4 1 7 5 2 3 6 8 4 1 7 5 8 6 3 2 4 1 7 5 8 3 2 6 4 1 7 5 Goal node 14 2 3 1 8 4 7 6 5 26 1 2 3 8 4 7 6 5 13 2 8 3 7 1 4 6 5 25 2 8 3 7 1 4 6 5 6 2 8 3 1 4 7 6 5 24 12 8 3 2 1 4 7 6 5 8 3 2 1 4 7 6 5 23 2 8 3 6 7 4 1 5 2 2 8 3 1 6 4 7 5 11 2 8 3 6 4 1 7 5 22 2 8 3 6 4 1 7 5 5 2 8 3 6 4 1 7 5 21 2 3 6 8 4 1 7 5 10 8 3 2 6 4 1 7 5 © 1998 Morgan Kaufman Publishers 20 8 3 2 6 4 1 7 5 Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Si ABIERTOS está vacía no existe solución. Terminar. Para cada nodo sucesor j del nodo i. llamada CERRADOS. expandir el nodo i.Búsqueda con costos 1. Terminar. Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística .j). 3. inicialmente vacía. de nodos expandidos. asignando g(j)=g(i)+c(i. Ir a 3. 7. 2. 6. Suprimir de ABIERTOS el nodo i con mínima g(i) y colocarlo en CERRADOS. llamada ABIERTOS. si no tiene sucesores ir a 3. de nodos no expandidos. insertarlo correctamente en ABIERTOS. 8. Si i es un nodo objetivo se ha encontrado la solución. 4. En otro caso. 5. Crear una lista. Poner el nodo inicial s en una lista. Descenso iterativo Depth bound = 1 © 1998 Morgan Kaufman Publishers Depth bound = 2 Depth bound = 3 Depth bound = 4 Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . B.L) (B.Problemas descomponibles • Base de datos inicial (C.B.M) (B.M) • Objetivo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística .Z) • Operadores R1: C R2: C R3: B R4: Z (D.M) (M. Resolución del problema Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Grafo Y/O • Descomposición de problemas: arcos Y • Resolución de problemas: arcos O • Concepto de solución: subgrafo solución Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Nueva resolución del problema Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Ejemplo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Métodos de escalada • Algoritmo de escalada simple • Algoritmo de escalada por la máxima pendiente • Algunas variaciones estocásticas • Algoritmos genéticos Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . • Repetir hasta que se encuentre una solución o hasta que no queden nuevos operadores que aplicar al estado actual: – Seleccionar un operador que no haya sido aplicado con anterioridad al estado actual y aplicarlo para generar un nuevo estado. • Si es un estado objetivo. continuar con el estado inicial como estado actual. devolverlo y terminar. • Si no es mejor que el estado actual. En caso contrario. convertirlo en el estado actual. – Evaluar el nuevo estado. continuar con el bucle.Algoritmo de escalada simple • Evaluar el estado inicial. Si también es el estado objetivo. pero es mejor que el estado actual. Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . devolverlo y terminar. • Si no es un estado objetivo. Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . compararlo con SUCC. Si no. – Para cada operador aplicado al estado actual hacer lo siguiente: • Aplicar el operador y generar un nuevo estado • Evaluar el nuevo estado. devolverlo y terminar.Algoritmo de escalada por la máxima pendiente • Evaluar el estado inicial. continuar con el estado inicial como estado actual. • Repetir hasta que se encuentre una solución o hasta que una iteración completa no produzca un cambio en el estado actual: – Sea SUCC un estado tal que algún posible sucesor del estado actual sea mejor que este SUCC. Si es mejor. devolverlo y terminar. Si es un estado objetivo. En caso contrario. asignar a SUCC este nuevo estado. Si no es mejor. Si también es el estado objetivo. dejar SUCC como está. hacer que el estado actual sea SUCC. – Si SUCC es mejor que el estado actual. Métodos de escalada Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Algunas variaciones estocásticas • • • • Algoritmo de escalada estocástico Algoritmo de escalada de primera opción Algoritmo de escalada de reinicio aleatorio Enfriamiento simulado Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Algoritmo de enfriamiento simulado p=e − ΔE / kT Δ E =| ( valor del estado actual ) − ( valor del nuevo estado ) | • Los movimientos hacia estados peores pueden aceptarse • Se utiliza un programa de enfriamiento Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística .Algoritmos genéticos • • • • • Se genera los estados sucesores combinado dos estados padres Se inicia el proceso partiendo de k estados generados aleatoriamente (población) Un estado (individuo) se representa como una cadena sobre un alfabeto finito (a menudo cadenas de 0s y 1s) En la función de evaluación (fitness function) se asignan valores altos para los mejores estados La siguiente generación se produce mediante las operaciones de selección. cruce y mutación. Algoritmos genéticos Función de evaluación (8 reinas) = número de pares de reinas no atacadas 28 para una solución Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Algoritmos genéticos Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Búsqueda primero el mejor • • • • • • Algoritmo A* Búsqueda conducida mediante agendas Búsqueda dirigida Descenso iterativo A* Búsqueda primero el mejor recursiva A* con memoria acotada Tema 2: Métodos de búsqueda heurística Inteligencia Artificial e Ingeniería del Conocimiento . Algoritmo A* • ABIERTOS contiene el nodo inicial. insertarlo como un nodo nuevo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . CERRADOS esta vacío • Comienza un ciclo que se repite hasta que se encuentra solución o hasta que ABIERTOS queda vacío – – – – Seleccionar el mejor nodo de ABIERTOS Si es un nodo objetivo terminar En otro caso se expande dicho nodo Para cada uno de los nodos sucesores • Si está en ABIERTOS insertarlo manteniendo la información del mejor padre • Si está en CERRADOS insertarlo manteniendo la información del mejor padre y actualizar la información de los descendientes • En otro caso. Algoritmos de búsqueda Búsqueda Sobre grafos profundidad A* Con costo h=0 h<=h* Anchura Primero el mejor Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Descomposición de problemas • Algoritmo Y/O* Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Algoritmo Y/O* • GRAFO contiene el nodo de inicio. • Comienza un ciclo que se repite hasta que el nodo inicial quede resuelto o hasta que supere un valor MAXIMO – Trazar el mejor camino actual desde inicio – Seleccionar un nodo – Generar los sucesores del nodo e incluirlos de forma adecuada en el GRAFO – Propagar la información obtenida hacia arriba en el GRAFO Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Heurísticas sobre el proceso de búsqueda • Arquitecturas combinadas de percepción y planificación • Búsqueda orientada a subobjetivos • Búsqueda jerárquica • Búsqueda con horizonte Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Dificultades del proceso • Los procesos de percepción no siempre pueden obtener la información necesaria acerca del estado del entorno • Las acciones pueden no disponer siempre de modelos de sus efectos • Pueden haber otros procesos físicos. u otros agentes. en el mundo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Dificultades del proceso • En el tiempo que transcurre desde la construcción de un plan. sus recursos de memoria podrían no permitirle realizar la búsqueda de un estado objetivo Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . el mundo puede cambiar de tal manera que el plan ya no sea adecuado • Podría suceder que se le requiriese al agente actuar antes de que pudiese completar una búsqueda de un estado objetivo • Aunque el agente dispusiera de tiempo suficiente. Arquitectura percepción/planificación/actuación Sensory input Perceptual processing Goal (desired state) Current state State-space graph Planning (graph search) © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Find first action Action Tema 2: Métodos de búsqueda heurística . Búsqueda orientada a subobjetivos Islands in the search space Local searches © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Búsqueda jerárquica Metalevel path Metalevel search Goal Start Base-level searches © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística . Búsqueda jerárquica Barrier G Robot Block © 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento Tema 2: Métodos de búsqueda heurística .