Pure-Past Linear Temporal and Dynamic Logic on Finite Traces

Giuseppe De Giacomo, Antonio Di Stasio, Francesco Fuggitti, Sasha RubinIJCAI 2020 · DOI

TL;DR

This paper introduces "pure-past" temporal logics (PLTLf and PLDLf) that reason backward in time. These logics offer an exponential speedup in converting temporal specifications into efficient automata for AI planning and decision-making, compared to traditional "pure-future" logics. The key is leveraging a theoretical result about reversing languages, making past-oriented specifications a practical advantage.

What Problem Does This Paper Address?

Many AI applications, such as planning, reasoning about actions, and specifying system behavior, rely on temporal logic to express goals and constraints. Traditional temporal logics like LTL (Linear Temporal Logic) and PDL (Propositional Dynamic Logic) focus on the future ("what will happen"). However, in many real-world scenarios, it's more natural and intuitive to express properties in terms of the past ("what has happened"). For example, "I've completed the task, and since I was decontaminated, I've been in clean areas" is a past-oriented statement.

While existing logics can express these past-oriented properties, they often require complex translations that lead to computationally expensive representations (e.g., large automata). This paper addresses the challenge of efficiently representing and reasoning about past-oriented temporal specifications, particularly for AI problems involving finite sequences of events (finite traces).

Methods

The core contribution is the introduction and analysis of Pure-Past Linear Temporal Logic on Finite Traces (PLTLf) and its extension, Pure-Past Dynamic Logic on Finite Traces (PLDLf). These logics are designed to reason backward from the end of a finite trace.

The key technical innovation lies in exploiting a theoretical result from automata theory: while converting a standard temporal logic formula to a deterministic finite automaton (DFA) can be doubly exponential in complexity, converting it to a DFA for the reverse language can be done in single exponential time.

The authors achieve this by:

  1. Swapping Operators: Defining a "swap" operation that syntactically transforms past operators into future ones and vice-versa. This allows them to relate PLTLf/PLDLf formulas to LTLf/LDLf formulas on reversed traces.
  2. Automata Construction: Leveraging the fact that an Alternating Finite Automaton (AFA) for a formula can be converted to a DFA for its reverse language in single exponential time. This is the crucial step that provides the exponential advantage.
  3. Algorithm for DFA Conversion: Developing an algorithm (Algorithm 2) that translates PLTLf/PLDLf formulas into DFAs in single exponential time, a significant improvement over the double exponential time required for LTLf/LDLf formulas (Algorithm 1).

Datasets

Not discussed in the paper. The paper focuses on the theoretical foundations and algorithmic improvements for temporal logics rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Past is Powerful (and Efficient): Expressing temporal properties directly using past-oriented logic (PLTLf/PLDLf) can lead to exponentially smaller and more efficiently computable automata compared to using future-oriented logic (LTLf/LDLf) and then translating.
  • The Power of Reversal: A fundamental result in automata theory about reversing languages provides the theoretical backbone for this efficiency gain. It's not just about the logic itself, but how it interacts with automata constructions.
  • Direct Expression is Key: While PLTLf/PLDLf and LTLf/LDLf have the same expressive power, translating between them is computationally expensive. This means that for practical benefits, properties should be natively expressed in the past-oriented logic.
  • Bridging Logic and AI Problems: The improved DFA construction directly impacts the complexity of AI problems like planning in non-deterministic domains, reinforcement learning with non-Markovian rewards, and synthesis, offering exponential speedups.

Key Results

  • Exponential DFA Construction: PLTLf/PLDLf formulas can be translated into equivalent DFAs in single exponential time with respect to the formula size, compared to double exponential time for LTLf/LDLf.
  • Complexity Improvements in AI: This translates to exponential improvements in the complexity of solving problems like:
  • FOND (Fully Observable Nondeterministic Planning) for PLTLf/PLDLf goals: EXPTIME-complete in domain and goal, vs. 2EXPTIME for LTLf/LDLf goals.
  • MDPs with non-Markovian rewards: EXPTIME vs. 2EXPTIME.
  • Planning in non-Markovian domains: EXPTIME vs. 2EXPTIME.
  • Same Expressive Power: PLTLf/PLDLf have the same expressive power as LTLf/LDLf, respectively.

Limitations and Future Work

  • Translation Cost: The paper acknowledges that while PLTLf/PLDLf offer an advantage in DFA construction, the translation from LTLf/LDLf to PLTLf/PLDLf is computationally expensive (triple-exponential in the worst case). This reinforces the idea that properties should be natively expressed in the past-oriented logic.
  • Open Questions on Bounds: The authors note that the bounds for translating between PLTLf/LDLf and LTLf/LDLf (triply exponential) and between PLDLf and RE (doubly exponential) are the best known upper bounds, and it remains an open question whether these bounds are tight.
  • Future Work: The paper suggests that the exponential improvements demonstrated here can be applied to a wider range of AI problems involving temporal specifications, implying further research into these applications. The authors also highlight the need for further investigation into the tightness of the translation bounds.

Summary updated

BibTeX
@inproceedings{giacomo2020pure,
  author = {Giuseppe De Giacomo and Antonio Di Stasio and Francesco Fuggitti and Sasha Rubin},
  title = {{Pure-Past Linear Temporal and Dynamic Logic on Finite Traces}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/690},
}

Loading related content...

Figure