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 de política en MDP que mapea los estados subyacentes a las acciones, la política de POMDP es un mapeo 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 estado discreto, y se estudió más a fondo en la comunidad de investigación de operaciones donde se acuñó el acrónimo POMDP. Más tarde fue adaptado para detectar problemas en la inteligencia artificial y de planificación automática por Leslie P. Kaelbling y Michael L. Littman . [2]
Una solución exacta a un POMDP produce la acción óptima para cada posible creencia en los estados del mundo. La acción óptima maximiza (o minimiza) la recompensa (o costo) esperada del agente en un horizonte posiblemente infinito. La secuencia de acciones óptimas se conoce como la 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, dónde
- es un conjunto de estados,
- es un conjunto de acciones,
- es un conjunto de probabilidades de transición condicionales entre estados,
- es la función de recompensa.
- es un conjunto de observaciones,
- es un conjunto de probabilidades de observación condicionales, y
- es el factor de descuento.
En cada período de tiempo, el medio ambiente se encuentra en algún estado . El agente toma una acción, lo que hace que el medio ambiente cambie al estado con probabilidad . Al mismo tiempo, el agente recibe una observación que depende del nuevo estado del medio ambiente, y sobre la acción que se acaba de realizar, , con probabilidad (o algunas veces dependiendo del modelo de sensor). Finalmente, el agente recibe una recompensa. igual a . Entonces el proceso se repite. El objetivo es que el agente elija acciones en cada paso de tiempo que maximicen su recompensa futura esperada con descuento:, dónde es la recompensa ganada en el momento . El factor de descuentodetermina cuánto se favorecen las recompensas inmediatas sobre las recompensas más distantes. Cuándoel agente solo se preocupa por qué acción producirá la mayor recompensa inmediata esperada; Cuándo el agente se preocupa por maximizar la suma esperada de recompensas futuras.
Discusión
Debido a que el agente no observa directamente el estado del medio ambiente, el agente 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 real 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, lo que le permite tomar mejores decisiones en el futuro.
Es instructivo comparar la definición anterior con la definición de un proceso de decisión de Markov . Un MDP no incluye el conjunto de observación, porque el agente siempre conoce con certeza el estado actual del entorno. Alternativamente, un MDP puede reformularse como un POMDP estableciendo el conjunto de observaciones para que sea igual al conjunto de estados y definiendo las probabilidades condicionales de observación para seleccionar determinísticamente la observación que corresponde al estado verdadero.
Actualización de creencias
Después de haber tomado la acción y observando , un agente necesita actualizar su creencia en el estado en el que el entorno puede estar (o no). Dado que el estado es markoviano (por suposición), mantener una creencia sobre los estados solo requiere el conocimiento del estado de creencia anterior, 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.
Después de alcanzar , el agente observa con probabilidad . Dejar ser una distribución de probabilidad sobre el espacio de estados . denota la probabilidad de que el medio ambiente esté en estado . Dado, luego, después de tomar medidas y observando ,
dónde es una constante normalizadora con .
Creencia MDP
Un estado de creencias de Markov permite que un POMDP se formule como un proceso de decisión de Markov en el que cada creencia es un estado. La creencia resultante MDP se definirá así en un espacio de estado continuo (incluso si la POMDP "originaria" 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]
Formalmente, la creencia MDP se define como una tupla dónde
- es el conjunto de estados de creencias sobre los estados POMDP,
- es el mismo conjunto finito de acciones que para el POMDP original,
- es la función de transición del estado de creencias,
- es la función de recompensa en los estados de creencias,
- es el factor de descuento igual al en el POMDP original.
De estos, y deben derivarse del POMDP original. es
dónde es el valor derivado en la sección anterior y
La función de recompensa de la creencia MDP () es la recompensa esperada de la función de recompensa POMDP sobre la distribución del estado de creencias:
.
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 desde un solo estado), en el MDP de creencias correspondiente todos los estados de creencias 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 por cualquier creencia .
Aquí se asume que el objetivo es maximizar la recompensa total descontada esperada en un horizonte infinito. Cuándo define un costo, el objetivo se convierte en la minimización del costo esperado.
La recompensa esperada por la política partiendo de la creencia Se define como
dónde es el factor de descuento. La política óptima se obtiene optimizando la recompensa a largo plazo.
dónde es la creencia inicial.
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 optimalidad de Bellman :
Para 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 aproximarsearbitrariamente de cerca, cuya forma permanece convexa. La iteración de valor aplica una actualización de programación dinámica para mejorar gradualmente el valor hasta la convergencia a un-Función de valor óptimo, 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 explícitamente y mejora la política en su lugar. [5] [6]
Soluciones POMDP aproximadas
En la práctica, los POMDP a menudo son difíciles de resolver desde el punto de vista computacional, por lo que los científicos informáticos han desarrollado métodos que se aproximan a las soluciones para los POMDP. [7]
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 la interpolación se usa 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. El trabajo más reciente hace uso de técnicas de muestreo, técnicas de generalización y explotación de la estructura del problema, y ha 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 muestrean puntos de creencias alcanzables al azar para restringir la planificación a áreas relevantes en el espacio de creencias. [11] [12] También se ha explorado la reducción de la dimensionalidad utilizando PCA . [13]
Teoría POMDP
La planificación en POMDP es indecidible en general. Sin embargo, se ha identificado que algunos entornos son decidibles (consulte la Tabla 2 en, [14] reproducida a continuación). Se han considerado diferentes objetivos. Los objetivos de Büchi están definidos por los autómatas de Büchi . La accesibilidad es un ejemplo de una condición 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 alcanzar un mal estado en el que murió algún robot). Los objetivos de paridad se definen mediante juegos de paridad ; Permiten definir objetivos complejos de tal manera que alcanzan un buen estado cada 10 pasos de tiempo. El objetivo se puede cumplir:
- casi con seguridad, esa es 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 dado.
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.
Objetivos | Casi seguro (memoria infinita) | Casi seguro (memoria finita) | Positivo (inf. Mem.) | Positivo (mem. Finita) | Cuantitativo (inf. Mem) | Cuantitativo (memoria finita) |
---|---|---|---|---|---|---|
Büchi | EXPTIME -completo | EXPTIME-complete | indecidible | EXPTIME-complete [14] | indecidible | indecidible |
coBüchi | indecidible | EXPTIME-complete [14] | EXPTIME-complete | EXPTIME-complete | indecidible | indecidible |
paridad | indecidible | EXPTIME-complete [14] | indecidible | EXPTIME-complete [14] | indecidible | indecidible |
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 manejo de pacientes con cardiopatía isquémica, [15] tecnología de asistencia para personas con demencia, [9] [10] la conservación de tigres de Sumatra en peligro crítico y difíciles de detectar [16] y aviones. evitación de colisiones. [17]
Referencias
- ^ Åström, KJ (1965). "Control óptimo de los 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 .
- ^ a b Kaelbling, LP, Littman, ML, Cassandra, AR (1998). "Planificación y actuación en dominios estocásticos parcialmente observables". Inteligencia artificial . 101 (1-2): 99-134. doi : 10.1016 / S0004-3702 (98) 00023-X .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Sondik, EJ (1971). El control óptimo de procesos de Markov parcialmente observables (tesis doctoral). Universidad Stanford.
- ^ Smallwood, RD, Sondik, EJ (1973). "El control óptimo de los procesos de decisión de Markov parcialmente observables en un horizonte finito". Investigación operativa . 21 (5): 1071–88. doi : 10.1287 / opre.21.5.1071 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Sondik, EJ (1978). "El control óptimo de los procesos de Markov parcialmente observables en el horizonte infinito: costo descontado". Investigación operativa . 26 (2): 282-304. doi : 10.1287 / opre.26.2.282 .
- ^ Hansen, E. (1998). "Resolver POMDP mediante la búsqueda en el espacio de políticas". Actas de la XIV Conferencia Internacional sobre Incertidumbre en Inteligencia Artificial (UAI-98) . arXiv : 1301.7380 .
- ^ 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. doi : 10.1613 / jair.678 .
- ^ Lovejoy, W. (1991). "Límites computacionalmente factibles para procesos de decisión de Markov parcialmente observados". Investigación operativa . 39 : 162-175. doi : 10.1287 / opre.39.1.162 .
- ^ a b Jesse Hoey; Axel von Bertoldi; Pascal Poupart; Alex Mihailidis (2007). "Ayudar a las personas con demencia durante el lavado de manos mediante un proceso de decisión de Markov parcialmente observable". Proc. Congreso Internacional de Sistemas de Visión por Computador (ICVS) . doi : 10.2390 / biecoll-icvs2007-89 .
- ^ a b Jesse Hoey; Pascal Poupart; Axel von Bertoldi; Tammy Craig; Craig Boutilier; Alex Mihailidis. (2010). "Asistencia automatizada de lavado de manos para personas con demencia mediante vídeo y un proceso de decisión de Markov parcialmente observable". Visión por Computador 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 .
- ^ 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 Internacional Conjunta sobre Inteligencia Artificial (IJCAI). Acapulco, México . págs. 1025–32.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ 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 de Inteligencia Artificial (AAAI). Providence, RI . págs. 734–739. CiteSeerX 10.1.1.85.8303 .
- ^ Roy, Nicholas ; Gordon, Geoffrey (2003). "PCA familiar exponencial para la compresión de creencias en POMDP" (PDF) . Avances en sistemas de procesamiento de información neuronal .
- ^ a b c d e Chatterjee, Krishnendu; Chmelík, Martin; 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 Sistemas . 82 (5): 878–911. doi : 10.1016 / j.jcss.2016.02.009 . ISSN 0022-0000 .
- ^ 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 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Chadès, I., McDonald-Madden, E., McCarthy, MA, Wintle, B., Linkie, M., Possingham, HP (16 de septiembre de 2008). "Cuándo dejar de manejar o vigilar especies crípticas amenazadas" . Proc. Natl. Acad. Sci. USA . 105 (37): 13936–40. Código bibliográfico : 2008PNAS..10513936C . doi : 10.1073 / pnas.0805265105 . PMC 2544557 . PMID 18779594 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Kochenderfer, Mykel J. (2015). "Evitación optimizada de colisiones aerotransportadas" . Toma de decisiones bajo incertidumbre . La prensa del MIT.
enlaces externos
- Páginas POMDP de Tony Cassandra con un tutorial, ejemplos de problemas modelados como POMDP y software para resolverlos.
- pomdp: Solver for Partially Observable Markov Decision Processes (POMDP) un paquete R que proporciona una interfaz para el solver POMDP de Tony Cassandra.
- zmdp , un solucionador de POMDP de Trey Smith
- APPL , un solucionador de POMDP rápido basado en puntos
- SPUDD , un solucionador MDP estructurado factorizado (PO) que utiliza diagramas de decisión algebraicos (ADD).
- pyPOMDP , una caja de herramientas MDP (PO) (simulador, solucionador, alumno, lector de archivos) para Python por Oliver Stollmann y Bastian Migge
- Controladores de estado finito que utilizan un solucionador POMDP exacto para políticas de tamaño limitado
- POMDPs.jl , una interfaz para definir y resolver MDP y POMDP en Julia con una variedad de solucionadores.