Traditional goal-conditioned reinforcement learning (GCRL) and classical planning frameworks operate under a simple assumption: the goal is a destination. An agent succeeds if it reaches a specific target state or configuration. However, real-world instructions are rarely static. They are often temporally extended goals—objectives defined over an entire sequence of actions and states. For example, a robot might be told to "visit the kitchen, then the living room, but never enter the bedroom while the lights are off."
Standard state-based reward functions fail here because they lack memory. If an agent is currently in the living room, a standard Markovian policy cannot know whether it already visited the kitchen or if it violated a safety constraint three steps ago. Early work in temporal planning recognized that standard snapshot models struggle with duration and ordering. To solve this, modern frameworks bridge formal verification and control by compiling temporal logic directly into the agent's decision-making loop.
The Automaton Bridge
How do we optimize for a goal that depends on history without destroying the mathematical convenience of the Markov property? The core mechanism relies on translating temporal specifications—typically written in Linear Temporal Logic (LTL) or its finite-trace variant ($LTL_f$)—into a state machine, such as a Deterministic Finite Automaton (DFA).
As formalized by Giuseppe De Giacomo et al. in Synthesis for LTL and LDL on Finite Traces, any $LTL_f$ formula can be represented as an automaton where transitions are triggered by events or states in the environment.
The magic happens when we take the cross-product of the environment's state space and the automaton's state space. The automaton state acts as an uncompressed, minimal representation of the task's history. By tracking the current automaton state alongside the physical environment state, a non-Markovian history-dependent task is transformed back into a standard Markovian reachability problem. The agent's new goal is simply to reach an accepting state in the automaton.
Decoupling Logic from Physical Execution
One of the greatest advantages of this approach is modularity. Instead of training an agent from scratch for every new temporal instruction, the automaton structure allows us to decouple high-level logical reasoning from low-level physical execution.
In Instructing Goal-Conditioned Reinforcement Learning Agents with Temporal Logic Objectives, Wenjie Qiu et al. demonstrate this by using a learned goal value function alongside a Büchi automaton. The automaton dictates which subgoals are relevant next, and the low-level goal-conditioned policy executes them. This architecture enables zero-shot generalization: if an agent knows how to reach individual states, it can immediately execute an infinite variety of unseen temporal logic formulas.
Similarly, Boris Katz et al. in Compositional RL Agents That Follow Language Commands in Temporal Logic use a compositional neural network that mirrors the syntax tree of an LTL command. This allows agents to execute complex, multi-stage instructions without task-specific retraining.
Compositional Task Algebras
Instead of viewing every task as an isolated problem, recent frameworks treat tasks as elements of a structured algebra. Geraud Nangue Tasse et al. show in Generalisation in Lifelong Reinforcement Learning through Logical Composition that by treating tasks as elements of a Boolean algebra, agents can logically compose base skills using operators like AND, OR, and NOT.
To extend this to strict temporal ordering, researchers integrate sequential composition. For instance, Kevin Leahy et al. in Run-Time Task Composition with Safety Semantics introduce a runtime framework that composes pre-trained reinforcement learning tasks while strictly respecting safety semantics. By structuring tasks this way, an agent can dynamically reconfigure its existing skills to satisfy complex, multi-stage missions on the fly.
Translating Human Intent to Formal Logic
While automata provide a robust mathematical foundation for planners, humans do not naturally communicate in LTL formulas. To bridge this gap, modern systems leverage the semantic power of Large Language Models (LLMs) to translate natural language into formal temporal constraints.
In Grounding Complex Natural Language Commands for Temporal Tasks in Unseen Environments, Jason Xinyu Liu et al. introduce a modular framework that uses LLMs to parse complex instructions into LTL, decoupling spatial landmark grounding from temporal reasoning. This allows robots to safely navigate long-horizon tasks in entirely unseen environments.
Similarly, Mathieu Tuli et al. develop a framework in Learning to Follow Instructions in Text-Based Games that equips text-based agents with the ability to internally track the progress of sequential instructions, preventing the "instruction blindness" common in purely neural architectures.
Managing Real-World Uncertainty and Constraints
In practice, executing temporally extended goals requires adapting to environmental uncertainty and safety boundaries. Alberto Camacho addresses this in Planning under Uncertainty and Temporally Extended Goals by combining probabilistic planning with LTL translations, allowing agents to maintain safety and ordering rules even when environmental transitions are stochastic.
When the environment changes unexpectedly, real-time adaptation becomes critical. Ruoyu Wang 0032 et al. tackle this in Sampling-based path planning under temporal logic constraints with real-time adaptation by utilizing a dual-root sampling tree. This structure allows a robot to instantly revise its path around dynamic obstacles without forgetting its overall progress through the logical stages of its mission, ensuring that long-term temporal constraints are never violated during local avoidance maneuvers.
Key Foundational Work
Planning Using a Temporal World Model (1983) — contributed 1 concept elements to this direction.