Reactive synthesis of dominant strategies
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 ---...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for the Advancement of Artificial Intelligence
2023
|
| _version_ | 1824458911621578752 |
|---|---|
| author | Aminof, B De Giacomo, G Rubin, S |
| author_facet | Aminof, B De Giacomo, G Rubin, S |
| author_sort | Aminof, B |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-12-09T03:37:32Z |
| format | Conference item |
| id | oxford-uuid:920d1b0d-b449-4a17-a2e9-ad051e13d082 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-02-19T04:33:25Z |
| publishDate | 2023 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:920d1b0d-b449-4a17-a2e9-ad051e13d0822025-01-16T11:04:23ZReactive synthesis of dominant strategiesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:920d1b0d-b449-4a17-a2e9-ad051e13d082EnglishSymplectic ElementsAssociation for the Advancement of Artificial Intelligence2023Aminof, BDe Giacomo, GRubin, SWe 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. |
| spellingShingle | Aminof, B De Giacomo, G Rubin, S Reactive synthesis of dominant strategies |
| title | Reactive synthesis of dominant strategies |
| title_full | Reactive synthesis of dominant strategies |
| title_fullStr | Reactive synthesis of dominant strategies |
| title_full_unstemmed | Reactive synthesis of dominant strategies |
| title_short | Reactive synthesis of dominant strategies |
| title_sort | reactive synthesis of dominant strategies |
| work_keys_str_mv | AT aminofb reactivesynthesisofdominantstrategies AT degiacomog reactivesynthesisofdominantstrategies AT rubins reactivesynthesisofdominantstrategies |