# Planning for Temporally Extended Goals in Pure-Past Linear Temporal Logic: A Polynomial Reduction to Standard Planning

arXiv: https://arxiv.org/abs/2204.09960 · HTML: https://mlsanity.com/paper/2204.09960/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 59 references that are in the map.
- First posted on arXiv 21 Apr 2022.

## Builds on (most cited first, 6 of 6)

- [Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective](https://mlsanity.com/paper/2003.00330/) (2020)
- [Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specifications](https://mlsanity.com/paper/1807.06333/) (2018)
- [First-Order vs. Second-Order Encodings for LTLf-to-Automata Translation](https://mlsanity.com/paper/1901.06108/) (2019)
- [Stochastic Fairness and Language-Theoretic Fairness in Planning on Nondeterministic Domains](https://mlsanity.com/paper/1912.11203/) (2019)
- [Expressivity of Planning with Horn Description Logic Ontologies (Technical Report)](https://mlsanity.com/paper/2203.09361/) (2022)
- [Reactive Synthesis from Extended Bounded Response LTL Specifications](https://mlsanity.com/paper/2008.05335/) (2020)

## Built on by (most cited first, 2 of 2)

- [Play Everywhere: A Temporal Logic based Game Environment Independent Approach for Playing Soccer with Robots](https://mlsanity.com/paper/2405.12628/) (2024)
- [Logical Regression for Planning with Axioms](https://mlsanity.com/paper/2607.21414/) (2026)

## Abstract (arXiv)

We study temporally extended goals expressed in Pure-Past LTL (PPLTL). PPLTL is particularly interesting for expressing goals since it allows to express sophisticated tasks as in the Formal Methods literature, while the worst-case computational complexity of Planning in both deterministic and nondeterministic domains (FOND) remains the same as for classical reachability goals. However, while the theory of planning for PPLTL goals is well understood, practical tools have not been specifically investigated. In this paper, we make a significant leap forward in the construction of actual tools to handle PPLTL goals. We devise a technique to polynomially translate planning for PPLTL goals into standard planning. We show the formal correctness of the translation, its complexity, and its practical effectiveness through some comparative experiments. As a result, our translation enables state-of-the-art tools, such as FD or MyND, to handle PPLTL goals seamlessly, maintaining the impressive performances they have for classical reachability goals.