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 proposals by applying them on several real-world case studies.
|Title of host publication||Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings|
|Number of pages||17|
|Publication status||Published - 01 Dec 2017|
Hahn, E. M., Hashemi, V., Hermanns, H., Lahijanian, M., & Turrini, A. (2017). Multi-objective Robust Strategy Synthesis for Interval Markov Decision Processes. In Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings (Vol. 10503, pp. 207-223). Springer. https://doi.org/10.1007/978-3-319-66335-7_13