On-the-fly Synthesis for LTL over Finite Traces

Shengping Xiao, Jianwen Li, Shufang Zhu, Yingying Shi, Geguang Pu, Moshe Y. VardiAAAI 2021 · DOI

Introduction

Linear Temporal Logic over finite traces (LTL$_f$) is a critical framework in AI planning and formal verification for specifying system behaviors over finite horizons. The synthesis problem—automatically generating a strategy that satisfies a given formula against an adversarial environment—traditionally relies on a two-step process: converting the formula into a Deterministic Finite Automaton (DFA) and then solving a game on that DFA. However, the DFA construction is often doubly exponential in the size of the formula, creating a significant computational bottleneck.

This paper introduces a new framework, OLFS, which bypasses the construction of the full DFA by employing lightweight pre-processing and an on-the-fly state exploration strategy.

Methodology: On-the-fly Exploration

The proposed framework avoids the "DFA bottleneck" through two primary mechanisms:

1. Lightweight Pre-processing

Before initiating state exploration, OLFS applies several quick checks to prune the search space:

  • Satisfiability/Validity: Trivial results are identified immediately if the formula is impossible to satisfy or universally true.
  • Length-1 Trace Check (satOnce): Determines if the goal can be achieved in a single step.
  • Formula Projection: Identifies unrealizable formulas by analyzing the first-position elements of traces, allowing for early termination if the first round is unwinnable.

2. On-the-fly TDFA Games

When pre-processing is insufficient, the framework utilizes a Transition-based DFA (TDFA) to explore the state space incrementally. Instead of mapping the entire DFA, OLFS generates successor states only as needed using SAT-based techniques.

On-the-fly state exploration and strategy propagation in OLFS.

As illustrated in the figure above, the system propagates "winning" or "failure" information back up the search tree as soon as it is discovered. This backtracking procedure allows the search to stop immediately once a strategy is found or proven non-existent, often before the majority of the DFA is constructed.

Experimental Evaluation

The researchers evaluated OLFS against 430 standard benchmarks and specific formula patterns (Until and Global/Finally) designed to test scalability.

Key Results

  • Exponential Speedups: On specific patterns, OLFS demonstrated linear-cost performance. While state-of-the-art tools like SYFT and LISASYNT exhibited exponential runtime growth as formula scale increased, OLFS maintained near-constant performance.
  • Benchmark Performance: OLFS solved 149 of the 430 benchmarks. Although symbolic tools solved more instances overall (~280), OLFS was uniquely faster on 50 instances, highlighting its value in a portfolio-based approach.
Comparison of run times across formula scales for OLFS, Syft, and LisaSynt.

The performance gap shown in the figure above underscores the efficiency of avoiding full DFA construction. For certain classes of specifications, the pre-processing and on-the-fly techniques turn an exponential-time problem into a nearly linear-time one.

Conclusion and Future Work

OLFS demonstrates that LTL$_f$ synthesis can be treated as a search problem rather than a complete construction problem. By focusing on the relevant portions of the state space, it achieves significant speedups on specific formula classes. The primary limitation remains the computational overhead of generating individual states via SAT solvers. Future research will focus on optimizing on-the-fly state generation to further reduce exploration costs.

Summary updated

BibTeX
@inproceedings{xiao2021fly,
  author = {Shengping Xiao and Jianwen Li and Shufang Zhu and Yingying Shi and Geguang Pu and Moshe Y. Vardi},
  title = {{On-the-fly Synthesis for LTL over Finite Traces}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16809},
}
Figure