Oxford logo
[HHH+17] Ernst Moritz Hahn and Vahid Hashemi and Holger Hermanns and Morteza Lahijanian and Andrea Turrini. Multi-objective Robust Strategy Synthesis for Interval Markov Decision Processes. In International Conference on Quantitative Evaluation of SysTems (QEST), Springer. September 2017. [pdf] [bib]
Downloads:  pdf pdf (1.23 MB)  bib bib
Notes: The original publication is available at www.springerlink.com.
Abstract. Interval Markov decision processes (IMDPs) generalise classical MDPs by having interval-valued transition probabilities. They provide a powerful modelling tool for probabilistic systems with an additional variation or uncertainty that prevents the knowledge of the exact transition probabilities. In this paper, we consider the problem of multi-objective robust strategy synthesis for interval MDPs, where the aim is to find a robust strategy that guarantees the satisfaction of multiple properties at the same time in face of the transition probability uncertainty. We first show that this problem is PSPACE-hard. Then, we provide a value iteration-based decision algorithm to approximate the Pareto set of achievable points. We finally demonstrate the practical effectiveness of our proposed approaches by applying them on several case studies using a prototypical tool.