EUVIMEDEUVIMED entdecken
Open Access · CC BY-ND 4.0

Interval Markov Decision Processes with Multiple Objectives

Ernst Moritz Hahn, Vahid Hashemi, Holger Hermanns, Morteza Lahijanian, Andrea Turrini

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →