Inteligencia artificial para videojuegos/Teoría de la decisión

Este recurso de aprendizaje es una lección creada originalmente como material didáctico del proyecto de aprendizaje Inteligencia Artificial para Videojuegos.

Introduzco la teoría de la decisión con una o dos frases

Introducción

La Teoría de la Probabilidad resulta útil para modelar la incertidumbre… … ¿cómo podemos aprovechar esta teoría para crear un agente basado en utilidad?

Aquí asumimos que el entorno, además de no determinista y/o parcialmente observable, es episódico. Por tanto el agente elegirá una acción en función de su resultado inmediato-

IA basada en utilidad

La IA basada en utilidad (en inglés Utility AI) se basa en la Teoría de la Decisión. Podemos decir que es el resultado de Teoría de la Utilidad + Teoría de la Probabilidad.

El agente maximiza su rendimiento eligiendo la acción que en promedio lleva al estado más útil.

Ej. ¿Disparo o tiro una granada? 
Elaboramos una tabla con las dos acciones posibles y sus estados resultantes, incluyendo la probabilidad de llegar con una determinada acción a cada estado y también la utilidad del estado.

Acción posible (probabilidad)	Estado resultante (utilidad)	Acción posible (probabilidad)
Disparo (0.7) →	Yo sobrevivo, el enemigo muere (+100)	← Granada (0.8)
Disparo (0.25) →	Yo sobrevivo, el enemigo también (-1)	← Granada (0.05)
Disparo (0.04) →	Ambos morimos (-400)	← Granada (0.1)
Disparo (0.01) →	Yo muero, el enemigo sobrevive (-501)	← Granada (0.05)

U(Disparo) = 100*(0.7) -1*(0.25) - 400*(0.04) - 501*(0.01) = 48.74
U(Granada) = 100*(0.8) -1*(0.05) - 400*(0.1) - 501*(0.05) = 14.9
¡Es mucho mejor disparar!

Teoría de la decisión

El principio de esta teoría es elegir para maximizar la utilidad esperada (UE)

$acci{\acute {o}}n={\underset {a}{argmax}}\,\,\,UE(a|{\boldsymbol {e}})$

donde

$UE(a|{\boldsymbol {e}})=\sum _{s'}P(resultado(a)=s'|a,{\boldsymbol {e}})*U(s')$

Trabajando con la probabilidad de que la acción a conduzca de la evidencia e al estado s’ $P(resultado(a)=s'|a,{\boldsymbol {e}})$

¡Cualquier agente racional sigue este principio! (lo difícil es calcular la probabilidad y la utilidad).

No conocer los estados esperados nos hace ver los posibles resultados... como loterías (lottery, en inglés). Los axiomas de esta teoría son que estas loterías pueden ordenarse por preferencia, son transitivas, continuas, sostenibles, monótonas y descomponibles.

Rendimiento vs Utilidad El rendimiento es un criterio externo y global, pero la utilidad es un criterio interno y local. Son diferentes, pero en cualquier caso los valores de utilidad de los estados resultantes no importante tanto como su orden, esto es, su preferencia.

Función de utilidad

Asigna números reales a loterías. Aunque no hay escalas absolutas, la utilidad se normaliza asignando 0 a lo peor y 1 a lo mejor. La utilidad de un estado S vale p, mismo valor que la probabilidad de una lotería estándar que resulta de igual preferencia para el agente $[p,u\top ;(1-p),u\bot ]$

En realidad, un agente puede no ser neutral y preferir un valor seguro igual o menor a la utilidad esperada promedio de una lotería. Esto se llama aversión al riesgo (en esto se basan los seguros) y lo contrario es propensión al riesgo

Dinero

La Teoría de la Utilidad es un campo de la Economía y el dinero suele ser un valor seguro importante. Aunque no siempre sea directamente proporcional: ganar tu primer millón de dólares resulta mucho más útil que el segundo...

INSERTAR GRÁFICA HECHA EN GOOGLE DOCS

Estudio de Grayson de 1960 sobre interés inversor en explotaciones petrolíferas (¡es casi logarítmico!)

Función de utilidad multiatributo

Parte de la Teoría de la Utilidad asume que la utilidad de un estado depende de varios valores (atributos) distintos.

Podemos decidir en base a todos ellos:

Ejemplo. Si hay dominancia estricta (todos los atributos son mejores) o estocástica (es más probable que los atributos sean mejores)

Podemos combinarlos en uno y decidir en base a él:

Ejemplo. Sumándolos, si los atributos son mútuamente preferencialmente independientes, o con otras fórmulas (teniendo en cuenta probabilidades) si son mútuamente útilmente independientes

Red de Decisión

Una red Bayesiana a la que se añaden nodos con acciones y utilidades. Sirve para formalizar e implementar sistemas de toma de decisiones.

Los óvalos son nodos de azar (las variables aleatorias)
El rectángulo es nodo de decisión, la acción elegida
El rombo es nodo de utilidad (la función)

AÑADIR GRAFO, DESDE AQUÍ O DESDE GOOGLE DRAW

Valor de la información

Si fuese posible obtener más información antes de decidir, habría que considerar el valor (utilidad) de dicha información.

Primero elegir qué información obtener (si es que interesa) y luego, en secuencia, tomar la decisión

Ejemplo. N cofres iguales de C/N €. Todos están vacíos salvo 1, que tiene C €. ¿Cuánto vale conocer el contenido de 1 cofre concreto, antes de elegir?

${1 \over n}*{(n-1)*C \over n}+{n-1 \over n}*{C \over n*(n-1)}={C \over n}$

Conocer el valor de la información permite a un agente ser racional haciendo averiguaciones.

Ejemplo. Pruebas médicas razonables para el sufrido paciente

Sistemas expertos

La Teoría de la Decisión se aplicó a muchos problemas reales en los años 50 y 60.

Ej. Gobierno, Negocios, Ejército, Salud Pública...
Había un tomador de decisión que establecía las preferencias y un analista de decisión que hacía los cálculos para identificar la mejor acción posible.
En los 80, el analista pasó a ser una máquina.

Se crearon sistemas expertos, IAs capaz de emular la toma de decisiones de un experto.

Usaban bases de conocimiento y reglas.
A partir de los 80 pudieron escalar gracias a una inferencia más eficaz sobre redes de decisión.

Se diseñan mediante un proceso:

Crear el modelo causal
Simplificarlo a un modelo cualitativo de decisión
Asignar probabilidades
Asignar utilidades
Verificar y refinar el modelo (comparándolo con el “patrón oro” (gold standard): las opiniones más expertas)

Realizar un análisis de sensibilidad (si un cambio pequeño afecta mucho a la decisión tomada, falta conocimiento)

METER RED DE DECISIÓN GRANDE DE EJEMPLO

Decisiones complejas

Si podemos realizar varias acciones en secuencia se complica el problema, hablamos de decisiones complejas.

Se requiere razonamiento probabilista temporal (que no llegamos a estudiar)
Se pueden encontrar Redes de Decisión con múltiples nodos de decisión, en vez de uno solo

Sin embargo la industria prefiere soluciones rápidas y muy controlables por el diseñador. Al menos por ahora, se usan herramientas más simples para la toma de decisiones...

Máquina de estados finitos

Una máquina de estados finitos (finite state machine o FSM) es la manera más flexible y popular de modelar el comportamiento en juegos. La toma de decisiones reside en las transiciones.

Existen variantes no determinista Ej. Estocástica de estado múltiple o Jerárquicas (hierarchical FSM o HFSM), para reducir tamaño y reutilizar código.

PONER IMAGEN DE FSM NORMAL, E IMAGEN LIBRE DE HFSM

Árbol de comportamiento

Para evitar acoplamiento entre los estados de una máquina jerárquica de estados finitos se usa un árbol de comportamiento (behavior tree). Representa intuitivamente la ejecución de un plan (secuencia de acciones).

Es un árbol dirigido. Tiene un nodo raíz, nodos de control de flujo y nodos de ejecución. También puede tener elementos estocásticos.

PONER DIAGRAMA LIBRE DE EJEMPLO

Hay dos nodos de control de flujo:

Nodo Selector (?), tiene éxito si uno de sus hijos tiene éxito, probando de izquierda a derecha.
Nodo Secuencia (→), tiene éxito si todos sus hijos tienen éxito, de izquierda a derecha.

Además para desacoplar el contexto los nodos pueden compartir información en una estructura llamada “pizarra” (Ej. tabla de vars.)

PONER OTRO DIAGRAMA DE EJEMPLO, CREO QUE TAMBIÉN LIBRE

Conclusiones

Concluyendo...

Decisión = Utilidad + Probabilidad
Todo agente racional maximiza la utilidad esperada, siendo la función de utilidad la que asigna un valor entre 0 y 1 a las loterías
Una red de Decisión es una red Bayesiana con acciones y utilidades, y se puede usar para crear sistemas expertos
La industria prefiere la más práctica máquina de estados finitos o el intuitivo árbol de comportamiento

Cuestionarios de auto-evaluación

Lecciones relacionadas

Participantes

Federico Peinado
Diego Mateos
Lluis Cañellas

	Una extensión de las redes Bayesianas incorporando Teoría de la Utilidad.
	Una red Bayesiana.
	Una herramienta para el cálculo de probabilidades.