Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs

Kim Bauters, Weiru Liu, Lluis Godo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)
260 Downloads (Pure)


The ability of an agent to make quick, rational decisions in an uncertain environment is paramount for its applicability in realistic settings. Markov Decision Processes (MDP) provide such a framework, but can only model uncertainty that can be expressed as probabilities. Possibilistic counterparts of MDPs allow to model imprecise beliefs, yet they cannot accurately represent probabilistic sources of uncertainty and they lack the efficient online solvers found in the probabilistic MDP community. In this paper we advance the state of the art in three important ways. Firstly, we propose the first online planner for possibilistic MDP by adapting the Monte-Carlo Tree Search (MCTS) algorithm. A key component is the development of efficient search structures to sample possibility distributions based on the DPY transformation as introduced by Dubois, Prade, and Yager. Secondly, we introduce a hybrid MDP model that allows us to express both possibilistic and probabilistic uncertainty, where the hybrid model is a proper extension of both probabilistic and possibilistic MDPs. Thirdly, we demonstrate that MCTS algorithms can readily be applied to solve such hybrid models.
Original languageEnglish
Title of host publicationFoundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings
ISBN (Electronic)978-3-319-30024-5
ISBN (Print)978-3-319-30023-8
Publication statusPublished - 04 Mar 2016
Event9th International Symposium on Foundations of Information and Knowledge Systems (FoIKS'16) - Linz, Austria
Duration: 07 Mar 201611 Mar 2016

Publication series

NameLecture Notes in Computer Science
ISSN (Electronic)0302-9743


Conference9th International Symposium on Foundations of Information and Knowledge Systems (FoIKS'16)


Dive into the research topics of 'Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs'. Together they form a unique fingerprint.

Cite this