⚡ electrical engineering

Complete Abstractions of Monotone Control Systems: From Model-based to Data-Driven Systems

This paper introduces the approximate strong upper alternating simulation (ASUAS) to construct a complete pair of upper- and lower-sparse abstractions for monotone control systems, enabling provably tunable controller synthesis and verification in both model-based and data-driven settings.

Original authors: Adnane Saoud, Anas Makdesi, Mohamed Maghenem, Antoine Girard, Murat Arcak

Published 2026-08-10

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Adnane Saoud, Anas Makdesi, Mohamed Maghenem, Antoine Girard, Murat Arcak

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 drive a car safely through a busy city. You want to be absolutely sure it never crashes, never runs a red light, and always keeps a safe distance from other cars. This is the world of control theory, the science of making machines behave the way we want them to. But real-world systems are messy and complicated. To solve this, engineers often use a trick called abstraction: they build a simplified, "cartoon" version of the real system to test their ideas. If the cartoon works, they hope the real thing will too. However, there's a catch. Sometimes these cartoons are too strict, telling the robot "don't move!" when it could actually move safely. Other times, they are too loose, letting the robot try things that are actually dangerous. The big challenge is finding a way to know exactly how close the cartoon is to reality, and having a way to tighten or loosen that gap whenever we need to.

This paper tackles that exact problem, but with a special focus on systems that have a "one-way" flow, like water moving downhill or traffic flowing in one direction. These are called monotone systems. The authors, a team of researchers from universities in Morocco, Germany, France, and the USA, introduce a new way to build these safety-checking cartoons. Instead of just making one simplified model, they build a pair of models: a "super-safe" version that is very strict, and a "super-permissive" version that is very loose. Think of it like drawing a safety zone with two lines: a red line that says "You definitely cannot cross this," and a green line that says "You definitely can cross this." If the robot can find a path between these lines, the authors can prove it will work in the real world. If it can't find a path even in the loose version, they know for sure the real robot can't do it either. This "complete pair" approach solves a long-standing headache where engineers were left guessing if a failure was due to a bad robot or just a bad map.

The New "Safety Sandwich"

The core of this paper is a new mathematical tool called ASUAS (Approximate Strong Upper Alternating Simulation). In plain English, this is a rulebook for comparing the real robot to its cartoon version. The authors realized that for monotone systems, you don't need the cartoon to be a perfect copy of the real thing; you just need to know which way is "up" and which way is "down."

They use this rulebook to build their "Safety Sandwich":

The Top Bun (Upper-Sparse Abstraction): This is the strict, conservative model. It's like a safety guard who is afraid of everything. If this model says "No, you can't go there," then you can be 100% sure the real robot shouldn't go there either. If you can find a controller (a set of instructions) for this strict model, you can translate it directly to the real robot, and it will be safe.
The Bottom Bun (Lower-Sparse Abstraction): This is the loose, optimistic model. It's like a safety guard who thinks everything is fine. If this model says "No, you can't go there," then the real robot definitely can't go there either. This is the magic part: if the strict model fails but the loose model also fails, you know for a fact that no controller exists for the real robot. You stop wasting time trying to solve an impossible problem.

The authors prove that these two models together form a complete abstraction pair. This means they cover all the bases. You aren't left in the dark wondering, "Did my robot fail because it's broken, or because my map was too strict?" With this pair, you know exactly where you stand.

Tuning the Gap

One of the coolest features of this paper is that the authors show you can tune the gap between the strict and loose models. Imagine the space between the red and green lines is a foggy zone where you aren't sure if the robot is safe or not. The authors show that by making the "grid" of your map finer (like switching from a low-resolution pixelated image to a high-definition one), you can shrink that foggy zone. They provide a mathematical formula that tells you exactly how fine your grid needs to be to get a specific level of precision. If you want to be super precise, you just use a finer grid. This turns a vague guess into a guaranteed calculation.

Learning from Data, Not Just Math

The paper doesn't stop at using perfect mathematical models. The authors know that in the real world, we often don't have the perfect equations for how a system works. We only have data—logs of what the robot did in the past. So, they extend their method to data-driven systems.

