Barrier certificate

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (September 2018) (Learn how and when to remove this message)

A barrier certificate or barrier function is used to prove that a given region is forward invariant for a given ordinary differential equation or hybrid dynamical system. That is, a barrier function can be used to show that if a solution starts in a given set, then it cannot leave that set.

Showing that a set is forward invariant is an aspect of safety, which is the property where a system is guaranteed to avoid obstacles specified as an unsafe set.

Barrier certificates map the system state (for example, its position) to a scalar value for which certain ranges must correspond to either the safe or unsafe set, the specifics of this vary by the type of barrier function used. Assuming a function ${\displaystyle h}$ of zeroing type, the question of safety becomes that of determining whether ${\displaystyle {\dot {h}}}$ is non-negative for any state where ${\displaystyle h=0}$. As the unsafe set corresponds to all negative values of ${\displaystyle h}$, its inability to reach a value below 0 implies the system is unable to cross the safe set boundary outwards.

Barrier certificates play the analogical role for safety to the role of Lyapunov functions for stability. For every ordinary differential equation that robustly fulfills a safety property of a certain type there is a corresponding barrier certificate.

History

The first result in the field of barrier certificates was the Nagumo theorem by Mitio Nagumo in 1942. The term "barrier certificate" was introduced later based on similar concept in convex optimization called barrier functions.

Barrier certificates were generalized to hybrid systems in 2004 by Stephen Prajna and Ali Jadbabaie.

Variants

There are several different types of barrier functions. One distinguishing factor is the behavior of the barrier function at the boundary of the forward invariant set ${\displaystyle S}$. A barrier function that goes to zero as the input approaches the boundary of ${\displaystyle S}$ is called a zeroing barrier function. A barrier function that goes to infinity as the input approaches the boundary is called a reciprocal barrier functions. Zeroing barrier functions may be preferred in embedded applications as they do not create unbounded values close to the set boundary. Here, "reciprocal" refers to the fact that a reciprocal barrier functions can be defined as the multiplicative inverse of a zeroing barrier function.

Control barrier functions

Barrier functions were extended to systems with control inputs as control barrier functions (CBFs), in a way analogous to how control-Lyapunov functions extend Lyapunov functions from stability analysis to the design of controllers. Whereas a barrier certificate verifies that a given system is safe, a control barrier function is used to choose control inputs that make the system safe.

For a system of the form ${\displaystyle {\dot {x}}=f(x)+g(x)u}$, where ${\displaystyle u}$ is the control input, a zeroing barrier function ${\displaystyle h}$ is a control barrier function if at every state there exists an input that keeps ${\displaystyle h}$ from decreasing too quickly near the boundary of the safe set, that is

${\displaystyle \sup _{u}\left[L_{f}h(x)+L_{g}h(x)\,u\right]\geq -\alpha (h(x))}$

for some extended class-K function ${\displaystyle \alpha }$, where ${\displaystyle L_{f}h}$ and ${\displaystyle L_{g}h}$ are Lie derivatives. Any locally Lipschitz controller satisfying this condition keeps the safe set forward invariant.

Since the condition is linear in the control input, it can be enforced in real time by solving a quadratic program that minimally modifies a desired control input to maintain safety. This approach, sometimes called a safety filter, can be combined with a control-Lyapunov function to pursue stabilization at the same time. It has been applied several field, such as adaptive cruise control, bipedal walking robots and collision avoidance in multi-robot systems.

References