Upload
martin-vidal-montes
View
223
Download
0
Embed Size (px)
Citation preview
PROCESOS DE DECISION DE MARKOV EN EL DISEÑO DE AGENTES INTELIGENTES
GERMAN HERNANDEZ
Ing. de Sistemas,
Universidad Nacional-Bogota
Http://dis.unal.edu.co/~hernandg
(PROGRAMACION DINAMICA ESTOCASTICA)
INTRODUCCIÓN
El objetivo fundamental de la charla es estudiar problemas de decisión secuencial,
en los que los resultados de las decisiones o acciones, que se toman en cada paso, no son predecibles completamente; i.e., hay
incertidumbre sobre los efectos de las acciones efectuadas. El objetivo en este tipo problemas es encontrar una
políticas optima de acción.
Teoría de control Control optimo de sistemas dinámicos estocásticos.
Teoría de la decisión, Inv. de operaciones, Ingeniería financiera Control de cadenas finitas de Markov.
Inteligencia artificial Decisiones secuénciales “inteligentes” (agentes intligentes).
Temario Decisiones secuenciales bajo
incertidumbre
Programación Dinámica Estocástica
Procesos de Decisión de Markov
Referencias
I. DESICIONES SECUENCIALES BAJO INCERTIDUMBRE
La incertidumbre introduce dos características nuevas a un problemas de optimización
• Riesgo
• Obtención de información durante el proceso de decisión
(D,N,O,f,)
• D : conjunto de posibles acciones o decisiones.
• N : conjunto de estados de la naturaleza
(índices de la incertidumbre en el problema).
• O : conjunto de salidas del problema.
• f: DNO función de salida.
• :relación de preferencia entre salidas.
Problema de decisión bajo incertidumbre
Un agente que toma decisiones tiene una función de utilidad o recompensa
u: DN RRu(a,y) es el pago obtenido al tomar la acción a en el estado y de la naturaleza. La naturaleza es modelada como un generador de estados aleatorios con una ley de probabilidad
y~P().Los agentes se suponen maximixadores de la utilidad. Entonces la estrategia optima (x) es la mejor respuesta del agente a la selección aleatoria y de la naturaleza, con x la información disponible.
“Una estrategia optima es la solución de equilibrio a un juego en contra de la naturaleza.”
Estrategias optimas
Sin información
Con información completa
Con información parcial
Desiciones secuenciales
Sistemas dinámicos
Sut
wt
ytF(ut,wt,xt)
xt+1
F(xt )xt+1
Autónomo
•No autónomo+incertidumbre•Parcialmente
observado
Sistema dinámico
(X,U,Y,W,F,S)• X conjunto de estados internos
• U conjunto de entradas
• Y conjunto de salidas
• W conjunto de incertidumbre
• F: UWX X dinámica del sistema
• S: X Y función de salida sistema
Ejemplos tomados de [1]
Sut
wt
xt
F
: Y U
“control de realimentación”
“política”
“función de decisión”
(yt)
yt
yt
Control
• D= conjunto de posibles controladores
• N=W• O=(UWY)• f: D N O
(,w) (u,w,y) dados u0 ,x0
• asociado con una función de utilidad
R: OT RR,
con T espacio de tiempo.
Problema de decisión secuencial bajo incertidumbre
• D= conjunto de posibles controladores
• N=W• O=(UWY)• f: D N O
(,w) (u,w,y) dados u0 ,x0
• asociado con una función de utilidad
R: OT RR,
con T espacio de tiempo.
La política optima *,dada una estructura probabilistica sobre
(u0 ,x0 ,w)
que modela la incertidumbre,
es la que maximiza el funcional de utilidad
V = Ew,u0,x0 [R(u,w,y)], i.e.,
V* =max V
Problemas de decisión secuencial de tiempo discreto
Diagramas de influencia Howard y Matheson 1984[2]
Problemas de Decisión Secuencial
•Tiempo discreto T={0,1,2,...,N,}
•Utilidad Tiempo-separables (utilidad aditiva)
Rt: XU RR (xt,at) R(xt,at)
R= Rt
I. PROG. DINAM. ESTOCASTICA
Principio de Optimalidad [Richard Bellman,1956]
Una política optima tiene la propiedad de que sin importar la decisión y el estado inicial, las decisiones
restantes deber ser optimas ,con respecto al estado resultante de la decisión inicial en el estado inicial.
“If you don't do the best with what you have happened to have got, you will never do the best with what you should
have had.” [Rutherford Aris]
• Horizonte• Finito• Infinito
• Espacio de estados• Discreto
• Finito• Infinito
• Continuo
• Transiciones• Determinísticas• Probalísticas
Modelo de juego
Cada jugada un jugador puede apostar cualquier cantidad menor o igual su fortuna presente y ganara o perdera esa cantidad con probabilidades p y q=p-1.
Al jugador se le permite hacer n apuestas su objetivo es maximizar la esperanza del logaritmo de su fortuna final.
Que estrategia debe seguir para conseguir esto?
Sea Vn(x) la maxima ganacia esperada del juagor si tiene una fortuna presente x y se le permite n juegos más.
con la condicion de frontera V0(x) = log(x) tenemos que
xxxqVxxxpVxVnnn
)()(max)(1110
xqp
xxqxxp
xxqVxxpVxV
log1log1logmax
loglogmax
max)(
10
10
00101
Cqp
1log1logmax10
Tenemos
xC
xqqpp
xqp
xxqxxp
xxqVxxpVxV
log
logloglog2log
log1log1logmax
loglogmax
max)(
10
10
00101
caso otroen ,0en 0
21
si ,en loglog2log*
*
α
pp-qαqqppC
entonces
xC
xCqp
xxCqxxCp
xxqVxxpVxV
log2
log1log1logmax
loglogmax
max)(
10
10
11102
Tenemos en general
xnCxVn
log)(
I. MDP’s
• Navegacion de robots
• Agentes financieros
• Inventarios
• Modelos Biologicos
• Agentes en la web
Aplicaciones
Modelos de agentes tomados de [1]
Referencias
[1] Dean T. Decision-Theoretic Planning and Markov Decision Porcesses
[2] Dean T. Algerbaic Structure in Sequential Decision Processes) ttp://www.cs.brown.edu/people/tld
[3] Bertsekas D.Dynamic Programing and Stochastic Control,Academic Press, 1987
[4] Ross Stochastic Dynamic Programming, John Wiley,
[5] Putterman M.L. Markov Descion Processes in Handbook of IO and MS Vol2 Stochastic Models, Eds Heyman Sobel, 1990