Modern autonomous systems—from deep-sea exploration robots to medical devices—operate in a continuous physical world governed by differential equations. However, the software engines we use to verify safety and synthesize control strategies speak a completely different language: the discrete math of finite automata, state-transition graphs, and digital logic.
To bridge this gap, researchers use symbolic abstraction. The core intuition is to partition an infinite, continuous state space into a finite set of regions, treating each region as a single discrete "symbol." By translating continuous physics into a discrete map, we can use computer science algorithms to guarantee safety and performance before a system ever deploys.
The Intuition of State-Space Partitioning
Imagine trying to verify that a drone will never crash into a wall. In a continuous model, the drone has an infinite number of possible positions $(x, y, z)$ and velocities. Checking every single point is mathematically impossible.
Symbolic abstraction solves this by overlaying a grid across the environment. Every cell in this grid becomes an abstract state. As explained by Tak-John Koo et al. in Bisimulation Based Hierarchical System Architecture for Single-Agent Multi-modal Systems, this partitioning creates an equivalence relation where all continuous points within the same cell are treated as functionally identical. This allows researchers to derive a discrete quotient transition system from complex underlying dynamics.
To ensure this simplified grid faithfully represents the true physics, the abstraction must preserve the system's behavior. This is achieved through bisimulation. If a discrete model is bisimilar to a continuous system, any trajectory possible in the physical world has a perfect counterpart in the symbolic world. While exact bisimulation is difficult to achieve for complex systems, Giordano Pola et al. demonstrated in Approximately bisimilar symbolic models for nonlinear control systems that stable nonlinear control systems can be mapped to approximately bisimilar symbolic models. By quantizing time, state space, and input space into discrete intervals, we can achieve any user-defined level of precision.
From Differential Equations to Discrete Games
Once the continuous dynamics are converted into a finite state-transition graph, controller synthesis transforms into a game played on a graph. The controller chooses a discrete action (such as a steering command), and the environment responds by moving the system to an adjacent cell.
As Xiang Yin 0003 et al. note in Formal Synthesis of Controllers for Safety-Critical Autonomous Systems: Developments and Challenges, mapping continuous dynamics into discrete models like grids or graphs allows researchers to apply automata and game theory to solve complex reachability and safety problems.
For example, consider public health management during an epidemic. Instead of relying on purely reactive policies, Kazumune Hashimoto et al. show in Synthesis of Event-triggered Controllers for SIRS Epidemic Models how continuous differential equations governing disease spread can be abstracted into a finite-state symbolic transition system. This abstraction enables the automated synthesis of event-triggered controllers that mathematically guarantee infection levels will remain within hospital capacity while minimizing the frequency of disruptive policy changes.
Taming Randomness with Stochastic Abstractions
Real-world physical systems are rarely deterministic; they are subject to wind gusts, sensor noise, and unpredictable disturbances. Discretizing a continuous stochastic process requires mapping continuous probability distributions onto discrete transitions.
Toolboxes like FAUST$^2$, introduced by Sadegh Soudjani et al. in FAUST2: Formal Abstractions of Uncountable-STate STochastic processes, automate this by partitioning uncountable state spaces into non-overlapping bins and selecting representative points. This process transforms complex stochastic processes into finite-state Markov chains or Markov Decision Processes (MDPs) suitable for standard model-checking tools.
However, when the underlying noise is highly uncertain or non-Gaussian, a single transition probability between cells cannot be known for certain. To handle this, the authors of Formal Controller Synthesis for Markov Jump Linear Systems with Uncertain Dynamics (Luke Rickard et al.) and Robust Control for Dynamical Systems with Non-Gaussian Noise via Formal Abstractions (Thom Badings et al.) abstract continuous dynamics into Interval Markov Decision Processes (iMDPs). Instead of exact probabilities, transitions are assigned intervals of possible probabilities. This abstraction allows for the synthesis of robust controllers that provide Probably Approximately Correct (PAC) safety guarantees without needing an explicit mathematical model of the noise.
Overcoming the Curse of Dimensionality
The primary challenge of symbolic abstraction is computational complexity. If you divide each dimension of a 6-dimensional state space into 100 intervals, the resulting grid contains $100^6 = 10^{12}$ states—far too large for standard verification algorithms. Researchers employ several key strategies to mitigate this state-space explosion:
- Coordinate Transformations: Complex, skewed physical dynamics often require highly dense grids to capture transitions accurately. Asger Horn Brorholt demonstrates in Efficient Shield Synthesis via State-Space Transformation that transforming the system's coordinates to align its dynamics with simple rectangular grids can reduce the state-space complexity by up to three orders of magnitude while maintaining formal safety guarantees.
- Abstraction Refinement (CEGAR): Rather than building a uniformly fine grid from the start, researchers begin with a very coarse abstraction. If the model checker finds a safety violation, a Counterexample-Guided Abstraction Refinement loop analyzes whether the violation is physically real or merely an artifact of the coarse grid. If it is an artifact, the grid is selectively refined only where needed. Krishnendu Chatterjee et al. leverage this approach in CEGAR for Qualitative Analysis of Probabilistic Systems to scale up the verification of complex probabilistic systems.
- Safety Shielding: When full system verification remains computationally out of reach, symbolic abstractions can be used to construct a "shield." Asger Horn Brorholt et al. show in Shielded Reinforcement Learning for Hybrid Systems how discretizing continuous state spaces into a finite grid allows for the efficient synthesis of a safety barrier. This shield monitors unverified controllers (like deep neural networks) and overrides their actions only when the system risks entering an unsafe abstract state.
Key Foundational Work
Qualitative Kinematics in Mechanisms (1987) — contributed 1 concept elements to this direction.
Synchronization and Grammatical Inference in an Oscillating Elman Net (1992) — contributed 1 concept elements to this direction.
Consistency-Based Diagnosis in Physiological Domains (1992) — contributed 1 concept elements to this direction.