⚡ electrical engineering

Refining Almost-Safe Value Functions on the Fly

This paper introduces refineCBF and its efficient successor HJ-Patch, a framework that enables real-time, online refinement of approximate or unsafe Control Barrier Functions via warm-started Hamilton-Jacobi reachability to guarantee formally safe adaptation to dynamic environmental changes on physical robotic systems.

Original authors: Sander Tonkens, Sosuke Kojima, Chenhao Liu, Judy Masri, Sylvia Herbert

Published 2026-03-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sander Tonkens, Sosuke Kojima, Chenhao Liu, Judy Masri, Sylvia Herbert

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to navigate a busy city. You want the robot to be fast and efficient, but most importantly, you need to guarantee it never crashes into a pedestrian or a wall.

In the world of robotics, this is a huge challenge. There are two main ways people try to solve this:

The "Perfect Map" Approach (Hamilton-Jacobi Reachability): This is like hiring a super-smart mathematician to calculate the perfect safe path for every single possible situation before the robot even starts moving. It's mathematically flawless and guarantees safety. But, it takes so much computing power that it can only be done for very simple robots or tiny rooms. If the city layout changes (a new construction site appears), you have to stop, recalculate everything from scratch, and wait hours. It's too slow for real life.
The "Gut Feeling" Approach (Learning/Neural Networks): This is like training a robot by showing it thousands of videos of safe driving. It learns quickly and can handle complex, messy environments. But, it's a "black box." Sometimes it makes a mistake because it hasn't seen that specific situation before, and it can't prove mathematically that it won't crash. It's fast, but not 100% safe.

The Problem: The "Static" Safety Net

The paper argues that we need the safety guarantees of the mathematician with the speed and adaptability of the gut-feeling robot.

Currently, if a robot using a "gut feeling" safety system encounters a new obstacle (like a sudden pothole or a gust of wind), the system might not know how to react safely. It's like driving with a map that was printed yesterday; if a bridge collapses today, your map is useless, and you might drive right off the edge.

The Solution: "Refining on the Fly"

The authors introduce two new algorithms, REFINECBF and HJ-PATCH, which act like a real-time safety editor.

Here is the core idea using a creative analogy:

The Analogy: The Sketch Artist and the Editor

Imagine a robot has a Sketch Artist (the initial safety function) who draws a rough outline of where it's safe to go.

Sometimes the artist is great, but sometimes they miss a detail (like a new wall).
Instead of firing the artist and hiring a new one to start from scratch (which takes too long), the authors bring in a Mathematical Editor.

REFINECBF is the Editor who looks at the Sketch Artist's rough drawing and says, "Okay, this part looks safe, but this corner near the new wall is risky. Let me fix just that part using strict math rules." It takes the rough sketch and "refines" it into a perfect, mathematically proven safe zone, but it does it so fast that the robot doesn't even stop moving.

HJ-PATCH is a super-fast version of this Editor. It realizes that if the robot is safe in 99% of the room, we don't need to redraw the whole room. We just need to patch the tiny hole where the new obstacle appeared. It's like using a band-aid instead of re-skinning the whole robot.

How It Works in Real Life

The paper tested this on two types of robots: a ground robot (like a Roomba on steroids) and a drone.

The "Sudden Wall" Test:
- Scenario: A robot is driving down a hallway. Suddenly, a heavy box falls in front of it.
- Old Way: The robot's safety system doesn't know the box is there. It keeps driving and crashes. Or, if it tries to recalculate the whole map, it freezes and crashes.
- New Way: The robot sees the box. The "Editor" instantly patches the safety map around the box. The robot smoothly steers around it, proving mathematically that the new path is safe, all while moving at full speed.
The "Gust of Wind" Test:
- Scenario: A drone is flying through a narrow gap. Suddenly, a fan turns on, creating a strong wind that pushes the drone sideways.
- Old Way: The drone thinks it's flying normally. The wind pushes it into the wall.
- New Way: The drone's sensors feel the wind. The "Editor" instantly updates the safety math to account for the wind pushing the drone. It tightens the safety rules, telling the drone, "You need to fly more aggressively to the left to counteract this wind," and it successfully navigates the gap.

Why This Matters

This research bridges the gap between theory and reality.

Before: You had to choose between a robot that was "safe but slow/stupid" or "fast but risky."
Now: You can have a robot that learns quickly, but if the world changes, it can instantly "edit" its own safety rules to guarantee it won't crash.

It's like giving a self-driving car a brain that doesn't just memorize rules, but can instantly rewrite its own rulebook the moment it sees a new danger, ensuring it stays safe no matter what happens. This is a massive step toward deploying truly autonomous robots in our unpredictable, real-world environments.

1. Problem Statement

The paper addresses the critical challenge of ensuring safety in robotic systems operating in dynamic, uncertain environments. While Control Barrier Functions (CBFs) are widely used to enforce safety via safety filters, designing a valid CBF that guarantees persistent safety is difficult.

Constructive Methods (Hamilton-Jacobi Reachability - HJR): Provide formal safety guarantees but suffer from the "curse of dimensionality," making them computationally intractable for real-time, high-dimensional systems. They are typically performed offline.
Approximate Methods (Learning-based CBFs): Offer scalability but lack formal guarantees and often fail to generalize to unseen environmental changes (e.g., new obstacles, unmodeled disturbances).
The Gap: Existing methods struggle to adapt online. If the environment changes (e.g., a new obstacle appears), a pre-computed safe value function may become invalid, leading to catastrophic failures. There is a need for a framework that bridges the gap between the formal guarantees of HJR and the scalability of approximate methods, enabling real-time, in-the-loop adaptation.

