In the design of autonomous systems—from UAVs to power converters—the most critical question is: "Can we guarantee this system will never enter an unsafe state?" Traditionally, answering this required either exhaustive simulation (which can never prove safety) or state-space discretization (which suffers from the "curse of dimensionality").
A powerful alternative has emerged that treats safety verification not as a search through trajectories, but as a convex optimization problem. By using Sum-of-Squares (SOS) programming, researchers can automatically synthesize mathematical "certificates" that prove a system is safe without ever needing to solve its underlying differential equations.
The Intuition: Safety as a Landscape
Imagine a robot moving through a state space. Some regions are "safe" (the road) and others are "unsafe" (a ditch). To prove the robot is safe, we don't need to track every possible path it might take. Instead, we can look for a Barrier Certificate.
A Barrier Certificate is a scalar function $B(x)$ that acts like a topographical map. We want to find a function where:
- $B(x) \leq 0$ for all initial starting positions.
- $B(x) > 0$ for all unsafe regions.
- The value of $B(x)$ never increases along the system's trajectories.
If such a function exists, it acts as an impenetrable fence. Since the robot starts in a region where $B \leq 0$ and the value of $B$ can only go down or stay the same, it can never reach the unsafe region where $B > 0$. Han Wang and Antonis Papachristodoulou demonstrate in Safety Verification and Controller Synthesis for Systems with Input Constraints that these certificates can be significantly less conservative than traditional methods, allowing for larger safe operating regions.
The Mechanism: Sum-of-Squares Programming
The challenge is finding this function $B(x)$. For a general nonlinear system, checking if a function is globally non-negative is an NP-hard problem. This is where Sum-of-Squares (SOS) optimization provides a breakthrough.
If a polynomial can be written as a sum of squared polynomials (e.g., $p(x) = f_1(x)^2 + f_2(x)^2$), it is obviously non-negative. While not every non-negative polynomial is a sum of squares, the set of SOS polynomials is much easier to work with. Crucially, checking if a polynomial is SOS can be cast as a Semidefinite Program (SDP), a type of convex optimization that can be solved efficiently.
Amir Ali Ahmadi and Anirudha Majumdar in Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making show that by relaxing complex polynomial constraints into SOS or even simpler SDSOS (Scaled Diagonally Dominant Sum of Squares) forms, we can generate safety certificates for UAVs in real-time.
Scaling to Complex Systems
This framework is remarkably flexible, extending far beyond simple robot motion:
- Stochastic Systems: When systems face random noise, we look for "Martingale" properties. Xiang Yin and Shaoyuan Li show in On the Construction of Barrier Certificate: A Dynamic Programming Perspective how to map these stochastic conditions to SOS problems to provide probabilistic safety bounds.
- Infinite-Dimensional Systems: For systems governed by Partial Differential Equations (PDEs), such as fluid flows, Mohamadreza Ahmadi and colleagues introduced Barrier Functionals. In Safety verification for distributed parameter systems using barrier functionals, they demonstrate that SOS programming can find these functionals to prove safety for systems with infinite states.
- Hybrid Systems: Systems that jump between different modes (like a walking robot) can be verified by finding "Invariant Clusters." Hui Kong and Christian Schilling combine SOS with algebraic geometry (Gröbner bases) in Invariant Clusters for Hybrid Systems to handle these discrete-continuous interactions.
From Verification to Synthesis
The ultimate goal is not just to verify safety, but to design controllers that ensure it. By treating the controller coefficients as variables in the SOS program, we can jointly search for a control law and its safety proof.
Milan Korda and Didier Henrion pioneered a "primal-dual" approach in Convex Computation of the Maximum Controlled Invariant Set For Polynomial Control Systems. Instead of guessing a Lyapunov function, they use "occupation measures" to characterize the largest possible safe set, transforming the search for a controller into a linear program over measures, which is then solved via the SOS hierarchy.
This shift—from manual "guess-and-check" of safety functions to automated synthesis via convex optimization—represents a fundamental change in how we build reliable autonomous systems. As Jared Miller and Mario Sznaier suggest in Quantifying the Safety of Trajectories using Peak-Minimizing Control, this hierarchy allows us to calculate increasingly tight bounds on safety, providing a rigorous numerical path toward absolute certainty in machine behavior.