Interval Markov Decision Processes with Multiple Objectives Journal Article uri icon

Overview

abstract

  • ; Accurate Modelling of a real-world system with probabilistic behaviour is a difficult task. Sensor noise and statistical estimations, among other imprecisions, make the exact probability values impossible to obtain. In this article, we consider Interval Markov decision processes (; IMDP; s), which generalise classical; MDP; s 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. We investigate the problem of robust multi-objective synthesis for; IMDP; s and Pareto curve analysis of multi-objective queries on; IMDP; s. We study how to find a robust (randomised) strategy that satisfies multiple objectives involving rewards, reachability, and more general ω-regular properties against all possible resolutions of the transition probability uncertainties, as well as to generate an approximate Pareto curve providing an explicit view of the trade-offs between multiple objectives. We show that the multi-objective synthesis problem is; PSPACE; -hard and 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 prototype tool.;

publication date

  • December 17, 2019

Full Author List

  • Hahn EM; Hashemi V; Hermanns H; Lahijanian M; Turrini A

Other Profiles

Additional Document Info

start page

  • 1

end page

  • 31

volume

  • 29

issue

  • 4