Effective Approach to LTLf Best-Effort Synthesis in Multi-Tier Environments

Benjamin Aminof, Giuseppe De Giacomo, Gianmarco Parretti, Sasha RubinIJCAI 2024

Introduction

Synthesizing robust AI agents for complex, unpredictable environments remains a significant challenge. Traditional formal synthesis often adopts an "all-or-nothing" approach, requiring a strategy that guarantees success against any possible environment behavior. However, real-world models are frequently too pessimistic, leading synthesis tools to conclude that no winning strategy exists. This paper, presented at IJCAI-24, addresses this by proposing a "best-effort" synthesis framework for Linear Temporal Logic on finite traces ($LTL_f$) within multi-tier environments.

Multi-Tier Best-Effort Synthesis

Instead of a flat environment model, the authors propose a hierarchy of models or "tiers." For instance, Tier 1 might represent expected normal behavior, while higher tiers represent increasingly adversarial or catastrophic conditions. Best-effort synthesis seeks a strategy that wins against the maximal set of environment responses across these tiers, based on the principle of non-domination.

Previous solutions relied on computationally expensive infinite tree automata. This work shifts the foundation to Deterministic Finite Automata (DFA) games. The core innovation is moving from a "product-based" approach—which suffers from exponential state-space explosion—to an "on-the-fly" approach. By solving DFA games for each tier independently and combining results greedily at runtime, the complexity of action selection becomes linear relative to the number of tiers.

Experimental Evaluation

The authors implemented their approach in a tool called MtSyft. Evaluation was conducted using a "Counter Game" benchmark, where an agent must increment a $k$-bit counter to a target value despite varying environment requests.

Scalability of MtSyft vs. cb-MtSyft as the number of tiers increases.

As shown in Figure 2, the tool demonstrates impressive scalability. The optimized variant, cb-MtSyft, designed for environments sharing a common base specification, maintains significantly lower runtimes as the number of tiers increases compared to the standard MtSyft.

Performance metrics (Coverage and Avg. RT) for MtSyft and cb-MtSyft across different counter bit sizes.

The results in Figure 3 highlight that the primary bottleneck is not the number of tiers, but the inherent complexity of the $LTL_f$ goal. While the tool handles many tiers effectively, performance drops sharply as the counter size increases to 9 or 10 bits, reflecting the "double-exponential" wall of $LTL_f$-to-DFA conversion.

Conclusion

The proposed DFA-based approach enables practical best-effort synthesis for complex AI agents. By decoupling tier solving, the algorithm achieves linear scalability and allows for easy parallelization. Future work includes supporting weakened goals for higher tiers and integrating the framework with PDDL for broader AI planning applications.

Summary updated

BibTeX
@inproceedings{aminof2024effective,
  author = {Benjamin Aminof and Giuseppe De Giacomo and Gianmarco Parretti and Sasha Rubin},
  title = {{Effective Approach to LTLf Best-Effort Synthesis in Multi-Tier Environments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure