PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Javier Borquez, Shuang Peng, Somil Bansal

arXiv:2609.17430v1cs.ROcs.SYeess.SY

TL;DR

Hybrid control must coordinate continuous dynamics and discrete mode transitions to address safety and performance. The paper extends Hamilton-Jacobi reachability with a hybrid safety filter and reach-avoid tubes; simulations and quadrupedal-robot experiments demonstrate their effectiveness.

  • Problem

    Hybrid robotic systems require simultaneous reasoning about continuous state evolution and discrete mode transitions, complicating the assurance of safety and performance.

    Source: §1 · p. 1

  • Method

    The framework combines a hybrid least restrictive filter that intervenes on nominal continuous and discrete control when needed with hybrid backward reach-avoid tubes for joint safety and goal-reaching guarantees.

    Source: §1 · p. 2, §1.1 · p. 2

  • Results

    The methods are demonstrated through simulations and real-world quadrupedal-robot experiments in contact-rich and dynamic environments.

    Source: §8 · p. 15

  • Takeaways & Limitations

    The framework supports minimally modifying nominal hybrid policies for safety and synthesizing policies that guarantee safety and task completion.

    Source: §1 · p. 2, §1.1 · p. 2

    Scalability to higher-dimensional systems remains a challenge for the framework.

    Source: §8 · p. 15

Abstract

from arXiv · show

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.

1 Introduction

Hybrid robotic systems require controllers to coordinate continuous evolution with discrete mode changes, making safety and performance difficult to ensure. This work extends hybrid reachability with a safety filter and a joint reach-avoid formulation.

1 Introduction

  • Hybrid controllers must coordinate continuous state evolution with discrete mode transitions, as when a jumping robot selects whether and when to jump and at what velocity.The paper identifies this coupled reasoning as conceptually and computationally demanding.Source: §1 · p. 1
  • Prior hybrid reachability work computed backward reachable tubes but did not integrate safety guarantees with goal-oriented control.The paper frames achieving goals while staying safe as a requirement for real-world applications.Source: §1 · pp. 1–2

1.1 Paper Organization and Contributions

  • The hybrid least restrictive filter wraps a nominal policy and intervenes on continuous inputs and discrete transition decisions only when needed to prevent unsafe entry.The authors identify state resets, forced transitions, and mode-dependent dynamics as challenges for formal safety guarantees.Source: §1.1 · p. 2
  • Hybrid backward reach-avoid tubes characterize states from which the system can reach a goal while avoiding unsafe states, yielding safe and goal-complete continuous and discrete policies.The paper derives a constrained HJI-VI and reports hardware verification on a quadrupedal robot.Source: §1.1 · p. 2
  • Together, the contributions support online safety enforcement and offline synthesis of provably safe, task-complete hybrid policies.The paper presents these contributions as bridging safety verification and goal-directed hybrid control.Source: §1.1 · p. 2

2 Related Work

Prior hybrid reachability methods include automata-based, set-propagation, computable-analysis, SMT, and Hamilton-Jacobi approaches. The paper identifies limitations in their dynamics, transition handling, or computation, and a gap in unified safety and goal-reaching guarantees.

2 Related Work

  • Hybrid automata methods propagate polygonal sets under constant-rate dynamics, but typically restrict continuous dynamics to linear models and omit continuous control inputs.The cited examples include timed automata (Alur and Dill 1994) and linear hybrid automata (Alur et al. 1991).Source: §2 · p. 2
  • Set-propagation approaches include zonotopes and other continuous reachability extensions, but nonlinear hybrid reachability remains difficult and controlled transitions are challenging to handle.Controlled transitions are relevant to planning mode changes in systems such as legged robots.Source: §2 · p. 2
  • Computable-analysis, Taylor-model, and SMT methods represent reachable sets geometrically or through formulas, but typically over-approximate sets and limit transitions to forced ones.The cited examples include Taylor models (Chen et al. 2012, 2013; Kochdumper and Althoff 2020) and SMT (Damm et al. 2007; Kong et al. 2015).Source: §2 · p. 2
  • Hybrid HJ methods support nonlinear dynamics, bounded disturbances, and state or input constraints, but iterative BRT computation may take time to converge.These methods refine each mode's BRT using continuous reach-avoid operators and discrete predecessor maps until reaching a fixed point.Source: §2 · pp. 2–3
  • Prior hybrid HJ work incorporated discontinuous state changes, while the paper identifies unified safety and goal-reaching control as a remaining challenge.Hybrid control barrier function approaches focus on candidate barrier functions rather than constructing global safe sets or synthesizing policies with unified safety and goal-reaching guarantees.Source: §2 · p. 3

3 Problem Formulation

The formulation models hybrid systems with continuous states and controls, disturbances, discrete modes, and reset-bearing transitions. It then defines reachability objectives and the safety-filter and reach-avoid tasks over these hybrid states.

3 Problem Formulation

  • A hybrid system comprises discrete modes, continuous states, controls and disturbances, mode-specific dynamics and invariants, discrete actions, and a reset relation.The reset relation encodes discrete transitions between mode-state pairs.Source: §3 · p. 3
  • Controlled switches can change modes within an invariant, while forced switches occur when continuous evolution exits that valid operating domain; either transition may reset the state.Figure 1 depicts controlled and forced transitions.Source: §3 · p. 3, Figure 1 · p. 3

3.1 Backward Reachable Tubes for Hybrid Systems

  • For liveness, the hybrid backward reachable tube is the set of initial state-mode pairs from which control can guarantee reaching a goal within the time horizon.The corresponding continuous and discrete control laws steer the system toward the goal.Source: §3.1 · pp. 3–4
  • The formulation uses nonanticipative disturbance strategies, which cannot respond differently to control signals that remain indistinguishable, though the disturbance can react to the current control action.Under this strategy assumption, the BRT can be obtained from a value function solving a Hamilton-Jacobi-Isaacs PDE.Source: §3.1 · pp. 3–4
  • For safety, the hBRT instead identifies states from which entering a failure set is unavoidable despite control effort.The paper uses the liveness interpretation for its mathematical exposition and notes the corresponding safety formulation.Source: §3.1 · pp. 3–4

3.2 Safety Filtering for Hybrid Systems

  • The safety-filter objective is to keep the system from a failure set over the horizon while modifying nominal hybrid behavior as little as possible.The hBRT supplies the basis for deciding when safety is at risk and intervention is needed.Source: §3.2 · p. 4
  • In the stated filter execution order, the nominal policy selects discrete transitions first, then evaluates continuous control at the resulting intermediate state.This order lets the filter assess transition effects before continuous evolution.Source: §3.2 · p. 4

3.3 Backward Reach-Avoid Tubes for Hybrid Systems

  • The hBRAT is the set of initial state-mode pairs from which, for all disturbances, some control reaches the goal within the horizon without entering failure beforehand.It supports synthesizing hybrid policies that guarantee both safety and goal satisfaction.Source: §3.3 · p. 4

4 Background

Classical HJ reachability computes states from which a system can reach a goal without entering a failure set, but its continuous-only formulation does not account for hybrid mode switches or state resets. The hybrid extension computes reachability across modes and transitions, with a grid-based algorithm whose exactness and termination have limits.

4.1 Hamilton-Jacobi Reachability

  • The BRAT identifies states that can reach the goal within the time horizon without entering the failure set, under optimal control against worst-case disturbance.Starting inside the BRAT and applying the optimal control at its boundary guarantees reaching the goal without entering the failure set.Source: §4.1 · p. 5
  • Classical HJ reachability assumes continuous dynamics and does not account for discrete mode switching or state resets.Source: §4.1 · p. 5

4.2 HJ Reachability for Hybrid Systems

  • The hybrid HJI-VI extends hBRT computation to controlled and forced transitions with state resets, choosing between a mode switch and continuous evolution in the current mode.A dummy transition represents remaining in the current mode.Source: §4.2 · p. 5, Figure 2 · p. 5
  • The numerical algorithm propagates one value function per discrete mode and adjusts each for available switches, jointly accounting for continuous and discrete transitions.It computes over a discretized state-space grid with finite time steps.Source: §4.2 · p. 6
  • Algorithm 1 has total complexity O(T · N^2 · M^nx/δ), scaling exponentially with continuous-state dimension and quadratically with mode count.Source: §4.2 · p. 6
  • The grid-based algorithm computes an approximate value function; exact hybrid reachable sets are generally undecidable, and the algorithm may not terminate for arbitrary hybrid dynamics.Source: §4.2 · p. 6

5 Safety Filtering for Hybrid Systems

The hLRF wraps a nominal hybrid policy and intervenes on continuous controls or discrete transitions only when needed to keep the system safe. Across jumping-robot and spacecraft simulations, it maintains safety while minimally changing nominal behavior.

5 Safety Filtering for Hybrid Systems

  • The hLRF checks planned discrete transitions and continuous inputs, overriding unsafe choices while otherwise preserving the nominal policy.For discrete transitions it selects a safe alternative; continuous control is adjusted at the safety boundary.Source: §5 · pp. 6–7
  • For any nominal hybrid policy, Theorem 2 states that the hLRF ensures forward invariance of the safe set encoded by the avoid hBRT.The proof preserves safety across the discrete update and then relies on a continuous-time safety filter.Source: §5 · p. 7

5.1 Hybrid Least Restrictive Filtering Case Studies

  • The case studies test the filter on systems with forced and controlled transitions, unactuated modes, and timing constraints.The jumping robot has stance and ballistic-flight modes, with ground forces available only in stance.Source: §5.1 · p. 7, §5.1.1 · p. 7, Figure 3 · p. 7

5.1.1 Planar Jumping Robot:

  • For both jumping-robot policies, the hLRF intervened to prevent obstacle collisions, including by triggering an earlier jump when the first jump left negative velocity.The second policy’s low hops could not clear the obstacle unaided; queries averaged 0.16 ms on an Intel i7-13620H.Source: §5.1.1 · p. 8

5.1.2 Low orbit spacecraft:

  • In the spacecraft case, the filter maintained collision-free motion from two initial conditions, averaging 0.19 ms per query.It handled controlled and forced transitions, timing constraints, and continuous controls when propulsion was available.Source: §5.1.2 · p. 8

6 Reach-Avoid Formulation for Hybrid Systems

The hBRAT formulation extends hybrid reachability to find states from which a system can reach a goal within a time horizon while avoiding failure. Its computation and case studies address continuous evolution, discrete mode changes, and safe goal-reaching behavior.

6 Reach-Avoid Formulation for Hybrid Systems

  • Theorem 3 extends hybrid reachability to find initial states that can reach a goal within a time horizon while avoiding a failure set.Unlike Theorem 1, it enforces reach and avoid objectives simultaneously.Source: §6 · p. 9
  • Within a mode’s operational domain, the value update considers either a discrete transition with its reset map or continued evolution; outside it, a forced transition is required.The update takes the minimum over mandatory resets when the system cannot remain in its current mode.Source: §6 · pp. 9–10
  • The reach-avoid cost minimizes over time the maximum of distance to the goal and clearance to the failure set.The value is defined under continuous and discrete controls that minimize cost and disturbances that maximize it.Source: §6 · p. 9
  • The numerical algorithm propagates the value function backward on a discretized grid, initializing the terminal condition with the pointwise maximum of the goal and failure functions.Its update accounts for continuous dynamics and transitions across modes.Source: §6 · p. 10
  • The hBRAT algorithm has the same scaling as hBRT computation: O(T · N^2 · M^nx/δ).Here N is the number of discrete modes, M grid points per continuous dimension, nx the number of continuous states, T the horizon, and δ the timestep.Source: §6 · p. 10

6.1 Hybrid Reach-Avoid Case Studies

  • Because the case-study computation uses discretized approximations, it may not yield exact results without infinite resolution.The two case studies include mode transitions, unactuated dynamics, and dwell-time constraints.Source: §6 · p. 10, §6.1 · p. 11

6.1.1 Planar Jumping Robot

  • Within 1.8 s, the planar robot reaches the goal without collision, with stance and flight hBRAT slices meeting at the forced jump transition.The trajectory follows the optimal reach-avoid policy from an initial state in the hBRAT.Source: Figure 7 · p. 11, §6.1.1 · p. 11

6.1.2 Low Earth Orbit Spacecraft

  • Figure 8 shows spacecraft docking trajectories from different initial conditions; high radial velocity yields an elongated hBRAT slice and a more aggressive approach using one thrust-mode transition.The low-velocity trajectory approaches gradually, while both trajectories avoid obstacles.Source: Figure 8 · p. 11, §6.1.2 · p. 11

7 Full System Experiments

The experiments evaluate an offline-computed hBRAT planner with a reduced-order torso model in simulation and on a quadruped, using both model-based and learned locomotion controllers. Across the reported tests, the planner achieves high safe reach under disturbances and supports obstacle-specific mode changes, with guarantees conditional on modeled disturbance bounds.

7 Full System Experiments

  • For the benchmark, hBRAT uses reduced-order torso dynamics with bounded velocity disturbances and discrete states for height, pitch, gait frequency, and velocity gains.The reduced state dimension makes grid-based hBRAT computation tractable; the reachable set is computed offline and queried online.Source: §7 · pp. 12–13

7.1 Simulation Validation

  • At σ = 0.4 m/s, hBRAT Safe Reach is 0.81, versus MPC 0.48, MPC-CBF 0.44, and MPPI 0.15; hBRAT leads at every disturbance level.The comparison uses 100 trials per disturbance level; Safe Reach is the fraction of goal-reaching trials without collisions.Source: Table 1 · p. 13, §7.1 · p. 13
  • In simulation, hBRAT recovers from disturbances toward a near-optimal goal path, while the baselines reach the goal but repeatedly penetrate obstacles.The study compares against MPPI, deterministic MPC, and CBF-MPC using shared reduced-order dynamics and task setups.Source: §7.1 · p. 13
  • At the highest simulated disturbance, 0.4 m/s, hBRAT’s safe reach rate falls to 0.81 as disturbance plus model mismatch can exceed its assumed 0.5 m/s bound.The paper attributes occasional shallow collisions to this bound being exceeded and reports average peak penetration of 0.048 m, within the stated discretization margin.Source: §7.1 · pp. 13–14

7.2 Real World Safety Across Locomotion Policies

  • The planner switches among walking, slope-climbing, crawling, and higher-frequency gait modes to navigate the weave poles, slope, overhang, and slippery terrain.Crawling is selected under the overhang; slope-climbing and slippery-terrain transitions are modeled as forced switches.Source: §7 · p. 12, §7.2 · p. 14
  • The real robot completed all obstacles without collisions with both locomotion controllers; course times were 58.6 s for MPC and 17.9 s for RL.Hardware results cover 10 trials with disturbances; the reported guarantees assume disturbances remain within the planner’s modeled bounds.Source: §7.2 · p. 14, Table 2 · p. 14

7.3 Robustness to External Disturbances

  • The robot autonomously reactivates crawl-walking after a push toward the overhang and can recover even after being dragged into an unsafe region.The reach-avoid formulation provides a fallback safety control strategy for recovery from momentary entry into unsafe regions.Source: §7.3 · pp. 14–15, Figure 12 · p. 15
  • The framework provides the top level of a hierarchical planner; safe real-world operation also depends on perception, state estimation, and disturbance estimation.The paper identifies integrating these modules as future work.Source: §7.3 · p. 15

8 Discussion And Future Work

The discussion identifies scalability, environmental knowledge, and Zeno behavior as current constraints on the framework. It also points to extensions in numerical methods and broader robotic domains.

Scalability

  • Grid-based computation scales exponentially with the number of continuous states, limiting direct application to high-dimensional hybrid systems.Proposed directions include learning-based HJI-VI solvers and structure-exploiting methods such as Sum-of-Squares and Zonotopes.Source: §8 · p. 15

Environmental Knowledge

  • Computing the hybrid BRT or BRAT offline currently requires a priori knowledge of the full environment, limiting use where environments are partially known or change dynamically.The paper suggests incremental or online reachability as a possible direction.Source: §8 · p. 15

Zeno Behaviors

  • The algorithm avoids Zeno behaviors with a finite transition timestep δ, at the cost of approximate value functions.The paper identifies properly handling Zeno behavior during reachable-set and safety-controller computation as an open direction.Source: §8 · p. 15

Broader Applications

  • The framework is validated on quadrupedal locomotion; broader applications named include legged manipulation, multi-contact locomotion, and aerial-ground hybrid vehicles.The paper presents extension to these domains as future work.Source: §8 · p. 15
Loading 2609.17430v1…