⚡ electrical engineering

An Update to the Level Set Theorems in Hamilton-Jacobi Reachability Analysis

This paper provides a technical update to the Level Set Theorems in Hamilton-Jacobi Reachability Analysis by specifying additional criteria required for these theorems to hold, thereby refining the interpretation of value functions for safety-critical control tasks.

Original authors: Dylan Hirsch, William McEneaney, Jaime Fisac, Claire Tomlin, Sylvia Herbert

Published 2026-07-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Dylan Hirsch, William McEneaney, Jaime Fisac, Claire Tomlin, 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 the captain of a spaceship trying to navigate through a dense asteroid field. You have a steering wheel (the controller) and a mischievous ghost (the disturbance) that can tug at your ship in unpredictable ways. Your goal is to reach a safe harbor without crashing into any rocks. In the world of robotics and engineering, this isn't just a sci-fi story; it's a daily challenge for self-driving cars, drones, and surgical robots. To solve this, scientists use a powerful mathematical tool called Hamilton-Jacobi Reachability. Think of this tool as a super-smart weather map that doesn't just show rain, but predicts every possible future path your ship could take, accounting for both your best steering and the ghost's worst tricks. This map tells you exactly where you can start your journey and still be guaranteed to survive.

However, reading this map requires a very specific set of instructions, known as "Level Set Theorems." These theorems are like the legend on a treasure map; they tell you how to translate the mathematical numbers on the page into real-world safety zones. For years, the community has used a specific legend to interpret these maps. But recently, a group of researchers realized that the old legend had some typos and missing footnotes. If you followed the old instructions too literally, you might think you were safe when you were actually doomed, or vice versa. This paper is a crucial update to that legend, fixing the errors so that the map tells the truth.

The Paper's Mission: Fixing the Map's Legend

This paper, titled "An Update to the Level Set Theorems in Hamilton-Jacobi Reachability Analysis," is a technical correction to the rules we use to interpret safety maps. The authors, a team of mathematicians and engineers, argue that the standard way of reading these maps has been slightly off, leading to confusion about who actually wins the game between the controller and the disturbance.

The core of the paper is a proof that the old rules fail under certain conditions and that a new, stricter set of rules is required to get the right answer. They don't just suggest this; they provide a rigorous mathematical proof and concrete counterexamples to show exactly where the old logic breaks.

Here is what they found, broken down into the story of the game:

1. The "Ghost" Needs to Be a Shape-Shifter (The Convexity Rule)

In the old version of the game, the rules assumed that the "ghost" (the disturbance) could only pull the ship in a straight line or a smooth curve. But in reality, the ghost might be able to pull in jagged, unpredictable ways.

The authors discovered that if the ghost's possible moves aren't "convex" (a fancy word meaning the ghost can't just jump between two extreme options without passing through the middle), the old map legend fails.

The Counterexample: They created a scenario where the ghost can only pull the ship left (-1) or right (+1), but never stay still or pull in between. Using the old rules, the map said the ship was doomed to hit a specific point. But when they actually played the game, the controller could dodge the ghost perfectly every time. The old map was wrong because it didn't account for the ghost's inability to "smooth out" its moves.
The Fix: The new theorem requires that the ghost's possible moves form a convex set. If they don't, you can't trust the simple "zero line" on the map to tell you who wins.

2. The Target Must Be an Open Door (The Target Set Rule)

The second major fix concerns the "goal." Imagine the safe harbor is a specific point on a map.

The Mistake: Some previous rules assumed the safe harbor was a closed circle (including the very edge). They claimed that if your ship touched the edge, you had won.
The Reality: The authors proved that because the ghost has an "instantaneous advantage" (it can react to your move the split second you make it), touching the exact edge of a closed target isn't enough to guarantee a win. The ghost can always push you off the edge at the very last micro-second.
The Fix: The new rules state that for the controller to be guaranteed a win, the target must be an open set (like a door that is slightly ajar, not a closed wall). If the target is closed, the map might say you are safe when you are actually on the brink of failure.

3. The New, Corrected Legend

The paper provides a new, generalized theorem (Theorem 1) that acts as the corrected legend. It says:

If the value on the map is strictly greater than zero, you are safe.
If the value is less than or equal to zero, you are in danger.

This seems simple, but the paper proves that this specific combination of "strictly greater" and "less than or equal" is the only way to get the right answer when the ghost has the advantage. The old rules often mixed these up, leading to dangerous errors.

Why This Matters

You might wonder, "If the old rules were wrong, why did we use them?" The authors explain that the errors were subtle. In many simple, smooth scenarios, the old rules happened to work by accident. But in complex, real-world situations where the system is jerky or the target is a hard edge, the old rules give false confidence.

By fixing these technicalities, the paper ensures that when engineers design safety systems for robots or cars, the mathematical guarantees they rely on are actually true. It's not about inventing a new way to drive; it's about making sure the GPS doesn't tell you to drive off a cliff just because the math was slightly off. The authors have cleared up the confusion, proving that for the controller to win, the target must be open, the ghost's moves must be convex, and the safety zone must be strictly positive.

Technical Summary: An Update to the Level Set Theorems in Hamilton-Jacobi Reachability Analysis

Problem Statement
Hamilton-Jacobi Reachability (HJR) is a established framework for synthesizing controllers for safety-critical nonlinear systems under uncertainty, typically formulated as differential games. The process involves converting a qualitative control task (e.g., obstacle avoidance or goal reaching) into a "game of degree," solving the associated Hamilton-Jacobi (HJ) partial differential equation to obtain a value function, and finally interpreting this value function to define the set of safe or unsafe initial states. This final step relies on "Level Set Theorems."

The authors identify that existing literature contains technical errors and ambiguities regarding these theorems, specifically concerning the conditions under which the value function's level sets correctly correspond to the winning sets of the game. These issues have caused confusion in the community, particularly regarding the interpretation of states lying exactly on the zero level set of the value function. The paper posits that previous formulations often overlook necessary topological and convexity assumptions, leading to incorrect characterizations of safety and reachability sets.

Methodology
The paper employs a rigorous mathematical approach rooted in differential game theory and topology. The authors:

Formalize the Game Setup: They define a finite-horizon differential game with a controller player and an adversarial disturbance player. The system dynamics are governed by $\dot{x} = f(x, a, b)$ , where $a$ and $b$ are control and disturbance signals, respectively. The disturbance player utilizes non-anticipative strategies.
Establish Assumptions: The analysis relies on five key assumptions:
- Standard continuity and compactness of dynamics and control sets (Assumptions 1-3).
- Convexity of the disturbance dynamics: For every state and control, the set of possible dynamics vectors induced by the disturbance set $B$ must be convex (Assumption 4).
- Closedness of failure modes: The set of failure trajectories $F(t)$ must be closed in the space of continuous trajectories (Assumption 5).
Derive a General Theorem: They prove a generalized Level Set Theorem (Theorem 1) that links the value function $v(x,t)$ to the safe ( $L(t)$ ) and unsafe ( $G(t)$ ) sets. The theorem establishes that $L(t) = \{x \mid v(x,t) > 0\}$ and $G(t) = \{x \mid v(x,t) \leq 0\}$ , provided the functional $J$ defining the failure modes is continuous and bounded.
Construct Counterexamples: To demonstrate the necessity of the new assumptions, the authors construct two specific counterexamples:
- Lack of Convexity: An obstacle avoidance game where the disturbance set $B$ is non-convex (discrete points). They show that without Assumption 4, a state on the zero level set ( $v=0$ ) may not belong to the unsafe set, contradicting standard interpretations.
- Closed Target Sets: A goal-reaching game where the target set is closed rather than open. They demonstrate that without Assumption 5 (which implies targets should be open), a state on the zero level set may not belong to the safe set, again contradicting standard interpretations.
Proof Techniques: The proofs utilize Filippov's Lemma to establish the existence of measurable disturbance signals, and topological arguments involving the compactness of trajectory sets and non-anticipative disturbance plans (using Tychonoff's Theorem and lexicographic ordering) to prove the main theorem.

Key Contributions

Correction of Technical Errors: The paper identifies and corrects technical flaws in prior Level Set Theorems found in the literature, specifically pointing out the omission of the convexity condition on dynamics (Assumption 4) and the requirement for closed failure sets (Assumption 5).
General Level Set Theorem: The authors provide a unified, concise theorem applicable to all finite-horizon games of interest in HJR, clarifying the strict inequality for the safe set ( $v > 0$ ) and the non-strict inequality for the unsafe set ( $v \leq 0$ ).
Clarification of Zero-Level Set Ambiguity: Through counterexamples, the paper explains why points on the zero level set of the value function are ambiguous when standard assumptions are violated. In such cases, the outcome of the game (win/loss) for these specific points cannot be determined solely by the value function being zero; the controller may win for some points on the boundary while the disturbance wins for others.
Topological Rigor: The work bridges the gap between HJR and topological arguments used in viability theory and semi-permeable barriers, offering a more robust theoretical foundation for interpreting value functions.

Results
The primary result is Theorem 1, which rigorously defines the safe and unsafe sets based on the value function under the specified assumptions. The paper demonstrates that:

If the disturbance dynamics are not convex (e.g., discrete disturbance sets), the standard interpretation that $v(x,t) \leq 0$ implies the state is unsafe fails for points on the boundary.
If the target set is closed (violating the requirement for open targets in reachability games), the standard interpretation that $v(x,t) > 0$ implies the state is safe fails for points on the boundary.
Under the corrected assumptions, the value function provides a precise characterization of the winning sets, with the disturbance player holding an "instantaneous advantage" that necessitates the strict/non-strict inequality split.

Significance
The authors state that while these technical issues may not immediately impact practitioners who rely on existing software tools, their theoretical resolution is "interesting and nuanced." The paper aims to clear up confusion in the community caused by previous technical errors. By providing a corrected general theorem and explaining the origin of discrepancies via counterexamples, the work ensures that the theoretical underpinnings of Hamilton-Jacobi Reachability are sound. This is particularly relevant for researchers developing learning-based HJR methods or extending the framework to complex, layered tasks, as it clarifies the precise conditions required for the value function to correctly certify safety and liveness.

The Paper's Mission: Fixing the Map's Legend

1. The "Ghost" Needs to Be a Shape-Shifter (The Convexity Rule)

2. The Target Must Be an Open Door (The Target Set Rule)

3. The New, Corrected Legend

Why This Matters

More like this