Least Restrictive Hyperplane Control Barrier Functions

Control Barrier Functions (CBFs) provide provable safety guarantees for dynamic systems, but finding a valid CBF can be nontrivial for complex systems due to computational constraints. This paper introduces the Least Restrictive Hyperplane Control Barrier Function (LRH-CBF), which generalizes distance-based CBFs by optimizing over the orientation of supporting hyperplanes to find a safe control action that is as close as possible to the desired one, thereby reducing conservatism.

The core concept involves finding an optimal safety constraint.

The central idea is to replace the standard CBF approach—where a single CBF is chosen first and then a safe control is found—with an optimization over a family of CBFs parameterized by some variable, denoted as theta (θ). The goal is to find the combined choice of (θ, u) that makes u safe, and minimises u − udes. This results in the Least Restrictive Hyperplane CBF (LRH-CBF).

The optimization problem is formally defined as Problem 3.

Problem 3 replaces Problem 1 (CBF-QP) with the Least Restrictive-CBF-Optimisation-Problem (LR-CBF-OP):

(u(x), θ) = argmin u,θ (u − udes)T Q(u − udes) s.t. h˙(x, θ, u) ≥ −α(h(x, θ)) h(x, θ) ≥ 0 u ∈ U, θ ∈ Θ.

This formulation ensures that the chosen CBF is such that the agent and the obstacle are on the same side of the hyperplane, which corresponds to removing an invalid choice like P5 in Figure 1.

The approach generalizes existing methods by optimizing over a family of hyperplanes.

The paper studies Hyperplane CBFs (H-CBFs), where a hyperplane separates the agent from the obstacle. It notes that a common distance-based CBF is a special case of an H-CBF where the hyperplane is a supporting hyperplane of the obstacle that is orthogonal to a line between the agent and the obstacle. The LRH-CBF approach allows one to optimise over a family of CBFs using θ, to find the least restrictive H-CBF, enabling controls that are closer to the desired ones, especially when moving fast and passing close to obstacles.

The analysis establishes existence and conservativeness conditions.

The paper uses convex analysis results (Theorem 1 and Theorem 2) to show that for any given orientation nˆ(θ), a H-CBF exists as a supporting hyperplane to the convex hull of the obstacle. Furthermore, Lemma 2 provides sufficient conditions for the existence of a single H-CBF that does not interfere with a given safe trajectory, specifically when the convex hull of the obstacle and the convex hull of the trajectory positions do not intersect.

The performance is evaluated through simulations comparing different parameterizations.

The researchers compare Continuous and Discrete LRH-CBFs (C-LRH-CBFs and D-LRH-CBFs) against the standard Orthogonal Hyperplane CBF (OH-CBF). Simulations demonstrate that the LRH-CBF is less conservative regarding the obstacles, resulting in a faster trajectory. The results show that while computational complexity is comparable to the highly popular OH-CBF, performance is significantly better. The choice of the set Θ, such as whether it's a single element or a spread around thetaOH, impacts convergence speed and performance depending on the resolution Nθ.

The method handles various obstacle geometries through specialized H-CBF formulations.

The paper details how to find the required safety margin δ(θ) for different shapes:

1. For general closed, bounded obstacles O, δ(θ) is found by solving δ(θ) = max p∈conv(O) nˆ(θ)T p.

2. For polygonal obstacles, this simplifies to finding the supremum over the vertex set: δ(θ) = sup p∈[p1,p2,…,pK] nˆ(θ)T p.

3. For ellipses given in a specific form, the optimization yields a closed-form solution for δ(θ), involving trigonometric functions of the eccentric anomaly γmax.

The discrete-time implementation involves a modification to the continuous constraint.

For discrete-time systems (D-CBFs), the continuous CBF constraint is transformed into: h˙(xk) − ∆t (nˆ(θ)T(uk)) squared / 2umax ≥ −α(h(xk)), where α(x) = xγ/∆t. This means the problem reduces to a Quadratically Constrained QP for a fixed θ.

**The paper concludes that selecting the CBF with the desired control is superior.

Based on the provided scientific paper, here are the specific improvements that can be made to AI systems and what those improved systems could achieve:

The core contribution of this paper is a method called the Least Restrictive Hyperplane Control Barrier Function (LRH-CBF), which optimizes over a family of hyperplanes rather than using a single, conservative one.

Here are the specific improvements and capabilities for an AI system utilizing this approach:

1. The system can implement safety filters that are significantly less conservative than traditional distance-based Control Barrier Functions (OH-CBFs).

2. This allows the AI agent to execute control actions that are much closer to its desired, aggressive maneuvers (i.e., minimizes the deviation between safe and desired control, u - udes), especially when moving fast or passing obstacles closely.

3. The system can handle complex obstacle geometries (such as ellipses and polygons) effectively by optimizing the hyperplane orientation over a family of possibilities rather than relying on a single, fixed geometric model.

4. The safety guarantees are maintained while allowing for higher performance and faster trajectories compared to systems using standard OH-CBFs, leading to improved efficiency in dynamic environments.

Specifically, the improved AI system can:

1. Perform high-speed maneuvers near complex obstacles (like those modeled by ellipses or polygons) with minimal unnecessary braking or slowdowns that are characteristic of conservative safety filters.

2. Navigate narrow gaps between moving and static obstacles more aggressively by choosing the optimal hyperplane orientation to maximize the allowable control input, enabling trajectories closer to the desired path without violating safety constraints.

3. Maintain provable safety guarantees in dynamic systems (like double integrators with acceleration constraints) while maximizing performance metrics like speed and tracking accuracy (minimizing u - udes).

4. Be deployed in scenarios where computational resources are limited, as the proposed approach has a complexity comparable to the standard OH-CBF, making it practical for real-time embedded systems.