LTLf and LDLf Synthesis under Partial Observability

Giuseppe De Giacomo, Moshe Y. Vardi

Abstract

Synthesis for temporal logic specifications on finite traces ($LTL_f$ and $LDL_f$) under partial observability is a critical challenge in automated controller generation. This paper demonstrates that this problem remains 2EXPTIME-complete, matching the complexity of the full-observability case. By introducing a novel projection-based automata technique that avoids the traditional, more complex belief-state construction, the authors provide an efficient algorithmic framework for synthesis that is readily implementable.

Introduction

In automated synthesis, the goal is to generate a strategy—a controller or program—that satisfies a logical specification regardless of the environment's actions. While most research assumes full observability, where the agent sees every environment variable, real-world applications often involve partial observability due to sensor limitations or hidden internal states. Historically, moving from full to partial observability often results in a significant jump in computational complexity. This paper investigates whether such a jump occurs for $LTL_f$ (Linear Temporal Logic on finite traces) and $LDL_f$ (Linear Dynamic Logic).

Methodology: The Projection-Based Approach

The authors contrast two primary methods for solving synthesis under partial observability:

1. The Belief-State Construction

Derived from AI planning, this standard approach tracks the "belief state"—the set of all possible states the system could be in given current observations. However, applying this to $LTL_f/LDL_f$ synthesis results in a 3EXPTIME complexity. The process involves converting the logic to a Nondeterministic Finite Automaton (NFA), then to a Deterministic Finite Automaton (DFA), and finally applying the belief-state power-set construction.

2. The Projection-Based Construction

The authors propose a more direct route that avoids the intermediate DFA step, maintaining a lower complexity profile. The algorithm follows four key stages:

  1. Complementation: Start with an automaton representing traces that violate the specification.
  2. Projection: "Hide" unobservable variables by projecting them out, resulting in an NFA that accepts an observable trace if any hidden sequence violates the spec.
  3. Second Complementation: Convert the NFA into a DFA that accepts a trace only if all possible hidden sequences satisfy the original specification.
  4. Game Solving: Treat the resulting DFA as a standard full-observability game.
Summary of synthesis algorithms and complexity for various specification types.

Key Insights and Complexity Analysis

The core finding of this research is complexity parity: synthesis under partial observability for $LTL_f/LDL_f$ is no harder than under full observability. Both are 2EXPTIME-complete. The "cost" of partial observability is effectively absorbed into the existing complexity of the logic.

By avoiding the "belief-state trap," the projection-based approach combines the elimination of angelic nondeterminism with the handling of partial observation in a single, more efficient step. Furthermore, the paper highlights the advantages of finite traces ($LTL_f$) over infinite traces (standard LTL). Finite traces allow for simpler automata operations, such as NFA complementation via subset construction, avoiding the more cumbersome Safra’s construction required for $\omega$-automata.

Results and Conclusion

The paper establishes several key theoretical bounds:

  • Theorem 9: $LTL_f/LDL_f$ synthesis under partial observability is 2EXPTIME-complete.
  • DFA Specifications: If the specification is already a DFA, the problem is EXPTIME-complete.
  • Implementability: The proposed technique relies on standard automata operations (complementation, projection, determinization), making it highly compatible with existing formal methods libraries.

While the theoretical complexity is optimized, future work is needed to evaluate practical performance on large-scale industrial specifications. Additionally, integrating these synthesis techniques into modern planning systems could offer a more robust way to handle complex, temporally-extended goals in partially observable environments.

Summary updated

BibTeX
@inproceedings{giacomo2016ltlf,
  author = {Giuseppe De Giacomo and Moshe Y. Vardi},
  title = {{LTLf and LDLf Synthesis under Partial Observability}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure