Download Búsqueda multiagente - Grupo de Inteligencia Artificial

Inteligencia Artificial
Búsqueda en línea y
Búsqueda multiagente
Ingeniería Informática, 4º
Curso académico: 2011/2012
Profesores: Ramón Hermoso y Matteo Vasirani
–1–
Inteligencia Artificial
4º Ing. Sup. Inf
Tema 2: Agentes basados en Búsqueda
Resumen:
2. Agentes basados en búsqueda
2.1. Búsqueda en espacios de estados
2.2 Búsqueda no-informada
2.3. Búsqueda heurística
2.4. Búsqueda multiagente
2.5. Búsqueda con espacios estructurados
–2–
Inteligencia Artificial
4º Ing. Sup. Inf
Búsqueda en línea
Búsqueda en línea (online search):
•  engranar búsqueda (elección de acciones) y acción/percepción
•  necesario cuando:
–  el espacio de búsqueda es demasiado grande para buscar hasta la
solución (y no se puede aplicar las técnicas anteriores)
–  no es realista usar un modelo determinista de los efectos de acciones
•  por frecuentes contingencias (p.e.: a veces el brazo deja caer un bloque)
•  porque no se dispone de un modelo del entorno (p.e.: un mapa )
•  medida de eficiencia:
–  en general, no se puede asegurar optimalidad ni completitud
del camino real del agente
–  minimizar el índice competitivo = CosteCoste
del camino óptimo
–  el índice competitivo puede ser infinito, particularmente cuando hay
acciones que no son reversibles
–3–
Inteligencia Artificial
4º Ing. Sup. Inf
Búsqueda con horizonte
Búsqueda con horizonte (limited-horizon search):
•  Idea subyacente:
–  la primera acción de un plan que lleva a un nodo con una evaluación heurística
óptima, tiene una buena probabilidad de pertenecer al camino (óptimo) al objetivo
•  Algoritmo:
–  Percibir el estado actual s
–  Aplicar búsqueda en profundidad limitada por el nivel k y nodos metas.
Sea H el conjunto de hojas del árbol de búsqueda correspondiente.
–  Determinar el nodo hoja n* de menor valor de f *: n* ← arg min f * (n)
n∈H
–  Ejecutar la primera acción a* en el camino que lleva a n*
–  Repetir hasta que el agente se encuentra en un estado meta
[
]
•  Optimización mediante podas α (para h* consistente)
–  Sea H el conjunto de hojas del árbol de búsqueda desarrollado hasta el momento.
Mantener un valor de corte α tal que α ← min[ f * (n)]
n∈H ʹ′
–  Abandonar cualquier rama a partir de un nodo n con f *(n) > α
–4–
Inteligencia Artificial
4º Ing. Sup. Inf
Ejemplo: Búsqueda con horizonte
estado actual s = A
horizonte k = 3
filtrando ciclos simples
A
S
F
f* =
= 393
O
f * = 0+366
= 366
140+253
T
f * = 118+329
= 447
Z
f * = 75+374
= 449
f * = 220+193
= 413
R
f * = 239+178 f * = 291+380
= 417
= 671
k=3
α = 413
–5–
Inteligencia Artificial
4º Ing. Sup. Inf
Ejemplo: Búsqueda con horizonte
estado actual s = S
horizonte k = 3
filtrando ciclos simples
A
T
f * = 140+366
= 506
f * = 258+329
= 587
Z
f * = 215+374
= 589
S
F
f * = 0+253
= 253
f * = 99+178
= 277
O
f * = 151+380
= 531
C
B
R
f * = 226+160
= 386
f * = 80+193
= 273
P
f * = 177+98
= 275
f * = 310+0
= 310
k=3
α = 587
α = 310
–6–
Inteligencia Artificial
4º Ing. Sup. Inf
Ejemplo: Búsqueda con horizonte
estado actual s = R
horizonte k = 3
filtrando ciclos simples
R
C
D
f* =
= 306
f * = 0+193
= 193
146+160
P
P
f * = 266+242 f * = 284+98
= 508
= 382
f * = 97+98
= 195
B
f
*=
198+0
= 198
S
f * = 80+253
= 333
C
f * = 235+160
= 395
k=3
α = 382
α = 198
–7–
Inteligencia Artificial
4º Ing. Sup. Inf
Ejemplo: Búsqueda con horizonte
estado actual s = R
horizonte k = 3
filtrando ciclos simples
P
B
f* =
101+0
= 101
f * = 0+98
= 98
C
f * = 138+160
= 298
R
f * = 97+193
= 290
k=3
–8–
Inteligencia Artificial
4º Ing. Sup. Inf
Tema 2: Agentes basados en Búsqueda
Resumen:
2. Agentes basados en búsqueda
2.1. Búsqueda en espacios de estados
2.2 Búsqueda no-informada
2.3. Búsqueda heurística
2.4. Búsqueda multiagente
2.5. Búsqueda con espacios estructurados
–9–
Inteligencia Artificial
4º Ing. Sup. Inf
Resolución de problemas con múltiples agentes
– 10 –
Inteligencia Artificial
4º Ing. Sup. Inf
Agentes especializados
Situación:
•  múltiples agentes de resolución de problemas actúan en el mismo entorno
•  las acciones de los demás agentes influyen en la medida de rendimiento
de cada agente
•  ningún agente puede controlar las acciones de los demás agentes
•  hasta cierto punto, un agente puede predecir las acciones de los demás
Tipos de problemas multiagente :
•  escenarios cooperativos: metas compartidas
•  escenarios parcialmente cooperativos: algunas metas compartidas,
otras opuestas
•  escenarios antagónicos: metas opuestas
– 11 –
Inteligencia Artificial
4º Ing. Sup. Inf
Escenarios antagónicos: Juegos
Juegos:
•  ejemplo clásico de escenarios antagónicos (juegos de suma nula)
•  el escenario está totalmente definido por las reglas del juego, y los agentes
jugadores los conocen completamente
Tipos de juegos:
•  número de jugadores :
–  bipersonales (damas) / múltiples jugadores (Monopoly)
•  elementos de azar:
–  con elementos de azar (backgammon) /
sin elementos de azar (damas)
•  información:
–  información perfecta (damas) /
información incompleta (póker)
– 12 –
juegos bipersonales con
información perfecta y
sin elementos de azar
Inteligencia Artificial
4º Ing. Sup. Inf
Ejemplo: Tres en Raya
Tres en Raya:
•  dos jugadores (min y max)
•  los jugadores van poniendo fichas en las casillas
de un tablero 3x3
–  max usa las fichas X / min usa las fichas O
gana max
–  una casilla puede contener como mucho una ficha
•  Reglas:
–  Inicialmente el tablero está vacío
–  max empieza y los jugadores se van alternando en
poner sus fichas
gana min
–  max gana si obtiene una raya de tres fichas X
–  min gana si obtiene una raya de tres fichas O
–  si todas las casillas están ocupadas sin que haya
una raya de 3 fichas del mismo tipo, hay empate
– 13 –
empate
Inteligencia Artificial
4º Ing. Sup. Inf
Modelo de juegos bipersonales
Conocimientos mínimos a priori de los agentes max y min :
–  s0
–  expandir: s  {si1, ..., sin}
posición inicial (estado inicial)
cjto. finito de posiciones sucesores
–  terminal?: s  true | false
prueba terminal
–  U: s  k, k∈ℜ
función parcial de utilidad del juego
Nótese:
•  la función expandir
–  codifica las jugadas (acciones) permitidas en una posición s
–  supone implícitamente que los jugadores se alternan en realizar las jugadas
•  la función de utilidad está definida sólo en los estados terminales s
–  juegos de suma nula: max gana si y sólo si min pierde
–  gana max: U(s) = +∞ / gana min : U(s) = –∞ / empate: U(s) = 0
– 14 –
Inteligencia Artificial
4º Ing. Sup. Inf
Ejemplo: Árbol de juego para Tres en Raya
max
min
...
max
min
...
... ...
...
–∞
+∞
terminal
0
utilidad
– 15 –
Inteligencia Artificial
4º Ing. Sup. Inf
Árboles de juego
Definición:
Sea N un conjunto de nodos, E⊆N×N, L = {max,min}, y G = (N,E,L) un árbol
etiquetado. G es un árbol de juego si
–  G no es vacío
–  la raíz está etiquetada max
–  todos los sucesores de max son etiquetados min
–  todos los sucesores de min son etiquetados max
Observaciones:
•  cada nivel del árbol de juego representa un ply (media jugada)
–  en los nodos etiquetados max, es el turno del agente max
–  en los nodos etiquetados min, es el turno del agente min
•  las hojas de un árbol de juego (completamente desarrollado)
representan las posiciones terminales del juego
– 16 –
Inteligencia Artificial
4º Ing. Sup. Inf
Estrategias
Problema del agente max: ¿cómo determinar su mejor jugada?
•  max podría aplicar métodos de búsqueda estándar, usando las posiciones en
las que él gana como estados meta
•  pero min no querría realizar las acciones que el plan de max prevé para él !
Estrategia:
•  define las jugadas de max para cada posible jugada de min
•  un subárbol del árbol de juego
Estrategia óptima (ó racional) :
•  la estrategia que implica el mejor resultado garantizado para max
•  escenarios totalmente antagónicos con agentes racionales:
–  max puede asumir que min hará lo mejor para sí mismo, lo cual el lo peor para max
•  la estrategia óptima para max es la estrategia minimax:
–  maximizar la utilidad mínima en cada jugada
– 17 –
Inteligencia Artificial
4º Ing. Sup. Inf
Ejemplo: estrategia minimax
estrategia óptima:
mejor jugada de max: a1
max
0
a2
a1
-∞
0
min
a3
a1,1 a1,2
a1,3
0
+∞
a2,1 a2,2
-∞
a2,3
a3,1
–∞
0
a3,2
a3,3
0
–∞
terminal
utilidad
0
+∞
– 18 –
+∞
Inteligencia Artificial
4º Ing. Sup. Inf
Método minimax
Método Minimax:
1.
Generar el árbol de juego completo
2. Aplicar la función de utilidad en cada nodo terminal
3.
Propagar las utilidades hacia arriba
– en los nodos max, usar la utilidad máxima de los sucesores
– en los nodos min, usar la utilidad mínima de los sucesores
4.
Eventualmente los valores de utilidad llegan al nodo raíz (max)
5.
La jugada óptima de max es la que lleva al sucesor de utilidad máxima
– 19 –
Inteligencia Artificial
4º Ing. Sup. Inf
Algoritmo Minimax básico
Algoritmo:
•  funciones mutuamente recursivas
•  estado es el estado actual
•  α : máximo de la utilidad de los
sucesores de un nodo max
•  β : mínimo de la utilidad de los
sucesores de un nodo min
{MaxValor en el Minimax básico}
{MinValor en el Minimax básico}
Función MaxValor(estado)
Si terminal?(estado) entonces
devolver(U(estado))
sucesores ← expandir(max, estado)
α ← -∞
Para cada s∈sucesores hacer
α ← max(α, MinValor(s))
devolver(α)
Fin {MaxValor}
Función MinValor(estado)
Si terminal?(estado) entonces
devolver(U(estado))
sucesores ← expandir (min, estado)
β ← +∞
Para cada s∈sucesores hacer
β ← min(β,MaxValor(s))
devolver(β)
Fin {MinValor}
– 20 –
Inteligencia Artificial
4º Ing. Sup. Inf
Decisiones imperfectas
Problema: crecimiento exponencial del árbol de juego
•  incluso en juegos muy simples, es imposible desarrollar el árbol de
juego completo hasta todos sus nodos terminales
Solución: Heurísticas
•  sustituir la prueba terminal por una prueba suspensión que detiene la
búsqueda aún sin llegar a una posición terminal:
–  límite de profundidad fijo
–  posiciones en reposo
•  aplicar una función de evaluación e, que estime la utilidad esperada
del juego correspondiente a una posición s determinada
–  e debe coincidir con la función de utilidad u en los nodos terminales
–  suele ser función lineal ponderada : e(s) = w1 f1(s) + w2 f2(s) + . . . + wn fn(s)
–  Ajedrez:
e(s) = suma de los valores materiales en s
–  Tres en Raya: e(s) = nº de líneas abiertas para líneas max en s –
nº de líneas abiertas para líneas min en s
– 21 –
Inteligencia Artificial
4º Ing. Sup. Inf
Ejemplo: minimax con suspensión
estrategia óptima:
mejor jugada de max: a1
max
3
a2
a1
3
min
a1,1 a1,2
evaluación e
3
12
a3
2
a1,3
8
a2,1 a2,2
2
4
– 22 –
2
a2,3
a3,1
a3,2
6
14
5
a3,3
2
Inteligencia Artificial
4º Ing. Sup. Inf
Algoritmo Minimax con suspensión
Algoritmo:
•  funciones mutuamente recursivas
•  estado es el estado actual
•  α : máximo de la evaluación de los
sucesores de un nodo max
•  β : mínimo de la evaluación de los
sucesores de un nodo min
{MaxValor: Minimax con suspensión}
{MinValor: Minimax con suspensión}
Función MaxValor(estado)
Si suspensión?(estado) entonces
devolver(e(estado))
sucesores ← expandir(max, estado)
α ← -∞
Para cada s∈sucesores hacer
α ← max(α, MinValor(s))
devolver(α)
Fin {MaxValor}
Función MinValor(estado)
Si suspensión?(estado) entonces
devolver(e(estado))
sucesores ← expandir (min, estado)
β ← +∞
Para cada s∈sucesores hacer
β ← min(β,MaxValor(s))
devolver(β)
Fin {MinValor}
– 23 –
Inteligencia Artificial
4º Ing. Sup. Inf
Ejemplo: Tres en Raya
Suspensión en ply 3
max
min
...
–∞
...
–∞
...
–∞
1
+∞
1
1
–∞
...
2
max
–∞ +∞
1
0
1
1
+∞
1
– 24 –
+∞
Inteligencia Artificial
4º Ing. Sup. Inf
Poda α-β
Nótese:
•  a veces es posible calcular la utilidad de un nodo sin tener que evaluar
todos sus sucesores
max
3
a2
a1
3
min
a1,1 a1,2
3
12
a3
2
≤2
a1,3
8
a2,1 a2,2
2
– 25 –
a2,3
a3,1
14
a3,2
5
a3,3
2
Inteligencia Artificial
4º Ing. Sup. Inf
Poda α-β
Utilidad más alta encontrada en un nodo max hasta el momento: α
max
min
α
...
Condición de poda: β≤α
•  La utilidad Umin del nodo min
será como mucho β
•  La utilidad Umax del nodo max
será al menos α
•  No es necesario explorar los
sucesores restantes de min, ya
que se cumple en todo caso:
Umin ≤ β ≤ α ≤ Umax
β
– 26 –
Inteligencia Artificial
4º Ing. Sup. Inf
Poda α-β
Utilidad más baja encontrada en un nodo min hasta el momento: β
min
max
β
...
Condición de poda: α≥β
•  La utilidad Umax del nodo max
será al menos α
•  La utilidad Umin del nodo min
será como mucho β
•  No es necesario explorar los
sucesores restantes de max, ya
que se cumple en todo caso:
Umin ≤ β ≤ α ≤ Umax
α
– 27 –
Inteligencia Artificial
4º Ing. Sup. Inf
Minimax con poda α-β
Algoritmo:
•  funciones mutuamente recursivas
•  estado es el estado actual
{MaxValor: Minimax con poda α-β}
•  α es el mejor valor de evaluación
para max en el camino hasta estado
•  β es el mejor valor de evaluación
para min en el camino hasta estado
{MinValor: Minimax con poda α-β}
Función MaxValor(estado,α,β)
Función MinValor(estado,α,β)
Si suspensión?(estado) entonces
Si suspensión?(estado) entonces
devolver(e(estado))
devolver(e(estado))
sucesores ← expandir(max, estado)
sucesores ← expandir (min, estado)
Para cada s∈sucesores hacer
Para cada s∈sucesores hacer
α ← max(α, MinValor(s,α,β ))
β ← min(β,MaxValor(s,α,β ))
Si α ≥ β entonces devolver(β)
Si β ≤ α entonces devolver(α)
devolver(α)
devolver(β)
Fin {MaxValor}
Fin {MinValor}
– 28 –
Inteligencia Artificial
4º Ing. Sup. Inf
Resumen
Análisis:
•  la eficiencia de minimax con poda α-β depende del orden en el que se
exploran los nodos
•  en promedio, la poda α-β permite expandir 50% menos nodos que
minimax
Problemas:
•  efecto horizonte:
–  la búsqueda se suspende justo cuando el jugador está por hacer una gran jugada
•  suposición de racionalidad perfecta:
–  suponga que max está a punto de perder si min juega de forma óptima
–  sin embargo, hay una jugada que hace ganar a max, si min hace un solo error
Extensiones:
•  juegos con elementos de azar (p.e. backgammon)
–  expectminimax: añadir niveles de nodos azar y calcular su utilidad esperada
•  aprender funciones de evaluación y de suspensión
•  heurísticas fuertes basados en meta-razonamiento
–  algoritmos de búsqueda guiados por la utilidad esperada de expandir un nodo
– 29 –
Inteligencia Artificial
4º Ing. Sup. Inf
Ejercicio 5.1
Considérese el siguiente árbol de juego desarrollado hasta ply 3. Los nodos
están etiquetados con los valores de la función de evaluación e.
a) Evalúe el árbol del juego en base al algoritmo minimax.
b) ¿Cuál es la mejor jugada para el agente max?
7
6
8
5
2
3
0
– 30 –
–2
6
2
5
8
9
2
Inteligencia Artificial
4º Ing. Sup. Inf
Ejercicio 5.2
Considerese el árbol de juego del ejercicio anterior. Evalúe el árbol
utilizando el algoritmo minimax con poda α-β. Cuando aplica una poda,
indique la condición de poda correspondiente.
7
6
8
5
2
3
0
– 31 –
–2
6
2
5
8
9
2
Inteligencia Artificial
4º Ing. Sup. Inf