⚡ electrical engineering

Extending and Unifying the Fundamental Tasks of Hamilton-Jacobi Reachability Analysis

This paper introduces the generalized reach-avoid (GRA) task as a unifying primitive that extends Hamilton-Jacobi Reachability analysis to solve a broader class of fundamental and composite tasks, including those from timed temporal logic, while also providing a comprehensive PDE perspective for representing regular solutions.

Original authors: Dylan Hirsch, William Sharpless, Donggun Lee, Sylvia Herbert

Published 2026-08-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dylan Hirsch, William Sharpless, Donggun Lee, 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

In the world of robotics and autonomous vehicles, safety is not just a feature; it is the foundation. Engineers must design systems that can navigate a chaotic world filled with moving obstacles, unpredictable weather, and mechanical failures, all while reaching a specific destination. To do this, they rely on a mathematical framework known as Hamilton-Jacobi reachability analysis. Think of this framework as a way to calculate the "safe zone" for a machine. It asks a simple but profound question: given the worst possible interference from the environment, can the machine still control itself to reach its goal without crashing? By answering this, the system can generate a controller that keeps the machine safe no matter what happens. For decades, researchers have used this method to solve specific types of problems, such as reaching a target, avoiding an obstacle, or staying within a safe area until a deadline. However, these problems were often treated as separate, distinct challenges, each requiring its own unique mathematical setup.

A team of researchers at the University of California, San Diego, and North Carolina State University has now unified these separate challenges into a single, more powerful tool. They introduced a new concept called the generalized reach-avoid task. This new approach does not just solve the old problems; it combines them into one flexible framework that can handle situations where a machine has multiple ways to succeed. In the past, if a drone needed to either land on a pad or stay near a communication tower, engineers had to treat these as two different scenarios. The new method recognizes that these are actually two sides of the same coin. It allows the system to calculate a single safety map that accounts for the possibility of reaching a target, staying in a safe zone, or arriving at a specific location at a specific time, all simultaneously.

The researchers demonstrated that this unified task is not just a theoretical curiosity but a practical necessity for complex, real-world scenarios. They showed that by using this single framework, they could solve problems that were previously difficult or impossible to address with standard methods. For instance, they tackled a scenario involving a drone flying over water with strong, unpredictable winds. The drone had two options to survive a ten-second gust: it could fly to a landing pad, or it could stay within a safe distance of a communication antenna for the entire duration. Using older methods, engineers would have tried to calculate the safety for landing and the safety for staying put separately, then combined the results. The researchers proved this approach was flawed; the combined result was often incorrect because the two strategies interact in complex ways. By using their new generalized method, they calculated the true safety zone, showing exactly where the drone could start and still survive, regardless of which path it chose.

This unification also opens the door to solving tasks that involve time-sensitive logic, which is crucial for robots working in warehouses or hospitals. The researchers applied their method to a scenario with two robots tasked with picking up packages. One robot was faster but had a shorter window to act, while the other was slower but had more time. The goal was for either robot to reach the shelf without hitting walls or each other. The new framework allowed the system to decompose this complex, timed requirement into a sequence of simpler steps. It effectively told the slower robot to move out of the way so the faster one could pass, ensuring the overall mission succeeded. This kind of dynamic decision-making, where the system adapts its strategy based on time and constraints, is now computable using their single, unified equation.

Furthermore, the team showed that this new task is the natural mathematical building block for the entire field. They proved that almost any regular solution to the underlying safety equations can be represented by this generalized task. This means that instead of having a toolbox full of different, specialized equations for different types of safety problems, engineers can now rely on one master equation. They simply adjust the parameters to define the specific goal, the obstacles, and the time limits. This simplification is significant because it provides a consistent way to handle systems that change behavior over time, such as a medical infusion pump that switches between active treatment and rest periods. By breaking the problem into smaller time segments and stitching the solutions together, the method ensures safety even when the rules of the system change abruptly.

The work does not solve the problem of high-dimensional complexity, where the number of variables makes calculations too heavy for current computers, but it provides a clearer path forward. The researchers established that their method works under very general conditions, requiring only that the system's behavior is continuous and predictable within small steps. They validated their findings through rigorous mathematical proofs and numerical simulations, showing that the new approach is both theoretically sound and practically useful. By extending and unifying the fundamental tasks of reachability analysis, this research offers a more robust and flexible way to ensure that autonomous systems can navigate the real world safely, efficiently, and intelligently.

Technical Summary: Extending and Unifying the Fundamental Tasks of Hamilton-Jacobi Reachability Analysis

Problem Statement

Hamilton-Jacobi Reachability (HJR) analysis is a foundational framework for safety-critical control, rooted in differential game theory. Traditionally, HJR addresses five canonical finite-horizon tasks: (I) Terminal-set, (II) Reach, (III) Avoid, (IV) Constrained Terminal-set, and (V) Reach-avoid. While these tasks are solved via Hamilton-Jacobi Terminal Value Problems (HJ-TVPs) sharing a common partial differential equation (PDE) structure, they are treated as distinct primitives with specific boundary conditions.

A significant limitation in the existing framework is that complex, composite tasks—such as those specified by temporal logic or involving piecewise-continuous dynamics—often cannot be solved by simply taking the maximum or minimum of the value functions of these canonical tasks. The algebraic relationship between performance functionals does not generally hold for their corresponding value functions due to the underlying minimax nature of the differential game. Consequently, there is a need for a more general primitive that unifies these tasks, allows for rigorous value function decomposition of composite problems, and provides a complete characterization of the solutions to the canonical HJ-PDE.

Methodology

The authors introduce the Generalized Reach-Avoid (GRA) task, defined by a tuple $(r, q, \ell; T)$ , where:

$r(x,t)$ defines a target tube (a moving goal).
$q(x,t)$ defines a constraint tube (a safety region).
$\ell(x)$ defines a terminal set (a goal at the final time $T$ ).
$T$ is the terminal time.

The GRA task requires the system to satisfy either:

Reach the target tube $r$ by time $T$ while remaining in the constraint tube $q$ until the reach time; OR
Be in the terminal set $\ell$ at time $T$ while remaining in the constraint tube $q$ until $T$ .

The performance functional $J_{GRA}$ is formulated to capture this "OR" logic. The value function $V_{GRA}$ is then characterized as the unique continuous viscosity solution to a specific HJ-TVP. Crucially, the underlying Hamilton-Jacobi PDE for the GRA task is identical to that of the canonical Reach-Avoid task, but the terminal boundary condition is generalized to incorporate the terminal set function $\ell$ .

The methodology further establishes a value function decomposition theorem (Theorem 1). This theorem demonstrates that the value function of a composite task—consisting of an upstream GRA task followed by a downstream task—can be computed exactly by modifying the terminal set function of the upstream GRA task to include the value function of the downstream task evaluated at the switching time.

Key Contributions

Introduction of the GRA Task: The paper defines the GRA task as a fundamental primitive that strictly extends and unifies the five canonical HJR tasks. By setting specific parameters (e.g., $r = -\infty$ or $q = \infty$ ), the canonical tasks (I) through (V) are recovered as special cases of the GRA formulation.
Unified HJ-TVP Formulation: The authors show that the value function for the GRA task is the unique viscosity solution to an HJ-TVP where the PDE remains the standard canonical form, but the terminal condition is relaxed to $v(x, T) = \min\{q(x, T), \max\{r(x, T), \ell(x)\}\}$ . This unifies the mathematical treatment of all five canonical tasks under a single boundary condition structure.
Value Function Decomposition (Theorem 1): A critical theoretical result establishes that the value function of a composite task (GRA followed by an arbitrary downstream task) can be represented as a single GRA value function. This is achieved by updating the terminal set function $\ell$ to $\tilde{\ell}(x) = \max\{\ell(x), V_{downstream}(x, T)\}$ . This enables the computation of value functions for complex, timed tasks (e.g., timed temporal logic) without solving separate, non-commuting optimization problems.
Completeness of Representation (Corollary 2): The paper proves that every sufficiently regular viscosity solution of the canonical HJ-PDE can be represented as the value function of a GRA task with an appropriately chosen terminal set function $\ell$ . This suggests that the GRA formulation is "complete" in the sense that it can represent the full solution space of the canonical PDE, whereas individual canonical tasks (like Reach-Avoid) represent only specific slices of that space.
Handling Piecewise-Continuous Dynamics: The authors propose an iterative algorithm (Algorithm 1) to compute GRA value functions for systems with dynamics that are piecewise-continuous in time (e.g., switching systems). This is achieved by solving the GRA-TVP sequentially over continuous intervals and using the value function at the switching time as the new terminal set function for the subsequent interval.

Results and Examples

The paper validates the theoretical framework through three examples:

Reach-Avoid or Always-Avoid: A drone scenario where the task is to either reach a landing pad or maintain communication indefinitely. The results demonstrate that the true value function (computed via GRA) differs strictly from the maximum of the individual Reach-Avoid and Avoid value functions, proving the necessity of the unified approach.
Timed Temporal Logic: A multi-robot warehouse scenario involving a disjunction of timed reach-avoid constraints. The decomposition theorem allows the complex specification to be solved by chaining GRA tasks, effectively handling the temporal logic structure.
Piecewise-Continuous Dynamics: A pharmacology model involving drug infusion with on/off cycles. The iterative algorithm successfully stitches value functions across discontinuities in the system dynamics, demonstrating the utility of the terminal set function as a "port" for dynamic programming.

Significance

The paper claims that the GRA task serves as a natural and unifying primitive for HJR from both a task specification and a PDE perspective.

Theoretical Unification: It resolves the fragmentation of the five canonical tasks into a single framework, establishing uniform theoretical results (existence, uniqueness, and continuity) under weaker assumptions than previous separate studies.
Practical Utility: It enables the rigorous computation of value functions for composite tasks that were previously difficult to address, particularly those involving timed temporal logic or switching dynamics.
PDE Completeness: It provides a converse to standard existence theorems, showing that the GRA formulation can represent any sufficiently regular solution to the canonical HJ-PDE, thereby "completing" the set of solvable tasks within the HJR framework.

The work does not claim to solve the curse of dimensionality inherent in HJR but provides a more robust and flexible mathematical foundation for applying HJR to increasingly complex control problems.