Qualitative possibilistic Mixed-Observable MDPs

Nicolas Drougard, Didier Dubois, Florent Teichteil-Königsbuch, Jean-Loup Farges
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:372-381, 2013.

Abstract

Possibilistic and qualitative POMDPs ($\pi$- POMDPs) are counterparts of POMDPs used to model situations where the agent’s initial belief or observation probabilities are imprecise due to lack of past experiences or insufficient data collection. However, like probabilistic POMDPs, optimally solving $\pi$- POMDPs is intractable: the finite belief state space exponentially grows with the number of system’s states. In this paper, a possibilis- tic version of Mixed-Observable MDPs is pre- sented to get around this issue: the complex- ity of solving $\pi$-POMDPs, some state vari- ables of which are fully observable, can be then dramatically reduced. A value iteration algorithm for this new formulation under in- finite horizon is next proposed and the op- timality of the returned policy (for a spec- ified criterion) is shown assuming the exis- tence of a ”stay” action in some goal states. Experimental work finally shows that this possibilistic model outperforms probabilistic POMDPs commonly used in robotics, for a target recognition problem where the agent’s observations are imprecise.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-drougard13a, title = {Qualitative possibilistic Mixed-Observable MDPs}, author = {Drougard, Nicolas and Dubois, Didier and Teichteil-K{\"o}nigsbuch, Florent and Farges, Jean-Loup}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {372--381}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/drougard13a/drougard13a.pdf}, url = {https://proceedings.mlr.press/r11/drougard13a.html}, abstract = {Possibilistic and qualitative POMDPs ($\pi$- POMDPs) are counterparts of POMDPs used to model situations where the agent’s initial belief or observation probabilities are imprecise due to lack of past experiences or insufficient data collection. However, like probabilistic POMDPs, optimally solving $\pi$- POMDPs is intractable: the finite belief state space exponentially grows with the number of system’s states. In this paper, a possibilis- tic version of Mixed-Observable MDPs is pre- sented to get around this issue: the complex- ity of solving $\pi$-POMDPs, some state vari- ables of which are fully observable, can be then dramatically reduced. A value iteration algorithm for this new formulation under in- finite horizon is next proposed and the op- timality of the returned policy (for a spec- ified criterion) is shown assuming the exis- tence of a ”stay” action in some goal states. Experimental work finally shows that this possibilistic model outperforms probabilistic POMDPs commonly used in robotics, for a target recognition problem where the agent’s observations are imprecise.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Qualitative possibilistic Mixed-Observable MDPs %A Nicolas Drougard %A Didier Dubois %A Florent Teichteil-Königsbuch %A Jean-Loup Farges %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-drougard13a %I PMLR %P 372--381 %U https://proceedings.mlr.press/r11/drougard13a.html %V R11 %X Possibilistic and qualitative POMDPs ($\pi$- POMDPs) are counterparts of POMDPs used to model situations where the agent’s initial belief or observation probabilities are imprecise due to lack of past experiences or insufficient data collection. However, like probabilistic POMDPs, optimally solving $\pi$- POMDPs is intractable: the finite belief state space exponentially grows with the number of system’s states. In this paper, a possibilis- tic version of Mixed-Observable MDPs is pre- sented to get around this issue: the complex- ity of solving $\pi$-POMDPs, some state vari- ables of which are fully observable, can be then dramatically reduced. A value iteration algorithm for this new formulation under in- finite horizon is next proposed and the op- timality of the returned policy (for a spec- ified criterion) is shown assuming the exis- tence of a ”stay” action in some goal states. Experimental work finally shows that this possibilistic model outperforms probabilistic POMDPs commonly used in robotics, for a target recognition problem where the agent’s observations are imprecise. %Z Reissued by PMLR on 04 October 2026.
APA
Drougard, N., Dubois, D., Teichteil-Königsbuch, F. & Farges, J.. (2013). Qualitative possibilistic Mixed-Observable MDPs. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:372-381 Available from https://proceedings.mlr.press/r11/drougard13a.html. Reissued by PMLR on 04 October 2026.

Related Material