Modern engineering increasingly relies on cyber-physical systems, where discrete digital software controls continuous physical processes. This creates a fundamental theoretical mismatch. Software operates on discrete logic, state machines, and temporal formulas (such as "never enter an unsafe state" or "eventually reach the target"). Physics, on the other hand, operates on continuous state spaces governed by differential equations.
To verify or synthesize software controllers for these systems, we need a way to translate infinite, continuous dynamics into finite, discrete models without losing formal guarantees. The mathematical framework that makes this possible is symbolic abstraction via approximate bisimulation.
The Rigidity of Exact Equivalence
In computer science, two transition systems are considered behaviorally equivalent if they are bisimilar. An exact bisimulation relation requires that if the original system can make a move to a new state, the abstract model must be able to make a matching move to an equivalent state, and vice versa.
Early frameworks attempted to use exact bisimulation to bridge the continuous-discrete divide. For instance, Tak-John Koo et al. established exact bisimulation relations to preserve reachability properties across hierarchical abstraction levels in multi-modal systems (Bisimulation Based Hierarchical System Architecture for Single-Agent Multi-modal Systems). Similarly, Paulo Tabuada et al. demonstrated that continuous dynamics could be converted into exact discrete bisimilar models to automate the synthesis of hybrid controllers (From discrete specifications to hybrid control).
However, exact bisimulation is exceptionally fragile when applied to continuous physics. In a continuous state space, a microscopic perturbation—such as a tiny amount of measurement noise or a slight discretization error in time—means that two trajectories will no longer be perfectly identical. Under the strict rules of exact bisimulation, any mismatch, no matter how small, breaks the relation entirely. As noted by Ebru Aydin Gol et al., simple or naive approximations often fail to preserve critical dynamical properties, yet demanding strict exactness makes the abstraction of general nonlinear systems computationally impossible (Finite bisimulations for switched linear systems).
Relaxing the Metric: Approximate Bisimulation
To solve this problem, researchers shifted from a purely qualitative view of equivalence to a quantitative, metric-based view. Instead of requiring the outputs of the continuous system and the discrete model to be identical, we allow them to deviate, provided they stay within a strictly bounded spatial error, denoted by $\epsilon$.
This relationship is known as an approximate bisimulation. In this paradigm, every trajectory in the continuous physical system is guaranteed to have a corresponding trajectory in the discrete symbolic model that tracks it within an $\epsilon$ error bound, and vice versa.
Giordano Pola et al. formalized this breakthrough for nonlinear control systems, proving that continuous physical systems could be mapped to discrete transition systems with a user-defined level of precision (Approximately bisimilar symbolic models for nonlinear control systems). This two-way mapping ensures that if a controller is synthesized and verified on the discrete model, it is mathematically guaranteed to work on the real physical system within a predictable margin of error.
The Engine of Discretization: Incremental Stability
How is it possible to safely group an infinite number of continuous states into a finite number of discrete symbolic states? The mechanism relies entirely on the system's underlying physics—specifically, its stability properties.
The primary mathematical tool used to construct these abstractions is incremental input-to-state stability ($\delta$-ISS).
Standard System: State x_1 ───(Input u)───> State x_2 (Diverges if unstable)
Incremental (δ-ISS): State x_1 ┐
├─(Same Input u)─> Trajectories contract/stay close
State y_1 ┘
In a standard stable system, trajectories converge toward an equilibrium point. In an incrementally stable system, trajectories converge toward each other if they are driven by the same control inputs. If you start the system from two slightly different initial states and apply the same sequence of inputs, the distance between the resulting trajectories will remain bounded or contract over time.
This contraction property is what makes discretization work:
- State Space Gridding: Because nearby trajectories naturally stay close to each other, we can partition the continuous state space into a finite grid of size $\tau$.
- Representative Symbols: We can choose a single point at the center of each grid cell to act as a "symbolic state."
- Bounded Error: The $\delta$-ISS property guarantees that any actual continuous state inside that grid cell will not drift arbitrarily far from its symbolic representative.
By leveraging $\delta$-ISS, Giordano Pola et al. proved that the error between the continuous system and its finite-state abstraction can be made arbitrarily small by choosing a sufficiently fine grid (Approximately bisimilar symbolic models for nonlinear control systems).
Taming Delays, Randomness, and Networks
The power of the approximate bisimulation framework is its adaptability to increasingly complex and non-ideal physical realities.
Time Delays
In many real-world systems, the future state depends not just on the current state, but on past states due to transmission or processing delays. Giordano Pola et al. extended the $\delta$-ISS mechanism to nonlinear time-delay systems, showing that finite symbolic models could still be constructed despite the infinite-dimensional nature of delay history (Symbolic models for nonlinear time-delay systems using approximate bisimulations). This theoretical foundation allows formal process calculi, such as Delay Hybrid CSP, to be systematically discretized into executable code while maintaining bounded behavioral differences (Synthesizing SystemC Code from Delay Hybrid CSP).
Stochastic Uncertainty
When systems are influenced by random noise, we can no longer guarantee that trajectories stay within a strict geometric tube. Instead, we must bound the probability of deviation. Majid Zamani et al. introduced a stochastic stability condition ($\delta$-ISS-$M_q$) to construct finite abstractions for continuous-time stochastic systems (Symbolic control of stochastic systems via approximately bisimilar finite abstractions).
For general Markov Decision Processes (gMDPs) with continuous state spaces, Sofie Haesaert et al. formulated $(\epsilon, \delta)$-approximate probabilistic relations. These relations relax exact matching by simultaneously bounding spatial output errors ($\epsilon$) and transition probability deviations ($\delta$), providing a rigorous way to verify complex stochastic systems via simpler models (Verification of General Markov Decision Processes by Approximate Similarity Relations and Policy Refinement).
Network Non-Idealities
When controllers communicate with physical hardware over digital networks, they must contend with packet drops and variable communication intervals. To model this adversarial environment, Majid Zamani et al. utilized alternating approximate bisimulations (Symbolic Abstractions of Networked Control Systems). This framework treats the interaction between the controller and the network as a two-player game, ensuring that the discrete abstraction accounts for the worst-case moves of the network environment while maintaining a guaranteed error bound.
Correct-by-Construction Controller Refinement
The ultimate goal of creating an approximately bisimilar abstraction is to solve the control problem in the discrete world and seamlessly transfer the solution back to the physical world. This process is called policy refinement.
1. Specify Goal ───> 2. Synthesize Discrete Controller ───> 3. Refine via Interface
(e.g., LTL) (Automata / Game Theory) (Apply to Physical System)
│ │
▼ ▼
Discrete Model ◀──[Approx. Bisimulation]──▶ Continuous Physics
The workflow operates in three distinct phases:
- Abstraction: A continuous system is discretized into a finite symbolic model using an approximate relation.
- Discrete Synthesis: Because the symbolic model is finite, computer science algorithms (such as reactive synthesis or model checking) can automatically compute a discrete controller that satisfies a high-level specification, such as Linear Temporal Logic (LTL).
- Refinement via an Interface: The discrete controller is coupled with a mathematical "interface." When the discrete controller chooses a symbolic action, the interface translates it into a continuous control input.
Because the approximate bisimulation relation guarantees a bidirectional error bound, any safety or performance property verified on the discrete abstraction is mathematically guaranteed to hold true for the physical system, modulo the known tracking error $\epsilon$. This paradigm, leveraged across multi-affine and stochastic systems alike (An input-output simulation approach to controlling multi-affine systems for linear temporal logic specifications; Temporal logic control of general Markov decision processes by approximate policy refinement), provides a robust, correct-by-construction pipeline for engineering complex cyber-physical systems.
Key Foundational Work
From discrete specifications to hybrid control (2003) — contributed 3 concept elements to this direction.
Bisimulation Based Hierarchical System Architecture for Single-Agent Multi-modal Systems (2002) — contributed 1 concept elements to this direction.