Control Barrier Functions

Key Terms

Barrier Functions

Purpose

Barrier functions are designed to penalise or discourage solutions that violate constraints. They are used in constrained optimsation problems, where certain conditions must be satisfied by the solution.

How it works

In essence, a barrier function incorporates constraints of optimisation problem into objective function. This is done by adding a penalty term to the objective function that becomes large as the solution approaches the boundary of the feasible region defined by the constraints.

Nagumo's Theorem

Defines necessary and sufficient conditions for set invariance (safety).

Theorem defines a safe set 'C' (like a safe driving path) using a mathematical function ' $h$ '. If the system's state is described by ' $x$ ', the safe set includes all states where $h (x)$ is non-negative (safe states). The theorem states that the system remains in this safe set if the rate of change of $h$ along the path's boundary is never negative. This ensures that the system doesn't cross from safe to unsafe.

$C is invariant ⟺ \dot{h} (x) \geq 0$ for all $x$ on the boundary of set C

Advantages and Disadvantages

Barrier functions allow for the conversion of a constrained problem into an unconstrained one, simplifying the optimization process.

However, the choice of barrier function and its parameters can significantly impact the convergence and performance of the optimization algorithm.

Types

Given the case of objective $f (x)$ with constraints $g_{i} (x) \leq 0$ for $i = 1, . . ., m$

The barrier adds a term to the objective function. The purpose is for the barrier function to grow as the function approaches the constraint boundary.

Linear Barrier Function:

F (x, c) = f (x) + \frac{1}{c} \sum_{m}^{i + 1} max (0, g_{i} (x))

Quadratic Barrier Function:

F (x, c) = f (x) + \frac{1}{c^{2}} \sum_{m}^{i + 1} max (0, g_{i} (x))

Logarithmic Barrier Function:

F (x, c) = f (x) + - 1 \sum_{m}^{i + 1} l n (- g_{i} (x))

Examples

Logarithmic barrier functions:
Consider the optimisation problem:

Minimise $f (x) = x^{2} \in x \geq 1$

Here the constraint can be rewritten as $g (x) = 1 - x \leq 0$

By applying a logarithmic barrier function, the modified objective function becomes:

F (x, c) = x^{2} - c \ln (1 - x)

As $x$ approaches 1, the logarithmic term, becomes large, penalising solutions near the constraint boundary. In practice, an optimisation algorithm would minimise $F (x, c)$ for a sequence of decreasing values of $c$ , effectively pushing the solution towards the boundary of the feasible region while maintaining feasibility.

Interior Point Methods

Purpose

Algorithms for solving linear and nonlinear optimsation probems. They are particularly useful for large-scale optimisation problems, like linear programming, quadratic programming and convex optimisation.

How it works

Starting from a point within the interior of the feasibly region (set) and iteratively moving towards the solution. This is in contrast to the methods like simplex algorithms that operate on boundary of the feasible region.

Key Features:

Barrier Functions: Interior point methods often use barrier functions to ensure that the iterations remain within the feasible region. The logarithmic barrier function is a common choice.
Polynomial Time Complexity: These methods have a polynomial time complexity, which can make them more efficient for certain large-scale problems compared to other methods like the simplex algorithm.
Path-Following Algorithms: They typically follow a path that is defined by a sequence of optimization problems with decreasing values of a parameter in the barrier function.

Lyapunov Function

Definition and Purpose

Lyapunov function is a scalar function that helps to determine stability of an equlibrium point in a dynamical system. The function is analogous to a potential energy function in physics, where its value represents a measure of the system's potential for change.

They are valuable because they provide a way to prove stability without solving system's differential equation directly. Useful if equation is too complex to solve analytically.

Characteristics

Positive Definiteness

A Lyapunov function $V (x)$ is typically required to be positive definite. i.e. $V (x) > 0$ for all $x \neq 0$ and $V (0) = 0$ . This means that the function has a minimum value at the equilibrium point. Kind of like a bowl.

Derivative Sign

The derivative of the Lyapunov function along the trajectories of the system, $\dot{V} (x) \leq 0$ for all $x$ in the region of interest. This means that the function does not increase in value over time, suggests stability.

Choosing a Lyapunov Function

Choosing a Lyapunov function for a dynamical system is more of an art than an exact science, as there's no universal method applicable to all systems. However, some general guidelines can help in the selection process:

Positive Definiteness
Negative Definite Derivative
Intuition and System Knowledge - Understanding the physics or mechanics of the system can guide the choice. For mechanical systems, energy-like functions (kinetic plus potential energy) often serve as good candidates.
Simplicity and Computability - Prefer simpler functions that make it easier to compute the derivative and analyze the system.
Trial and Error - Sometimes, selecting a Lyapunov function involves trial and error, testing different functions to see which one satisfies the necessary conditions for the particular system being analyzed.

It is possible for one Lyapunov function to prove stability for a system while another does not. This can occur because the effectiveness of a Lyapunov function in proving stability depends on its specific form and how well it captures the dynamics of the system. A Lyapunov function that fails to prove stability doesn't necessarily mean the system is unstable; it might simply be that the particular function chosen isn't suitable for demonstrating stability for that system.

Therefore, finding a Lyapunov function that proves stability can sometimes be a matter of trial and error, and the inability of one function to prove stability doesn't preclude the existence of another function that can.

Types of Stability Analysis

Stability

If $\dot{V} (x) \leq 0$ the equilibrium point is stable. Small perturbations from equilibrium will not cause system to diverge significantly.

Asymptotic Stability

If $\dot{V} (x) < 0$ the equilibrium is asymptotically stable. Perturbations will not only stay bounded but will also decay to zero over time.

Global Stability

