Beyond Winning Strategies: Admissible and Admissible Winning Strategies for Quantitative Reachability Games
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908395642028032 |
|---|---|
| author | Muvvala, Karan Ho, Qi Heng Lahijanian, Morteza |
| author_facet | Muvvala, Karan Ho, Qi Heng Lahijanian, Morteza |
| contents | Classical reactive synthesis approaches aim to synthesize a reactive system that always satisfies a given specifications. These approaches often reduce to playing a two-player zero-sum game where the goal is to synthesize a winning strategy. However, in many pragmatic domains, such as robotics, a winning strategy does not always exist, yet it is desirable for the system to make an effort to satisfy its requirements instead of "giving up". To this end, this paper investigates the notion of admissible strategies, which formalize "doing-your-best", in quantitative reachability games. We show that, unlike the qualitative case, quantitative admissible strategies are history-dependent even for finite payoff functions, making synthesis a challenging task. In addition, we prove that admissible strategies always exist but may produce undesirable optimistic behaviors. To mitigate this, we propose admissible winning strategies, which enforce the best possible outcome while being admissible. We show that both strategies always exist but are not memoryless. We provide necessary and sufficient conditions for the existence of both strategies and propose synthesis algorithms. Finally, we illustrate the strategies on gridworld and robot manipulator domains. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13369 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Beyond Winning Strategies: Admissible and Admissible Winning Strategies for Quantitative Reachability Games Muvvala, Karan Ho, Qi Heng Lahijanian, Morteza Computer Science and Game Theory Formal Languages and Automata Theory Logic in Computer Science Robotics D.2.4; I.2.4; I.2.9 Classical reactive synthesis approaches aim to synthesize a reactive system that always satisfies a given specifications. These approaches often reduce to playing a two-player zero-sum game where the goal is to synthesize a winning strategy. However, in many pragmatic domains, such as robotics, a winning strategy does not always exist, yet it is desirable for the system to make an effort to satisfy its requirements instead of "giving up". To this end, this paper investigates the notion of admissible strategies, which formalize "doing-your-best", in quantitative reachability games. We show that, unlike the qualitative case, quantitative admissible strategies are history-dependent even for finite payoff functions, making synthesis a challenging task. In addition, we prove that admissible strategies always exist but may produce undesirable optimistic behaviors. To mitigate this, we propose admissible winning strategies, which enforce the best possible outcome while being admissible. We show that both strategies always exist but are not memoryless. We provide necessary and sufficient conditions for the existence of both strategies and propose synthesis algorithms. Finally, we illustrate the strategies on gridworld and robot manipulator domains. |
| title | Beyond Winning Strategies: Admissible and Admissible Winning Strategies for Quantitative Reachability Games |
| topic | Computer Science and Game Theory Formal Languages and Automata Theory Logic in Computer Science Robotics D.2.4; I.2.4; I.2.9 |
| url | https://arxiv.org/abs/2408.13369 |