Planning for Temporally Extended Goals in Pure-Past Linear Temporal Logic (Extended Abstract)

Luigi Bonassi, Giuseppe De Giacomo, Marco Favorito, Francesco Fuggitti, Alfonso Emilio Gerevini, Enrico ScalaIJCAI 2024

Abstract

This paper introduces a highly efficient method for solving planning problems with temporally extended goals (TEGs) using Pure-Past Linear Temporal Logic (PPLTL). By shifting from forward-looking temporal logics to a past-oriented perspective, the authors demonstrate that complex trajectory requirements can be compiled into standard classical planning problems with minimal overhead. The resulting tool, Plan4Past (P4P), achieves significantly higher coverage, faster compilation times, and shorter plan lengths compared to state-of-the-art $LTL_f$ compilation techniques.

Introduction

In classical AI planning, a goal is typically defined as a specific target state. However, real-world tasks often involve temporally extended goals (TEGs)—requirements about the entire trajectory or sequence of states. For example, a robot might need to ensure it performs a specific sequence of safety checks before opening a valve.

While Linear-time Temporal Logic on finite traces ($LTL_f$) is the standard way to express these, its forward-looking nature makes it computationally expensive to integrate into planning. Existing methods to "compile" $LTL_f$ into classical planning often result in an exponential explosion in state variables or require adding "spurious" actions that artificially inflate plan length. This paper addresses this efficiency gap by switching the perspective from the future to the past.

Methodology

The authors propose using Pure-Past Linear Temporal Logic (PPLTL). While $LTL_f$ and PPLTL have the same expressive power, PPLTL looks at the trace backward. The core of their method is a fixpoint characterization that decomposes any PPLTL formula into a present component (what must be true now) and a past component (what was true at the previous step).

By using this decomposition, they transform a PPLTL goal into a set of axioms and derived predicates in a standard planning language (PDDL). This compilation is polynomial in size and adds zero extra actions to the planning process. They implemented this approach in a tool called Plan4Past (P4P).

Experimental Evaluation

The researchers evaluated P4P using a benchmark suite of 152 instances across four classic planning domains: Rovers, BlocksWorld, OpenStacks, and Elevator. They compared P4P against two state-of-the-art $LTL_f$ compilation techniques: Exp (which uses Non-deterministic Finite Automata) and Poly (which uses a polynomial-sized but action-heavy encoding).

Performance comparison of P4P against Exp and Poly methods in terms of coverage and compilation time.

Key Results

  • Higher Coverage: P4P solved 122 out of 152 instances, significantly outperforming the "Poly" method (48 solved) and the "Exp" method (80 solved).
  • Faster Compilation: P4P compiled 94.7% of instances in under 10 seconds. In contrast, $LTL_f$ methods often struggled with compilation time-outs or produced problems too complex for the underlying planner (LAMA) to handle.
  • Plan Efficiency: Because the encoding doesn't require "spurious" actions to update the state of a temporal monitor, the resulting plans are shorter. In the BlocksWorld domain, the "Poly" method required over 6,000 actions to solve a problem that P4P solved in just 104 actions.
Detailed coverage results across different planning domains showing P4P's superior performance.

Discussion and Conclusion

The "Rearview Mirror" advantage of PPLTL allows the planner to check goal satisfaction incrementally without needing to guess or branch on future possibilities. While PPLTL is as expressive as $LTL_f$, it provides a significant computational advantage by adding only a linear number of new variables relative to the goal formula size.

Future work includes developing "PPLTL-aware" planners that handle these logic operators natively to yield even better performance, as well as extending the approach to Fully Observable Non-Deterministic (FOND) planning for more robust real-world applications.

Summary updated

BibTeX
@inproceedings{bonassi2024planning,
  author = {Luigi Bonassi and Giuseppe De Giacomo and Marco Favorito and Francesco Fuggitti and Alfonso Emilio Gerevini and Enrico Scala},
  title = {{Planning for Temporally Extended Goals in Pure-Past Linear Temporal Logic (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure