Compositional strategy synthesis for stochastic games with multiple objectives

Journal article

Design of autonomous systems is facilitated by automatic synthesis of controllers from formal models and specifications. We focus on stochastic games, which can model interaction with an adverse environment, as well as probabilistic behaviour arising from uncertainties. Our contribution is twofold. First, we study long-run specifications expressed as quantitative multi-dimensional mean-payoff and ratio objectives. We then develop an algorithm to synthesise ε-optimal strategies for conjunctions of almost sure satisfaction for mean payoffs and ratio rewards (in general games) and Boolean combinations of expected mean-payoffs (in controllable multi-chain games). Second, we propose a compositional framework, together with assume-guarantee rules, which enables winning strategies synthesised for individual components to be composed to a winning strategy for the composed game. The framework applies to a broad class of properties, which also include expected total rewards, and has been implemented in the software tool PRISM-games.

Authors: Basset, N; Kwiatkowska, M; Wiltsche, C

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Information and Computation
• Volume: 261
• Issue: 3
• Pages: 536-587
• Publication date: 2017-09-17
• Acceptance date: 2017-03-31
• DOI: 10.1016/j.ic.2017.09.010
• ISSN: 0890-5401