AAM

    advanced air mobility
ACC

    adaptive cruise control
ADAS

    advanced driver assistance system
AEB

    automatic emergency braking
AI

    artificial intelligence
ATG

    automatic test generation
AV

    autonomous vehicle
CA

    California
CA DMV

    California Department of Motor Vehicles
CARLA

    CARs Learning to Act
CE

    Cross Entropy
CP

    correctness property
CPS

    cyberphysical system
DL

    deep learning
DNN

    deep neural network
DoD

    Department of Defense
DTW

    dynamic time warping
EDA

    electronic design automation
FM

    formal methods
FOL

    first order logic
FV&V

    formal verification and validation
GAN

    Generative Adversarial Network
GPU

    graphics processing unit
HOL

    higher-order logic
HVT

    high-value target
IED

    improvised explosive device
IoT

    internet of things
ISR

    intelligence, surveillance, and reconnaissance
KL

    Kullback-Leibler
LKA

    lane keeping assist
LSTM

    long short-term memory
LTL

    linear-time propositional temporal logic
LV&V

    lightweight verification and validation
ML

    machine learning
MLCP

    machine-learned correctness property
MTL

    metric temporal logic
MTS

    multivariate time series
NASA

    National Aeronautics and Space Administration
NL

    natural language
PDF

    probability distribution function
PED

    processing, exploitation, and dissemination
R&D

    research and development
RDF

    random decision forest
RM

    runtime monitoring
RNN

    recurrent neural network
RV

    random variable
SAE

    Society of Automotive Engineers
SITL

    software-in-the-loop
SME

    subject matter expert
STL

    signal temporal logic
SUT

    system under test
SVM

    support vector machine
TEVV

    test and evaluation, verification and validation
TL

    temporal logic
TTC

    time-to-collision
UAS

    unmanned aerial system
VM

    virtual machines
V&V

    verification and validation
USN

     United States (U.S.) Navy
USG

     U.S. Government

This work has been submitted to the IEEE for possible publication. Copyright
may be transferred without notice, after which this version may no longer be
accessible.

# Discovering Decision Manifolds to
Assure Trusted Autonomous Systems

