Model checking and strategy synthesis for stochastic games: from theory to practice

Conference item

Probabilistic model checking is an automatic procedure for establishing if a desired property holds in a probabilistic model, aimed at verifying quantitative probabilistic specifications such as the probability of a critical failure occurring or expected time to termination. Much progress has been made in recent years in algorithms, tools and applications of probabilistic model checking, as exemplified by the probabilistic model checker PRISM (www.prismmodelchecker.org). However, the unstoppable rise of autonomous systems, from robotic assistants to self-driving cars, is placing greater and greater demands on quantitative modelling and verification technologies. To address the challenges of autonomy we need to consider collaborative, competitive and adversarial behaviour, which is naturally modelled using game-theoretic abstractions, enhanced with stochasticity arising from randomisation and uncertainty. This paper gives an overview of quantitative verification and strategy synthesis techniques developed for turn-based stochastic multi-player games, summarising recent advances concerning multi-objective properties and compositional strategy synthesis. The techniques have been implemented in the PRISM-games model checker built as an extension of PRISM.

Authors: Kwiatkowska, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl
• Host title: ICALP2016: 43rd International Colloquium on Automata, Languages and Programming
• Journal: ICALP2016: 43rd International Colloquium on Automata, Languages and Programming
• Pages: 4:1-4:18
• Publication date: 2016-07-01
• Acceptance date: 2016-06-04
• DOI: 10.4230/LIPIcs.ICALP.2016.4
• EISSN: 1868-8969
• ISSN: 1868-8969
• Keywords: Model checking; Stochastic games; Temporal logic; Strategy synthesis; Quantitative verification