# Testing Rare Downstream Safety Violations via Upstream Adaptive Sampling of
Perception Error Models

Craig Innes and Subramanian Ramamoorthy1,2 1Craig Innes<EMAIL_ADDRESS>and Subramanian Ramamoorthy<EMAIL_ADDRESS>are with the School of
Informatics, University of Edinburgh, Edinburgh, United Kingdom. 2 Work
supported by a grant from the UKRI Strategic Priorities Fund to the UKRI
Research Node on Trustworthy Autonomous Systems Governance and Regulation
(EP/V026607/1, 2020-2024). For the purpose of open access, the author(s) has
applied a Creative Commons Attribution (CC BY) license to any Accepted
Manuscript version arising

###### Abstract

Testing black-box perceptual-control systems in simulation faces two
difficulties. Firstly, perceptual inputs in simulation lack the fidelity of
real-world sensor inputs. Secondly, for a reasonably accurate perception
system, encountering a rare failure trajectory may require running infeasibly
many simulations. This paper combines perception error models—surrogates for a
sensor-based detection system—with state-dependent adaptive importance
sampling. This allows us to efficiently assess the rare failure probabilities
for real-world perceptual control systems within simulation. Our experiments
with an autonomous braking system equipped with an RGB obstacle-detector show
that our method can calculate accurate failure probabilities with an
inexpensive number of simulations. Further, we show how choice of safety
metric can influence the process of learning proposal distributions capable of
reliably sampling high-probability failures.

##  I INTRODUCTION

Perceptual-control systems, such as in automated vehicles (av), must be
rigorously evaluated before deployment. Safety specifications can be defined
formally in Signal Temporal Logic (stl) [1, 2], but the black-box nature and
operating scenario complexity of such systems often preclude analytical
guarantees. Instead, we seek assurances via testing.

While one can aim at the ideal of conducting exhaustive real world tests, this
is infeasible [3]. In addition to the cost, these tests represent danger to
the public. Alternatively, we can simulate our system, but simulation poses
two core problems: First, while modern simulators can replicate real-world
physics with high accuracy, perceptual inputs from a simulated sensor are far
from their real-world counterparts. Figure 1 shows the photorealism gap
between a real and simulated RGB-camera image. In a black-box system with a
mixture of perception and control components, this means that, if we train the
upstream perception components on simulated inputs, we lack assurances that
simulated downstream control failures will correspond to failures experienced
by our system when using real-world sensor inputs.

Figure 1: The difference in fidelity between real traffic images (top) and
simulated images rendered in CARLA (bottom).

However, a key insight is that, to trust our simulation, photorealism may be
unnecessary. It is sufficient that the simulated perception system is accurate
in the same situations as the real one. _Perception Error Models_ (pems) [4]
are surrogate models of a perception system which, instead of taking sensor
inputs, take salient characteristics of those inputs, outputting the expected
accuracy of the target system.

A second problem is, for any modestly accurate perception system, safety
violations can be extremely rare – especially if a system must fail many times
in sequence to cause danger. Consider an automated braking system with an
image-based obstacle detector. If the detector achieves $99\%$ accuracy, and
needs to miss an obstacle for one second to cause a crash, then at 20 images-
per-second, failure probability is $(1.0-0.99)^{20}$. This means we would
expect to run $1\text{\times}{10}^{40}$ simulations before observing _a single
crash_.

Instead of direct sampling, _importance sampling_ draws from a proposal
distribution where failures are likely, then re-weights samples according to
their likelihood under the target. The challenge is finding proposals where
failures are likely, while producing trajectories common under the original
distribution. Existing importance sampling approaches define proposal
distributions over full trajectories, often failing to produce proposals
capable of generating extremely rare events caused by long sequences of
perception failures.

This paper proposes a method for estimating black-box perceptual-control
system failures against stl specifications in simulation. To achieve this, we
first train a pem to mimic a perception system trained on real-world images.
Then, we exploit this pem to drive learning of a low-variance sampler using
_state-dependent_ adaptive importance sampling.

We apply our method to an automated braking scenario in the carla simulator.
The perceptual-control system under test uses a yolo obstacle detector [5]
trained on images from the kitti dataset [6]. Our experiments show that, with
a representative set of training images and sufficiently descriptive salient
variables, our method accurately estimates how upstream perception accuracy
affects downstream safety violations. Since multiple robustness metric choices
exist for stl, our experiments also demonstrate how different metrics affect
the learning process of adaptive sampling.

##  II ESTIMATING THE PROBABILITY OF FAILURE

We first formally describe failure probability estimation for our perceptual-
control system: Our environment contains states $s$ in $d$-dimensional space
$\mathcal{S}=\left\\{(x_{1},\dots,x_{d})\mid x_{1\dots d}\in X_{1\dots
d}\right\\}$. Our perceptual-control system
$\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ will, given state $s$,
output action $a\in\mathcal{A}$ with probability $\pi(a|s)$. In the av domain,
variables $X_{1},\dots,X_{d}$ may include vehicle position/velocity, or pixel
values from a camera; action space $\mathcal{A}$ may consist of whether an
obstacle detection system detects a vehicle in frame.

The probability of transitioning to state $s^{\prime}$ from $s$ is
$p(s^{\prime},a\mid s)=\pi(a\mid s)p(s^{\prime}\mid s,a)$. This paper makes
the simplifying assumption (as in [7]) that the only source of stochasticity
is perception system outputs. E.g., once the perception system decides an
obstacle is ahead, the decision to brake (and effect of braking on velocity)
is deterministic:

$p(s^{\prime},a\mid s)=\pi(a\mid s)$ (1)

Starting from $s_{0}$ we define a $T$-step _simulation rollout_ as
$\tau=\left[s_{0},a_{1},s_{1},a_{2}\dots s_{T-1}\right]$, where the rollout
probability is:

$p(\tau)=\prod_{t=1}^{T-1}\pi(a_{t}\mid s_{t-1})$ (2)

We define a _safety metric_ $r(\varphi,\tau)\in\mathbb{R}$, where $\varphi$ is
a specification, and $r(\varphi,\tau)<0$, denotes violation. Our goal is to
compute the probability our system falls below some safety threshold $\gamma$:

$\mathbb{E}_{\pi}\left[\mathds{1}\left\\{r(\mathbf{\tau},\varphi)\leq\gamma\right\\}\right]=\int_{\tau}\mathds{1}\left\\{r(\mathbf{\tau},\varphi)\leq\gamma\right\\}p(\tau)$
(3)

Subsequent sections describe the components needed to estimate (3) —
specifying $\varphi$ and $r(\tau,\varphi)$, constructing a pem, and learning a
proposal distribution.

###  II-A Specifying Safety Requirements with STL

Signal Temporal Logic (stl) is a language for expressing properties of timed,
continuous signals [8]. Its grammar is:

$\displaystyle\varphi:=\top\mid\eta\mid\neg\varphi\mid\varphi_{1}\wedge\varphi_{2}\mid\square_{I}\varphi\mid\diamondsuit_{I}\varphi\mid\varphi_{1}\mathcal{U}_{I}\varphi_{2}$
(4)

where $\eta$ is any predicate $\rho(s)-b\leq 0$ (with $b\in\mathbb{R}$ and
$\rho:\mathcal{S}\rightarrow\mathbb{R}$). Symbol $\square_{I}\varphi$ means
$\varphi$ is _always_ true at every time-step within interval $I$. Symbol
$\diamond_{I}\varphi$ means $\varphi$ must _eventually_ be true at some time-
step in $I$, and $\varphi_{1}\mathcal{U}_{I}\varphi_{2}$ means $\varphi_{1}$
must remain true within $I$ _until_ $\varphi_{2}$ becomes true. For example:

$\square_{[0,T]}\left(\lVert C_{ego}.pos-C_{other}.pos\rVert\geq 2.0\right)$
(5)

means _“From 0 to T, the distance between the ego car and other car must never
drop below 2 metres”_. stl formulae are paired with a _robustness metric_
$r(\tau,\varphi)\in\mathbb{R}$, specifying how strongly $\tau$ satisfied
$\varphi$ ($r(\tau,\varphi)>0$) or violated $\varphi$ ($r(\tau,\varphi)<0$).
Classical robustness focuses on _spatial robustness_ , applying hard minimums
across conjunctions [8]. For instance, equation (6) evaluates the _always_
operator:

$r(\tau,\square_{[0,T]}\varphi)=\min\left(r(s_{0},\varphi),\dots,r(s_{T},\varphi)\right)$
(6)

Applied to (5), this corresponds to the single state in $\tau$ with the
smallest distance between vehicles.

Alternative robustness metrics exist, each offering trade-offs in time/space
robustness, soundness, and smoothness: agm-robustness [9] replaces the min/max
functions in _always_ /_eventually_ with geometric/arithmetic means; Smooth
Cumulative Robustness [10], combines smooth-approximations to min/max with
cumulative summations.

###  II-B Perception Error Models

In equation (2), $\tau$ is determined by our perceptual model
$\pi(\mathcal{A}\mid s)$. For an obstacle detector, this could be a function
$f$ over RGB images, outputting $detected$ or $\neg detected$:

$\pi(\mathit{detected}\mid s)=f_{\theta}(s)$ (7)

Here $\theta$ could represent e.g., the weights of a Convolutional Neural
Network trained on real traffic images. When testing in simulation however, we
cannot use $f_{\theta}$ directly, since our simulator does not produce real
sensor inputs. We could train an alternative $f$ based on rendered images, but
as discussed in the introduction, such images correspond poorly to the real
world. The added cost of including a rendering and image-processing step in
the simulation pipeline also increases simulation costs by an order of
magnitude.

Here is the key insight of pems: For simulated risk assessment to be useful,
it is sufficient that, for the same state $s$, our surrogate $\hat{f}$ and
function $f$ share the same error:

$\forall s\in\mathcal{S},f_{\theta}(s)=\hat{f}_{\hat{\theta}}(g(s))$ (8)

where $g$ is a projection of $\mathcal{S}$ (which could contain RGB image
pixels, or other sensor data), down to a set of _salient variables_ — a subset
of perceptual features necessary to predict system performance. This may
include obstacle distance to camera, vehicle type, or level of occlusion.

We train $\hat{f}$ using $m$ training samples $D$, consisting of predictions
from our perception system $f$ paired with the corresponding salient
variables:

$D=\\{\langle f(s_{0}),g(s_{0})\rangle,\dots\langle
f(s_{m}),g(s_{m})\rangle\\}$ (9)

We then find the $\hat{\theta}$ which minimizes the binary cross entropy (bce)
between predictions $f_{\theta}(s)$ and $\hat{f}_{\hat{\theta}}(g(s))$:

$\sum_{i=0}^{m}f(s_{i})\log\left[\hat{f}_{\hat{\theta}}(g(s_{i}))\right]+(1-f(s_{i}))\log\left[1-\hat{f}_{\hat{\theta}}(g(s_{i}))\right]$
(10)

Once $\hat{f}_{\hat{\theta}}$ is learned, we can use it as a drop-in surrogate
for $f$ in our simulator by projecting each $s$ down to its salient variables
as they arrive online.

###  II-C Adaptive Importance Sampling

Given $N$ simulations, we can estimate (3) via monte-carlo approximation:

$\hat{\mu}_{\textsc{mc}}=\frac{1}{N}\sum_{i=0}^{N}\mathds{1}_{\left\\{r(\mathbf{\tau_{i}},\varphi)\leq\gamma\right\\}}$
(11)

For rare-events, this is highly inefficient. For $N$ samples, the relative
error [11] is approximately $\sqrt{(N\mu)^{-1}}$. This means to achieve a
$1\%$ relative error with event probability $\mu=10^{-6}$, we need to run
$10^{10}$ simulations. A more efficient approach is to use _importance
sampling_ to draw from a proposal $q$ where the rare-event is more likely,
then re-weight each sample with respect to target distribution $p$:

$\hat{\mu}_{\textsc{is}}=\frac{1}{N}\sum_{i=0}^{N}\mathds{1}_{\left\\{r(\mathbf{\tau_{i}},\varphi)\leq\gamma\right\\}}\frac{p(\tau_{i})}{q(\tau_{i})}$
(12)

Rather than defining distributions over $\tau$, our modified importance
sampler defines proposals over _states_ $s\in\mathcal{S}$:

$\frac{1}{N}\sum_{i=0}^{N}\mathds{1}_{\left\\{r(\mathbf{\tau_{i}},\varphi)\leq\gamma\right\\}}\prod_{t=0}^{T}\frac{\hat{f}_{\hat{\theta}}(g(s_{i,t}))}{q_{\phi}(h(s_{i,t}))}$
(13)

We use $s_{i,t}$ to denote state at time $t$ of the i-th simulation. Following
(2) and (7), we factor $p(\tau)$ as a product of state-dependent outputs from
pem $\hat{f}$. Likewise, $q(\tau)$ is factored as product of probabilities
$q_{\phi}(h(s))$. Note, $h(s)$ does not need to be the same as $g(s)$. $h(s)$
might project $s$ over a small subset of features we suspect influence safety
e.g., vehicle acceleration or velocity.

We want a proposal where failure events are common, and trajectories have high
likelihood under the target distribution. The perfect proposal $q^{*}$ has the
form:

$q^{*}(\tau)=\left(\frac{p(\tau)}{\mu}\right)\mathds{1}_{r(\tau,\varphi)<\gamma}$
(14)

Of course, we do not know $\mu$, but given example trajectories
$[\tau_{0},\dots\tau_{N}]$, we can learn good proposal parameters $\phi$ by
minimizing the KL-divergence between the data and (14):

$-\sum_{i=0}^{N}w_{i}\left(\sum_{t=0}^{T}\log
q_{\phi}(h(s_{i,t}))\right)\mathds{1}_{r(\tau_{i},\varphi)<\gamma}$ (15)

with weights $w_{i}$ defined as:

$w_{i}=\prod_{t=0}^{T}\frac{\hat{f}_{\hat{\theta}}(g(s_{i,t}))}{q_{\phi}(h(s_{i,t}))}$
(16)

However, we have a problem: If no trajectory in $\tau_{0},\dots,\tau_{N}$
passes threshold $\mathds{1}_{r(\tau,\varphi)<\gamma}$, this halts
optimization. To address this, we apply techniques from the cross-entropy
method (cem) literature [11] — Instead of filtering all simulations by
threshold $\gamma$, we iteratively sample multiple batches of simulations. At
each stage $\kappa\in[0,\dots K]$, we run $N_{\kappa}$ simulations, then sort
$\\{\tau_{1},\dots,\tau_{N_{\kappa}}\\}$ by $r(\tau,\varphi)$. In place of
$\gamma$, we set an intermediate threshold
$\gamma_{\kappa}=\max(\gamma,r(\tau_{\sigma N_{\kappa}}))$, where $\sigma$ is
a desired quantile within range $0.95\leq\sigma<1.0$. This ensures some
simulations meet the threshold at every stage, driving incremental proposal
learning via (15).

Because we are finding a proposal via numerical optimization of a product of
state dependent distributions (rather than e.g., a single exponential
distribution admitting a closed-form solution [12, 13, 14]), and because low
safety thresholds are characterized by long chains of consecutive failures, we
have another problem: The difference between the highest and lowest trajectory
weights $w$ may become enormous. This difference can lead to numerical
instability, with less likely trajectories having effectively zero weight
during learning. If those less likely trajectories are necessary to achieve
lower safety thresholds, this can result in the optimization stalling at an
intermediate threshold $\gamma_{\kappa}$.

Defensive Importance Sampling techniques can be used to limit the ratio
between the target and proposal likelihoods for a single state [15], but such
techniques place no limit on weights $w_{i}$ resulting from the _product_ of
likelihood sequences. Instead, our approach is to apply a smoothing parameter
$\alpha\in[0,1]$ to importance weights:

$-\sum_{i=0}^{N}w_{i}^{\alpha}\left(\sum_{t=0}^{T}\log
q_{\phi}(h(s_{i,t}))\right)\mathds{1}_{r(\tau_{i},\varphi)<\gamma}$ (17)

This lessens the gap between the highest and lowest weights, allowing our
adaptive learning process to progress.

Algorithm 1 Simulated Risk Estimation with pems

1:function adaptive-est($D,\varphi,N_{\kappa},N_{e},\gamma$)

2: $\hat{\theta}\leftarrow$ Train pem using $D$ with (10)

3: $\phi\leftarrow$ Initialize proposal distribution

4: for $\kappa=1$ to $K$ do

5: $\\{\tau_{0}\dots\tau_{N_{\kappa}}\\}\leftarrow$ Sample $N_{\kappa}$
rollouts with $q_{\phi}$

6: Sort $\\{\tau_{0}\dots\tau_{N_{\kappa}}\\}$ by $r(\tau,\varphi)$

7: $\gamma_{\kappa}\leftarrow
max\left(\gamma,r\left(\varphi,\tau_{\lfloor\sigma
N_{\kappa}\rfloor}\right)\right)$

8: $\phi\leftarrow$ Min (17) with
$\gamma_{\kappa},q_{\phi},\hat{f}_{\hat{\theta}},\\{\tau_{0}\dots\tau_{N_{\kappa}}\\}$

9: $\\{\tau_{0}\dots\tau_{N_{e}}\\}\leftarrow$ Sample $N_{e}$ rollouts with
$q_{\phi}$

10: return $\hat{\mu_{\textsc{is}}}$ using $\\{\tau_{0}\dots\tau_{N_{e}}\\}$
with (13)

Algorithm (1) Combines our stl robustness components, pem, and adaptive
sampling to give our full method. After training our pem to replicate real-
world perceptual system behaviour as outlined in section (II-B), we perform
$K$ stages of black-box simulation. At each stage $\kappa$, we conduct
$N_{\kappa}$ simulations, set threshold $\gamma_{\kappa}$ based on the upper
quantile of rollouts, then use these rollouts to optimize parameters $\phi$
for the next iteration. After the $K$ iterations, we perform a final $N_{e}$
simulations to estimate failure probability $\mu$.

##  III EXPERIMENTS

Our experiments apply algorithm (1) to an automated braking problem in the
CARLA vehicle simulator [16]. We show our method can estimate the probability
of a rare collision event efficiently, yielding a greater number of high-
probability failure events (compared with classical monte-carlo sampling, or a
naive custom proposal). Further, we show how the choice of stl robustness
metric can affect learning of the proposal distribution.

Figure 2: Automated braking scenario — When the front car abruptly stops, our
vehicle must brake to avoid crashing.

Figure (2) illustrates our scenario: Our car follows another for $T=100$ time
steps. At the end of the road, the front vehicle brakes, and our car must
brake to avoid crashing. We use (5) as our safety condition — If the distance
between vehicles is ever less than 2 metres we consider it a “crash”111Note,
the true distance is less than 2 metres, as we measure from the windscreen
camera to the rear of the other car [6].

Our vehicle’s perceptual-control system comprises two main components: a
physical controller and a perception system. The physical controller is a
simplification of the BasicAgent from the base CARLA
library222https://carla.readthedocs.io: A global planner sets road waypoints
for the car to follow; A local planner applies pid control to reach max speed
if the road is obstacle-free, and applies emergency brakes if there is an
obstacle within 10 metres of the vehicle333Code at
https://github.com/craigiedon/CarlaStuff. The perception system is a neural-
network-based obstacle detector trained on RGB images of real traffic from the
kitti dataset [6]. We first describe how we train a pem from this detector,
then outline its use within CARLA.

###  III-A Learning a pem of the kitti dataset

kitti is an object detection dataset of $1242\times 375$ traffic images, with
labels denoting vehicle type and 2D bounding boxes. It contains 7481 training
and 7518 test images.

The obstacle detection system uses yolo-v3 [5], trained on kitti. Figure 3
sketches yolo’s operation. Images are divided into regions, bounding boxes
produced, and detection probabilities $f(s)$ predicted in one pass through the
network.

Figure 3: (Diagram from [5]) The yolo detector. Images are divided into a
grid. For each grid cell, it predicts B bounding boxes, box confidences, and
class probabilities. Figure 4: pem architecture of 3 feed-forward layers
(20-hidden units each), ReLU activations and Batch Normalization.

We next learn a pem to act as a surrogate $\hat{f}_{\hat{\theta}}$ for our
yolo perception system. Figure (4) shows our feed-forward pem architecture. To
train, we first pre-process the data from our yolo-kitti detector, separating
individual obstacles and pairing them to their closest bounding box prediction
via Hungarian Matching [17]. For salient variables $g(s)$, we use 14
dimensions based on auxilliarly labels provided by the kitti dataset for each
image. The 14 dimensions are: A 6-dimensional one-hot encoding of vehicle
category, a 3-dimensional one-hot encoding for the amount the vehicle is
occluded (None, Partial, Mostly), the $xyz$ obstacle location, and the
rotation of the obstacle on the y-axis. After removing obstacles with unknown
values, we were left with 37498 obstacles to train over. We then minimize loss
function (10) using the Adam Optimizer [18] over $300$ epochs.

Note, our pem training has two limits. First, by considering labels on single
obstacles, our model is unable to capture false positive detections. This is a
common limitation [4], but could be overcome with a more expressive surrogate.
Second, we assume the kitti auxiliary labels are expressive enough to explain
variance in detection performance across the domain. This is likely
untrue—perception systems are affected by additional factors such as time of
day, weather conditions, road surface reflections etc. In an industry-scale
system deployment, we would expect to have dedicated teams of annotators to
design and record a more widely expressive set of salient variables for each
image. These issues lie outside the scope of this paper.

Table (I) summarizes our pem’s performance (ML-NN), via 5-fold cross-
validation. Several baselines are also given: LR fits a logistic regressor;
Guess-$\mu$ returns the mean detection probability. We also fit a complex
Bayesian Neural Network (B-NN). Rather than finding the most likely
$\hat{\theta}$, B-NN learns a distribution over parameters using variational
inference [19]. We report the binary cross-entropy (bce) and area under the
receiver operating characteristic curve (roc-auc) for each model. Across
baselines, our original model ML-NN performs best.

It is perhaps surprising that B-NN does not perform better. It may be that the
variational family used to capture the detection distribution was not
sufficiently expressive. Alternatively, held-out data used in the 5-fold
validation may be insufficiently different from the training data to realise
the benefit of marginalizing over parameters. While not the focus of this
paper, it could be interesting to investigate the performance of such pems in
cases of distribution shift and out-of-domain images.

TABLE I: Results of 5-fold cross validation across perception error models for KITTI obstacle detection task. Model | bce | roc-auc
---|---|---
B-NN | 0.238 | 0.726
LR | 0.244 | 0.688
ML-NN | 0.226 | 0.777
Guess-$\mu$ | 0.260 | 0.5

###  III-B Adaptive Sampling of Rare Crash Events

We now use our pem to drive adaptive sampling in algorithm (1). We run $K=10$
stages, with $N_{\kappa}=100$, and $N_{e}=100$. Each simulation runs for
$T=100$ time steps, with a delta $0.05$. Cars start at 70 km/h, 15 metres
apart.

Proposal network $q_{\phi}$ is a two-layer feed-forward network, with $32$
hidden nodes per layer, and $ReLU$ activations. Transformation function $h(s)$
projects $s$ down to a single dimension—the distance (in metres) between
vehicles. To ensure our initial proposal produces trajectories similar to the
original pem, we pre-train $\phi$ with $100$ simulations from
$\hat{f}_{\hat{\theta}}$. In adaptation stages, we minimize (17) with
$\alpha=0.1$. We use the Adam optimizer [18] for $500$ epochs.

We compare our method ($\textsc{adaptive-pem}_{100}$) to several baselines:
$\textsc{mc}_{100}$ and $\textsc{mc}_{10,000}$ estimate crash probability
using 100 and 10000 raw monte-carlo samples respectively. We also compare
against a naive custom importance sampler ($\textsc{naive-50}_{100}$ and
$\textsc{naive-50}_{1000}$) which ignores state information, instead detecting
obstacles with a flat $50\%$ probability. This is likely to produce more
frequent crashes, but the trajectories may be unlikely under the target.

For our robustness metrics $r(\tau,\varphi)$ used to evaluate thresholds
$\gamma{\kappa}$, we consider three variants—Classical Spatial Robustness
($r_{c}$), agm Robustness ($r_{a}$), and Smooth-Cumulative Robustness
($r_{s}$), with $\gamma=0$ across all three.

###  III-C Results

TABLE II: Estimated failure probabilities under different sampling strategies. Averaged over 10 repetitions, with standard errors given in brackets. Method | $\hat{\mu}$ | Failures | nll
---|---|---|---
$\textsc{mc}_{100}$ | 0.0 | 0 / 100 | -
$\textsc{mc}_{10000}$ | 0.0 | 0 / 10000 | -
$\textsc{naive-50}_{100}$ | 2.64e-48  ($\pm$ 4.69e-49) | 77 / 100 | 199.95
$\textsc{naive-50}_{1000}$ | 4.75e-44  ($\pm$ 2.16e-44) | 748 / 1000 | 177.97
$\textsc{adaptive-pem}_{100}$ | 5.02e-15  ($\pm$ 3.83e-15) | $52/100$ | $\mathbf{41.6}$

Table II shows the results of each sampling strategy. Clearly, raw monte-carlo
sampling is insufficient for this problem — After 10,000 simulations,
$\textsc{mc}_{10000}$ has produced 0 failures, reporting $0\%$ crash
probability. This is unsurprising given the theoretical results around
relative-error combined with the high accuracy of our target detector ($>90\%$
average detection accuracy). Since conducting enough monte-carlo simulations
to extract a ground-truth probability is computationally infeasible, we
instead rely on two proxies—Proportion of final trajectories resulting in a
crash, and average negative log likelihood (nll) of failures.

$\textsc{adaptive-pem}_{100}$, successfully learns a proposal that produces
more than half of its simulations as failures, with an average NLL of 41.6. In
contrast, while naive-50 produces a larger failure proportion, the NLL is far
higher ($199.95$). This means trajectories from naive-50 are
$1\text{\times}{10}^{69}$ times less likely under $\hat{f}_{\hat{\theta}}$
than those from adaptive-pem. As a result, naive-50 is dominated by a few
trajectories with large importance weights, leading to inaccurate estimates of
$\hat{\mu}$. In fact, we can see that as the number of simulations increases
from $100$ to $1000$, naive-50’s estimate gradually moves towards adaptive-
pem’s estimate.

Figure 5: Learned proposal at $\kappa=10$ using Alg (1)

Figure (5) shows the detection rate of adaptive-pem as a function of vehicle
distance. At distances where safety is not a concern, the proposal mimics the
detection accuracy of the original pem (between $98-99.9\%$). As the cars
approach distances where a failure to brake would cause a crash, the proposal
gradually lowers the detection probability.

TABLE III: stl metrics comparison Metric | $\hat{\mu_{\textsc{is}}}$ | Failures | NLL
---|---|---|---
$r_{c}$ | 5.02e-15 ($\pm$ 3.83e-15) | $52/100$ | $41.6$
$r_{a}$ | 6.76e-15  ($\pm$ 3.64e-15) | $41/100$ | $42.4$
$r_{s}$ | 2.01e-15  ($\pm$ 5.38e-16) | $40/100$ | $41.3$
Figure 6: Proposal distributions learned for $r_{c}$, $r_{a}$, and $r_{s}$ at
intermediate adaptation stage $\kappa=3$. Averaged over 10 repetitions. Figure
7: Trajectories for the three lowest ranked simulation runs according to the
$r_{c}$, $r_{a}$, and $r_{s}$ robustness metrics.

For robustness metrics $r(\tau,\varphi)$, Table (III) shows that the final
proposals and $\hat{\mu}$-estimates after $K=10$ adaptation stages is roughly
similar across all three. However, as figure (6) reveals, the behaviour of the
three metrics at intermediate stages can vary.

To understand why this occurs, consider the different ways $r_{c}$, $r_{a}$,
and $r_{s}$ rank the safety of a batch of simulations. Figure (7) shows the
trajectories that each metric chose as “least safe” from a collection of 10000
random simulations. These choices align with our understanding of how each
metric calculates robustness: $r_{c}$ computes robustness as a strict minimum
of distances across all time steps, so chooses the trajectory with the single
smallest distance value. In contrast, $r_{a}$ applies a geometric mean over
distances, leading the metric to choose a trajectory with a (marginally)
higher minimum distance, but which stays lower for a longer time-span.
Finally, $r_{s}$ applies a smoothed approximation to the minimum, leading it
to choose a trajectory somewhere between the absolute minimum and mean values.
These ranking differences affect trajectory sorting in line 6 of Algorithm
(1), which then influences the trajectories chosen in each adaptation stage to
optimize (17)

The main insight is, given limited adaptation budget, the choice of
$r(\tau,\varphi)$ can influence threshold levels $\gamma_{\kappa}$, trajectory
ordering, and potentially learning process behaviour.

##  IV RELATED WORK

Many works test systems via black-box falsification or adaptive-stress testing
[20, 21, 22, 23, 24, 25]. Such works focus on finding a single failure
trajectory, rather than estimating the overall probability of failure.

This paper estimated rare-event failures by augmenting cem techniques [11].
Other works use cem for AV risk estimation [26, 14, 12]. These typically learn
proposals over trajectories, an approach which can fail when rare events
result from a product of probabilities over long-running trajectories.
Additionally, these works often limit themselves to exponential-family
proposals over a set of initial conditions; They avoid sampling perceptual
behaviours of the vehicle itself. Our method instead learns proposals over
individual states, using pems to handle sensor observations.

One state-dependent approach close to ours frames rare-event sampling as an
approximate dynamic programming problem [7]. It requires the user to have
prior knowledge of the transition model, and the ability to jump to arbitrary
states. For black-box simulators like CARLA, neither requirement holds.

An alternative adaptive sampling technique is multi-level splitting [27, 28].
Here initial simulation trajectories are treated as particles which are
perturbed using Markov-Chain Monte Carlo (mcmc). This method scales better to
long-running sequential problems, but conducting mcmc transitions per
trajectory per stage is intractable for simulators with non-trivial run time.

_Continuation approaches_ use earlier perception system training epochs as a
proxy for proposal stages [29]. They assume the user has access to earlier
training checkpoints, and that failures in those earlier stages are similar to
those encountered by the final system.

pems are applied in av as surrogates for image, radar, and lidar sensors [4,
30, 31, 32]. The primary motivation of such applications is usually to bypass
expensive rendering, providing fast, low-fidelity predictions. In contrast,
our work takes advantage of the probabilistic outputs provided by pems to also
drive adaptive importance sampling.

We make the core assumption that our pem is _well calibrated_ [33]. Several
issues can challenge this assumption. First, our model may encounter
_epistemic uncertainty_ if images in simulation are far from the training
distribution [34]. Second, our model may encounter _aleatoric uncertainty_ if
the salient variables insufficiently express relevant safety aspects of a
scene [35]. In future work, we aim to explore this relationship between
epistemic/aleatoric uncertainty in the upstream perceptual system, and the
guarantees given on downstream failures.

There have been multiple attempts to encode complex traffic rules using
temporal logic [36, 37, 1, 2]. In future work, we aim to scale our method from
automated braking to more complex traffic scenarios, investigating the effect
of balancing multiple competing rules.

For testing of black-box systems, one issue is assessing trust in your final
estimation. Safety certificates help ensure risk is not under or over-
estimated [38, 39, 40, 41]. These techniques are complementary to our task,
and can be applied as an additional step after sampling.

##  V CONCLUSION

This paper proposed a method for testing black box perceptual-control systems
in simulation, even when the perception system takes real-world sensor inputs,
and failures are rare. We used pems to drive state-dependent adaptive
importance samplers, with an stl robustness metric to assess failure
thresholds. Our experiments in automated braking showed our method efficiently
estimates rare failure probabilities, learning distributions that generate a
high percentage of high-likelihood failure trajectories.

