Abstract
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.
Original language | English |
---|---|
Title of host publication | Quantitative Evaluation of Systems |
Subtitle of host publication | 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings |
Editors | Nathalie Bertrand, Luca Bortolussi |
Place of Publication | Cham |
Publisher | Springer |
Pages | 207-223 |
Number of pages | 17 |
ISBN (Electronic) | 978-3-319-66335-7 |
ISBN (Print) | 978-3-319-66334-0 |
DOIs | |
Publication status | Published - 2017 |
Externally published | Yes |
Event | 14th International Conference on Quantitative Evaluation of Systems, QEST 2017 - Berlin, Germany Duration: 5 Sept 2017 → 7 Sept 2017 Conference number: 14 http://www.qest.org/qest2017/ |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 10503 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 14th International Conference on Quantitative Evaluation of Systems, QEST 2017 |
---|---|
Abbreviated title | QEST |
Country/Territory | Germany |
City | Berlin |
Period | 5/09/17 → 7/09/17 |
Internet address |