11institutetext: University of Illinois Urbana-Champaign

# Estimating Uncertainty of Autonomous Vehicle Systems with Generalized
Polynomial Chaos

Keyur Joshi  Chiao Hsieh  Sayan Mitra  Sasa Misailovic

###### Abstract

Modern autonomous vehicle systems use complex perception and control
components and must cope with uncertain data received from sensors. To
estimate the probability that such vehicles remain in a safe state, developers
often resort to time-consuming simulation methods.

This paper presents an alternative methodology for analyzing autonomy
pipelines in vehicular systems, based on Generalized Polynomial Chaos (GPC).
We also present GAS, the first algorithm for creating and using GPC models of
complex vehicle systems. GAS replaces complex perception components with a
perception model to reduce complexity. Then, it constructs the GPC model and
uses it for estimating state distribution and/or probability of entering an
unsafe state.

We evaluate GAS on five scenarios used in crop management vehicles, self
driving cars, and aerial drones – each system uses at least one complex
perception or control component. We show that GAS calculates state
distributions that closely match those produced by Monte Carlo Simulation,
while also providing 2.3x-3.0x speedups.

##  1 Introduction

Autonomous vehicles are increasingly pervasive. They navigate by perceiving
the vehicle’s state, making a control decision based on this _perceived_
state, and moving accordingly. To ensure safety of life and property, their
developers must ensure that the vehicle does not enter an unsafe state, which
corresponds to undesirable outcomes such as crashes, immobilization, and
moving off course. However, 1) many sensors give uncertain readings (e.g., GPS
and LIDAR) and 2) the vehicle’s software processes sensor values or makes
decisions using complex, possibly imperfect components such as neural networks
and lookup tables. Due to this uncertainty, proving that an autonomous vehicle
will _never_ enter an unsafe state is impossible or impractical. Researchers
instead focus on ensuring that an autonomous system will not enter an unsafe
state _with high probability_ , and use probabilistic and statistical
techniques for system analysis.

_Monte Carlo Simulation_ (MCS) is perhaps the most used general method for
estimating the probability of entering an unsafe state over time.
Unfortunately, MCS requires a large number of simulations (which may be too
expensive to run) in order to get a sufficiently accurate estimate of the
state distribution [21, 27].

Analytical techniques for nonlinear dynamics and _uncertainty quantification_
(UQ) are an attractive alternative to MCS for estimating the state
distribution over time. _Generalized Polynomial Chaos_ (GPC) is a well-known
analytical technique that has found many applications in physics and
engineering [31]. GPC constructs a polynomial model of the simulated system
(typically represented as a system of partial differential equations), using a
limited number of system evaluations. Researchers then use the GPC model
instead of the original system simulation to estimate the state distribution
over time.

A complete autonomous vehicle system contains complex perception and control
components alongside vehicle dynamics. While vehicle dynamics in isolation can
be represented as differential equations [16], the same is not true for such
complex perception and control components. Additionally, small input
perturbations may significantly change their output. As a result, we cannot
directly apply GPC for estimating the vehicle’s state distribution over time.

#### Our work.

We present GAS (GPC for Autonomous Vehicle Systems), the first approach for
using GPC to analyze the navigation software pipeline of an autonomous vehicle
system.

GAS first creates a _perception model_ to represent the error of the
perception system and overcome its sensitivity to inputs. GAS uses the
perception model to estimate the output distribution of the state perception
system. GAS then automatically constructs a GPC model of the perception model
coupled with the remaining stages of the navigation system, and uses it to
estimate the vehicle state distribution and statistical safety properties. We
show that the outputs of GAS converge in distribution to the outputs of the
original navigation system.

We use GAS to estimate the state distribution of vehicle systems over time in
five scenarios. These scenarios model systems used in crop management
vehicles, self driving cars, and aerial drones. Each vehicle system uses at
least one complex perception or control component. We show that GAS produces
state distribution estimates that closely match those calculated via MCS,
while being 2.3x-3.0x faster. We also use GAS for global sensitivity analysis
of the vehicle systems to initial state perturbations by calculating Sobol
sensitivity indices [29].

#### Contributions.

This paper makes several contributions:

  * •

State distribution estimation for complex autonomous vehicle systems. We
present GAS, a novel methodology and an algorithm for estimating the state
distribution and statistical safety properties of complex autonomous vehicle
systems over time using GPC.

  * •

Perception models for GPC. We present models for complex perception systems
that estimate the output distribution of the original systems. We use these
perception models as part of our GAS approach.

  * •

Implementation. We implement GAS as a tool which automates the creation of the
perception model and the creation and usage of the GPC model.

  * •

Evaluation. We evaluate GAS on five scenarios from self driving cars, aerial
drones, and crop monitoring vehicles. GAS provides fast and accurate estimates
of the vehicle state distribution over time and the global sensitivity of the
vehicle systems.

##  2 Example

Consider a scenario from precision agriculture. An autonomous vehicle travels
between two rows of corn in order to monitor crop growth and detect weeds.
Farmers or other autonomous vehicles can use this information to adjust
fertilizer and herbicide levels on a location to location basis. We have
adapted this scenario from [28]. Figures 3-3 illustrate the scenario. The
desired path is shown in red.

Figure 1: Real-life corn monitoring vehicle

Figure 2: Gazebo simulation overhead view

Figure 3: Gazebo simulation front camera view

The top half of Figure 4 shows a block diagram representation of the system
responsible for driving the vehicle between two rows of corn. First, a camera
captures the area in front of the vehicle. The image depends on the current
vehicle state as well as environmental conditions. The neural network analyzes
the image to perceive the current vehicle state. The relevant state variables
in this scenario are: 1) The _heading_ angle $h$, which is the angle between
the vehicle’s current heading and the imaginary centerline between the two
rows of corn; $h$ can take values in $[-\pi,\pi]$ radians, with $0$
corresponding to the direction of the centerline. 2) The _distance_ $d$ of the
vehicle from the centerline; $d$ can take values in $[-0.38,0.38]$ meters,
with $0$ corresponding to the centerline.

As neural networks are inherently approximate, the state perceived by the
neural network may not be the same as the ground truth. The vehicle uses this
approximate heading and distance reading to calculate a steering angle in
order to keep the vehicle on the centerline. Finally, the vehicle moves
according to its constant speed and commanded steering angle.

#### Unsafe States.

We wish to avoid two undesirable outcomes: 1) if $|d|>0.228m$, the vehicle
will hit the corn, and 2) if $|h|>\pi/6$, the neural network output becomes
highly inaccurate and recovery may be impossible. To avoid these outcomes, we
want the vehicle to remain in the _safe region_ , defined as all states with
$d\in[-0.228,0.228]\wedge h\in[-\pi/6,\pi/6]$. Because the vehicle makes
steering decisions based on approximate data, we cannot be certain that the
vehicle will remain safe. Instead, we answer the question: _What is the
probability that the vehicle will remain safe over a period of time?_

Figure 4: Corn monitor vehicle model: original (top) and abstract (bottom)

#### Monte Carlo Simulation.

In _Monte Carlo Simulation_ (MCS), we simulate the vehicle’s movement a large
number of times and count the number of times the vehicle reaches an unsafe
state. We use Gazebo (Figures 3 and 3) for precise control over the simulation
environment.

We simulate 1000 samples over 100 time steps of 0.1 seconds each. We randomly
sample environmental conditions and choose the initial vehicle state from a
normal distribution. For each sample at each time step, we invoke the _vehicle
navigation pipeline_ , which 1) captures an image from Gazebo in the current
vehicle state and environment, 2) passes the image through the neural network
to get the approximate perceived state, 3) calculates a steering angle based
on the _perceived_ state, and 4) calculates the position of the vehicle after
one time step using the _actual_ state and steering angle. At each time step,
we calculate the fraction of vehicles remaining within the safe region.

Unfortunately, MCS requires a large amount of time. The major contributor to
runtime is image generation using Gazebo and processing using the neural
network. Furthermore, if we increase the number of samples for more
confidence, or increase the number of time steps, the simulation time
increases proportionally.

###  2.1 GAS: Using Generalized Polynomial Chaos

To reduce analysis time, we use GPC to construct a polynomial model as a
replacement for the original navigation model. Constructing the GPC model
requires evaluating the navigation model a small number of times ($<\\!1000$),
independent of the number of distribution estimation samples or time steps.
Unfortunately, small changes in the input image to the neural network can
greatly affect its output, which affects the final state of the vehicle – this
is something that a GPC polynomial model cannot accurately replicate.

#### Perception Model.

We present GAS, a novel approach for constructing polynomial models of
navigation systems and using them for state distribution estimation. First,
GAS creates an abstract navigation model by replacing Gazebo image generation
and neural network processing with a _perception model_. To train the
perception model, we choose 121 ground truth states in a 11 by 11 grid in the
safe region. At each ground truth state, we gather 350 images with randomly
sampled environmental conditions, pass them through the neural network, and
store the outputs. GAS assumes that, for any given heading $h$ and distance
$d$, the output of the neural network is drawn from a 2D normal distribution
with mean vector $\mu(h,d)$ and the covariance matrix $\sigma^{2}(h,d)$. GAS
uses the 350 outputs for each ground truth state to calculate $\mu$ and
$\sigma^{2}$ for that state, and trains a degree 4 polynomial regression model
to predict $\mu$ and $\sigma^{2}$ for any state in the safe region. Instead of
returning the state perceived by the neural network, this perception model
returns the _distribution_ of possible perceived states. GAS samples this
perceived state distribution when constructing the GPC model of the entire
navigation system.

#### GPC Model Construction.

Next, GAS next creates an abstract navigation model which accepts a sample
from a standard normal distribution instead of an environment (bottom half of
Figure 4). The abstracted navigation model first calculates the neural network
output distribution parameters using the perception model, then transforms the
raw input sample into a sample from this output distribution. The navigation
model uses this sample for the rest of the pipeline.

To construct the GPC model, GAS 1) creates a joint distribution, consisting of
a distribution over all safe vehicle states and the standard normal
distribution used by the abstracted vehicle model, 2) chooses a set of
polynomials which are orthogonal w.r.t. the joint distribution, 3) picks
specific samples from the joint distribution that are necessary for _Gaussian
quadrature_ , a fast and accurate numerical integration method, 4) evaluates
these samples with the abstracted navigation model, and finally 5) uses the
input samples and the corresponding outputs to create the polynomial model of
the end to end vehicle navigation system. The GAS model is a $4^{th}$ degree
polynomial over 4 state variables with 70 terms, including 53 interaction
terms. GAS substitutes this model in place of the original navigation model in
the MCS procedure described above to estimate the state distribution of the
vehicle over time. Since the GAS model is faster than the original model, GAS
increases the number of simulations to 10000 for higher fidelity distribution
estimation.

###  2.2 Results

Figure 5: Distributions at final time step

Figure 6: Distribution similarity over time

Figure 7: Safe probabilities over time

#### Accuracy.

Figure 7 shows a comparison of the heading and distance distributions after
100 time steps. The X Axis shows the variable value and the Y Axis shows the
cumulative probability. The green and red plots show the distributions
estimated using MCS and GAS, respectively. We compare the GAS and MCS
distributions using the Kolmogorov-Smirnov (KS) statistic, which is a
conservative measure of distribution similarity, and the Wasserstein metric.
Figure 7 shows how the KS statistic evolves over time. The X Axis shows time
steps and the Y Axis shows the KS statistic. The low KS statistic value
indicates good correlation between the two distributions at all times. The
Wasserstein metric also remains below 0.02. Figure 7 shows the probability of
remaining in a safe state over time. The X Axis shows time steps and the Y
Axis shows the probability of remaining safe. The shaded region around each
plot shows the 95% bootstrap confidence interval. We use the t-test to check
if the safe state probabilities are similar. The t-test passes for 99 of 100
time steps, indicating high similarity.

#### Time.

GAS is 2.3x faster than MCS. MCS required 19.5 hours on our hardware.
Gathering the training data for the perception model required 8.5 hours on our
hardware. The time required for training the perception model, constructing
the polynomial approximation with GPC, and using the GPC approximation was
negligible in comparison ($<1$ minute). Increasing the number of samples or
the number of time steps would further increase the gap between the two
methods.

#### Conclusion.

These results jointly indicate that GAS gives us a faster, accurate
replacement for MCS of this autonomous corn row navigation model.

##  3 Background

We present key GPC definitions. Dedicated books, e.g., [31], give more
details.

#### Lagrange Basis Polynomials.

Given points $(x_{i},y_{i}),\ 1\leq i\leq N$, where all $x_{i}$ are distinct,
Equation 1 gives the _Lagrange basis polynomials_ $L_{i}$ for this set of
points.

$L_{i}(x)=\prod\limits_{\begin{subarray}{c}1\leq j\leq N\\\ j\neq
i\end{subarray}}\frac{x-x_{j}}{x_{i}-x_{j}}$ (1)

#### Orthogonal Polynomials.

Assume $X$ is a continuous variable with support $S_{X}$ and p.d.f.
$p_{X}:S_{X}\rightarrow\mathbb{R}$. Let
$\Psi=\\{\Psi_{n}|n\in\mathbb{N}_{0}\\}$ be a set of polynomials, where
$\Psi_{n}$ is an $n^{th}$ degree polynomial. Then $\Psi$ is a set of
orthogonal polynomials with respect to $X$ if $n\neq
m\Rightarrow\int_{S_{X}}\Psi_{n}(x)\Psi_{m}(x)p_{X}(x)dx=0$. The orthogonal
polynomial $\Psi_{n}$ has $n$ distinct roots in $S_{X}$.

#### Orthogonal Polynomial Projection (GPC).

Let $f:S_{X}\rightarrow\mathbb{R}$. Then the $N^{th}$ order orthogonal
polynomial projection of $f$, written as $f_{N}$, with respect to a set of
orthogonal polynomials $\Psi$, is:

$f_{N}=\sum\limits_{i=0}^{N}c_{i}\Psi_{i}\qquad\text{where}\qquad
c_{i}=\frac{\int\limits_{S_{X}}f(x)\Psi_{i}(x)p_{X}(x)dx}{\int\limits_{S_{X}}\Psi_{i}^{2}(x)p_{X}(x)dx},$
(2)

If $f$ is a $N^{th}$ degree polynomial, then $f_{N}=f$. Otherwise, $f_{N}$ is
the _optimal_ $N^{th}$ degree polynomial approximation of $f$ w.r.t. $X$, in
the sense that it minimizes $\ell_{2}$ error, calculated as
$\int_{S_{X}}(f(x)-f_{N}(x))^{2}p_{X}(x)dx$. The $\ell_{2}$ error is lower for
functions that are close in behavior to an $N^{th}$ degree polynomial. As $N$
approaches $\infty$, the $\ell_{2}$ error approaches 0, meaning that we can
construct arbitrarily good approximations of $f$. $f_{N}$ is called the
$N^{th}$-order generalized polynomial chaos (GPC) approximation. GPC can be
easily extended for functions of multiple _independent_ variables. We provide
details in Appendix 0.A.

#### Gaussian Quadrature.

To use Equation 2, we must perform multiple integrations to calculate the
coefficients $c_{i}$ ($i\in\\{0\ldots N\\}$). For any non-trivial function
$g$, we must use numerical integration by approximating the integral with a
sum:

$\int\limits_{S_{X}}g(x)p_{X}(x)dx\approx\sum\limits_{i=1}^{N}w_{i}g(x_{i})\qquad\text{where}\qquad
w_{i}=\int\limits_{S_{X}}L_{i}(x)p_{X}(x)dx$ (3)

We choose $w_{i}$ and $x_{i}$ so as to minimize integration error. In
_Gaussian quadrature_ , we choose $x_{i}$ to be the $N$ roots of $\Psi_{N}$,
the $N^{th}$ order orthogonal polynomial w.r.t. $X$. We calculate the
corresponding weights using the Lagrange basis polynomials $L_{i}$ (Equation
1) passing through $x_{j}\ \forall j\neq i$.

#### Global Sensitivity (Sobol) Indices.

Sobol Indices [29] decompose the variance of the model output over the entire
input distribution into portions that depend on subsets of the input
variables. Particularly, the _first order_ sensitivity indices show the
contribution of a single input variable to the output variance. For an input
variable $X_{i}$, the sensitivity index $S_{i}=V_{i}/V$, where
$V=\mathit{Var}_{\mathbf{X}}(f(\mathbf{x}))$ is the total variance and
$V_{i}=\mathit{Var}_{X_{i}}(E_{\mathbf{X}_{\sim i}}(f(\mathbf{x})|x_{i}))$.
Here $\mathbf{X}_{\sim i}$ is the set of all input variables except $X_{i}$.

##  4 GAS Approach

We present our approach for estimating the state distribution over time for a
vehicle navigation system containing an image processing neural network. GAS
consists of four high level steps:

  1. 1.

Create a deterministic end-to-end vehicle navigation model.

  2. 2.

Train a perception model (Algorithm 1) and use it to replace the neural
network in the vehicle model (Algorithm 2).

  3. 3.

Construct a GPC polynomial model from the vehicle model (Algorithm 3).

  4. 4.

Use the GPC polynomial model for estimating the state distribution and safe
state probability over time (Algorithm 4).

GAS automates almost the entire process of constructing and using the GPC
model. The user provides the perception model training data, the distributions
of state and random variables, GPC order, and simulation parameters. GAS
infers the optimal degree of polynomial regression for the perception model
using cross-validation to maximize accuracy while preventing overfitting.

###  4.1 Creating a Deterministic Vehicle Model

First, we represent the end-to-end vehicle model as a function of independent
random variables,
$M_{V}:\mathbb{D}_{S}\times\mathbb{D}_{E}\times\mathbb{D}_{R}\rightarrow\mathbb{D}_{S}$.
$S\in\mathbb{D}_{S}$ is a vector of state variables, $E\in\mathbb{D}_{E}$ is a
vector of environment-related random variables that affect the neural network,
and $R\in\mathbb{D}_{R}$ is a vector of random variables that do not affect
the neural network, but affect other parts of $M_{V}$. Making $M_{V}$
deterministic is necessary as GPC produces a deterministic polynomial model
over independent random variables. Because multivariate GPC requires the input
variables to be independent, we remove any input variable dependencies by
isolating their independent components and using those as the input variables
instead.

###  4.2 Replacing Image Processing Components

Polynomials over reals are continuous and have a limited number of inflection
points. Consequently, polynomials make poor replacements for models that are
discontinuous or whose output changes rapidly with small changes in input.
Image processing neural networks are particularly susceptible to perturbations
– even tiny changes in the input image can lead to significant output changes
[24].

This is why GAS replaces the neural network with a perception model prior to
constructing the GPC polynomial model. Algorithm 1 shows how GAS creates the
perception model. The steps are as follows:

  1. 1.

Suppose $\mathbb{D}_{S}^{S}$ is the safe set of states. We pick a set of
ground truth states $G\subset\mathbb{D}_{S}^{S}$, such that $G$ is an evenly
spaced tensor grid that includes the extreme states within
$\mathbb{D}_{S}^{S}$.

  2. 2.

For each $g\in G$, GAS captures a list of images $I_{g}$ using a
photorealistic simulator such as Gazebo and AirSim. For each image, GAS
randomly samples $E$ from the environment distribution $\mathcal{D}_{E}$
($E\sim\mathcal{D}_{E}$). GAS obtains a large number of images per state
($N_{i}\geq 350$) to get a high confidence estimate of the output
distributions in the next step.

  3. 3.

For each $g\in G$, GAS passes $I_{g}$ through the neural network to obtain a
list of network outputs $O_{g}$. GAS calculates the mean $\mu_{g}$ and
covariance $\sigma^{2}_{g}$ of $O_{g}$.

  4. 4.

GAS trains a polynomial regression model $M_{\mathit{per}}$ to predict
$\mu_{S}$ and $\sigma_{S}^{2}$ for any $S\in\mathbb{D}_{S}^{S}$.

The perception model $M_{\mathit{per}}$ returns a _distribution_ of possible
outputs. We create an _abstracted_ vehicle model
$M^{\prime}_{V}:\mathbb{D}_{S}\times\mathbb{R}^{n}\times\mathbb{D}_{R}\rightarrow\mathbb{D}_{S}$
(Algorithm 2) to use $M_{\mathit{per}}$ instead of the neural network. Instead
of a sample from $\mathcal{D}_{E}$, $M^{\prime}_{V}$ accepts a sample $N$ from
a multivariate standard normal distribution $\mathcal{N}(0,1)$. It calculates
$\mu_{S}$ and $\sigma_{S}^{2}$ using $M_{\mathit{per}}$, and transforms $N$ to
a sample from $\mathcal{N}(\mu_{S},\sigma_{S})$. $M^{\prime}_{V}$ uses this
sample as the neural network output for the rest of the model.

1:Input $G$: even, extensive tensor grid in safe state space;
$\mathcal{D}_{E}$: distribution of environment variables; $N_{i}$: number of
images to capture for each $g\in G$

2:Returns $M_{\mathit{per}}$: trained perception model

3:function TrainPerceptionModel($G,\mathcal{D}_{E},N_{i}$)

4: $\mathit{TrainTestData}\leftarrow\\{\;\\}$

5: for $g\in G$ do

6: $I_{g}\leftarrow[\;]$

7: for $i$ from $1$ to $N_{i}$ do

8: $E\sim\mathcal{D}_{E}$

9: $\mathit{Img}\leftarrow\textsc{CaptureImage}(g,E)$

10: $I_{g}\leftarrow I_{g}::\mathit{Img}$

11: $O_{g}\leftarrow\textsc{NeuralNetwork}(I_{g})$

12: $\mu_{g}\leftarrow\textsc{Mean}(O_{g})$

13: $\sigma^{2}_{g}\leftarrow\textsc{Covariance}(O_{g})$

14:
$\mathit{TrainTestData}\leftarrow\mathit{TrainTestData}[g\mapsto(\mu_{g},\sigma^{2}_{g})]$

15:
$M_{\mathit{per}}\leftarrow\textsc{PolynomialRegressionModel}(\mathit{TrainTestData})$

Algorithm 1 Training the perception model

1:Input $S$: initial state of vehicle; $N$: raw sample to be transformed into
neural network output sample; $R$: other random variables; $M_{\mathit{per}}$:
trained perception model

2:Returns $S^{\prime}$: state of vehicle after one time step

3:function $M^{\prime}_{V}$($S,N,R,M_{\mathit{per}}$)

4: $\mu_{S},\sigma^{2}_{S}\leftarrow M_{\mathit{per}}(S)$

5: $O_{S}\leftarrow\textsc{Transform}(N,\mu_{S},\sigma^{2}_{S})$

6: $S^{\prime}\leftarrow\textsc{VehicleControlAndDynamics}(S,O_{S},R)$

Algorithm 2 Abstracted vehicle model

We assume the output is distributed according to
$\mathcal{N}(\mu_{S},\sigma_{S})$ as we can easily define the distribution in
terms of $\mu_{S},\sigma_{S}^{2}$. However, we can use any distribution whose
parameters we can predict through polynomial regression. Likewise, instead of
choosing raw samples from $\mathcal{N}(0,1)$, we can sample any distribution
that has orthogonal polynomials for use with GPC (e.g., Uniform, Beta, or more
complicated distributions as polynomials of such random variables).

###  4.3 GPC for the End to End Vehicle System

Algorithm 3 shows how GAS constructs the GPC approximation of the abstracted
vehicle model:

  1. 1.

GAS constructs a joint distribution $J$ over
$\mathbb{D}_{S}\times\mathbb{R}^{n}\times\mathbb{D}_{R}$. For the state
variables, GAS chooses a normal or truncated normal distribution
$\mathcal{D}_{S}^{S}$ over the safe state space $\mathbb{D}_{S}^{S}$. GAS uses
$\mathcal{N}(0,1)$ for the perception model raw sample. For the other random
variables, GAS uses their actual distribution $\mathcal{D}_{R}$.

  2. 2.

GAS constructs the basis polynomials which are orthogonal w.r.t. $J$.
Increasing the order $o_{\mathit{gpc}}$ increases accuracy, but also runtime.

  3. 3.

GAS chooses samples from $J$ and calculates the corresponding weights for
using Gaussian quadrature using Equation 3.

  4. 4.

GAS evaluates the abstracted vehicle model $M^{\prime}_{V}$ at the chosen
samples.

  5. 5.

GAS calculates the GPC polynomial model as the weighted sum of the orthogonal
polynomials using Equation 2.

1:Input $\mathcal{D}_{S}^{S}$: distribution over $\mathbb{D}_{S}^{S}$;
$\mathcal{D}_{R}$: distribution of other random variables; $o_{\mathit{gpc}}$:
order of GPC model; $M^{\prime}_{V}$: abstracted vehicle model

2:Returns $M_{\mathit{GPC}}$: GPC polynomial model

3:function
CreateGPCModel($\mathcal{D}_{S}^{S},\mathcal{D}_{R},o_{\mathit{gpc}},M^{\prime}_{V}$)

4:
$J\leftarrow\textsc{Join}(\mathcal{D}_{S}^{S},\mathcal{N}(0,1),\mathcal{D}_{R})$

5:
$\Psi\leftarrow\textsc{GenerateOrthogonalPolynomials}(\textit{order}=o_{\mathit{gpc}},J)$

6:
$X,W\leftarrow\textsc{GenerateQuadratureNodesAndWeights}(\textit{order}=o_{\mathit{gpc}},J)$

7: $Y\leftarrow[M^{\prime}_{V}(x)$ for $x\in X]$

8: $M_{\mathit{GPC}}\leftarrow\textsc{QuadratureAndGPC}(\Psi,X,W,Y)$

Algorithm 3 GPC approximation construction

Algorithm 4 shows how GAS uses the GPC model to estimate the probability that
the vehicle will remain in a safe state over time. GAS creates initial joint
samples using the initial state distribution $\mathcal{D}_{S}^{0}$, the raw
sample distribution, and the distribution of other random variables (Line 6).
At each time step, GAS evaluates the GPC model on each joint sample to get the
next state. If the next state is safe, GAS chooses new random values to
prepare the joint sample for the next time step. Finally, GAS calculates and
stores the fraction of samples that are still in the safe region.

#### Computing Sobol Indices.

Because variable marginalization and analytical integration is simple for
polynomials, GAS can analytically calculate the Sobol indices for
$M_{\mathit{GPC}}$ over the joint distribution $J$. To calculate Sobol indices
using MCS, we have to use estimators that increase in accuracy as the number
of samples increases.

1:Input $N_{s}$: number of samples to use for distribution estimation; $T$:
number of time steps; $\mathcal{D}_{S}^{0}$: initial state distribution;
$\mathcal{D}_{R}$: distribution of other random variables; $\mathit{Pred}$:
safety predicate; $M_{\mathit{GPC}}$: constructed GPC approximation

2:Returns $P_{\mathit{safe}}$: probability that the vehicle is safe until each
time step

3:function
EstimateSafeProbability($N_{s},T,\mathcal{D}_{S}^{0},\mathcal{D}_{R},\mathit{Pred},M_{\mathit{GPC}}$)

4: $X\leftarrow[\;]$; $P_{\mathit{safe}}\leftarrow\\{\;\\}$

5: for $i$ from $1$ to $N_{s}$ do

6: $x\sim\textsc{Join}(\mathcal{D}_{S}^{0},\mathcal{N}(0,1),\mathcal{D}_{R})$

7: $X\leftarrow X::x$

8: for $t$ from $1$ to $T$ do

9: $X^{\prime}\leftarrow[\;]$

10: for $x\in X$ do

11: $S^{\prime}\leftarrow M_{\mathit{GPC}}(x)$

12: if $\textsc{Safe}(S^{\prime},\mathit{Pred})$ then

13: $N^{\prime}\sim\mathcal{N}(0,1)$

14: $R^{\prime}\sim\mathcal{D}_{R}$

15: $X^{\prime}\leftarrow X^{\prime}::(S^{\prime},N^{\prime},R^{\prime})$

16: $X\leftarrow X^{\prime}$

17: $P_{\mathit{safe}}\leftarrow P_{\mathit{safe}}[t\mapsto|X|/N_{s}]$

Algorithm 4 Using the GPC approximation to estimate safe probability

#### Accuracy.

Multiple GAS parameters affect the accuracy of the GPC model: the tensor grid
size $|G|$, the number of images for each grid point $N_{i}$, the degree of
polynomial regression used for the perception model, and the GPC order
$o_{\mathit{gpc}}$. Under certain conditions, GAS converges in distribution to
the exact solutions.

######  Theorem 4.1 (GAS Convergence)

Assume that for a particular environment distribution $\mathcal{D}_{E}$, the
distribution of neural network outputs in any state is Gaussian. Then, the GAS
model $M_{\mathit{GPC}}$ converges in output distribution to the original
vehicle model $M_{V}$.

We provide a proof sketch for Theorem 4.1 in Appendix 0.B.

#### Runtime.

The most time consuming components of the vehicle model are photorealistic
image capture and subsequent neural network image processing. MCS requires
$\Theta(N_{s}T)$ evaluations of these components, while GAS requires
$\Theta(|G|N_{i})$ evaluations. GAS also requires additional time for training
$M_{\mathit{per}}$, constructing $M_{\mathit{GPC}}$, and $\Theta(N_{s}T)$
evaluations of $M_{\mathit{GPC}}$. As a result, the speedup offered by GAS –
after amortizing the GPC creation time – depends strongly on the speedup of
$M_{\mathit{GPC}}$ over the original vehicle model $M_{V}$ used for MCS.

#### Scalability.

The GPC polynomial model must consider all possible interactions between state
variables, and can suffer from the “curse of dimensionality” (combinatorial
explosion of the number of polynomial terms). This is a general GPC
limitation, for which researchers in engineering applications have proposed,
e.g., low-rank approximation [18], or a combination of GPC and MCS [25]. The
authors of the former approach successfully apply it to a scenario with over
50 input random variables (parameters). These are interesting directions for
future research, but are beyond the scope of GAS.

#### Vehicle models with categorical state variables.

GAS uses Multi-Element GPC (MEGPC) for vehicle models that have categorical
state variables, in conjunction with an _ancillary model_ for predicting the
final values of the categorical state variables. Details of this approach are
provided in Appendix 0.C.

##  5 Methodology

Table 1: GAS benchmarks Benchmark | Perception | Control | $\mathbf{dim_{s}}$ | $\mathbf{dim_{r}}$ | Replacement
---|---|---|---|---|---
Corn-Monitor | Resnet-18 | Skid-Steer | 2 | 2 | Perc |  $\rightarrow$ Poly Reg
Car-Straight | LaneNet | Pure Pursuit | 2 | 2 | Perc |  $\rightarrow$ Poly Reg
Car-Curved | LaneNet | Pure Pursuit | 2 | 2 | Perc |  $\rightarrow$ Poly Reg
ACAS-Table | Ground Truth | ACAS-Xu Table | 4 | 0 | Ctrl |  $\rightarrow$ Dec Tree
ACAS-NN | Ground Truth | ACAS-Xu NN | 4 | 0 | Ctrl |  $\rightarrow$ Dec Tree

#### Benchmarks.

We chose five benchmarks that include autonomous vehicle systems such as self
driving cars, aerial drones, and crop monitoring vehicles. Table 1 shows
details of the benchmarks. Columns 2 and 3 state the vehicle’s perception and
control system, respectively. Columns 4 and 5 state the number of state
dimensions and random variable dimensions, respectively. Column 6 indicates if
GAS made a replacement in the perception (Perc) or control (Ctrl) system, and
the nature of the replacement (Poly Reg: polynomial regression, Dec Tree:
decision tree). The benchmarks are:

  * •

Corn Monitoring Vehicle. A vehicle that travels between two rows of corn and
must avoid hitting them. This is our main example (Section 2).

  * •

Self-Driving Car on a Straight Road. A vehicle that must drive within a road
lane
($\mathbb{D}_{S}^{S}\equiv|\mathit{heading}|\leq\pi/12\wedge|\mathit{distance}|\leq
1.2m$). It uses LaneNet to perceive the location of the lane edges and uses
the pure pursuit controller. We derive this benchmark from [7].

  * •

Self-Driving Car on a Curved Road. Similar to the previous benchmark, but on a
circular road of 100m radius.

  * •

Aerial Drone Collision Avoidance (Lookup Table). An aerial drone that must
avoid a near miss with an intruder
($\mathbb{D}_{S}^{S}\equiv|\mathit{separation}|\geq 500ft$). The drone uses
ACAS-Xu lookup tables from [15]. As this model’s state includes a categorical
variable (the previous ACAS advisory), we use MEGPC and predict the next
advisory using a decision tree.

  * •

Aerial Drone Collision Avoidance (Neural Network). Similar to the previous
benchmark, but uses a neural network from [15] trained to replace the lookup
table. We use decision tree for predicting the next advisory.

#### Implementation and Experimental Setup.

We performed our experiments on machines with an Intel Xeon CPU, NVIDIA Quadro
P5000 GPU, 32 GB RAM, and Ubuntu 20.04. We implement GAS in Python, using the
chaospy library [10]. We use Gazebo 11 [17] to capture images for Corn-
Monitor, Car-Straight, and Car-Curved benchmarks. We run all image processing
neural networks on the GPU. We run ACAS-NN entirely on CPU as its network is
small.

Since there are no closed form solutions for calculating the state
distribution over time for non-trivial systems, we compare GAS to a MCS
baseline. We set GAS parameters as follows: $G$ is a 11x11 grid in the safe
state space, $N_{i}=350$, and $o_{\mathit{gpc}}=4$. We set the number of time
steps $T=100$. For MCS, we set $N_{s}=1000$ to limit runtime to $\leq 24$
hours. For GAS, we set $N_{s}=10000$ for better distribution fidelity and
confidence bounds.

#### Distribution Similarity Metrics.

We use two complementary similarity metrics to compare MCS and GAS state
distributions at each time step. The KS statistic quantifies the maximum
distance between two cumulative distribution functions, while the Wasserstein
metric can be interpreted as the energy needed to transform one distribution
into another. The smaller the metrics are, the more closely the two
distributions resemble each other. We also compare the fraction of simulated
vehicles remaining in the safe region till each time step.

##  6 Evaluation

###  6.1 Does GAS provide an _accurate_ replacement for Monte Carlo Simulation
of end to end vehicle systems?

Table 2 presents the values of the distribution similarity metrics. For each
benchmark state variable, Columns 3-4 show the maximum values of the KS
statistic and Wasserstein metric over all time steps. The Wasserstein metric
is high for the distance variables of the ACAS benchmarks due to their large
range. However, the metric is still low compared to the variance of these
variables. Columns 5-6 compare the mean and standard deviation of the
distributions at the final time step, showing that they are close. We also
visualize the distributions in the final time step in Appendix 0.D.

Table 2: State variable distribution comparison Benchmark | Variable | $\mathbf{KS_{max}}$ | $\mathbf{Wass_{max}}$ | $\mathbf{\mu_{GAS{}}}$ | $\mathbf{/\mu_{MCS}}$ | $\mathbf{\sigma_{GAS{}}}$ | $\mathbf{/\sigma_{MCS}}$
---|---|---|---|---|---|---|---
Corn-Monitor | Heading (rad) | 0.11 | 0.02 | 0.00 | /-0.01 | 0.04 | /0.04
Distance (m) | 0.14 | 0.01 | -0.01 | /-0.02 | 0.03 | /0.03
Car-Straight | Heading (rad) | 0.09 | 0.00 | 0.00 | /0.00 | 0.01 | /0.01
Distance (m) | 0.12 | 0.02 | 0.09 | /0.10 | 0.05 | /0.06
Car-Curved | Heading (rad) | 0.17 | 0.00 | 0.00 | /0.00 | 0.01 | /0.01
Distance (m) | 0.12 | 0.01 | 0.05 | /0.06 | 0.04 | /0.05
ACAS-Table | Crossrange (ft) | 0.06 | 155 | -845 | /-985 | 1424 | /1458
Downrange (ft) | 0.04 | 116 | 2224 | /2113 | 1751 | /1702
Heading (rad) | 0.02 | 0.05 | 0.15 | /0.17 | 1.71 | /1.69
ACAS-NN | Crossrange (ft) | 0.09 | 382 | 869 | /489 | 1753 | /1943
Downrange (ft) | 0.05 | 138 | 2154 | /2019 | 1658 | /1646
Heading (rad) | 0.02 | 0.05 | -0.07 | /-0.04 | 1.73 | /1.76

Figure 8: Evolution of safe state probability over time. Red: GAS, Green:MCS.

Figure 8 shows the time evolution of the probability that the vehicle remains
in a safe state. The red plots show the probability estimate obtained using
GAS, while the green plots show the probability estimate obtained using MCS.
The shaded region around each plot shows the 95% bootstrap confidence
interval. Since GAS approximates the behavior of the vehicle model, as opposed
to under/over approximation of reachable states, GAS’s safe state probability
estimate can be on either side of the MCS estimate.

Table 3: Safe state probability comparison

Benchmark | t-test pass |  $\mathbf{\ell_{2}}$ error | X-Cor
---|---|---|---
Corn-Monitor | 99/100 | 0.004 | 0.974
Car-Straight | 99/100 | 0.001 | 0.905
Car-Curved | 99/100 | 0.001 | 0.907
ACAS-Table | 100/100 | 0.051 | 0.998
ACAS-NN | 100/100 | 0.021 | 0.998

Table 3 shows the metrics we use to rigorously measure the similarity of the
safe state probabilities from Figure 8. We used the standard t-test to analyze
the similarity of the safe state probabilities computed by GAS and MCS in each
time step. Column 2 shows the number of time steps for which the t-test
“passed”, meaning that we could not reject the null hypothesis that the
probabilities are equal. Column 3 shows the $\ell_{2}$ error – RMS of the
differences in safe state probability at each time step, and Column 4 shows
the cross-correlation – the Pearson correlation coefficient between the two
series of probabilities. The similarity of the safe state probability is
directly the result of the similarity of the state distributions.

In conclusion, the vehicle state variable distributions that we estimate using
GAS closely resemble those that we estimate using MCS, even after 100 time
steps. Consequently, the vehicle safe state probability estimate is also
similar between the two approaches.

###  6.2 Is GAS _faster_ compared to Monte Carlo Simulation?

Table 4 compares the time required for distribution estimation using MCS
(Column 2) and GAS (Columns 3-4). Column 3 gives the time required to gather
data for and train the perception model and/or the ancillary model. Column 4
gives the time required for constructing and using the GPC model. Finally,
Column 5 gives the relative speedup of GAS over MCS.

Table 4: Time usage comparison for GAS and MCS (∗use same ancillary model). Benchmark | $\mathbf{t_{MCS}}$ | $\mathbf{t_{model}}$ | $\mathbf{t_{GPC}}$ | Speedup | $\mathbf{t^{MCS}_{sens}}$ | $/\mathbf{N^{s}_{sens}}$ | $\mathbf{t^{GPC}_{sens}}$ | Speedup
---|---|---|---|---|---|---|---|---
Corn-Monitor | 19.5h | 8.5h | 3.4s | $2.3\times$ | 99.9s | $/10^{7}$ | 12.3s | $8.1\times$
Car-Straight | 4.9h | 1.9h | 3.1s | $2.6\times$ | 102s | $/10^{7}$ | 12.5s | $8.2\times$
Car-Curved | 4.9h | 1.9h | 3.2s | $2.6\times$ | 99.6s | $/10^{7}$ | 11.7s | $8.5\times$
ACAS-Table | 7.7s | 0.29s∗ | 3.1s | $2.3\times$ | 394s | $/10^{6}$ | 3.3s | $119.4\times$
ACAS-NN | 10.3s | 0.29s∗ | 3.2s | $3.0\times$ | 516s | $/10^{6}$ | 3.4s | $151.8\times$

The time consuming process of gathering images using Gazebo and processing
them with the neural network leads to the high time requirement for the Corn-
Monitor, Car-Straight, and Car-Curved benchmarks, both for MCS and for
gathering the training data for the perception model. Increasing $N_{s}$ or
$T$ increases $t_{\mathit{MCS}}$, but not $t_{\mathit{model}}$. Consequently,
the speedup of GAS increases for longer experiments or higher number of
samples. Constructing and using the GPC approximation takes a comparatively
negligible amount of time. The ACAS-Table and ACAS-NN benchmarks require less
time as their models are much simpler. Even then, GAS provides a speedup over
the MCS approach, while having $10\times$ the samples.

Reducing perception model parameters such as $N_{i}$ and the size of $G$ leads
to further speedups. However, we observed that such changes caused significant
reduction in accuracy. We describe these observations in detail in Appendix
0.E.

In conclusion, GAS provides $2.3\times$ to $3.0\times$ speedups over MCS,
despite the additional time required to construct the perception and/or
ancillary model and using ten times more samples than MCS for distribution
estimation.

###  6.3 Can the GAS model be used for fast global sensitivity analysis?

Using the GAS polynomial model, we analytically calculate the first order
Sobol sensitivity indices for the model, as opposed to calculating them using
MCS. Figure 9 shows how one of the first order sensitivity indices for Corn-
Monitor calculated using MCS approaches the value calculated analytically
using the GAS model. The X-Axis shows the number of simulations, while the
Y-Axis shows the index value. Figure 9 shows that $10^{6}$-$10^{7}$ runs are
required to accurately calculate sensitivity indices with MCS. Given the cost
of running the original vehicle model $M_{V}$, for sensitivity analysis with
MCS, we use the abstracted vehicle model $M^{\prime}_{V}$. We present the rest
of the sensitivity index plots like Figure 9 in Appendix 0.F.

Figure 9: Sensitivity Index Comparison

Table 4 Column 6 shows the time taken to calculate all first order sensitivity
indices using MCS and the number of samples used. Column 7 shows the
corresponding times for GAS and Column 8 shows the speedup from 8x-150x.

In conclusion, the GAS model is also a superior alternative to MCS for
calculating the sensitivity indices of the vehicle model.

##  7 Related Work

#### Simulation and modeling of systems.

Althoff et al. [2] model multi-vehicle scenarios using MCS and Markov Chain
models. The Markov Chain approach suffers from discretization error, while MCS
requires many samples. GAS does not suffer from either of these problems.
Kewlani et al. [16] use GPC for analyzing the effects of vehicle _dynamics_
components on the vehicle state. GAS extends the applicability of GPC to end-
to-end vehicle systems with complex components.

Most classical system identification techniques handle only linear systems.
Recently, ARIsTEO [21] used system identification to reduce the cost of
testing cyber-physical systems. Recent techniques that use ML to address
nonlinearity are typically unsuitable for characterizing model uncertainty. In
contrast, GPC both captures model non-linearity and efficiently propagates
uncertainty.

#### Simplification of complex perception and control systems.

Cheng et al. [4] explore the correspondence between a neural network and
polynomial regressions. Unlike their approach, our perception model only needs
to predict the _distribution_ of neural network outputs, instead of individual
input-output relationships. Multiple works construct and verify neural network
alternatives to the ACAS-Xu lookup tables [15, 30]. Our benchmarks use both
the lookup table and neural network. Compared to verification, estimating the
distribution of states using GPC takes only a few seconds. Hsieh et al. [13]
create a perception model using piecewise linear regression, and verify the
perception model composed with downstream components using model checking
tools such as CBMC. In contrast, our perception model uses polynomial
regression, and estimates safe state probabilities using GPC.

#### Formal verification of vehicle systems.

DryVR [9] verifies the safety of vehicle models that have a whitebox mode-
switching control system with a blackbox dynamics system. GAS supports models
with perception neural networks, which act like blackbox control systems due
to their uninterpretability. Researchers have extensively explored the problem
of formal verification of vehicle related systems [3, 5, 12, 14, 19, 23, 26].
Many of these techniques suffer from either a lack of flexibility or
scalability (e.g., can be applied only at a component-level). Recently,
probabilistic analysis techniques started to address these concerns for entire
systems and/or individual components [1, 6, 11, 20]. GAS can provide accurate
reliability estimates for a wide variety of complex vehicle systems whose
simulations and analyses are time-consuming.

##  8 Conclusion

We present GAS, the first methodology for using Generalized Polynomial Chaos
(GPC) to analyze a complete autonomous vehicle navigation system. GAS 1)
creates an analyzable model of the perception subsystem and 2) uses it to
generate a GPC model of the entire system pipeline. GAS accurately models the
system while being 2.3x-3.0x faster than Monte Carlo Simulation on five
scenarios used in agricultural vehicles, self driving cars, and aerial drones.
These results indicate an exciting unexplored potential for GPC and similar
techniques in analysis of autonomous systems. We anticipate future
intersection with symbolic formal methods to jointly improve system
reliability.

## References

  * [1] Abbas, H., Fainekos, G., Sankaranarayanan, S., Ivancic, F., Gupta, A.: Probabilistic temporal logic falsification of cyber-physical systems. TECS 12 (2013)
  * [2] Althoff, M., Mergel, A.: Comparison of markov chain abstraction and monte carlo simulation for the safety assessment of autonomous cars. T-ITS 12 (2011)
  * [3] Aniculaesei, A., Arnsberger, D., Howar, F., Rausch, A.: Towards the verification of safety-critical autonomous systems in dynamic environments. EPTCS 232 (2016)
  * [4] Cheng, X., Khomtchouk, B., Matloff, N., Mohanty, P.: Polynomial regression as an alternative to neural nets (2019)
  * [5] Clarke, E., Fehnker, A., Han, Z., Krogh, B., Stursberg, O., Theobald, M.: Verification of hybrid systems based on cegar. In: TACAS (2003)
  * [6] Converse, H., Filieri, A., Gopinath, D., Pasareanu, C.S.: Probabilistic symbolic analysis of neural networks. In: ISSRE (2020)
  * [7] Du, P., Huang, Z., Liu, T., Ji, T., Xu, K., Gao, Q., Sibai, H., Driggs-Campbell, K., Mitra, S.: Online monitoring for safe pedestrian-vehicle interactions. In: ITSC (2020)
  * [8] Ernst, O., Mugler, A., Starkloff, H.J., Ullmann, E.: On the convergence of generalized polynomial chaos expansions. ESAIM: Mathematical Modelling and Numerical Analysis 46 (2012)
  * [9] Fan, C., Qi, B., Mitra, S., Viswanathan, M.: Dryvr: Data-driven verification and compositional reasoning for automotive systems. In: CAV (2017)
  * [10] Feinberg, J., Langtangen, H.P.: Chaospy: An open source tool for designing methods of uncertainty quantification. Journal of Com. Sci. 11 (2015)
  * [11] Filieri, A., Pasareanu, C.S., Visser, W., Geldenhuys, J.: Statistical symbolic execution with informed sampling. In: FSE (2014)
  * [12] Gros, T.P., Hermanns, H., Hoffmann, J., Klauck, M., Steinmetz, M.: Deep statistical model checking. In: FORTE (2020)
  * [13] Hsieh, C., Li, Y., Sun, D., Joshi, K., Misailovic, S., Mitra, S.: Verifying controllers with vision-based perception using safe approximate abstractions. In: EMSOFT (2022)
  * [14] Jha, S.K., Krogh, B.H., Weimer, J.E., Clarke, E.M.: Reachability for linear hybrid automata using iterative relaxation abstraction. In: HSCC (2007)
  * [15] Julian, K.D., Kochenderfer, M.J.: Guaranteeing safety for neural network-based aircraft collision avoidance systems. In: DASC (2019)
  * [16] Kewlani, G., Crawford, J., Iagnemma, K.: A polynomial chaos approach to the analysis of vehicle dynamics under uncertainty. Veh. Sys. Dyn. 50 (2012)
  * [17] Koenig, N., Howard, A.: Design and use paradigms for gazebo, an open-source multi-robot simulator. In: IROS (2004)
  * [18] Konakli, K., Sudret, B.: Uncertainty quantification in high-dimensional spaces with low-rank tensor approximations. In: UNCECOMP (2015)
  * [19] Larsen, K.G., Mikučionis, M., Taankvist, J.H.: Safe and Optimal Adaptive Cruise Control, pp. 260–277. Springer (2015)
  * [20] Mangal, R., Nori, A.V., Orso, A.: Robustness of neural networks: A probabilistic and practical approach. In: ICSE-NIER (2019)
  * [21] Menghi, C., Nejati, S., Briand, L., Parache, Y.I.: Approximation-refinement testing of compute-intensive cyber-physical models: An approach based on system identification. In: ICSE (2020)
  * [22] Pan, R., Rajan, H.: On decomposing a deep neural network into modules. In: Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (2020)
  * [23] Păsăreanu, C.S., Gopinath, D., Yu, H.: Compositional Verification for Autonomous Systems with Deep Learning Components, pp. 187–197. Springer (2019)
  * [24] Pei, K., Cao, Y., Yang, J., Jana, S.: Deepxplore: Automated whitebox testing of deep learning systems. Commun. ACM 62 (2019)
  * [25] Poëtte, G.: A gpc-intrusive monte-carlo scheme for the resolution of the uncertain linear boltzmann equation. Journal of Computational Physics 385 (2018)
  * [26] Prabhakar, P., Duggirala, P.S., Mitra, S., Viswanathan, M.: Hybrid automata-based cegar for rectangular hybrid systems. In: VMCAI (2013)
  * [27] Robert, C.P., Casella, G.: Monte Carlo statistical methods, vol. 2. Springer (2004)
  * [28] Sivakumar, A.N., Modi, S., Gasparino, M.V., Ellis, C., Velasquez, A.E.B., Chowdhary, G., Gupta, S.: Learned visual navigation for under-canopy ag robots (2021)
  * [29] Sobol, I.: Global sensitivity indices for nonlinear mathematical models and their monte carlo estimates. Mathematics and Computers in Simulation 55 (2001)
  * [30] Tran, H.D., Yang, X., Manzanas Lopez, D., Musau, P., Nguyen, L.V., Xiang, W., Bak, S., Johnson, T.T.: Nnv: The neural network verification tool for deep neural networks and learning-enabled cyber-physical systems. In: CAV (2020)
  * [31] Xiu, D.: Numerical Methods for Stochastic Computations: A Spectral Method Approach. Princeton University Press (2010)

##  Appendix 0.A Multivariate GPC

#### Multivariate GPC.

GPC can be easily extended to the multivariate case, as long as all _all
random variables are independent_. Let $\mathbf{X}=X_{1},\ldots,X_{d}$ be the
$d$ independent random variables and let $f$ be a function over $\mathbf{X}$.
The orthogonal polynomials $\mathbf{\Psi_{i}}$ for $\mathbf{X}$ are simply the
products of the orthogonal polynomials $\Psi_{i_{1}},\ldots,\Psi_{i_{d}}$ for
$X_{1},\ldots,X_{d}$ respectively. The GPC approximation closely resembles the
one for the univariate case:

$f_{N}=\sum\limits_{\mathbf{i}}c_{\mathbf{i}}\mathbf{\Psi_{i}}\qquad\text{where}\qquad
c_{\mathbf{i}}=\frac{\int\limits_{S_{\mathbf{X}}}f(\mathbf{x})\mathbf{\Psi_{i}}(\mathbf{x})p_{\mathbf{X}}(\mathbf{x})d\mathbf{x}}{\int\limits_{S_{\mathbf{X}}}\mathbf{\Psi_{i}}^{2}(\mathbf{x})p_{\mathbf{X}}(\mathbf{x})d\mathbf{x}}$
(4)

We calculate $c_{\mathbf{i}}$, using Gaussian quadrature, in a manner
analogous to the univariate case, but summing over all dimensions of
$\mathbf{i}$.

##  Appendix 0.B Proof Sketch: GAS Convergence

######  Lemma 1 (GPC Error Bound)

The root mean square (RMS) error of the outputs of the GAS model
$M_{\mathit{GPC}}$ with respect to the outputs of $M^{\prime}_{V}$ is bounded.

###### Proof

From [31][Theorem 3.6] and Ernst et al. [8], which state that the RMS error of
a GPC approximation is proportional to $o_{\mathit{gpc}}^{-p}$, where $p$ is a
positive value that depends on the smoothness of the function being
approximated.111For $M^{\prime}_{V}$, the process of obtaining the neural
network output sample using the perception model and the vehicle dynamics are
usually smooth. However, the control system components may not be
differentiable everywhere. ∎

######  Corollary 1 (GPC Convergence)

As $o_{\mathit{gpc}}\rightarrow\infty$, RMS error of GPC approaches 0, that
is, $M_{\mathit{GPC}}$ can be an arbitrarily close approximation of
$M^{\prime}_{V}$.

######  Lemma 2 (Perception Model Convergence)

Assume that for a particular environment distribution $\mathcal{D}_{E}$, the
distribution of neural network outputs in any state is Gaussian. Then, the
output distribution of the perception model $M_{\mathit{per}}$ in any state
approaches the real neural network output distribution at that state as $|G|$,
$N_{i}$, and the degree of the perception model are increased.

###### Proof

Increasing the density of the state tensor grid $G$ increases the number of
ground truth states used to train the perception model. Increasing $N_{i}$
increases the accuracy of the neural network output distribution calculated at
each grid point. Thus, after we increase the number and accuracy of the
training data points, the accuracy of the perception model can be arbitrarily
increased by increasing the degree of polynomial regression (increasing only
the degree of polynomial regression leads to overfitting; increasing the
amount of training data first is necessary.) ∎

######  Theorem 0.B.1 (GAS Convergence)

Assume that for a particular environment distribution $\mathcal{D}_{E}$, the
distribution of neural network outputs in any state is Gaussian. Then, the GAS
model $M_{\mathit{GPC}}$ converges in output distribution to the original
vehicle model $M_{V}$.

###### Proof

Since we can construct an arbitrarily accurate perception model (Lemma 2), we
can use it to obtain accurate neural network output samples for any state
through $M^{\prime}_{V}$. The GPC model can be made an arbitrarily accurate
approximation of $M^{\prime}_{V}$ (Corollary 1), and thus of $M_{V}$. ∎

Practically, controlling the error of the perception model (or any
approximation of a neural network) is an open problem [4, 22]. While precise
analytic calculation of the perception model error is often not tractable, we
can empirically estimate the error after the approximation. After creating
$M^{\prime}_{V}$, $M_{\mathit{GPC}}$ will be the optimal polynomial model of
it for any $o_{\mathit{gpc}}$ ([31][Equation 5.9]).

Finally, our assumption that neural network outputs have a Gaussian
distribution impacts accuracy. We can use standard statistical tests (e.g.,
the Shapiro-Wilk test or the Anderson-Darling test) to check if the assumption
is satisfied while gathering perception model training data. If the
distribution is not approximately Gaussian, one can use a different base
distribution (and orthogonal polynomial) that would better fit the data.

##  Appendix 0.C Vehicle Models with Categorical State Variables

Some vehicle models have categorical state variables. For example, consider an
autonomous plane which avoids a collision by following advisories from a
Collision Avoidance System (CAS) such as [15]. CAS systems take into
consideration the advisory given in the previous time step when giving the
advisory for the current time step. The model for such a vehicle accepts the
previous advisory as a state variable, and returns the current advisory as
part of its updated state.

Unlike categorical variables, polynomial inputs and outputs are totally
ordered. Therefore, we cannot use GPC for predicting categorical variables.
Similarly, we cannot accept a categorical variable as an input to the GPC
model. GAS solves this problem by splitting the GPC approximation problem and
using a separate classifier for predicting categorical variables.

Consider a vehicle model $M_{V}$ whose state includes a categorical variable
$X$ with the domain $\mathbb{D}_{X}=\\{x_{1},\ldots,x_{k}\\}$. GAS uses MEGPC
to create a separate GPC approximation for each $x_{i}\in\mathbb{D}_{X}$. GAS
chooses which of these approximation to use based on the input to the vehicle
model. These GPC approximations calculate all output state variables except
$X$.

For predicting the value of $X$ in the output of $M_{V}$, GAS creates an
ancillary classifier, which it trains as follows:

  1. 1.

GAS picks a set of states $G$ from the safe states $\mathbb{D}_{S}^{S}$, such
that $G$ is an evenly spaced tensor grid that includes the most extreme states
within $\mathbb{D}_{S}^{S}$, and includes all categorical values in
$\mathbb{D}_{X}$.

  2. 2.

For each $g\in G$, GAS evaluates $M_{V}(g,E,R)$ for a large number of samples
($\geq 350$) of $E$ and $R$. GAS isolates the value of $X$ in the output and
calculates the mode value.

  3. 3.

GAS trains a classifier to predict the mode output $X$ value for any
$S\in\mathbb{D}_{S}^{S}$.

GAS returns the mode predicted by the classifier as the value of $X$ in the
output. This method can be generalized to multiple categorical variables, but
the number of separate GPC approximations required can become impractical.

##  Appendix 0.D Visual Distribution Comparisons at Final Time Step

Figure 10: Distribution comparison at final time step. Red: GAS, Green: MCS.

Figure 10 shows a visual comparison of the distributions of each state
variable of each benchmark at the final ($100^{th}$) time step. The red plots
show the CDF of the distribution obtained using GAS, while the green plots
show the distribution obtained using MCS. The name of each benchmark and state
variable is below the corresponding comparison. Visually, the MCS and GAS
distributions closely resemble each other.

##  Appendix 0.E How do Perception Model Parameters Affect GAS Accuracy?

Table 5: Effect of varying perception model parameters on maximum KS statistic (* denotes the value in the evaluation). C-M: Corn-Monitor, C-S: Car-Straight, $\mathit{t_{rel}}$: relative time. $\mathbf{G}$ | C-M | C-S | $\mathbf{t_{rel}}$ | $\mathbf{N_{i}}$ | C-M | C-S | $\mathbf{t_{rel}}$ | degree | C-M | C-S | $\mathbf{t_{rel}}$
---|---|---|---|---|---|---|---|---|---|---|---
7x7 | 0.201 | 0.126 | $0.40\times$ | 100 | 0.288 | 0.120 | $0.29\times$ | 3 | 0.096 | 0.115 | $1.00\times$
9x9 | 0.084 | 0.126 | $0.67\times$ | 350* | 0.081 | 0.126 | $1.00\times$ | 4* | 0.081 | 0.126 | $1.00\times$
11x11* | 0.081 | 0.126 | $1.00\times$ |  |  |  |  | 5 | 0.192 | 0.176 | $1.00\times$

We varied the parameters of the perception model, specifically $G$, $N_{i}$,
and the degree of polynomial regression, to measure their effect on accuracy.
Table 5 shows how these parameters affect the maximum KS statistic for Corn-
Monitor (C-M) and Car-Straight (C-S). Smaller grid sizes (Columns 1-4) and
number of images per grid point (Columns 5-8) decrease the time required to
create the perception model ($\mathit{t_{rel}}$ is relative time usage), but
greatly hinder accuracy. We limit grid size to 11x11 as accuracy improvement
over a 9x9 grid is minimal. Similarly, increasing $N_{i}$ beyond 350 gives
diminishing returns. Using larger grids or $N_{i}$ would unnecessarily
increase the time required to create the perception model. A degree 4
polynomial regression model appears to provide the highest accuracy (Columns
9-12); further increasing degree reduces accuracy (due to overfitting).

In conclusion, perception model parameters can have a significant effect on
end-to-end GAS results, and we must choose them carefully for optimal
accuracy.

##  Appendix 0.F Additional Sensitivity Analysis Plots

Below are additional sensitivity analysis plots for all benchmarks. Each
subplot corresponds to one sensitivity index. In all plots, the X-Axis shows
the number of MCS simulations, while the Y-Axis shows the value of the
sensitivity index. The red plots correspond to the value analytically
calculated by GAS, while the green plots correspond to the value empirically
calculated using MCS. Below each subplot, the label $X\rightarrow Y$ indicates
that the subplot is for the effect of the input variable $X$ on the output
variable $Y$ after one time step. Raw0 and Raw1 correspond to the raw sample
used by the perception model for the Corn-Monitor and Car benchmarks. In most
cases, the MCS values reach those calculated by GAS after $10^{6}-10^{7}$
samples. In some cases where the sensitivity index is very close to 0 or 1,
the MCS and GAS values still differ. This is likely due to the accuracy of GAS
w.r.t. the abstracted vehicle model. However, as indicated by the Y-Axis,
these differences are very small in the absolute sense.