We study the synthesis under environment specifications problem for LTL/LTLf which, in particular, generalizes FOND (strong) planning with these temporal goals. We consider the case where the agent cannot enforce its goal - for which the argument for using best-effort strategies has been made - and study the intermediate ground, between enforcing and best-effort strategies, of dominant strategies. Intuitively, such strategies achieve the goal against any environment for which it is achievable. We show that dominant strategies may exist when enforcing ones do not, while still sharing with the latter many desirable properties such as being interchangeable with each other, and being monotone with respect to tightening of environment specifications. We give necessary and sufficient conditions for the existence of dominant strategies, and show that deciding if they exist is 2EXPTIME-complete - the same as for enforcing strategies. Finally, we give a uniform, optimal, game-theoretic algorithm for simultaneously solving the three synthesis problems of enforcing, dominant, and best-effort strategies.

Reactive Synthesis of Dominant Strategies / Aminof, B.; De Giacomo, G.; Rubin, S.. - 37:5(2023), pp. 6228-6235. (Intervento presentato al convegno National Conference of the American Association for Artificial Intelligence tenutosi a Washington; USA) [10.1609/aaai.v37i5.25767].

Reactive Synthesis of Dominant Strategies

Aminof B.
;
De Giacomo G.
;
2023

Abstract

We study the synthesis under environment specifications problem for LTL/LTLf which, in particular, generalizes FOND (strong) planning with these temporal goals. We consider the case where the agent cannot enforce its goal - for which the argument for using best-effort strategies has been made - and study the intermediate ground, between enforcing and best-effort strategies, of dominant strategies. Intuitively, such strategies achieve the goal against any environment for which it is achievable. We show that dominant strategies may exist when enforcing ones do not, while still sharing with the latter many desirable properties such as being interchangeable with each other, and being monotone with respect to tightening of environment specifications. We give necessary and sufficient conditions for the existence of dominant strategies, and show that deciding if they exist is 2EXPTIME-complete - the same as for enforcing strategies. Finally, we give a uniform, optimal, game-theoretic algorithm for simultaneously solving the three synthesis problems of enforcing, dominant, and best-effort strategies.
2023
National Conference of the American Association for Artificial Intelligence
Linear temporal logic; planning; reactive synthesis; best-effort strategies
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Reactive Synthesis of Dominant Strategies / Aminof, B.; De Giacomo, G.; Rubin, S.. - 37:5(2023), pp. 6228-6235. (Intervento presentato al convegno National Conference of the American Association for Artificial Intelligence tenutosi a Washington; USA) [10.1609/aaai.v37i5.25767].
File allegati a questo prodotto
File Dimensione Formato  
Aminof_Reactive-Synthesis_2023.pdf

accesso aperto

Note: https://ojs.aaai.org/index.php/AAAI/article/download/25767/25539
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 145.91 kB
Formato Adobe PDF
145.91 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1728606
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact