Proceso de Decisión (POMDP)

Un proceso de decisión de Markov parcialmente observable POMDP (Partially Observable Markov Decision Process) ​​es una generalización de un MDP junto a un modelo oculto de Markov HMM. La primera referencia publicada que plantea de forma explícita un problema POMDP,  fue la de A.W. Drake en 1.962, posteriormente Karl Johan Åström en 1.965 lo describe, acuñándose más tarde el acrónimo POMDP.

Proceso de decisión de Markov parcialmente observable POMDP (Partially Observable Markov Decision Process)
Proceso de decisión de Markov parcialmente observable – POMDP

 

Un POMDP es un modelo probabilístico para la toma de decisiones secuenciales bajo incertidumbre, donde el estado solo puede estimarse a partir de observaciones. Su propósito es obtener una política que describa cómo cambian los estados mediante la elección (ejecución) de acciones óptimas para cada estado de creencia, de tal forma que se propongan planes para mejorar el estado a lo largo del tiempo. Este trabajo lo realiza el denominado “Agente”, él es quién elije las acciones en cada paso de tiempo, tratando de maximizar su recompensa, y en la realidad siempre en un horizonte temporal acotado. Se aplican fundamentalmente en campos donde la toma de decisiones se realiza con incertidumbre, por ejemplo en la inteligencia artificial.

 

Existen dos tipos de PODMP, los de horizonte finito que son completos para PSPACE  y pueden ser con o sin recompensa y los POMDP de horizonte infinito que son indecidibles y tienen recompensa.

 

Antes de continuar, debemos tener en cuenta que estos procesos son de alta complejidad computacional y según crece el nº de variables (estados), el tiempo de proceso puede llegar a ser inasumible y “lo mejor de todo”, pocos de ellos pueden resolverse exactamente y el resto quizás no tengan solución.

 

 

Descripción del modelo.

Un Proceso de Decisión (POMDP) es un modelo probabilístico que puede ser representado por la siguiente notación y elementos:  (E, A, P, R, Ω, O, θ, λ), donde:

 

N: Número de estados.

M: Número de acciones.

t: Tiempo

E: Conjunto finito de estados ocultos, E = {e1, …, en }.  El estado en el tiempo t se denota por Et. La transición de E puede verse como  (ei  → ej ) o ( ee’). Igual que en MDP.

A: Conjunto finito de acciones posibles que se pueden tomar en cualquier estado, A = {a1, a2, . . . , am}. Igual que en MDP.

P ↔ P(e’|e,a):

Probabilidades de transición de estados. Definen cómo las acciones cambian los estados del sistema. Representa la probabilidad de obtener el estado e’ cuando se realiza la acción a ∈ A partiendo del estado e. También lo podemos ver como:

 

Se supone que los pij(a) son conocidos, pero el estado ei no se conoce en el tiempo de decisión, que se infiere de la observación.

Igual que en MDP. En la literatura se la encuentra representada tanto por P como por T.

R: a × e → R:

Función de recompensa que puede variar para cada estado-acción. La recompensa en la acción a ∈ A  en la transición de ei a ej se denota como rij (a).

 

 

: Es el conjunto finito de M observaciones que se pueden hacer;  = {o1, o2, …, oM}. La observación en el tiempo t se denota por t.

O: Observaciones.

ø ↔ P(o|e’,a):

Probabilidades de observación. Define cuáles observaciones aparecen cuando el sistema se encuentra en un estado e’ determinado, al haber ejecutado la acción a. Describe la relación entre las observaciones, los estados del proceso y las acciones

 

γ ∈ [0, 1]:

Es un factor de descuento aplicable en la Recompensa. El factor de descuento asegura que la recompensa a corto plazo se considere más importante que la recompensa recibida mucho más tarde, haciendo que la noción de una política óptima esté bien definida.

 

π:

Política, trata de encontrar las acciones que maximizan el valor de la función. Una opción que facilita esta búsqueda, aunque da resultados aproximados, es restringir el espacio de políticas a través de controladores de estado finito (FSC, Finite State Controllers) que proporcionan un equilibrio entre las elecciones de acción y la capacidad de controlar fácilmente la complejidad del espacio de políticas que se busca.

 

 

Evolución temporal.

El modelo transita de la siguiente forma:

 

  1. En cada (época) período de tiempo t, el sistema está en un estado e ∈ E. El agente elige una acción a ∈ A, que hace que el entorno pase al estado e’ ∈ E con probabilidad P (e’ | e, a).
  2. Al mismo tiempo, el agente recibe una observación o ∈ O que depende del nuevo estado del entorno con probabilidad θ (o | e’, a).
  3. Al final de estos dos pasos el agente recibe una recompensa R (a, e).

Los procesos anteriores se repiten hasta que el agente toma una decisión, eligiendo acciones en cada paso de tiempo que maximicen su recompensa.

 

Agente.

En Proceso de Decisión (POMDP), hay un Agente o varios que actúan de forma similar a como se indicó en MDP, su objetivo es maximizar la recompensa que el sistema le proporcionará eligiendo las acciones apropiadas.

 

En POMDP los estados no son observables, por tanto no se pueden elegir acciones en función de esos estados (evidente), de modo que el Agente tiene que considerar una historia (h) completa de sus acciones y observaciones pasadas para elegir su acción actual, se la representa como:

ht = { a0, Ω1, … , at−1, Ωt }.

 

Para poder trabajar con esa historia (acciones y observaciones), se la resume en una distribución de probabilidad sobre el estado E, a este resultado se le denomina estado de creencia c, que se representa como:

ct(e) = P(et = e  | Ωt, at−1 , Ωt−1 , … , a0, c0).

donde:

0 ≤  ct(e)  ≤ 1. Probabilidad de que el proceso esté en el estado Et = e dada la distribución de creencias c.

 

El estado de creencia c facilita las cosas al Agente, así sus acciones se basan en ct, la creencia actual. Para llegar a este ct se parte del estado de creencia inicial c0, (es el conocimiento sobre el estado inicial del entorno). Después, cualquier creencia ct podrá calcularse con la creencia anterior ct-1, utilizando la acción previa at-1 y la observación actual t. Para ello se utiliza una función de actualización de creencia representada por:

ψ (c, a, Ω)

donde:

ct (e) = ψ (ct-1, at − 1, Ωt)

dentro de la función de actualización se utiliza P(Ω | c, a), la probabilidad de observar  después de realizar la acción a en la creencia c, actúa como una constante de normalización de modo que ct sigue siendo una distribución de probabilidad.

 

El siguiente paso es, cómo elegir una acción basada en esta creencia, para ello se utiliza la política π del Agente, esta política especifica la probabilidad de ejecución de cualquier acción en cualquier estado de creencia.

 

Con la creencia c, el Agente elegirá una acción basada en ella y que está determinada por su política π (describe de su comportamiento entre estados y acciones), esta política define la estrategia del Agente para cualquier situación que pueda encontrar, siendo el objetivo de π maximizar la cantidad de recompensa a obtener en el tiempo (finito o infinito). La política π es (ct, a), la probabilidad de que la acción a se realice en la creencia ct, según lo señalado en su política π.

 

Sólo queda por ver cómo se obtiene la recompensa, la función RC (c, a) especifica la recompensa esperada después de ejecutar la acción a en la creencia c de acuerdo con la función de recompensa R:

RC (c,a) = e∈E  c(e) R(e,a)

 

Esta es, a “groso modo”, la forma de actuar del Agente. Existen varias corrientes de software desarrollado para programarlos, todas ellas tratan de que el Agente sea verdaderamente inteligente.

 

 

Las fórmulas.

Es imposible terminar este artículo sin algunas de sus fórmulas, aquí están. Para seguir profundizando la mejor opción es leer lo publicado por las personas que las han hecho posible.

Creencia.

La creencia resultante usando la regla de Bayes:

 

 

 

donde la probabilidad de observar o después de ejecutar la acción a en la creencia c :

 

 

 

POMDP de horizontes infinitos.

Criterio de optimización para los que utilizan γ (descuento):

 

 

 

Para una política determinada π, la recompensa con descuento esperada Vπ(c) obtenida al ejecutar π a partir de c se define como:

 

 

donde:

recompensa esperada al ejecutar π (ct) en la creencia ct

 

Para la política óptima π, satisface la ecuación de optimización de Bellman:

 

 

 

POMDP de horizontes finitos.

Criterio de optimización para los que utilizan γ (descuento):

 

 

 

Para una política determinada π, la recompensa con descuento esperada Vπ(c) obtenida al ejecutar π a partir de c se define como:

 

 

 

 

 

 

Métodos y Técnicas relacionadas para PO-MDP.

? Pulsar en la cabecera de la columna para Clasificar.

 

Métodos y Técnicas relacionadas para PO – MDP
Fecha Nombre Autor Notas
Moore-Mealy Autómatas de estado finito en los que se basan los FSC.
FSC (Finite State Controllers) Controlador. Proporcionan una forma simple de representar las políticas de los POMDP. Cada agente es representado por un controlador.
MCTS (Monte-Carlo Tree Search)
Algoritmo. Combina un enfoque de árbol de búsqueda con simulaciones de Monte Carlo.
1.977 LTL (Linear Time Logic) Amir Pnueli Marco teórico. Basado en la lógica (Aristóteles). Se aplica en la prueba de programas de computación y en la codificación de fórmulas sobre el futuro de los caminos a seguir.
1.977 COL (Concurrent Object Languages) C. Hewitt Entorno de programación, ancestro-precursor de los lenguajes para agentes.
1.976± DL(Dynamic Logic) V. Pratt Marco teórico. Lógica de programación para “hablar y razonar sobre estados de cosas, procesos, cambios y resultados”.
1.979± PDL(Propositional Dynamic Logic) M. Fischer y R. Ladner Marco teórico que describe las propiedades de la interacción entre programas y proposiciones que son independientes del dominio de la computación. Desarrollado desde 1.959 por J. Yanov, E. Engeler 1.967, C. Hoare 1.969, A. Salwicki  1970, V. Pratt  (DL) 1.976 y otros.
1.980± BDI (Belief-Desire-Intention) Daniel Dennett, John Searle, Michael Bratman y otros. Marco teórico (Creencia-Deseo-Intención.). Entorno de programación para el desarollo de Agentes.
1.980± PRS (Procedural Reasoning System)
Michael Georgeff, Amy L. Lansky y François F. Ingrand Agente. Evolución de BSI. Sistema de razonamiento para entornos de programación
1.981 CTL (Computation tree logic)
E.M. Clarke y E. A. Emerson Entorno de programación. Lenguaje que permite describir las propiedades de cálculo de un árbol. Pertenece a la familia de los LTL (Linear-Time Logic).
1.988 IRMA (Intelligent Resource-Bounded Machine Architecture)
M. E. Bratman, D. J. Israel y M. E. Pollack Entorno de programación. Agente basado en BDI.
1.990 AOP (Agent-Oriented Programming)
Y. Shoham Marco teórico. Lenguaje de programación. Agente.
1.991 AGENT-0
Y. Shoham Lenguaje de programación basado en AOP.
1.992 ABLE (Agent Behaviour Language)
D. Connah y P. Wavish Entorno de programación para el desarrollo de agentes múltiples.
1.992 OASIS Fah-Chun Cheong Entorno de programación para el desarrollo de agentes múltiples.
1.993 PLACA (Planning Communicating Agents)
R. S. Thomas Entorno de programación. Lenguaje experimenal evolucionado de AOP.
1.994 PCTL (Probabilistic Computation Tree Logic)
Hans Hansson y Bengt Jonsson Algoritmo. Extiende el algoritmo CTL a las  DTMC (Cadenas de Markov de tiempo discreto)
1.994 UM-PRS (University of Michigan PRS) Jaeho Lee, Marcus J. Huber, Patrick G. Kenny y Edmund H. Durfee Entorno de programación. Derivado de PRS para construir agentes. Hermano de JAM.
1.994 APRIL
F. G. MCabe y  K. L. Clark Entorno de programación para el desarrollo de agentes múltiples.
1.994 MAIL
H. Haugeneder, D. Steiner y F. G. MCabe Entorno de programación para el desarrollo de agentes múltiples.
1.994 Witness
Michael L. Littman Algoritmo.
1.994 METATEM M. Fisher Entorno de programación. Lenguaje interpretado y concurrente.
1.995 QMDP Michael L. Littman, Anthony R.Cassandra y Leslie P. Kaelbling Algoritmo.
1.995 Open PRS
Félix Ingrand Agente. Es una versión basada en C-PRS y Propice. Los fuentes son de libre disposición.
1.995 RTDP (Real-Time DP) Andrew G. Barto, Steven J. Bradtke y Satinder P. Singh Algoritmo. En línea.
1.996 AgentSpeak (L) Anand S. Rao Entorno de programación. Derivada del modelo PRS para arquitecturas BDI.
1.997 SCS (Structured Circuit Semantics)
Joeh Lee y Edmund H. Durfee Agente. Semántica que puede representar el comportamiento sistemas de control.
1.997 BI-POMDP (Bounded, incremental POMDP) Richard Washington Algoritmo. En línea.
1.998 BDI-CTL Anand S. Rao y Michael P. Georgeff Marco teórico. Agente. Hídrido BDI y CTL
1.998 MABS (Multi-Agent-Based Simulation) Jaime S. Sichman, Rosaria Conte y Nigel Gilbert Agente
1.998 PI (Policy Iteration)
E. A. Hansen Controlador de estado finito.
1.999 JAM Marcus J. Huber Entorno de programación. Para el desarrollo de Agentes. Híbrido PRS y SCS. Hermano de UM-PRS. Disponibles los fuentes en Java.
1.999 F-POMDP-BSS (Factored POMDP using Belief State Simplification)
David Allen Mcallester y Satinder Singh Algoritmo. En línea.
2.000 FIB (Fast Informed Bound) Milos Hauskrecht Algoritmo.
2.002 ADL (Agent Dynamic Logic). Wayne Wobcke Agente. Modelo similar a PRS, combina aspectos de CTL, PDL y BDI-CTL
2.000 LORA(Logic Of Rational Agents) Michael Wooldridge Agente. Derivado de BDI-CTL. Puede intervenir en la comunicación e interacciones en un sistema de agentes múltiples.
2.000 DEC-POMDP (Decentralized POMDP)
Daniel.S.Bernstein, R.Givan, N. Immerman y S. Zilberstein Agente. Es una generalización de un POMDP. Se aplica a problemas que necesitan de múltiples agentes. Muchas versiones utilizan internamente los FSC.
2.001 ACS (Agent-Centered Search )
Sven Koenig Agente. En línea.
2.001 CL (Coalition Logic)
Marc Pauly Agente.
2.002 MPOMDP (Multiagent POMDP) David V. Pynadath y Milind Tambe Marco teórico.
2.003 JESP (Joint Equilibrium Search for Policies) Ranjit Nair, Milind Tambe, Makoto Yokoo y David V. Pynadath Algoritmo. Agente. Método que garantiza encontrar una política conjunta localmente óptima.
2.003 PBVI (Point-based Value Iteration) Joelle Pineau, Geoff Gordon y Sebastian Thrun Algoritmo. Basado en puntos de horizonte finito. Provee una solución de valor exacto rastreando el valor de un conjunto pequeño de puntos de creencia y su derivada para esos punto.
2.003 BPI (Bounded Policy Iteration) Pascal Poupart y Craig Boutilier Algoritmo que combina los dos controladores más utilizados en FSC: el PI y el del ascenso de gradiente GA (gradient ascent).
2.004 I-POMDP (Interactive-POMDP) Piotr J. Gmytrasiewicz y Prashant Doshi Marco teórico. Planificación de la cooperacion de múltiples agentes. Se desarrolla posteriormente con I-PF e I-PBVI. La complejidad de la solución crece exponencialmente con el número de agentes.
2.004 ATL (Alternating-time Temporal Logic)
R. Alur, T. A. Henzinger y O. Kupferman. Marco teórico. Extensión de CTL para múltiples agentes.
2.004 BBSLS-POMDP (Belief-Based SLS-Stochastic Local Search)
Darius Braziunas y Craig Boutilier Híbrido.
2.005 DP-JESP (Dynamic Programming – JESP) LID-JESP(Locally Interacting Distributes – JESP) Ranjit Nair Algoritmo. Utiliza el principio de optimización de Bellman.
2.005 Jadex Alexander Pokahr, Lars Braubach  y Winfried Lamersdorf Agente. Entorno de desarrollo software para la creación de agentes orientados a objetivos siguiendo el modelo BDI. Los fuentes son de libre disposición.
2.005 VDCBPI (Value Directed Compression BPI) Pascal Poupart y Craig Boutilier Anticipado.
2.005 Perseus (Randomized Point-based
Value Iteration for POMDP)
Matthijs T. J. Spaan y Nikos Vlassis Algoritmo. Basado en PBVI de horizonte finito.
2.005 SOVI (Simple Online Value Iteration)
Guy Shani, Ronen I. Brafman y Solomon E. Shimony En línea.
2.005 ADCOP (Adopt Distributed Constraint Optimization Problem)
Pragnesh JayModi, Wei-MinShen y Makoto Yokoo Agente. Derivado de DCOP (1.980). Permite especificar restricciones.
2.005 HSVI (Heuristic Search Value Iteration) y HSVI2 Trey Smith y Reid Simmons Algoritmo Anticipado. Basado en PBVI. Horizonte finito. Mantiene los límites superior e inferior en la función de valor óptimo. Obtiene una política con un límite pequeño de incertidumbre respecto a la política óptima.
2.005 HPB (Hybrid-POMDP-BDI) Ranjit Nair y Milind Tambe Híbrido
2.005 RTBSS (Real-Time Belief Space Search) Sébastien Paquet, Ludovic Tobin y Brahim Chaib-draa Híbrido.
2.005 ND-POMDP (Networked Distributed POMDP) Ranjit Nair, Pradeep Varakantham, Milind Tambe y Makoto Yokoo Similar a un n DCOP.
2.005 RTBSS-QMDP, RTBSS-PBVI-QMDP y RTDPBSS Sébastien Paquet, Brahim Chaib-draa y Stéphane Ross Híbrido.
2.007 MBDP (Memory Bounded Dynamic Programming)
Sven Seuken y Shlomo Zilberstein Algoritmo. Desarrollado para los DEC-POMDP.  Mejora respecto de los algoritmos exactos, pero no resuelve la necesidad de memoria.
2.007 MILP-POMDP (Mixed Integer Linear Programming)
Raghav Aras y Alain Dutech Algoritmo. Para DEC-POMDP
2.007 FSVI (Forward Search Value Iteration) Guy Shani, Ronen I. Brafman y Solomon E. Shimony Agente.
2.016 GPOMCP (Graphical Partially Observable Monte-Carlo Planning)
Julius Pfrommer Algoritmo. Agente. Combina MTCS con el algorithm (Max-Sum).
2.008 QCL (Quantified Coalition Logic)
Thomas Agotnes, Wiebe van der Hoek y Michael Wooldridge Agente. Basado en CL e influenciado por ATL.
2.009 RBCL (Resource-Bounded Coalition Logic)
Natasha Alechina, Brian Logan, Nguyen Hoang Nga y Abdur Rakib Agente. Evolución de ATL y CL.  .,
2.009 ATLBM (Alternating-time Temporal Logic with Bounded Memory) Thomas Ågotnes y Dirk Walther Agente. Tiene reminiscencias de ATL, PDL y CL.
2.010 POMCP (Partially Observable Monte Carlo Planning) David Silver y Joel Veness Algoritmo. Basado en MCTS y adaptado a POMDP.
2.010 ADL (Alternating-time Dynamic
Logic)
Nicolas Troquard y Dirk Walther Agente. Modela acciones superpuestas de agentes. Está cercano a PDL y a ATL y puede verse como una variante de Agent  Dynamic Logic.
2.008 SARSOP (Successive Approximations of the Reachable Space under Optimal Policies) Hanna Kurniawati, David Hsu y Wee Sun Lee Basado en PBVI. Horizonte finito.
2.011 RMTDP (Role-based Markov Team Decision Problem)
Milind Tambe y  Ranjit Nair Agente multiple.
2.011 HPB (Hybrid-POMDP-BDI)
Milind Tambe y  Ranjit Nair Híbrido. Agente multiple.
2.011 BA-POMDP (Bayes Adaptive POMDP ) Stephane Ross, Brahim Chaib-draa y Joelle Pineau Anticipado
2.011 MPOMDP (Multiagent POMDP) Joao V. Messias, Matthijs Spaan y Pedro U. Lima Algoritmo. Anticipado – Basado en puntos
2.011 CPBVI (Constrained Point-Based Value Iteration)
Dongho Kim, Jaesong Lee, Kee-Eung Kim y  Pascal Poupart Algoritmo. Basado en puntos de horizonte infinito. Permite especificar restricciones.
2.011 I-POMDP (Interactive-POMDP) Ekhlas Sonu y Prashant Doshi Agentes multiples. Reducción de la complejidad al incrementar el nº de agentes.
2.012 MAA* (Multi-agent A* ) Daniel Szer, François Charpillet y Shlomo Zilberstein Algoritmo. Gestión de múltiples agentes para DEC-POMDP
2.012 IMP (Inquiry Modeling POMDP)
Jeremiah T. Folsom-Kovarik, Gita Sukthankar ySae Schatz Híbrido. Sistema de tutoría para representar el modelo del alumno.
2.013 I-POMDP-L (Interactive-POMDP-Lite)
Trong Nghia Hoang y Kian Hsiang Low Evolición de la planificación de la cooperacion de múltiples agentes.
2.014 BA-MPOMDP (Bayes Adaptive Multiagent POMDP )
Christopher Amato y Frans A. Oliehoek Algoritmo. Anticipado
2.014 GapMin
Pascal Poupart, Kee-Eung Kim y Dongho Kim Basado en PBVI. Reduce la brecha entre los límites superior e inferior al calcular límites más estrictos.
2.014 D2NG-POMCP (Dirichlet-Dirichlet Normal Gamma based Partially Observable MonteCarlo Planning)

