Sesión 12: Procesos de Decisión de Markov



Descargar 36,54 Kb.
Fecha de conversión07.02.2017
Tamaño36,54 Kb.

Sesión 12: Procesos de Decisión de Markov

  • Modelos Gráficos Probabilistas
  • L. Enrique Sucar
  • INAOE

Procesos de Decisión de Markov

  • Procesos 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)
  • Extensiones (abstracción, partición)
  • Aplicaciones

Problemas de decisión secuenciales

  • Problema 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)

Ejemplo – robot móvil

  • Inicio

Modelo 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

Modelo de Transición

  • Probabilidad dirección deseada – Pij=0.8
  • Probabilidad 2 direcciones vecinas – Pik=0.1

Modelo 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

MDP

POMDP

Polí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

Ejemplo de Política

  • Inicio

Controlador basado en un MDP

  • solución MDP
  • Controlador
  • Sistema
  • Modelo
  • Eventos
  • estado
  • acción
  • política

Procesos de Decisión de Markov

  • Problema 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
  • Otros métodos de solución son “iteración de política” (policy iteration) y programación lineal (al transformar el problema a un problema de optimización lineal)

Procesos de Decisión de Markov

  • Formalmente, 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)

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) ) =  P(Hi(p)) Uh Hi(p)

Utilidad

  • 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

Programación Dinámica

  • Dada 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 j P(sj | si,a) U(j)
  • La política óptima esta dada por la acción que de mayor utilidad:
  • P*(i) = arg maxa j P(sj | si,a) U(j)

Programación Dinámica

  • Si se tiene un número finito de pasos o estados terminales, 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)

PD – ejemplo robot

  • Si se define la función de utilidad como:
  • Uh = valor estado final – 1/25 x 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

Recompensa

  • -1/25
  • -1/25
  • -1/25
  • -1/25
  • -1/25
  • -1/25
  • -1/25
  • -1/25
  • -1/25
  • -1
  • +1

PD – ejemplo robot

  • Asumiendo que el robot está en el estado (3,3):
  • U(a=derecha) = [0.8*1-0.1*1/25 -0.1*1/25] = 0.792
  • U(a=abajo) = [0.1*1-0.8*1/25 -0.1*1/25] = 0.064
  • U(a=izq.) = [-0.1*1/25-0.8*1/25 -0.1*1/25] = -0.04
  • U(s33) = -1/25 + max [.792, .064, -.04] = 0.752; P*(s31) = derecha
  • 1
  • 2
  • 3
  • 1
  • 2
  • 3
  • 4

Valor

  • 0.752
  • -1
  • +1
  • 0.422

Ejemplo – planificación de trayectorias usando PD

  • Posición inicial
  • Meta

Ejemplo – primeras etapas

  • 0
  • 1
  • 1.4
  • 1
  • 1.4
  • 1
  • 2.4
  • 2.4
  • 2
  • 2

Ejemplo – llega a la posición inicial

  • 0
  • 1
  • 1.4
  • 1
  • 1.4
  • 1
  • 2.4
  • 2.4
  • 2
  • 2
  • 3
  • 3.4
  • 3
  • 3.4
  • 3.4
  • 3.8
  • 4.8
  • 4.4
  • 4.8
  • 4.4
  • 4.4
  • 5.8
  • 4
  • 6.8
  • 5.8
  • 5.4
  • 6.4
  • 6.8
  • 6.8
  • 7.8
  • 8.2
  • 7.8
  • 7.8
  • 8.2
  • 9.2
  • 8.8
  • 8.8
  • 9.2
  • 10.2
  • 9.8

Ejemplo – solución

  • 0
  • 1
  • 1.4
  • 1
  • 1.4
  • 1
  • 2.4
  • 2.4
  • 2
  • 2
  • 3
  • 3.4
  • 3
  • 3.4
  • 3.4
  • 3.8
  • 4.8
  • 4.4
  • 4.8
  • 4.4
  • 4.4
  • 5.8
  • 4
  • 6.8
  • 5.8
  • 5.4
  • 6.4
  • 6.8
  • 6.8
  • 7.8
  • 8.2
  • 7.8
  • 7.8
  • 8.2
  • 9.2
  • 8.8
  • 8.8
  • 9.2
  • 10.2
  • 9.8

