Fuel in Markov Decision Processes (FiMDP): A Practical Approach
to Consumption

D 2021

Fuel in Markov Decision Processes (FiMDP): A Practical Approach to Consumption

BLAHOUDEK, František; Murat CUBUKTEPE; Petr NOVOTNÝ; Melkior ORNIK; Pranay THANGEDA et. al.

Basic information

Original name

Fuel in Markov Decision Processes (FiMDP): A Practical Approach to Consumption

Authors

BLAHOUDEK, František (203 Czech Republic); Murat CUBUKTEPE (792 Turkey); Petr NOVOTNÝ (203 Czech Republic, guarantor, belonging to the institution); Melkior ORNIK (191 Croatia); Pranay THANGEDA (356 India) and Ufuk TOPCU (792 Turkey)

Edition

Cham, Switzerland, 24th International Symposium on Formal Methods, FM 2021, p. 640-656, 17 pp. 2021

Publisher

Springer

Other information

Language

English

Type of outcome

Proceedings paper

Field of Study

10201 Computer sciences, information science, bioinformatics

Confidentiality degree

is not subject to a state or trade secret

Publication form

electronic version available online

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/21:00119269

Organization unit

Faculty of Informatics

ISBN

978-3-030-90869-0

ISSN

DOI

https://doi.org/10.1007/978-3-030-90870-6_34

UT WoS

000758218600034

EID Scopus

2-s2.0-85119837676

Keywords in English

resource constraints; planning under uncertainty; Markov decision processes

Abstract

In the original language

Consumption Markov Decision Processes (CMDPs) are prob- abilistic decision-making models of resource-constrained systems. We introduce FiMDP, a tool for controller synthesis in CMDPs with LTL objectives expressible by deterministic Büchi automata. The tool implements the recent algorithm for polynomial-time controller synthesis in CMDPs, but extends it with many additional features. On the conceptual level, the tool implements heuristics for improving the expected reachability times of accepting states, and a support for multi-agent task allocation. On the practical level, the tool offers (among other features) a new strategy simulation framework, integration with the Storm model checker, and FiMDPEnv - a new set of CMDPs that model real-world resource-constrained systems. We also present an evaluation of FiMDP on these real-world scenarios.

Links

GJ19-15134Y, research and development project

Name: Verifikace a analýza pravděpodobnostních programů

Cite

BLAHOUDEK, František; Murat CUBUKTEPE; Petr NOVOTNÝ; Melkior ORNIK; Pranay THANGEDA and Ufuk TOPCU. Fuel in Markov Decision Processes (FiMDP): A Practical Approach to Consumption. Online. In 24th International Symposium on Formal Methods, FM 2021. Cham, Switzerland: Springer, 2021, p. 640-656. ISBN 978-3-030-90869-0. Available from: https://doi.org/10.1007/978-3-030-90870-6_34.

@inproceedings{1797367,
   author = {Blahoudek, František and Cubuktepe, Murat and Novotný, Petr and Ornik, Melkior and Thangeda, Pranay and Topcu, Ufuk},
   address = {Cham, Switzerland},
   booktitle = {24th International Symposium on Formal Methods, FM 2021},
   doi = {https://doi.org/10.1007/978-3-030-90870-6_34},
   keywords = {resource constraints; planning under uncertainty; Markov decision processes},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Cham, Switzerland},
   isbn = {978-3-030-90869-0},
   pages = {640-656},
   publisher = {Springer},
   title = {Fuel in Markov Decision Processes (FiMDP): A Practical Approach to Consumption},
   year = {2021}
}

TY  - CONF
ID  - 1797367
AU  - Blahoudek, František - Cubuktepe, Murat - Novotný, Petr - Ornik, Melkior - Thangeda, Pranay - Topcu, Ufuk
PY  - 2021
TI  - Fuel in Markov Decision Processes (FiMDP): A Practical Approach to Consumption
PB  - Springer
CY  - Cham, Switzerland
SN  - 9783030908690
KW  - resource constraints
KW  - planning under uncertainty
KW  - Markov decision processes
N2  - Consumption Markov Decision Processes (CMDPs) are prob- abilistic decision-making models of resource-constrained systems. We introduce FiMDP, a tool for controller synthesis in CMDPs with LTL objectives expressible by deterministic Büchi automata. The tool implements the recent algorithm for polynomial-time controller synthesis in CMDPs, but extends it with many additional features. On the conceptual level, the tool implements heuristics for improving the expected reachability times of accepting states, and a support for multi-agent task allocation. On the practical level, the tool offers (among other features) a new strategy simulation framework, integration with the Storm model checker, and FiMDPEnv - a new set of CMDPs that model real-world resource-constrained systems. We also present an evaluation of FiMDP on these real-world scenarios.
ER  -

BLAHOUDEK, František; Murat CUBUKTEPE; Petr NOVOTNÝ; Melkior ORNIK; Pranay THANGEDA and Ufuk TOPCU. Fuel in Markov Decision Processes (FiMDP): A Practical Approach to Consumption. Online. In \textit{24th International Symposium on Formal Methods, FM 2021}. Cham, Switzerland: Springer, 2021, p.~640-656. ISBN~978-3-030-90869-0. Available from: https://doi.org/10.1007/978-3-030-90870-6\_{}34.

Přehled o publikaci