CS Paper Radar

Exact Decomposition of Value Functions for Two-Player Games in Hamilton-Jacobi Reachability

Dylan Hirsch, William Sharpless, Sylvia Herbert

eess.SY ·submitted 2026-08-27 19:42 UTC · v2

Abstract

Hamilton-Jacobi reachability (HJR) is an important framework in safe control theory. HJR provides theoretical tools and numerical methods to obtain value-functions for tasks involving target-reaching and obstacle-avoidance. A recent work proposed an algebraic framework to scale to complex, composite tasks via decomposing the value functions of the composite tasks into value functions for the fundamental tasks traditionally studied in HJR, all in the one-player setting. Many of these decomposition results, however, do not directly translate to the two-player setting. In this technical note, we nevertheless show that one of the previous work's key results for analyzing various tasks involving reaching multiple targets while obeying constraints still holds in the two-player setting, so long as a critical monotonicity assumption is satisfied. In particular, we detail the analogous result and its proof (which structurally differs from the one-player case), we show via a counter-example what can go wrong if this monotonicity assumption is not satisfied, and we show how the analysis of a variety of tasks can be performed using this result. Such tasks include sequential and any-order multi-target-reaching tasks under constraints. We note that, whereas the prior work considered discrete-time, infinite-horizon tasks, which are more standard in reinforcement learning, we here consider continuous-time, finite-horizon tasks, which are more standard in HJR.

Closest papers

Nearest neighbours by meaning across the whole index.

Hamilton-Jacobi Reachability for Hybrid Systems: Unified Goal-Driven Control with Safety Guarantees

cs.RO eess.SY ·2026-09-15 ·Javier Borquez, Shuang Peng, Somil Bansal
published similarity 0.67
Abstract

Hybrid dynamical systems provide a powerful modeling framework for robotic systems, particularly in contact-rich environments. However, ensuring safety and performance in such systems remains challenging due to the intricate coupling between continuous dynamics and discrete mode transitions. In this work, we extend classical Hamilton-Jacobi (HJ) reachability analysis, a formal verification method for continuous-time nonlinear systems, to hybrid dynamical systems. Our framework characterizes safe sets for hybrid systems through a generalized value function defined over both discrete and continuous states while accounting for control constraints and model uncertainty. We additionally provide a numerical algorithm to compute this value function. Building on these safe sets, we propose two different mechanisms to integrate performance objectives. First, we introduce a hybrid least-restrictive safety filter that intervenes on both the discrete and continuous components of a nominal controller only when necessary to avoid unsafe states, thereby preserving nominal behavior whenever possible. Second, we formulate and compute hybrid backward reach-avoid tubes, enabling the simultaneous enforcement of safety and goal-reaching behavior, an extension not previously addressed within hybrid HJ reachability. This enables the synthesis of continuous and discrete control policies that guarantee both safety and task completion. We validate our framework through simulation studies and real-world experiments on a quadrupedal robot, demonstrating its effectiveness in hybrid mode planning and safety-critical applications.

0.60

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

eess.SY ·2026-08-18 ·Dylan Hirsch, William Sharpless, Donggun Lee, Sylvia Herbert
similarity 0.65
Abstract

In this work, we introduce the generalized reach-avoid (GRA) task, which both extends and unifies the canonical tasks of Hamilton-Jacobi Reachability (HJR). We show that the GRA not only serves as a common primitive in this class of fundamental tasks, but also strictly extends the fundamental tasks that can be solved with HJR. Moreover, the GRA formulation enables one to compute the value functions of certain composite tasks, including ones from timed temporal logic, by decomposing the value function of the composite task into value functions of GRA tasks. We additionally show that the GRA is also a natural primitive to consider from a PDE perspective, as it can be used to represent all sufficiently regular solutions of the HJ-PDE that is canonical to HJR. Collectively, the results in this work show the theoretical and practical utility of this task within the increasingly important framework of HJR.

0.44

Reliable Conditioned Hamilton-Jacobi Reachability via Subsolution Learning on Exact Local Windows

eess.SY cs.RO ·2026-11-14 ·Seunghwan Jang, Wei Xiao
similarity 0.64
Abstract · 27 pages, 10 figures, 10 tables

Hamilton-Jacobi (HJ) reachability computes the maximal safe set and a safety filter for a given obstacle configuration, but it must be re-solved whenever the obstacles change, which a deployed robot cannot afford. Learning a single value function conditioned on the obstacle set removes the re-solve, yet it sharpens the central weakness of learned reachability: one network must now cover a whole family of safety problems, and its approximation error carries no preferred sign, so rare obstacle configurations silently produce false-safe states. To address these challenges, we present a conditioned reachability model designed so that the remaining error falls on the conservative side. Specifically, our method caps the obstacle margin, which makes the value function provably local, in the sense that obstacles farther than a known threshold cannot affect it, so the model reads only a body-frame window, trains on small scenes, and transfers to scenes of any size with millisecond per-scene preparation. Moreover, the output structure builds the value bound into the model. By training with counterexample mining over the finite-dimensional window configuration space, we maximize the claimed safe volume subject to the HJ inequality, so the learned set grows toward the true safe set from the conservative side. Across all tested obstacle settings, ours is the only method that combines recovery comparable to per-scene DeepReach training with near-zero rollout collisions. We also extend the method to a 10D quadrotor, again with markedly lower collision rates than the baselines.

0.19

Learning Reachability-Based Safety Representations for Real-Time Robot Navigation in Unknown and Dynamic Environments

cs.RO cs.LGeess.SY ·2026-10-12 ·Bojan Derajić
similarity 0.63
Abstract

Safe robot navigation in unknown, dynamic environments requires more than geometric collision checking: a robot still far from an obstacle may be unable to avoid it because of its speed, orientation, or the obstacle's motion. Hamilton--Jacobi (HJ) reachability analysis captures this in a value function whose sign separates states that admit a safe continuation from those where collision is unavoidable, but computing it online for every newly observed environment is too expensive. This dissertation trains neural implicit representations offline on reachability solutions to give optimization-based controllers this information in real time. Since the value function never exceeds the constraint, it equals a directly computed constraint, such as a signed distance, minus a nonnegative dynamics correction. Learning only this correction keeps represented obstacles outside the predicted safe set despite approximation errors. The first two of five methods use the learned function as a terminal constraint in model predictive control, for static local environments and predicted obstacle motion. The next two use it as a barrier candidate in control barrier function safety filters, for static environments and, through pairwise barriers in relative coordinates, for a varying number of moving obstacles. Simulations and hardware experiments on ground and aerial robots show better collision avoidance than geometric and hand-designed baselines, especially for short horizons and moving obstacles. The fifth method replaces the grid-based offline solver, which limits the first four to low-dimensional models. For control-affine dynamics with polytopic inputs, the HJ Hamiltonian is maximized at a vertex, so a parallelizable tree search over vertex inputs can generate training labels. With a loss from the HJ variational inequality, these labels yield barrier candidates for systems with up to 13 states.

0.10

Unified Overview of Safety Certificate Functions: Techniques from Hamilton--Jacobi Reachability and Control Barrier Functions

cs.RO eess.SY ·2026-11-05 ·Hao Wang, Max Cohen, Zeyuan Feng, Donggeon David Oh, Oswin So +7 more
surveybenchmark similarity 0.62
Abstract

Safety is a central concern in modern autonomous systems. Safety certificates---functions whose existence guarantees that a system meets its safety specification---have long been used as a principled tool for rigorously reasoning about safety. Methods for synthesizing such certificates are scattered across research areas, with little guidance on when to use a particular approach. This tutorial provides a holistic treatment of safety certificate synthesis centered on two widely used families: Hamilton--Jacobi (HJ) reachability analysis and control barrier functions (CBFs). For each family of methods, we first introduce its general formulation, along with classical and learning-based tools for certificate synthesis. Next, we introduce two benchmark problems consisting of vehicle systems of differing complexity to assess the certificate quality of different synthesis methods and their effectiveness in safety-critical control. We use these benchmarks to compare various methods and provide practical guidance for selecting an approach.

0.24

Geometry-Evolving Barrier Functions for Safety Evaluation in Dynamic Environments

eess.SY ·2026-11-05 ·Zhi Zhang, Francesco Belardinelli, Alessandro Abate
similarity 0.62
Abstract

