2021
IJCAI
IJCAI 2021
Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up
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.
🌉
Interdisciplinary Bridge
- Artificial Intelligence and Knowledge & Reasoning and Mathematics & Optimization