Horizonte finito vs. infinito

  • Los 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, en general, de horizonte infinito y no se pueden resolver directamente por PD

Solución

  • Los métodos principales para resolver MDPs son:
  • Iteración de valor (Bellman, 57),
  • Iteración de política (Howards, 60),
  • Programación lineal (Puterman, 94).

MDPs – ecuaciones fundamentales

  • Función de valor (ecuación de Bellman):
  • V*(s) = maxa { R(s,a) +  s’ P(s’ | s, a) V*(s’) }
  • Política:
  • *(s) = arg maxa { R(s,a) +  s’ P(s’ | s, a) V*(s’) }
  • Donde  es un factor de descuento

Solución

  • Función de valor
  • Una política para un MDP es una asociación :SA (acción por estado).
  • Dada la política, el valor para horizonte finito es: Vn: S  
  • Vn(i) = R(i, (i)) +  P((i) | i,j) Vn-1(j)
  • Para horizonte infinito, generalmente se considera un factor de descuento, 0<=<1:
  • V(i) = R(i, (i)) +  P((i) | i,j) V(j)

Solución

  • Política óptima
  • La solución a un MDP da una política óptima.
  • Esto es, la política que maximiza la ecuación de Bellman:
  • *(i) = max [R(i, a) +  P(a | i,j) V*(j)]

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 j P(sj | si,a) Ut(j)
  • Cuando tinf, los valores de utilidad convergen a un valor estable

Iteración de Valor

  • Algoritmo:
    • Inicializar: Ut = Ut+1 = R
    • Repetir:
      • Ut=Ut+1
      • Ut+1(i) = R(i) + maxa j P(sj | si,a) Ut(j)
    • Hasta: | Ut-Ut+1 | < 

Iteració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

Iteración de valor

  • Para evitar problemas de valores muy grandes (infinito) de la recompensa, normalmente se aplica un factor de descuento, 0<<1, para el valor de los siguientes estados
  • El cálculo iterativo de la utilidad con el factor de descuento es entonces:
      • Ut+1(i) = R(i) + maxa  j P(sj | si,a) Ut(j)

Ejemplo – utilidades de los estados

  • Inicio
  • 0.812
  • 0.762
  • 0.868
  • 0.912
  • 0.660
  • 0.611
  • 0.705
  • 0.338
  • 0.655

Ejemplo – política óptima

  • Inicio

Iteración de Política

  • Empezando de cierta política (aleatoria), esta se mejora encontrando una acción por estado que tenga un mejor valor que la acción actual
  • Se puede usar conocimiento del problema para definir la política inicial
  • El proceso termina cuando ya no puede haber mejoras
  • Normalmente converge en menor número de iteraciones que iteración de valor, pero cada iteración es más costosa

Ejemplo –robot virtual

Política óptima

Otra configuración

Función de valor

POMDP

  • 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)

POMDP

  • 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

POMDP

  • 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
    • Aproximar la función de valor continua mediante curvas paramétricas aprovechando ciertas propiedades de dichas funciones
    • 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)

Ejemplo 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)

MDP como una RDD

  • St
  • St+1
  • St+2
  • St+3
  • at-1
  • rt
  • at
  • at+1
  • at+2
  • rt+1
  • rt+2

POMDP como una RDD

  • St
  • St+1
  • St+2
  • St+3
  • at-1
  • rt
  • O
  • O
  • O
  • O
  • at
  • at+1
  • at+2
  • rt+1
  • rt+2

Extensiones

  • El principal problema de los MDPs es el crecimiento de la complejidad al aumentar el número de estados y acciones. Para ello se han planteado:
  • Representaciones factorizadas
  • Representaciones abstractas (agregación de estados)
  • Modelos jerárquicos (serie / paralelo)

MDPs factorizados

  • El estado de descompone el en un conjunto de variables o factores
  • Esto permite utilizar representaciones basadas en modelos gráficos para reducir la complejidad del modelo de transición y de recompensa:
    • El modelo de transición se representa usando RBD (una RBD de 2 etapas por acción)
    • La función de recompensa se representa usando árboles de decisión (considerando sólo las variables relevantes)

MDP factorizado

  • X = {x1, x2, x3, x4, x5}
  • Se tiene una RBD por acción
  • x2
  • x3
  • x4
  • x5
  • x1
  • x2’
  • x3’
  • x4’
  • x5’
  • x1’
  • t
  • t+1
  • X
  • X’

MDP - factorizado

  • R
  • La función de recompensa
  • considera sólo las variables
  • que inciden directamente
  • x2
  • x3
  • x2
  • x3
  • x3
  • x2
  • x2
  • V1
  • V2
  • V3
  • V4
  • V5
  • V6

Diagramas de Decisión Algebraicos

    • Otra alternativa para representar en forma compacta M y R es mediante Diagramas de Decisión Algebraicos (SPUDD)

MDPs abstractos

  • Otra alternativa para reducir la complejidad es reducir el número de estados, agrupando estados con propiedades similares (recompensa, probabilidades de transición)
  • Esto también se puede aplicar a dominios continuos
  • La desventaja es que la solución puede ya no ser óptima

Estados abstractos (cualitativos)

  • x2
  • y
  • x
  • x1
  • y1
  • y2
  • y3
  • x3
  • x1, x2, x3, y1, y2, y3 son valores de referencia o corte
  • Q1=pos(x, x2), ~pos(x,x3), pos(y, y1), ~pos(y,y3).
  • Q2=pos(x, x1), ~pos(x,x2), pos(y, y1), ~pos(y,y3).
  • Q1
  • Q2

Refinamiento

  • Si la política obtenida no es satisfactoria, se pueden agregar particiones adicionales o desagrupar estados.
  • Q1
  • Q2
  • Q3
  • Q4
  • Q5
  • x1
  • x2
  • Q1-p1
  • Q2
  • Q3-p1
  • Q5
  • x1
  • x2
  • Q1-p2
  • Q3-p2-1
  • Q3-p2-1
  • Q4-p1
  • Q4-p2

Particiones

  • La otra alternativa para simplificar la solución de un MDP es “partir” el problema en subproblemas, de forma que se puede resolver c/u por separado y después “integrar la solución”
  • Dos principales enfoques:
    • serie: se descompone la tarea en subtareas de forma que cada es una submeta que hay que cumplir para alcanzar la meta global (p. ej. Heirarchical RL)
    • paralelo: se descompone el problema en subproblemas que puedan resolverse “independientemente” y ejecutarse en “paralelo” (p. ej. Parallel MDPs)

Aprendizaje de MDPs

  • Aprender el modelo:
    • En base a una exploración aleatoria del ambiente, se puede aprender el modelo de transición y la función de recompensa
  • Sin modelo:
    • Se aprende directamente la política explorando el ambiente (aprendizaje por refuerzo)
  • Enfoques híbridos

Aplicaciones

  • 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
  • Control de aviones

Ejemplo de Aplicación

  • Control de una Planta Eléctrica utilizando MDP

Generador de vapor y domo

Espacio de control

Ejemplo acciones

Variables relevantes

  • Flujo de agua
  • Flujo de vapor
  • Presión vapor
  • d
  • msv
  • fwv

Modelo de Transición

  • fms, fms_ref1
  • fms, fms_ref2
  • ffw, ffw_ref
  • d, d_ref
  • pd, pd_ref1
  • pd, pd_ref2
  • pd, pd_ref3
  • g, g_ref
  • fms, fms_ref1
  • fms, fms_ref2
  • ffw, ffw_ref
  • d, d_ref
  • pd, pd_ref1
  • pd, pd_ref2
  • pd, pd_ref3
  • g, g_ref
  •  
  • 0
  • +
  • -
  • 0
  • 0.33
  • 0.13
  • 0.01
  • +
  • 0.33
  • 0.82
  • 0.00
  • -
  • 0.33
  • 0.05
  • 0.99
  • acción: cerrar
  • válvula
  • Q'
  • t'

Asistente del Operador

  • Arquitectura
  • Data Base
  • Power Plant
  • Simulator
  • Operator Interface
  • Factored MDP
  • Operator
  • Process
  • Operator Assistant

Resultados

  • El modelo de transición se obtuvo de a partir del simulador

Resultados – comparación de un MDP plano con uno factorizado

  • State Space
  • S = 61 x 81 x 23 = 384 states
  • VAR
  • msf
  • fwf
  • pd
  • g
  • d
  • # Vals
  • 6
  • 2
  • 8
  • 2
  • 2
  • Variable discretization
  • Parameters enumerated
  • a0
  • a1
  • a2
  • a3
  • Total
  • Compilation time
  • Traditional MDP
  • 147456
  • 147456
  • 147456
  • 147456
  • 589824
  • 5.6 days
  • Factored MDP
  • 175
  • 175
  • 204
  • 204
  • 758
  • 2 mins
  • CPTs dimensions

Resultados – comparación con el control convencional

  • En algunos casos son similares, pero el MDP lleva
  • más rápidamente a la planta a un estado seguro.

Ejemplo de Aplicaciones

  • Coordinación de tareas en un robot móvil

Task Coordination

  • A complex robotic task, such as message delivery, requires several capabilities:
    • Path planning
    • Obstacle avoidance
    • Localization
    • Mapping
    • Person finding
    • Speech synthesis and recognition
    • Gesture generation

Task Coordination

  • Each task can be implemented fairly independent as a software module
  • Challenge: how to integrate and coordinate these modules so the robot performs the “best” actions in each situation
  • Our solution: MS-MDP –Multiply Sectioned Markov Decision Processes, that can be specified and solved independently, and executed concurrently to select the best actions according to the optimal policy

MS-MDPs

  • We partition the global task into a number of subtasks, so each subtask is assigned to an MDP an each one is solved independently
    • The actions for each MDP are independent and can be performed concurrently
    • There is no conflict bewteen the actions of different MDPs
    • All the MDPs have a common goal (reward)

MS-MDPs

  • We solve each MDP independently (off-line) and execute the optimal policy for each one concurrently (on-line)
  • The MDPs are coordinated by a common state vector – each only needs to consider the state variables that are relevant for its subtask, this reduces the complexity of the model
  • Each MDP only considers its actions, which implies a further reduction in complexity

MS-MDPs

  • Advantages:
    • Reduction in complexity
    • Easier to build or learn the models
    • Concurrent actions
    • Modularity
  • Current limitations:
    • No guarantee of global optimality
    • Does not consider action conflicts

Homer

  • RWI B-14 robot
  • Bumblebee stereo vision camera
  • LCD display – animated face
  • “Head” – pan tilt unit
  • Omnidirectional microphone
  • 4 on-board computers, interconnect with a 100Mbps LAN
  • Wireless comm. to external computers at 10Mbps

Homer: “head”

Homer: Software Architecture

Message Delivery

  • Homer explores the environment looking for a sender
  • A sender is detected by speech or vision
  • Homer asks for the receiver and sender name, and the message
  • Homer goes to the receiver expected location (model of the environment –map)
  • When the potential receiver is detected, Homer confirms and delivers the message
  • If not, it continues looking for the receiver or it aborts and looks for a new message
  • At the same time, Homer keeps localized in the map and will go home if its battery is low

Message Delivery – subtasks

  • Navigator
  • Dialogue manager
  • Gesture generator
  • Locali-
  • zation
  • User
  • Loc.
  • Speech
  • Gen.
  • N
  • D
  • G
  • Naviga-
  • tion
  • Gesture
  • Gen.