2. Methodology

The authors propose a framework that uses HJ Reachability to refine an initial, approximate (and potentially unsafe) value function online. The core idea is to treat the approximate function as a "warm start" for a formal refinement process.

Core Algorithms

The paper introduces two primary algorithms:

A. REFINECBF (Global Refinement)

Mechanism: Iteratively refines a candidate value function $h_0$ using the Variational Inequality (VI) formulation of HJ Reachability.
Process: It applies a dynamic programming update rule over a discretized state-space grid. It can run offline or continuously in-the-loop.
Adaptation: When environmental changes occur (new obstacles, changed disturbance bounds), the algorithm updates the constraint function $\ell(x)$ and continues refining the value function.
Safety Variant (SAFEADAPT-REFINECBF): To guarantee safety during the refinement process (not just at convergence), this variant uses a two-phase approach:
1. Retraction Phase: Uses a contractive PDE update to shrink the safe set until it is provably control-invariant (eliminating "false positive" unsafe states).
2. Refining Phase: Switches to the non-contractive VI update to expand the safe set for performance, leveraging the guarantee that safety is never lost once established.

B. HJ-PATCH (Local Patching)

Motivation: REFINECBF is computationally expensive because it updates the entire grid. HJ-PATCH is designed for scenarios where the initial CBF is "mostly safe" and only requires localized corrections.
Mechanism: Uses the Single-Boundary PDE formulation. Instead of updating the whole grid, it maintains an active set of states near the boundary of the safe set where the value is decreasing (potentially unsafe).
Efficiency: It only updates states in this active set and their neighbors. This drastically reduces computational cost, making it suitable for resource-constrained platforms (e.g., running on CPUs without GPUs).
Guarantee: It converges to the largest control-invariant subset of the initial guess's 0-superlevel set.

Theoretical Guarantees

Convergence: Both methods are proven to converge to a valid Control Barrier Value Function (CBVF).
Safety: The converged 0-superlevel set is a subset of the viability kernel (the largest set of states from which safety can be maintained).
Monotonic Improvement: The SAFEADAPT-REFINECBF and HJ-PATCH algorithms guarantee a monotonic reduction in "false positive" states (states incorrectly labeled as safe) with every iteration.
Robustness: The framework handles unknown but bounded external disturbances by incorporating them into the Hamiltonian calculation.

3. Key Contributions

Theoretical Extension: Extends the REFINECBF method to formally guarantee safety for systems subject to unknown but bounded external disturbances.
Unified Framework: Presents a unified approach spanning offline synthesis and online, in-the-loop adaptation, providing theoretical analysis for real-time deployment.
HJ-PATCH: Introduces a computationally efficient "patching" algorithm that accelerates refinement by focusing only on localized unsafe regions, enabling real-time performance on standard hardware.
Hardware Validation: Demonstrates the first successful real-time adaptation of formally guaranteed safety filters on physical hardware (ground robots and quadcopters) in the presence of sudden obstacles and unmodeled wind disturbances.

4. Experimental Results

The authors validated their framework through extensive simulations and hardware experiments.

Simulation (Ground Robot - Jackal):
- Scenario: A robot navigating with limited-range LiDAR in an environment with dynamic obstacles.
- Comparison: Compared against naive constraint combination (JointCBF) and full HJR re-computation.
- Result: JointCBF failed (collisions) due to infeasible joint constraints. Full HJR was too slow for real-time. HJ-PATCH (CPU) and REFINECBF (GPU) successfully avoided collisions, with HJ-PATCH showing superior performance on resource-constrained hardware.
Simulation (Quadcopter):
- Scenario: Navigation to a goal occluded by an obstacle, requiring the robot to discover new safe paths.
- Comparison: Compared against Backup CBFs (fixed policy).
- Result: Backup CBFs led to deadlock (unable to navigate around the obstacle). REFINECBF successfully expanded the safe set online to find a path over the obstacle.
Hardware Experiments:
- Mobile Robot: A Jackal robot encountered a suddenly fallen block. The adaptive REFINECBF detected the change, backtracked, and found a new safe path. A non-adaptive baseline crashed.
- Quadcopter (Occlusion): A drone navigated to a goal hidden behind an obstacle, then encountered a second hidden obstacle. The adaptive system updated its value function in <2 seconds and avoided the new obstacle.
- Quadcopter (Disturbances): A drone flew through a narrow passage with a fan creating unmodeled wind. The adaptive system detected the disturbance, updated the safety filter, and successfully navigated the passage (9/10 trials), while the non-adaptive baseline crashed.

5. Significance and Impact

Bridging Theory and Practice: The paper successfully bridges the gap between the rigorous safety guarantees of Hamilton-Jacobi Reachability and the practical need for real-time adaptability in robotics.
Real-World Viability: By demonstrating success on physical hardware with dynamic changes (falling objects, wind), the work proves that formal safety methods can be deployed outside of static simulations.
Scalability: The introduction of HJ-PATCH solves a major bottleneck, showing that formal safety refinement can be achieved efficiently on standard CPUs, not just high-end GPUs.
Future Path: This work provides a foundational path for deploying "formally guaranteed safety" in complex, long-term robotic deployments (e.g., search-and-rescue, autonomous logistics) where the environment is unpredictable.

Limitations noted by authors: The approach currently relies on idealized sensors (simulated perception), requires a known dynamics model (with bounded uncertainty), and is limited by the scalability of dynamic programming (currently effective up to ~4D state spaces). Future work aims to integrate noisy sensor data and merge with deep learning for higher dimensions.