Transcript
Tema 2: Métodos de búsqueda heurística • • • • •
Búsqued Bús eda a sin in info forrmac ació ión n Métodos de escalada Bús Bú squed eda a pri rim mero el mej ejo or Des esc com omp posic ició ión n de de pro prob ble lem mas Heur He urís ísti tica cas s sob sobre re el pr proc oces eso o de de bús búsqu qued eda a
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 en pr profundidad Búsqueda con costos Pro Pr oble lem mas desc sco ompo pon nib ible les s
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 en pr profundidad Búsqueda con costos Pro Pr oble lem mas desc sco ompo pon nib ible les s
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
Procedimiento Búsqueda 1. DATOS base de datos inicial 2. until DATOS satisface la condición de terminación do 3. begin 4. select alguna regla R en el conjunto de reglas que pueda ser aplicada a DATOS 5. DATOS resultado de aplicar R a DATOS 6. end
Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
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
Modelo de estrategia retroactiva BACKTRACK(LISTABD) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
DATOS PRIMER(LISTABD) If MIEMBRO(DATOS,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,LISTABD) CAMINO BACKTRACK(RLISTABD) If CAMINO=FALLO go CICLO return CONS(R,CAMINO)
Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
Búsqueda en profundidad retroactiva 0
1
2 8 3 1 6 4 7 5
2
2 8 3 6 4 1 7 5
3
8 3 2 6 4 1 7 5
4
8 3 2 6 4 1 7 5
5
8 3 2 6 4 1 7 5
2 8 3 1 6 4 7 5
(a)
2 8 3 1 6 4 7 5
0
1
2 8 3 1 6 4 7 5
2
2 8 3 6 4 1 7 5
3
8 3 2 6 4 1 7 5
4
8 3 2 6 4 1 7 5
6 (b)
0
7
8 6 3 2 4 1 7 5
1
2 8 3 1 6 4 7 5
2
2 8 3 6 4 1 7 5
2 8 3 6 4 1 7 5
2 8 3 1 6 4 7 5
7
Discarded before generating node 7
8
2 3 6 8 4 1 7 5
9
2 3 6 8 4 1 7 5
2 8 3 6 4 1 7 5
(c)
© 1998 Morgan Kaufman Publishers
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.880 Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
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
Búsqueda en anchura 1. Crear una variable llamada LISTA-NODOS y asignarle el estado inicial 2. Hasta que se encuentre un estado objetivo o LISTA-NODOS esté vacía, hacer: 1. Eliminar el primer elemento de LISTA-NODOS y llamarlo E. Si LISTA-NODOS está vacía, terminar 2. Para cada regla que se empareje con el estado descrito en E hacer: 1. Aplicar la regla para generar un nuevo estado 2. Si el nuevo estado es un estado objetivo, terminar y devolver este estado 3. En caso contrario, 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
Búsqueda en anchura 19
9 2 8 3 1 6 7 5 4
4
2 8 1 6 3 7 5 4
2 8 1 6 3 7 5 4
18
2 8 3 1 5 6 7 4
2 8 3 1 6 7 5 4
17
2 8 3 1 6 4 7 5
8 2 8 3 1 4 7 6 5
2 8 3 1 4 5 7 6
2 8 3 1 6 7 5 4
16
2 8 3 1 4 5 7 6
2 8 1 4 3 7 6 5
15
Start node
2 3 1 8 6 7 5 4
2 8 1 4 3 7 6 5
1
3
7
2 3 1 8 4 7 6 5
2 3 4 1 8 7 6 5
2 8 3 1 6 4 7 5
2 8 3 1 4 7 6 5
2 3 1 8 4 7 6 5
14
26
2 3 1 8 4 7 6 5
1 2 3 8 4 7 6 5
13
25
2 8 3 7 1 4 6 5
2 8 3 7 1 4 6 5
27 1 2 3 8 4 7 6 5
24
2 8 3 7 1 4 6 5 2 8 3 7 4 6 1 5 8 1 3 2 4 7 6 5
12
8 3 2 1 4 7 6 5
2 8 3 6 7 4 1 5
8 3 2 1 4 7 6 5
23
2 8 3 6 7 4 1 5
2 8 3 6 7 4 1 5
2 2 8 3 1 6 4 7 5
11
22
2 8 3 6 4 1 7 5
2 8 3 6 4 1 7 5
5 2 8 3 6 4 1 7 5
Goal node
8 3 2 1 4 7 6 5
6 2 8 3 1 4 7 6 5
1 2 3 7 8 4 6 5
21 2 3 6 8 4 1 7 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
10
20
8 3 2 6 4 1 7 5
8 3 2 6 4 1 7 5
8 3 2 6 4 1 7 5
© 1998 Morgan Kaufman Publishers
Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
Búsqueda con costos 1. 2. 3. 4. 5. 6. 7. 8.
Poner el nodo inicial s en una lista, llamada ABIERTOS, de nodos no expandidos. Crear una lista, llamada CERRADOS, de nodos expandidos, inicialmente vacía. Si ABIERTOS está vacía no existe solución. Terminar. Suprimir de ABIERTOS el nodo i con mínima g(i) y colocarlo en CERRADOS. Si i es un nodo objetivo se ha encontrado la solución. Terminar. En otro caso, expandir el nodo i, si no tiene sucesores ir a 3. Para cada nodo sucesor j del nodo i, insertarlo correctamente en ABIERTOS, asignando g(j)=g(i)+c(i,j). Ir a 3.
Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
Descenso iterativo
Depth bound = 1
Depth bound = 2
Depth bound = 3
Depth bound = 4
© 1998 Morgan Kaufman Publishers
Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
Problemas descomponibles • Base de datos inicial (C,B,Z) • Operadores R1: C R2: C R3: B R4: Z
(D,L) (B,M) (M,M) (B,B,M)
• Objetivo Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
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
Algoritmo de escalada simple • Evaluar el estado inicial. Si también es el estado objetivo, devolverlo y terminar. En caso contrario, continuar con el estado inicial como estado actual. • 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. – Evaluar el nuevo estado. • Si es un estado objetivo, devolverlo y terminar. • Si no es un estado objetivo, pero es mejor que el estado actual, convertirlo en el estado actual. • Si no es mejor que el estado actual, continuar con el bucle. Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
Algoritmo de escalada por la máxima pendiente • Evaluar el estado inicial. Si también es el estado objetivo, devolverlo y terminar. En caso contrario, 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. – Para cada operador aplicado al estado actual hacer lo siguiente: • Aplicar el operador y generar un nuevo estado • Evaluar el nuevo estado. Si es un estado objetivo, devolverlo y terminar. Si no, compararlo con SUCC. Si es mejor, asignar a SUCC este nuevo estado. Si no es mejor, dejar SUCC como está.
– Si SUCC es mejor que el estado actual, hacer que el estado actual sea SUCC. Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
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 =| ( valor
− Δ E / kT
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
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.
Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
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
Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
Algoritmo A* • ABIERTOS contiene el nodo inicial, 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, insertarlo como un nodo nuevo
Inteligencia Artificial e Ingeniería del Conocimiento
Tema 2: Métodos de búsqueda heurística
Algoritmos de búsqueda Búsqueda Sobre grafos
profundidad
A*
Con costo h=0
Anchura
h<=h*
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, 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, 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
Arquitectura percepción/planificación/actuación Sensory input
Perceptual processing
Goal (desired state)
Current state
State-space graph
Planning (graph search)
Find first action
Action
© 1998 Morgan Kaufman Publishers Inteligencia Artificial e Ingeniería del Conocimiento
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