Autonomous systems operating in dynamic environments often involve multiple interacting agents, giving rise to high-dimensional safety evaluation problems. Hamilton--Jacobi (HJ) reachability provides rigorous finite-horizon safety guarantees, but solving a global HJ partial differential equation (PDE) over the entire state space leads to prohibitive computational complexity. In this paper, we introduce Geometry-Evolving Barrier Functions (GEBFs), a novel representation for dynamic safety evaluation that propagates local safety geometry of the solution to a terminal-value HJ PDE. By evolving the value, gradient, and curvature information along a Hamiltonian-induced reference trajectory, GEBFs provide a compact representation of the local HJ safety landscape. Under suitable local regularity assumptions, we establish consistency between the GEBF and the value, gradient, and Hessian of the HJ solution along an HJ-optimal characteristic. Building on these theoretical results, we develop an iterative algorithm that couples local geometric propagation with trajectory refinement. We further establish a trajectory-wise one-sided relationship between the GEBF and HJ value function, together with a fixed-point consistency result for the iterative scheme. Experiments on widely adopted agent--obstacle collision-avoidance benchmarks, across low- and high-dimensional systems, demonstrate that GEBFs accurately capture the evolution of dynamic safety boundaries, while achieving substantially lower computational cost than conventional HJ reachability.

0.29

Safe Score Matching: Diffusion Policies with Hamilton-Jacobi Reachability for Online Safe Reinforcement Learning

cs.LG cs.RO ·2026-09-27 ·Boyang Li, Matthew Kim, Sylvia Lee Herbert
top venuecode/data similarity 0.61
Abstract · Accepted to NeurIPS 2026. 29 pages, 4 figures. Code: https://github.com/byli888/safe-score-matching

Online safe reinforcement learning (RL) seeks policies that maximize reward while satisfying safety constraints. A popular line of research in safe RL relaxes safety to a soft expected-cost constraint and solves the resulting Constrained Markov Decision Process via primal-dual Lagrangian updates that only enforce safety on average. To address this limitation, hard, state-wise constraints are introduced and often imposed through Hamilton-Jacobi (HJ) reachability. Yet such constraints require solving different objectives in the feasible and infeasible regions: reward maximization in the former, recovery toward the feasible regions in the latter. The resulting target action distributions are inherently multimodal, and this structure poses a fundamental challenge for the Gaussian or deterministic actors used in existing HJ-based safe RL, which often collapse onto suboptimal modes. Diffusion policies provide the expressiveness needed to represent such distributions, and recent work on Q-score matching offers a route to training them for online RL by score regression -- but has been applied only to reward maximization. We propose Safe Score Matching (SSM), an off-policy actor-critic method that adapts Q-score matching to hard-constrained safe RL by gating a two-branch score target with HJ reachability: inside the feasible set, the denoising process degenerates to Q-score matching on actions classified as viable by the HJ critic; outside, a recovery branch biases denoising toward regions with lower worst-case violation. On quadrotor and fixed-wing trajectory-tracking and stabilize-and-avoid benchmarks, SSM attains the best or near-best task performance with low false-safe rates, whereas the primal-dual baseline admits more unsafe behavior and reachability-based baselines tend to be more conservative; on Safety-Gymnasium velocity tasks, SSM attains the lowest cost with competitive reward.

0.43

Temporal Difference Learning of Probabilistic Reach-Avoid Value Functions

cs.RO eess.SY ·2026-10-20 ·Elias Fontanari, Pietro Noah Crestaz, Matteo Saveriano, Andrea Del Prete
similarity 0.61
Abstract · Submitted to ICRA 2027

Reach-avoid sets, defining the states from which a task can be completed while avoiding unsafe regions, are fundamental tools for deploying robots in environments subject to disturbances and uncertainty, as well as for runtime task-feasibility monitoring, allowing prediction of whether a state is safe and will lead to successful task completion. Classical Hamilton-Jacobi Reachability (HJR) and its recent neural extensions (e.g., Lipschitz Continuous Reachability Learning, DeepReach) treat disturbances adversarially, computing the reach-avoid set under worst-case disturbances from a bounded set. This guarantees safety but can yield overly conservative sets when disturbances are stochastic rather than adversarial, and additionally requires the disturbance set to be known or specified in advance. We propose Probabilistic reach-avoid Value Function (PVF), a self-supervised method, applicable to black-box systems, for computing reach-avoid sets as the states with a certain reach-avoid probability under stochastic, potentially unbounded disturbances. We evaluate our approach against HJR-based baselines on systems of increasing complexity, up to a Hopper locomotion task, and show that our probabilistic sets are less conservative and more accurate than adversarial HJR sets when disturbances are non-adversarial.

0.08