A Forward Reachability Perspective on Control Barrier Functions and Discount Factors in Reachability Analysis

1. Problem Statement

The paper addresses the challenge of designing safe control policies for nonlinear systems subject to adversarial disturbances over an indefinite time horizon. The core objective is to identify Control Invariant Sets (sets where the system can remain forever) and construct Control Barrier Functions (CBFs) to enforce safety.

Limitations of Existing Approaches (Backward Reachability):

• Traditional methods rely on Backward Reachability Analysis (computing the Backward Reachable Tube, BRT) to find the maximal robust control invariant set.
• These methods typically use Hamilton-Jacobi (HJ) formulations with discount factors that lead to value functions which are either:
  • Flat (zero gradient) inside the invariant set, making them useless for generating control inputs via barrier constraints.
  • Unbounded or discontinuous when attempting to enforce barrier constraints (e.g., using negative discount factors), leading to non-unique solutions in the HJ partial differential equations (PDEs).
• Consequently, backward reachability does not naturally yield valid, differentiable CBFs that satisfy the required barrier constraints everywhere.

2. Methodology

The authors propose a novel framework based on Forward Reachability and Differential Games to bridge the gap between reachability analysis and CBFs.

A. Inevitable Forward Reachable Tube (FRT)

Instead of looking backward from a failure set, the authors define the Inevitable Forward Reachable Tube (FRT) of an initial set $C$.

• Definition: The FRT is the set of all states that inevitably must have passed through the initial set $C$ in the past, regardless of the control input (assuming worst-case disturbances).
• Game Formulation: It is formulated as a differential game where the disturbance acts adversarially to expand the tube, and the control acts to restrain its growth.
• Mathematical Characterization: The FRT is characterized as the strict zero-superlevel set of a value function $V_\gamma(x)$.

B. Hamilton-Jacobi Formulation with Discount Factor

The authors introduce a specific cost functional for the differential game involving a discount factor $\gamma > 0$ applied backward in time:
$$J_\gamma = \sup_{t \in (-\infty, 0]} e^{\gamma t} h_C(x(t))$$
where $h_C$ is a function defining the initial set.

• HJ-FRT-VI: The value function $V_\gamma$ is the unique viscosity solution to a specific Hamilton-Jacobi Variational Inequality (HJ-FRT-VI):
  $$0 = \min \left\{ V_\gamma(x) - h_C(x), \quad \max_{u \in U} \min_{d \in D} \left( \nabla V_\gamma \cdot f(x, u, d) + \gamma V_\gamma(x) \right) \right\}$$
• Key Insight: The term $+\gamma V_\gamma(x)$ (arising from the backward-time discount) naturally enforces the barrier constraint required for CBFs, unlike the $-\gamma V$ term in backward formulations.

C. Connection to Control Barrier Functions (CBFs)

The paper establishes a rigorous theoretical link:

1. FRT as a CBF: If the boundary of the FRT is continuously differentiable ($C^1$), the value function $V_\gamma$ itself is a valid robust CBF.
2. Supersolutions as CBFs: Even if the exact viscosity solution $V_\gamma$ is non-differentiable (which can happen at boundaries), any $C^1$ supersolution $W$ of the HJ-FRT-VI is a valid robust CBF.
   • A supersolution $W$ satisfies the inequality version of the HJ-PDE.
   • The zero-superlevel set of such a $W$ is a robust control invariant set that outer-approximates the FRT.

D. Learning-Based Approach (Neural FRT-CBF)

To compute these supersolutions for complex systems, the authors propose a neural network-based method:

• Architecture: A Multi-Layer Perceptron (MLP) outputs two functions, $u_\theta(x)$ and $v_\theta(x)$.
• Parameterization: The learned CBF is defined as $W_\theta(x) = h_C(x) + u_\theta(x)^2$. This hard-constraint ensures $W_\theta(x) \geq h_C(x)$, guaranteeing the learned set contains the initial set.
• Loss Function: The training minimizes three terms:
  1. HJ-Supersolution Loss: Penalizes violation of the HJ-FRT-VI inequality (the barrier constraint).
  2. Set Inclusion Loss: Ensures the learned set remains within the global safety constraints ($X$).
  3. Control Invariance Loss: Enforces tangential conditions at the boundary of the learned set.

3. Key Contributions

1. Forward Reachability Framework: First work to systematically connect forward reachability with Control Barrier Functions, contrasting with the dominant backward reachability literature.
2. Theoretical Link via Discount Factors: Proves that incorporating a discount factor in the forward reachability cost function naturally induces the barrier constraint ($\nabla V \cdot f + \gamma V \geq 0$) in the HJ equation.
3. Supersolution Characterization: Establishes that any $C^1$ supersolution of the HJ-FRT-VI is a valid robust CBF. This provides a constructive method to generate differentiable CBFs even when the exact value function is non-smooth.
4. Outer-Approximation Guarantee: Proves that the set defined by any valid CBF derived from this method is a robust control invariant set that contains the Inevitable FRT.
5. Neural Learning Algorithm: Develops a practical, learning-based algorithm (Neural FRT-CBF) to compute these supersolutions for high-dimensional nonlinear systems, avoiding the "curse of dimensionality" associated with grid-based HJ solvers.

4. Results

• Double Integrator Example: The method was tested on a double integrator system.
  • Scenario: The initial set was chosen to be non-invariant (a circle).
  • Outcome: The backward reachability approach would struggle to find a smooth CBF for this set. The proposed method successfully learned a smooth CBF ($W_\theta$) whose zero-superlevel set is a control invariant set that strictly contains the initial set and outer-approximates the minimal invariant set.
  • Visualization: The learned function was shown to be continuously differentiable and satisfied the barrier constraint, whereas the exact FRT value function (computed via finite-horizon methods) exhibited non-differentiable points.
• Convergence: Theoretical proofs (via contraction mapping) guarantee the uniqueness of the value function and the convergence of the learning process.

5. Significance

• Bridging Theory and Practice: This work resolves a long-standing theoretical disconnect where reachability analysis (often used for verification) and CBFs (used for real-time control) were treated as separate, often incompatible, frameworks.
• Robustness: By explicitly modeling disturbances as an adversary in a differential game, the resulting CBFs are robust, ensuring safety even under worst-case perturbations.
• Differentiability: The focus on supersolutions allows for the construction of smooth, differentiable CBFs, which are essential for gradient-based control optimization (e.g., in Quadratic Programming formulations) and avoid the chattering or discontinuity issues common in non-smooth value functions.
• Scalability: The learning-based approach offers a path to applying rigorous safety guarantees to high-dimensional systems where traditional grid-based HJ solvers are computationally infeasible.

In summary, the paper redefines the relationship between reachability and safety by showing that forward reachability with a discount factor is the inverse-optimal cost function for Control Barrier Functions, providing a unified, mathematically rigorous, and computationally tractable framework for safe control design.