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