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.

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 ( e → e’). 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:
- 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).
- Al mismo tiempo, el agente recibe una observación o ∈ O que depende del nuevo estado del entorno con probabilidad θ (o | e’, a).
- 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) |
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. |