2008
On the Controller Synthesis for Finite-State Markov Decision Processes
KUČERA, Antonín a Oldřich STRAŽOVSKÝZákladní údaje
Originální název
On the Controller Synthesis for Finite-State Markov Decision Processes
Název česky
Algoritmická syntéza řídících jednotek pro konečné Markovovy rozhodovací procesy
Autoři
KUČERA, Antonín (203 Česká republika, garant) a Oldřich STRAŽOVSKÝ (203 Česká republika)
Vydání
Fundamenta Informaticae, Polsko, IOS Press, Nizozemí, 2008, 0169-2968
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.715
Kód RIV
RIV/00216224:14330/08:00025760
Organizační jednotka
Fakulta informatiky
UT WoS
000252980000010
Klíčová slova anglicky
Markov decision process; temporal logic
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 22. 5. 2009 15:13, prof. RNDr. Antonín Kučera, Ph.D.
V originále
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 controller is 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 that the existence of robust controllers is also decidable, and that such controllers are effectively computable if they exist.
Česky
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, že problém existence vhodné řídící jednotky je algoritmicky rozhodnutelný a je podán algoritmus na jeho konstrukci.
Návaznosti
| MSM0021622419, záměr |
| ||
| 1M0545, projekt VaV |
|