Imagine instructing an autonomous robot to perform a complex service mission: "Deliver mail to Room A, then to Room B, but never enter Room C while the floor is wet, and repeat this cycle indefinitely."
For a standard reinforcement learning (RL) agent or motion planner, this instruction is a nightmare. It requires long-term memory (e.g., Did I already visit Room A during this cycle?) and suffers from severe reward sparsity. If the robot only receives a reward upon completing the entire sequence perfectly, it will likely spend millions of steps wandering aimlessly before stumbling upon a valid execution trace.
To solve this, a powerful paradigm has emerged that bridges symbolic reasoning and continuous control. By expressing complex, temporally extended goals in formal languages like Linear Temporal Logic (LTL) and translating them into Finite State Automata, researchers can decompose long-horizon, rule-bound tasks into manageable, localized subgoals.
The Non-Markovian Trap
Standard sequential decision-making frameworks, such as Markov Decision Processes (MDPs), rely on the Markov property: the optimal next action depends solely on the agent's current state. However, tasks involving sequential rules, safety constraints, or temporal dependencies are inherently non-Markovian. The reward depends on the history of execution, not just the immediate configuration of the environment.
As noted by Farzan Memarian et al. in Active Task-Inference-Guided Deep Inverse Reinforcement Learning, simple memory flags or binary status bits fail when an agent must distinguish between identical actions performed at different stages of a temporal hierarchy. Without a structured way to track history, an agent cannot tell whether entering Room B is currently a requirement or a violation.
Restoring the Markov Property via Automata
The core insight of automata-based task representation is that we can compile the history-dependent rules of an LTL formula into a discrete state machine—such as a Deterministic Finite Automaton (DFA) or a Büchi Automaton.
In this architecture, the automaton acts as a high-level supervisor or flowchart. The nodes represent distinct stages of task progress, and the edges represent symbolic transitions triggered by events or observations in the physical world. As explained by Jaime Middleton et al. in Real-Time Heuristic Search with LTLf Goals, reaching an accepting state within the automaton mathematically guarantees that the underlying temporal logic goal has been satisfied.
[ Environment State (s) ] -------> [ Low-Level Policy / Planner ]
|
v
[ Automaton State (q) ] -------> [ Evaluates Transitions (edges) ]
Why does this make the problem solvable? Because it allows us to construct a product state space $(s, q)$, where $s$ is the physical state of the environment and $q$ is the internal state of the automaton. By augmenting the agent's observation with $q$, the history of the task is perfectly summarized by the current automaton node. The problem becomes Markovian once again. Andrea Fanti 0001 et al. leverage this exact mechanism in Transfer Learning between non-Markovian RL Tasks through Semantic Representations of Temporal States to track task progress precisely across varying multi-step instructions.
Modular Decomposition into Reach-Avoid Subgoals
Beyond tracking history, the automaton provides a natural framework for hierarchical task decomposition. Every edge in the automaton defines a localized, short-horizon reach-avoid task: reach the condition that triggers the next state, while avoiding conditions that trigger a violation or a regression.
Instead of forcing a single neural network or motion planner to learn the entire long-horizon mission, the task is broken down into modular pieces. For instance, in The Logical Options Framework, Brandon Araki et al. combine symbolic logic with hierarchical RL options. Because each option is tied to an automaton transition, the learned policies become plug-and-play modules that can be rearranged to solve entirely new tasks zero-shot.
Similarly, Geraud Nangue Tasse et al. introduce Skill Machines in Skill Machines: Temporal Logic Skill Composition in Reinforcement Learning, mapping LTL instructions to a finite state machine where each state executes a specific logical combination of pre-learned skill primitives. This concept is pushed to its logical conclusion in the framework presented in One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learning. By conditioning the low-level policy strictly on the immediate reach-avoid subgoal dictated by the automaton edge, the agent avoids distribution shift entirely when encountering novel or longer task chains at test time.
Bridging Continuous Control and Discrete Logic
This framework acts as a translation layer between high-level semantic reasoning and low-level continuous control or motion planning.
Christian Pek, in SpaTiaL: monitoring and planning of robotic tasks using spatio-temporal logic specifications, demonstrates how compiling spatio-temporal specifications into deterministic finite automata allows a planner to search for valid trajectories while pruning physically impossible spatial configurations early. For continuous systems with complex dynamics, Pushpak Jagtap et al. show in Formal Synthesis of Stochastic Systems via Control Barrier Certificates that converting specifications into a deterministic automaton allows long-term logic to be managed as a series of short-term control objectives solved via Control Barrier Certificates.
When operating in uncertain or unmapped spaces, the automaton serves as an anchor. Mariliza Tzes demonstrates in Reactive Informative Planning for Mobile Manipulation Tasks under Sensing and Environmental Uncertainty that finite state machines allow a mobile manipulator to dynamically determine its order of operations—such as moving an unexpected obstacle out of the way—based on logical constraints rather than fixed, pre-calculated geometric coordinates.
Handling Infinite Horizons and Partial Satisfaction
Real-world missions are not always finite. Tasks like persistent surveillance require infinite-horizon execution, while environmental failures might make a task impossible to complete fully. Automata handle both edges of this spectrum gracefully.
To manage infinite horizons, specifications are often compiled into Büchi Automata, which define acceptance based on cycles that must be visited infinitely often. Wenjie Qiu et al. exploit this property in Instructing Goal-Conditioned Reinforcement Learning Agents with Temporal Logic Objectives, showing that agents can learn persistent behaviors (like oscillating between locations) by finding the lowest-cost loops within the automaton graph that return to an accepting state.
Conversely, if a robot encounters a broken bridge or a locked door that makes its primary goal impossible, it must degrade gracefully. Bruno Lacerda et al. demonstrate in Optimal Policy Generation for Partially Satisfiable Co-Safe LTL Specifications that the quantitative structure of the automaton allows an agent to calculate a policy that maximizes the partial satisfaction of the mission, ensuring the robot does as much useful work as possible rather than freezing up upon failure.
Taming the State-Space Explosion
The primary bottleneck of automata-based methods is computational: translating a complex LTL formula into a DFA can result in an exponential explosion in the number of automaton states ($2^{2^{|LTL|}}$ in the worst case).
To circumvent this memory exhaustion, researchers have developed compact alternative representations. Jorge Torres et al. propose in Polynomial-Time Reformulations of LTL Temporally Extended Goals into Final-State Goals using Alternating Automata. This approach maintains a polynomial-size representation of the goal constraints by offloading the resolution of non-determinism from the compilation phase to the search phase, letting the planner evaluate valid transitions on the fly.
Traditional LTL-to-DFA Compilation:
[ LTL Formula ] ===(Exponential Explosion)===> [ Massive Deterministic Graph ]
Compositional / Alternating Approach:
/---> [ Slave Automaton 1 (Subformula X) ]
[ LTL Formula ] ------> [ Master Automaton ]
\---> [ Slave Automaton 2 (Subformula Y) ]
Another approach is to break the formula down structurally. Javier Esparza et al. introduce a compositional architecture in From LTL to deterministic automata - A safraless compositional approach that decouples the task into a master automaton and multiple slave automata. The master automaton monitors the global formula structure, while each slave automaton independently tracks a specific globally-quantified subformula, keeping the state space modular and computationally tractable.