Efficient Strategy Synthesis for MDPs With Resource Constraints

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F23%3A00134423" target="_blank" >RIV/00216224:14330/23:00134423 - isvavai.cz</a>

Výsledek na webu

<a href="https://ieeexplore.ieee.org/document/9903331" target="_blank" >https://ieeexplore.ieee.org/document/9903331</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/TAC.2022.3209612" target="_blank" >10.1109/TAC.2022.3209612</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Efficient Strategy Synthesis for MDPs With Resource Constraints

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Efficient Strategy Synthesis for MDPs With Resource Constraints

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA21-24711S" target="_blank" >GA21-24711S: Efektivní analýza a optimalizace pravděpodobnostních systémů a her</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

IEEE Transactions on Automatic Control

ISSN

0018-9286

e-ISSN

1558-2523

Svazek periodika

68

Číslo periodika v rámci svazku

8

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

16

Strana od-do

4586-4601

Kód UT WoS článku

001041305400007

EID výsledku v databázi Scopus

2-s2.0-85139456742