Formal Synthesis for Stochastic Systems via Symbolic Abstractions

This direction is split into other directions: stochastic simulation functions. Its last version stays readable and citable here.

Version 1 of 126 papers31 conceptsfrozen 2026-10-04

Engineers designing controllers for complex systems—like power grids, autonomous robots, or chemical plants—face a fundamental tension. On one hand, the real world is continuous, noisy, and high-dimensional. On the other hand, the requirements we want these systems to meet are often discrete and logical, such as "reach the target within ten seconds without ever entering the danger zone."

Bridging this gap requires a "correct-by-design" approach. Instead of designing a controller and then testing it to see if it fails, researchers like Majid Zamani and Sofie Haesaert have developed frameworks that mathematically guarantee a system will satisfy complex specifications. The core of this research direction is the use of symbolic abstractions to turn intractable continuous problems into solvable discrete ones.

The Map is Not the Territory

The central challenge in formal synthesis is the "curse of dimensionality." A continuous system has an infinite number of possible states. To make this manageable, we create an abstraction: a simplified model (often a finite Markov Decision Process or a symbolic automaton) that acts as a "map" of the original "territory."

In Automata-based Controller Synthesis for Stochastic Systems, Bingzhuo Zhong and Majid Zamani demonstrate how to synthesize controllers on these simplified models. If the abstraction says a certain move is safe, we want to be sure that the real-world system—despite its noise and complexity—will also be safe.

Simulation Functions: The Mathematical Bridge

How do we know our "map" is accurate enough to trust? This research direction relies on a mechanism called a stochastic simulation function.

Think of a simulation function as a measure of the "probabilistic distance" between the real system and its abstraction. As shown in Approximations of Stochastic Hybrid Systems by Majid Zamani and Peyman Mohajerin Esfahani, these functions provide a rigorous upper bound on the expected error.

If we can find a simulation function, we can quantify exactly how much the real system might deviate from the model. As Zhe Xu and Ufuk Topcu explain in their work on wind turbine generators, this allows us to design a controller for the simple model with a "robustness margin." If the model stays away from the edge of a cliff by at least the margin of error, the real system is guaranteed to stay safe with a calculable probability.

Scaling via Compositionality

The biggest hurdle for these methods is scale. Modeling a 1000-room building or a massive power grid as a single abstraction would require more memory than any computer possesses.

To solve this, Abolfazl Lavaei and Sadegh Soudjani propose a compositional approach. In Compositional (In)Finite Abstractions for Large-Scale Interconnected Stochastic Systems, they use "small-gain" theorems to prove that if we can bound the error for each individual subsystem (like a single room's heater), we can bound the error for the entire interconnected network.

This "divide-and-conquer" strategy allows for the formal synthesis of controllers for systems that were previously considered too large for formal methods. For instance, Lavaei and colleagues utilized dissipativity theory to construct abstractions for networks of hundreds of interconnected components while maintaining rigorous performance guarantees.

Handling Uncertainty and Privacy

The framework is flexible enough to handle more than just physical noise. In Differentially Private Controller Synthesis, Matthew T. Hale and Zhe Xu show that the noise added to protect agent privacy can be treated as just another stochastic perturbation. By accounting for this "privacy noise" in the simulation function, they can guarantee that a multi-agent system completes its mission without revealing sensitive trajectory data.

Furthermore, when the system parameters themselves are unknown, Oliver Schön and Sofie Haesaert have introduced Bayesian formal synthesis. This approach uses Bayesian regression to bound parameter uncertainty, creating a "sub-simulation relation" that ensures the controller is robust even when the underlying model is partially unknown.

By treating approximation error, physical noise, and even privacy-preserving randomness as quantifiable distances between a model and reality, this research direction provides a path toward truly reliable, autonomous infrastructure.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_formal_synthesis_for_stochastic_systems__14efe75b,
  title = {Formal Synthesis for Stochastic Systems via Symbolic Abstractions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-synthesis-for-stochastic-systems-via-symbolic-abstractions/rdr_14efe75be2c74eedb9c5be4306738e34},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_formal_synthesis_for_stochastic_systems__14efe75b_v1,
  title = {Formal Synthesis for Stochastic Systems via Symbolic Abstractions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-synthesis-for-stochastic-systems-via-symbolic-abstractions/rdr_14efe75be2c74eedb9c5be4306738e34/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}