⚡ electrical engineering

Computing Sound Lower and Upper Bounds on Hamilton-Jacobi Reach-Avoid Value Functions

This paper presents an algorithm for computing sound upper and lower bounds on Hamilton-Jacobi value functions to guarantee the over-approximation of backward reachable sets and under-approximation of reach-avoid sets, addressing the lack of error guarantees in classical grid-based methods through a refinement process that iteratively tightens these bounds.

Original authors: Ihab Tabbara, Eliya Badr, Hussein Sibai

Published 2026-03-31

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ihab Tabbara, Eliya Badr, Hussein Sibai

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 the captain of a spaceship trying to navigate through a dangerous asteroid field (the Failure Set) to reach a safe harbor (the Target Set). Your goal is to figure out exactly which starting positions in space guarantee that you can reach the harbor without crashing, no matter how the asteroids move.

In the world of robotics and self-driving cars, this is called Reachability Analysis. Scientists use complex math (specifically something called Hamilton-Jacobi equations) to draw a map of "Safe Zones" and "Danger Zones."

However, there's a big problem with the old way of doing this: The Map is Blurry.

The Problem: The "Pixelated" Map

To solve these complex math problems, computers have to break the continuous universe into a grid of tiny squares (like a pixelated image).

The Old Way: The computer calculates the safety of the center of each square. If the center is safe, it assumes the whole square is safe.
The Flaw: This is like looking at a low-resolution photo. A square might look green (safe) because its center is safe, but its edges might be touching a red (dangerous) asteroid. The old methods don't account for this "pixelation error." They might tell you a spot is safe when it's actually a death trap, or vice versa.

The Solution: A "Double-Check" System

This paper introduces a new, super-strict method that doesn't just guess; it proves safety with a margin of error. Think of it as building a Double-Walled Fortress around your calculations.

Instead of calculating one single value for a grid square, the authors' algorithm calculates two values for every square:

The "Best-Case" Estimate (Upper Bound): "Even if we get incredibly lucky, this is the best safety score we can hope for."
The "Worst-Case" Estimate (Lower Bound): "Even if we get incredibly unlucky, this is the worst safety score we will face."

The Magic Rule:

If the Worst-Case is still positive (safe), then the entire square is 100% safe.
If the Best-Case is negative (unsafe), then the entire square is 100% dangerous.
If the Best-Case is safe but the Worst-Case is dangerous, the square is "Unclassified" (the gray zone).

The "Zoom-In" Refinement

What happens when a square is "Unclassified"? The old methods would just guess or stop. This paper uses a clever Refinement Algorithm.

Imagine you are looking at a blurry photo of a cliff edge. You can't tell if the person is safe or about to fall.

The Algorithm's Move: It takes that specific blurry square and splits it into four smaller squares. It then re-calculates the safety for these tiny new pieces.
The Result: By zooming in only on the confusing edges, the algorithm creates a map that is incredibly detailed where it matters (the edges of danger) but stays coarse where everything is clearly safe or clearly dangerous. This saves massive amounts of computer power.

Why "Stopping Early" Matters

Usually, to get a perfect answer, a computer has to run its calculations until it stops changing (convergence). This takes forever.

The Paper's Trick: The authors figured out a way to stop the calculation early (like pausing a video game before the level is fully finished) and still get a guaranteed correct answer. They add a "safety buffer" (a correction term) to account for the fact that they stopped early. It's like saying, "I haven't finished counting the money, but I know I have at least $100, so I'm safe."

Real-World Impact

The authors tested this on two scenarios:

A Dubins Car: A robot car that can only move forward and turn (like a real car).
3D Evasion: A plane trying to dodge a missile.

They compared their method to existing tools. The existing tools often made mistakes (labeling dangerous spots as safe) or took a long time to get a rough answer. The new method:

Never lies: It guarantees that if it says "Safe," you are safe.
Is faster: It finds larger safe zones in less time than the competition.
Adapts: It automatically zooms in on the tricky parts of the map.

Summary Analogy

Think of the old method as a weather forecast that says, "It might rain." It's vague and risky for a pilot.
This new method is like a military-grade radar that draws a perfect, shrinking circle around the storm. It tells you exactly where the storm definitely is and where it definitely isn't. If there's a tiny sliver of uncertainty, it instantly zooms in on that sliver until the uncertainty disappears.

This ensures that self-driving cars, surgical robots, and drones can navigate complex environments with mathematical certainty, not just a good guess.

1. Problem Statement

Hamilton-Jacobi (HJ) reachability analysis is a standard technique for verifying safety and synthesizing controllers for nonlinear systems. It computes the Backward Reachable Set (BRS) (states from which a failure set cannot be avoided) and the Reach-Avoid Set (RAS) (states from which a target can be reached while avoiding failure).

The Core Challenge:
Existing numerical methods solve the HJ partial differential equation (PDE) on a discretized grid. However, these methods generally:

Do not explicitly account for discretization errors introduced by gridding the continuous state space.
Do not guarantee that the computed sets are sound approximations. Specifically, they cannot guarantee that the computed BRS is an over-approximation (ensuring no unsafe state is missed) or that the computed RAS is an under-approximation (ensuring no safe state is falsely claimed).
Often require the value iteration algorithm to converge to a fixed point, which can be computationally expensive or impossible to verify within a finite time budget.

2. Methodology

The authors propose a framework to compute sound upper and lower bounds on the HJ value function ( $V_\gamma$ ) for discrete-time nonlinear control systems. These bounds guarantee the soundness of the resulting reachable sets.

A. Discrete Abstraction and Grid Construction

The continuous state space $\mathcal{X}$ is discretized into a finite grid of cells $S$ .
A non-deterministic transition relation $\Delta$ is constructed. For a cell $s$ and control $a$ , the set of successor cells $\Delta(s, a)$ is an over-approximation of the actual reachable states. This is achieved using the Lipschitz constant of the system dynamics ( $L_f$ ) to bound the error between the cell center and any point within the cell.
Similarly, the failure function $l(x)$ and reward function $r(x)$ are bounded within each cell using their respective Lipschitz constants ( $L_l, L_r$ ) to create cell-wise lower ( $\underline{l}, \underline{r}$ ) and upper ( $\bar{l}, \bar{r}$ ) bounds.

B. Bounding the Value Function

The authors define two new value functions over the discrete state space $S$ :

Upper Bound ( $\bar{V}_\gamma$ ): Represents the "best-case" scenario for the system (optimistic about safety/reachability). It uses the maximum over successor states in the transition relation.
Lower Bound ( $\underline{V}_\gamma$ ): Represents the "worst-case" scenario (pessimistic). It uses the minimum over successor states.

These functions satisfy specific Bellman equations. The authors prove that the associated Bellman operators are contraction mappings, ensuring unique fixed points.

C. Handling Early Termination (Soundness Guarantees)

A key innovation is handling the case where value iteration is stopped before convergence (early stopping).

Lower Bound Correction: When stopping early, the algorithm introduces a correction term derived from the minimum change in the value function between iterations ( $\delta_k$ ). This term ensures that the computed lower bound remains a valid under-approximation of the true value function, even if the iteration hasn't converged.
Upper Bound Monotonicity: The algorithm initializes the upper bound iteration such that the sequence is monotonically decreasing, guaranteeing that any intermediate iterate is a valid upper bound.

D. Adaptive Refinement Algorithm

If the computed bounds for a cell are not tight enough to classify it as strictly safe (in RAS) or strictly unsafe (in BRS), the cell is marked as unclassified.

The algorithm adaptively splits these unclassified cells (specifically along their longest dimension) into smaller sub-cells.
The value iteration and bounding process is re-run on the refined grid.
This process repeats until all cells are classified or a minimum resolution ( $\epsilon_{min}$ ) is reached.

3. Key Contributions

Sound Bounds on HJ Value Functions: The paper presents an algorithm that computes provable upper and lower bounds on the HJ value function, explicitly accounting for discretization errors. This guarantees that:
- The computed BRS is a sound over-approximation (no unsafe state is classified as safe).
- The computed RAS is a sound under-approximation (no safe state is classified as unsafe).
Early Termination Guarantees: The method provides sound bounds even when value iteration is terminated before reaching a fixed point, utilizing a correction term for the lower bound.
Adaptive Refinement: A novel refinement algorithm that locally splits unclassified cells to tighten bounds, avoiding the computational cost of uniformly refining the entire grid.
Quantitative Safety Margins: Unlike binary classification tools, this method provides a value function that quantifies the "safety margin" or degree of specification satisfaction.

4. Experimental Results

The authors validated their approach on two case studies:

Dubins Car: A 3D state system (position + heading) avoiding a cylindrical obstacle and reaching a target.
3D Evasion: A 3D aircraft pursuit-evasion scenario.

Key Findings:

Comparison with Existing Tools: Compared against the standard HJ PDE toolbox [25] and the symbolic control tool ROCS 2.0 [19]:
- The standard HJ toolbox produced under-approximations of the unsafe set (mislabeled some unsafe states as safe) at coarse grid resolutions.
- The proposed method computed a larger Reach-Avoid Set (RAS) than ROCS 2.0 while maintaining soundness guarantees, often with competitive or better runtimes.
- The proposed method provided soundness guarantees that the standard HJ toolbox lacked.
Refinement Effectiveness: The adaptive refinement successfully classified unclassified cells, expanding the known safe and unsafe regions without requiring a globally fine grid.
Performance: Runtime grew almost linearly with the number of grid cells, though the total number of cells grew exponentially with refinement iterations. The method scales reasonably well for the tested dimensions.

5. Significance

This work addresses a critical gap in formal verification and control synthesis: the lack of rigorous guarantees in discretized HJ analysis.

Safety-Critical Applications: For systems like autonomous vehicles and surgical robots, it is unacceptable to falsely classify an unsafe state as safe. This method guarantees that the computed "safe" set is truly safe (under-approximation of RAS) and the "unsafe" set is truly unsafe (over-approximation of BRS).
Efficiency vs. Accuracy: By using adaptive refinement and early-stopping corrections, the method achieves high accuracy without the prohibitive computational cost of ultra-fine uniform grids or infinite iteration convergence.
Generalizability: The framework applies to general nonlinear systems with Lipschitz continuous dynamics, making it a robust tool for safety verification in complex control environments.

In summary, the paper transforms HJ reachability from an approximate numerical method into a formally sound verification tool that provides rigorous bounds on safety and reachability, even under computational constraints.