Planning for Temporally Extended Goals

This direction is merged into another direction: temporally extended goals. Its last version stays readable and citable here.

Version 1 of 149 papers53 conceptsfrozen 2026-10-04

In classical automated planning, the objective is usually simple: find a sequence of actions that ends in a specific state. You are at point A; you want to be at point B. However, real-world tasks are rarely just about the destination. They are about the journey—maintaining safety protocols, following specific sequences of events, or ensuring certain conditions remain true throughout execution.

Researchers like Chitta Baral and Sheila A. McIlraith have spearheaded a shift toward Temporally Extended Goals (TEGs). Instead of a single target state, these goals define requirements over the entire execution trace of a plan.

The Limits of Reachability

Standard planners are "reachability" engines. They use heuristics to estimate the distance between the current state and a goal state. But as Jorge A. Baier and Sheila A. McIlraith point out in Planning with First-Order Temporally Extended Goals using Heuristic Search, this fails when the goal is a constraint like "never let the fuel drop below 20%" or "visit the hospital only after picking up the medicine."

In these cases, the "goal" isn't a place you arrive at; it's a property of the path you took. Traditional planners can't "see" these constraints because they only look at the current state, not the history or the future requirements of the trajectory.

Translating Logic into State

The breakthrough in this field is the use of Linear Temporal Logic (LTL) to formally describe these complex behaviors. LTL allows us to use operators like Always ($\square$), Eventually ($\diamond$), and Until ($\mathcal{U}$) to map out temporal dependencies.

The core intuition for why this works is Automata-Based Compilation. To make a classical planner understand an LTL goal, we translate the logic into a finite-state automaton—a "monitor" machine.

  1. The automaton represents the progress of the temporal goal.
  2. As the planner simulates actions, it also "updates" the state of this automaton.
  3. The goal of the planner then becomes reaching a state where the automaton is in an "accepting" condition.

By doing this, we transform a complex path-based constraint into a simple state-based reachability problem. Jorge Torres and Jorge A. Baier demonstrated in Polynomial-Time Reformulations of LTL Temporally Extended Goals into Final-State Goals that using Alternating Automata can prevent the "exponential explosion" of states that usually plagues these translations, making it computationally feasible for large-scale problems.

Finite vs. Infinite Horizons

A key distinction in this research is the time horizon. While theoretical computer science often deals with infinite traces (systems that run forever), AI agents usually perform tasks with a clear beginning and end.

Giuseppe De Giacomo and Moshe Y. Vardi introduced $LTL_f$ (LTL over finite traces) in Synthesis for LTL and LDL on Finite Traces. This allows planners to reason about goals that must be satisfied within a specific execution window. Building on this, Alberto Camacho and Alberto Rivas extended these concepts to Non-Deterministic (FOND) planning, where an agent must satisfy temporal goals even when action outcomes are uncertain.

Looking Backward to Move Forward

While most temporal logic looks forward ("Eventually X will happen"), a recent innovation involves looking backward. Luigi Bonassi and colleagues, in Planning for Temporally Extended Goals in Pure-Past Linear Temporal Logic, argue that Pure-Past LTL (PPLTL) is often more efficient for planning.

In PPLTL, the goal is defined by what has already happened (e.g., "I can only enter the lab if I have previously put on a mask"). Because the past is fixed, the planner only needs to track a small amount of "history" in the current state, leading to faster solving times and shorter plans compared to forward-looking logics that must account for all possible future paths.

Beyond Achievement: Preferences and Safety

This framework isn't just for "must-have" goals. It also allows for preferences. Tran Cao Son and Enrico Pontelli developed the $\mathcal{PP}$ language, which uses temporal logic to let users specify "soft" goals, such as "I'd prefer to avoid highways, but only if it doesn't double the travel time."

By treating the entire trajectory as the object of interest, this research direction enables AI agents to move beyond simple task completion toward sophisticated, context-aware behavior that respects safety, user preference, and complex operational logic.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_planning_for_temporally_extended_goals_c652b669,
  title = {Planning for Temporally Extended Goals},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/planning-for-temporally-extended-goals/rdr_c652b66924034b7ab4b0fa5952a0130c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_planning_for_temporally_extended_goals_c652b669_v1,
  title = {Planning for Temporally Extended Goals},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/planning-for-temporally-extended-goals/rdr_c652b66924034b7ab4b0fa5952a0130c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}