Aijun Bai, Feng Wu, Zongzhang Zhang y Xiaoping Chen

Agente. Trata la recompensa acumulada de realizar una acción desde un estado de creencia en el árbol de búsqueda MCTS
2.014 FV-MPOMCP (Factored-Value MPOMCP) Christopher Amato y Frans A. Oliehoek Algoritmo. Adapta POMCP para la configuración POMDP multiagente.
2.015 HPB (Hybrid-POMDP-BDI) Gavin B. Rens y Thomas Meyer En línea
2.015 MHA* (Multi-Heuristic A*) IMHA* – SMHA*
Sandip Aine, Siddharth Swaminathan, Venkatraman Narayanan, Victor Hwang y Maxim Likhachev Derivado del algoritmo de búsqueda A*, 1.968.
2.015 CALP (Constrained Approximate Linear Programming)
Pascal Poupart, Aarti Malhotra, Pei Pei, Kee-Eung Kim, Bongseok Goh y Michael Bowling Formula un POMDP restringido como un MDP restringido. Define estados de creencia en lugar de estados. Orientado a problemas de horizonte infinito. Permite especificar restricciones.
2.015 C-POMDP (Constrained POMDP)
Pascal Poupart, Aarti Malhotra, Pei Pei, Kee-Eung Kim, Bongseok Goh y Michael Bowling Permite especificar restricciones. Modela problemas que involucran recursos limitados o múltiples objetivos.
2.016 HPB (Hybrid-POMDP-BDI) Gavin Rens y Deshendran Moodley Híbrido. Enfocado al Agente.
2.016 RAO∗ (Risk-bounded AO∗)
Pedro Santana, Sylvie Thiebaux y Brian Williams Resuelve los CC-POMDP limitados. AO* (And-Or)
2.016 FCBDI (First-order Coalition BDI)
Qingliang Chen, Kaile Su, Abdul Sattar, Xiangyu Luo, y Aixiang Chen Agente.
2.016 GPOMCP (Graphical Partially Observable Monte-Carlo Planning)
Julius Pfrommer Algoritmo. Agente. Combina MTCS con el algorithm (Max-Sum).
2.016 CC-POMDP (Chance-Constrained POMDP)
Pedro Santana, Sylvie Thiebaux y Brian Williams Se utiliza cuando las restricciones implican limitar la probabilidad de fallos.
2.017 QMDP (Quantile MDP) Xiaocheng Li, Huaiyang Zhong y Margaret L. Brandeau Maximizador de la recompensa esperada.
2.017 RLE-BA-POMCP (Root Sampling Linking States Expected Dynamics) Sammie Katt, Frans A Oliehoek y Christopher Amato Extensión del método de Monte-Carlo Tree Search a BA-POMCP.
2.018 CC-POMCP (Cost-Constrained POMCP)
Jongmin Lee, Geon-Hyeong Kim, Pascal Poupart y Kee-Eung Kim En línea. MCTS para CPOMDP grandes. Permite especificar restricciones.
2.018 Goal-HSVI (Heuristic Search Value Iteration for Goal POMDP) Karel Horák, Branislav Bošanský y Krishnendu Chatterjee Basado en PBVI. Garantiza la convergencia, dicen.
2.018 CGCP (Column Generation algorithm for Constrained POMDP) Erwin Walraven y Matthijs T. J. Spaan Algoritmo. Permite especificar restricciones.
2.018 IH-EOPG (Infinite Horizon Expectation Optimization with Probabilistic Guarantees in POMDP)
Krishnendu Chatterjee, Adrian Elgyütt, Petr Novotny y Owen Rouille Reduce un problema de HI (Horizonte Infinito) a una variante de horizonte finito.
2.019 POMHDP (Partially Observable Multi-Heuristic Dynamic Programming ) Sung-Kyun Kim, Oren Salzman y Maxim Likhachev Basado en PBVI.
2.019 FPTAS (Fully Polynomial Time Approximation Scheme)
Majid Khonji, Ashkan Jasour y
Brian Williams
Aplicable a C-POMDP y CC-POMDP
2.019 I-POMDP-Net
Yanlin Han y Piotr Gmytrasiewicz Red neuronal para la planificación de múltiples agentes según I-POMDP.
2.019 FiVI (Finite-Horizon Point-Based Value Iteration)
Erwin Walraven y Matthijs T. J. Spaan Algoritmo. De horizonte finito. Basado en PBVI.