Interval Markov Decision Processes with Multiple Objectives
ACM Transactions on Modeling and Computer Simulation · 31.10.2019 · 29 (4) · 1-31
DOI: 10.1145/3309683 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Modeling and Computer Simulation, online erschienen am 18.11.2019. Verfasst von Ernst Moritz Hahn und 4 weiteren Autor:innen. Die Arbeit wurde bisher 24-mal zitiert (Crossref) und nennt 43 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-ND 4.0). Gefördert von: National Natural Science Foundation of China, European Research Council, CAS/SAFEA.
Abstract (Originalsprache)
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.
Förderung
- National Natural Science Foundation of China
- European Research Council
- CAS/SAFEA
- Chinese Academy of Sciences
- Deutsche Forschungsgemeinschaft
- Engineering and Physical Sciences Research Council
- H2020
- CDZ
Zitieren
APA
Hahn, E. M., Hashemi, V., Hermanns, H., Lahijanian, M., & Turrini, A. (2019). Interval Markov Decision Processes with Multiple Objectives. ACM Transactions on Modeling and Computer Simulation, 29(4), 1-31. https://doi.org/10.1145/3309683
Vancouver
Hahn EM, Hashemi V, Hermanns H, Lahijanian M, Turrini A. Interval Markov Decision Processes with Multiple Objectives. ACM Transactions on Modeling and Computer Simulation. 2019;29(4):1-31. doi:10.1145/3309683
BibTeX
@article{Hahn2019,
author = {Hahn, Ernst Moritz and Hashemi, Vahid and Hermanns, Holger and Lahijanian, Morteza and Turrini, Andrea},
title = {Interval Markov Decision Processes with Multiple Objectives},
journal = {ACM Transactions on Modeling and Computer Simulation},
year = {2019},
volume = {29},
number = {4},
pages = {1--31},
doi = {10.1145/3309683}
}
EUVIMED