Polynomial-Time Reformulations of LTL Temporally Extended Goals into Final-State Goals

Jorge Torres, Jorge A. BaierIJCAI 2015

Introduction

In automated planning, goals are traditionally defined as a set of conditions to be met in a final state. However, many real-world applications require temporally extended goals (TEGs), which impose constraints on the entire sequence of states in a plan. Linear Temporal Logic (LTL) is the standard formalism for expressing these constraints. While LTL goals can be compiled into standard planning problems, existing state-of-the-art methods often suffer from an "exponential explosion" in the size of the resulting problem, rendering complex goals computationally intractable. This research presents a novel compilation technique that ensures polynomial-time translation by leveraging Alternating Automata (AA).

The Polynomial-Time Compilation Approach

The primary bottleneck in traditional LTL compilation is the reliance on Finite State Automata (FSA). To track the satisfaction of an LTL formula, FSA-based methods must represent all possible valid states of the automaton within the planning state, leading to an exponential increase in fluents.

The proposed method shifts this complexity from the state representation to the search process. By using Alternating Automata, the compiler only needs to track a single run of the automaton. The non-determinism inherent in the AA is resolved by the planner during search. This is achieved through synchronization actions, which update the internal state of the goal-tracking automaton after each world action.

Table 1: Definition of synchronization actions, including preconditions and effects for various LTL operators.

As shown in Table 1, these actions manage the transition logic for operators like conjunction ($\wedge$), disjunction ($\vee$), and temporal operators like "Until" ($U$) and "Release" ($R$). This approach ensures that the translation remains polynomial relative to the size of the input LTL formula.

Experimental Evaluation

The effectiveness of the AA-based compilation was evaluated using modified benchmarks from the 2006 International Planning Competition (IPC), including the Rovers, Openstacks, and Blocksworld domains. Since these domains lack native TEGs, the authors generated families of LTL formulas (labeled 'a' through 'j') with increasing levels of nesting and complexity.

The study compared the new method against the established Baier & McIlraith (B&M) translator. Several variants of the AA-based method were tested, including those using "Positive Goals" (PG) to assist heuristic search and "Ordering for Synchronization Actions" (OSA) to constrain the sequence of internal updates.

Results and Analysis

The experimental results demonstrate a significant advantage for the polynomial-time approach as goal complexity increases.

Table 2: Performance comparison across different domains and LTL formula families. TT: Translation Time, PL: Plan Length, PT: Planning Time, PS: States Searched.

Key observations from the data in Table 2 include:

  • Scalability: For "deep" or highly nested LTL formulas, the B&M translator frequently failed (marked as 'NR' or 'Not Reachable') due to memory or time limits during the exponential compilation phase. In contrast, the AA-based method consistently produced solvable planning problems.
  • Translation Efficiency: Translation time (TT) for the AA-based method was nearly instantaneous and remained stable regardless of formula complexity, whereas B&M's TT scaled poorly.
  • Heuristic Impact: The inclusion of Positive Goals (PG) proved essential. Without them, planners often struggled to find solutions because the heuristic could not effectively gauge progress toward the temporal goal.
  • Plan Length Trade-off: The AA-based method results in longer total plan lengths (PL) because it counts synchronization actions. However, the number of "real-world" actions remains comparable to traditional methods.

Conclusion

By offloading the complexity of LTL satisfaction from the compiler to the planner's search space, this research provides a scalable path for solving planning problems with complex temporal constraints. While the overhead of synchronization actions can make the method slower for very simple goals, its polynomial-time guarantee makes it the only viable option for the "deep" temporal logic required in sophisticated autonomous systems.

Summary updated

BibTeX
@inproceedings{torres2015polynomial,
  author = {Jorge Torres and Jorge A. Baier},
  title = {{Polynomial-Time Reformulations of LTL Temporally Extended Goals into Final-State Goals}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure