⚡ electrical engineering

Verification of High-Order Control Barrier Functions by Computing Class K Functions

This paper proposes a verification method for High-Order Control Barrier Functions (HOCBFs) using a sequence of Sum-of-Squares (SOS) programs to compute associated class K functions, thereby guaranteeing system safety when solutions exist.

Original authors: Ellie Pond, Matthew Hale

Published 2026-08-03

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Ellie Pond, Matthew Hale

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are programming a fleet of delivery drones to zip through a bustling city. You want them to be fast and efficient, but more importantly, you need them to never crash into buildings, other drones, or people. In the world of robotics and engineering, this is the holy grail of "safety." Scientists use mathematical tools called Control Barrier Functions (CBFs) to act like invisible force fields around these robots. These force fields tell the robot's computer, "If you go this way, you're safe; if you go that way, you're in trouble."

However, there's a tricky catch. Sometimes, the robot's physics are complex. It might take a few seconds for the robot to stop even after it hits the brakes, or it might need to turn before it can stop. This is where "High-Order" CBFs come in. They are like a more sophisticated version of the force field that accounts for these delays and complex movements. But here's the problem: to make these force fields work, engineers have to pick specific mathematical curves, called "class K functions," to define how strict the safety rules are. Picking the wrong curve is like setting a speed limit that is either too high (and you crash) or too low (and the robot gets stuck). For a long time, engineers had to guess these numbers, hoping they would work, which is a risky game when lives or expensive equipment are on the line.

This paper, titled "Verification of High-Order Control Barrier Functions by Computing Class K Functions," tackles that guessing game head-on. The authors, Ellie Pond and Matthew T. Hale, propose a new way to mathematically prove that a robot's safety rules will actually work before the robot ever leaves the garage. Instead of guessing the right curves, they use a powerful type of math called "Sum-of-Squares" programming to automatically calculate the perfect safety curves. Think of it as a master architect who doesn't just draw the blueprints but runs a thousand computer simulations to prove the building won't collapse before a single brick is laid.

The paper shows that if their mathematical recipe finds a solution, the robot is guaranteed to stay safe forever, no matter how it moves or what obstacles it faces. They tested this idea with a simulation of a unicycle-like robot navigating a space with seven different safety zones (like avoiding seven different circles and staying within a box). The computer successfully generated the necessary safety curves for all seven zones at once, and the robot zipped through the simulation without ever breaking a safety rule. While this was a computer simulation and not a physical robot on a real street, the math behind it is solid, offering a reliable way to verify safety for complex systems that have multiple rules to follow simultaneously.

The Invisible Force Fields

To understand why this is such a big deal, let's look at the tools the paper uses. Imagine a robot is a car driving on a highway. A standard safety rule might be: "Stay in your lane." In math, this is a simple line. But what if the car is heavy and takes a long time to stop? A simple line isn't enough; you need a rule that says, "If you are close to the edge, you must slow down now so you don't slide off later." This is what a High-Order Control Barrier Function (HOCBF) does. It's a safety rule that looks ahead, accounting for the robot's momentum and how long it takes to react.

But to make this "look-ahead" rule work, the engineer has to choose a specific shape for the rule, known as a class K function. Imagine you are setting the sensitivity of a smoke alarm. If you set it too sensitive, it goes off when you toast bread (the robot stops unnecessarily). If you set it too loose, it doesn't go off until the house is burning (the robot crashes). For a long time, engineers had to pick these "sensitivity knobs" by hand, often guessing and checking. If they guessed wrong, the robot might get stuck, or worse, the computer might crash because it couldn't find a safe path.

The "Magic Calculator" for Safety

The authors of this paper realized that instead of guessing, they could use a mathematical trick to compute the perfect knobs. They used a method called Sum-of-Squares (SOS) programming. You can think of SOS programming as a super-smart calculator that checks if a shape is always "positive" (safe) or "negative" (unsafe).

The paper's main discovery is a step-by-step recipe (an algorithm) that uses this calculator to find the right class K functions for a robot with multiple safety rules. Here is how it works in their story:

The Problem: They had a robot with seven different safety rules (HOCBFs) to follow at the same time. Each rule had its own unknown "sensitivity knob" (class K function) to figure out. That's 14 unknown functions in total (two for each of the seven rules).
The Solution: They built a sequence of math problems. First, they solved for the first layer of safety, then used that result to solve for the next layer, and so on. It's like building a tower of blocks where you can't place the second block until you've proven the first one is stable.
The Result: The computer successfully found the values for all 14 unknown functions.

The Simulation Test

To see if their magic recipe actually worked, they ran a simulation. They created a virtual robot that looked like a unicycle (it has a position, a speed, and an angle). They set up a playground with seven different safety zones:

Three zones were like invisible circles the robot had to avoid.
Four zones were the walls of the room the robot had to stay inside.

They also added a goal: the robot needed to drive to a specific spot and stop there (this is called a "Control Lyapunov Function," or CLF, which is like a magnet pulling the robot to its destination).

The computer ran the math recipe and generated the safety curves. Then, they let the robot drive. The results, shown in the paper's figures, were successful. The robot started from various places and drove around, and every single time, it stayed inside the safe zone (the area where all seven rules overlapped). The red dashed lines in their diagrams showed the boundaries, and the robot's path never crossed them.

What This Means (and What It Doesn't)

The paper proves that if their math problems have a solution, the robot is guaranteed to be safe. It's a "certificate of safety." If the computer says "Yes, I found the curves," then you know the robot won't crash due to a bad safety setting.

However, there are a few important limits to keep in mind. The paper explicitly states that this method works for systems where the math can be written as polynomials (a specific type of smooth curve). While most real-world systems can be approximated this way, it's a mathematical requirement. Also, the results presented here are simulations. The robot existed only on a computer screen. The authors did not test this on a physical robot in a real lab or on the street.

Furthermore, the paper notes that sometimes the math might get too complicated to solve. If the computer can't find a solution, it doesn't necessarily mean the robot can't be safe; it might just mean the specific math tools they used weren't strong enough for that particular problem. In those cases, they suggest tweaking the math (like making the curves simpler) and trying again.

In the simulation, the computer took about 1,053 seconds (roughly 17 minutes) to verify the safety for all seven rules combined. This shows that while the math is heavy, it is doable. The authors found that as they added more safety rules, the time it took to solve the problem grew in a straight line, which is a good sign for future, more complex robots.

The Bottom Line

This paper doesn't invent a new robot or a new way to drive. Instead, it invents a new way to check the math that keeps robots safe. Before, engineers had to hope their safety settings were right. Now, they have a tool that can mathematically prove, "Yes, these settings will keep the robot safe," even when the robot has to juggle seven different safety rules at once. It turns a game of guess-and-check into a game of proof and certainty, paving the way for safer, more reliable autonomous machines in the future.

Technical Summary: Verification of High-Order Control Barrier Functions by Computing Class K Functions

Problem Statement
High-order control barrier functions (HOCBFs) are utilized to enforce safety in control-affine systems by ensuring that a set of safe states remains forward-invariant under system dynamics. However, the practical implementation of HOCBFs faces a critical verification challenge. At runtime, HOCBFs are typically enforced by solving a sequence of optimization problems (specifically Sequential Quadratic Programs, or SQPs) that incorporate safety constraints. These constraints rely on user-determined "class K functions" ( $\alpha_i$ ). Currently, there are no established rules for selecting these functions to guarantee forward invariance, and it is often unclear whether the resulting optimization problems remain feasible when multiple safety constraints, control Lyapunov functions (CLFs) for stability, and input constraints must be satisfied simultaneously. If the SQP becomes infeasible, the system cannot generate a safe control input, potentially leading to safety violations. This paper addresses the need for an a priori verification method to ensure that a system can continuously generate safe inputs online.

Methodology
The authors propose a framework to verify HOCBFs by automatically constructing the necessary class K functions using Sum-of-Squares (SOS) programming. The methodology proceeds as follows:

Theoretical Bounds: The paper first establishes a theoretical upper bound for class K functions (Theorem 3.1). It demonstrates that if specific polynomial functions $\beta_i$ satisfy certain differential inequalities, then valid class K functions exist that render the safe set forward-invariant. This transforms the problem of finding unknown class K functions into a problem of finding polynomial coefficients that satisfy non-negativity conditions.
SOS Formulation: Leveraging the connection between inequality constraints and non-negativity certificates from real algebraic geometry, the authors formulate a sequence of SOS programs (SOSPs). These programs search for polynomial solutions for the class K functions and the control input.
- Single HOCBF Case: For a system with a single HOCBF of relative degree $r$ , the authors develop a "bottom-up" sequence of SOSPs. The process begins by solving for $\beta_1$ (related to $\alpha_1$ ), then uses that result to solve for subsequent $\beta_i$ and finally $\alpha_r$ , ensuring the constraints are met sequentially.
- Multiple HOCBFs Case: For systems with $J$ safety constraints, the authors propose an iterative algorithm (Algorithm 1). The algorithm verifies HOCBFs one by one. Crucially, when verifying the $(j+1)$ -th HOCBF, the previously verified $j$ -th HOCBF is incorporated into the quadratic module of the SOS program. This ensures that the new class K functions do not invalidate the safety guarantees of the previously verified constraints.
Feasibility Guarantee: The sequence of SOSPs is solved prior to runtime. If solutions exist, the paper guarantees that the online SQP used for real-time control will remain feasible for all time steps, provided the sampling interval is sufficiently small.

Key Contributions
The paper makes three primary contributions:

Theoretical Upper Bound: It provides a theoretical upper bound for class K functions in an HOCBF (Theorem 3.1). Any class K function satisfying this bound validates that the HOCBF meets its definition, decoupling the recursive dependency of class K functions found in standard definitions.
Verification Sequence: It develops a sequence of SOSPs (Theorem 4.1 and Algorithm 1) that (i) generates the class K functions for a finite number of HOCBFs and (ii) guarantees the continued feasibility of the online optimization problems for systems subject to CLFs and input constraints.
Numerical Validation: It presents numerical simulations demonstrating the framework on a unicycle system with seven HOCBFs of relative degree two, involving a total of 14 unknown class K functions.

Results
The proposed framework was tested on a unicycle system with:

Safety Constraints: Seven HOCBFs ( $J=7$ ) encoding safe regions (avoiding three circular obstacles and staying within a rectangular workspace).
Stability Goals: Three Control Lyapunov-like functions (CLlFs) guiding the system to a target position and velocity.
Implementation: The SOSPs were solved using MATLAB and the SOSTOOLS toolbox.
Outcome: The algorithm successfully generated the required class K functions. Simulations showed that trajectories starting from various initial conditions remained within the intersection of all safe sets ( $C_{sys}$ ). The resulting SQP implementation produced continuous inputs that satisfied all safety and stability constraints.
Computation: The computation time for the verification process scaled roughly linearly with the number of HOCBFs, increasing from 127 seconds for 1 HOCBF to 1053 seconds for 7 HOCBFs.

Significance and Claims
The authors claim that this work provides a rigorous, a priori certificate for the continued feasibility of safe stabilization in systems with multiple HOCBFs. Unlike previous methods that may assume feasibility or focus on single HOCBFs without input constraints, this approach systematically handles the interaction between multiple safety constraints, stability requirements (CLFs), and actuation limits.

The paper modestly notes that while SOS programming is limited to polynomial systems (or polynomial approximations), any continuous function can be uniformly approximated by polynomials, making the approach broadly applicable. The authors emphasize that their method does not guarantee safe stabilization (where the stability slack variable $\rho = 0$ ) in all cases; in the simulation, non-zero $\rho$ values indicated that while safety was guaranteed, strict stabilization required the use of slack variables. The primary contribution is the assurance that safe inputs can always be generated, preventing the optimization problem from becoming infeasible. Future work is noted to extend these methods to distributed safe system verification.

The Invisible Force Fields

The "Magic Calculator" for Safety

The Simulation Test

What This Means (and What It Doesn't)

The Bottom Line

More like this