|
David ParkerLecturerSchool of Computer Science University of Birmingham Edgbaston, Birmingham, B15 2TT Email: d.a.parker@cs.bham.ac.uk Tel: +44 (0) 121 41 47264 Office: 107 Office hours: Wed 12.30-1.30, Thu 3-4 |
<< NEWS >>
|
|
[CFK+13b]
Taolue Chen, Vojtěch Forejt, Marta Kwiatkowska, David Parker and Aistis Simaitis.
Automatic Verification of Competitive Stochastic Systems.
Formal Methods in System Design, 43(1), pages 61-92, Springer.
August 2013.
[pdf]
[bib]
[Introduces model checking techniques for stochastic multi-player games, implemented in the PRISM-games tool.]
|
|
Notes:
This is an extended journal version of [CFK+12].
Details of the models and properties presented in the paper are here.
See also the accompanying tool PRISM-games.
The original publication is available at www.springerlink.com.
|
|
Abstract.
We present automatic verification techniques for the modelling and analysis of
probabilistic systems that incorporate competitive behaviour. These systems are
modelled as turn-based stochastic multi-player games, in which the players can either
collaborate or compete in order to achieve a particular goal. We define a
temporal logic called rPATL for expressing quantitative properties of stochastic
multi-player games. This logic allows us to reason about the collective ability
of a set of players to achieve a goal relating to the probability of an event's
occurrence or the expected amount of cost/reward accumulated. We give an
algorithm for verifying properties expressed in this logic and implement the
techniques in a probabilistic model checker, as an extension of the PRISM tool. We demonstrate the
applicability and efficiency of our methods by deploying them to
analyse and detect potential weaknesses in a variety of large case studies,
including algorithms for energy management in Microgrids
and collective decision making for autonomous systems.
|