Successive barriers
Stacking barrier certificates, level by level, to certify far more of the state space.
A single barrier certificate found by SOS programming is usually far too conservative. Successive barriers keep adding certificates, each of which only has to hold outside the region already certified, so the certified safe set grows level by level.
A car with constant speed and three turn rates (left, straight, right) must stay inside the fence and out of the red disc. The map is a slice of its three-dimensional state space at the heading shown in the top-left badge. Click anywhere to drop a car: it holds its level's turn rate until it enters an earlier level, hands over, and finally settles on a turning circle that is safe forever. The regions are computed in your browser on a grid of positions and headings; in the paper, each level is a polynomial certificate found by SOS programming.
The idea
Take a system \(\dot x = f(x, u)\) with an unsafe set \(X_u\). Fix one input \(u_j\) from a finite set and look for a polynomial \(B_j\) that is positive on \(X_u\) and satisfies
\[\nabla B_j(x) \cdot f(x, u_j) \;\le\; -\lambda\, B_j(x).\]Holding \(u_j\) then keeps the state inside \(\{B_j \le 0\}\). Fixing the input keeps the search a tractable SOS program, but the certified region is small. Taking the minimum over several such barriers, \(B^{(0)} = \min_j B_j\), already certifies more.
A successive barrier relaxes the decrease condition: it only has to hold where the previous level does not certify the state,
\[B^{(k-1)}(x) \ge 0 \;\Longrightarrow\; \nabla B^{(k)}_j(x) \cdot f(x, u_j) \;\le\; -\lambda\, B^{(k)}_j(x).\]Inside the earlier region, the earlier level takes over. Each new level is again an SOS program, and the union of all levels is a controlled invariant set that can be far larger than any single certificate.
At run time, a monitor passes the nominal controller while the active certificate is comfortably negative and overrides it with that certificate’s input when the state approaches the boundary. A bound on how fast the certificate can rise gives a minimum dwell time, so the monitor can run at a fixed sampling rate (Wajid & Sankaranarayanan, 2025).
In the paper
The running example is a three-dimensional car model near an obstacle. Each image is a slice of the certified region at one heading; drag the slider to turn the car.
The benchmarks go up to six states. On the 4-D polynomial system, the 5-D coordinated-turn model and the 6-D planar multirotor, the neural-certificate tool FOSSIL did not find a certificate, while successive barriers did.
