SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes

Pranav Ashok, Jan Kretínsky, Kim Guldstrand Larsen, Adrien Camille le Coent, Jakob Haahr Taankvist, Maxmillian Weininger

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

Abstract

For hybrid Markov decision processes, Open image in new window Stratego can compute strategies that are safe for a given safety property and (in the limit) optimal for a given cost function. Unfortunately, these strategies cannot be exported easily since they are computed as a very long list. In this paper, we demonstrate methods to learn compact representations of the strategies in the form of decision trees. These decision trees are much smaller, more understandable, and can easily be exported as code that can be loaded into embedded systems. Despite the size compression and actual differences to the original strategy, we provide guarantees on both safety and optimality of the decision-tree strategy. On the top, we show how to obtain yet smaller representations, which are still guaranteed safe, but achieve a desired trade-off between size and optimality.
Original languageEnglish
Title of host publicationQuantitative Evaluation of Systems - 16th International Conference, QEST 2019, Proceedings
EditorsDavid Parker, Verena Wolf
Number of pages18
Place of PublicationHeidelberg
PublisherSpringer
Publication date2019
Pages147-164
ISBN (Print)978-3-030-30280-1
ISBN (Electronic)978-3-030-30281-8
DOIs
Publication statusPublished - 2019
EventQEST 2019: International Conference on Quantitative Evaluation of Systems -
Duration: 10 Sep 201912 Sep 2019

Conference

ConferenceQEST 2019: International Conference on Quantitative Evaluation of Systems
Period10/09/201912/09/2019
SeriesLecture Notes in Computer Science
Volume11785
ISSN0302-9743

Fingerprint

Decision trees
Embedded systems
Cost functions

Cite this

Ashok, P., Kretínsky, J., Larsen, K. G., Coent, A. C. L., Taankvist, J. H., & Weininger, M. (2019). SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes. In D. Parker, & V. Wolf (Eds.), Quantitative Evaluation of Systems - 16th International Conference, QEST 2019, Proceedings (pp. 147-164). Heidelberg: Springer. Lecture Notes in Computer Science, Vol.. 11785 https://doi.org/10.1007/978-3-030-30281-8_9
Ashok, Pranav ; Kretínsky, Jan ; Larsen, Kim Guldstrand ; Coent, Adrien Camille le ; Taankvist, Jakob Haahr ; Weininger, Maxmillian. / SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes. Quantitative Evaluation of Systems - 16th International Conference, QEST 2019, Proceedings. editor / David Parker ; Verena Wolf. Heidelberg : Springer, 2019. pp. 147-164 (Lecture Notes in Computer Science, Vol. 11785).
@inproceedings{d2104d9395a541269388b4f278a44227,
title = "SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes",
abstract = "For hybrid Markov decision processes, Open image in new window Stratego can compute strategies that are safe for a given safety property and (in the limit) optimal for a given cost function. Unfortunately, these strategies cannot be exported easily since they are computed as a very long list. In this paper, we demonstrate methods to learn compact representations of the strategies in the form of decision trees. These decision trees are much smaller, more understandable, and can easily be exported as code that can be loaded into embedded systems. Despite the size compression and actual differences to the original strategy, we provide guarantees on both safety and optimality of the decision-tree strategy. On the top, we show how to obtain yet smaller representations, which are still guaranteed safe, but achieve a desired trade-off between size and optimality.",
author = "Pranav Ashok and Jan Kret{\'i}nsky and Larsen, {Kim Guldstrand} and Coent, {Adrien Camille le} and Taankvist, {Jakob Haahr} and Maxmillian Weininger",
year = "2019",
doi = "10.1007/978-3-030-30281-8_9",
language = "English",
isbn = "978-3-030-30280-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "147--164",
editor = "David Parker and Verena Wolf",
booktitle = "Quantitative Evaluation of Systems - 16th International Conference, QEST 2019, Proceedings",
address = "Germany",

}

Ashok, P, Kretínsky, J, Larsen, KG, Coent, ACL, Taankvist, JH & Weininger, M 2019, SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes. in D Parker & V Wolf (eds), Quantitative Evaluation of Systems - 16th International Conference, QEST 2019, Proceedings. Springer, Heidelberg, Lecture Notes in Computer Science, vol. 11785, pp. 147-164, QEST 2019: International Conference on Quantitative Evaluation of Systems, 10/09/2019. https://doi.org/10.1007/978-3-030-30281-8_9

SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes. / Ashok, Pranav; Kretínsky, Jan; Larsen, Kim Guldstrand; Coent, Adrien Camille le; Taankvist, Jakob Haahr; Weininger, Maxmillian.

Quantitative Evaluation of Systems - 16th International Conference, QEST 2019, Proceedings. ed. / David Parker; Verena Wolf. Heidelberg : Springer, 2019. p. 147-164 (Lecture Notes in Computer Science, Vol. 11785).

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes

AU - Ashok, Pranav

AU - Kretínsky, Jan

AU - Larsen, Kim Guldstrand

AU - Coent, Adrien Camille le

AU - Taankvist, Jakob Haahr

AU - Weininger, Maxmillian

PY - 2019

Y1 - 2019

N2 - For hybrid Markov decision processes, Open image in new window Stratego can compute strategies that are safe for a given safety property and (in the limit) optimal for a given cost function. Unfortunately, these strategies cannot be exported easily since they are computed as a very long list. In this paper, we demonstrate methods to learn compact representations of the strategies in the form of decision trees. These decision trees are much smaller, more understandable, and can easily be exported as code that can be loaded into embedded systems. Despite the size compression and actual differences to the original strategy, we provide guarantees on both safety and optimality of the decision-tree strategy. On the top, we show how to obtain yet smaller representations, which are still guaranteed safe, but achieve a desired trade-off between size and optimality.

AB - For hybrid Markov decision processes, Open image in new window Stratego can compute strategies that are safe for a given safety property and (in the limit) optimal for a given cost function. Unfortunately, these strategies cannot be exported easily since they are computed as a very long list. In this paper, we demonstrate methods to learn compact representations of the strategies in the form of decision trees. These decision trees are much smaller, more understandable, and can easily be exported as code that can be loaded into embedded systems. Despite the size compression and actual differences to the original strategy, we provide guarantees on both safety and optimality of the decision-tree strategy. On the top, we show how to obtain yet smaller representations, which are still guaranteed safe, but achieve a desired trade-off between size and optimality.

U2 - 10.1007/978-3-030-30281-8_9

DO - 10.1007/978-3-030-30281-8_9

M3 - Article in proceeding

SN - 978-3-030-30280-1

T3 - Lecture Notes in Computer Science

SP - 147

EP - 164

BT - Quantitative Evaluation of Systems - 16th International Conference, QEST 2019, Proceedings

A2 - Parker, David

A2 - Wolf, Verena

PB - Springer

CY - Heidelberg

ER -

Ashok P, Kretínsky J, Larsen KG, Coent ACL, Taankvist JH, Weininger M. SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes. In Parker D, Wolf V, editors, Quantitative Evaluation of Systems - 16th International Conference, QEST 2019, Proceedings. Heidelberg: Springer. 2019. p. 147-164. (Lecture Notes in Computer Science, Vol. 11785). https://doi.org/10.1007/978-3-030-30281-8_9