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

  • October 31, 2019

has restriction

  • bronze

Date in CU Experts

  • January 31, 2020 7:49 AM

Full Author List

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

author count

  • 5

Other Profiles

International Standard Serial Number (ISSN)

  • 1049-3301

Electronic International Standard Serial Number (EISSN)

  • 1558-1195

Additional Document Info

start page

  • 1

end page

  • 31

volume

  • 29

issue

  • 4