1 Sesión 12: Procesos de Decisión de Markov
2 Procesos de Decisión de MarkovProcesos de Decisión Secuenciales Procesos de Decisón de Markov (MDP) Método de Iteración de Valor Procesos de Decisión de Markov Parcialmente Observables (POMDP) Aplicaciones Incertidumbre - MDP, L.E. Sucar
3 Problemas de decisión secuencialesProblema de decisión que involucra un conjunto de decisiones cuyo resultado (utilidad) se conoce hasta el final Se considera que se tiene una serie de estados y decisiones asociadas en el tiempo Se tiene incertidumbre asociada con los resultados de las acciones (MDP), y posiblemente también con los estados (POMDP) Incertidumbre - MDP, L.E. Sucar
4 Incertidumbre - MDP, L.E. SucarEjemplo – robot móvil Inicio Incertidumbre - MDP, L.E. Sucar
5 Incertidumbre - MDP, L.E. SucarModelo de Transición Normalmente existe incertidumbre respecto a los resultados de una decisión (acción) Esta incertidumbre se modela como una probabilidad de llegar al estado “j” dado que se encuentra en el estado “i” y se realizá la acción “a”: Mija Incertidumbre - MDP, L.E. Sucar
6 Incertidumbre - MDP, L.E. SucarModelo de Transición Probabilidad dirección deseada – Pij=0.8 Probabilidad 2 direcciones vecinas – Pik=0.1 Incertidumbre - MDP, L.E. Sucar
7 Incertidumbre - MDP, L.E. SucarModelo de los Sensores Normalmente el agente puede sensar el ambiente para observar en que estado se encuentra. Existen dos casos principales: Observa directamente el estado donde se encuentra- proceso de decisión de Markov Se tiene incertidumbre sobre el estado en que se encuentra- proceso de decisión de Markov parcialmente observable Incertidumbre - MDP, L.E. Sucar
8 Incertidumbre - MDP, L.E. Sucar
9 Incertidumbre - MDP, L.E. SucarPOMDP Incertidumbre - MDP, L.E. Sucar
10 Incertidumbre - MDP, L.E. SucarPolítica Óptima Dado el modelo de transición y el modelo de los sensores, el objetivo es encontrar la política óptima para maximizar la utilidad esperada Una política indica la acción que se debe ejecutar dado el estado (o probabilidad del estado) Se considera que las probabilidades de transición sólo dependen del estado actual por lo que son procesos markovianos Incertidumbre - MDP, L.E. Sucar
11 Incertidumbre - MDP, L.E. SucarEjemplo de Política Inicio Incertidumbre - MDP, L.E. Sucar
12 Procesos de Decisión de MarkovProblema de obtener la política óptima en un ambiente observable – MDP El método clásico para resolver estos problemas se conoce como “iteración de valor” (value iteration) La idea básica es calcular la utilidad de cada posible estado y usar éstas para seleccionar la acción óptima en cada estado Incertidumbre - MDP, L.E. Sucar
13 Procesos de Decisión de MarkovFormalmente, un PDM (discreto) se define por: Un conjunto finito de estados, S Un conjunto finito de posibles acciones, A Un modelo de transición, que especifica la probabilidad de pasar a un estado dado el estado presente y la acción, P(s | s’, a) Una función de recompensa, que especifica el “valor” de ejecutar cierta acción a en el estado s, r(s, a) Incertidumbre - MDP, L.E. Sucar
14 Utilidad La utilidad de un estado depende de la secuencia de acciones tomadas a partir de dicho estado (i) de acuerdo a la política establecida (p) En principio, se puede obtener como la utilidad esperada de todas las posibles secuencias de acciones (Hi) y la utilidad resultante para c/u: U(i) = UE( Hi(p) ) = S P(Hi(p)) Uh Hi(p) Incertidumbre - MDP, L.E. Sucar
15 Incertidumbre - MDP, L.E. SucarUtilidad Si la utilidad es separable, se puede estimar como la utilidad del estado presente y la utilidad de los siguiente estados La forma más sencilla es que sea una función aditiva: U[s0, s1, ... sn] = R(s0) + U[s1, ... sn] Donde R se conoce como la función de recompensa Incertidumbre - MDP, L.E. Sucar
16 Programación DinámicaDada la condición de separabilidad, la utilidad de un estado se puede obtener en forma iterativa maximizando la utilidad del siguiente estado: U(i) = R(i) + maxa Sj P(sj | si,a) U(j) La política óptima esta dada por la acción que de mayor utilidad: P*(i) = arg maxa Sj P(sj | si,a) U(j) Incertidumbre - MDP, L.E. Sucar
17 Programación DinámicaSi se tiene un número finito de pasos (n), entonces la política óptima se puede calcular eficientemente utilizando PD: Se obtiene la utilidad de los estados en el paso n-1 en base a la utilidad de los estados terminales y se determina la mejor acción Se obtiene la utilidad de los estados en el paso n-2 en base al paso n-1, y así sucesivamente Al final se tiene la política óptima (mejor acción para cada estado) Incertidumbre - MDP, L.E. Sucar
18 Incertidumbre - MDP, L.E. SucarPD – ejemplo robot Si se define la función de utilidad como: Uh = valor estado final – 1/25 (número de pasos) Entonces la función de recompensa es: R = +1, -1 para los estados terminales R = -1/25 para los demás estados Incertidumbre - MDP, L.E. Sucar
19 Incertidumbre - MDP, L.E. SucarPD – ejemplo robot Asumiendo que se llega a la meta en n pasos: U(a=derecha) = [0.8*1-0.1*1/ *1/25] = 0.792 U(a=abajo) = [0.1*1-0.8*1/ *1/25] = 0.064 U(a=izq.) = [-0.1*1/25-0.8*1/ *1/25] = -0.04 U(s33) = -1/25 + max [.792, .064, -.04] = 0.752; P*(s31) = derecha 3 2 1 Incertidumbre - MDP, L.E. Sucar 1 2 3 4
20 Horizonte finito vs. infinitoLos problemas de con un número finito de pasos se conocen como MDP de horizonte finito Los problemas en que puede haber un número infinito de pasos se conocen como MDP de horizonte infinito Muchos problemas, como el ejemplo del robot, son de horizonte infinito y no se pueden resolver directamente por PD Incertidumbre - MDP, L.E. Sucar
21 Iteración de Valor En el caso de horizonte infinito, se puede obtener la utilidad de los estados –y la política óptima, mediante un método iterativo En cada iteración (t+1), se estima la utilidad de cada estado basada en los valores de la iteración anterior (t): Ut+1(i) = R(i) + maxa Sj P(sj | si,a) Ut(j) Cuando tinf, los valores de utilidad convergen a un valor estable Incertidumbre - MDP, L.E. Sucar
22 Incertidumbre - MDP, L.E. SucarIteración de Valor Algoritmo: Inicializar: Ut = Ut+1 = R Repetir: Ut=Ut+1 Ut+1(i) = R(i) + maxa Sj P(sj | si,a) Ut(j) Hasta: | Ut-Ut+1 | < e Incertidumbre - MDP, L.E. Sucar
23 Incertidumbre - MDP, L.E. SucarIteración de Valor ¿Cuántas veces repetir la iteración? Normalmente el número de iteraciones para obtener la política óptima es menor que el requerido para que las utilidades converjan En la práctica, el número de iteraciones es relativamente pequeño Incertidumbre - MDP, L.E. Sucar
24 Incertidumbre - MDP, L.E. SucarIteración de valor Para evitar problemas de valores muy grandes (infinito) de la recompensa, normalmente se aplica un factor de descuento, 0
25 Ejemplo – utilidades de los estados0.812 0.868 0.912 0.762 0.660 0.705 0.655 0.611 0.338 Inicio Incertidumbre - MDP, L.E. Sucar
26 Ejemplo – política óptimaInicio Incertidumbre - MDP, L.E. Sucar
27 Incertidumbre - MDP, L.E. SucarPOMDP En muchos problemas reales, no se puede observar exactamente el estado del agente, por lo que se tiene un POMDP Además de los elementos de un MDP, un POMDP incluye: Una función de observación que especifica la probabilidad de las observaciones dado el estado, P(O|S) Una distribución de probabilidad inicial para los estados, P(S) Incertidumbre - MDP, L.E. Sucar
28 Incertidumbre - MDP, L.E. SucarPOMDP El enfoque exacto para resolver un POMDP consiste en considerar la distribución de probabilidad sobre los estados y en base a esta determinar las decisiones óptimas Para ello, se puede considerar un POMDP como un MDP en que los estados corresponden a la distribución de probabilidad El problema es que el espacio de estados se vuelve infinito y la solución exacta es muy compleja Incertidumbre - MDP, L.E. Sucar
29 Incertidumbre - MDP, L.E. SucarPOMDP Soluciones aproximadas: Asumir que el agente se encuentra en el estado más probable – se transforma en un MDP que se puede resolver por el método de iteración de valor Considerar un número finito de pasos y modelar el problema como una red de decisión dinámica – la aproximación depende del número de estados que se “ven” hacia delante (lookahead) Incertidumbre - MDP, L.E. Sucar
30 Incertidumbre - MDP, L.E. SucarEjemplo POMDP El robot detecta su posición con sonares Hay errores y ruido en las lecturas, alcance limitado Ciertas celdas son muy parecidas (1,2 – 3,2) Incertidumbre - MDP, L.E. Sucar
31 Incertidumbre - MDP, L.E. SucarAplicaciones Manejo de inventarios Mantenimiento de equipos y carreteras Control de sistemas de comunicaciones Modelado de procesos biológicos Planeación en robótica móvil Construcción de mapas / localización Control de procesos industriales Incertidumbre - MDP, L.E. Sucar
32 Control de una Planta Eléctrica utilizando MDPEjemplo de Aplicación Control de una Planta Eléctrica utilizando MDP
33 Incertidumbre - MDP, L.E. Sucar
34 Recuperador de calor con deareadorFlujo de agua Condensada DEAREADOR vapor de extracción de la turbina de vapor RECUPERADOR DE CALOR TANQUE DE OSCILACION Evaporador de Baja Presión líquido flujo de vapor saturado válvula de agua alim. Economizador Evaporador de Alta Presión DOMO flujo de agua de alimentación líquido Sobrecalentador bomba de recirculación alta presión by pass de atemperación Gases Calientes de Escape de la Turbina de Gas quemadores posteriores flujo de vapor sobrecalentado Recuperador de calor con deareador Incertidumbre - MDP, L.E. Sucar
35 Generador de vapor y domoIncertidumbre - MDP, L.E. Sucar
36 Incertidumbre - MDP, L.E. SucarEspacio de control Incertidumbre - MDP, L.E. Sucar
37 Resultados preliminaresIncertidumbre - MDP, L.E. Sucar
38 Arquitectura del ControlNuevo Set point Set point PID Planta ajuste MDP Incertidumbre - MDP, L.E. Sucar
39 Incertidumbre - MDP, L.E. SucarReferencias [Russell & Norvig] – Cap. 17 H. A. Taha, “Investigación de Operaciones”, Alfaomega, 1991 – Cap. 14 M. Puterman, “Markov Decision Processes”, Wiley, 1994. M. Agueda, P. Ibargüengoytia, “Control of a power plant using MDP and POMDP” (por publicarse). Incertidumbre - MDP, L.E. Sucar
40 Incertidumbre - MDP, L.E. SucarActividades Obtener los valores de utilidad para cada estado en el ejemplo del robot mediante el método de iteración de valor. Incertidumbre - MDP, L.E. Sucar