Certifiable Reachability Learning Using a New Lipschitz Continuous Value Function

Jingqi Li, Donggun Lee, Jaewon Lee, Kris Shengjun Dong, Somayeh Sojoudi, Claire Tomlin

TL;DR

Researchers have developed a new framework for training robots to perform complex tasks—like high-speed drone racing—with deterministic safety guarantees. By introducing a novel, Lipschitz continuous value function, the team enables deep reinforcement learning to solve high-dimensional "reach-avoid" problems faster and more reliably than previous methods, providing a way to mathematically certify safety in real-time.

What Problem Does This Paper Address?

In robotics, "reach-avoid" problems are the bread and butter of autonomy: a robot must reach a target (the "reach") while staying within safe boundaries and avoiding obstacles (the "avoid"), even when faced with unpredictable disturbances like wind or the erratic movements of other agents.

Traditionally, these problems are solved using Hamilton-Jacobi (HJ) reachability analysis. While mathematically rigorous, HJ analysis hits a "curse of dimensionality"—as the number of variables (dimensions) in a system grows, the computational cost explodes. While machine learning (ML) can handle high dimensions, it usually lacks deterministic safety guarantees. You might know a robot is likely safe, but you can't prove it. Furthermore, the mathematical functions ML models try to learn in these scenarios are often "jumpy" (discontinuous), making training unstable and slow.

Methods

The authors propose a two-part solution: a new way to learn safety and a new way to prove it.

1. A Better Value Function

The core innovation is a new time-discounted reach-avoid value function. Unlike previous versions that were prone to discontinuities, this new function is provably Lipschitz continuous. In plain English, this means the function changes smoothly, which is a massive advantage for training neural networks.

Crucially, they prove that their associated Bellman operator is a contraction mapping. This ensures that the learning process converges to a unique, stable solution without the need for complex "annealing" tricks used in prior work.

2. Deterministic Certification

Once the value function is learned via a max-min Deep Deterministic Policy Gradient (DDPG) approach, the framework applies post-learning certification to define a "trustworthy" set of safe states:

  • Lipschitz Certification: Uses the mathematical smoothness of the system to quickly bound safety. It’s fast but can be conservative.
  • SOCP Certification: Uses Second-Order Cone Programming to search for a tighter, more accurate safe set.

These methods can be run offline to map out safe zones or online (at 10 Hz) to verify safety during a mission.

Figure 1: Applying our reachability analysis framework to drone racing. In (a), hardware experiments demonstrate that our learned control policy enables an ego drone to safely overtake another drone, despite unpredictable disturbances in the other drone’s acceleration. In (b), we illustrate the concept of the propeller induced airflow [15], which can affect other drones’ flight. In (c), we apply our learned control policy in a simulation with randomly sampled disturbances. In (d), we project the learned reach-avoid value function onto the (x, y) position of the ego drone. The super-zero level set, outlined by dashed curves, indicates our learned reach-avoid (RA) set. In (e), we plot the certified RA sets using Lipschitz and second-order cone programming certification.

Datasets and Benchmarks

The researchers validated their framework on two challenging high-dimensional systems:

  • 12D Drone Racing: A hardware experiment using Crazyflie drones where an "ego" drone must overtake another drone while avoiding the turbulent airflow (propeller wash) generated by the leader.
  • 10D Highway Overtaking: A simulation where a vehicle must safely pass a slower car while avoiding a third vehicle coming from the opposite direction.

They compared their approach against state-of-the-art constrained reinforcement learning (CRL) methods, including DDPG-Lagrangian, SAC-Lagrangian, and Constrained Policy Optimization (CPO).

Key Insights and Ideas

  • Smoothness Matters: By ensuring the value function is Lipschitz continuous, the "landscape" the neural network navigates during training becomes much easier to climb, leading to faster convergence.
  • Contraction is King: Proving the Bellman operator is a contraction mapping removes the need for the "gamma-annealing" process, theoretically reducing training time to a fraction ($1/N$) of previous methods.
  • Deterministic > Probabilistic: While many ML safety papers offer "probabilistic" safety (e.g., 99% safe), this method provides a hard mathematical guarantee for states within the certified set.
Figure 2: Comparing Vγ(x) with ¯V (x) from (9) and V (x), a constructed solution to the Bellman equation of ¯V (x) in prior works [6]–[11], [14]. Consider a 1-dimensional dynamics: xt+1 = 1.01xt + 0.01(ut + dt), with |ut| ≤1 and |dt| ≤0.5. We associate T = {x : x < −1} and C = {x : x > −2} with bounded, Lipschitz continuous functions r(x) = max(min(−(x + 1), 10), −10) and c(x) = max(min(x + 2, 10), −10), respectively. For all γ ∈(0, 1), our super-zero level set {x : Vγ(x) > 0} equals the RA set R = {x : −2 < x < 0.5}. By Theorem 2, Vγ(x) is Lipschitz continuous if γ ∈(0, 0.99009). The super-zero level set of ¯V (x) also recovers R, but ¯V (x) is discontinuous at x = 0.5 because the control fails to drive the state to T under the worst-case disturbance when xt ≥0.5. Finally, in the third subfigure, we show that the Bellman equation in prior works [6]–[11], [14] has non-unique solutions, whose super-zero level set may not equal R.

Key Results

  • 100% Success Rate: In both drone racing and highway simulations, every single test starting from the SOCP-certified set successfully reached the target safely, despite disturbances.
  • Superior Learning: The proposed method significantly outperformed standard CRL methods. For example, in the highway simulation, the new method achieved an 87.8% success rate in a large state set, compared to just 55.5% for CPO.
  • Real-Time Capability: The certification process is efficient enough to run at 10 Hz, making it viable for active safety filtering during flight or driving.
The highway overtaking simulation, illustrating the ego vehicle (orange) navigating around other vehicles within the certified safe zones.

Limitations and Future Work

While the certification is fast, it currently relies on a value function that must be learned offline beforehand. The authors suggest that future research could explore online reachability learning, allowing a robot to adapt its safety certificates on the fly as it encounters new environments. Additionally, they aim to develop even more efficient certification algorithms to handle even higher-dimensional or more complex nonlinear dynamics.

Summary updated

Abstract

We propose a new reachability learning framework for high-dimensional nonlinear systems, focusing on reach-avoid problems. These problems require computing the reach-avoid set, which ensures that all its elements can safely reach a target set despite disturbances within pre-specified bounds. Our framework has two main parts: offline learning of a newly designed reachavoid value function, and post-learning certification. Compared to prior work, our new value function is Lipschitz continuous and its associated Bellman operator is a contraction mapping, both of which improve the learning performance. To ensure deterministic guarantees of our learned reach-avoid set, we introduce two efficient post-learning certification methods. Both methods can be used online for real-time local certification or offline for comprehensive certification. We validate our framework in a 12-dimensional crazyflie drone racing hardware experiment and a simulated 10-dimensional highway take-over example.
BibTeX
@article{li2025certifiable,
  author = {Jingqi Li and Donggun Lee and Jaewon Lee and Kris Shengjun Dong and Somayeh Sojoudi and Claire Tomlin},
  title = {{Certifiable Reachability Learning Using a New Lipschitz Continuous Value Function}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2025},
  doi = {10.1109/lra.2025.3535183},
}
Figure