Efficient Strategy Synthesis for MDPs With Resource Constraints

J 2023

Efficient Strategy Synthesis for MDPs With Resource Constraints

BLAHOUDEK, Fratišek, Petr NOVOTNÝ, Melkior ORNIK, Pranay THANGEDA, Ufuk TOPCU et. al.

Basic information

Original name

Efficient Strategy Synthesis for MDPs With Resource Constraints

Authors

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

Edition

IEEE Transactions on Automatic Control, 2023, 0018-9286

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

URL

Impact factor

Impact factor: 6.800 in 2022

RIV identification code

RIV/00216224:14330/23:00134423

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1109/TAC.2022.3209612

UT WoS

001041305400007

Keywords in English

Consumption Markov decision process (CMDP); planning; resource constraints; strategy synthesis

Změněno: 7/4/2024 23:48, RNDr. Pavel Šmerk, Ph.D.

Abstract

V originále

We consider qualitative strategy synthesis for the formalism called consumption Markov decision processes. This formalism can model the dynamics of an agent that operates under resource constraints in a stochastic environment. The presented algorithms work in time polynomial with respect to the representation of the model and they synthesize strategies ensuring that a given set of goal states will be reached (once or infinitely many times) with probability 1 without resource exhaustion. In particular, when the amount of resource becomes too low to safely continue in the mission, the strategy changes course of the agent toward one of a designated set of reload states where the agent replenishes the resource to full capacity; with a sufficient amount of resource, the agent attempts to fulfill the mission again. We also present two heuristics that attempt to reduce the expected time that the agent needs to fulfill the given mission, a parameter important in practical planning. The presented algorithms were implemented, and the numerical examples demonstrate the effectiveness (in terms of computation time) of the planning approach based on consumption Markov decision processes and the positive impact of the two heuristics on planning in a realistic example.

Links

GA21-24711S, research and development project

Name: Efektivní analýza a optimalizace pravděpodobnostních systémů a her (Acronym: Efektivní analýza a optimalizace pravděpodobnostní)

Investor: Czech Science Foundation

Citovat

BLAHOUDEK, Fratišek, Petr NOVOTNÝ, Melkior ORNIK, Pranay THANGEDA and Ufuk TOPCU. Efficient Strategy Synthesis for MDPs With Resource Constraints. IEEE Transactions on Automatic Control. 2023, vol. 68, No 8, p. 4586 - 4601. ISSN 0018-9286. Available from: https://dx.doi.org/10.1109/TAC.2022.3209612.

@article{2386722,
   author = {Blahoudek, Fratišek and Novotný, Petr and Ornik, Melkior and Thangeda, Pranay and Topcu, Ufuk},
   article_number = {8},
   doi = {http://dx.doi.org/10.1109/TAC.2022.3209612},
   keywords = {Consumption Markov decision process (CMDP); planning; resource constraints; strategy synthesis},
   language = {eng},
   issn = {0018-9286},
   journal = {IEEE Transactions on Automatic Control},
   title = {Efficient Strategy Synthesis for MDPs With Resource Constraints},
   url = {https://ieeexplore.ieee.org/document/9903331},
   volume = {68},
   year = {2023}
}

TY  - JOUR
ID  - 2386722
AU  - Blahoudek, Fratišek - Novotný, Petr - Ornik, Melkior - Thangeda, Pranay - Topcu, Ufuk
PY  - 2023
TI  - Efficient Strategy Synthesis for MDPs With Resource Constraints
JF  - IEEE Transactions on Automatic Control
VL  - 68
IS  - 8
SP  - 4586 - 4601
EP  - 4586 - 4601
SN  - 00189286
KW  - Consumption Markov decision process (CMDP)
KW  - planning
KW  - resource constraints
KW  - strategy synthesis
UR  - https://ieeexplore.ieee.org/document/9903331
N2  - We consider qualitative strategy synthesis for the formalism called consumption Markov decision processes. This formalism can model the dynamics of an agent that operates under resource constraints in a stochastic environment. The presented algorithms work in time polynomial with respect to the representation of the model and they synthesize strategies ensuring that a given set of goal states will be reached (once or infinitely many times) with probability 1 without resource exhaustion. In particular, when the amount of resource becomes too low to safely continue in the mission, the strategy changes course of the agent toward one of a designated set of reload states where the agent replenishes the resource to full capacity; with a sufficient amount of resource, the agent attempts to fulfill the mission again. We also present two heuristics that attempt to reduce the expected time that the agent needs to fulfill the given mission, a parameter important in practical planning. The presented algorithms were implemented, and the numerical examples demonstrate the effectiveness (in terms of computation time) of the planning approach based on consumption Markov decision processes and the positive impact of the two heuristics on planning in a realistic example.
ER  -

BLAHOUDEK, Fratišek, Petr NOVOTNÝ, Melkior ORNIK, Pranay THANGEDA and Ufuk TOPCU. Efficient Strategy Synthesis for MDPs With Resource Constraints. \textit{IEEE Transactions on Automatic Control}. 2023, vol.~68, No~8, p.~4586 - 4601. ISSN~0018-9286. Available from: https://dx.doi.org/10.1109/TAC.2022.3209612.

Detailed Information on Publication Record