19/08/2021

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

Benjamin Aminof, Giuseppe De Giacomo, Sasha Rubin

Keywords: Knowledge Representation and Reasoning, Action, Change and Causality, Theoretical Foundations of Planning, 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.

 0
 0
 0
 0
This is an embedded video. Talk and the respective paper are published at IJCAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd

Similar Papers