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 Mathematics & Optimization
🧭
Keyword Pioneer
— best-effort synthesis
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning