On the Controller Synthesis for Finite-State Markov Decision Processes

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F08%3A00025760" target="_blank" >RIV/00216224:14330/08:00025760 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On the Controller Synthesis for Finite-State Markov Decision Processes

Original language description

We study the problem of effective controller synthesis for finite-state Markov decision processes (MDPs) and the class of properties definable in the logic PCTL extended with long-run average propositions. We show that the existence of such a controlleris decidable, and we give an algorithm which computes the controller if it exists. We also address the issue of ``controller robustness'', i.e., the problem whether there is a controller which still guarantees the satisfaction of a given property when the probabilities in the considered MDP slightly deviate from their original values. From a practical point of view, this is an important aspect since the probabilities are often determined empirically and hence they are inherently imprecise. We show thatthe existence of robust controllers is also decidable, and that such controllers are effectively computable if they exist.

Czech name

Algoritmická syntéza řídících jednotek pro konečné Markovovy rozhodovací procesy

Czech description

V článku se zkoumá problematika algoritmické syntézy řídících jednotek pro konečné Markovovy rozhodovací procesy a třídu vlastností definovatelných pomocí temporální logiky PCTL rozšířené o predikáty umožňující popsat limitní chování běhů. Je ukázáno, žeproblém existence vhodné řídící jednotky je algoritmicky rozhodnutelný a je podán algoritmus na jeho konstrukci.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

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

Name of the periodical

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

—

Volume of the periodical

82

Issue of the periodical within the volume

1-2

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

13

Pages from-to

—

UT code for WoS article

000252980000010

EID of the result in the Scopus database

—