Synthesis of Optimal Resilient Control Strategies

Christel BaierChristel Baier, Clemens DubslaffClemens Dubslaff, Ľuboš KorenčiakĽuboš Korenčiak, Antonín KučeraAntonín Kučera, Vojtěch ŘehákVojtěch Řehák

DOI Link

Christel Baier, Clemens Dubslaff, Ľuboš Korenčiak, Antonín Kučera, Vojtěch Řehák
Synthesis of Optimal Resilient Control Strategies
Proc. of the 15th International Symposium on Automated Technology for Verification and Analysis (ATVA), volume 10482 of Lecture Notes in Computer Science, 417--434, 2017. Springer

Details
Bibtex

KurzfassungAbstract
Repair mechanisms are important within resilient systems to maintain the system in an operational state after an error occurred. Usually, constraints on the repair mechanisms are imposed, e.g., concerning the time or resources required (such as energy consumption or other kinds of costs). For systems modeled by Markov decision processes (MDPs), we introduce the concept of resilient schedulers, which represent control strategies guaranteeing that these constraints are always met within some given probability. Assigning rewards to the operational states of the system, we then aim towards resilient schedulers which maximize the long-run average reward, i.e., the expected mean payoff. We present a pseudo-polynomial algorithm that decides whether a resilient scheduler exists and if so, yields an optimal resilient scheduler. We show also that already the decision problem asking whether there exists a resilient scheduler is PSPACE-hard.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-68167-2_27.

@inproceedings{BDKK{2017,
  author    = {Christel Baier and Clemens Dubslaff and {\v{L}}ubo{\v{s}}
               Koren{\v{c}}iak and Anton{\'{\i}}n Ku{\v{c}}era and Vojt{\v{e}}ch
               {\v{R}}eh{\'{a}}k},
  title     = {Synthesis of Optimal Resilient Control Strategies},
  booktitle = {Proc. of the 15th International Symposium on Automated Technology
               for Verification and Analysis (ATVA)},
  series    = {Lecture Notes in Computer Science},
  volume    = {10482},
  publisher = {Springer},
  year      = {2017},
  pages     = {417--434},
  doi       = {10.1007/978-3-319-68167-2_27}
}