PROCESOS DE DECISION DE MARKOV EN EL DISEÑO DE AGENTES INTELIGENTES GERMAN HERNANDEZ Ing. de...
-
Upload
martin-vidal-montes -
Category
Documents
-
view
223 -
download
0
Transcript of PROCESOS DE DECISION DE MARKOV EN EL DISEÑO DE AGENTES INTELIGENTES GERMAN HERNANDEZ Ing. de...
![Page 1: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/1.jpg)
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)
![Page 2: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/2.jpg)
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.
![Page 3: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/3.jpg)
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).
![Page 4: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/4.jpg)
Temario Decisiones secuenciales bajo
incertidumbre
Programación Dinámica Estocástica
Procesos de Decisión de Markov
Referencias
![Page 5: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/5.jpg)
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
![Page 6: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/6.jpg)
(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
![Page 7: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/7.jpg)
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.”
![Page 8: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/8.jpg)
![Page 9: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/9.jpg)
Estrategias optimas
Sin información
Con información completa
![Page 10: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/10.jpg)
Con información parcial
![Page 11: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/11.jpg)
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
![Page 12: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/12.jpg)
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
![Page 13: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/13.jpg)
Ejemplos tomados de [1]
![Page 14: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/14.jpg)
Sut
wt
xt
F
: Y U
“control de realimentación”
“política”
“función de decisión”
(yt)
yt
yt
Control
![Page 15: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/15.jpg)
• 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.
![Page 16: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/16.jpg)
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
![Page 17: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/17.jpg)
Problemas de decisión secuencial de tiempo discreto
Diagramas de influencia Howard y Matheson 1984[2]
![Page 18: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/18.jpg)
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
![Page 19: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/19.jpg)
![Page 20: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/20.jpg)
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]
![Page 21: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/21.jpg)
• Horizonte• Finito• Infinito
• Espacio de estados• Discreto
• Finito• Infinito
• Continuo
• Transiciones• Determinísticas• Probalísticas
![Page 22: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/22.jpg)
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?
![Page 23: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/23.jpg)
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
![Page 24: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/24.jpg)
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
![Page 25: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/25.jpg)
xC
xCqp
xxCqxxCp
xxqVxxpVxV
log2
log1log1logmax
loglogmax
max)(
10
10
11102
Tenemos en general
xnCxVn
log)(
![Page 26: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/26.jpg)
I. MDP’s
![Page 27: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/27.jpg)
![Page 28: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/28.jpg)
![Page 29: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/29.jpg)
![Page 30: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/30.jpg)
• Navegacion de robots
• Agentes financieros
• Inventarios
• Modelos Biologicos
• Agentes en la web
Aplicaciones
![Page 31: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/31.jpg)
Modelos de agentes tomados de [1]
![Page 32: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/32.jpg)
![Page 33: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/33.jpg)
![Page 34: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/34.jpg)
![Page 35: 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.](https://reader036.fdocumento.com/reader036/viewer/2022062500/5665b4d21a28abb57c93ff93/html5/thumbnails/35.jpg)
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