Notes · Safety as set invariance

Safety as set invariance

What it means for a system to be safe, why that question turns into a question about sets, and how Nagumo's theorem for an uncontrolled system becomes the control barrier function quadratic program.

Definition

The standard way to write that down is with a scalar constraint function \(h : \mathbb{R}^n \to \mathbb{R}\), continuously differentiable, chosen so that \(h\\geq 0) means the state is safe. For example:

  • Circular obstacle avoidance: \(h(x) = \|p - p_{\mathrm{obs}}\|^2 - r^2\), positive when the robot is farther than \(r\) from the obstacle centre.
  • Speed limit: \(h(x) = v_{\max}^2 - v^2\).

Usually, non-negative means safe.

Superlevel, sublevel, and level sets

Given \(h\), three sets matter:

$$\underbrace{\mathcal{C} = \{x : h(x) \ge 0\}}_{\text{0-superlevel set}}, \qquad \underbrace{\partial\mathcal{C} = \{x : h(x) = 0\}}_{\text{0-level set}}, \qquad \underbrace{\{x : h(x) \le 0\}}_{\text{0-sublevel set}}.$$

\(\mathcal{C}\) is the safe set. Its interior \(\mathrm{Int}(\mathcal{C}) = \{h \ge 0\}\) is where you are safe, and outside of the superlevel set, you are unsafe.

C = {x : h(x) ≥ 0} h > 0, interior, with margin h = 0, the boundary h < 0, unsafe the thin curves are level sets of h at positive values
Safety has been converted from a property of trajectories into a property of a set. Everything after this is about keeping the state inside it.

One technical condition recurs throughout: \(0\) should be a regular value of \(h\). That means \(\nabla h(x) \neq 0\) for every \(x \in \partial\mathcal{C}\). Geometrically, the boundary is then a genuine surface with a well-defined normal rather than a point where \(h\) touches zero tangentially.

Forward invariance and Nagumo's theorem

For an autonomous system \(\dot x = f(x)\) with \(f\) locally Lipschitz, the set \(\mathcal{C}\) is forward invariant if every trajectory starting inside stays inside:

$$x(0) \in \mathcal{C} \quad \Longrightarrow \quad x(t) \in \mathcal{C} \ \text{ for all } t \ge 0.$$

That quantifies over every trajectory and all time. Nagumo's theorem converts it into a pointwise condition.

We define thetangent cone, the set of directions pointing into \(\mathcal{C}\) or along its boundary \(\partial\mathcal{C}\):

$$T_{\mathcal{C}}(x) = \left\{ v \in \mathbb{R}^n \ :\ \liminf_{\tau \to 0^+} \frac{\mathrm{dist}(x + \tau v,\ \mathcal{C})}{\tau} = 0 \right\}.$$

Nagumo's theorem. For \(\dot x = f(x)\) with \(f\) locally Lipschitz and \(\mathcal{C}\) closed, \(\mathcal{C}\) is forward invariant if and only if

$$f(x) \in T_{\mathcal{C}}(x) \qquad \text{for all } x \in \mathcal{C}.$$

At an interior point, the tangent cone is all of \(\mathbb{R}^n\). What that means is that from strictly inside, every direction keeps you inside for at least a short time, which is trivial. What really matters is at the boundary \(\partial\mathcal{C}\).

And at the boundary, when \(0\) is a regular value of \(h\), the tangent cone is a half-space determined by the gradient,

$$T_{\mathcal{C}}(x) = \big\{ v : \nabla h(x)^\top v \ge 0 \big\}, \qquad x \in \partial\mathcal{C},$$

so the theorem collapses to one scalar inequality:

$$\dot{h}(x) = \nabla h(x)^\top f(x) \ \ge\ 0 \qquad \text{for all } x \in \partial\mathcal{C}.$$

In words: on the boundary the vector field must not point outward. It may point inward, or run exactly along the boundary.

∇h allowed leaves C h < 0 the shaded wedge is the tangent cone, the half space ∇h · v ≥ 0
Nagumo's condition at a boundary point. Interior points impose nothing, because there the cone is the whole space.

From invariance to controlled invariance

For a control-affine system

$$\dot x = f(x) + g(x)\,u, \qquad u \in U \subset \mathbb{R}^m,$$

Controlled invariance is a property of the set. For every \(x \in \mathcal{C}\) there exists some \(u \in U\) with \(f(x) + g(x)u \in T_{\mathcal{C}}(x)\). Note it only says that a safe control input always exists for the set.

Forward invariance is a property of the closed loop. Given a specific policy \(u = \pi(x)\), every trajectory of \(\dot x = f(x) + g(x)\pi(x)\) starting in \(\mathcal{C}\) stays in \(\mathcal{C}\).

Controlled invariance is necessary for safety. If some state in \(\mathcal{C}\) admits no safe input at all, we can't ensure safety with any controller. But we also need a forward invariant controller to actually find the safe control input.

So the design problem is: given a controlled invariant set, construct a policy that renders it forward invariant. That is what a control barrier function is for.

Vector fields and Lie derivatives

The Lie derivative of a scalar function \(h\) along a vector field \(f\) is the directional derivative of \(h\) in the direction \(f\):

$$L_f h(x) \ =\ \nabla h(x)^\top f(x) \ =\ \frac{\partial h}{\partial x}(x)\, f(x).$$

It is a scalar, shows how \(f\) affects \(h\). The Lie derivative is the component of the vector field along that normal, so its sign is the in-or-out question: \(L_f h > 0\) means the flow carries you deeper into \(\mathcal{C}\), \(L_f h < 0\) means it carries you out, and \(L_f h = 0\) means it runs parallel to the level set.

h = 2 h = 1 h = 0 ∇h f(x) L f h the component of the flow along the inward normal is the rate of change of h
The gradient supplies the direction; the Lie derivative says how much of the vector field points that way.

Apply the chain rule to the controlled system and the rate of change of \(h\) splits cleanly in two:

$$\frac{d}{dt} h(x(t)) \ =\ \nabla h^\top \big(f(x) + g(x)u\big) \ =\ \underbrace{L_f h(x)}_{\text{drift}} \ +\ \underbrace{L_g h(x)\,u}_{\text{control}} .$$

Here \(L_g h(x) = \nabla h(x)^\top g(x)\) is a row vector in \(\mathbb{R}^{1\times m}\), one entry per input channel, each saying how strongly that channel moves \(h\). This decomposition is the whole reason control barrier functions work:

  • \(L_f h\) is what the system does to your safety margin on its own. You get no say in it.
  • \(L_g h\,u\) is your authority over that margin, and it is linear in \(u\). Any requirement of the form \(\dot h \ge \text{something}\) is therefore an affine inequality in the decision variable.
  • If \(L_g h(x) = 0\) you have no first-order authority at all: at this instant the input cannot influence \(h\), whatever you do. That is the relative-degree problem, and it is what exponential and high-order CBFs exist to handle.

From Nagumo to a condition you can enforce

Combining the last two sections, controlled invariance at a boundary point reads

$$\exists\, u \in U \ : \quad L_f h(x) + L_g h(x)\,u \ \ge\ 0, \qquad x \in \partial\mathcal{C}.$$

Correct, but awkward to build a controller around. The condition only cares about being safer than before.

The fix is to extend it to a condition defined everywhere that reduces to Nagumo's at the boundary and relaxes smoothly inward. Pick an extended class \(\mathcal{K}_\infty\) function \(\alpha\) — strictly increasing, \(\alpha(0) = 0\), defined on all of \(\mathbb{R}\)— and require

$$\dot h(x,u) \ =\ L_f h(x) + L_g h(x)\,u \ \ge\ -\alpha\big(h(x)\big).$$

At \(h = 0\) the right-hand side is zero and this is exactly \(\dot h \ge 0\). For \(h > 0\) it is negative, so \(h\) is allowed to decrease, and the deeper inside you are the faster it may decrease. The constraint interferes only as the margin goes to zero.

Note what that argument needs: the inequality must hold along the whole trajectory, not merely at points of \(\mathcal{C}\). That is why the CBF condition is stated on a domain \(D \supset \mathcal{C}\) rather than on \(\mathcal{C}\) alone, and it is where the regular-value condition from section 2 comes back. The next page takes that apart.

zeroing cbf

A zeroing barrier function goes to zero at the boundary, with the condition \(\dot h \ge -\alpha(h)\) from the previous section. Outside the set \(h < 0\), so \(-\alpha(h) > 0\) and the condition demands that \(h\) increase. It drives the state back. The set is not merely invariant but asymptotically stable.

Reciprocal (RCBF)Zeroing (ZCBF)
Behaviour at \(\partial\mathcal{C}\)\(B \to \infty\)\(h \to 0\)
Domain\(\mathrm{Int}(\mathcal{C})\) onlyall of \(D \supset \mathcal{C}\)
Guaranteeinvariance of the interiorinvariance of \(\mathcal{C}\), plus asymptotic stability of \(\mathcal{C}\)
Recovery from \(h < 0\)undefinedbuilt into the condition
Conditioning near the edgepoor; effort grows without boundbenign

The intuition worth keeping

A zeroing CBF does not keep you away from the boundary. It lets you go right up to it, and only insists that when you get there, you still have the authority to stay in.

The constraint \(\dot h \ge -\alpha(h)\) is slack while \(h\) is large: deep inside the set the margin may be spent freely and the nominal controller runs untouched. As \(h\) shrinks the permitted rate of decrease shrinks with it, so the margin is spent more and more slowly — you decelerate toward the boundary rather than being repelled from it. At \(h = 0\) the permitted rate is exactly zero, which is Nagumo's condition, and at that moment the input has to be able to ensure \(\dot h \ge 0\).

$$K_{\mathrm{cbf}}(x) = \big\{ u \in U : L_f h(x) + L_g h(x)\,u + \alpha(h(x)) \ge 0 \big\}$$

be nonempty at every state — which at a boundary point needs \(L_g h(x) \neq 0\), so that the input has first-order authority over \(h\), and needs \(U\) to be large enough to overcome the drift \(L_f h(x)\). A CBF is a certificate that this authority is present everywhere.

Scaling \(\alpha\) up makes the constraint more permissive, letting the state approach faster and brake later; scaling it down keeps the state conservatively inside.

The CBF-QP

You have a nominal controller \(k(x)\) that does whatever the task requires and knows nothing about safety, and a constraint that is affine in \(u\). So minimally modify the nominal input that satisfies the cbf constraint (and thus ensures safety):

$$\begin{aligned} u^\star(x) \ =\ \underset{u \in U}{\arg\min} \quad & \tfrac{1}{2}\big\|u - k(x)\big\|^2 \\ \text{subject to} \quad & L_f h(x) + L_g h(x)\,u \ \ge\ -\alpha\big(h(x)\big). \end{aligned}$$

A quadratic objective with affine constraints: a quadratic program. Several safety constraints are several rows. A control Lyapunov function for the task can be added as another row, usually with a slack variable so that safety takes precedence over stability.

The structure is modular in a way that matters in practice. The nominal controller can be a PID loop, an MPC, or a learned policy; the filter does not care, and it intervenes only when the constraint is about to bind. This is the safety filter pattern.

References

  • Nagumo, “Über die Lage der Integralkurven gewöhnlicher Differentialgleichungen,” 1942. The original invariance theorem; Blanchini's survey “Set invariance in control” (Automatica, 1999) is the readable modern account.
  • Ames, Xu, Grizzle, Tabuada, “Control barrier function based quadratic programs for safety critical systems,” IEEE TAC 62(8), 2017. Defines both the reciprocal and zeroing forms and relates them.
  • Xu, Tabuada, Grizzle, Ames, “Robustness of control barrier functions for safety critical control,” ADHS 2015. The robustness argument that settles the question in favour of the zeroing form.
  • Ames, Coogan, Egerstedt, Notomista, Sreenath, Tabuada, “Control Barrier Functions: Theory and Applications,” ECC 2019 (arXiv:1903.11199). The standard tutorial reference and the source of the definitions used here.
← Control law design CBF-QP: three clarifications →