Matthew Litton, Doron Drusinsky, and James Bret Michael M. Litton, J. Michael,
and D. Drusinsky are with with the Department of Computer Science at the Naval
Postgraduate School, Monterey, CA, 93943.
E-mail: {matthew.litton, ddrusins<EMAIL_ADDRESS>This research is
sponsored by the U.S. Department of the Navy.

###### Abstract

Developing and fielding complex systems requires proof that they are reliably
correct with respect to their design and operating requirements. Especially
for autonomous systems which exhibit unanticipated emergent behavior, fully
enumerating the range of possible correct and incorrect behaviors is
intractable. Therefore, we propose an optimization-based search technique for
generating high-quality, high-variance, and non-trivial data which captures
the range of correct and incorrect responses a system could exhibit. This
manifold between desired and undesired behavior provides a more detailed
understanding of system reliability than traditional testing or Monte Carlo
simulations. After discovering data points along the manifold, we apply
machine learning techniques to quantify the decision manifold’s underlying
mathematical function. Such models serve as correctness properties which can
be utilized to enable both verification during development and testing, as
well as continuous assurance during operation, even amidst system adaptations
and dynamic operating environments. This method can be applied in combination
with a simulator in order to provide evidence of dependability to system
designers and users, with the ultimate aim of establishing trust in the
deployment of complex systems. In this proof-of-concept, we apply our method
to a software-in-the-loop evaluation of an autonomous vehicle.

###### Index Terms:

verification and validation, system reliability, accountable intelligence,
machine learning, intelligent autonomous systems, trusted autonomy, formal
methods.

##  I Introduction

Providing evidence that a system behaves correctly with respect to its design
and operating requirements necessitates an oracle that can immediately and
unambiguously determine if a behavior is correct or incorrect. For relatively
simple systems such as traffic lights, such oracles can be easily encoded in
natural language (e.g., if a traffic light is yellow, its next state must be
red) or more formal representations like propositional logic (e.g.,
$CURRENT\\_STATE_{YELLOW}\implies NEXT\\_STATE_{RED}$). For such systems, all
possible states can be enumerated, and then the system can be tested in its
operational environment to guarantee that it performs correctly for a set of
test cases that provides complete coverage of all possible system responses.

Autonomous systems pose significant difficulties to this method. First, the
full range of system responses cannot be known, both because many autonomous
systems operate in dynamic environments which cannot be fully modeled, and
because such systems often use machine learning (ML) algorithms to enable
continuous adaptation. Second, testing systems in their operational
environment to ensure they behave correctly is not always effective.
Relatively mature systems, such as many autonomous vehicles, often exhibit
critical failures very rarely, making it unlikely that testing alone will
discover those instances. Other systems, such as nuclear survivability
systems, cannot be tested in an operational environment due to the dangers
they pose to humans and the environment (see Fig. 1). To address this
challenge, we propose an approach where a system’s behavior can be enumerated
early in design and testing to discover both correct and incorrect behaviors,
including rare events that are unlikely to be observed until well after
deployment. Then, such behaviors are synthesized into a mathematical function
representing a correctness property (CP) which can be executed on future
behaviors, determining if a system’s response was correct, even for previously
unobserved behaviors. Then, we propose a similar technique to go beyond
monitoring system behavior to actually predicting and assuring correct
behavior. By demonstrating that potential failures can be detected in advance,
we provide a means to mitigate the potential for death, injury, damage to
property, and damage to the environment that autonomous systems pose.

Figure 1: In other work, we applied our approach to the Defense Threat
Reduction Agency’s (DTRA) Mission Impact of Nuclear Effects Software (MINES)
to discover a decision manifold for military nuclear survivability. This
technique is applicable to any complex system, including autonomous systems,
with a realistic simulation capability.

The core contribution of this paper is the description and implementation of
an algorithm (HybridPair Cross Entropy (CE)) which discovers decision
manifolds to verify and assure correct system behavior. Additionally, we
describe our ML approach to mathematically quantifying the manifold for use as
CP. Then, we show how such ML models can be utilized for verifying,
validating, and assuring autonomous system behavior to provide evidence of the
system’s dependability and enable their trusted deployment.

The paper is organized as follows. In the rest of this section, we clarify
terms and definitions related to CP, as well as propose a new term: machine-
learned correctness properties. In Section II we discuss related work. Section
III provides background related to the CE method and Section IV discusses our
modification to the algorithm. Sections V and VI detail the experiment and its
results, and Sections VII and VIII discuss the implications of the results and
avenues for future work. Finally, Section IX concludes the discussion,
highlighting the importance of this research.

###  I-A Formal and Practical Properties: Terms and Definitions

Several closely related terms are often used in the verification and
validation (V&V) literature: correctness properties, formal specifications,
natural language requirements, and assertions. As a contribution of our
research, we add a fourth term: machine-learned correctness properties.

Figure 2: The relationship between correctness properties and its various sub-
types.

As depicted in Fig. 2, correctness properties is an umbrella term which refers
to descriptions of acceptable or unacceptable system behavior. Often, these
requirements are first written in natural language, but ambiguous, context-
sensitive languages (e.g., unconstrained English sentences) are not amenable
to automated verification. Therefore, experts manually translate such
requirements into an unambiguous, usually machine-readable form. Historically,
the term specification has dominated the literature because much of the
academic research has focused on human specified properties of interest, using
dedicated formal specification languages. Assertions typically refer
specifically to requirements that are embedded in the source code (e.g., the C
library <assert.h>).

####  I-A1 Machine-Learned Correctness Properties

We propose an alternative to logic-based CP in the form of MLCP. MLCP are ML
models which are trained to determine whether a system is behaving correctly
or incorrectly with respect to some requirement. They seek the same goal as
formally specified properties or embedded assertions which is: to accurately
represent correct system behavior so that a system’s compliance with its
requirements can be verified or monitored. This idea follows from the ideas
presented in our earlier position papers ([1, 2]), but this work actually
describes the construction and evaluation of MLCP in detail, and we apply this
approach to AVs to demonstrate their usefulness. Using ML classifiers which
are trained using actual system data to discover undesired behavior during
testing, and monitor system behavior during operation, addresses weaknesses
associated with logic-based CP. First, developing CP by training ML models
brings the task of developing robust CP from the realm of Ph.D.-level experts
into the domain of system developers and engineers. Secondly, rather than
translating human-specified CP into executable code for embedding in the
implementation software, MLCP automatically learn a model that represents the
underlying requirement, and such models are already executable. Third, the
expressive power of MLCP extends to the entirety of the operational domain of
the system under test (SUT). Because MLCP use actual system behavior with the
environmental configuration, any behavior or interaction that the system can
experience, and any configuration of the surrounding environment, can be used
to train the model.

##  II Related Work

Two of the areas of research that are related to the research on MLCP are:
search-based techniques for scenario generation (Section II-A), and anomaly
and incident detection for cyberphysical systems (Section II-B).

###  II-A Automated Generation of Scenarios for Cyberphysical Systems

Because the entire state space of most autonomous CPSs cannot be explored
prior to deployment, it is of particular interest to developers (including
testers) to identify situations under which a system is most likely to violate
its CP (e.g., falsification). These are widely known as ”critical events.” The
use of falsification to identify such scenarios has been widely explored in
the literature. In [3], the authors model an artificial pancreas controller
for Type-1 diabetics, and demonstrate the use of S-Taliro, a falsification
engine, for finding violations of metric temporal logic (MTL)-specified CP. In
nearly all cases, these methods are still largely applied to isolated systems
(i.e., without modeling external actors or environmental factors) with finite
state spaces. Other researchers have opted for statistical methods to identify
critical events. Researchers used Monte Carlo sampling of stochastic models of
driving behavior to evaluate AVs in the presence of human drivers, but they
discovered the occurrence of unsafe events was very low [4]. In addition,
generating such scenarios in naturalistic driving conditions is expensive and
slow. To accelerate the search for events of interest, researchers have used
importance sampling methods which can generate a new probability distribution
with a higher likelihood of critical events. The authors in [4] use the CE
method to find an importance sampling distribution that identifies unsafe
lane-change behavior by human drivers to accelerate the evaluation of AV
software stacks. Similarly, O’Kelly et al. developed a custom simulation
framework that utilizes adaptive importance sampling methods to significantly
accelerate the evaluation of deep-learning based AVs compared to open-road
testing [5]. Likewise, Ding et al. explored using deep generative models as an
alternative to importance sampling techniques for generating safety-critical
scenarios [6].

###  II-B Anomaly and Incident Detection for Cyberphysical Systems

Multiple researchers have proposed methods of detecting incorrect behavior in
CPSs through anomaly detection. Chen et al. [7] used supervised learning
approaches to learn and monitor invariants of a water treatment testbed. They
collect execution traces from the system under normal operating conditions,
and then inject faults into the system’s underlying software, simulating
malicious cyber attacks, to collect execution traces under abnormal operating
conditions. They then use support vector machines to learn a model of correct
behavior and monitor the system during runtime. However, they find that they
must generate over 500 mutants (i.e., faults injected into the software) in
order to accurately learn invariants; verifying that the mutations accurately
reflect realistic malicious cyber activity, as well as generating and
simulating the mutated code can be time consuming for certain applications. In
[8], the authors use unsupervised clustering techniques to automatically learn
oracles that can determine if a CPS is behaving correctly. They apply a multi-
step procedure to cluster telemetry logs, making the assumption that incorrect
behavior is likely to be rare, while correct behavior occurs frequently. Xiao
et al. [9] note that predicting imminent incidents, including collisions, is a
key enabler for the reliable deployment of AVs. In their survey, they note
that in addition to rule-based and probabilistic methods for predicting
hazardous events, ML-based methods can allow greater generalization and
scalability when learning causal factors for hazardous events [9].

##  III The CE Method

Section III-A provides an overview of the CE method and is meant to facilitate
the reader’s understanding of Section IV where we describe how we use the CE
method to generate data for training and testing ML models which serve as
MLCP.

###  III-A Cross-Entropy Method

The CE method derives its name from the cross-entropy (a.k.a., Kullback-
Leibler (KL)) distance which is a fundamental concept in information theory.
It was originally developed for estimating the probability of rare events
based on variance minimization, and has been adapted for solving combinatorial
optimization problems [10]. Certain optimization and estimation problems are
static and can be solved analytically; many estimation problems are noisy,
meaning the objective function is unknown and must be estimated. The
dependability analysis of complex systems, including CPSs, is one such
problem.

At its most basic level, the Cross-Entropy Method is an iteration of the two
steps of Algorithm 1.

Algorithm 1 One Iteration of the Basic Cross-Entropy Algorithm

1: Generate a volume of data samples (trajectories, paths, etc.) according to
some specified mechanism, using an existing distribution of random variables.

2: Update RV distributions using an elite subset of scored samples generated
in Step 1, to produce improved distributions for the next iteration.

In order to implement Algorithm 1, three essential factors must be defined:

  1. 1.

The family of probability distributions functions $\\{f(\cdot;\mathbf{v})\\}$
which is used to generate the random samples

  2. 2.

The method of scoring the samples in order to determine which are “better”

  3. 3.

The updating rules for the parameters (based on cross-entropy minimization)

With the above three ingredients supplied, the general algorithm can be
applied to any discrete and continuous optimization problem by implementing
Algorithm 2. This method is referred to as importance sampling because the
probability distribution parameter update (Algorithm 2, Step 6) is based on an
elite subset of samples which are deemed to be the most “important”
((Algorithm 2, Step 5).

Algorithm 2 Cross-Entropy Algorithm for Optimization

1: Initialize parameter vectors ($\mathbf{u}$) for each random initial
distribution

2: Define $\widehat{\mathbf{v}}_{0}=\mathbf{u}$. Set $t=1$.

3: Generate N samples $\mathbf{X_{1},\ldots,X_{N}}$ from the distributions
$f(\cdot;\widehat{\mathbf{v}}_{t-1})$

4: Calculate the performance $S(\mathbf{X}_{i})$ for all i, order them from
smallest to largest: $S_{(1)}\leqslant\ldots\leqslant S_{(N)}$

5: Compute the sample $(1-\rho)\\!-\\!quantile$ as:
$\widehat{\gamma_{t}}=S_{(\lceil(1-\rho)N\rceil)}$ (i.e., the gamma element)
as well as the elite set which consists of the set of vectors satisfying
$S(\mathbf{X}_{i})\geqslant\widehat{\gamma_{t}}$

6: Update the parameter vector $\widehat{\mathbf{v}}_{t-1}$ to
$\widehat{\mathbf{v}}_{t}$ using the elite set and optional smoothing
parameter $\alpha$:
$\widehat{\mathbf{v}}_{t}=\alpha\widehat{\mathbf{v}}_{t}+(1-\alpha)\widehat{\mathbf{v}}_{t-1}$

7: If for some $t\geq d$, say $d=3$,
$\widehat{\gamma_{t}}=\widehat{\gamma}_{t-1}=\ldots=\widehat{\gamma}_{t-d}$
then stop, otherwise, set $t=t+1$ and reiterate from Step 3

Note: The initial vector $\mathbf{u}$, the sample size $N$, the stopping
parameter $d$, and the number $\rho$ have to be specified in advance, but the
rest of the algorithm is “self-tuning”.

The foundation of the CE method is to estimate the optimal importance sampling
probability distribution function (PDF) $g^{*}$ by choosing from a parametric
class of PDFs $f(\cdot;\mathbf{v})$. The CE estimation minimizes the distance
between the the optimal PDF $g^{*}$ and that of $f$. [11]. The KL divergence
between $g^{*}$ and $f$ is given by:

$\displaystyle\mathcal{D}_{KL}(g^{*},f)$ $\displaystyle=\int
g^{*}(\mathbf{x})\ln\frac{g^{*}(\mathbf{x})}{f(\mathbf{x})}d\mathbf{x}=\mathbb{E}\left[\ln\frac{g^{*}(\mathbf{X})}{f(\mathbf{X})}\right],\mathbf{X}\sim
g^{*}$ $\displaystyle=\int g^{*}(\mathbf{x})\ln
g^{*}(\mathbf{x})d\mathbf{x}-\int g^{*}(\mathbf{x})\ln
f(\mathbf{x})d\mathbf{x}$ (1)

In order to minimize $\mathcal{D}_{KL}$, we need to maximize the right hand
side of Equation III-A:

$\max_{\mathbf{v}}\int g^{*}(\mathbf{x})\ln f(\mathbf{x;v})d\mathbf{x}$ (2)

Using importance sampling space, we get:

$\displaystyle\max_{\mathbf{v}}\int\mathrm{I}_{\\{S(\mathbf{X})\geqslant\gamma\\}}\ln
f(\mathbf{x;v})d\mathbf{x}$ $\displaystyle=$
$\displaystyle\max_{\mathbf{v}}\mathbb{E}_{\mathbf{u}}\mathrm{I}_{\\{S(\mathbf{X})\geqslant\gamma\\}}\ln
f(\mathbf{X;v})$ (3)

Using change of measure (i.e., from $\mathbf{u}$ to some $\mathbf{w}$), the CE
method is reduced to a search for the optimal reference parameter vector,
$\mathbf{v}^{*}$ of $g^{*}$, through CE minimization:

$\displaystyle\mathbf{v}^{*}$
$\displaystyle=\operatorname*{argmin}_{\mathbf{v}}\mathcal{D}_{KL}(g^{*},f(\cdot;\mathbf{v}))$
$\displaystyle=\operatorname*{argmax}_{\mathbf{v}}\mathbb{E}_{\mathbf{u}}\mathrm{I}_{\\{S(\mathbf{X})\geqslant\gamma\\}}\ln
f(\mathbf{X};\mathbf{v})$
$\displaystyle=\operatorname*{argmax}_{\mathbf{v}}\mathbb{E}_{\mathbf{w}}\mathrm{I}_{\\{S(\mathbf{X})\geqslant\gamma\\}}\ln
f(\mathbf{X};\mathbf{v})\frac{f(\mathbf{X;u})}{f(\mathbf{X;w})}$ (4)

where the subscript in the expectation operator indicates the density of
$\mathbf{X}$. This $\mathbf{v}^{*}$ can be estimated via the stochastic
counterpart of Equation III-A:

$\widehat{\mathbf{v}}=\operatorname*{argmax}_{\mathbf{v}}\frac{1}{N}\sum^{N}_{k=1}\mathrm{I}_{\\{S(\mathbf{X}_{i})\geqslant\gamma\\}}W(\mathbf{X}_{k};\mathbf{u,w})\ln
f(\mathbf{X}_{k};\mathbf{v})$ (5)

where
$W(\mathbf{X}_{k};\mathbf{u,w})=\frac{f(\mathbf{X}_{k};\mathbf{u})}{f(\mathbf{X}_{k};\mathbf{w})}$

The optimal parameter $\widehat{\mathbf{v}}$ in Equation 5 can often be
obtained in explicit form, in particular when the class of sampling
distributions forms an exponential family (e.g., exponential, normal,
categorical, and multinomial)[11], as discussed in the next two sections.

####  III-A1 Optimal Parameter Estimation for Normal Distributions

If RVs $\mathbf{X}_{1},\ldots,\mathbf{X}_{N}$ are drawn from
$\mathbf{X}\sim\mathcal{N}(\widehat{\mu}_{t-1},\widehat{\sigma}^{2}_{t-1})$,
then $\mathbf{X}_{1},\ldots,\mathbf{X}_{N}$ can be used to update the
parameters $\widehat{\mu}_{t}$ and $\widehat{\sigma}^{2}_{t}$ using the
following formulas [11]:

Let $N^{e}=\lceil\rho\cdot N\rceil$ (i.e., the number of items in the elite
set) and let $\mathcal{I}$ be the indices of $N^{e}$.
For all $j=1,\ldots,n$ let

$\widehat{\mu}_{t,j}=\frac{1}{N^{e}}\sum_{k\in\mathcal{I}}W(X_{k,j};u,w_{t-1})\cdot
X_{k,j}$ (6)
$\widehat{\sigma}^{2}_{t,j}=\frac{1}{N^{e}}\sum_{k\in\mathcal{I}}(W(X_{k,j};u,w_{t-1})\cdot
X_{k,j}-\widehat{\mu}_{t,j})^{2}$ (7)

where $w_{t-1}=\langle{\mu}_{t-1},{\sigma}^{2}_{t-1}\rangle$

####  III-A2 Optimal Parameter Estimation for Multinomial Distributions

The multinomial distribution models the outcome of $n$ experiments where the
outcome of each experiment is a categorical distribution. A widely used
example is where $(X_{1},\ldots,X_{n})$ has independent components such that
$X_{i}=j$ with probability $v_{i,j},i=1,\ldots,n,j=1,\ldots,m$.

If RVs $\mathbf{X}_{1},\ldots,\mathbf{X}_{N}$ are drawn from $\mathbf{X}\sim
Mult(\widehat{v}_{t-1,i,j})$, then $\mathbf{X}_{1},\ldots,\mathbf{X}_{N}$ can
be used to update the parameter vector $\widehat{v}_{t,i,j}$ using the
following formula:

$\widehat{v}_{t,i,j}=\frac{1}{N^{e}}\sum_{k\in\mathcal{I}}{\mathrm{I}_{\\{X_{k,i}=j\\}}}$
(8)

Equation 8 simply describes the fact that the updated probability
$\widehat{v}_{t,i,j}$ is the number of elite samples for which the i-th
component is equal to j, normalized by the number of samples [11].

###  III-B Machine Learning for Multivariate Time Series Data

Most CPSs produce telemetry logs over the course of their operation. From
those logs we extract execution traces which can be represented as
multivariate time series (MTS), time series data consisting of both discrete
and continuous variables. There are multiple models which are well-suited to
classifying MTS.

RDF [12] have become one of the most popular ML algorithms due to the fact
that they perform well over a wide range of applications, are easy to tune,
and are fast to compute. They have been widely applied to tabular data, but
are also well-suited to time series data [13]. Other authors have suggested
modifications to the traditional random decision forest (RDF) algorithm for
constructing time-series forest classifiers which split the data into random
intervals, extract summary features, train a decision tree on the extracted
features, and repeat those steps until the required number of trees are built.
As with the traditional structure, time series are classified according to
majority vote [12].

In addition to RDFs, SVMs [12] have also been applied to time series data
classification and regression problems. An SVM is a classifier which
constructs a separating hyperplane to distinguish between known groupings by
maximizing the margin of the training data through the use of a kernel
function. In tabular data, that kernel function is often based on
dissimilarity measures such as Euclidean distance (e.g., the radial basis
function kernel). Such kernels are typically not well suited to time-series
data, and so dynamic time warping (DTW) is more often used to obtain the
distance between two time series due to the alignment problems inherent in
Euclidean distance measurements. The Gaussian DTW kernel, Gaussian elastic
metric kernel, and global alignment kernel are examples of kernels well-suited
to operate on time series [12].

####  III-B1 Deep Learning Approaches

RNN [13] were first proposed in the 1980s, but have become more popular in
recent years due to increased computational power. They are a form of deep
neural network (DNN) where neurons maintain information about previous inputs,
allowing them to extract temporal patterns from data. RNN models can suffer
from vanishing gradients, a phenomenon that results from the gradient value
sometimes becoming so small that it does not contribute to the learning
process, resulting in the model excluding long-term correlations from the
beginning of the temporal sequence. LSTM networks, a type of recurrent neural
network (RNN), are capable of learning long-term correlations through the
addition of gates and cells which help prevent important information from
being lost during the computation of gradient values in the backpropagation
process. A well-known drawback of DNNs and RNNs is their long training time
compared to that of SVMs and especially that of RDFs.

##  IV Method: Data Generation for Machine-Learned Correctness Property
Training and Testing using HybridPair Cross-Entropy Search

To demonstrate the efficacy of this approach, we present an experimental
method that: (1) automatically searches for correct and incorrect behavior,
(2) automatically generates a large dataset of execution traces from those
behaviors and (3) trains a RDF to learn a model for the behavior of interest.
We call this approach HybridPair CE search: Hybrid because it optimizes a
probability distribution which is a hybrid of multiple underlying
distributions, and Pair because it searches for a pair of hybrid-paths, one of
which exhibits correct behavior, the other of which does not. We describe our
approach to generating data using the CE method (Section IV-A) and for
training and testing the resulting MLCP (Section IV-B).

###  IV-A Data Generation

We simulate the behavior of an ego vehicle (the AV) in the presence of one or
more adversary vehicles with the goal of identifying both correct behavior
(i.e., behavior that satisfies some requirement) and incorrect behavior (i.e.,
behavior that violates some accepted understanding of correct behavior) for
the training of MLCP. Generating such events through random sampling
techniques such as Monte Carlo methods is highly ineffective because assuming
a relatively mature AV, incorrect behavior such as collisions are rare events.
Hence, we search for these events using a novel adaptation of the CE method.

Overall, there are six novel parts to our method of CE-based data generation
for MLCP.

  1. 1.

Search for explainable paths

  2. 2.

Excluding “Suicide Manuever” paths using vanilla/perturbed hybrid-path pairs

  3. 3.

CE of hybrid probability distributions

  4. 4.

Integration of data-set variance into the CE cost function

  5. 5.

Use of a weighted cost function

  6. 6.

Generation of rudimentary and variant hybrid-paths

Algorithm 3 describes our adaptations to the CE algorithm and Sections IV-A1
through IV-A6 explain the abovementioned items. In this algorithm, samples
($\mathbf{X}_{i}$) are scored according to a custom cost function
$S(\mathbf{X}_{i})$, which is the one part of the algorithm that is customized
to solve the underlying optimization problem. The cost function is customized
to capture the requirement that will ultimately be represented by the MLCP,
guiding the search for scenarios which are correct/incorrect with respect to
that requirement.

Algorithm 3 HybridPair Cross-Entropy Algorithm for Data Generation

1: Initialize hybrid distribution parameter vectors ($\mathbf{u}$) for each
adversary

2: Define $\hat{\mathbf{v}}_{0}=\mathbf{u}$. Set $t=1$.

3: Generate a hybrid sample $\mathbf{X_{1},\ldots,X_{N}}$ from the density
$f_{hybrid}(\cdot;\mathbf{v}_{t-1})$ , SEE *[1]

4: Calculate the performance $S(\mathbf{X}_{i})$ for all i, order them from
smallest to largest: $S_{(1)}\ldots\leqslant S_{(N)}$, SEE *[2]

5: Compute the sample $\rho\\!-\\!quantile$ as:
$\widehat{\gamma_{t}}=S_{(\lceil\rho\cdot N\rceil)}$ (i.e., the gamma element)
as well as the elite set which consists of the set of vectors satisfying
$S(\mathbf{X}_{i})\leqslant\widehat{\gamma_{t}}$

6: Update the parameter vector $\widehat{\mathbf{v}}_{t-1}$ to
$\widehat{\mathbf{v}}_{t}$ using the elite set and optional smoothing
parameter $\alpha$, SEE *[3]:
$\widehat{\mathbf{v}}_{t}=\alpha\widehat{\mathbf{v}}_{t}+(1-\alpha)\widehat{\mathbf{v}}_{t-1}$

7: If all gamma elements meet satisfying conditions then stop, otherwise, set
$t=t+1$ and reiterate from Step 3

*[1]: Each $\mathbf{X_{i}}$ is a sequence of positions and accelerations drawn from the hybrid distribution
*[2]: We calculate the elite set as $\mathbf{X_{S(1)},\ldots,X_{S(\rho\cdot N)}}$ instead of $\mathbf{X_{S((1-\rho)N)},\ldots,X_{S(N)}}$ (From Algorithm 2) because, in line with the approach taken by Falsification methods [14], lower scores are considered better than higher scores. As such, $S(\mathbf{X}_{i})<0$ indicates that the sample (e.g. path) satisfies rigid constraints such as “vehicle must not collide with ego”
*[3]: We set $\alpha=0.8$ in our implementation

####  IV-A1 Search for Explainable Paths

The resulting model learned by any ML algorithm is a direct result of the data
used to train it. Because our goal is to bootstrap the creation of MLCP
through data generation, we ensure the resulting model is explainable by
focusing on the explainability of the training data we generate. As such, we
use real-world data collected by the California Department of Motor Vehicles
(CA DMV). In order to enable the safe testing and deployment of AVs in
California, in 2014 the CA DMV began requiring companies testing AVs on public
roads to submit disengagement reports. These reports record instances where
the vehicle’s autonomous control system is disengaged, either by the vehicle
or by the human backup driver, and the CA DMV publishes on an annual basis the
disengagement reports (as well as crash reports) from all companies testing
AVs. Disengagement reports are of particular interest because:

  * •

AV technology being tested on public roads is relatively mature, and hence
unlikely to make lots of mistakes under normal driving conditions, so reported
disengagements usually indicate the occurrence of critical/unprecedented
scenarios.

  * •

Disengagements represent a failure of human-machine teaming, a critical
component in developing trust in the use of CPSs in areas such as automotive
vehicles. If the disengagement is initiated by the AV, it indicates an error
in the underlying CPS which reduces human trust in the system. If the
disengagement is driver-initiated, it usually represents a preemptive takeover
to prevent a potential perceived incorrect action by the CPS, also indicating
lack of trust.

Therefore, when we look at what type of interactions for which MLCP would
provide the most benefit to establishing trust in the dependability of AVs, we
use natural language descriptions from CA DMV reports as a starting point of a
CE search for paths of a MLCP dataset. For example, on September 24, 2019, the
AV company Zoox reported a disengagement by a backup driver due to “Prediction
discrepancy; incorrect yield estimation for a vehicle cutting into the lane of
traffic” [15]. Since our MLCP dataset generation method uses such natural
language descriptions as its starting point, the resulting dataset is
explainable. In the example used by our experimentation, data generated for
the behavior of an AV interacting with nearby vehicles performing lane change
maneuvers will induce an explainable dataset for one or more resulting
explainable MLCP. This is the example we take for our experimentation.

The essence of this paper is the application of novel extensions to the CE
search algorithm (Algorithm 3). One part of that extension resides in the CE
cost function (Algorithm 3, Step 4) which is written to detect paths that
conform to, and paths that do not conform to, the particular MLCP
disengagement instance.

In addition, we assume that the ego and a single adversary vehicle are not the
only vehicles on the road. We add an additional vehicle to the simulation
which we call the independent adversary (independent because its behavior is
controlled by a probability distribution that is independent of the
adversary’s) to both increase explainability and demonstrate the
generalizability of our approach to complex multi-agent systems with
potentially hundreds of adversaries or more.

####  IV-A2 Excluding “Suicide Manuever” Paths using vanilla/perturbed Hybrid-
Path Pairs

In the simulation-based search for correct and incorrect behavior, we attempt
to rule out the types of trivially unsafe behavior that is not likely to be
seen in real traffic scenarios or is not useful for generating CP. For
example, simply making a vehicle perform a high-speed “suicide” collision with
an AV travelling predictably on a highway is clearly a collision scenario, but
is not an event of interest for MLCP because there is little the AV can do
about it. Therefore, we take the philosophical approach that collisions (or
near-misses) of interest are the result of only slight variations from
otherwise acceptable behavior. The “normal” behavior that does not result in a
collision (or violation of another condition of interest) we call a vanilla
hybrid-path of the adversary. The behavior that is similar to the correct
path, but does result in a violation, we call the perturbed hybrid-path of the
adversary. A pair of such core paths of the adversary (vanilla/perturbed) can
be visualized on a two-dimensional decision boundary as depicted in Fig. 3. In
reality, the separating hyperplane is of a significantly higher dimension.
This boundary is an abstract border separating the path parameters of a
collision-avoiding vehicle and those of a slightly perturbed collision-
inducing path for the same vehicle.

Both vanilla and perturbed paths of the adversary are hybrid-paths, i.e., they
are sequences of location (a Categorically distributed value) and acceleration
(a Normally distributed value). The concept of a vanilla/perturbed path pair
(i.e., showing incorrect behavior that is subtly different from correct
behavior) helps to support both the realism and explainability of the data
ultimately used to train the MLCP. The vanilla/perturbed path pairs make up
the Pair component of the HybridPair term we use to refer to our CE search
technique.

We adapted the CE search algorithm to search for vanilla/perturbed pairs of
adversary paths by adding the following constraints to the CE cost function:

  * •

vanilla adversary path has no collision with ego

  * •

perturbed adversary path has collision with ego

  * •

Distance between vanilla and perturbed adversary paths (as measured by a
combination distance metric of location and acceleration) must be below some
threshold

####  IV-A3 Cross Entropy Search Using A Hybrid Probability Distribution

Typically, the CE method focuses on drawing samples from a single underlying
PDF for the simulation of rare events or solving a combinatorial optimization
problem [10]. In our case, we take the novel approach of optimizing a hybrid
probability distribution consisting of the following underlying distributions:

  * •

Multinomial (Categorical) Distribution: This distribution is used to represent
the adversary’s position

  * •

Gaussian (Normal) Distribution: This distribution is used to represent the
adversary’s speed/acceleration

By using a hybrid distribution, CE can search through a wide range of paths
that are variable in both position and speed, allowing the resulting paths to
encompass the full range of driving behavior in order to find rare paths that
may lead to collisions or near misses. The suggested approach is not the same
as searching for solutions that optimize one distribution and then searching,
with that set, for solutions that optimize the other distribution. Rather, CE
samples are drawn from a combination of both distributions, and the CE cost
function is a hybrid cost function, inducing a score used for creating a new
set of hybrid distributions.

####  IV-A4 Integrating Data-Set Variance Into the Cross Entropy Cost Function

In Algorithm 3, each batch of CE (i.e., a certain number of CE iterations that
occur prior to the $\hat{\gamma}_{t}<0$) results in a single pair of hybrid-
paths of the adversary - a perturbed (which will serve as a 1-labeled path for
the MLCP) and a vanilla path (which will serve as a 0-labeled path for the
MLCP). Because we have a goal of ensuring the MLCP is trained on a wide
variety of data to maximize generalizability, we integrate the variance
between the existing paths in the dataset and the newly generated
vanilla/perturbed pair of adversary paths into the cost function,
$S(\textbf{X}_{i})$. Given that collisions can happen in a variety of
different ways, the modified cost function incentivizes CE to discover
collisions that differ from previous collisions to ensure that a variety of
paths are represented in the training data.

Specifically, this process is comprised of three steps:

  1. 1.

Determine the current distribution of vanilla adversary paths in the dataset,
and the current distribution of perturbed adversary paths in the dataset. Each
of those distributions is the combination of two normal distributions.

Distribution of Vanilla paths of the adversary:

     * •

$\mathcal{N}_{\textsc{vanilla},location}(\mu_{\textsc{vanilla},location},\sigma^{2}_{\textsc{vanilla},location})$

     * •

$\mathcal{N}_{\textsc{vanilla},accel}(\mu_{\textsc{vanilla},accel},\sigma^{2}_{\textsc{vanilla},accel})$

Distribution of Perturbed paths:

     * •

$\mathcal{N}_{\textsc{perturbed},location}(\mu_{\textsc{perturbed},location},\sigma^{2}_{\textsc{perturbed},location})$

     * •

$\mathcal{N}_{\textsc{perturbed},accel}(\mu_{\textsc{perturbed},accel},\sigma^{2}_{\textsc{perturbed},accel})$

  2. 2.

Calculate metrics for the candidate vanilla and perturbed hybrid-paths of the
adversary. The metrics map the candidate hybrid-path’s location vector
($\mathbf{X}_{loc}\sim Mult(\widehat{v}_{t-1,i,j})$) to a scalar value
($\chi_{location}$) representing the hybrid-path’s entire location vector;
likewise, map the candidate hybrid-path’s acceleration vector
($\mathbf{X}_{accel}\sim\mathcal{N}(\widehat{\mu}_{t-1},\widehat{\sigma}^{2}_{t-1})$)
to a scalar value $\chi_{acceleration}$.

  3. 3.

Score paths as “better” (lower scores) for which ($\chi_{\textsc{VP},la}$) is
closer to $\mu_{\textsc{VP},la}\pm 2\cdot\sigma_{\textsc{VP},la}$, for all
pairs $\textsc{VP}\in\textsc{VANILLA},\textsc{PERTURBED}$, $la\in
location,acceleration$. In other words, ensure the newly discovered hybrid-
paths are close to two standard deviations away from the current mean of all
previously discovered hybrid-paths.

Scoring paths whose combined location and acceleration metrics are closer to
$\mu\pm 2\cdot\sigma$ from all previous paths incentivizes the HybridPair CE
search to add paths to the dataset that vary from previous paths, increasing
the variance of the dataset.

####  IV-A5 Weighted Cost Function

The HybridPair CE algorithm searches for a vanilla/perturbed pair of adversary
paths using a cost function, $S(\textbf{X}_{i})$, that accounts for five
factors:

  1. 1.

Categorical cost ($\mathcal{C}$): prioritize shorter paths

  2. 2.

Gaussian cost ($\mathcal{G}$): ensure the normally distributed speed values
are positive

  3. 3.

Distance between vanilla and perturbed hybrid-paths of the adversary
($\mathcal{D}_{v/p}$): ensure that these paths are similar according to the
philosophy discussed in Section IV-A2

  4. 4.

Variance ($\mathcal{V}$): ensure that the next hybrid-path added to the
dataset maximizes the distance from previously discoverd hybrid-paths (as
discussed in Section IV-A4)

  5. 5.

Rigid Constraints ($\mathcal{R}$): a hybrid-path must obey certain rigid
constraints (e.g., requiring a perturbed (vanilla) path of the adversary to
collide (not collide) with the ego vehicle, requiring all paths to avoid
obstacles). Failure to conform to a rigid constraint results in a poor score.

The first four factors above can each be assigned different weights according
to the prioritization placed on each component of the score (Equation 9).

$S(\mathbf{X}_{i})=\alpha_{1}\cdot\mathcal{C}+\alpha_{2}\cdot\mathcal{G}+\alpha_{3}\cdot\mathcal{D}_{v/p}+\alpha_{4}\cdot\mathcal{V}+\mathcal{R}$
(9)

For example, placing a higher weight on the categorical cost ($\alpha_{1}$)
indicates a preference for shorter paths over and above the other factors.
Similarly, a lower weight ($\alpha_{3}$) for the vanilla/perturbed distance
(which is a smaller negative number the closer they are to each other) would
indicate a lower emphasis on the similarity between the vanilla (non-
collision) and perturbed (collision) hybrid-paths of the adversary. The final
factor (rigid constraints) is not weighted because it is either zero (all
rigid constraints satisfied) or it is an extremely high value that dwarfs all
the other factors, indicating that rigid constraints were violated.

Through experimentation, we utilize the following weights:

$\alpha_{1}=3,\alpha_{2}=2,\alpha_{3}=2,\alpha_{4}=1$

####  IV-A6 Rudimentary and Variant Hybrid-Paths

The HybridPair CE search can be seen as finding the boundary between 1-labeled
(perturbed) and 0-labeled (vanilla) ML data items (See Fig. 3). Although each
component of the pair has different labels, its constituent hybrid-paths are
very similar to each other (see Fig. 4), which is a direct result of the
algorithm’s purpose of generating explainable paths in the form of
vanilla/perturbed pairs of adversary paths.

A classifier however, typically needs to be trained using additional data
items, such as 0-labeled data items that are farther away from the decision
boundary (e.g., a vehicle traveling along the same sequence of locations as
the vanilla adversary path, yet whose sequence of accelerations are
sufficiently different). Hence, we generate two additional types of hybrid-
paths: rudimentary paths and variant paths.

Fig. 3 depicts a pair of vanilla/perturbed core paths, as well as three
additional types of adversary hybrid-paths called helper paths, which are used
for generating a robust MLCP training set. More specifically, the path types
are:

  * •

Core Adversary Hybrid-Paths

    * –

vanilla: Class 0. Correct behavior that would be incorrect with a slight
perturbation.

    * –

perturbed: Class 1. Incorrect behavior that would be correct without a slight
perturbation.

  * •

Helper Adversary Hybrid-Paths

    * –

variant vanilla: Class 0. Correct behavior farther from the decision boundary.

    * –

variant perturbed: Class 1. Incorrect behavior farther from the decision
boundary.

    * –

rudimentary: Class 0. Correct behavior that represents the normal, routine
behavior of a system.

Figure 3: A visual depiction of the execution traces used to train the model.
Note the proximity of the vanilla/perturbed hybrid-pairs to the decision
boundary, and the larger relative distance of the variant and rudimentary
traces.

Rudimentary paths are those generated from distributions that have not been
iteratively updated by CE. They represent the types of naturalistic non-
collision paths likely to be prevalent in randomly sampled real-world data and
they are like paths that would be generated from pure Monte Carlo simulation.
Variant paths are generated by the same pair of distributions that CE computed
for vanilla/perturbed hybrid-path pairs (discussed in Section IV-A2), but they
are sufficiently different than their vanilla/perturbed counterparts. One such
variant hybrid-path pair is shown in Fig. 3 to illustrate their larger
relative distance from the decision boundary.

###  IV-B Machine Learning

In order to test the ability to train ML models from the generated data, we
first pre-process the data by taking the following steps:

  1. 1.

For each vanilla/perturbed hybrid-pair of adversary paths, identify the time
at which the collision between the adversary and the ego occurs in the
perturbed path. This time is denoted as $t_{collision}$.

    1. (a)

Starting at $t_{collision}$, go back in time some number of seconds ($X$)
prior to the collision ($t_{collision-X}$).

    2. (b)

Then take a series of time-sequenced features at some sampling rate ($R$) for
some number of seconds ($Y$) before $t_{collision-X}$ (i.e.,
$t_{collision-(X+Y)}$).

    3. (c)

Features taken from the vanilla hybrid-path of the adversary are taken at
exactly the same intervals and frequency as from the perturbed hybrid-path of
the adversary.

  2. 2.

For each Rudimentary and Variant Vanilla hybrid-path of the adversary, take
features from the exact same interval and frequency as described above in Step
1.

  3. 3.

For each Variant Perturbed hybrid-path, determine $t_{collision}$ and then
then follow Steps 1a and 1b.

For example, if the collision occurred at $t=5s$, you may choose to set $X=1$,
$Y=2$, and $R=0.5$. This would mean that the features taken from the
vanilla/perturbed adversary paths would be a sequence of features starting at
$t=2s$ and ending at $t=4s$, sampled every $0.5s$. The variant vanilla and
rudimentary hybrid-paths would have features sampled at the same indices. The
variant perturbed hybrid-paths would have features sampled relative to their
$t_{collision}$. If 33 features are collected at every timestep, then there
would be 165 total features for each path; the row of 165 features taken from
the vanilla, variant vanilla, and rudimentary paths are labeled as a ’0’, and
the row of 165 features taken from the perturbed and variant perturbed hybrid-
paths are labeled as a ‘1.’ The features used to train each ML model include
the relative position, velocity, and acceleration of the ego and adversary
vehicles.

The ML classifier is trained and tested using this dataset. Consequently, it
is trained to answer the question (with the above parameters), “Given data
from 3 seconds before the potential collision up to 1 second before the
potential collision, can I predict whether or not there will actually be a
collision between the adversary and the ego?”.

##  V Experiment

###  V-A Implementation and Simulation

The technique and novel contributions described above are implemented in
approximately 10k lines of code which consists of the following components:

  1. 1.

A CE generator that implements the CE method and produces paths to be executed
by the simulator in addition to tracking the state of the underlying
distributions

  2. 2.

A scenario executor which takes the paths generated by CE and
executes/analyzes them in the simulator

  3. 3.

Data pre-processing algorithms

  4. 4.

ML model training and testing

For our simulator we utilize CARs Learning to Act (CARLA) [16] due to its
strong developer support and flexible API.

####  V-A1 Simulation Example

Each simulation involves three vehicles: the ego vehicle (i.e, the AV), the
adversary vehicle, and the independent adversary. The adversary’s path either
results in a collision with the ego, in which case it is a perturbed path, or
it does not, making it a vanilla path. The independent adversary causes the
perturbed path of the adversary to result in a collision by encroaching into
the adversary’s lane and forcing it into a collision with the ego. One such
set of paths can be seen in Figs. 4 and 5. This visualization clearly depicts
the similarity in position (the Multinomial part of the hybrid distribution
discussed in Section IV-A3) between the vanilla/perturbed adversary paths
prior to the collision. The perturbed path collides with the ego vehicle,
hence its path is truncated at the point of collision (the bounding boxes of
the ego and (perturbed) adversary vehicles at the point of collision are shown
in Fig. 4). The vanilla path of the adversary does not collide with the ego
vehicle and is truncated at the point that the adversary’s perturbed path
resulted in a collision. Note how close the vanilla/perturbed paths are, a
direct result of the CE search approach previously discussed.

Figure 4: A visual depiction of a vanilla/perturbed paths with the ego and
adversary trajectories. Note the similarity in position of the
vanilla/perturbed paths of the adversary prior to the collision. The position
of each vehicle is represented by grid coordinate, where each grid cell is
approximately the length of a vehicle and the width of one half of a traffic
lane. Figure 5: The same scenario represented in Fig. 4 rendered in the
simulator. The left column shows the vanilla adversary path, and the right
column shows a perturbed path, where the perturbed adversary path results in a
collision with the ego vehicle at $t=4s$.

###  V-B Research Questions

To validate this research, we aim to answer the following research questions.
Research Question 1: Can ML be used to assert about critical properties of
CPSs in their environment?
Research Question 1(a): Which ML models perform best on these datasets?
Research Question 2: Can MLCP serve as requirements for systems which must
give advance notice to humans (e.g., alert a human of an imminent collision)?
Research Question 2(a): How does the performance of the MLCP vary depending on
desired detection time (i.e., the difference in time between when the MLCP
flags and when the potential collision occurs)?
Research Question 3: What is the impact of adding rudimentary paths to the
training set?
Research Question 4: What is the impact of adding variant paths to the
training set?

##  VI Results

###  VI-A Results for Research Question 1

To answer this research question, we trained a classifier on the various paths
discussed in Section IV, all of which are labeled as 0 (no collision) or 1
(collision). The classifier learns a model which can distinguish between
adversary lane changes that do result in collisions, and adversary lane
changes that are collision-free. A natural language equivalent for this model
would be ”Alert when a vehicle in the right adjacent lane is executing a lane
change trajectory which will cause a collision with the AV.” The MLCP could be
used to detect the condition discussed in Section IV-A1 where AVs experienced
disengagements due to “Prediction discrepancy; incorrect yield estimation for
a vehicle cutting into the lane of traffic” [15]. We begin by training a RDF
on a dataset consisting of 770 vanilla adversary paths (including vanilla
paths contained in vanilla/perturbed path pairs of the adversary, rudimentary,
and variant vanilla) and 210 perturbed paths (including perturbed paths
contained in vanilla/perturbed paths pairs and variant perturbed paths).

Because the distance between the ego and the nearest adversary is used as a
feature for the ML model, we do not sample features all the way up until the
collision to avoid giving the classifier information indicating that a
collision has already occurred (i.e. distance = 0). Rather, we sample features
up to one second prior to the collision. Using the preprocessing steps
described in Section IV-B, we set $X=1$, $Y=2$, and $R=0.2$ which equates to
taking two seconds of features every fifth of a second, starting three seconds
prior and ending one second prior to the collision.

The dataset exhibits only a minor class imbalance; the imbalance is
significantly smaller than a real-world dataset where 1’s are even less
frequent, which is a significant advantage of the CE search. Due to small
imbalance, we chose not to perform any undersampling of the 0’s or
oversampling of the 1’s; rather, we evaluate each classifier based primarily
on its F1 score as well as its balanced accuracy
($\frac{1}{2}\cdot(sensitivity+specificity)$ in order to use metrics most
well-suited to imbalanced data. Table I demonstrates that such a condition can
be detected with very high accuracy, showing that MLCP can indeed be used to
assert about critical properties of autonomous CPSs.

TABLE I: Machine Learning Results Classifier | Recall | Precision |  F1 Score |  Training Time (seconds)
---|---|---|---|---
RDF | 0.99 | 0.95 | 0.97 | 0.25
SVM | 0.78 | 0.89 | 0.83 | 0.32
LSTM | 0.98 | 0.91 | 0.94 | 46.5

###  VI-B Results for Research Question 1(a)

To determine the most appropriate model to use on the dataset, we compared the
RDF results against an SVM (DTW kernel) as well as an long short-term memory
(LSTM) for the same dataset. Table I shows the results from the various
models, as well as their time to train. We see that the RDF is the most
performant model, demonstrating high F1 score as well as the least time to
train. While the RDF and SVM were trained on a laptop (Intel® Core i9-9980HK
CPU @ 2.40GHz with 64GB of memory), the LSTM required a High Performance
Computing cluster with a NVIDIA V100 GPU due to memory requirements.

###  VI-C Results for Research Question 2

In order to provide advance notice to a human (e.g., some sort of visual,
auditory, or haptic feedback that human engagement is required), a MLCP must
first be able to detect that a condition will take place some amount of time
before the condition actually occurs. The exact amount of time required
depends significantly on the driver, the vehicle, and the operating conditions
at the time of takeover; those types of considerations are outside the scope
of this work. We demonstrate through the preprocessing steps previously
described and the results listed in Table I (i.e., one second of advance
notice) that indeed, MLCP can provide advance notice of future potentially
hazardous conditions. In Section VI-D we investigate the accuracy of that
prediction as the advance notice time varies. The ability to predict incidents
in advance, and quantify the uncertainty of those predictions, has been
discussed in previously published work [17].

###  VI-D Results for Research Question 2(a)

Fig. 6 displays the performance (F1 score) of various classifier models as $X$
in $t_{collision-X}$ is varied from one second to five seconds (see Section
IV-B for an explanation of pre-processing steps and the calculation of
$t_{collision-X}$). As expected, the F1 score decreases (on average) with an
increase in advance notice time, but the machine learning models (specifically
the RDF and LSTM) still demonstrate significant predictive power even as far
away as five seconds prior to the potential collision.

Figure 6: The F1 score of the classifiers tested plotted against the time
prior to the collision at which features were collected.

###  VI-E Results for Research Question 3

In Section IV-A6 we discuss the motivation for adding rudimentary paths to the
dataset; namely, the desire to add realistic non-collision paths which would
represent lane changes under naturalistic driving conditions. In order to
evaluate the efficacy of adding the rudimentary paths, we train a classifier
using only the vanilla/perturbed hybrid-paths of the adversary and then test
the classifier on the rudimentary hybrid-paths. We expect some rudimentary
paths (all of which are 0-labeled) to be misclassified due to their absence
from the training set. We find that only one rudimentary path was
misclassified out of a total of 520 rudimentary paths in the testing set using
a RDF. This indicates that perhaps rudimentary hybrid-paths don’t
significantly improve the performance and generalizability of the resulting
models.

###  VI-F Results for Research Question 4

In Section IV-A6, we discuss the motivation for adding vanilla/perturbed
hybrid-path pairs of an adversary which are farther from the decision
boundary. We call these variant hybrid-path pairs, and one such pair is
highlighted in Fig. 3. This allows the classifier to learn a broader notion of
vanilla and perturbed adversary paths. In order to evaluate the efficacy of
adding the variant paths, we train a classifier using only the
vanilla/perturbed adversary paths and then test the classifier on the variant
paths. We expect some of the vanilla variant and perturbed variant paths to be
misclassified due to their distance from the existing paths present in the
training set. In a test set containing all variant paths, we find that the
classifier still achieves an F1 score of 0.97 using the RDF which was
surprising. The false negative rate did increase in this experiment from 0.01
to 0.05, indicating that adding the variant paths may better help the
classifier identify collision paths that may be incorrectly classified as non-
collision paths otherwise - this reduction in false negatives is a significant
benefit for safety-focused CP. The results are shown in Table II.

TABLE II: Results for Testing on Variant Paths Only Classifier | Recall | Precision | F1 Score
---|---|---|---
RDF | 0.95 | 0.99 | 0.97

##  VII Discussion of Results

Generally, this technique demonstrates that MLCP can be utilized to assert
about behaviors of CPSs in complex multi-agent systems such as self-driving
vehicles, and these CP can additionally be used to provide advance notice of
critical events in order to mitigate hazards associated with failures of CPSs.

The question becomes, “what then?” Now that we have these MLCP, what do we do
with them? There are two types of runtime monitoring (RM) which could be
conducted to monitor these MLCP: offline and online.

###  VII-A Offline Runtime Monitoring

Offline RM is conducted retroactively, usually on log files recorded from the
SUT. One of the most significant challenges to the widespread deployment of
AVs is establishing liability for crashes and setting insurance rates. For
human drivers, this is typically done by looking at a driver’s pattern of
behavior to determine whether there is a high risk (and therefore should
demand higher insurance rates), or whether it represents a lower risk of
collisions. When a collision does occur, the insurance company uses the data
available to establish financial liability. CP could play a key role in
establishing risk metrics for AVs and assigning liability for collisions. For
example, suppose an insurer wants to determine the risk-taking level of an AV;
the insurer could train a MLCP on naturalistic driving data that contains both
normal and risky human driving behavior, and then use log files from AVs to
determine how often the AVs exhibits risky driving behavior to better assess
appropriate insurance rates.

Similarly, suppose an AV swerves suddenly on a highway to avoid a vehicle
encroaching in its lane, and strikes a guardrail. The insurer could run the
MLCP discussed in Section VI-A above to show that one second before the AV
swerved, a collision was imminent and the vehicle encroaching in the AV’s lane
was at fault and should bear the financial liability, even though it suffered
no damage itself. We do not attempt to weigh in on the discussion of who
exactly is liable for a fully autonomous system (e.g., the manufacturer, the
owner), but many such MLCP could be run offline for retrospective analysis to
provide key risk metrics and behavior analysis to insurers, policymakers,
vehicle manufacturers, regulators, and other stakeholders.

###  VII-B Online Runtime Monitoring

Offline RM is often the preferred approach for safety-critical systems because
the computational power required to analyze the CP in real time can interfere
with the operation of the underlying system. However, advances in edge
computing, networking, and storage have mitigated this issue in many types of
systems including AVs. Online RM can enable systems to respond to CP
violations in real time which in turn can aid in advancing cooperative
autonomy, also known as human-machine teaming.

As autonomous systems continue to advance and proliferate, humans who interact
with such systems need to understand the tasks that can be delegated to them,
along with the risks of delegating such tasks. When humans place too much
trust in the dependability of an autonomous system to perform a task, the
human is not likely to maintain an adequate level of situational awareness in
order to be able to intervene and take control such as in an emergency. When
humans place too little trust in autonomous systems, the cognitive burden
(e.g., task overload) on humans is increased and the intended benefits of
autonomy are reduced. Therefore, understanding what tasks can be delegated to
an autonomous system, the risks of delegating such tasks, and how that risk
changes over time is critical to enabling humans to effectively trust
autonomous systems.

This paradigm is well-illustrated by the current state of the automotive
industry. The Society of Automotive Engineers (SAE) defines six levels of
driving automation ranging from Level 0 (no automation) up to Level 5 (full
automation) [18]. Nearly all new vehicles in 2023 can be categorized as Level
2, in which the vehicle can perform steering and acceleration, but the human
is solely responsible for monitoring the environment and must stay
consistently engaged in the vehicle’s control. However, while the transition
from Level 0 through 2 has proceeded relatively smoothly, and has even been
welcomed by users and policymakers alike, the potential transition from Level
2 to Level 3 has been widely contested and the subject of much debate. This is
primarily because in Level 2, the human monitors the driving environment and
is well-equipped to take over at any time. In Level 3, the autonomous system
monitors the driving environment, and the challenge of alerting a human
concerning the need to take over control, provide awareness of the current
state of the environment, and detect the need to do so far enough ahead of
time, is a significant challenge. Each of these factors: when to alert a human
driver, whether or not the driver is professionally trained as an AV backup
driver, what to alert them about, how many alerts to provide, conditions under
which they should be alerted, and time between alerts and takeover are all
factors that can (and should) be encoded in CP.

MLCP, defined in Section I-A and described in Section VI can be well-suited
for this purpose with additional human factors analysis. Suppose an AV
manufacturer who is deploying Level 3 vehicles wants to warn a backup driver
when a nearby vehicle is making an unsafe lane change. In that case, the AV
would need to first detect the fact that a nearby vehicle is making an unsafe
lane change, and then it would need to alert the backup driver through visual
or haptic feedback in enough time for the driver to safely gain situational
awareness and take control to avoid a potential collision. Fig. 6 demonstrates
that a classifier still performs well when attempting to predict whether or
not there will be a collision even up to five seconds away from the potential
collision, demonstrating that MLCP could be suitable for triggering real time
modifications to the behavior of such CPSs, including warning humans if
present.

##  VIII Future Work

In the experiments discussed in Section V, we exclude uncertainty related to
sensor readings as a confounding factor. Therefore, the features which
represent the kinematics of the adversary vehicles are collected directly from
the simulation, and are not the result of sensor readings taken by the ego
vehicle. Such an approach is well suited for much-discussed trend of
“connected highways” and machine-to-machine/vehicle-to-vehicle communication
[19]. It also makes way for future work where the HybridPair search is
conducted using state-of-the-art sensors.

Additionally, the detection window is defined as a certain time prior to the
potential collision, but in real-world operation, it is unclear when a
potential collision might occur, making it unclear when the detection window
begins for evaluating the MLCP. Therefore, it would be necessary to define
preconditions for the MLCP to begin its prediction window, which could be
triggered by the proximity of a nearby vehicle to the ego.

Various times between a CP flagging and a potential collision are discussed.
There is significant room for research into the time required between alerting
a human of the need to take control and actually transferring control from an
autonomous system to a human. In addition, the MLCP could be trained to vary
their detection window depending on the situational awareness of the human
backup driving as measured by an engagement metric such as eye tracking.

Finally, the results for Research Question 3 (Section VI-E) could indicate
that despite our efforts in create a high-variance training set, the training
set still needs additional factors to provide sufficient variance. Such
factors could be related to the addition of weather, varying road friction
coefficients, lighting conditions, junction types, non-vehicle actors, etc.

##  IX Conclusion

While once only developed by deep-pocket corporations and government agencies
like the National Aeronautics and Space Administration (NASA), software-based
CPSs are now ubiquitous. Autonomous CPSs are being deployed at a rapid pace;
the automotive industry estimates that over 740,000 autonomous-ready vehicles
will be on global roads by the end of 2023, and in early 2023. Providing
continuous assurance of autonomous systems is of great interest to the
military as well. In early 2023, the U.S. Department of Defense (DoD) released
an updated strategy for deploying lethal weapons systems with autonomous
capabilities with a requirement that such systems undergo rigorous hardware
and software V&V [20]. Explainable MLCP provide a way to make it practical to
apply formal methods on real-world CPSs and intelligent transportation
systems, providing continuous assurance of dependable behaviors throughout the
entire system lifecycle.

## Disclaimer

The views and conclusions contained herein are those of the authors and should
not be interpreted as necessarily representing the official policies or
endorsements, either expressed or implied, of the U.S. Government. The U.S.
Government is authorized to reproduce and distribute reprints for Government
purposes notwithstanding any copyright annotations thereon.

## References

  * [1] D. Drusinsky, M. Litton, and J. B. Michael, “Lightweight verification and validation of cyberphysical systems using machine-learned correctness properties,” _Computer_ , vol. 55, no. 2, Feb. 2022. [Online]. Available: https://doi.org/10.1109/MC.2022.3142829
  * [2] D. Drusinsky, J. B. Michael, and M. Litton, “Machine-learned specifications for the verification and validation of autonomous cyberphysical systems,” in _2022 IEEE International Symposium on Software Reliability Engineering Workshops (ISSREW)_ , 2022, pp. 333–341. [Online]. Available: https://doi.org/10.1109/ISSREW55968.2022.00089
  * [3] F. Cameron, G. Fainekos, D. M. Maahs, and S. Sankaranarayanan, “Towards a verified artificial pancreas: challenges and solutions for runtime verification,” in _Runtime Verification_ , 2015, pp. 3–17.
  * [4] 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 Trans. Intell. Transp. Syst._ , vol. 18, no. 3, pp. 595–607, Mar. 2017.
  * [5] M. O’Kelly, A. Sinha, H. Namkoong, J. Duchi, and R. Tedrake, “Scalable end-to-end autonomous vehicle testing via rare-event simulation,” in _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , 2018, p. 9849–9860.
  * [6] W. Ding, B. Chen, M. Xu, and D. Zhao, “Learning to collide: An adaptive safety-critical scenarios generating method,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2020, p. 2243–2250. [Online]. Available: https://doi.org/10.1109/IROS45743.2020.9340696
  * [7] Y. Chen, C. M. Poskitt, and J. Sun, “Learning from mutants: Using code mutation to learn and monitor invariants of a cyber-physical system,” in _2018 IEEE Symposium on Security and Privacy (SP)_ , 2018, pp. 648–660.
  * [8] A. Afzal, C. Le Goues, and C. S. Timperley, “Mithra: Anomaly detection as an oracle for cyberphysical systems,” _IEEE Trans. Softw. Eng._ , vol. 48, no. 11, pp. 4535–4552, 2022.
  * [9] D. Xiao, M. Dianati, W. G. Geiger, and R. Woodman, “Review of graph-based hazardous event detection methods for autonomous driving systems,” _IEEE Trans. Intell. Transp. Syst._ , vol. 24, no. 5, pp. 4697–4715, 2023.
  * [10] R. Y. Rubinstein and D. P. Kroese, _The Cross Entropy Method: A Unified Approach To Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning_. Berlin, Heidelberg: Springer, 2004.
  * [11] Z. I. Botev, D. P. Kroese, R. Y. Rubinstein, and P. L’Ecuyer, “The cross-entropy method for optimization,” in _Handbook of Statistics_. Elsevier, 2013, vol. 31, pp. 35–59. [Online]. Available: https://www.sciencedirect.com/science/article/pii/
B9780444538598000035

  * [12] E. A. Maharaj, _Time series clustering and classification_. Boca Raton, FL, USA: CRC Press, 2019.
  * [13] F. Lazzeri, _Machine Learning for Time Series Forecasting with Python_. Newark, NJ, USA: John Wiley & Sons, Incorporated, 2020.
  * [14] Y. Annpureddy, C. Liu, G. Fainekos, and S. Sankaranarayanan, “S-taliro: A tool for temporal logic falsification for hybrid systems,” in _Tools and Algorithms for the Construction and Analysis of Systems_. Berlin, Heidelberg: Springer, 2011, pp. 254–257.
  * [15] California Department of Motor Vehicles, “Disengagement reports,” Dec. 2022. [Online]. Available: https://www.dmv.ca.gov/portal/vehicle-industry-services/autonomous-vehicles/disengagement-reports/
  * [16] “CARLA. Open-source simulator for autonomous driving research,” Accessed June 23, 2022. [Online]. Available: https://carla.org/
  * [17] D. Drusinsky, M. Litton, and J. B. Michael, “Machine-learned verification and advance notice oracles for autonomous systems,” _Computer_ , vol. 56, no. 7, Jul. 2023.
  * [18] _Taxonomy and Definitions for Terms Related to Driving Automation Systems for On-Road Motor Vehicles_ , SAE Standard J3016 Std., Jun. 2018. [Online]. Available: https://www.sae.org/standards/content/j3016_201806/
  * [19] Z. Hameed Mir and F. Filali, “Large-scale simulations and performance evaluation of connected cars - a v2v communication perspective,” _Simulation Modelling Practice and Theory_ , vol. 73, pp. 55–71, 2017.
  * [20] _Autonomy in Weapons Systems_ , DOD Instruction 3000.09, Department of Defense, Washington, DC, USA, 2023.

  *[U.S.]: United States
  *[ML]: machine learning
  *[CP]: correctness property
  *[CE]: Cross Entropy
  *[V&V]: verification and validation
  *[MLCP]: machine-learned correctness property
  *[AVs]: autonomous vehicle
  *[SUT]: system under test
  *[CPSs]: cyberphysical system
  *[MTL]: metric temporal logic
  *[AV]: autonomous vehicle
  *[CPS]: cyberphysical system
  *[KL]: Kullback-Leibler
  *[RV]: random variable
  *[PDF]: probability distribution function
  *[PDFs]: probability distribution function
  *[RVs]: random variable
  *[MTS]: multivariate time series
  *[RDF]: random decision forest
  *[RDFs]: random decision forest
  *[SVMs]: support vector machine
  *[SVM]: support vector machine
  *[DTW]: dynamic time warping
  *[DNN]: deep neural network
  *[RNN]: recurrent neural network
  *[DNNs]: deep neural network
  *[RNNs]: recurrent neural network
  *[CA DMV]: California Department of Motor Vehicles
  *[CARLA]: CARs Learning to Act
  *[LSTM]: long short-term memory
  *[RM]: runtime monitoring
  *[SAE]: Society of Automotive Engineers
  *[NASA]: National Aeronautics and Space Administration
  *[DoD]: Department of Defense