Publications
Publications › References ›
2014
Technical reports
Permissive Controller Synthesis for Probabilistic Systems
[DFK+14b]
Klaus Draeger, Vojtěch Forejt, Marta Kwiatkowska, David Parker and Mateusz Ujma..
Permissive Controller Synthesis for Probabilistic Systems.
Technical report RR-14-01, Department of Computer Science, University of Oxford.
March 2014.
pdf bib
- Downloads
PDF 542 KB
BibTeX
- Notes
- This is an extended version of [DFK+14].
- Search for this paper
- Google · Google Scholar
Abstract
We propose novel controller synthesis techniques for probabilistic systems
modelled using stochastic two-player games: one player acts as a controller,
the second represents its environment, and probability is used to
capture uncertainty arising due to, for example, unreliable sensors or faulty system components.
Our aim is to generate robust controllers that are
resilient to unexpected system changes at runtime,
and flexible enough to be adapted if additional constraints need to be imposed.
We develop a permissive controller synthesis framework,
which generates multi-strategies for the controller,
offering a choice of control actions to take at each time step.
We formalise the notion of permissiveness using penalties,
which are incurred each time a possible control action is blocked by a multi-strategy.
Permissive controller synthesis aims to generate a multi-strategy that minimises these penalties,
whilst guaranteeing the satisfaction of a specified system property.
We establish several key results about the optimality of multi-strategies
and the complexity of synthesising them.
Then, we develop methods to perform permissive controller synthesis using mixed integer linear programming
and illustrate their effectiveness on a selection of case studies.