Mean-Payoff Optimization in Continuous-Time Markov Chains with Parametric Alarms
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00107916" target="_blank" >RIV/00216224:14330/19:00107916 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1145/3310225" target="_blank" >http://dx.doi.org/10.1145/3310225</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3310225" target="_blank" >10.1145/3310225</a>
Alternative languages
Result language
angličtina
Original language name
Mean-Payoff Optimization in Continuous-Time Markov Chains with Parametric Alarms
Original language description
Continuous-time Markov chains with alarms (ACTMCs) allow for alarm events that can be non-exponentially distributed. Within parametric ACTMCs, the parameters of alarm-event distributions are not given explicitly and can be the subject of parameter synthesis. In this line, an algorithm is presented that solves the epsilon-optimal parameter synthesis problem for parametric ACTMCs with long-run average optimization objectives. The approach provided in this article is based on a reduction of the problem to finding long-run average optimal policies in semi-Markov decision processes (semi-MDPs) and sufficient discretization of the parameter (i.e., action) space. Since the set of actions in the discretized semi-MDP can be very large, a straightforward approach based on an explicit action-space construction fails to solve even simple instances of the problem. The presented algorithm uses an enhanced policy iteration on symbolic representations of the action space. Soundness of the algorithm is established for parametric ACTMCs with alarm-event distributions that satisfy four mild assumptions, fulfilled by many kinds of distributions. Exemplifying proofs for the satisfaction of these requirements are provided for Dirac, uniform, exponential, Erlang, and Weibull distributions in particular. An experimental implementation shows that the symbolic technique substantially improves the efficiency of the synthesis algorithm and allows us to solve instances of realistic size.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA18-11193S" target="_blank" >GA18-11193S: Algorithms for Infinite-State Discrete Systems and Games</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
ACM Transactions on Modeling and Computer Simulation (TOMACS)
ISSN
1049-3301
e-ISSN
1558-1195
Volume of the periodical
29
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
26
Pages from-to
„28:1“-„28:26“
UT code for WoS article
000510187600010
EID of the result in the Scopus database
2-s2.0-85075548712