D 2018

Continuous-Time Markov Decisions Based on Partial Exploration

ASHOK, Pranav, Yuliya BUTKOVA, Holger HERMANNS a Jan KŘETÍNSKÝ

Základní údaje

Originální název

Continuous-Time Markov Decisions Based on Partial Exploration

Autoři

ASHOK, Pranav (356 Indie), Yuliya BUTKOVA (860 Uzbekistán), Holger HERMANNS (276 Německo) a Jan KŘETÍNSKÝ (203 Česká republika, garant, domácí)

Vydání

Cham, Automated Technology for Verification and Analysis. ATVA 2018, od s. 317-334, 18 s. 2018

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

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

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/18:00108289

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-01089-8

ISSN

DOI

UT WoS

000723531300019

Klíčová slova anglicky

Continuous-Time Markov Decision Processes; reachability; Partial Exploration

Štítky

Změněno: 16. 5. 2022 14:35, Mgr. Michal Petr

Anotace

V originále

We provide a framework for speeding up algorithms for time-bounded reachability analysis of continuous-time Markov decision processes. The principle is to find a small, but almost equivalent subsystem of the original system and only analyse the subsystem. Candidates for the subsystem are identified through simulations and iteratively enlarged until runs are represented in the subsystem with high enough probability. The framework is thus dual to that of abstraction refinement. We instantiate the framework in several ways with several traditional algorithms and experimentally confirm orders-of-magnitude speed ups in many cases.

Návaznosti

GA18-11193S, projekt VaV
Název: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy
Investor: Grantová agentura ČR, Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy