Multi-objective robust strategy synthesis for Interval Markov decision processes

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

doi:10.1007/978-3-319-66335-7_13

Multi-objective robust strategy synthesis for Interval Markov decision processes

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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

27 Citations (Scopus)

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	https://doi.org/10.1007/978-3-319-66335-7_13
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	http://www.qest.org/qest2017/

Access to Document

10.1007/978-3-319-66335-7_13

Cite this

Hahn, E. M., Hashemi, V., Hermanns, H., Lahijanian, M., & Turrini, A. (2017). Multi-objective robust strategy synthesis for Interval Markov decision processes. In N. Bertrand, & L. Bortolussi (Eds.), Quantitative Evaluation of Systems: 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings (pp. 207-223). (Lecture Notes in Computer Science; Vol. 10503). Springer. https://doi.org/10.1007/978-3-319-66335-7_13

Hahn, Ernst Moritz ; Hashemi, Vahid ; Hermanns, Holger et al. / Multi-objective robust strategy synthesis for Interval Markov decision processes. Quantitative Evaluation of Systems: 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings. editor / Nathalie Bertrand ; Luca Bortolussi. Cham : Springer, 2017. pp. 207-223 (Lecture Notes in Computer Science).

@inproceedings{28e25c8ea30f43bf9f2e20f3db76c6e1,

title = "Multi-objective robust strategy synthesis for Interval Markov decision processes",

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.",

author = "Hahn, {Ernst Moritz} and Vahid Hashemi and Holger Hermanns and Morteza Lahijanian and Andrea Turrini",

year = "2017",

doi = "10.1007/978-3-319-66335-7_13",

language = "English",

isbn = "978-3-319-66334-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "207--223",

editor = "Nathalie Bertrand and Luca Bortolussi",

booktitle = "Quantitative Evaluation of Systems",

address = "Germany",

note = "14th International Conference on Quantitative Evaluation of Systems, QEST 2017, QEST ; Conference date: 05-09-2017 Through 07-09-2017",

url = "http://www.qest.org/qest2017/",

}

Hahn, EM, Hashemi, V, Hermanns, H, Lahijanian, M & Turrini, A 2017, Multi-objective robust strategy synthesis for Interval Markov decision processes. in N Bertrand & L Bortolussi (eds), Quantitative Evaluation of Systems: 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10503, Springer, Cham, pp. 207-223, 14th International Conference on Quantitative Evaluation of Systems, QEST 2017, Berlin, Germany, 5/09/17. https://doi.org/10.1007/978-3-319-66335-7_13

Multi-objective robust strategy synthesis for Interval Markov decision processes. / Hahn, Ernst Moritz; Hashemi, Vahid; Hermanns, Holger et al.
Quantitative Evaluation of Systems: 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings. ed. / Nathalie Bertrand; Luca Bortolussi. Cham: Springer, 2017. p. 207-223 (Lecture Notes in Computer Science; Vol. 10503).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Multi-objective robust strategy synthesis for Interval Markov decision processes

AU - Hahn, Ernst Moritz

AU - Hashemi, Vahid

AU - Hermanns, Holger

AU - Lahijanian, Morteza

AU - Turrini, Andrea

N1 - Conference code: 14

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85028663181&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-66335-7_13

DO - 10.1007/978-3-319-66335-7_13

M3 - Conference contribution

SN - 978-3-319-66334-0

T3 - Lecture Notes in Computer Science

SP - 207

EP - 223

BT - Quantitative Evaluation of Systems

A2 - Bertrand, Nathalie

A2 - Bortolussi, Luca

PB - Springer

CY - Cham

T2 - 14th International Conference on Quantitative Evaluation of Systems, QEST 2017

Y2 - 5 September 2017 through 7 September 2017

ER -

Hahn EM, Hashemi V, Hermanns H, Lahijanian M, Turrini A. Multi-objective robust strategy synthesis for Interval Markov decision processes. In Bertrand N, Bortolussi L, editors, Quantitative Evaluation of Systems: 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings. Cham: Springer. 2017. p. 207-223. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-66335-7_13