Quantitative Strategy Templates
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913805506707456 |
|---|---|
| author | Anand, Ashwani Nayak, Satya Prakash Raha, Ritam Sağlam, Irmak Schmuck, Anne-Kathrin |
| author_facet | Anand, Ashwani Nayak, Satya Prakash Raha, Ritam Sağlam, Irmak Schmuck, Anne-Kathrin |
| contents | This paper presents (permissive) \emph{Quantitative Strategy Templates} (QaSTels) to succinctly represent infinitely many winning strategies in two-player energy and mean-payoff games. This transfers the recently introduced concept of \emph{Permissive (qualitative) Strategy Templates} (PeSTels) for $ω$-regular games to games with quantitative objectives. We provide the theoretical and algorithmic foundations of (i) QaSTel synthesis, and (ii) their (incremental) combination with PeSTels for games with mixed quantitative and qualitative objectives. Using a prototype implementation of our synthesis algorithms, we demonstrate empirically that QaSTels extend the advantageous properties of strategy templates over single winning strategies -- known from PeSTels -- to games with (additional) quantitative objectives. This includes (i) the enhanced robustness of strategies due to their runtime-adaptability, and (ii) the compositionality of templates w.r.t. incrementally arriving objectives. We use control-inspired examples to illustrate these superior properties of QaSTels for CPS design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16528 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantitative Strategy Templates Anand, Ashwani Nayak, Satya Prakash Raha, Ritam Sağlam, Irmak Schmuck, Anne-Kathrin Computer Science and Game Theory This paper presents (permissive) \emph{Quantitative Strategy Templates} (QaSTels) to succinctly represent infinitely many winning strategies in two-player energy and mean-payoff games. This transfers the recently introduced concept of \emph{Permissive (qualitative) Strategy Templates} (PeSTels) for $ω$-regular games to games with quantitative objectives. We provide the theoretical and algorithmic foundations of (i) QaSTel synthesis, and (ii) their (incremental) combination with PeSTels for games with mixed quantitative and qualitative objectives. Using a prototype implementation of our synthesis algorithms, we demonstrate empirically that QaSTels extend the advantageous properties of strategy templates over single winning strategies -- known from PeSTels -- to games with (additional) quantitative objectives. This includes (i) the enhanced robustness of strategies due to their runtime-adaptability, and (ii) the compositionality of templates w.r.t. incrementally arriving objectives. We use control-inspired examples to illustrate these superior properties of QaSTels for CPS design. |
| title | Quantitative Strategy Templates |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2504.16528 |