Concurrent Permissive Strategy Templates

Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review

Contributors

Abstract

Two-player games on finite graphs provide a rigorous foundation for modeling the strategic interaction between reactive systems and their environment. While concurrent game semantics naturally capture the synchronous interactions characteristic of many cyber-physical systems (CPS), their adoption in CPS design remains limited. Building on the concept of permissive strategy templates (PeSTels) for turn-based games, we introduce concurrent (permissive) strategy templates (ConSTels) – a novel representation for sets of randomized winning strategies in concurrent games with Safety, Büchi, and Co-Büchi objectives. ConSTels compactly encode infinite families of strategies, thereby supporting both offline and online adaptation. Offline, we exploit compositionality to enable incremental synthesis: combining ConSTels for simpler objectives into non-conflicting templates for more complex combined objectives. Online, we demonstrate how ConSTels facilitate runtime adaptation, adjusting action probabilities in response to observed opponent behavior to optimize performance while preserving correctness. We implemented ConSTel synthesis and adaptation in a prototype tool and experimentally show its potential.

Details

Original languageEnglish
Title of host publicationTools and Algorithms for the Construction and Analysis of Systems
EditorsSebastian Junges, Guy Katz
PublisherSpringer, Cham
Pages377-397
Number of pages21
ISBN (electronic)978-3-032-22752-2
ISBN (print)978-3-032-22751-5
Publication statusPublished - 2026
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science
Volume16505
ISSN0302-9743

Conference

Title32nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems
Abbreviated titleTACAS 2026
Conference number32
Descriptionheld as Part of the International Joint Conferences on Theory and Practice of Software, ETAPS 2026
Duration11 - 16 April 2026
Website
Degree of recognitionInternational event
LocationCentro Congressi Lingotto
CityTurin
CountryItaly

External IDs

Scopus 105039644203
ORCID /0000-0002-5321-9343/work/220697672
ORCID /0000-0003-1724-2586/work/220700554
ORCID /0000-0002-3437-0240/work/220701835

Keywords

Keywords

  • Strategy Adaptation, Concurrent Games, Permissive Strategies