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

Benjamin Aminof; Giuseppe De Giacomo; Sasha Rubin

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

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence

Main Track. Pages 1766-1772. https://doi.org/10.24963/ijcai.2021/243

PDF BibTeX

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.

Keywords:

Knowledge Representation and Reasoning: Action, Change and Causality

Planning and Scheduling: Theoretical Foundations of Planning

Agent-based and Multi-agent Systems: Formal Verification, Validation and Synthesis