# Imposing Exact Safety Specifications in Neural Reachable Tubes

Aditya Singh∗1, Zeyuan Feng∗2, and Somil Bansal2 ∗ Denotes equal contribution.
This work is supported in part by the NSF CAREER Program under award 2240163
and the DARPA ANSR program.1Author is with EE at Indian Institute of
Technology Patna, India<EMAIL_ADDRESS>are with ECE at
the University of Southern California, LA, USA: {zeyuanfe<EMAIL_ADDRESS>
###### Abstract

Hamilton-Jacobi (HJ) reachability analysis is a powerful verification tool to
provide safety and performance guarantees for autonomous systems. It is widely
adopted because of its capability to handle nonlinear dynamical systems with
bounded adversarial disturbances and constraints on the states and inputs.
However, it involves solving a partial differential equation (PDE) to compute
a safety value function, whose computational and memory complexity scales
exponentially with the state dimension, thereby making its direct application
to large-scale systems intractable. Recently, a learning-based approach called
DeepReach, has been proposed to approximate high-dimensional reachable tubes
using neural networks. While the approach has been shown to be effective, the
accuracy of the learned solution typically decreases with the increase in the
system complexity. One of the reasons for this degradation is the inexact
imposition of safety constraints during the learning process, which
corresponds to the boundary conditions of the PDE. Specifically, DeepReach
imposes boundary conditions as soft constraints within the loss function,
which leaves room for error during the value function learning. Moreover, one
needs to carefully adjust the relative contributions from the imposition of
boundary conditions and the imposition of the PDE in the loss function. This,
in turn, induces errors in the overall learned solution. In this work, we
propose a variant of DeepReach that exactly imposes safety constraints during
the learning process by restructuring the overall value function as a weighted
sum of the boundary condition and the neural network output. The proposed
variant no longer needs a boundary loss during the training process, thus
bypassing the need for loss adjustment. We demonstrate the efficacy of the
proposed approach in significantly improving the accuracy of the learned
reachability solutions for challenging high-dimensional reachability tasks,
such as rocket-landing and multivehicle collision-avoidance problems.

##  I Introduction

With the recent surge in real-world applications of autonomous systems,
ensuring the safety of these systems is becoming increasingly important. One
way to formalize the safety of autonomous systems is via Hamilton-Jacobi (HJ)
Reachability analysis [1]. In HJ reachability analysis, a Backward Reachable
Tube (BRT) of the system is computed. The BRT is the set of all initial states
of the system from which it will eventually be driven to a target set within a
specified time horizon, despite the best control effort. Therefore, if the
target set represents the undesirable states, the BRT comprises the unsafe
states for the system and should be avoided. Conversely, if the target set
represents the desirable set of states, the BRT represents the initial states
from which the system can reach the target set despite the worst-case
disturbance (e.g., modeling error, environment disturbance, or an adversarial
agent). Along with the BRT, the reachability analysis also yields a safe
controller for the system to maintain system safety.

HJ reachability analysis frames the BRT computation as an optimal control
problem. This eventually results in solving a partial differential equation
(PDE), called Hamilton-Jacobi-Isaacs (HJI) PDE, over the state space to obtain
the value function corresponding to this optimal control problem. Once
computed, the sub-zero level set of the value function yields the BRT.
Traditionally, this PDE is solved numerically over a state-space grid [2, 3,
4, 5]. However, the computational complexity of grid-based methods scales
exponentially with the number of state dimensions, rendering them ineffective
for high-dimensional reachability problems.

Several recent advancements have been made to mitigate this “curse of
dimensionality.” Among these, a promising class of methods leverages deep
neural networks to approximate the safety value function, such as DeepReach
[6]. DeepReach leverages advances in implicit neural representations [7] and
physics-informed neural networks [8] to solve the HJI PDE. Specifically, the
safety value function is represented as a neural network whose weights are
optimized by using a combination of two loss terms – (a) the residual errors
arising from enforcing the boundary conditions of the HJI PDE, which
corresponds to the specification of the target set (also referred to as the
safety specification from here on) and (b) the residual errors associated with
the HJI PDE within the domain’s interior. A notable advantage of DeepReach is
that, unlike grid-based methods, its complexity doesn’t scale exponentially
with the system dimensions, thereby allowing it to handle high-dimensional
reachability problems. Nevertheless, the accuracy of the learned solution
suffers from the ability to co-optimize the two loss terms and the relative
weight between them. Additionally, the imposition of the safety specifications
as a soft constraint makes it particularly prone to learning inaccurate value
functions, as the solution of any PDE depends heavily on the boundary
conditions. This drawback is more acute for complex boundary conditions (e.g.,
cluttered obstacles for a mobile robot), where DeepReach may learn completely
non-physical solutions.

In this work, we overcome these challenges by proposing a new variant of
DeepReach that exactly satisfies the safety constraints (i.e., the boundary
conditions). Rather than using the neural network (NN) to learn the value
function directly, our key idea is to represent the value function as a
weighted combination of the boundary value function and the neural network
output, where the NN output is weighted by a “distance function” to the
boundary. This distance function is zero at the boundary and increases as the
system state is farther from the boundary. Consequently, we show that the
learned value function always satisfies the boundary conditions. Corresponding
to this novel formulation, we derive a new loss function to train the neural
network. However, now the network needs to optimize only a single loss
function, which corresponds to the HJI PDE residual errors, thereby
eliminating the scope of inaccuracies that could stem from the incorrect
weighting of two loss terms. Overall, we show that the proposed method
significantly enhances the accuracy of the learned safety value function. To
summarize, our overall contributions are:

  1. 1.

We propose a new method to increase the accuracy of deep learning-based
approximation of high-dimensional reachable tubes.

  2. 2.

Our proposed variant computes the value function by optimizing a single loss
function, thereby eliminating the need for hyperparameter tuning and the scope
of inaccuracies that could stem from the incorrect weighting of two loss
terms.

  3. 3.

We illustrate the benefits of the proposed strategy through case studies on
two high-dimensional reachability problems: a 6D Rocket Landing problem and a
9D three-vehicle collision avoidance problem, both of which are intractable
for traditional methods.

##  II Related work

###  II-A BRT Computation via HJ Reachability

Several methods have been proposed to compute BRT using Hamilton-Jacobi
reachability analysis.

Traditionally, level-set methods [2, 3, 4, 5] compute BRTs by solving an HJI
partial differential equation (PDE) on a discretized grid of the state-space.
However, the computational complexity of these methods scales exponentially
with the system dimensionality, which limits a direct application of these
methods to systems up to 5D.

[1] provides a comprehensive survey of various methods that have been
introduced to reduce the aforementioned computation burden. For example,
several works impose assumptions on the system dynamics to compute the value
function for high-dimensional systems, such as linearity [9, 10, 11] or
monotonicity [12]. Alternative methods decompose system dynamics to reduce a
high-dimensional reachability problem to several smaller subproblems [13, 14].
However, none of the above approaches offer a framework to handle general
high-dimensional system dynamics within HJ reachability analysis. To overcome
these challenges, learning-based methods have been proposed to compute neural
approximations of the reachable tubes and the value function [6, 15, 16, 17,
18, 19]. As a special realization of neural PDE solvers, DeepReach [6] took
advantage of the periodic (sinusoidal) activation function to accurately learn
the safety value function and demonstrated its success on high-dimensional
reachability problems. However, the learned solution is prone to errors as
DeepReach imposes boundary conditions as soft constraints during the training
process. Additionally, DeepReach requires the user to carefully choose the
hyperparameter balancing the imposition of boundary constraints and the PDE
constraints, which can affect the learned solution quality. This work builds
upon DeepReach and aims to overcome these limitations by imposing the boundary
conditions exactly during the learning process.

###  II-B Imposing Exact Boundary Condition in Physics Informed Machine
Learning Models

In general, a PDE can have infinitely many solutions, and boundary conditions
are defined to recover a particular solution of the PDE. Hence, an inexact
boundary value function can lead to inaccurate or even non-physical solutions.
In addition, training with a composition of boundary loss and PDE loss
compromises the convergence of the stochastic gradient descent algorithm [20,
21, 22].

To address these challenges, some recent works have studied the imposition of
exact boundary conditions with neural ODE and PDE solvers. [23, 24, 25]
modified the structure of kernels within neural operators to make the model
always satisfy boundary conditions. [20] proposes a method for imposing
boundary constraints for physics-informed neural networks (PINNs) by
constructing an approximate distance function to the boundary. However,
constructing a complex distance function is generally time-consuming and
unnecessary for imposing boundary conditions in the HJI PDE. In one of the
earlier studies, [26] represented the trial solution of PDE by the sum of two
terms. The first term is a fixed function satisfying the boundary conditions,
and the second term is the product of the neural network approximation and a
function that zeroes out at the boundary of the domain. Our work takes
inspiration from this idea and presents a more specific formulation that
caters to the HJI PDE. We also propose a pretraining scheme to facilitate
learning stability under the new solution structure.

##  III Problem Setup

Consider a general nonlinear, time-invariant dynamical system

$\dot{x}=f(x,u,d),$ (1)

where $x\in\mathbb{R}^{n}$ is the system state, $u\in\mathcal{U}$ is the
control input, and $d\in\mathcal{D}$ represents the disturbance in the system.
Disturbance could capture the modeling errors or the action of an actual
adversarial agent that we may want to safeguard against. For such a system, we
let $\xi^{u,d}_{x,t}(\tau)$ denote the system state achieved at time $\tau$
starting with the initial state $x$ and applying controls $u(\cdot)$ and
$d(\cdot)$ over the time horizon $[t,\tau]$.

We are also given a target set $\mathcal{L}=\\{x:l(x)\leq 0\\}$ that consists
of the undesirable states for the system (e.g., obstacles for a mobile robot).
Here, $l(x)$ can be interpreted as a user-defined Lipschitz function measuring
the “distance” to the target set. Given $\mathcal{L}$, our goal is to compute
the Backward Reachable Tube (BRT) of the system that represents the set of
potentially unsafe states for the system. Formally, BRT is the set of all
initial states of the system which will eventually be driven to $\mathcal{L}$
under worst-case $d(\cdot)$, regardless of $u(\cdot)$ applied,

$\mathcal{G}(t)=\left\\{x:\forall u(\cdot)\in\mathcal{U},\exists
d(\cdot)\in\mathcal{D},\exists\tau\in[t,T],l(\xi_{x,t}^{u,d}(\tau))\leq
0\right\\}.$ (2)

On the contrary, if the target set consists of the states that should be
reached, a BRT can also represent the set of safe states at time $t$ where
there exists an $u(\cdot)$ for the system to reach the target set
$\mathcal{L}$ before the end of time horizon $T$ under any possible
disturbance $d(\cdot)$.

$\mathcal{G}(t)=\left\\{x:\forall d(\cdot)\in\mathcal{D},\exists
u(\cdot)\in\mathcal{U},\exists\tau\in[t,T],l(\xi_{x,t}^{u,d}(\tau))\leq
0\right\\}.$ (3)

In this work, we will propose a learning-based method to compute the BRT,
$\mathcal{G}$.

Running Example: Rocket Landing. To demonstrate the concept of BRTs and the
key ideas involved in computing them, we will use a six-dimensional rocket
landing system as a running exmaple throughout this paper. It involves a
rocket trying to safely land on a rectangular landing pad centered at the
origin. The system states include its position coordinates $(x,y)$, heading
$\theta$, velocity, $(v_{x},v_{y})$, angular velocity, $\omega$. The rocket is
controlled by its torque inputs, $\tau_{1},\tau_{2}$, that are bounded within
$[\tau_{min},\tau_{max}]$. The rocket’s state space dynamics are given as

$\displaystyle\qquad\qquad\dot{x}=v_{x},\quad\dot{y}=v_{y},\quad\dot{\theta}=\omega,\quad\dot{\omega}=k\tau_{1},$
$\displaystyle\dot{v_{x}}=\tau_{1}cos\theta-\tau_{2}sin\theta,$
$\displaystyle\dot{v_{y}}=\tau_{1}sin\theta+\tau_{2}cos\theta-g,$ (4)

where $g$ is gravitational acceleration and $k$ is a constant multiplier. For
this example, we assume that there is no disturbance in the system.

The goal of the rocket is to reach a rectangular region of length $2d_{l}$ and
width $d_{w}$ centered at the origin in $xy$ plane, shown as the Green area in
Figure 3b. Correspondingly, the target set for this system can be defined as:

$\mathcal{L}=\\{(x,y):l(x,y)=\max\\{|x|-d_{l},y-d_{w}\\}\leq 0\\}.$ (5)

In this case, we are interested in computing the BRT as defined in (3). Here,
the BRT represents the set of all initial states from which the rocket can
successfully land on the landing pad within a time horizon of $T=1s$.

A direct BRT computation for this case is not feasible via grid-based methods.
Instead, our objective is to compute an accurate BRT through neural PDE
solvers, such as DeepReach, using an exact imposition of boundary conditions.

##  IV Background: Hamilton-Jacobi Reachability and DeepReach

Hamilton-Jacobi (HJ) Reachability analysis formulates the computation of BRTs
as a robust optimal control problem, which amounts to solving a partial
differential equation. Our work builds upon DeepReach, a neural PDE solver
that leverages HJ reachability to compute BRTs for high-dimensional systems.
This section provides a concise overview of both methods.

###  IV-A Hamilton-Jacobi Reachability

In HJ Reachability, the first step is to define the target set as the sub-zero
level set of a Lipschitz continuous function, $\mathit{l(x)}$, also referred
to as the target function:

$\mathcal{L}=\\{x:l(x)\leq 0\\}.$ (6)

Usually, $l(x)$ is chosen as a signed distance function to obstacles.

Then, HJ reachability synthesizes BRT by computing the minimum distance to
$\mathcal{L}$ throughout the system trajectory resulting from both optimal
control and worse-case disturbance:

$V(x,t)=\inf_{d(\cdot)}\sup_{u(\cdot)}~{}\min_{\tau\in[t,T]}l\left(\xi_{x,T}^{u,d}(\tau)\right).$
(7)

Here, the sub-zero level set of the value function $V(\cdot)$ is the set of
all potentially unsafe states $x$ at time $t$ from which the system will
inevitably enter the target set $\mathcal{L}$ during the time horizon $[t,T]$
under worse-case disturbance, no matter what control is being applied.
Therefore, this sub-zero level set is precisely the BRT,

$\mathcal{G}(t)=\left\\{x:V(x,t)\leq 0\right\\}.$ (8)

For liveness problems such as the aforementioned Rocking Landing example, the
system aims to reach the target set $\mathcal{L}$. Consequently, the BRT is
the subzero level set of the value function minimized by $u(\cdot)$ and
maximized by $d(\cdot)$:

$V(x,t)=\sup_{d(\cdot)}\inf_{u(\cdot)}~{}\min_{\tau\in[t,T]}l\left(\xi_{x,T}^{u,d}(\tau)\right).$
(9)

The value function, in either case, can be computed using the principle of
dynamic programming which results in the following final-value Hamilton-
Jacobi-Isaacs Variational Inequality (HJB-VI):

$\begin{gathered}\min\\{D_{t}V(x,t)+H(x,t),l(x)-V(x,t)\\}=0,\\\
H(x,t)=\max_{u\in\mathcal{U}}\min_{d\in\mathcal{D}}\langle\nabla
V(x,t)\;,\;f(x,u,d)\rangle,\\\ V(x,T)=l(x),\end{gathered}$ (10)

where $\nabla$ and $D_{t}$ denote the spatial and time derivatives of the
value function. $H(x,t)$ is the Hamiltonian of the system that encodes the
role of control and disturbance and how they affect the value function. The
term $l(x)-V(x,t)$ enforces the value function to be non-increasing over time,
preventing the system from entering and then leaving the target set. The
boundary condition for the HJI-VI is given by $l(x)$, which defines the safety
specification (or the target set) for the system. For a detailed explanation
and derivation of the HJI-VI, we refer interested readers to [1, 2].

Once the value function is computed, the BRT is given by (8). Along with the
BRT, the value function also provides an optimal safe policy for the system:

$\pi^{*}(x,t)=\arg\max_{u}\min_{d}\langle\nabla V(x,t),f(x,u,d)\rangle.$ (11)

Intuitively, the safety controller steers the system towards higher values
(i.e., away from the target set) at any state $x$. Similarly, the liveness
reachability controller is given as

$\pi^{*}(x,t)=\arg\min_{u}\max_{d}\langle\nabla V(x,t),f(x,u,d)\rangle.$ (12)

###  IV-B DeepReach

DeepReach is a learning-based method to solve the HJI-VI in (10) that is
designed to tackle high-dimensional reachability problems [6]. It leverages a
deep neural network (DNN) parameterized by $\theta$ with a sinusoidal
activation function to predict approximate value function $V_{\theta}(x,t)$.

DeepReach (called vanilla DeepReach here on to differentiate it from the
proposed variant) learns the value function in a self-supervised manner, with
a loss function composed of a PDE violation loss and a boundary condition loss
with a trade-off parameter $\lambda$:

$\displaystyle
h\left(x_{i},t_{i};\theta\right)=h_{pde}\left(x_{i},t_{i};\theta\right)+\lambda
h_{bc}\left(x_{i},t_{i};\theta\right),$ (13) $\displaystyle
h_{pde}\left(x_{i},t_{i};\theta\right)=\|\min\left\\{D_{t}V_{\theta}\left(x_{i},t_{i}\right)+H\left(x_{i},t_{i}\right),\right.$
$\displaystyle\qquad\qquad\left.l\left(x_{i}\right)-V_{\theta}\left(x_{i},t_{i}\right)\right\\}\|,$
$\displaystyle
h_{bc}\left(x_{i},t_{i};\theta\right)=\left\|V_{\theta}\left(x_{i},t_{i}\right)-l\left(x_{i}\right)\right\|\mathds{1}\left(t_{i}=T\right).$

Here, $h_{pde}$ corresponds to how consistent the value function propagation
is with the HJI-VI, whereas $h_{bc}$ attempts to impose correct value function
approximation at the terminal time. Even though DeepReach is shown to be
effective for high-dimensional problems, the solution quality depends heavily
on the imposition of $h_{bc}$ and $\lambda$, as we demonstrate later in this
paper. Our goal is to reduce these dependencies in order to obtain a more
accurate safety value function via DeepReach.

##  V Our Approach: Exact Imposition of Boundary Constraints (ExactBC)

As discussed earlier, the performance of DeepReach depends heavily on the
imposition of boundary constraints, which in turn, depends on the
hyperparameter $\lambda$ in (13). This becomes particularly challenging when
the target set, and hence the boundary condition, is complex. To mitigate
these limitations, we propose a novel variant of DeepReach (referred to as
ExactBC for Exact Boundary Conditions). The key innovation of the variant is
to ensure that the learned value function inherently satisfies the time
boundary condition of (10) for all states at time $t=T$.

###  V-A Value Function Approximation

We approximate the overall value function as:

$V_{\theta}(x,t)=l(x)+g_{\theta}(x,t),$ (14)

where $g_{\theta}(x,t)$ can be any function parameterized by $\theta$ such
that the $\forall x,g_{\theta}(x,T)=0$. The above structure guarantees that
$\forall x,V_{\theta}(x,T)=l(x)$, thereby, ensuring that the terminal time
boundary constraints are exactly satisfied. In this paper, we choose
$g_{\theta}(x,t)$ as the product of the time factor, $(T-t)$, and the function
$O_{\theta}(x,t)$ is given by a neural network (NN) with parameters $\theta$.
Thus, the overall value function can be represented as:

$V_{\theta}(x,t)=l(x)+(T-t)*O_{\theta}(x,t).$ (15)

Note that the above structure inherently satisfies the boundary condition
(i.e., the safety constraint). An interesting consequence of choosing this
structure is that the neural network needs to minimize only a single loss
function (corresponding to the HJI-VI) as the boundary condition is already
exactly imposed, regardless of what the network learns. This is in contrast
with DeepReach, where the neural network was required to minimize the weighted
sum of two loss terms as discussed in (13). Specifically, the new loss
function to learn the NN parameters is given by:

$\displaystyle
h\left(x_{i},t_{i};\theta\right)=h_{pde}\left(x_{i},t_{i};\theta\right)$ (16)
$\displaystyle=\|\min\left\\{D_{t}V_{\theta}\left(x_{i},t_{i}\right)+H\left(x_{i},t_{i}\right),\right.$
$\displaystyle\qquad\qquad\left.l\left(x_{i}\right)-V_{\theta}\left(x_{i},t_{i}\right)\right\\}\|$
$\displaystyle=\|\min\left\\{(T-t_{i})D_{t}O_{\theta}\left(x_{i},t_{i}\right)-O_{\theta}\left(x_{i},t_{i}\right)+H\left(x_{i},t_{i}\right),\right.$
$\displaystyle\qquad\qquad\left.l\left(x_{i}\right)-V_{\theta}\left(x_{i},t_{i}\right)\right\\}\|,$
$\displaystyle H\left(x_{i},t_{i}\right)=$
$\displaystyle\qquad\max_{u}\min_{d}\langle(T-t_{i})\nabla O(x_{i},t)+\nabla
l(x_{i}),f(x_{i},u,d)\rangle.$

An immediate advantage of optimizing only over the PDE loss is the elimination
of training uncertainty stemming from the choice of tradeoff hyperparameter,
$\lambda$. This also improves the convergence of stochastic gradient descent
during training [22]. Secondly, for many dynamical systems, the boundary value
function can be very complex to learn, making the learning difficult for
vanilla DeepReach. This representation mitigates this challenge by implicitly
embedding the boundary value function in the parameterized value function,
thereby, eliminating the need to learn it explicitly. Additionally, in the
proposed method, the boundary value serves as a static and accurate ground-
truth signal that anchors and stabilizes the self-supervised learning process,
whereas, in DeepReach, the learned boundary value dynamically varies during
training causing fluctuations in the value function throughout the time
horizon which can cause training instabilities, especially for systems with
complex boundary functions.

###  V-B Training Scheme

Since the solution of HJI-VI essentially propagates (backwards) over time,
i.e., the value function at time $t$ depends on the value function at time
$t+\Delta t$, similar to DeepReach, we adopt a curriculum training scheme over
the time horizon to train the neural network. Specifically, the time interval
for data sampling grows linearly from $[T,T]$ to $[0,T]$ during training. Such
curriculum training scheme allows the model to learn accurate value function
approximation starting from the terminal boundary conditions and slowly
propagating the value function backwards using the HJI-VI.

Furthermore, one key takeaway from (16) is that the terminal time gradient of
the value function at the beginning of the curriculum training depends on the
parameter initialization of the DNN, as shown in (17).

$\displaystyle D_{t}V_{\theta}\left(x,t\right)$ $\displaystyle=(T-t)\cdot
D_{t}O_{\theta}\left(x,t\right)-O_{\theta}\left(x,t\right)$ (17)
$\displaystyle\approx-
O_{\theta}\left(x,t\right),\quad\text{for}~{}~{}t=(T-\epsilon),\epsilon\approx
0.$

This implies that poor weight initilaizations of the DNN can adversely impact
the terminal time gradients, which may drive the optimization process towards
a bad local minimum. To address this issue, we introduce a pretraining
strategy for the neural network before performing the curriculum training
using the following loss:

$h_{pretrain}\left(x_{i},T;\theta\right)=\left\|O_{\theta}\left(x_{i},T\right)\right\|.$
(18)

It can be easily inferred from (18) that the pretraining phase aims to
simultaneously suppress the neural network output and the time gradients at
terminal time. The goal of this idea is to smooth out the gradients and
terminal boundary value function to mitigate the training instabilities that
can stem from abnormally large initial values and gradients of the NN. In
addition to this, it also makes the learned value function agnostic to the
DNN’s stochastic parameter initialization, thereby granting more control to
the training phase. It is to be mentioned that both the pretraining and
training phases utilize only a single loss function. The pretraining phase
employs the pretraining loss detailed in Equation (18), while the training
phase utilizes the training loss derived in Equation (16).

##  VI Experiments

In this section, we conduct a comparative study on the performance of the
proposed model and vanilla DeepReach on two reachability problems: a rocket
landing reach problem and a three-vehicle collision avoidance problem.

###  VI-A Baselines and Training Details

We benchmark the proposed ExactBC model against vanilla DeepReach and the
DiffModel variant of DeepReach. The description of each variant is as follows:

  1. 1.

Vanilla DeepReach: It is the original version of DeepReach detailed in Section
IV-B.

  2. 2.

DiffModel: The DiffModel variant of DeepReach learns the residual between the
value function and boundary function instead of directly learning the value
function. The value function structure for this variant can be given as
follows:

$\displaystyle V_{\theta}(x,t)=l(x)+O_{\theta}(x,t)$ (19)

where, $O_{\theta}(x,t)$ is the function learned by the neural network. While
DiffModel does not impose the boundary condition exactly, it alleviates the
learning burden on the neural network as the NN now only needs to learn the
residual value function.

  3. 3.

ExactBC with pretraining: It is the proposed variant coupled with the
pretraining strategy introduced in Section V-B.

  4. 4.

ExactBC without pretraining: It is the proposed variant without any
pretraining. We compare against this variant to understand the efficacy of the
proposed pretraining scheme.

For all our case studies and variants, we use a 3-layer, fully-connected,
feedforward neural network with a hidden layer size of 512. For each method,
we performed curriculum training for 100k iterations using the Adam optimizer
with a learning rate of $2\times 10^{-5}$. In each training iteration, 65000
data points are uniformly sampled from the (normalized) state space
(normalized to [-1,1]). For each case study and variant, we ran the experiment
with five different initial random seeds to capture the training variance.

###  VI-B Evaluation Metric

In general, the BRT provided by DeepReach is only a candidate safe set since
there might be learning errors [27]. Thus, it might be hard to compare BRTs
obtained by different variants. Although level-set methods are able compute
BRTs with high numerical accuracy, they are not applicable to high-dimensional
reachability problems for gauging the accuracy of learned solutions. To
compare different learned BRTs, we use the formal verification strategy
proposed in [27] that establishes an error bound on the DeepReach solution via
scenario optimization [28], which in turn allows us to obtain a high-
confidence safe set using DeepReach. We run this verification scheme on
different learned BRTs to first obtain a provably safe set and then employ the
volume fraction of the provably safe set (over the volume of the entire state
space) as the evaluation metric to compare different variants. Thus, the
higher the fraction of the provably safe set, the better the quality of the
learned solution.

We now provide further details about the verification method and how it is
used in our work. The error metric, $\delta_{\tilde{V},\tilde{\pi}}$, for
correcting the learned value function, $\tilde{V}(x,t)$, is defined as the
maximum learned value among all unsafe states under the induced safe policy
$\tilde{\pi}(x,t)$

$\delta_{\tilde{V},\tilde{\pi}}=\max_{x\in\mathcal{X}}\\{\tilde{V}(x,0):\min_{\tau\in[0,T]}l\left(\xi_{x,T}^{\tilde{\pi}}(\tau)\right)\leq
0\\},$ (20)

Authors in [27] propose a scenario optimization-based method to compute a
probabilistic bound on $\delta$ using a finite number of state samples $N$.
Once this error bound is computed, the super-$\delta$ level set of the learned
value function, $\left\\{x:x\in
X,\tilde{V}(x,0)>\delta_{\tilde{V},\tilde{\pi}}\right\\}$, is provably safe
under the policy $\tilde{\pi}(x,t)$. For a detailed explanation of the
technique, we refer the interested readers to [27].

For the scenario optimization, we used $\beta=10^{-16}$ and $\epsilon=0.001$.
The implication of these values is that we are $1-10^{-16}$ confident that at
least $99.9\%$ of the recovered set (i.e., the super-$\delta$ level set) is
indeed safe. Using the Scenario Optimization Verification Theorem detailed in
[27] [29], the aforementioned values of $\beta$ and $\epsilon$ yield a value
of $N=75683$ for the number of required testing samples. It is to be mentioned
that throughout the paper, the learned and recovered volume of any BRT is
expressed as the fraction of the state space volume it occupies.

Figure 1: (From Left to Right) Trained and Recovered BRT slices for (a)
Vanilla DeepReach, (b) DiffModel, (c) ExactBC with pretraining, and (d)
ExactBC without pretraining. These slices correspond to
$v_{x}=150,v_{y}=-100,\theta=0,\omega=0$. Vanilla DeepReach is not able to
recover any volume that is provably safe, while DiffModel is only able to
recover a small fraction of the volume. On the other hand, ExactBC is able to
recover a significant portion of the learned volume, which illustrates the
increase in learning accuracy over the other baselines

###  VI-C Rocket Landing

The first example we consider is the rocket landing system, our running
example from Section III. The system parameters being used are $k=0.3$ and
$g=9.81$. The range of torque controls $\tau_{1},\tau_{2}$ is $[-250,250]$.
The rectangular landing zone is of side length 20 centered around the origin.
Hence, the target set is given as:

$\mathcal{L}=\\{x,y:|x|\leq 20,y\leq 20\\}.$ (21)

For this example, we used 100K pertaining iterations for all the variants that
have a pretraining phase. Following the pretraining, we performed curriculum
training for 100K iterations. The rest of the training details are as
mentioned in Sec. VI-A. Once trained, the value functions were corrected using
the method described in Section VI-B.

Fig. 1 shows the $xy$ slices of the learned BRT (yellow) as well as the slice
of the recovered BRT after verification (cyan) for different variants. We also
illustrate the recovered volume for each model across the five seeds in Fig.
2. As evident from these figures, the vanilla DeepReach completely fails on
this problem and is not able to certify any part of the learned volume for any
of the five seeds. This is because of high learning errors in certain parts of
the state space, which leads to a very conservative $\delta$ bound. The
DiffModel shows only minor improvement over the vanilla version as it is able
to recover an average volume fraction of 0.115 (out of a learned volume of
0.4). Its recovered volume also has a high standard deviation of 0.063 across
the five seeds, making it very susceptible to the NN’s initialization and,
consequently, unreliable. In contrast, the proposed variant, with and without
pretraining, can recover, on average, a provably safe volume of 0.33. This
indicates the utility of imposing exact boundary conditions within the
DeepReach framework. Furthermore, the variance of the proposed approach is
significantly lower, indicating a consistent performance. This is particularly
the case when the proposed pretraining phase is used, which further helps
stabilize the training for different NN initializations.

Figure 2: The average fraction of state space volume recovered across
different seeds. ExactBC consistently performs better than Vanilla DeepReach
and DiffModel both in terms of average recovered volume and observed training
variance.

Although the boundary condition of this reach problem is relatively simple,
the learning accuracy of the boundary condition is still essential for
achieving high-quality results. From Fig. 3a, we observe that the learned
value of vanilla DeepReach at $t=T$ is inaccurate and larger than the actual
target set. This can be attributed to vanilla DeepReach softly imposing the
boundary constraints. This, in turn, results in DeepReach learning a larger
but incorrect BRT, as shown in Fig. 3c. On the other hand, with the exact
imposition of boundary conditions, DeepReach is able to maintain the correct
target set and learn a more accurate BRT.

(a)

(b)

(c)

(d)

Figure 3: The slice of the boundary value function learned by (a) Vanilla
DeepReach and (b) ExactBC. The corresponding value function slices at $t=0$
are shown in (c) and (d), respectively. The boundary function learned by
Vanilla DeepReach is erroneous, leading to an inaccurate value function and
the BRT.

###  VI-D Three-Vehicle Collision Avoidance

We next consider a 9D three-vehicle collision avoidance problem. The three-
vehicle collision avoidance system involves three independent cars trying to
avoid colliding with each other. For each car, the states include its position
$[x,y]$ and heading $\theta$. The control is one-dimensional steering control
$u_{i}\in[u_{min},u_{max}]$, i.e., the yaw rate of the vehicle. The velocity,
$v$, of all three cars is equal and constant. The dynamics of each car are
given as:

$\displaystyle\quad\dot{x_{i}}=vcos\theta_{i},\quad\dot{y_{i}}=vsin\theta_{i},\quad\dot{\theta_{i}}=u_{i}\quad
i=1,2,3.$ (22)

The target set in this case is given as the set of states where any two
vehicles are in close proximity of each other and can be formulated as:

$\mathcal{L}=\\{x:\min\\{d(C_{1},C_{2}),d(C_{2},C_{3}),d(C_{1},C_{3})\\}\leq
R\\}$ (23)

where, $d(C_{i},C_{j})$ represents the distance between the cars $i,j$. For
our experiment, we choose the system parameters as $v=0.6~{}m/s$,
$u_{min}=-1.1~{}rad/s$, $u_{max}=1.1~{}rad/s$ and $R=0.25~{}m$. We used 60K
pertaining iterations for all variants with a pretraining phase. Following the
pretraining, we performed curriculum training for 100K iterations. The rest of
the training details are as mentioned in Sec. VI-A.

Fig. 5 shows the trained and recovered BRT slices for different variants. The
vanilla DeepReach solution yields an average recoverable volume of 0.627 with
a standard deviation of 0.047 across the five seeds. The DiffModel’s
performance is also very similar to vanilla DeepReach as it is able to recover
an average volume of 0.56 across all five seeds. However, Fig. 4 shows that it
has a significantly high standard deviation of 0.276 which can be attributed
to its exceptionally poor performance for one of the seeds where it failed to
recover any volume. This, again, validates the hypothesis even though
DiffModel typically outperforms the vaniall DeepReach, due to the soft
imposition of the boundary constraints, it remains sensitive to the DNN
initialization and hence, is unreliable. In contrast, the proposed variant,
coupled with the suggested pertaining scheme, yields a significantly higher
average recovered volume of 0.742 with a standard deviation of 0.02.
Additionally, the proposed variant without pretraining yields a recovered
volume of 0.726 with a standard deviation of 0.048 across the five seeds. This
case study clearly demonstrates that the proposed variant improves over the
vanilla DeepReach, even for cases where the boundary function isn’t
necessarily very complex.

Figure 4:  ExactBC, on average, is able to recover a much higher fraction of
state space volume than DiffModel and Vanilla DeepReach. ExactBC with
pretraining shows the least training variance illustrating the advantage of
the introduced pretraining strategy aimed at minimizing the performance
dependence on neural network’s weight initialization.

From Fig. 4, we can make an interesting observation that the proposed variant
when used without pretraining demonstrates a relatively higher variance
compared to when it is pretrained. This can be attributed to poor
initialization in some of the seeds resulting in lower recovered volume for
those seed compared to other seeds. This illustrates the need for the devised
pretraining strategy as it reduces the variance and stabilizes the results
across all seeds by minimizing performance dependence on the parameter
initialization.

(a)

(b)

(c)

(d)

Figure 5: Trained and Recovered BRT slices for (a) Vanilla DeepReach (b)
DiffModel (c) Proposed Variant with pretraining (d) Proposed Variant without
pretraining. These slices correspond to the shown starting configurations of
the first two aircraft and the start heading of the third aircraft is shown in
the inlet (i.e.,
$x_{2}=-0.4,y_{2}=0.0,x_{3}=0.4,y_{3}=0.0,\theta_{1}=-\pi,\theta_{2}=\frac{\pi}{4},\theta_{3}=\frac{3\pi}{4}$).
ExactBC is able to recover more volume than Vanilla DeepReach and DiffModel.

##  VII Conclusion and Future Work

In this work, we propose a novel variant of DeepReach with the intrinsic
property that time boundary conditions are exactly imposed throughout the
learning process. This allows us to mitigate the learning inaccuracies
introduced by imposing boundary conditions as soft constraints. In addition to
this, the proposed variant learns the value function by optimizing over one
single PDE loss, thereby eliminating the need for correctly weighing different
losses. This reduces the hyperparameter space and, consequently, does away
with the errors induced by the incorrect weighting of different loss terms. We
also introduce a pretraining strategy that, when coupled with the proposed
strategy, decreases the dependence of performance on the NN’s parameter
initialization and stabilizes the training process. We evaluate our approach
on high-dimensional rocket landing and three vehicle collision avoidance
problems which existing variants of DeepReach struggle with. The proposed
approach shows significant improvement over other baselines both in terms of
accuracy and generalizability across different learning seeds.

Future works include investigating the use of other functions in (14) to
exactly impose the boundary conditions and their corresponding effect on the
learning of the PDE solution. It would also be interesting to apply the
proposed variant to reach-avoid settings that inherently have a complex
boundary condition. Finally, we will holistically evaluate the proposed
variant on other reachability problems to verify its broader applicability.

## References

  * [1] S. Bansal, M. Chen, S. Herbert, and C. J. Tomlin, “Hamilton-jacobi reachability: A brief overview and recent advances,” in _IEEE 56th Annual Conference on Decision and Control (CDC)_ , 2017, pp. 2242–2253.
  * [2] I. M. Mitchell, A. M. Bayen, and C. J. Tomlin, “A time-dependent hamilton-jacobi formulation of reachable sets for continuous dynamic games,” _IEEE Transactions on automatic control_ , vol. 50, no. 7, pp. 947–957, 2005.
  * [3] J. Lygeros, “On reachability and minimum cost optimal control,” _Automatica_ , vol. 40, no. 6, pp. 917–927, 2004.
  * [4] J. F. Fisac, M. Chen, C. J. Tomlin, and S. S. Sastry, “Reach-avoid problems with time-varying dynamics, targets and constraints,” in _Proceedings of the 18th international conference on hybrid systems: computation and control_ , 2015, pp. 11–20.
  * [5] W. Liao, T. Liang, P. Xiong, C. Wang, A. Song, and P. X. Liu, “An improved level set method for reachability problems in differential games,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , 2024.
  * [6] S. Bansal and C. J. Tomlin, “Deepreach: A deep learning approach to high-dimensional reachability,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pp. 1817–1824.
  * [7] V. Sitzmann, J. Martel, A. Bergman, D. Lindell, and G. Wetzstein, “Implicit neural representations with periodic activation functions,” in _Advances in Neural Information Processing Systems, 2020_ , H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, Eds., vol. 33. Curran Associates, Inc., pp. 7462–7473.
  * [8] M. Raissi, P. Perdikaris, and G. E. Karniadakis, “Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations,” _Journal of Computational physics_ , vol. 378, pp. 686–707, 2019.
  * [9] J. Darbon and S. Osher, “Algorithms for overcoming the curse of dimensionality for certain hamilton–jacobi equations arising in control theory and elsewhere,” _Research in the Mathematical Sciences_ , vol. 3, no. 1, p. 19, 2016.
  * [10] Y. T. Chow, J. Darbon, S. Osher, and W. Yin, “Algorithm for overcoming the curse of dimensionality for time-dependent non-convex hamilton–jacobi equations arising from optimal control and differential games problems,” _Journal of Scientific Computing_ , vol. 73, pp. 617–643, 2017.
  * [11] D. Lee and C. J. Tomlin, “A hopf-lax formula in hamilton–jacobi analysis of reach-avoid problems,” _IEEE Control Systems Letters_ , vol. 5, no. 3, pp. 1055–1060, 2020.
  * [12] S. Coogan and M. Arcak, “Efficient finite abstraction of mixed monotone systems,” in _Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control_ , 2015, pp. 58–67.
  * [13] M. Chen and C. J. Tomlin, “Exact and efficient hamilton-jacobi reachability for decoupled systems,” in _54th IEEE Conference on Decision and Control (CDC)_ , 2015, pp. 1297–1303.
  * [14] C. He, Z. Gong, M. Chen, and S. Herbert, “Efficient and guaranteed hamilton–jacobi reachability via self-contained subsystem decomposition and admissible control sets,” _IEEE Control Systems Letters_ , vol. 7, pp. 3824–3829, 2023.
  * [15] J. Darbon, G. P. Langlois, and T. Meng, “Overcoming the curse of dimensionality for some hamilton–jacobi partial differential equations via neural network architectures,” _Research in the Mathematical Sciences_ , vol. 7, pp. 1–50, 2020.
  * [16] K. Niarchos and J. Lygeros, “A neural approximation to continuous time reachability computations,” in _Proceedings of the 45th IEEE Conference on Decision and Control_ , 2006, pp. 6313–6318.
  * [17] B. Djeridane and J. Lygeros, “Neural approximation of pde solutions: An application to reachability computations,” in _Proceedings of the 45th IEEE Conference on Decision and Control_ , 2006, pp. 3034–3039.
  * [18] V. Rubies-Royo and C. Tomlin, “Recursive regression with neural networks: Approximating the hji pde solution,” _arXiv preprint arXiv:1611.02739_ , 2016.
  * [19] F. Jiang, G. Chou, M. Chen, and C. J. Tomlin, “Using neural networks to compute approximate and guaranteed feasible hamilton-jacobi-bellman pde solutions,” _arXiv preprint arXiv:1611.03158_ , 2016.
  * [20] N. Sukumar and A. Srivastava, “Exact imposition of boundary conditions with distance functions in physics-informed deep neural networks,” _Computer Methods in Applied Mechanics and Engineering_ , vol. 389, p. 114333, 2022.
  * [21] S. Wang, Y. Teng, and P. Perdikaris, “Understanding and mitigating gradient pathologies in physics-informed neural networks,” _arXiv preprint arXiv:2001.04536_ , 2020.
  * [22] J. Chen, R. Du, and K. Wu, “A comparison study of deep galerkin method and deep ritz method for elliptic problems with different boundary conditions,” _arXiv preprint arXiv:2005.04554_ , 2020.
  * [23] N. Saad, G. Gupta, S. Alizadeh, and D. C. Maddix, “Guiding continuous operator learning through physics-based boundary constraints,” _arXiv preprint arXiv:2212.07477_ , 2022.
  * [24] Z. Li, N. Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, A. Stuart, and A. Anandkumar, “Fourier neural operator for parametric partial differential equations,” _arXiv preprint arXiv:2010.08895_ , 2020.
  * [25] Z. Li, H. Zheng, N. Kovachki, D. Jin, H. Chen, B. Liu, K. Azizzadenesheli, and A. Anandkumar, “Physics-informed neural operator for learning partial differential equations,” _arXiv preprint arXiv:2111.03794_ , 2021.
  * [26] I. E. Lagaris, A. Likas, and D. I. Fotiadis, “Artificial neural networks for solving ordinary and partial differential equations,” _IEEE transactions on neural networks_ , vol. 9, no. 5, pp. 987–1000, 1998.
  * [27] A. Lin and S. Bansal, “Generating formal safety assurances for high-dimensional reachability,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , pp. 10 525–10 531.
  * [28] M. Campi and S. Garatti, “A sampling-and-discarding approach to chance-constrained optimization: Feasibility and optimality,” _Journal of Optimization Theory and Applications_ , vol. 148, pp. 257–280, 02 2011.
  * [29] M. Campi, S. Garatti, and M. Prandini, “The scenario approach for systems and control design,” _Annual Reviews in Control_ , vol. 33, pp. 149–157, 12 2009.