Instead of using the equations of the car, they use a dataset of 10,000 points (in their simulations) collected from the car's movements. They build the strict and loose models directly from this data.

They show that if you have enough data points, you can build a "data-driven strict model" that is just as safe as the one built from perfect math.
They even calculated how many data points you need to be confident in your result. For their example, they found that with about 517,939 random samples, you have a 90% confidence that your data-driven map is accurate enough to replace the math-based one.

The Car Test Drive

To prove this works, the authors ran simulations with a vehicle model. They set up a scenario where a car (the follower) had to stay behind another car (the leader) without crashing, while keeping its speed within safe limits.

The Result: They built the strict and loose models. The strict model gave them a "safe zone" that was smaller than the real car's actual safe zone, but they knew for sure that anything inside that zone was safe. The loose model gave a larger zone.
The Gap: When they used a coarse grid (fewer points), there was a noticeable gap between the two models. But when they followed their own advice and used a finer grid (280 by 60 states instead of 20 by 14), the gap shrank dramatically. The safe zone from the strict model almost perfectly matched the real car's actual safe zone.
The Data Test: When they switched to using only data (no math equations), the results held up. The controller built from data was at least as conservative as the one built from math, exactly as the theory predicted, proving that the data-driven approach is "correct-by-construction."

What This Means

This paper doesn't just suggest a new idea; it provides a proven framework with mathematical guarantees. It rules out the old way of guessing whether a controller exists or not. By using this "Safety Sandwich" of strict and loose models, engineers can now:

Guarantee safety: If the strict model works, the real system works.
Prove impossibility: If the loose model fails, the real system is impossible to control for that task.
Control precision: They can adjust the grid size to get as close to the truth as they need.

The authors are careful to note that while this works beautifully for monotone systems (like traffic flow or biological signaling), it's a specific type of system. They suggest that future work could try to apply these ideas to more complex, mixed-up systems. But for now, they have handed engineers a powerful new tool to build safer, smarter robots without needing to guess in the dark.

Title: Complete Abstractions of Monotone Control Systems: From Model-based to Data-Driven Systems

Problem Statement
The paper addresses the challenge of synthesizing controllers for monotone control systems that satisfy logic specifications, particularly within the framework of symbolic control. While existing methods can construct "sound" abstractions (where a controller for the abstraction refines to the original system), they often suffer from conservativeness. Specifically, if a controller cannot be found for a sound abstraction, it remains undecidable whether a controller exists for the original system. Furthermore, most existing complete abstraction techniques rely on incremental stability properties, which are restrictive, or require explicit system models, which are often unavailable in practice. The authors aim to bridge the gap between model-based and data-driven settings by developing a framework that provides complete abstractions (deciding both existence and non-existence of controllers) for monotone systems without requiring incremental stability, and extends these results to settings where only finite sampled data is available.

Methodology
The proposed methodology is built upon a new behavioral relation and a pair of sparse abstractions:

