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, 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quantitative Strategy Templates

  • Ashwani Anand,
  • Satya Prakash Nayak,
  • Ritam Raha,
  • Irmak Sağlam,
  • Anne-Kathrin Schmuck

摘要

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, 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.