## References

  * [1] M. Hekmatnejad, S. Yaghoubi, A. Dokhanchi, H. B. Amor, A. Shrivastava, L. Karam, and G. Fainekos, “Encoding and monitoring responsibility sensitive safety rules for automated vehicles in signal temporal logic,” in _Proceedings of the 17th ACM-IEEE International Conference on Formal Methods and Models for System Design_ , 2019, pp. 1–11.
  * [2] N. Arechiga, “Specifying safety of autonomous vehicles in signal temporal logic,” in _2019 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2019, pp. 58–63.
  * [3] N. Kalra and S. M. Paddock, “Driving to safety: How many miles of driving would it take to demonstrate autonomous vehicle reliability?” _Transportation Research Part A: Policy and Practice_ , vol. 94, pp. 182–193, 2016.
  * [4] J. Sadeghi, B. Rogers, J. Gunn, T. Saunders, S. Samangooei, P. K. Dokania, and J. Redford, “A step towards efficient evaluation of complex perception tasks in simulation,” _arXiv preprint arXiv:2110.02739_ , 2021.
  * [5] J. Redmon and A. Farhadi, “Yolov3: An incremental improvement,” _arXiv preprint arXiv:1804.02767_ , 2018.
  * [6] A. Geiger, P. Lenz, C. Stiller, and R. Urtasun, “Vision meets robotics: The kitti dataset,” _The International Journal of Robotics Research_ , vol. 32, no. 11, pp. 1231–1237, 2013.
  * [7] A. Corso, R. Lee, and M. J. Kochenderfer, “Scalable autonomous vehicle safety validation through dynamic programming and scene decomposition,” in _2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2020, pp. 1–6.
  * [8] A. Donzé and O. Maler, “Robust satisfaction of temporal logic over real-valued signals,” in _International Conference on Formal Modeling and Analysis of Timed Systems_. Springer, 2010, pp. 92–106.
  * [9] N. Mehdipour, C.-I. Vasile, and C. Belta, “Arithmetic-geometric mean robustness for control from signal temporal logic specifications,” in _2019 American Control Conference (ACC)_. IEEE, 2019, pp. 1690–1695.
  * [10] I. Haghighi, N. Mehdipour, E. Bartocci, and C. Belta, “Control from signal temporal logic specifications with smooth cumulative quantitative semantics,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_. IEEE, 2019, pp. 4361–4366.
  * [11] D. P. Kroese, R. Y. Rubinstein, and P. W. Glynn, “The cross-entropy method for estimation,” in _Handbook of statistics_. Elsevier, 2013, vol. 31, pp. 19–34.
  * [12] Y. Kim and M. J. Kochenderfer, “Improving aircraft collision risk estimation using the cross-entropy method,” _Journal of Air Transportation_ , vol. 24, no. 2, pp. 55–62, 2016.
  * [13] D. Zhao, H. Lam, H. Peng, S. Bao, D. J. LeBlanc, K. Nobukawa, and C. S. Pan, “Accelerated evaluation of automated vehicles safety in lane-change scenarios based on importance sampling techniques,” _IEEE transactions on intelligent transportation systems_ , vol. 18, no. 3, pp. 595–607, 2016.
  * [14] M. O' Kelly, A. Sinha, H. Namkoong, R. Tedrake, and J. C. Duchi, “Scalable end-to-end autonomous vehicle testing via rare-event simulation,” in _Advances in Neural Information Processing Systems_ , vol. 31, 2018.
  * [15] M. F. Bugallo, V. Elvira, L. Martino, D. Luengo, J. Miguez, and P. M. Djuric, “Adaptive importance sampling: The past, the present, and the future,” _IEEE Signal Processing Magazine_ , vol. 34, no. 4, pp. 60–79, 2017.
  * [16] 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.
  * [17] D. A. Forsyth and J. Ponce, _Computer vision: a modern approach_. prentice hall professional technical reference, 2002.
  * [18] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _CoRR_ , vol. abs/1412.6980, 2014.
  * [19] L. V. Jospin, H. Laga, F. Boussaid, W. Buntine, and M. Bennamoun, “Hands-on bayesian neural networks—a tutorial for deep learning users,” _IEEE Computational Intelligence Magazine_ , vol. 17, no. 2, pp. 29–48, 2022.
  * [20] T. Dreossi, S. Jha, and S. A. Seshia, “Semantic adversarial deep learning,” in _International Conference on Computer Aided Verification_. Springer, 2018, pp. 3–26.
  * [21] T. Dreossi, A. Donzé, and S. A. Seshia, “Compositional falsification of cyber-physical systems with machine learning components,” _Journal of Automated Reasoning_ , vol. 63, no. 4, pp. 1031–1053, 2019.
  * [22] Y. Annpureddy, C. Liu, G. Fainekos, and S. Sankaranarayanan, “S-taliro: A tool for temporal logic falsification for hybrid systems,” in _International Conference on Tools and Algorithms for the Construction and Analysis of Systems_. Springer, 2011, pp. 254–257.
  * [23] K. D. Julian, R. Lee, and M. J. Kochenderfer, “Validation of image-based neural network controllers through adaptive stress testing,” in _2020 IEEE 23rd international conference on intelligent transportation systems (ITSC)_. IEEE, 2020, pp. 1–7.
  * [24] R. Lee, O. J. Mengshoel, A. Saksena, R. W. Gardner, D. Genin, J. Silbermann, M. Owen, and M. J. Kochenderfer, “Adaptive stress testing: Finding likely failure events with reinforcement learning,” _Journal of Artificial Intelligence Research_ , vol. 69, pp. 1165–1201, 2020.
  * [25] H. Delecki, M. Itkina, B. Lange, R. Senanayake, and M. J. Kochenderfer, “How do we fail? stress testing perception in autonomous vehicles,” _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 5139–5146, 2022.
  * [26] D. Zhao, X. Huang, H. Peng, H. Lam, and D. J. LeBlanc, “Accelerated evaluation of automated vehicles in car-following maneuvers,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 19, no. 3, pp. 733–744, 2017.
  * [27] J. Norden, M. O’Kelly, and A. Sinha, “Efficient black-box assessment of autonomous vehicle safety,” _arXiv preprint arXiv:1912.03618_ , 2019.
  * [28] A. Sinha, M. O’Kelly, R. Tedrake, and J. C. Duchi, “Neural bridge sampling for evaluating safety-critical autonomous systems,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 6402–6416, 2020.
  * [29] J. Uesato, A. Kumar, C. Szepesvari, T. Erez, A. Ruderman, K. Anderson, K. Dvijotham, N. Heess, and P. Kohli, “Rigorous agent evaluation: An adversarial approach to uncover catastrophic failures,” in _International Conference on Learning Representations_ , 2019.
  * [30] P. Mitra, A. Choudhury, V. R. Aparow, G. Kulandaivelu, and J. Dauwels, “Towards modeling of perception errors in autonomous vehicles,” in _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2018, pp. 3024–3029.
  * [31] A. Piazzoni, J. Cherian, M. Slavik, and J. Dauwels, “Modeling perception errors towards robust decision making in autonomous vehicles,” in _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence_ , 2021.
  * [32] V. Berkhahn, M. Kleiber, J. Langner, C. Timmermann, and S. Weber, “Traffic dynamics at intersections subject to random misperception,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 5, pp. 4501–4511, 2021.
  * [33] J. Gawlikowski, C. R. N. Tassi, M. Ali, J. Lee, M. Humt, J. Feng, A. Kruspe, R. Triebel, P. Jung, R. Roscher, _et al._ , “A survey of uncertainty in deep neural networks,” _arXiv preprint arXiv:2107.03342_ , 2021.
  * [34] M. Sensoy, L. Kaplan, and M. Kandemir, “Evidential deep learning to quantify classification uncertainty,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [35] A. Kendall and Y. Gal, “What uncertainties do we need in bayesian deep learning for computer vision?” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [36] L. Gressenbuch and M. Althoff, “Predictive monitoring of traffic rules,” in _2021 IEEE International Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2021, pp. 915–922.
  * [37] S. Maierhofer, P. Moosbrugger, and M. Althoff, “Formalization of intersection traffic rules in temporal logic,” in _2022 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2022, pp. 1135–1144.
  * [38] X. Qin, Y. Xian, A. Zutshi, C. Fan, and J. V. Deshmukh, “Statistical verification of cyber-physical systems using surrogate models and conformal inference,” in _2022 ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS)_ , 2022, pp. 116–126.
  * [39] H. L. Younes, “Probabilistic verification for “black-box” systems,” in _International Conference on Computer Aided Verification_. Springer, 2005, pp. 253–265.
  * [40] M. Arief, Z. Huang, G. K. S. Kumar, Y. Bai, S. He, W. Ding, H. Lam, and D. Zhao, “Deep probabilistic accelerated evaluation: A robust certifiable rare-event simulation methodology for black-box safety-critical systems,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2021, pp. 595–603.
  * [41] C. Harper, G. Chance, A. Ghobrial, S. Alam, T. Pipe, and K. Eder, “Safety validation of autonomous vehicles using assertion-based oracles,” _arXiv preprint arXiv:2111.04611_ , 2021.