If Lyapunov function and its derivative conditions are valid for all $x$ in the system, then global stability is implied, meaning the stability conditions hold for any initial state of the system.

Barrier Certificates

Definition and Purpose

Barrier certificate is a function $B (x)$ that separates the state space of a dynamical system into safe and unsafe regions. Function is constructed such that its level sets define a boundary between safe and unsafe states.

They are used to certify that trajectories of the system starting from a safe initial condition will not enter unsafe regions over time.

Characteristics

Non-negativity

Typically $B (x)$ is designed such that it is non-negative in the safe region and negative in the unsafe region.

Derivative Condition

Along the trajectories of the system, the derivative of $B (x)$ , denoted as $\dot{B} (x)$ , must satisfy certain conditions to ensure safety. Common requirement is that it should be non-positive whenever $B (x) = 0$ . This ensures that the system's trajectory cannot cross from safe into unsafe regions.

Example

Consider a simple robotic system where the goal is to ensure the robot does not collide with an obstacle. Let's define the state of the robot as $x$ and the unsafe region as a particular area around the obstacle.

A barrier certificate $B (x)$ can be designed such that the $B (x) \geq 0$ represents the safe region (away from the obstacle) and $B (x) < 0$ represents the unsafe region (close to or in the obstacle).

If we can show that for all initial states $x_{0}$ in teh safe region and for all times $t \geq 0, B (x (t)) \geq 0$ holds (the certificate's value remains non-negative along system trajectory) then we have certified that the robot will not collide with the obstace.

Application

Barrier certificates are used extensively in the verification of safety properties in autonomous systems, including robots and self-driving cars. They are crucial in scenarios where it is not feasible to test all possible trajectories for safety, which is often the case in complex or high-dimensional systems. By providing a mathematical proof of safety, barrier certificates play a vital role in the design and implementation of reliable and secure autonomous systems.

Locally Lipschitz

Refers to a property of a function in context of differential equations and control theory. A function $f (x)$ is said to be locally Lipschitz if, for every point in its domain, there exists a neighbourhood around that point where the function does not change too rapidly.

In more technical terms, within this neighbourhood, the difference in the function's values at any two points is bounded by a constant (Lipschitz constant) times the distance between the two points.

This property is important to ensure that the well-behavedness of solutions to differential equations and is often a requirement for applying certain mathematical theorems and techniques.

Paper - Control Barrier Functions: Theory and Application

Access reference

Objective

Safety requires that "bad" things do not happen while liveness requires that "good" things eventually happen.

Asymptotic stability is an example of a liveness property since it is seen as "equilibrium is eventually reached". Invariance is analogous to safety.

Usually Lyapunov functions have played a predominant role in the investigation of liveness properties. This paper aims to refocus the discussion on safety by introducing control barrier functions that play a role equivalent to Lyapunov functions in study of liveness property.

Paper aims to establish basic theory of safety-critical control and highlight some important applications.

Fundamentals

Always consider a nonlinear affine control system:

\dot{x} = f (x) + g (x) u

Control Lyapunov Function (CLF)

Definition and Purpose

CLFs are used to ensure the stability of a system. They help in designing a control input that drives the system towards a desired stable state.

A function $V (x)$ is a CLF if it satisfies all the rules as defined by a regular #Lyapunov Function, with regards to its positive definiteness and negative definiteness of its derivative.

Difference between CLF and regular Lyapunov Function

Regular LF

Primarily used to analyse stablity of an equilibrium point of a system. If such a function decreases over time, it implies that the system's state will converge to the equilibrium, indicating stability.

Consider simple system:

\dot{x} = - x

A potential LF could be

V (x) = \frac{1}{2} x^{2}

Take time derivative:

\dot{V} (x) = \frac{d V}{d x} \times \frac{d x}{d t} = x (- x) = - x^{2}

It abides to all the rules of a LF. Now at $x = 0$ the $\dot{V} (x) = 0$ thus the system is stable.

CLF

Extends the concept to systems with control inputs. It is designed not just to assert stability but to actively guide the selection of control inputs that ensure the system's convergence to a stable state. Essentially, a CLF helps in designing a controller for stabilizing the system.

For a control system described:

\dot{x} = u

A CLF might also be:

V (x) = \frac{1}{2} x^{2}

However, we can use the CLF to design a control law. For example, by choosing:

u = - k x, k > 0

We find the derivative (note that it is being done w.r.t. time variable):

\dot{V} (x) = \frac{d V}{d x} \times \frac{d x}{d t} = x \dot{x} = x (- k x) = - k x^{2}

Which is negative definite. Thus the control law can stabilise the system at $x = 0$

Theorem 1

For the nonlinear control system, if there exists a control Lyapunov function positive definite function satisfying (3), then any Lipschitz continuous feedback controller $u (x) \in K_{c l f} (x)$ asymptotically stabilizes the system to $x^{s t a r} = 0$ .

Control Barrier Function (CBF)

Definition and Purpose

CBFs provide a more flexible way to define safety in control systems. It defines a safe region (C), and the system is controlled to stay within C without requiring every possible state within C to always remain within C.

Unlike stability which involves driving a system to a point (or set), safety can be framed in the context of enforcing invariance of a set (i.e. not to leave a safe set).

{sup}_{u \in U} [L_{f} h (x) + L_{g} h (x) u] \geq - α (h (x))

Control Lyapunov Functions (CLFs) are powerful tools for ensuring stability in control systems. They help define regions (sublevel sets) where the system is guaranteed to remain.

However, CLFs can be overly restrictive for defining safety in systems. Applying CLF concepts directly would prevent a system from ever leaving a defined safe region, which might be too limiting in practice.