Approximate Strong Upper Alternating Simulation (ASUAS): The authors introduce a new behavioral relation, $\varepsilon$ -ASUAS, tailored for monotone systems. Unlike traditional relations that enforce output closeness (bisimulation or approximate simulation), ASUAS enforces an output ordering ( $H_1(x_1) \leq H_2(x_2) + \varepsilon$ ). Crucially, it requires that for every input in the abstract system, all smaller inputs in the concrete system (within the partial order) are valid and can be matched. This structure allows the abstract controller to be more permissive, admitting a larger set of valid control inputs.
Complete Abstraction Pairs (Model-Based):
- Upper-Sparse Abstraction ( $U\Sigma$ ): Constructed using the upper bounds of state intervals and worst-case disturbances. It simulates the original system ( $U\Sigma \preceq S\Sigma$ ). A controller synthesized for $U\Sigma$ can be refined into a controller for the original system.
- Lower-Sparse Abstraction ( $L\Sigma$ ): Constructed using lower bounds of state intervals. The original system simulates this abstraction ( $S\Sigma \preceq L\Sigma$ ). If no controller exists for $L\Sigma$ , then no controller exists for the original system.
- Together, $(U\Sigma, L\Sigma)$ form a complete abstraction pair, allowing the decision of controller existence for the original system.
Controlling Conservativeness: The paper provides a constructive approach to tune the gap between the upper and lower abstractions. By relating the abstractions to a perturbed version of the system ( $S_{\Sigma\varepsilon}$ ) and utilizing bounds on the system's Jacobian (Assumption 5), the authors derive a relationship between the desired precision $\varepsilon$ and the state-space discretization parameter $\eta$ . This ensures that the conservativeness gap can be made arbitrarily small by refining the discretization.
Data-Driven Extension: The framework is extended to data-driven settings where the system model $f$ is unknown.
- Data-Driven Abstractions: Upper and lower sparse abstractions ( $U\Sigma_D, L\Sigma_D$ ) are constructed directly from finite sampled data points. The transition relations are defined by bounding the successors of abstract states using the successors of data points that are greater (for upper) or smaller (for lower) in the partial order.
- Guarantees: The paper establishes that the data-driven upper abstraction is simulated by the model-based upper abstraction ( $U\Sigma_D \preceq U\Sigma$ ), and the model-based lower abstraction simulates the data-driven lower abstraction ( $L\Sigma \preceq L\Sigma_D$ ).
- Sampling Requirements: The authors provide both deterministic conditions (Assumption 6) and probabilistic bounds (Proposition 2) on the number of samples required to ensure the data-driven abstraction approximates the model-based abstraction within a specified precision with a given confidence level.

Key Contributions

New Behavioral Relation: Introduction of the $\varepsilon$ -ASUAS relation, which leverages the monotonicity of systems to provide stronger refinement guarantees than traditional relations without requiring incremental stability.
Complete Abstraction Pairs: For the first time, a complete abstraction pair (providing both soundness and completeness) is constructed for monotone systems. This resolves the undecidability issue inherent in one-sided sound abstractions.
Precision Control: A constructive method to bound the conservativeness gap between upper and lower abstractions via discretization parameters, applicable to both model-based and data-driven settings.
Data-Driven Synthesis: A rigorous framework for constructing complete abstraction pairs directly from finite data, providing deterministic and probabilistic guarantees on the quality of the abstraction relative to the underlying (unknown) system.

Results
The theoretical results are validated through numerical simulations involving a vehicle control problem (adaptive cruise control):

Model-Based Example: The authors demonstrate that the domain of the maximal safety controller for the upper-sparse abstraction is a subset of the original system's safe domain, which is itself a subset of the lower-sparse abstraction's domain. By refining the discretization (increasing from $20 \times 14$ to $280 \times 60$ states), the gap between the upper abstraction and the true system is shown to shrink, validating the precision control mechanism.
Data-Driven Example: Using a dataset of $10^4$ points, the authors synthesize controllers from data-driven abstractions. The results confirm the theoretical ordering: the safe set of the data-driven upper abstraction is contained within the model-based upper abstraction, and the safe set of the model-based lower abstraction is contained within the data-driven lower abstraction.
Sampling Validation: A Monte-Carlo experiment validates the probabilistic sample complexity bound, showing that the derived number of samples achieves the required coverage with the predicted confidence level.

Significance and Claims
The paper claims to advance the state of the art in symbolic control by overcoming two major limitations:

Completeness for Monotone Systems: It provides the first complete abstraction framework for monotone systems, a class of systems relevant in biology, traffic, and power grids, without requiring the restrictive incremental stability assumptions needed for general nonlinear systems.
Model-Free Synthesis: It successfully extends the concept of complete abstractions to data-driven settings, allowing for the synthesis of provably correct controllers without an explicit system model.

The authors position this work as a step toward more practical and less conservative symbolic control, noting that future work could extend these concepts to mixed-monotone systems and improve scalability through compositional techniques. The paper does not claim to solve the general case for all nonlinear systems but strictly targets the class of monotone systems.

The New "Safety Sandwich"

Tuning the Gap

Learning from Data, Not Just Math

The Car Test Drive

What This Means

More like this