Partitioning Techniques in LTLf Synthesis

Lucas Martinelli Tabajara, Moshe Y. VardiIJCAI 2019 · DOI

TL;DR

This paper investigates the effectiveness of partitioning techniques for LTLf (Linear Temporal Logic over Finite Traces) synthesis, a crucial problem in robotics and AI. While partitioning has been successful in model checking, the authors demonstrate that it actually hinders performance in LTLf synthesis due to an inability to effectively exploit state-space minimization, leading to significantly larger BDDs and longer computation times.

What Problem Does This Paper Address?

Decomposing complex problems into smaller, manageable subproblems is a cornerstone of computational thinking. In formal verification, this "partitioning" approach has been instrumental in scaling BDD-based model checking to handle large state spaces. This technique has also found success in related areas like Boolean synthesis. Recently, researchers have explored applying partitioning to LTLf synthesis, a finite-horizon version of reactive synthesis with applications in robotics. LTLf synthesis aims to automatically generate a system (a function) that satisfies a given temporal logic specification over finite execution traces. The current state-of-the-art for LTLf synthesis relies on BDD-based symbolic algorithms, similar to those used in model checking. A major bottleneck in these algorithms is the construction of a Deterministic Finite Automaton (DFA) that represents the specification, which can become prohibitively large. Partitioning offers a potential solution by breaking down the synthesis problem into smaller, independently synthesized components, hoping to reduce the overall complexity of DFA construction.

Methods

The paper proposes integrating partitioning into LTLf synthesis by decomposing an LTLf formula into its conjunctive subformulas. Each subformula is then translated into a separate DFA. The "partitioned DFA" is then represented by the collection of these individual DFAs. The core of the LTLf synthesis algorithm, a fixpoint computation to find winning states, is then adapted to work with this partitioned representation. The authors detail how to symbolically represent these component DFAs using BDDs (Binary Decision Diagrams) and how to adapt the fixpoint algorithm to operate on these partitioned BDDs. A key aspect is the attempt to perform "early quantification" of variables to keep intermediate BDDs smaller, a heuristic that has proven useful in other contexts.

Datasets

The paper introduces three new benchmark families for evaluating LTLf synthesis:

  • Single Counter: A simple example where the system's behavior is determined by the environment, focusing on proving realizability.
  • Double Counters: Similar to the single counter, but with two counters, one controlled by the environment and one by the system, where the system's goal is to "catch up."
  • Nim: A generalized version of the game of Nim, requiring more complex strategic reasoning.

These benchmarks are designed to scale with parameters (n and m) that increase the number of moves required to win the game, making them more suitable for evaluating synthesis algorithms than previous benchmarks that often resulted in very shallow winning strategies.

Key Insights and Ideas

  • Partitioning Hinders LTLf Synthesis: The most significant finding is that, contrary to expectations, partitioning does not improve performance for LTLf synthesis. Instead, it leads to a substantial performance degradation.
  • State-Space Minimization is Crucial: The paper strongly suggests that the inability of partitioning to effectively exploit state-space minimization is the root cause of its failure in LTLf synthesis. While partitioning might create a more compact transition relation, it leads to a much larger state space for the winning states, which BDDs struggle to represent efficiently.
  • Early Quantification Isn't Enough: While techniques like early quantification can help manage BDD sizes in other scenarios, they are insufficient to overcome the fundamental issue of state-space explosion introduced by partitioning in LTLf synthesis.
  • BDD Blow-up: The fixpoint computation for finding winning states exhibits a dramatic increase in BDD sizes when using the partitioned approach, often growing by orders of magnitude compared to the monolithic approach.

Key Results

  • Increased Running Time: The partitioned approach resulted in significantly longer running times, often by orders of magnitude, compared to the monolithic approach. In many cases, the partitioned version timed out or ran out of memory, while the monolithic version completed successfully.
  • Larger BDDs: Figures and tables clearly show that the BDDs representing the winning states grow much larger and faster in the partitioned approach during the fixpoint computation. For instance, in the Single-Counter benchmarks, BDD sizes in the partitioned approach become orders of magnitude larger than in the monolithic approach by the time the fixpoint stabilizes.
  • DFA Construction Benefit Nullified: While partitioning did make the initial DFA construction more feasible (finishing in under a second), this benefit was completely overshadowed by the massive overhead during the winning strategy computation.

Limitations and Future Work

  • Limited Benchmark Scope: While the introduced benchmarks are more suitable than previous ones, the authors acknowledge that their evaluation encompasses only a few families. They suggest that further testing on a wider range of synthesis problems is needed.
  • Domain-Specific Partitioning: The authors propose that for partitioning to be effective in LTLf synthesis, it might require domain-specific knowledge to partition problems in a way that still allows for significant minimization.
  • Beyond Classic Partitioning: The paper concludes that classic partitioning techniques are insufficient for LTLf synthesis. Future work should explore more sophisticated decomposition techniques, potentially drawing inspiration from alternative approaches for Boolean relations or novel notions of decomposition for relations and DFAs. The key will be to find decomposition methods that can effectively leverage state-space minimization.
  • Infinite-Horizon LTL: The authors note that their findings focus on LTLf and do not definitively answer whether similar partitioning approaches would be effective for standard, infinite-horizon LTL synthesis. However, they speculate that similar state-space explosion issues might arise, albeit potentially to a lesser degree due to the different role of minimization.

Summary updated

BibTeX
@inproceedings{tabajara2019partitioning,
  author = {Lucas Martinelli Tabajara and Moshe Y. Vardi},
  title = {{Partitioning Techniques in LTLf Synthesis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/777},
}
Figure