MDPs for message delivery

  • Navigator
    • Explore
    • Navigate
    • Localize
    • Get new goal
    • Go home
    • Wait
  • Dialogue
    • Ask
    • Confirm
    • Give message
  • Gesture
    • Neutral
    • Happy
    • Sad
    • Angry

State variables

  • Has message
  • Receiver name
  • Sender name
  • At location
  • Has location
  • Location unreachable
  • Receiver unreachable
  • Battery low
  • Uncertain location
  • Voice heard
  • Person close
  • Called Homer
  • Yes/No

Experiments

    • Person approached
      • D: ask
      • G: smile
    • Message received
      • N: navigate
      • D: mute
      • G: neutral
    • Position uncertain
      • N: localize

Experiments

    • Deliver message
      • N: wait
      • D: deliver
      • G: smile
    • Battery low-go home
      • N: go home

Demo 5: Homer’s video

Referencias

  • [Russell & Norvig] – Cap. 17
  • H. A. Taha, “Investigación de Operaciones”, Alfaomega, 1991 – Cap. 14
  • M. Puterman, “Markov Decision Processes”, Wiley, 1994.

Referencias

  • Blythe, J., 1999, Decision –Theoretic Planning. AAAI. AI Magazine, 37-54.
  • C. Boutilier, T. Dean, and S. Hanks. Decision-theoretic planning: structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1–94, 1999
  • D. Suc and I. Bratko. Qualitative reverse engineering. In Proceedings of the 19th International Conference on Machine Learning, 2000.
  • E. Morales. Scaling up reinforcement learning with a relation representation.pages 15–26. Proc. of the Workshop on Adaptability in Multi-agent Systems (AORC-2003), 2003.

Referencias

  • J. Hoey, R. St-Aubin, A. Hu, and C. Boutilier. Spudd: Stochastic planning using decision diagrams. In Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence, UAI-99, pages 279–288, 1999.
  • K. Forbus. Qualitative process theory. Artificial Intelligence, 24, 1984.
  • R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. 1998.

Referencias

  • P. Elinas, E. Sucar, A. Reyes and J. Hoey; A decision theoretic approach to task coordination in social robots, IEEE International Workshop on Robots and Human Interactive Communications RO-MAN 04; Japan 2004. Demo Videos.
  • A. Reyes, P. H. Ibarguengoytia, L. E. Sucar; Power Plant Operator Assistant: An Industrial Application of Factored MDPs; Mexican International Conference on Artificial Intelligence (MICAI-04); Mexico City; April 2004.
  • A. Reyes, L. E. Sucar, E. Morales, P. H. Ibarguengoytia; Abstract MDPs using Qualitative Change Predicates: An Application in Power Generation; Planning under Uncertainty in Real-World Problems Workshop. Neural Information Processing Systems (NIPS-03), Vancouver CA, Winter 2003. Poster.

Referencias

  • A. Reyes, L. E. Sucar, P. Ibarguengoytia; Power Plant Operator Assistant; Bayesian Modeling Applications Workshop in the 19th Conference on Uncertainty in Artificial Intelligence UAI-03, Acapulco-Mexico, August 2003.
  • A. Reyes, M.A. Delgadillo, P. H. Ibarguengoytia; An Intelligent Assistant for Obtaining the Optimal Policy during Operation Transients in a HRSG; 13th Annual Joint ISA POWID/ EPRI Controls and Instrumentation Conference; Williamsburg, Virginia, June 2003.
  • Ibargüengoytia P. H., Reyes A. 2001. Continuous Planning for The Operation of Power Plants, Memorias del Encuentro Nacional de Computación ENC 2001, Aguscalientes-Mexico.

Software

  • MDPs
    • Markov Decision Process (MDP) Toolbox v1.0 for MATLAB (INRIA) http://www.inra.fr/bia/T/MDPtoolbox/
    • Markov Decision Process (MDP) Toolbox for Matlab (K. Murphy) http://www.ai.mit.edu/~murphyk/Software/MDP/mdp.html
    • SPUDD http://www.cs.ubc.ca/spider/staubin/Spudd/

Actividades

  • Presentación proyecto final


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal