smallalign  $\displaystyle\BODY$

# Learning Certifiably Robust Controllers Using Fragile Perception

Dawei Sun1, Negin Musavi1, Geir Dullerud1, Sanjay Shakkottai2, and Sayan
Mitra1 1Dawei Sun, Negin Musavi, Geir Dullerud, and Sayan Mitra are with
Coordinated Science Laboratory, University of Illinois, Urbana, IL 61801, USA
{daweis2, nmusavi2, dullerud<EMAIL_ADDRESS>Shakkottai is with
the Department of Electrical and Computer Engineering, University of Texas at
Austin,, Austin, TX 78712, USA<EMAIL_ADDRESS>
###### Abstract

Advances in computer vision and machine learning enable robots to perceive
their surroundings in powerful new ways, but these perception modules have
well-known fragilities. We consider the problem of synthesizing a safe
controller that is robust despite perception errors. The proposed method
constructs a state estimator based on Gaussian processes with input-dependent
noises. This estimator computes a high-confidence set for the actual state
given a perceived state. Then, a robust neural network controller is
synthesized that can provably handle the state uncertainty. Furthermore, an
adaptive sampling algorithm is proposed to jointly improve the estimator and
controller. Simulation experiments, including a realistic vision-based lane
keeping example in CARLA, illustrate the promise of the proposed approach in
synthesizing robust controllers with deep-learning-based perception.

##  I Introduction

Advances in computer vision and machine learning enable robots to perceive
their surroundings in powerful new ways, but these perception modules have
well-known fragilities. The decision boundaries for classifiers are vulnerable
to adversarial inputs [1]. ML models are often overconfident, and do not know
what they do not know [2]. Biases in training data can bleed into biased
algorithms for pedestrian detection that do not work well for dark-skinned
people [3]. Embodied in robots or autonomous vehicles, like driver-assistance
systems, robotic tractors, and delivery drones, the perception module
fragilities can trigger safety violations.

We address the problem of designing robust controllers that tolerate and
compensate for the fragilities of the perception modules they use. Simply put,
how to design reliable controllers that use unreliable perception? We study
the fundamental control task for a robot to maintain a given invariant. For
example, a drone has to stay within a geo-fenced area, or a car has to stay
within the lanes. The system uses computer vision-based perception. There are
several technical challenges in rigorously addressing this problem. First,
unlike the typical i.i.d. model of sensor noise in control theory textbooks,
the output from the perception modules here may have wildly biased, state-
dependent errors. Secondly, leaving aside the issue of perception errors, even
the task of designing an invariance-preserving controller for a nonlinear,
(and possibly incompletely known) dynamical system is an actively researched
topic [4, 5, 6, 7, 8, 9]. Finally, certifying the correctness or safety of a
given control system is also another challenge actively pursued by the formal
verification and the control theory communities.

In this paper, the perception module is modeled as a function that takes in
the actual state and generates a noisy copy of it, i.e., the perceived state.
In order to design a feedback controller that only has access to the perceived
state to maintain safety, we utilize Gaussian processes (GP) with input-
dependent noises to construct a set-valued state estimator from a data set of
input-output pairs of the perception module, such that given a perceived state
it computes a high-confidence set for the actual state. We then design a
learning algorithm for synthesizing a controller that takes in the high-
confidence set from the state estimator and computes the control signal. A
barrier function is jointly synthesized with the controller, which provides
theoretical guarantee on the safety of the resulting closed-loop system.
Inspired by [10], the original theory of control barrier functions is extended
to handle uncertainty in the state. However, the synthesis could fail due to
the large uncertainty of the GP-based state estimator. In this case, new
samples from the perception module will be collected to improve the state
estimator until a satisfying controller and certificate are found. An adaptive
sampling algorithm is proposed to reduce the number of samples required in
this process.

We evaluated the proposed approach on three benchmark systems including two
simpler ones with synthetic perception errors and one more realistic one in
the CARLA simulator with a deep-learning-based perception module. Experimental
results clearly verified that with the proposed approach, one can synthesize
controllers that are robust to perception errors, and the proposed adaptive
sampling algorithm indeed improves the sample efficiency.

Our main contributions are threefold. (1) We formulate the problem of state
estimation with uncertainty bounds as a GP regression problem with input-
dependent noises, and show that indeed, this formulation can be effective for
realistic deep-learning-based perception modules. (2) We design a learning-
based algorithm that models the controller and the certificate as neural
networks, and show how state estimation uncertainty bounds can be used for
synthesizing controllers that are certifiably robust to perception
fragilities. (3) We propose an adaptive sampling approach to reduce the number
of samples required to learn such a certifiable controller.

##  II Related work

Perception-based control. As new types of sensors emerge, the problem of
integrating these sensors and the corresponding perception module into the
control pipeline has attracted interest. In recent works [11, 12, 13], the
perception-based controller has been studied to enable aggressive control for
drones. Further, data-driven approaches have been developed by the machine
learning community. For example, imitation learning [14] and reinforcement
learning [15] have been used to learn vision-based control policies. However,
such purely data-driven approaches do not provide any safety guarantees. In a
series of recent works by Dean et al., the authors studied the robustness
guarantees of perception-based control algorithms. In [16], the authors
proposed a perception-based controller synthesis approach for linear systems
and provided a theoretical analysis. In [10], the authors proposed robust
barrier functions which provide an approach for synthesizing safety-critical
controllers under uncertainty of the state. In our approach, such a robust
barrier function is used as a component of the estimation and control
pipeline.

Analysis of systems with ML-based modules. As machine learning becomes the
dominant approach in autonomy, analysis of such ML-based systems attracts more
and more interest. VerifAI [17] provides a complete framework for analyzing
autonomous systems with ML modules in the loop. In [18], the authors study the
safe abstraction of systems with ML-based perception modules. In [19], the
reachability of a closed-loop system with a neural controller has been
studied. In [20], a data-driven reachability analysis tool is developed, which
works for ML-based systems.

Certifiable controller synthesis. Recently, the idea of jointly synthesizing
certificates and controllers with machine learning has been popular. Unlike
purely data-driven approaches, such approaches can draw guarantees on the
performance of the synthesized controller. For example, control Lyapunov
functions [21], contraction metrics [7], and barrier functions [22] have all
been studied under this setting.

##  III Preliminaries and problem setup

Figure 1: Overview of the system and the learning algorithm.

We denote by ${\mathbb{R}}$ and ${\mathbb{R}}^{\geq 0}$ the set of real and
non-negative real numbers respectively. Unless otherwise stated, $x^{(i)}$
denotes the $i$-th element of vector $x$. Similarly, for a vector-valued
function $f:{\mathbb{R}}^{n}\mapsto{\mathbb{R}}^{m}$,
$f^{(i)}:{\mathbb{R}}^{n}\mapsto{\mathbb{R}}$ is its $i$-th component. For a
vector $x\in{\mathbb{R}}^{n}$, $\mathop{\mathrm{diag}}(x)$ is the $n\times n$
diagonal matrix generated from $x$. Also, let
$\exp(x)=[\exp(x^{(i)}),\cdots,\exp(x^{(n)})]$. For a point
$c\in{\mathbb{R}}^{n}$ and a positive definite matrix
$Q\in{\mathbb{R}}^{n\times n}$, denote
$\mathcal{E}\left(c,Q\right):=\\{x\in{\mathbb{R}}^{n}:x^{\intercal}Qx\leq
1\\}$ to be the ellipsoid at $c$ with $Q$ defining its shape. Further, let
$\mathrm{center}(A)$ be the center of an ellipsoid $A$. For a set ${\cal S}$,
we denote $\mathtt{Unif}\left({\cal S}\right)$ the uniform distribution over
${\cal S}$, $2^{\cal S}$ the power set of ${\cal S}$, and $\mathbb{I}_{\cal
S}$ the indicator function generated from this set, which is a binary-valued
function such that $\mathbb{I}_{\cal S}(s)=1$ iff. $s\in{\cal S}$. Let
$\mathtt{ReLU}$ be the Rectified Linear Unit (ReLU) function. That is,
$\mathtt{ReLU}(x)=x$ if $x>0$, otherwise, $\mathtt{ReLU}(x)=0$. An extended
class ${\cal K}_{\infty}$ function is a continuous function
$\alpha:{\mathbb{R}}\mapsto{\mathbb{R}}$ that is strictly increasing with
$\alpha(0)=0$ and $\lim_{r\rightarrow\infty}\alpha(r)=\infty$.

###  III-A Dynamical systems

We consider dynamical systems of the form

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

where $x\in{\cal X}\subseteq{\mathbb{R}}^{n}$ is the state and
$u\in\mathcal{U}\subseteq{\mathbb{R}}^{m}$ is the control input. Here, ${\cal
X}$ and $\mathcal{U}$ are the state space and the control input space, which
are compact sets. We assume that
$f:{\mathbb{R}}^{n}\times{\mathbb{R}}^{m}\mapsto{\mathbb{R}}^{n}$ is a smooth
function. A feedback controller is a function $\pi:{\cal X}\mapsto{\cal U}$,
which can be plugged into the dynamical system in Eq. (1) and results in an
autonomous system $\dot{x}=f(x,\pi(x))$. A function $\xi:{\cal
X}\times{\mathbb{R}}^{\geq 0}\mapsto{\cal X}$ is called the solution function
of the autonomous system if for all initial states $x_{0}\in{\cal X}$,
$\xi(x_{0},\cdot)$ satisfies Eq. (1). Given an initial state $x_{0}$, the
function of time $\xi(x_{0},\cdot)$ is called a trajectory of the system.

In this paper, we only assume input-output access to the function $f$, i.e.,
$f(x,u)$ can be computed given the state $x$ and control input $u$. This
enables the application in practical situations where a closed-form
description of $f$ is unavailable or unwieldy. For example, $f$ could be a
deep neural network model of a complicated robot.

###  III-B Imperfect perception functions

We study autonomous systems equipped with sensors and perception modules,
which together constitute a perception function $s:{\cal X}\mapsto{\cal X}$.
That is, it takes in the actual state $x\in{\cal X}$ and produces a noisy
observation $\hat{x}:=s(x)$ which is called the perceived state. The
perception function $s$ is a complex composite of the environment, the sensor,
and the perception module, for instance, a deep convolutional neural network,
and we treat it as a black box function. We need not have the closed-form
expression of the perception function, instead we only need input-output
access to it, i.e., given a state $x$, it is possible to run the perception
function and compute the perceived state $\hat{x}$. However, this evaluation
process is expensive and should be called as few times as possible. In this
paper, we do not assume the smoothness or invertibility of function $s$. The
perception function $s$ could map two states to the same perceived state, in
which case, recovering the exact actual state from the perceived state becomes
impossible, and the inverse of the perception function $s$ should be a set-
valued function.

###  III-C The synthesis problem

We first introduce the notion of invariant sets.

######  Definition 1 (Invariant sets).

Consider an autonomous system $\dot{x}=f(x)$, where $x\in{\cal X}$. A set
${\cal C}\subseteq{\cal X}$ is called an invariant set of the autonomous
system, if starting from any initial state in ${\cal C}$, a trajectory always
stays in ${\cal C}$, i.e., $x_{0}\in{\cal C}\implies\forall
t\in{\mathbb{R}}^{\geq 0},\xi(x_{0},t)\in{\cal C}$.

The notion of invariant sets is widely used in safety-critical synthesis. For
example, if one can ensure that the user-defined safe set is invariant to the
system, then starting from a safe state, the system will always maintain
safety.

The synthesis problem considered in this paper is as shown in Figure 1. The
goal is to synthesize a module that computes control input $u$ for the
dynamical system such that after plugging this module into the dynamical
system, a user-defined set ${\cal S}\subset{\cal X}$ is invariant to the
closed-loop system. However, different from an ordinary feedback controller,
this module does not have access to the actual state $x$ of the system.
Instead, it only has access to a noisy version of the actual state, which is
the perceived state $\hat{x}$. Formally, we have the following problem
definition.

######  Problem (Synthesis problem).

Given a dynamical system as in Eq. (1), a perception function $s:{\cal
X}\mapsto{\cal X}$, and a target invariant set ${\cal S}\subset{\cal X}$, the
synthesis problem is to find a function $c:{\cal X}\mapsto{\cal U}$, such that
${\cal S}$ is indeed invariant with respect to the closed-loop system, i.e.,

$\dot{x}=f(x,c(s(x))).$

Our proposed approach to solving the above problem uses Gaussian processes and
certificate-based robust controller synthesis. A GP-based state estimator is
constructed such that given a perceived state $\hat{x}$ it computes a high-
confidence set that contains the actual state $x$ with a high probability.
Then, based on the GP-based state estimator, the approach jointly searches for
a certificate (a control barrier function) and a controller. Input-output
pairs of the perception function are adaptively sampled to improve the GP-
based state estimator until a certificate and a certified controller are
found. With the certificate, we can theoretically show the safety of the
closed-loop system and its robustness to perception error. The approach could
fail to find such a controller in cases where the perception function maps
multiple vastly different states to the same perceived state and the
controller cannot obtain enough information from the perceived state. In this
case, the algorithm outputs a list of perceived states that prevents a
successful controller synthesis. This information can be useful for the user
to improve the perception function.

##  IV Overview of Design Methodology

Our approach decomposes the desired controller function $c$ into two
components, a GP-based state estimator $g:{\cal X}\mapsto 2^{\cal X}$ aiming
to recover a high-confidence set for the actual state from the perceived
state, and a robust controller $\pi:{\cal X}\mapsto{\cal U}$ (See Fig. 1). As
will be shown later, the output of $g$ is an ellipsoid. We call the sequential
combination of the two components as the Estimator and Controller Module
(ECM): $c(\cdot):=\pi(\mathrm{center}(g(\cdot)))$.

This section is organized as follows. In Section IV-A, we will show a GP-based
algorithm for constructing the state estimator $g$. In Section IV-B, we will
show a learning-based algorithm that learns a robust controller $\pi$ given
the state estimator $g$. In Section IV-C, we will combine these two components
and show an algorithm that jointly improves the state estimator and the
controller with adaptive sampling.

###  IV-A Constructing the state estimator

The ECM consists of a state estimator $g$ that estimates the ground-truth
state $x$ from the perceived state $\hat{x}=s(x)$ (Recall Fig. 1). Since $s$
might not be exactly invertible, there might be a set of possible states that
correspond to a perceived state $\hat{x}$. This suggests designing the state
estimator $g$ as a set-valued function. Further, the state estimator $g$ is
constructed from a finite set of samples, we can only expect the estimate
$g(\hat{x})$ will contain the actual state with a high probability. Thus, the
state estimator is designed as $g:{\cal X}\mapsto 2^{\cal X}$ such that for an
arbitrary state $x$, $x\in g(s(x))$ with a high probability. In this paper, we
construct such an estimator using Gaussian processes. Gaussian processes (GP)
are widely used non-parametric models for regression. Here, we view the
problem of estimating $x$ from $\hat{x}$ as a regression problem. One of the
key features of GP regression is that given a query $\hat{x}$, it does not
compute a single-point estimate of $x$ but a posterior distribution of $x$,
from which a high-confidence set containing $x$ can be extracted.

Construction of the data set. The state estimator will be constructed from
samples of the perception function $s$. To this end, a data set ${\cal
D}=\\{(\hat{x}_{j},x_{j})\\}_{j=1}^{N}$ that captures the relationship between
the perceived state and the actual state is constructed. Each sample is
obtained as follows: first, a state $x_{j}\in{\cal X}$ is sampled, then
$\hat{x}_{j}$ is computed as $\hat{x}_{j}=s(x_{j})$.

Setup of the probabilistic model. In order to apply GP regression, we first
set up a probabilistic model to represent the observations in the above data
set. As stated earlier, since $s$ might not be invertible, there might be
multiple $x$’s that correspond to the same $\hat{x}$ in the above data set. To
characterize this property of the data set, we assume there is an input-
dependent observation noise. Specifically, we adopt the following
probabilistic model (Along the lines of [23]).

$x_{j}=s^{+}(\hat{x}_{j})+w_{j},\,j=1,\cdots,N,$

where $s^{+}:{\cal X}\mapsto{\cal X}$ approximately inverts $s$ with an input-
dependent zero-mean noise
$w_{j}\sim\mathcal{N}\left(0,\mathop{\mathrm{diag}}(\exp(z(\hat{x}_{j})))^{2}\right)$.
Here, $z:{\cal X}\mapsto{\mathbb{R}}^{n}$ is the noise-level function, which
characterizes the non-invertibility of the perception function $s$ at
$\hat{x}$. The goal is to learn the function $z$ and the “inverse” function
$s^{+}$ from data. Notice that the perceived state $\hat{x}$ is a noisy copy
of the actual state $x$. Given a perceived state $\hat{x}$, the actual state
$x$ should be close to $\hat{x}$. Thus, instead of estimating $x$ directly, it
should be easier to estimate an error $e$ such that $x=\hat{x}+e$. Here, the
error $e$ is called the perception error. To this end, we decompose $s^{+}$ as
the summation of an identity mapping and a function $r:{\cal X}\mapsto{\cal
X}$ as follows.

$s^{+}(a)=a+r(a),\,\forall a\in{\cal X}.$

Now, we can rewrite our probabilistic model as the relationship between the
perception error and the perceived state,

$e_{j}:=x_{j}-\hat{x}_{j}=r(\hat{x}_{j})+w_{j},\,j=1,\cdots,N,$

Next, we will use GP regression to identify the functions $r$ and $z$. Instead
of identifying the vector-valued functions directly, we assume the components
of these functions are independent and thus apply GP regression to identify
each component individually. Here, we only show the process for the $i$-th
components, i.e., $r^{(i)}$ and $z^{(i)}$. As in common settings in GP
literature, for example [24, Chapter 2.2], we first put priors on functions
$r^{(i)}$ and $z^{(i)}$. Specifically, we assume that $r^{(i)}$ is a sample
from a zero-mean Gaussian process generated by a kernel $k_{r^{(i)}}:{\cal
X}\times{\cal X}\mapsto{\mathbb{R}}^{\geq 0}$ or formally
$r^{(i)}\sim\mathcal{GP}\left(0,k_{r^{(i)}}(\cdot,\cdot)\right)$. That is, we
assume that the function $r^{(i)}$ is realizable by a Gaussian process. As for
the unknown function $z^{(i)}$, we follow the approach in [23] and assume that
$z^{(i)}$ is also a sample from a Gaussian process,
$z^{(i)}\sim\mathcal{GP}\left(0,k_{z^{(i)}}(\cdot,\cdot)\right)$, generated by
a kernel $k_{z^{(i)}}$.

Computation of the posterior distribution. The prior distributions of
$r^{(i)}$ and $z^{(i)}$ are the best estimate we can make before we sample
from the underlying function. However, with the data, this estimate can be
improved by computing the posterior distribution. Specifically, the goal is,
given ${\cal D}$ and a query $\hat{x}_{*}$, to compute the posterior
distribution of $e_{*}^{(i)}$, i.e., $e_{*}^{(i)}|\hat{x}_{*},{\cal D}$. We
adopt the approach in [23], which proceeds as follows. Given data set ${\cal
D}$, we first estimate a standard, homoscedastic111That is, the noise term is
independent of the input. GP. Then, this GP is evaluated on ${\cal D}$, and
the empirical noises are recorded and form a new data set to compute the
posterior of the noise-level function $z^{(i)}$. For more details of the
computation, please refer to [23, Section 4]. Let the posterior of $z^{(i)}$
be $\hat{z}^{(i)}$.

Then, it is a standard result (e.g., please see [25]) that given the data set
${\cal D}$ and a query $\hat{x}_{*}$, the posterior distribution of
$e_{*}^{(i)}$ is still Gaussian, $e_{*}^{(i)}|\hat{x}_{*},{\cal
D}\sim\mathcal{N}\left(\mu^{(i)}(\hat{x}_{*}),(\sigma^{(i)}(\hat{x}_{*}))^{2}\right)$,
where the mean function $\mu^{(i)}$ and standard deviation function
$\sigma^{(i)}$ are defined as follows.

$\mu^{(i)}(\hat{x}_{*})=K(\hat{x}_{*},\hat{X})(K(\hat{X},\hat{X})+K_{N})^{-1}E,\vspace{-0.3cm}$
$\sigma^{(i)}(\hat{x}_{*})=k_{r^{(i)}}(\hat{x}_{*},\hat{x}_{*})+\exp(\hat{z}^{(i)}(\hat{x}_{*}))\\\
-K(\hat{x}_{*},\hat{X})(K(\hat{X},\hat{X})+K_{N})^{-1}K(\hat{x}_{*},\hat{X}),$

where $\hat{X}=[\hat{x}_{1},\cdots,\hat{x}_{N}]^{\intercal}$,
$E=[e^{(i)}_{1},\cdots,e^{(i)}_{N}]^{\intercal}$,
$K_{N}=\mathop{\mathrm{diag}}([\hat{z}^{(i)}(\hat{x}_{1}),\cdots,\hat{z}^{(i)}(\hat{x}_{N})])$.
The matrices are defined as follows.

$K(\hat{x}_{*},\hat{X})\in{\mathbb{R}}^{1\times N},\leavevmode\nobreak\
K(\hat{x},\hat{X})_{j}=k_{r^{(i)}}(\hat{x}_{*},\hat{x}_{j}),$
$K(\hat{X},\hat{X})\in{\mathbb{R}}^{N\times N},\leavevmode\nobreak\
K(\hat{X},\hat{X})_{jl}=k_{r^{(i)}}(\hat{x}_{j},\hat{x}_{l}).$

It should be clear that the posterior distribution of the actual state
$x_{*}=\hat{x}_{*}+e_{*}$ is also Gaussian, $x_{*}|\hat{x}_{*},{\cal
D}\sim\mathcal{N}\left(\hat{x}_{*}+\mu(\hat{x}_{*}),\mathop{\mathrm{diag}}(\sigma(\hat{x}_{*}))^{2}\right)$.

Construction of the high-confidence set. Next, we construct a high-confidence
set such that the actual state is contained in it, with high probability.
Since the posterior distribution of the actual state $x$ is a multivariate
Gaussian distribution, it is standard to construct an ellipsoid as the high-
confidence set. Specifically, given a confidence level $\delta$, we construct
the high-confidence set $g(\hat{x})$ as an ellipsoid centered at the mean of
the distribution, $\hat{x}+\mu(\hat{x})$, and whose semiaxes are proportional
to the standard deviations $\\{\sigma^{(i)}\\}$ such that $\Pr\left(x\in
g(\hat{x})\right)=\delta$. The computation of this ellipsoid follows from
standard results in statistics.

###  IV-B Learning the controller

In this section, we will elaborate on the process of learning a certified
controller $\pi$ given such a state estimator $g$. Throughout this section, we
fix the target invariant set ${\cal S}\subset{\cal X}$ for the control system.
In order to prove or certify that ${\cal S}$ is indeed invariant with respect
to the closed-loop system, we will learn a continuously differentiable
function $h:{\cal X}\mapsto{\mathbb{R}}$, the certificate, such that the
$0$-superlevel set of $h$, ${\cal C}_{h}:=\\{x\in{\cal X}:h(x)>0\\}$ is equal
to ${\cal S}$. Functions like $h$ are often called barrier functions or
barrier certificates.

Barrier certificates were introduced by Prajna and Jadbababie in [26]
formalizing the folk theorem that at the boundary of an invariant set, the
vector field of an autonomous system must be pointing inwards. The approach
was used earlier to prove invariance of complex hybrid systems (see, for
example [27]). A natural extension of this idea to controlled systems is
presented in [4], which we quote here:

######  Theorem 1.

If $\pi:{\cal X}\mapsto{\cal U}$ be a differentiable controller such that
there exists an extended class ${\cal K}_{\infty}$ function $\alpha$ such that
$\forall x\in{\cal X}$,

$\frac{\partial h}{\partial x}\cdot f(x,\pi(x))+\alpha(h(x))\geq 0,$ (2)

then, ${\cal C}_{h}$ is invariant to $\dot{x}=f(x,\pi(x))$.

The function $h$ is called a control barrier function. All of the above,
assume that the controller $\pi$ has access to the perfect state. Going
forward, we relax this assumption. Instead, we assume that $\pi$ only has
access to the output set from the estimator $g$, and the actual state can be
anywhere in that set. Control barrier functions can be extended to handle
uncertainty in states as in [10]. Specifically, we have the following theorem.

######  Theorem 2.

Assume that a state estimator $g$ satisfies that for all $x$, the set
$g(s(x))$ contains $x$. If $\pi:{\cal X}\mapsto{\cal U}$ be a differentiable
controller such that there exists an extended class ${\cal K}_{\infty}$
function $\alpha$ such that $\forall\hat{x}\in{\cal X}$,

$\inf_{x\in g(\hat{x})}\left(\frac{\partial h}{\partial x}(x)\cdot
f(x,c(\hat{x}))+\alpha(h(x))\right)\geq 0,$ (3)

where $c(\cdot):=\pi(\mathrm{center}(g(\cdot)))$, then, ${\cal C}_{h}$ is
invariant to the closed-loop system, i.e., $\dot{x}=f(x,c\circ s(x))$.

###### Proof.

Let us denote the resulting feedback controller by $\hat{\pi}$, i.e.,
$\hat{\pi}:=c\circ s$. Then, we show that $\hat{\pi}$ indeed satisfies the
conditions in Theorem 1. For an arbitrary $x\in{\cal X}$, we know that
$x\subset g(s(x))=g(\hat{x})$, and thus by assumption, we have that

$\frac{\partial h}{\partial x}(x)\cdot f(x,\hat{\pi}(x)))+\alpha(h(x))\geq 0.$
(4)

Then, by Theorem 1, we have that ${\cal C}_{h}$ is invariant to the closed-
loop system $\dot{x}=f(x,\hat{\pi}(x))$. ∎

Learning-based synthesis. Next, we present the algorithm for learning the
robust barrier function and the controller given the Gaussian process
developed in the last section. As shown in Figure 1, we model the controller
and the barrier function with two neural networks $\pi(\cdot;\theta_{\pi})$
and $h(\cdot;\theta_{h})$, where $\theta_{\pi}$ and $\theta_{h}$ are the
parameters. To simplify the notations, we may omit $\theta_{\pi}$ and
$\theta_{h}$. The learning algorithm aims at finding the correct parameters
such that $\pi$ and $h$ satisfy the condition in Theorem 2. To impose this
condition, we define a loss function ${\cal L}_{1}$.

${\cal
L}_{1}(\theta_{h},\theta_{\pi})=\mathop{\mathbb{E}}_{\hat{x}\sim\mathtt{Unif}\left({\cal
X}\right)}\mathop{\mathbb{E}}_{x\sim\mathtt{Unif}\left(g(\hat{x})\right)}\Bigg{[}\\\
\mathtt{ReLU}\left(-\left(\frac{\partial h}{\partial x}(x)\cdot
f(x,\pi(\mathrm{center}(g(\hat{x}))))+\alpha(h(x))\right)\right)\Bigg{]}.$

The above loss function penalizes the violations of the condition of Theorem 2
in a probabilistic sense. Furthermore, the 0-superlevel set of the barrier
function $h$ and the user-defined safe set ${\cal S}$ should coincide. To this
end, we define the following loss function.

${\cal L}_{2}(\theta_{h})=\mathop{\mathbb{E}}_{x\sim\mathtt{Unif}\left({\cal
X}\right)}\left[\left(1-\mathbb{I}_{\cal S}(x)\right)h(x)-\mathbb{I}_{\cal
S}(x)h(x)\right].$

In order to train the neural networks on sampled data, we transform the above
loss functions into their empirical version. That is, replacing the
expectations with empirical averages. To this end, we construct a data set
${\cal D}_{c}$ as follows. We sample $M_{1}$ perceived state $\hat{x}$ from
$\mathtt{Unif}\left({\cal X}\right)$ and denote them by
$\\{\hat{x}_{i}\\}_{i=1}^{M_{1}}$. Then, for each $\hat{x}_{i}$, we sample
$M_{2}$ points $x$ from $\mathtt{Unif}\left(g(\hat{x})\right)$ and denote them
by $\\{x_{i}^{j}\\}_{j=1}^{M_{2}}$. These samples constitute the data set
${\cal D}_{c}:=\cup_{i=1}^{M_{1}}\\{(\hat{x}_{i},x_{i}^{j})\\}_{j=1}^{M_{2}}$.
Then, the empirical approximation of the above loss functions is defined as
follows.

${\cal
L}(\theta_{h},\theta_{\pi})=\frac{1}{M_{1}M_{2}}\sum_{i=1}^{M_{1}}\sum_{j=1}^{M_{2}}\Bigg{[}\\\
\lambda_{1}\mathtt{ReLU}\left(-\left(\frac{\partial h}{\partial
x}(x_{i}^{j})\cdot
f(x_{i}^{j},\pi(\mathrm{center}(g(\hat{x}_{i}))))+\alpha(h(x_{i}^{j}))\right)\right)\\\
+\lambda_{2}\left(\left(1-\mathbb{I}_{\cal
S}(x_{i}^{j})\right)h(x_{i}^{j})-\mathbb{I}_{\cal
S}(x_{i}^{j})h(x_{i}^{j})\right)\Bigg{]},$ (5)

where $\lambda_{1}>0$ and $\lambda_{2}>0$ are weights that balance two loss
terms. We train the neural networks by minimizing ${\cal L}$.

###  IV-C Adaptive sampling for estimation and control

We minimize the loss function defined in Eq. (5) with stochastic gradient
descent. After training, the loss function might remain positive due to the
large uncertainty of the Gaussian process at certain points. These points are
called hard samples. As stated above, in order to obtain robustness, we
require the barrier function condition to hold for every point in a set
defined by $g(\hat{x})$. For a hard sample $\hat{x}$, this set is too large
and satisfying this condition might be impossible. To conquer this problem, we
sample more data around these hard samples to reduce uncertainty. For each
hard sample $\hat{x}$, ideally we should add the sample $(\hat{x},x)$ to
${\cal D}$ in order to reduce the uncertainty of the GP at $\hat{x}$. However,
since we do not have access to $x$, we resort to evaluating the perception
function at $\mathrm{center}(g(\hat{x}))$ instead of $x$, and thus the new
sample is $(s(\mathrm{center}(g(\hat{x}))),\mathrm{center}(g(\hat{x})))$.
Then, we collect these samples into a set ${\cal H}$. As shown in Algorithm 1,
${\cal H}$ is then merged with the existing samples to create a new data set
for GP. The algorithm returns the control module $c$ if it successfully finds
one, otherwise, it returns some debug information to the user such that the
perception function can be improved accordingly in a separate procedure. The
debug information is simply the set ${\cal H}$ in the last iteration.

Input: Max number of iteration: $I$; Confidence $\delta$.

Output: $\pi$ and $g$, or ${\cal H}$.

Randomly initialize ${\cal
D}=\\{(\hat{x}_{1},x_{1}),\cdots,(\hat{x}_{N},x_{N})\\}$;

$i\leftarrow 0$;

do

Compute the state estimator $g$ on ${\cal D}$;

Construct ${\cal D}_{c}$ and train $h$ and $\pi$ on ${\cal D}_{c}$;

Collect hard samples ${\cal H}$;

${\cal D}\leftarrow{\cal D}\cup{\cal H}$; $i\leftarrow i+1$;

while  _${\cal H}\neq\varnothing$ and $i<I$_;

Algorithm 1 Adaptive sampling.

By jointly improving the state estimator and the controller, we avoid learning
an unnecessarily accurate state estimator at points where a rough state
estimate already suffices. For example, at points that are far away from the
boundary of the safe set, safe control input can be synthesized even if the
state estimate is not very accurate. While at points close to the boundary, an
accurate estimate becomes necessary for synthesizing a safe control input.

##  V Experiments

We evaluated the proposed approach on three dynamical systems, two simple
systems with synthetic perception error functions, and one realistic
simulation environment in CARLA with deep-learning-based perception modules.
We begin by discussing the details of the benchmarks.

###  V-A Benchmarks and implementation details

Dubins vehicle. The Dubins vehicle model [28, 7] has four state variables
$p_{x}$, $p_{y}$, $\theta$, and $v$ representing the 2D position, the heading
angle, and the speed. The target invariant set ${\cal S}$ is defined to keep
the position of the vehicle inside the area enclosed with red lines as shown
in Fig. 3 (left). The state variables $p_{x}$, $p_{y}$, and $v$ are all
perfectly observable (i.e., the perceived values equal to the actual values),
but the heading angle $\theta$ is not observable. The controller only has
access to a perceived heading angle $\hat{\theta}=\theta+\sin(p_{x}+p_{y})$.
Please note that such a perception function is just designed to preliminarily
verify the proposed framework. As will be shown later, the proposed approach
can handle much more complicated perception functions.

Cart-pole. The standard cart-pole model [7, 29] has four state variables $p$,
$v$, $\theta$, and $\omega$, which represent the position and the velocity of
the cart, and the angle and angular velocity of the pole. The target invariant
set is defined as $|p|<3$ and $|\theta|<\pi/6$. Here $p$ and $\theta$ are
perfectly observable, but $v$ and $\omega$ are not. The controller only has
access to the perceived values $\hat{v}=v+\sin(2p+4\theta)$ and
$\hat{\omega}=\omega+\cos(2p+4\theta)$.

Lane-keeping. We adopt the default vehicle model and map in the CARLA
simulator [30] as shown in Fig. 3 (right). The key state variables of the
vehicle are the lateral position $p$ and the heading angle $\theta$. The
values $p=0$ define the center of the lane and $p=\pm 3.5$ define the boundary
of the lane. The target invariant set is for the lateral position of the car
to stay within the lane boundaries, i.e., $|p|<3.5$. The velocity of the
vehicle is set to a constant. There is a front-facing camera attached to the
vehicle, and the car’s controller uses the lane detection approach of [31] to
detect the lane boundaries from the image (See Fig. 3). Then, the lateral
position and the heading angle are computed based on the detected lanes using
the geometry discussed in [18].

Implementation details. We adopt GPytorch [32] as the programming framework
for GP. The confidence level is set to $\delta=0.95$. For all experiments in
this section, we model the controller and the barrier function with two
$3$-layer neural networks, of which the hidden layer contains $128$ neurons.
The $K_{\infty}$ function $\alpha$ is designed as $\alpha(x)=0.1x$. The loss
weights in Eq.(5) are $\lambda_{1}=0.01$ and $\lambda_{2}=1$. To construct the
data set ${\cal D}_{c}$ for learning the controller and barrier function, we
set $M_{1}=10000$ and $M_{2}=32$. We train the neural networks for $30$ epochs
with a learning rate $0.1$. The maximum number of iterations is set to $I=6$.

###  V-B Experimental results

As a performance index for the learned controller, we report the unsafe ratio,
which empirically measures the fraction of finite-time ($10$ seconds in our
experiments) trajectories that exit the invariant set ${\cal S}$ from a
critical set of initial conditions. The choice of the initial condition is
important because the unsafe ratio will be favorable for an initial set that
is far from the boundary of ${\cal S}$. In our experiments, the critical
initial set is chosen such that the trajectories exit ${\cal S}$ in $1$ second
if the control input $u$ is set to zero.

In Fig. 2, we show how the unsafe ratio varies with the number of samples in
the data set ${\cal D}$. We compared the proposed adaptive sampling approach
with uniform sampling, where instead of enlarging the data set ${\cal D}$ with
hard samples we use data points that are uniformly sampled from the state
space, and the baseline, where GP is disabled and the state estimator is set
to $g(\hat{x})=\\{\hat{x}\\}$. There are several observations from the
experiments. (1) Both methods find controllers that are robust to the
perception error. (2) Adaptive sampling leads to a lower unsafe ratio than
uniform sampling with the same number of samples in ${\cal D}$, which
empirically confirms our intuition that the proposed controller design
approach with adaptive sampling is more sample efficient. To further
illustrate the benefit of adaptive sampling, we contrast the data sets ${\cal
D}$ generated by adaptive and uniform sampling in Fig. 3 (left). As can be
seen from the figure, adaptive sampling zooms in on relevant areas of the
state space, because at those areas, a more accurate state estimator is
needed, while uniform sampling evenly distributes its sampling budget.
Furthermore, a video demonstration of the results on the lane-keeping
benchmark can be found in the supplementary material.

Figure 2: Comparison of sample efficiency of learning certifiable controller.
While both uniform and adaptive sampling approaches learn safety preserving
controllers, the latter is significantly more sample efficient. The baseline
for the three benchmarks are $0.58$, $0.85$, and $0.61$ respectively.

Figure 3: Distribution of samples in the data set ${\cal D}$ constructed by
two sampling approaches on Dubins vehicle (left). Darker color means higher
density. The simulated lane-keeping scenario in CARLA and the detected lanes
(right).

##  VI Limitations and future work

One should be careful with interpreting the theoretical guarantee of the
proposed approach. The confidence $\delta$ characterizes the probability of
each standalone state falling into the high-confidence set. Further
theoretical treatment is required to boost such a guarantee to one on the
safety of trajectories. Furthermore, in order to handle larger data sets,
approximate GP such as [33] has to be used.

## References

  * [1] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” in _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_ , Y. Bengio and Y. LeCun, Eds., 2014. [Online]. Available: http://arxiv.org/abs/1312.6199
  * [2] Y. Gal and Z. Ghahramani, “Dropout as a bayesian approximation: Representing model uncertainty in deep learning,” in _international conference on machine learning_. PMLR, 2016, pp. 1050–1059.
  * [3] B. Wilson, J. Hoffman, and J. Morgenstern, “Predictive inequity in object detection,” _arXiv preprint arXiv:1902.11097_ , 2019.
  * [4] A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada, “Control barrier functions: Theory and applications,” in _2019 18th European Control Conference (ECC)_. IEEE, 2019, pp. 3420–3431.
  * [5] C. Fan, K. Miller, and S. Mitra, “Fast and guaranteed safe controller synthesis for nonlinear vehicle models,” in _International Conference on Computer Aided Verification_. Springer, 2020, pp. 629–652.
  * [6] C. Fan, U. Mathur, S. Mitra, and M. Viswanathan, “Controller synthesis made real: reach-avoid specifications and linear dynamics,” in _International Conference on Computer Aided Verification_. Springer, 2018, pp. 347–366.
  * [7] D. Sun, S. Jha, and C. Fan, “Learning Certified Control using Contraction Metric,” in _Conference on Robot Learning_ , 2020.
  * [8] S. Vaskov, S. Kousik, H. Larson, F. Bu, J. R. Ward, S. Worrall, M. Johnson-Roberson, and R. Vasudevan, “Towards provably not-at-fault control of autonomous robots in arbitrary dynamic environments,” in _Proceedings of Robotics: Science and Systems_ , FreiburgimBreisgau, Germany, June 2019.
  * [9] S. L. Herbert, M. Chen, S. Han, S. Bansal, J. F. Fisac, and C. J. Tomlin, “FaSTrack: A modular framework for fast and guaranteed safe motion planning,” in _56th Annual Conference on Decision and Control (CDC)_. IEEE, 2017.
  * [10] S. Dean, A. J. Taylor, R. K. Cosner, B. Recht, and A. D. Ames, “Guaranteeing safety of learned perception modules via measurement-robust control barrier functions,” _arXiv preprint arXiv:2010.16001_ , 2020.
  * [11] Y. Lin, F. Gao, T. Qin, W. Gao, T. Liu, W. Wu, Z. Yang, and S. Shen, “Autonomous aerial navigation using monocular visual-inertial fusion,” _Journal of Field Robotics_ , vol. 35, no. 1, pp. 23–51, 2018.
  * [12] G. Loianno, C. Brunner, G. McGrath, and V. Kumar, “Estimation, control, and planning for aggressive flight with a small quadrotor with a single camera and imu,” _IEEE Robotics and Automation Letters_ , vol. 2, no. 2, pp. 404–411, 2016.
  * [13] S. Tang, V. Wüest, and V. Kumar, “Aggressive flight with suspended payloads using vision-based control,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 2, pp. 1152–1159, 2018.
  * [14] F. Codevilla, M. Müller, A. López, V. Koltun, and A. Dosovitskiy, “End-to-end driving via conditional imitation learning,” in _2018 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2018, pp. 4693–4700.
  * [15] F. Sadeghi and S. Levine, “Cad2rl: Real single-image flight without a single real image,” in _Proceedings of Robotics: Science and Systems_ , Cambridge, Massachusetts, July 2017.
  * [16] S. Dean, N. Matni, B. Recht, and V. Ye, “Robust guarantees for perception-based control,” in _Learning for Dynamics and Control_. PMLR, 2020, pp. 350–360.
  * [17] T. Dreossi, D. J. Fremont, S. Ghosh, E. Kim, H. Ravanbakhsh, M. Vazquez-Chanlatte, and S. A. Seshia, “Verifai: A toolkit for the design and analysis of artificial intelligence-based systems,” _arXiv preprint arXiv:1902.04245_ , 2019.
  * [18] C. Hsieh, K. Joshi, S. Misailovic, and S. Mitra, “Verifying controllers with convolutional neural network-based perception: a case for intelligible, safe, and precise abstractions,” _arXiv preprint arXiv:2111.05534_ , 2021.
  * [19] M. Everett, G. Habibi, and J. P. How, “Efficient reachability analysis of closed-loop systems with neural network controllers,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 4384–4390.
  * [20] D. Sun and S. Mitra, “Neureach: Learning reachability functions from simulations,” in _International Conference on Tools and Algorithms for the Construction and Analysis of Systems_. Springer, 2022, pp. 322–337.
  * [21] Y.-C. Chang, N. Roohi, and S. Gao, “Neural lyapunov control,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 3245–3254.
  * [22] Z. Qin, K. Zhang, Y. Chen, J. Chen, and C. Fan, “Learning safe multi-agent control with decentralized neural barrier certificates,” _arXiv preprint arXiv:2101.05436_ , 2021.
  * [23] K. Kersting, C. Plagemann, P. Pfaff, and W. Burgard, “Most likely heteroscedastic gaussian process regression,” in _Proceedings of the 24th international conference on Machine learning_ , 2007, pp. 393–400.
  * [24] C. E. Rasmussen, “Gaussian processes in machine learning,” in _Summer school on machine learning_. Springer, 2003, pp. 63–71.
  * [25] P. Goldberg, C. Williams, and C. Bishop, “Regression with input-dependent noise: A gaussian process treatment,” _Advances in neural information processing systems_ , vol. 10, 1997.
  * [26] S. Prajna and A. Jadbabaie, “Safety verification of hybrid systems using barrier certificates,” in _International Conference on Hybrid Systems: Computation and Control (HSCC)_. Springer, 2004, pp. 477–492.
  * [27] S. Mitra, Y. Wang, N. Lynch, and E. Feron, “Safety verification of model helicopter controller using hybrid Input/Output automata,” in _International Conference on Hybrid Systems: Computation and Control (HSCC)_ , 2003, pp. 343–358.
  * [28] L. E. Dubins, “On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents,” _American Journal of mathematics_ , vol. 79, no. 3, pp. 497–516, 1957.
  * [29] A. G. Barto, R. S. Sutton, and C. W. Anderson, “Neuronlike adaptive elements that can solve difficult learning control problems,” _IEEE transactions on systems, man, and cybernetics_ , no. 5, pp. 834–846, 1983.
  * [30] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “Carla: An open urban driving simulator,” in _Conference on robot learning_. PMLR, 2017, pp. 1–16.
  * [31] D. Wu, M. Liao, W. Zhang, X. Wang, X. Bai, W. Cheng, and W. Liu, “Yolop: You only look once for panoptic driving perception,” 2021.
  * [32] J. R. Gardner, G. Pleiss, D. Bindel, K. Q. Weinberger, and A. G. Wilson, “Gpytorch: Blackbox matrix-matrix gaussian process inference with gpu acceleration,” in _Advances in Neural Information Processing Systems_ , 2018\.
  * [33] J. Hensman, A. Matthews, and Z. Ghahramani, “Scalable variational gaussian process classification,” in _Artificial Intelligence and Statistics_. PMLR, 2015, pp. 351–360.