Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up

Aminof, Benjamin; De Giacomo, Giuseppe; Rubin, Sasha

doi:10.24963/ijcai.2021/243

Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up

Benjamin Aminof, Giuseppe De Giacomo, Sasha Rubin

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1766-1772.

https://doi.org/10.24963/ijcai.2021/243

Keywords

Planning and Scheduling: Theoretical Foundations of Planning
Knowledge Representation and Reasoning: Action, Change and Causality
Agent-based and Multi-agent Systems: Formal Verification, Validation and Synthesis

Abstract

We study best-effort synthesis under environment assumptions specified in LTL, and show that this problem has exactly the same computational complexity of standard LTL synthesis: 2EXPTIME-complete. We provide optimal algorithms for computing best-effort strategies, both in the case of LTL over infinite traces and LTL over finite traces (i.e., LTLf). The latter are particularly well suited for implementation.

Benjamin Aminof, Giuseppe De Giacomo, and Sasha Rubin. 2021. Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1766–1772. https://doi.org/10.24963/ijcai.2021/243

@inproceedings{ijcai2021p243,
  title     = {Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up},
  author    = {Aminof, Benjamin and De Giacomo, Giuseppe and Rubin, Sasha},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {1766--1772},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/243},
  url       = {https://doi.org/10.24963/ijcai.2021/243},
}

TY  - CPAPER
TI  - Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up
AU  - Aminof, Benjamin
AU  - De Giacomo, Giuseppe
AU  - Rubin, Sasha
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 1766
EP  - 1772
DO  - 10.24963/ijcai.2021/243
UR  - https://doi.org/10.24963/ijcai.2021/243
ER  -