Anytime Algorithms for Solving Possibilistic MDPs and Hybrid MDPs

Kim Bauters, Weiru Liu, Lluis Godo

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

3 Citations (Scopus)
207 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 (FolKS 2016)
Subtitle of host publication9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings
EditorsMarc Gyssens, Guillermo Simari
Number of pages18
ISBN (Electronic)9783319300245
ISBN (Print)9783319300238
Publication statusPublished - 4 Mar 2016

Publication series

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

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

Cite this