DeepReach: A Deep Learning Approach to High-Dimensional Reachability

Somil Bansal; Claire Tomlin

Source-linked AI summary

DeepReach: A Deep Learning Approach to High-Dimensional Reachability

Somil Bansal, Claire Tomlin

arXiv:2011.02082v1Nov 4, 2020cs.ROcs.AIcs.LGeess.SY

TL;DR

HJ reachability provides formal safety analysis for nonlinear dynamical systems but grid-based PDE solvers scale exponentially with state dimension. DeepReach represents the value function with a sinusoidal neural network trained by PDE self-supervision. It achieves low error on Air3D and comparable performance as dimensionality increases, while remaining applicable to disturbances, constraints, and safety-controller synthesis.

Problem
Grid-based HJ reachability solves a PDE whose computation and memory scale exponentially with state dimension, limiting direct use to low-dimensional systems.
Method
DeepReach represents the HJ value function with a deep neural network and uses the PDE itself as self-supervision, with sinusoidal activations for value-function gradients.
Results
DeepReach achieves MSE 1.9 × 10−4 against the analytical Air3D solution, MSE 1.01 × 10−4 against the LST value function, and MSE 2.1 × 10−4 for the 6D extension.
Takeaways & Limitations
DeepReach computes approximate reachable tubes and safety controllers for nonlinear systems with disturbances, adversarial inputs, and state and input constraints.
Takeaways & Limitations
DeepReach is primarily suitable for offline computation, and prediction error makes theoretical safety guarantees challenging.

Abstract

from arXiv · show

Hamilton-Jacobi (HJ) reachability analysis is an important formal verification method for guaranteeing performance and safety properties of dynamical control systems. Its advantages include compatibility with general nonlinear system dynamics, formal treatment of bounded disturbances, and the ability to deal with state and input constraints. However, it involves solving a PDE, whose computational and memory complexity scales exponentially with respect to the number of state variables, limiting its direct use to small-scale systems. We propose DeepReach, a method that leverages new developments in sinusoidal networks to develop a neural PDE solver for high-dimensional reachability problems. The computational requirements of DeepReach do not scale directly with the state dimension, but rather with the complexity of the underlying reachable tube. DeepReach achieves comparable results to the state-of-the-art reachability methods, does not require any explicit supervision for the PDE solution, can easily handle external disturbances, adversarial inputs, and system constraints, and also provides a safety controller for the system. We demonstrate DeepReach on a 9D multi-vehicle collision problem, and a 10D narrow passage problem, motivated by autonomous driving applications.

I. INTRODUCTION

HJ reachability provides safe configurations and controllers but becomes computationally and memory intensive as system dimensionality grows. DeepReach addresses this by representing the value function with a self-supervised sinusoidal neural network.

HJ reachability computes safe configurations and corresponding controllers by solving a value-function PDE for dynamical systems.Its formulation can include nonlinear dynamics, disturbances, and state-dependent constraints.
Grid-based HJ reachability has exponentially scaling computational and memory complexity with respect to system dimensionality.This limitation is commonly called the curse of dimensionality.
DeepReach represents the value function with a deep neural network instead of solving its PDE over a state-space grid.Its computation and memory requirements scale with value-function complexity rather than grid resolution.
DeepReach uses PDE-based self-supervision and periodic sinusoidal activations to represent the value function and its gradients.The gradients are needed to compute the safety controller.

II. RELATED WORK

Prior reachability methods trade scalability against dynamics, disturbances, constraints, precision, or supervision requirements. DeepReach combines nonlinear-system reachability with disturbances and avoids explicit supervision.

Level set methods accurately compute BRTs but their exponential complexity limits direct use to systems of roughly five dimensions.They solve the value-function PDE on a discretized state-space grid.
Approximate geometric methods scale to high-dimensional affine systems but may linearize nonlinear dynamics, producing overly conservative BRTs.Examples use polytopes, hyperplanes, ellipsoids, or zonotopes.
Sampling, support-vector, and neural-network methods approximate reachable tubes for nonlinear systems but often struggle with adversarial disturbances or state constraints.Some also require explicit supervision that is difficult to generate in general high-dimensional systems.
DeepReach does not rely on explicit supervision and computes approximate BRTs for nonlinear dynamics with disturbances.It can also be interpreted as approximate dynamic programming using a DNN to learn value-function basis features.

III. PROBLEM SETUP

The paper formulates reachability for controlled dynamical systems under disturbances, defining BRTs and BRATs for goal or unsafe targets. Air3D provides a nonlinear collision-avoidance benchmark with control and adversarial input.

The system is modeled with state x, control u, disturbance d, and trajectories generated over a finite time interval.Control and disturbance inputs are assumed to lie in compact sets under standard trajectory-existence assumptions.
A BRT contains initial states whose optimally controlled trajectories reach a target within the horizon despite worst-case disturbances.For unsafe targets, it identifies states that may become unsafe despite control efforts.
A BRAT contains states from which the system can reach a goal while avoiding an unsafe set throughout the horizon.The unsafe set can represent obstacles or violated system constraints.
Running example (Air3D): Air3D models relative position and heading between two vehicles, with bounded evader control and pursuer disturbance inputs.Both angular velocities lie in the interval [−¯ω, ¯ω].
Running example (Air3D): The Air3D BRT identifies states from which the pursuer can force entry into the collision set despite the evader's best avoidance efforts.The benchmark is nonlinear, nonconvex, partly nondifferentiable, and supports comparison against an almost analytical solution.

IV. BACKGROUND: HAMILTON-JACOBI REACHABILITY

HJ reachability solves a robust zero-sum control problem through dynamic programming and a Hamilton-Jacobi-Isaacs variational inequality. The resulting value function yields the reachable tube and safety control, but grid discretization causes exponential scaling.

HJ reachability formulates BRT and BRAT computation as a zero-sum game between control and disturbance.Dynamic programming recovers the BRT from the game's solution.
The target function l(x) defines the target set as its sub-zero level set, L = {x : l(x) ≤0}.It is typically chosen as a signed distance function.
The value function optimizes the distance to the target over time under control and disturbance inputs.The associated HJI VI is obtained through dynamic programming, with terminal value V (x, T) = l(x).
The value-function gradients determine the Hamiltonian and the corresponding optimal safety control.The safety control is especially relevant at the BRT boundary.
The BRT is recovered as the sub-zero level set of the value function after solving the HJI VI.The variational inequality preserves negative values after trajectories enter the target set.
Grid-based HJI VI solvers have exponentially scaling computation and memory requirements, limiting direct use to fairly low-dimensional systems.The paper uses machine learning to address this computational challenge.

V. DEEPREACH: REACHABILITY USING DEEP LEARNING

DeepReach represents the reachability value function with a DNN and learns it through self-supervision derived from the HJI VI, while requiring accurate value-function gradients for training and safety control.

Value-function representation: DeepReach uses a DNN that maps state and time to the corresponding reachability value function.The DNN is agnostic to grid resolution, so its memory generally scales with signal complexity rather than spatial resolution.
Self-supervised training: The training loss combines terminal-time supervision with an HJI VI consistency term to avoid degenerate solutions.The terminal-time term uses the ground-truth value function, while λ controls the trade-off between the two loss components.
Gradient requirements: The loss depends on temporal and spatial value-function gradients, which are also needed to compute the optimal safety controller.ReLU-based networks can struggle to represent these gradients accurately, degrading the learned value function.
Training procedure: Training first fits the terminal condition, then uses curriculum learning that gradually propagates it toward earlier times.The procedure decreases t linearly from T as training progresses.

A. Running example: Air3D

In the Air3D example, DeepReach accurately approximates the value function and BRT, while sinusoidal activations substantially outperform ReLU, tanh, and sigmoid alternatives.

Implementation: Training the Air3D value function required approximately 16 hours on a single GPU worker.The experiment used 65k randomly sampled 3D states, 10K pre-training iterations, and 100k curriculum-training iterations.
Accuracy: 1.01 × 10−4 MSE measures DeepReach’s value function against the Level Set Toolbox solution on a 101 × 101 × 101 grid.Against the analytical BRT solution, DeepReach also achieves 1.9 × 10−4 MSE.
Accuracy: 0.43% BRT volume error indicates close agreement between DeepReach’s BRT and the reference BRT.The volume error counts unsafe states incorrectly marked safe and vice versa.
Activation functions: DeepReach’s sinusoidal architecture closely matches the analytical solution, whereas ReLU, tanh, and sigmoid architectures fail to find the correct solution.The alternative architectures produce MSE values an order of magnitude higher than DeepReach.

B. Two-Vehicle Collision Avoidance Example

DeepReach extends the collision-avoidance formulation from relative coordinates to the joint state space, learning a 6D value function without a direct principled-solver comparison.

6D formulation: The joint-state formulation turns the two-vehicle collision-avoidance problem into a 6D reachability problem that is intractable for direct principled PDE solving.DeepReach learns the 6D value function and projects it back to relative coordinates for comparison.
Game formulation: The overall-system control is ωe and the disturbance is ωp in the joint-state game.
Results: 2.1 × 10−4 MSE shows that the projected 6D solution performs on par with the learned 3D solution against the analytical solution.The 6D experiment required approximately 17 hours of training.
Scaling: Training time and memory requirements increase little from the 3D to the 6D system.This supports the claim that DeepReach is agnostic to spatial resolution and instead scales with signal complexity when that complexity is unchanged.

C. Three-Vehicle Collision Avoidance Example

DeepReach computes the full 9D collision-avoidance BRT, capturing unsafe states caused by three-way vehicle interactions that pairwise approximations miss. The resulting trajectories show when the pursuer can force an evader collision and when the safety controller enables avoidance.

The 9D system contains two evaders and one pursuer, with the pursuer steering the evaders toward collisions while the evaders attempt to avoid them.
Pairwise BRT unions can underestimate unsafe states because they fail to capture three-way interactions among the vehicles.An evader strategy that is safe in a pairwise pursuit-evasion game may cause a collision with the other evader when all three vehicles interact.
20 hours were required to train the higher-dimensional network after 60k pretraining iterations followed by 100k training iterations.The reported results were similar with 30k pretraining iterations.
DeepReach captures additional unsafe pursuer states arising from three-way interactions beyond the union of pairwise BRTs.In the illustrated slice, these additional states are shown as the pink region, while the pairwise union is the green region.
When the pursuer starts inside the additional unsafe region, it can force the evaders to collide, whereas pairwise analysis predicts no collision.The full 9D value function yields a pairwise distance below the collision threshold, while the pairwise value function remains above it.

D. Narrow Passage Problem in Autonomous Driving

DeepReach computes a 10D backward reach-avoid tube and its safety controller for a narrow-passage scenario involving a stranded vehicle and oncoming traffic. The controller coordinates both vehicles’ deviations from nominal paths to avoid collision and then return to their targets.

The 10D problem requires Q1 to pass a stranded vehicle while coordinating with oncoming vehicle Q2 to avoid collisions.Q1 changes lanes around QS while avoiding both Q2 and the stranded vehicle.
The same safety controller adapts to Q2’s initial position by making Q2 swerve more aggressively when it starts closer to the centerline.
The vehicle model represents position, heading, velocity, and steering angle, with bounded acceleration and steering-rate controls.
DeepReach computes the BRAT in 25 hours using 60k pretraining iterations followed by 100k curriculum-training iterations.
Following nominal trajectories causes a collision, whereas the DeepReach safety controller makes Q1 take a tighter turn and Q2 swerve toward the curb.These maneuvers increase clearance between the vehicles and avoid the collision.
After passing, both vehicles converge back to their nominal trajectories and reach their respective targets.The cooperative collision-avoidance behavior emerges automatically from the safety controller.

VII. DISCUSSION AND FUTURE WORK

DeepReach uses neural PDE methods to compute reachable tubes and safety controllers without explicitly solving the value-function PDE on a grid. The authors report promising 9D and 10D demonstrations but identify offline use, prediction error, and fundamental dimensionality limits.

DeepReach implicitly computes reachable tubes by using the PDE as a supervision source rather than solving it explicitly, improving scalability to higher-dimensional systems.
DeepReach is primarily suitable for offline BRT computations despite not scaling exponentially.
Prediction error from the learning module makes theoretical safety guarantees challenging.
The authors do not expect DeepReach to overcome the curse of dimensionality in general because it is fundamental to dynamic-programming-based methods.
Success on 9D and 10D systems suggests that many robotic value functions may contain exploitable low-dimensional structure.The authors propose investigating this structure in future work on other robotic systems.