Proceso de decisión de Markov parcialmente observable

Generalización de un proceso de decisión de Markov.

Un proceso de decisión de Markov parcialmente observable ( POMDP ) ​​es una generalización de un proceso de decisión de Markov (MDP). Un POMDP modela un proceso de decisión de un agente en el que se supone que la dinámica del sistema está determinada por un MDP, pero el agente no puede observar directamente el estado subyacente. En cambio, debe mantener un modelo de sensor (la distribución de probabilidad de diferentes observaciones dado el estado subyacente) y el MDP subyacente. A diferencia de la función política del MDP, que asigna los estados subyacentes a las acciones, la política del POMDP es un mapeo de la historia de las observaciones (o estados de creencias) a las acciones.

El marco POMDP es lo suficientemente general como para modelar una variedad de procesos de decisión secuenciales del mundo real. Las aplicaciones incluyen problemas de navegación de robots, mantenimiento de máquinas y planificación en condiciones de incertidumbre en general. El marco general de los procesos de decisión de Markov con información imperfecta fue descrito por Karl Johan Åström en 1965 ^[1] en el caso de un espacio de estados discreto, y fue estudiado más a fondo en la comunidad de investigación de operaciones donde se acuñó el acrónimo POMDP. Posteriormente fue adaptado para problemas de inteligencia artificial y planificación automatizada por Leslie P. Kaelbling y Michael L. Littman . ^[2]

Una solución exacta a un POMDP produce la acción óptima para cada creencia posible en los estados del mundo. La acción óptima maximiza la recompensa esperada (o minimiza el costo) del agente en un horizonte posiblemente infinito. La secuencia de acciones óptimas se conoce como política óptima del agente para interactuar con su entorno.

Definición

Definicion formal

Un POMDP de tiempo discreto modela la relación entre un agente y su entorno. Formalmente, un POMDP es una tupla de 7 , donde ${\displaystyle (S,A,T,R,\Omega ,O,\gamma )}$

• ${\displaystyle S}$es un conjunto de estados,
• ${\displaystyle A}$es un conjunto de acciones,
• ${\displaystyle T}$es un conjunto de probabilidades de transición condicional entre estados,
• ${\displaystyle R:S\times A\to \mathbb {R} }$es la función de recompensa.
• ${\displaystyle \Omega }$es un conjunto de observaciones,
• ${\displaystyle O}$es un conjunto de probabilidades de observación condicional, y
• ${\displaystyle \gamma \in [0,1)}$es el factor de descuento.

En cada período de tiempo, el medio ambiente se encuentra en algún estado . El agente realiza una acción que hace que el entorno pase a un estado con probabilidad . Al mismo tiempo, el agente recibe una observación que depende del nuevo estado del entorno, y de la acción que se acaba de realizar , con probabilidad (o, a veces, dependiendo del modelo del sensor). Finalmente, el agente recibe una recompensa igual a . Luego se repite el proceso. El objetivo es que el agente elija acciones en cada paso de tiempo que maximicen su recompensa futura esperada con descuento: , donde está la recompensa obtenida en ese momento . El factor de descuento determina en qué medida se favorecen las recompensas inmediatas sobre las recompensas más distantes. Cuando al agente sólo le importa qué acción producirá la mayor recompensa inmediata esperada; cuando el agente se preocupa por maximizar la suma esperada de recompensas futuras. ${\displaystyle s\in S}$ ${\displaystyle a\in A}$ ${\displaystyle s'}$ ${\displaystyle T(s'\mid s,a)}$ ${\displaystyle o\in \Omega }$ ${\displaystyle s'}$ ${\displaystyle a}$ ${\displaystyle O(o\mid s',a)}$ ${\displaystyle O(o\mid s')}$ ${\displaystyle r}$ ${\displaystyle R(s,a)}$ ${\displaystyle E\left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\right]}$ ${\displaystyle r_{t}}$ ${\displaystyle t}$ ${\displaystyle \gamma }$ ${\displaystyle \gamma =0}$ ${\displaystyle \gamma \rightarrow 1}$

Discusión

Debido a que el agente no observa directamente el estado del medio ambiente, debe tomar decisiones bajo la incertidumbre del verdadero estado del medio ambiente. Sin embargo, al interactuar con el entorno y recibir observaciones, el agente puede actualizar su creencia en el estado verdadero actualizando la distribución de probabilidad del estado actual. Una consecuencia de esta propiedad es que el comportamiento óptimo a menudo puede incluir acciones (recopilación de información) que se toman simplemente porque mejoran la estimación del agente del estado actual, permitiéndole así tomar mejores decisiones en el futuro.

Es instructivo comparar la definición anterior con la definición de proceso de decisión de Markov . Un MDP no incluye el conjunto de observación, porque el agente siempre sabe con certeza el estado actual del entorno. Alternativamente, un MDP se puede reformular como un POMDP estableciendo que el conjunto de observaciones sea igual al conjunto de estados y definiendo las probabilidades condicionales de observación para seleccionar de manera determinista la observación que corresponde al estado verdadero.

Actualización de creencias

Después de haber realizado la acción y observar , un agente necesita actualizar su creencia en el estado en el que puede (o no) estar el entorno. Dado que el estado es markoviano (por suposición), mantener una creencia sobre los estados únicamente requiere conocimiento del estado anterior. estado de creencia, la acción tomada y la observación actual. La operación se denota . A continuación describimos cómo se calcula esta actualización de creencias. ${\displaystyle a}$ ${\displaystyle o}$ ${\displaystyle b'=\tau (b,a,o)}$

Después de alcanzarlo , el agente observa con probabilidad . Sea una distribución de probabilidad sobre el espacio de estados . denota la probabilidad de que el medio ambiente esté en el estado . Dado , luego de actuar y observar , ${\displaystyle s'}$ ${\displaystyle o\in \Omega }$ ${\displaystyle O(o\mid s',a)}$ ${\displaystyle b}$ ${\displaystyle S}$ ${\displaystyle b(s)}$ ${\displaystyle s}$ ${\displaystyle b(s)}$ ${\displaystyle a}$ ${\displaystyle o}$

${\displaystyle b'(s')=\eta O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)}$

donde es una constante de normalización con . ${\displaystyle \eta =1/\Pr(o\mid b,a)}$ ${\displaystyle \Pr(o\mid b,a)=\sum _{s'\in S}O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)}$

Creencia MDP

Un estado de creencia markoviano permite formular un POMDP como un proceso de decisión de Markov donde cada creencia es un estado. La creencia resultante MDP se definirá así en un espacio de estados continuo (incluso si el POMDP "originario" tiene un número finito de estados: hay infinitos estados de creencia (en ) porque hay un número infinito de distribuciones de probabilidad sobre los estados (de )). ^[2] ${\displaystyle B}$ ${\displaystyle S}$

Formalmente, la creencia MDP se define como una tupla donde ${\displaystyle (B,A,\tau ,r,\gamma )}$

• ${\displaystyle B}$es el conjunto de estados de creencias sobre los estados POMDP,
• ${\displaystyle A}$es el mismo conjunto finito de acciones que para el POMDP original,
• ${\displaystyle \tau }$es la función de transición del estado de creencia,
• ${\displaystyle r:B\times A\to \mathbb {R} }$es la función de recompensa en los estados de creencia,
• ${\displaystyle \gamma }$es el factor de descuento igual al del POMDP original. ${\displaystyle \gamma }$

De estos, es necesario derivar del POMDP original. es ${\displaystyle \tau }$ ${\displaystyle r}$ ${\displaystyle \tau }$

${\displaystyle \tau (b,a,b')=\sum _{o\in \Omega }\Pr(b'|b,a,o)\Pr(o|a,b),}$

donde es el valor obtenido en la sección anterior y ${\displaystyle \Pr(o|a,b)}$

${\displaystyle Pr(b'|b,a,o)={\begin{cases}1&{\text{if the belief update with arguments }}b,a,o{\text{ returns }}b'\\0&{\text{otherwise }}\end{cases}}.}$

La función de recompensa MDP de creencias ( ) es la recompensa esperada de la función de recompensa POMDP sobre la distribución del estado de creencias: ${\displaystyle r}$

${\displaystyle r(b,a)=\sum _{s\in S}b(s)R(s,a)}$.

La creencia MDP ya no es parcialmente observable, ya que en un momento dado el agente conoce su creencia y, por extensión, el estado de la creencia MDP.

Función de política y valor.

A diferencia del POMDP "originario" (donde cada acción está disponible en un solo estado), en el MDP de creencias correspondiente todos los estados de creencia permiten todas las acciones, ya que (casi) siempre tienes alguna probabilidad de creer que estás en cualquier estado (de origen). Como tal, especifica una acción para cualquier creencia . ${\displaystyle \pi }$ ${\displaystyle a=\pi (b)}$ ${\displaystyle b}$

Aquí se supone que el objetivo es maximizar la recompensa total descontada esperada en un horizonte infinito. Cuando se define un costo, el objetivo pasa a ser la minimización del costo esperado. ${\displaystyle R}$

La recompensa esperada por una política que parte de la creencia se define como ${\displaystyle \pi }$ ${\displaystyle b_{0}}$

${\displaystyle V^{\pi }(b_{0})=\sum _{t=0}^{\infty }\gamma ^{t}r(b_{t},a_{t})=\sum _{t=0}^{\infty }\gamma ^{t}E{\Bigl [}R(s_{t},a_{t})\mid b_{0},\pi {\Bigr ]}}$

¿Dónde está el factor de descuento? La política óptima se obtiene optimizando la recompensa a largo plazo. ${\displaystyle \gamma <1}$ ${\displaystyle \pi ^{*}}$

${\displaystyle \pi ^{*}={\underset {\pi }{\mbox{argmax}}}\ V^{\pi }(b_{0})}$

¿Dónde está la creencia inicial? ${\displaystyle b_{0}}$

La política óptima, denotada por , produce el valor de recompensa esperado más alto para cada estado de creencia, representado de manera compacta por la función de valor óptimo . Esta función de valor es la solución a la ecuación de optimización de Bellman : ${\displaystyle \pi ^{*}}$ ${\displaystyle V^{*}}$

${\displaystyle V^{*}(b)=\max _{a\in A}{\Bigl [}r(b,a)+\gamma \sum _{o\in \Omega }\Pr(o\mid b,a)V^{*}(\tau (b,a,o)){\Bigr ]}}$

Para los POMDP de horizonte finito, la función de valor óptimo es lineal por partes y convexa. ^[3] Puede representarse como un conjunto finito de vectores. En la formulación de horizonte infinito, un conjunto de vectores finitos puede aproximarse arbitrariamente, cuya forma permanece convexa. La iteración de valores aplica una actualización de programación dinámica para mejorar gradualmente el valor hasta la convergencia a una función de valor óptima y conserva su linealidad y convexidad por partes. ^[4] Al mejorar el valor, la política se mejora implícitamente. Otra técnica de programación dinámica llamada iteración de políticas representa y mejora explícitamente la política. ^{[5] [6]} ${\displaystyle V^{*}}$ ${\displaystyle \epsilon }$

Soluciones POMDP aproximadas

En la práctica, los POMDP suelen ser computacionalmente difíciles de resolver con exactitud. Esta intratabilidad se debe a menudo a la maldición de la dimensionalidad o a la maldición de la historia (el hecho de que las políticas óptimas pueden depender de toda la historia de acciones y observaciones). Para abordar estos problemas, los informáticos han desarrollado métodos que aproximan las soluciones para los POMDP. Estas soluciones normalmente intentan aproximarse al problema o la solución con un número limitado de parámetros, ^[7] planificar solo una pequeña parte del espacio de creencias en línea o resumir el historial de acción-observación de forma compacta.

Los algoritmos basados ​​en cuadrículas ^[8] comprenden una técnica de solución aproximada. En este enfoque, la función de valor se calcula para un conjunto de puntos en el espacio de creencias y se utiliza la interpolación para determinar la acción óptima a tomar para otros estados de creencias que se encuentran y que no están en el conjunto de puntos de la cuadrícula. Trabajos más recientes utilizan técnicas de muestreo, técnicas de generalización y explotación de la estructura del problema, y ​​han extendido la resolución de POMDP a grandes dominios con millones de estados. ^{[9] [10]} Por ejemplo, las cuadrículas adaptativas y los métodos basados ​​en puntos toman muestras de puntos de creencias alcanzables al azar para limitar la planificación a áreas relevantes en el espacio de creencias. ^{[11] [12]} También se ha explorado la reducción de dimensionalidad utilizando PCA . ^[13]

Los algoritmos de planificación en línea abordan los POMDP grandes mediante la construcción de una nueva política para la creencia actual cada vez que se recibe una nueva observación. Una política de este tipo sólo necesita considerar las creencias futuras alcanzables a partir de la creencia actual, que a menudo es sólo una parte muy pequeña del espacio total de creencias. Esta familia incluye variantes de la búsqueda de árbol de Monte Carlo ^[14] y la búsqueda heurística. ^[15] De manera similar a los MDP, es posible construir algoritmos en línea que encuentren políticas arbitrariamente cercanas a las óptimas y no tengan una dependencia directa de la complejidad computacional del tamaño del estado y los espacios de observación. ^[dieciséis]

Otra línea de técnicas de solución aproximada para resolver POMDP se basa en el uso (un subconjunto de) el historial de observaciones, acciones y recompensas anteriores hasta el paso de tiempo actual como un pseudoestado. Luego se pueden utilizar técnicas habituales para resolver MDP basadas en estos pseudoestados (por ejemplo, Q-learning ). Idealmente, los pseudoestados deberían contener la información más importante de toda la historia (para reducir el sesgo) y al mismo tiempo estar lo más comprimidos posible (para reducir el sobreajuste). ^[17]

Teoría POMDP

La planificación en el POMDP es, en general, indecidible . Sin embargo, se ha identificado que algunas configuraciones son decidibles (consulte la Tabla 2 en ^[18] que se reproduce a continuación). Se han considerado diferentes objetivos. Los objetivos de Büchi están definidos por autómatas de Büchi . La accesibilidad es un ejemplo de una condición de Büchi (por ejemplo, alcanzar un buen estado en el que todos los robots estén en casa). Los objetivos de coBüchi corresponden a trazas que no satisfacen una determinada condición de Büchi (por ejemplo, no llegar a un mal estado en el que algún robot murió). Los objetivos de paridad se definen mediante juegos de paridad ; Permiten definir objetivos complejos como alcanzar un buen estado cada 10 pasos. El objetivo se puede satisfacer:

• casi con seguridad, es decir, la probabilidad de satisfacer el objetivo es 1;
• positivo, es decir la probabilidad de satisfacer el objetivo es estrictamente mayor que 0;
• cuantitativo, es decir, la probabilidad de satisfacer el objetivo es mayor que un umbral determinado.

También consideramos el caso de memoria finita en el que el agente es una máquina de estados finitos y el caso general en el que el agente tiene una memoria infinita.

Aplicaciones

Los POMDP se pueden utilizar para modelar muchos tipos de problemas del mundo real. Las aplicaciones notables incluyen el uso de un POMDP en el tratamiento de pacientes con cardiopatía isquémica, ^[19] tecnología de asistencia para personas con demencia, ^{[9] [10]} la conservación de los tigres de Sumatra, en peligro crítico y difíciles de detectar ^[20] y aeronaves. evitación de colisiones. ^[21]

Una aplicación es un caso de enseñanza, un problema de llanto de un bebé, en el que un padre necesita decidir secuencialmente si alimentar al bebé basándose en la observación de si llora o no, lo cual es una representación imperfecta del estado real de hambre del bebé. ^{[22] [23]}

Referencias

1. Åström, KJ (1965). "Control óptimo de procesos de Markov con información de estado incompleta". Revista de Análisis y Aplicaciones Matemáticas . 10 : 174-205. doi : 10.1016/0022-247X(65)90154-X .
2. Kaelbling, LP, Littman, ML, Cassandra, AR (1998). "Planificar y actuar en dominios estocásticos parcialmente observables". Inteligencia artificial . 101 (1–2): 99–134. doi :10.1016/S0004-3702(98)00023-X.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. Sondik, EJ (1971). El control óptimo de procesos de Markov parcialmente observables (tesis doctoral). Universidad Stanford. Archivado desde el original el 17 de octubre de 2019.
4. Smallwood, RD, Sondik, EJ (1973). "El control óptimo de los procesos de decisión de Markov parcialmente observables en un horizonte finito". La investigación de operaciones . 21 (5): 1071–88. doi :10.1287/opre.21.5.1071.{{cite journal}}: CS1 maint: multiple names: authors list (link)
5. Sondik, EJ (1978). "El control óptimo de procesos de Markov parcialmente observables en el horizonte infinito: costo descontado". La investigación de operaciones . 26 (2): 282–304. doi :10.1287/opre.26.2.282.
6. Hansen, E. (1998). "Resolver POMDP mediante la búsqueda en el espacio de políticas". Actas de la Decimocuarta Conferencia Internacional sobre la Incertidumbre en la Inteligencia Artificial (UAI-98) . arXiv : 1301.7380 .
7. Hauskrecht, M. (2000). "Aproximaciones de funciones de valor para procesos de decisión de Markov parcialmente observables". Revista de investigación en inteligencia artificial . 13 : 33–94. arXiv : 1106.0234 . doi : 10.1613/jair.678 .
8. Lovejoy, W. (1991). "Límites computacionalmente factibles para procesos de decisión de Markov parcialmente observados". La investigación de operaciones . 39 : 162-175. doi :10.1287/opre.39.1.162.
9. Jesse Hoey; Axel von Bertoldi; Pascal Poupart; Álex Mihailidis (2007). "Ayudar a personas con demencia durante el lavado de manos mediante un proceso de decisión de Markov parcialmente observable". Proc. Congreso Internacional sobre Sistemas de Visión por Computador (ICVS) . doi :10.2390/biecoll-icvs2007-89.
10. Jesse Hoey; Pascal Poupart; Axel von Bertoldi; Tammy Craig; Craig Boutilier; Alex Mihailidis. (2010). "Asistencia automatizada para el lavado de manos para personas con demencia mediante vídeo y un proceso de decisión de Markov parcialmente observable". Visión por computadora y comprensión de imágenes (CVIU) . 114 (5): 503–519. CiteSeerX 10.1.1.160.8351 . doi :10.1016/j.cviu.2009.06.008. 
11. Pineau, J., Gordon, G., Thrun, S. (agosto de 2003). "Iteración de valor basada en puntos: un algoritmo en cualquier momento para POMDP" (PDF) . Conferencia Conjunta Internacional sobre Inteligencia Artificial (IJCAI). Acapulco, México . págs. 1025–32.{{cite conference}}: CS1 maint: multiple names: authors list (link)
12. Hauskrecht, M. (1997). "Métodos incrementales para calcular límites en procesos de decisión de Markov parcialmente observables". Actas de la 14ª Conferencia Nacional sobre Inteligencia Artificial (AAAI). Providencia, Rhode Island . págs. 734–739. CiteSeerX 10.1.1.85.8303 . 
13. Roy, Nicolás ; Gordon, Geoffrey (2003). "PCA familiar exponencial para la compresión de creencias en POMDP" (PDF) . Avances en los sistemas de procesamiento de información neuronal .
14. David Silver y Joel Veness (2010). Planificación Montecarlo en grandes POMDP . Avances en los sistemas de procesamiento de información neuronal.
15. Nan Ye, Adhiraj Somani, David Hsu y Wee Sun Lee (2017). "DESPOT: Planificación POMDP online con Regularización". Revista de investigación en inteligencia artificial . 58 . arXiv : 1609.03250 . doi : 10.1613/jair.5328 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
16. Michael H. Lim, Tyler J. Becker, Mykel J. Kochenderfer, Claire J. Tomlin y Zachary N. Sunberg (2023). "Garantías de optimización para la aproximación de la creencia de partículas de los POMDP". Revista de investigación en inteligencia artificial . 77 . arXiv : 2210.05015 . doi : 10.1613/jair.1.14525 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
17. Francois-Lavet, V., Rabusseau, G., Pineau, J., Ernst, D., Fonteneau, R. (2019). Sobre el sobreajuste y el sesgo asintótico en el aprendizaje por refuerzo por lotes con observabilidad parcial. Revista de Investigación en Inteligencia Artificial (JAIR) . vol. 65, págs. 1–30. arXiv : 1709.07796 .{{cite conference}}: CS1 maint: multiple names: authors list (link)
18. Chatterjee, Krishnendu; Chmelík, Martín; Tracol, Mathieu (1 de agosto de 2016). "Lo que es decidible sobre los procesos de decisión de Markov parcialmente observables con objetivos ω-regulares". Revista de Ciencias de la Computación y de Sistemas . 82 (5): 878–911. doi : 10.1016/j.jcss.2016.02.009 . ISSN  0022-0000.
19. Hauskrecht, M., Fraser, H. (2000). "Planificación del tratamiento de la cardiopatía isquémica con procesos de decisión de Markov parcialmente observables". Inteligencia artificial en medicina . 18 (3): 221–244. doi :10.1016/S0933-3657(99)00042-1. PMID  10675716.{{cite journal}}: CS1 maint: multiple names: authors list (link)
20. Chadès, I., McDonald-Madden, E., McCarthy, MA, Wintle, B., Linkie, M., Possingham, HP (16 de septiembre de 2008). "Cuándo dejar de gestionar o estudiar especies crípticas amenazadas". Proc. Nacional. Acad. Ciencia. EE.UU . 105 (37): 13936–40. Código bibliográfico : 2008PNAS..10513936C. doi : 10.1073/pnas.0805265105 . PMC 2544557 . PMID  18779594. {{cite journal}}: CS1 maint: multiple names: authors list (link)
21. Kochenderfer, Mykel J. (2015). "Evitación optimizada de colisiones aéreas". Toma de decisiones bajo incertidumbre . La prensa del MIT.
22. Kochenderfer, Mykel J.; Wheeler, Tim A.; Wray, Kyle H. (2022). Algoritmos para la toma de decisiones. Cambridge, Massachusetts; Londres, Inglaterra: MIT Press. pag. 678.ISBN​ 9780262047012.
23. Moss, Robert J. (24 de septiembre de 2021). "MIRAR: POMDP: Toma de decisiones en condiciones de incertidumbre POMDPs.jl. Problema del bebé que llora" (vídeo) . youtube.com . El lenguaje de programación Julia .

enlaces externos

• APPL, un solucionador POMDP rápido basado en puntos
• Controladores de estado finito que utilizan Branch-and-Bound Un solucionador POMDP exacto para políticas de tamaño acotado
• pomdp: Infraestructura para procesos de decisión de Markov parcialmente observables (POMDP), un paquete R que incluye una interfaz para el programa pomdp-solve de Tony Cassandra.
• POMDPs.jl, una interfaz para definir y resolver MDP y POMDP en Julia y Python con una variedad de solucionadores.
• pyPOMDP, una caja de herramientas (PO)MDP (simulador, solucionador, alumno, lector de archivos) para Python por Oliver Stollmann y Bastian Migge
• zmdp, un solucionador POMDP de Trey Smith