⚡ electrical engineering

Learning Linear Temporal Specifications from Demonstrations with Uncertainty

This paper presents a novel framework for learning minimal Linear Temporal Logic (LTL) specifications from uncertain demonstrations by modeling trace uncertainty via Hamming distance and reducing the problem to Pseudo-Boolean Optimization, thereby outperforming existing methods in recovering ground-truth formulas under noisy conditions.

Original authors: Parastou Fahim, Constantino Lagoa, Rômulo Meira-G'oes

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Parastou Fahim, Constantino Lagoa, Rômulo Meira-G'oes

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to behave by showing it a video of a perfect day. You want the robot to learn the rules: "If the room is hot and occupied, turn on the AC." But here's the catch: the video you recorded is glitchy. Maybe a sensor hiccuped, a frame got corrupted, or a measurement was slightly off. The robot sees a version of the day that is almost right, but with some fuzzy, uncertain parts.

Most existing methods for teaching robots are like strict teachers who assume the video is perfect. If the video shows the AC turning on when the room is cold, those methods might get confused or invent weird, complicated rules to explain the mistake. They assume the error is just a "labeling" mix-up (like calling a cat a dog), but they don't account for the video itself being blurry or incomplete.

This paper introduces a new, more forgiving approach called Robust LTL Learning. Instead of demanding the video be perfect, this method says, "Okay, this video is fuzzy. Let's imagine all the possible versions of this video that could have caused this glitch."

The "What-If" Bubble

The authors use a mathematical tool called Hamming distance to create a "bubble" of possibilities around every glitchy video. Think of it like a safety net. If your recorded video shows the AC turning on at step 3, but you know the sensor might be off by one step, the method doesn't just look at step 3. It looks at step 2, step 3, and step 4. It creates a group of "trace estimates"—all the possible ways the day could have actually happened within that small margin of error.

The big idea is this: We don't need to know exactly which version of the video is the true one. We just need to find a rule that works for at least one version inside that bubble.

The "Group" Rule

In the old way, if a video was labeled "Good Behavior," the robot had to follow the rule perfectly for that specific video. If the video was noisy, the robot failed.

In this new method, the robot looks at the whole group of possible videos. It asks, "Is there any version of this group where the rule holds true?" If the answer is yes, the robot accepts it. This is like a detective who knows a witness might be slightly confused about the time. Instead of throwing the witness out, the detective says, "As long as the suspect was in the building at some point during the time window the witness mentioned, the alibi holds."

The Results: A Closer Look

The authors tested this idea using a Heating, Ventilation, and Air Conditioning (HVAC) system. They set up a ground-truth rule: "Always, if the room is hot and occupied, then the AC must turn on in the next step."

They then took this perfect rule and intentionally messed up the data to simulate sensor errors, creating uncertainty windows where variables were changed. They compared their new method against two other approaches:

Flie: A standard method that doesn't handle uncertainty well.
Modified Flie: A tweaked version that tries to fix some issues but still assumes the data is mostly correct.

What happened?

Flie often gave up on the complex time-based rules entirely, learning simple but wrong patterns like "If it's not hot, then it's hot later" (which makes no sense).
Modified Flie did better, sometimes catching parts of the rule, but it often got the cause-and-effect backward. It would learn that "If the AC is on, then the room is occupied," which is the reverse of the truth.
The Robust Method (the authors' new approach) managed to recover the correct temporal structure in most cases, but it still frequently flipped the causal direction compared to the ground truth. For instance, while the true rule is "Occupancy + Heat → AC," the robust method often learned "AC → Occupancy." However, despite this reversal, it was much closer to the intended system behavior than the other methods because it successfully preserved the critical timing relationships (like "next step") that the others missed.

However, there is a trade-off. The paper notes that this new method takes longer to compute. In the HVAC tests, while the other methods took about 0.8 to 4.4 seconds, the robust method took anywhere from 6.5 to 73.1 seconds depending on the complexity. It's like the robot is taking a deep breath and thinking harder to make sure it gets it right, rather than just guessing quickly.

What This Means (and What It Doesn't)

The paper explicitly rules out the idea that we can just ignore the noise or assume the data is perfect. It argues that previous methods fail because they treat uncertain data as if it were a simple labeling error, rather than a corrupted signal.

The authors suggest that their method is a more promising direction for real-world applications where sensors fail. They show through simulations (using synthetic data and the HVAC example) that their method recovers formulas that are "more closely aligned" with the truth than current state-of-the-art methods, even if the logic isn't always perfect.

They do not claim to have solved the problem completely. In fact, they admit their results are "preliminary." They didn't prove it works on every possible robot or in every real-world disaster scenario yet. They simply showed that in these specific tests, looking at the "bubble" of possibilities helps the robot learn better rules than looking at the blurry video alone.

So, if you're a curious teenager building a robot that has to deal with glitchy sensors, this paper suggests: don't just trust the video. Imagine all the ways it could have been different, find a rule that fits at least one of those possibilities, and your robot will be much less likely to crash into a wall because of a single bad pixel.

Technical Summary: Learning Linear Temporal Specifications from Demonstrations with Uncertainty

Problem Statement

The paper addresses the challenge of inferring Linear Temporal Logic (LTL) specifications from system demonstrations in safety-critical domains (e.g., robotics, autonomous vehicles). While existing approaches for learning LTL from positive and negative traces assume that the traces themselves are correctly captured and only account for label misclassification errors, real-world data often suffers from trace uncertainty. This uncertainty arises from sensor faults, measurement errors, data loss, or communication delays, resulting in corrupted, incomplete, or inconsistent traces.

Current methods, which treat observed traces as ground truth, fail to recover accurate specifications when the trace content itself is uncertain. The authors define the Robust LTL Learning Problem: finding a minimal LTL formula that explains system behavior despite bounded uncertainty in the observed traces, rather than assuming the traces are perfectly accurate.

Methodology

The proposed framework models trace uncertainty and integrates it into a Pseudo-Boolean Optimization problem. The methodology proceeds through the following steps:

1. Modeling Trace Uncertainty

The authors quantify uncertainty using the Hamming distance between an observed trace and potential "correct" traces.

Trace Estimate Group ( $C^k_{tr}$ ): Given an observed trace $tr$ and an uncertainty bound $k$ , the set of trace estimates includes all traces within a Hamming distance of $k$ from $tr$.
Assumption: The true system behavior is assumed to be one of the traces within this uncertainty group, not necessarily the observed trace itself.

2. Robust Learning Formulation

The learning problem is reformulated to handle these groups rather than individual traces:

Group Misclassification: Instead of requiring every observed trace to satisfy the formula, the framework requires that at least one trace from each uncertainty group (for positive traces) satisfies the formula, and at least one trace from each negative uncertainty group does not satisfy it.
Loss Function: A group misclassification loss function, $\ell_g$ , is defined. It penalizes cases where no trace in an uncertainty group is consistent with the learned formula.

3. Algorithmic Implementation (Pseudo-Boolean Optimization)

The problem is encoded into a propositional formula $\Phi$ and solved using Max-SMT (specifically Pseudo-Boolean Optimization). The formula consists of four constraint categories:

Syntax Constraints ( $\Phi_{syn}$ ): Ensures the learned formula adheres to valid LTL grammar (represented as a syntax tree).
Semantic Constraints ( $\Phi_{sem}$ ): Encodes the satisfaction relation between traces and the LTL formula.
Selection Constraints ( $\Phi_{sel}$ ): Introduces binary variables $z_{tr}$ to select which specific trace estimate from an uncertainty group is used for learning. If a trace is selected ( $z_{tr}=1$ ), it must satisfy (or not satisfy) the formula.
Group Constraints ( $\Phi_{grp}$ ): A soft constraint enforcing that for every observed trace, at least one trace estimate from its uncertainty group is selected ( $z_{tr'}=1$ ).

The objective is to minimize the group misclassification loss (weighted by the number of traces) while satisfying all hard constraints. This is solved by minimizing a Pseudo-Boolean objective function.

Key Contributions

Novel Problem Formulation: The paper introduces the "Robust LTL Learning Problem," explicitly addressing uncertainty in trace content (corruption/incompleteness) rather than just label noise.
Uncertainty Modeling: The use of Hamming distance to define trace estimate groups allows the system to consider a range of possible "true" behaviors for any given observation.
Group-Based Constraints: The framework enforces that at least one trace per uncertainty group must be consistent with the learned formula, preventing the learning algorithm from being misled by corrupted data points.
Optimization Approach: The reduction of the robust learning problem to an equivalent Pseudo-Boolean Optimization problem, solvable via SMT solvers (e.g., Z3).

Experimental Results

The authors evaluated their method against state-of-the-art SAT-based learning approaches (specifically the "Flie" algorithm and a "Modified Flie" variant that incorporates user constraints) using two benchmarks:

HVAC Control System: A real-world scenario with atomic propositions for temperature, occupancy, and AC status.
Synthetic LTLf Patterns: Experiments using various ground-truth LTL formulas with injected uncertainty.

Findings:

Accuracy: The proposed robust learning method recovered specifications that were more closely aligned with ground-truth formulas compared to existing methods.
Temporal Relationships: While standard methods (Flie) often failed to capture temporal dependencies or learned spurious relationships under uncertainty, and Modified Flie partially recovered relationships but often inverted causal directions, the robust method consistently preserved critical temporal structures (e.g., global conditions and immediate dependencies).
Computational Cost: The robust method required more computation time than the baselines. The authors attribute this to the increased complexity of Pseudo-Boolean optimization compared to standard Max-SAT.

Significance and Claims

The paper claims that its framework bridges the gap between theoretical LTL learning and practical scenarios where data is imperfect. By effectively capturing uncertainty during the specification learning process, the method enables the inference of minimal, interpretable LTL formulas that reflect true system behaviors even when input traces are noisy or incomplete.

The authors position this work as a step toward more robust formal verification and controller synthesis in safety-critical systems. They modestly note that while the results are preliminary, the approach offers a "more principled and promising direction" compared to current state-of-the-art methods that assume trace integrity. Future work is identified as the development of formal distance metrics to quantitatively compare learned specifications against ground truth.