Quantitative Strategy Templates
Ashwani Anand, Satya Prakash Nayak, Ritam Raha, Irmak Sağlam, Anne-Kathrin Schmuck · 2025
Read Quantitative Strategy Templates by Ashwani Anand, Satya Prakash Nayak, Ritam Raha, Irmak Sağlam, Anne-Kathrin Schmuck (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16528.txt.
Introduction
Ashwani Anand, Satya Prakash Nayak, Ritam Raha, Irmak Sağlam, and Anne-Kathrin Schmuck extend strategy templates to games with numeric payoffs. Their paper from twenty twenty-five works on two-player energy and mean-payoff games. A template stands for infinitely many winning strategies at once. Qualitative templates for omega-regular games came first. Their QaSTels carry the idea to quantity.
Foundations cover how to build such templates and how to merge them with the qualitative kind. Mixed goals, part numeric and part logical, then fit one frame. A prototype tool runs the synthesis. Tests show the perks hold: runtime flexibility beats a single fixed strategy, and templates compose as new goals arrive. Control-style cases show the gains in action. The work serves cyber-physical system design.
Catalog record
| CREATOR | Ashwani Anand, Satya Prakash Nayak, Ritam Raha, Irmak Sağlam, Anne-Kathrin Schmuck |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-16528
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantitative Strategy Templates Ashwani Anand, Satya Prakash Nayak, Ritam Raha, Irmak Sağlam, Anne-Kathrin Schmuck Abstract This paper presents (permissive) 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 Permissive (qualitative) Strategy Templates (PeSTels) for ω \omega -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. 1 Introduction Two player games on finite graphs provide a powerful abstraction for modeling the strategic interactions between reactive systems and their environment. In this context, game-based abstractions are often enriched with quantitative information to model aspects like energy consumption, cost minimization, or maintaining system performance thresholds under varying conditions. As a result, games with quantitative objectives, such as energy [ 7 ] or mean-payoff [ 28 ] have gained significant attention in recent years. These games have been applied to a wide range of CPS problems, such as energy management in electric vehicles [ 7 ] , optimizing resource-constrained task management in autonomous robots [ 18 , 22 ] , embedded systems [ 10 ] , and dynamic resource allocations [ 5 ] . In practical CPS applications, strategic control decisions (i.e., the moves of the controller player in the abstract game) are typically implemented via low-level actuators. For instance, a robot’s strategic decision to move to a different room involves motion control integrated with LiDAR-based obstacle avoidance. However, due to unmodeled dynamics of the physical environment that become observable only at runtime, strategic adaptations may be necessary [ 26 , 17 ] . For example, if the robot detects that an entrance is obstructed by obstacles (e.g., humans), it should dynamically adjust its strategy and navigate through an alternative door instead. Therefore, synthesized (high-level) control strategies must not only be correct-by-design, but also flexible enough to accommodate runtime adaptations. This control-inspired property of strategies has recently been formalized via permissive strategy templates (PeSTels) [ 2 ] , which are similar to classical strategies but contain a vast set of relevant strategies in a succinct and simple data structure. Intuitively, PeSTels localize required progress towards \omega -regular objectives by classifying outgoing edges of a control-player vertex as unsafe, co-live and live – indicating edges to be taken never, finitely often and infinitely often, respectively, in case the source vertex of the edge is visited infinitely often. Inspired by PeSTels and driven by the need to capture quantitative objectives in CPS design, this paper introduces Quantitative Strategy Templates (QaSTels) for games with energy and mean-payoff objectives. n the context of the previously discussed robot example, such games model scenarios where a robot with limited battery must make informed re-routing decisions at runtime, ensuring that its remaining energy suffices for the required tasks. Similar to PeSTels, QaSTels localize necessary information about the future of the game. In contrast to PeSTels, which localize liveness requirements induced by a qualitative objective, QaSTels consider quantitative objectives and thereby localize the required energy loss and gain through local edge annotations. Knowing the current energy level at runtime, the control player can select from all edges that remain feasible given the available energy. This contrasts with standard game-solving approaches, which typically store only a single (optimal) action per node. Concretely, our contributions are as follows: (i) We formalize QaSTels for energy and mean-payoff objectives, and present algorithms to extract winning strategies from them. (ii) We introduce an edge-based value iteration algorithm to compute winning QaSTels and show that QaSTels are permissive , i.e., they capture all winning strategies for energy objectives and all finite-memory winning strategies for mean-payoff objectives. (iii) We combine QaSTels with a bounded version of PeSTels, and propose an efficient incremental algorithm for updating templates and strategies under newly arriving qualitative and quantitative objectives. (iv) We highlight the advantages of strategy templates for games with quantitative objectives, and the combination of quantitative and qualitative objectives, via extensive experiments on benchmarks derived from the SYNTCOMP benchmark suit. Detailed proofs for all claims are provided in the appendix. Related Work. The computation of permissive strategies has received significant attention over the past decade, particularly for qualitative objectives [ 6 , 25 , 8 , 20 ] . A key development in this area is the introduction of permissive strategy templates (PeSTels) by Anand et al. [ 2 , 1 ] , which capture a strictly broader class of winning strategies while maintaining the same worst-case computational complexity as standard game-solving techniques. This paper extends the idea behind PeSTels to quantitative games. When only ‘classical’ synthesis algorithms are available, achieving the adaptability of strategies that motivate PeSTels requires recomputing a new strategy from scratch whenever moves become unavailable at runtime or additional objectives arise. For the objectives considered in this paper, this entails using ‘classical’ synthesis algorithms for energy objectives [ 7 ] , mean-payoff objectives [ 28 , 9 ] , multi mean-payoff objectives [ 27 ] , and mean-payoff co-Büchi objectives [ 12 , 11 ] . However, since these approaches recompute strategies from scratch at each iteration, they are computationally expensive. Our benchmark experiments demonstrate that QaSTel-based adaptations offer a more efficient alternative for the applications considered. 2 Preliminaries In this section, we introduce the basic notations used throughout the paper. We denote \mathbb{Z} as the set of integers, \mathbb{Q} as the set of rational numbers, \mathbb{N} as the set of natural numbers including 0, and \mathbb{N}_{>0} as the set of positive integers. Let \mathbb{N}_{\infty}=\mathbb{N}\cup\{\infty\} and \mathbb{Z}_{\infty}=\mathbb{Z}\cup\{\infty,-\infty\} . The interval \color[rgb]{0,0,0}\mathopen{[}a;b\mathclose{)} represents the set \{a,a+1,\cdots,b\} . 2.1 Two-Player Games A two-player game graph is a pair G=(V,E) , where V=V_{0}\uplus V_{1} is a finite set of nodes, E\subseteq V\times V is a set of edges. The nodes are partitioned into two sets, V_{0} and V_{1} , where V_{i} represents the set of nodes controlled by Player i for i\in\{0,1\} . Further, we write E_{i} to denote the set of edges originating from nodes in V_{i} , i.e., E_{i}=E\cap(V_{i}\times V) . Given a node v , we write E(v) to denote the set \{e\in E\mid e=(v,v^{\prime})\text{ for }v^{\prime}\in V\} of all outgoing edges from v . Value Functions. For a set of nodes V , and a set of edges E let \mathcal{F}_{V} denote \{f\mid f:V\rightarrow\mathbb{N}_{\infty}\} , and \mathcal{F}_{E} denote \{f\mid f:E\rightarrow\mathbb{N}_{\infty}\} . Plays. A play \rho=v_{0}v_{1}\ldots\in V^{\omega} on G is an infinite sequence of nodes starting from v_{0} such that, (v_{i},v_{i+1})\in E for each i . We denote the i^{th} node v_{i} of \rho as \rho[i] and use the notations \rho[0;i]=v_{0}\ldots v_{i} , \rho[i;j]=v_{i}\ldots v_{j} , and \rho[i;\infty]=v_{i}\ldots to denote a prefix , infix , and suffix of \rho , respectively. We write v\in\rho (resp. e\in\rho ) to