---
title: "Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up"
authors:
  - "Benjamin Aminof"
  - "Giuseppe De Giacomo"
  - "Sasha Rubin"
doi: "10.24963/ijcai.2021/243"
url: "https://ijcai.org/proceedings/2021/243"
pdf: "https://ijcai.org/proceedings/2021/0243.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "1766-1772"
track: "Main Track"
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"
---

# 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*, pages 1766-1772. DOI: [10.24963/ijcai.2021/243](https://doi.org/10.24963/ijcai.2021/243)

## 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.