# DeepQTest: Testing Autonomous Driving Systems with Reinforcement Learning
and Real-world Weather Data

Chengjie Lu
Simula Research Laboratory and
University of Oslo
Oslo, Norway
<EMAIL_ADDRESS>
&Tao Yue
Simula Research Laboratory
Oslo, Norway
<EMAIL_ADDRESS>
&Man Zhang
Kristiania University College
Oslo, Norway
<EMAIL_ADDRESS>
&Shaukat Ali
Simula Research Laboratory and
Oslo Metropolitan University
Oslo, Norway
<EMAIL_ADDRESS>
Corresponding author

###### Abstract

Autonomous driving systems (ADSs) are capable of sensing the environment and
making driving decisions autonomously. These systems are safety-critical, and
testing them is one of the important approaches to ensure their safety.
However, due to the inherent complexity of ADSs and the high dimensionality of
their operating environment, the number of possible test scenarios for ADSs is
infinite. Besides, the operating environment of ADSs is dynamic, continuously
evolving, and full of uncertainties, which requires a testing approach
adaptive to the environment. In addition, existing ADS testing techniques have
limited effectiveness in ensuring the realism of test scenarios, especially
the realism of weather conditions and their changes over time. Recently,
reinforcement learning (RL) has demonstrated great potential in addressing
challenging problems, especially those requiring constant adaptations to
dynamic environments. To this end, we present DeepQTest, a novel ADS testing
approach that uses RL to learn environment configurations with a high chance
of revealing abnormal ADS behaviors. Specifically, DeepQTest employs Deep
Q-Learning and adopts three safety and comfort measures to construct the
reward functions. To ensure the realism of generated scenarios, DeepQTest
defines a set of realistic constraints and introduces real-world weather
conditions into the simulated environment. We employed three comparison
baselines, i.e., random, greedy, and a state-of-the-art RL-based approach
DeepCollision, for evaluating DeepQTest on an industrial-scale ADS. Evaluation
results show that DeepQTest demonstrated significantly better effectiveness in
terms of generating scenarios leading to collisions and ensuring the scenario
realism compared with the baselines. In addition, among the three reward
functions implemented in DeepQTest, Time-To-Collision is recommended as the
best design according to our study.

_Keywords_ Autonomous driving system testing $\cdot$ Test scenario generation
$\cdot$ Reinforcement learning $\cdot$ Software testing

##  1 Introduction

Autonomous driving systems (ADSs), as cyber-physical systems, sense their
operating environment and then autonomously make decisions based on sensed
information from the environment. Different from advanced driver-assistance
systems (ADASs), which are designed to assist/alert the driver in dealing with
dangerous situations, ADSs are designed with the ultimate goal of operating
vehicles without human intervention [79]. Testing ADSs has attracted a
significant level of attention from both the industry and academia, in recent
years. However, testing ADSs is still challenging because of the inherent
complexity of ADSs themselves and their operating environment, which is
dynamic, high-dimensional, and high-uncertain. In principle, there are an
infinite number of driving (and therefore testing) scenarios, and it is
critical to ensure that ADSs operate safely under any possible driving
scenarios.

Typically, there are two ways of testing ADSs, Offline testing [18] and online
testing [36]. Offline testing, also called model-level testing, does not test
ADSs as a whole but focuses on testing the decision-making deep neural
networks (DNNs) by considering DNNs as standalone components without involving
the operating environment of ADSs. Several Offline testing approaches [93, 86]
have been proposed to test ADSs by generating adversarial test inputs/scenes
(e.g., images) for DNNs. Such inputs are typically individual inputs that are
expected to find prediction errors of DNNs (e.g., steering angle errors). On
the contrary, online testing (or system-level testing) aims to identify
system-level failures by generating critical test scenarios, in which an ADS
under test is deployed in either a simulated or physical operating
environment, and the ADS is tested as a whole when it interacts with the
environment. Online testing approaches [8, 2, 1, 58] have demonstrated
promising performance in identifying system-level failures, but it remains
challenging to generate safety-critical test scenarios in a cost-effective way
due to the huge time overhead caused by the use of simulated/physical
environment.

Existing online testing approaches usually apply techniques such as search
algorithms and machine learning. For example, search-based testing (SBT)
techniques [8, 2] have been widely used to generate test scenarios by
formulating a testing problem (e.g., searching critical configurations of
driving scenarios) as an optimization problem, which can be addressed with
meta-heuristic optimization algorithms, such as Non-dominated Sorting Genetic
Algorithm II (NSGA-II) [23]. However, given the complexity and uncertainty of
the ADS operating environment, as well as the complexity of driving decision-
making, the application of these approaches are frequently restricted by
limited time, cost, and computational resource, or show limited effectiveness
in testing a long-term decision-making task under a continuously-changing
environment [84]. Recently, reinforcement learning (RL) has shown great
potential in addressing various challenging problems, where an agent learns
optimal behavior strategies through constantly interacting with its
environment without prior knowledge of the environment and the need for
labeled training data [47]. Several RL-based testing approaches [58, 20] have
been proposed and exhibit good performance in dealing with continuous system
and environment status changes. However, such an approach has limited
effectiveness in ensuring the realism of test scenarios, especially the
realism of weather conditions and their changes over time. Furthermore, there
is a lack of empirical studies investigating the effectiveness of different
reward functions.

Motivated by the above challenges and the successful applications of RL in
solving complicated problems, in this paper, we propose DeepQTest, an online
ADS testing approach that considers the test scenario generation problem as an
environment configuration problem and formulates the sequential interaction
between the environment configuration agent and the operating environment as
an RL problem. DeepQTest configures the operating environment and tests ADSs
throughout driving tasks; in each discrete instant of driving in the
environment, the RL agent decides an action to take on how to configure the
environment based on its observation of the environment (state), and gets
feedback (reward) from the environment afterwards. DeepQTest adopts Deep
Q-Learning (DQN) [63], a classical RL algorithm, which has demonstrated
excellent performance in addressing various autonomous driving problems, such
as lane following [76] and motion planning [16]. To encode the environment
states and extract features from the high-dimensional operating environment,
DeepQTest adopts multi-modal sensor fusion [28] as its state encoding
strategy. To ensure the realism of scenarios, we define a set of realistic
constraints on configurable parameters (e.g., positions of objects and
environmental parameters). We also develop a real-world weather generator that
introduces real-world weather data in simulation. Considering the importance
of reward functions in RL [46], we carefully design three reward functions:
$TTC_{Reward}$, $DTO_{Reward}$ and $Jerk_{Reward}$, based on three metrics:
time to collision (TTC), distance to obstacles (DTO), and the changing rate of
acceleration (Jerk). Corresponding to the three reward functions, we design
three approaches: $DeepQTest_{TTC}$, $DeepQTest_{DTO}$, and
$DeepQTest_{Jerk}$.

We trained 12 DeepQTest models using four real-world weather conditions in San
Francisco, and the three selected reward functions. The trained models are
evaluated with an industrial-level ADS (i.e., Apollo [27]) and a commonly used
autonomous driving simulator (i.e., SVL [75]). We perform an extensive
empirical study with four driving roads and compare DeepQTest with three
baseline strategies: random, greedy, and the state-of-the-art approach
DeepCollision [58]. Evaluation results show that 1) DeepQTest outperformed
random and greedy strategies in terms of collision generation and time cost
for enabling the occurrence of collisions; 2) $DeepQTest_{TTC}$ achieved the
overall best performance among all the three reward functions; 3)
$DeepQTest_{TTC}$ outperformed DeepCollision in terms of generating more
realistic collision scenarios with less time, and it also achieved better
performance than DeepCollision in introducing diverse environment
configurations and generating diverse scenarios. Based on the results on the
four roads under the four weather conditions with 20 times repetition,
DeepQTest is able to trigger a realistic collision scenario within 10.57
seconds on average.

The rest of the paper is organized as follows. Section 2 introduces RL,
especially the DQN algorithm. Section 3 surveys the existing research on
testing ADSs. We present DeepQTest in Section 4 and the evaluation design in
Section 5. In Section 6, we report results and analyses of the empirical
study, followed by discussions in Section 7, and conclude the paper in Section
8.

##  2 Background

In the section, we provide the required background information about DQN and
multi-modal sensor fusion, which are the key techniques applied in DeepQTest.

###  2.1 Deep Q-Learning (DQN)

Reinforcement Learning (RL) is essentially about agents learning decision-
making strategies while interacting with environments, which might not be
known beforehand. More specifically, during a learning process, based on each
observed state of the environment, the agent decides an action to take, and
then the performance of the agent after taking the action is evaluated with a
reward. The ultimate goal is to maximize the cumulative reward of a long-term
decision-making process.

When using Markov Decision Process (MDP) to formulate an RL problem, MDP can
be represented as a 5-tuple <$\mathcal{S,A,R,P,\gamma}$>, representing a set
of states $\mathcal{S}$, a set of actions $\mathcal{A}$, a reward function
$\mathcal{R}(s_{t},a_{t})$, a probability distribution
$\mathcal{P}(s_{t+1}|s_{t},a_{t})$, and a discount factor
$\mathcal{\gamma}\in[0,1]$. A stochastic policy
$\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ maps the state space to a
probability distribution over the action space, and $\pi(a_{t}|s_{t})$
represents the probability of choosing action $a_{t}$ at state $s_{t}$. The
optimal policy $\pi^{\ast}$, which represents the goal for an RL agent, is
expected to achieve the highest expected cumulative reward:
$R_{t}=\sum_{t>0}\gamma^{t-1}r_{t}$, where future rewards are discounted by
discount factor $\gamma$. Discount factor $\gamma$ controls how an agent
regards future rewards; a lower value of $\gamma$ encourages the agent to
focus more on short-term rewards, whereas a higher $\gamma$ value encourages
the agent to be more concentrated on a long-term perspective and maximize
long-term rewards. The learning process of an RL agent is that it first
observes a state $s_{t}\in\mathcal{S}$, then based on the observation (i.e.,
$s_{t}$), the agent selects and executes an action $a_{t}\in\mathcal{A}$.
After the execution of $a_{t}$, an immediate reward
$r_{t}\sim\mathcal{R}(s_{t},a_{t})$ is fed back to the agent, along with a
newly observed state $s_{t+1}\sim\mathcal{P}(s_{t+1}|s_{t},a_{t})$.

Many types of RL solutions have been proposed and demonstrate good performance
in solving practical problems. One classical method is value-based RL, which
uses an action-value function to estimate the performance of an action taken
at a given state. Q-learning [91] is a typical value-based method, which
employs Q-value as the measure of the expected reward in a state-action pair:
$(s_{t},a_{t})$. And the action-value function in Q-Learning is called the
Q-value function $Q^{\pi}(s,a):(\mathcal{S,A})\rightarrow\mathbb{R}$, which is
the discounted expected return of rewards given the state, action, and policy
represented by the equation:

$Q^{\pi}(s_{t},a_{t})=\mathbb{E}_{\pi}[R_{t}|s_{t},a_{t}].$ (1)

The Q-value of a given state-action pair $(s_{t},a_{t})$, i.e.,
$\textit{Q}^{\pi}(s_{t},a_{t})$, is an estimation of the expected future
reward obtained from pair $(s_{t},a_{t})$ with policy $\pi$. The optimal
action-value function $\textit{Q}^{\ast}(s_{t},a_{t})$ estimates the Q-value
of possible actions for a given state and selects the action with the highest
Q-value, based on the Bellman equation:

$Q^{\ast}(s_{t},a_{t})=\mathbb{E}_{\pi^{\ast}}[r_{t}+\gamma\max_{a_{t+1}}Q^{\ast}(s_{t+1},a_{t+1})].$
(2)

In Q-Learning, Q-values are stored in a Q-table, which represents the Q-value
function for all state-action pairs and updates based on the Bellman function.
Such a table is arbitrarily initialized and updated with data representing the
agent’s experience at each step using the equation:

$Q(s_{t},a_{t})\leftarrow
Q(s_{t},a_{t})+\alpha(r_{t}+\gamma\max_{a_{t+1}}Q(s_{t+1},a_{t+1})-Q(s_{t},a_{t})),$
(3)

where, $0<\alpha\leq 1$ is the learning rate. A larger learning rate leads to
a stronger influence of new data on an update.

One drawback of a Q-table is that when the action space is large and the
number of possible states of the environment is infinite, the memory required
to store the Q-table, as well as the computation resource required to search
from the Q-table, is huge. Therefore, it is very challenging to maintain a
separate Q-table for each $\mathcal{S\times A}$ [15]. Instead, a function is
often used to approximate Q-values. To overcome the above challenges, Deep
Q-Learning (DQN) [63] was proposed, which approximates and stores Q-values
with a neural network (i.e., Q-Network) parameterized by weights and biases,
together denoted as $\theta$: $Q(s,a;\theta)\approx Q^{\ast}(s,a)$. DQN
employs several mechanisms to ensure the stability of the training process: it
first uses a replay memory to store a certain number of state transitions
$<s_{t},a_{t},r_{t},s_{t+1}>$ and randomly samples data for training the
Q-Network. This step aims to reduce correlations among samples and thereby
increase sample efficiency through the reuse of data. Second, to ensure the
stability of the training process, a separate target network
$\hat{Q}(s,a;\theta^{-})$ parameterized with $\theta^{-}$ is used for
generating target Q-values in Q-Learning updates. $\hat{Q}$ is identical to
the main network $Q$, except that its parameters $\theta^{-}$ are cloned from
$\theta$ every C update. In this case, the Q-value function is updated as:

$\theta\leftarrow\theta+\alpha(y_{target}-Q(s_{t},a_{t};\theta))\nabla_{\theta}Q(s_{t},a_{t};\theta),$
(4)

where $y_{target}$ is the target value computed as:

$y_{target}=r_{t}+\gamma\max_{a_{t+1}}\hat{Q}(s_{t+1},a_{t+1};\theta^{-})$ (5)

Finally, at each training iteration, a batch of memory is sampled uniformly
from the replay memory for the Q-Network training. The training is based on
target Q-values from $\hat{Q}$. The loss function of Q-Network in DQN is
defined as:

$\mathcal{L}(\theta)=\mathbb{E}[(y_{target}-Q(s_{t},a_{t};\theta))^{2}].$ (6)

###  2.2 Multi-modal Sensor Fusion

Perception is an essential task of ADSs. To gain robust and reliable
environment comprehension, autonomous vehicles are usually equipped with
multiple sensors, such as cameras (visual cameras, thermal cameras), LiDARs,
and radars [28]. Multi-modal sensor fusion is then a crucial method for
perception tasks in autonomous driving. In multi-modal sensor fusion, DNNs are
often employed to serve as the environmental perception module by taking a
multi-modal representation of a driving environment (high dimensional) as the
input and generating a low dimensional feature representation. The input
consists of sensor data and vehicle state measurements. As for sensor data,
LiDAR point clouds and camera images are often considered. LiDAR point clouds
provide both depth and reflectance information of the driving environment and
are encoded into different representations such as a bird’s eye view [17] and
a front view [54]. Camera RGB images and depth images are also commonly used
sensor data to provide rich texture information (e.g., color) of the driving
environment. Vehicle state measurements are vehicle dynamics parameters such
as speed and acceleration.

By combining LiDAR cloud points, camera images, vehicle measurements, and
other sensor data, multi-modal representation can be encoded and inputted into
a perception module for feature extraction. To construct a perception module,
various neural networks will be adopted. For example, convolutional neural
networks (CNNs), which are neural networks with multiple layers, are often
used in image or object recognition and classification systems. A typical CNN
usually has three types of layers, i.e., convolutional, pooling, and fully
connected layers. Convolutional layers are the building block of a CNN, which
carry the main computation responsibility, such as identifying edges of images
for feature extraction; pooling layers then mitigate the dimensionality of
extracted features; fully connected layers, also named output layers,
recognize features of an image by using back-propagation algorithms. Due to
its exclusive features, such as local connectivity and shared weights, CNN can
achieve high accuracy and good performance in various tasks, such as image
classification and object detection [22].

Another commonly applied network is the Long Short-Term Memory (LSTM) [39],
which is capable of learning long-term dependencies and time series
prediction. The key of LSTM is the cell state, which serves as a memory unit
where the information can remain unchanged for a sufficient time. This helps
the unit to memorize the last calculated value. There are three types of gates
in an LSTM memory unit: forget gate, input gate, and output gate, where the
forget gate decides which information needs attention and which to ignore, and
the input gate updates the memory by controlling the flow of new information
into the memory, and the output gate determines the value of the next hidden
state, which contains information on previous inputs.

In multi-modal sensor fusion, DNNs represent features hierarchically and offer
different schemes to multi-modal sensor fusion, including early, middle, and
late fusion schemes. In the early fusion scheme, the multiple representations
from raw data are joined together, then the DNN learns the joint features of
multiple modalities at an early stage. Early fusion can fully exploit the
information of the raw data because data from different sources are directly
joined without losing the original information. In the middle fusion scheme,
feature representations from different sensing modalities are combined at
intermediate layers of a DNN, which enables it to learn cross-modalities with
different feature representations. The late fusion scheme uses separate
networks for feature extraction of each single sensing modality (e.g., LiDAR
point clouds, camera images), and the outputs are further concatenated and
processed by a network to get the final feature representation.

Evidence shows that multi-modal fusion outperforms single-sensor data
perception in autonomous driving [28]. Among different fusion schemes, middle
fusion has demonstrated promising performance in terms of leading to more
accurate object detection [78, 34] and improving the accuracy of geometry and
semantics of the resulting representation [71]. Thus, we opt for the middle
fusion scheme for multi-modal sensor fusion in our approach.

##  3 Related Work

As discussed in Section 1, existing ADS testing techniques typically can be
classified into offine ADS testing (Section 3.1) and online ADS testing
(Section 3.2).

###  3.1 Offline ADS Testing

Offline testing primarily focuses on only testing decision-making DNNs
embedded in ADSs without involving an operating environment. There are a large
number of offline testing approaches that have been proposed by using machine
learning (ML)-based testing [93, 86, 95], fuzz testing [92, 32] and mutation
testing [60, 40] techniques to generate adversarial inputs for DNNs in ADSs.
To measure test adequacy, various metrics have been proposed, such as neuron
coverage [68, 86] and surprise coverage [45].

Several approaches leverage real-world changes in driving conditions (e.g.,
heavy rain, heavy snow, or adverse lighting), and synthesize adversarial
driving conditions using ML techniques. Zhang et al. [93] proposed DeepRoad,
an Generative Adversarial Network (GAN)-based unsupervised learning framework,
for identifying inconsistent behaviors of DNN-based ADSs under various weather
conditions. DeepRoad synthesizes driving scenes with various weather
conditions and utilizes metamorphic testing techniques for checking the
consistency of such systems under synthetic driving scenes. Tian et al. [86]
proposed DeepTest, a systematic testing tool focusing on generating realistic
synthetic images by applying image transformations and mimicking different
real-world phenomena (e.g., weather conditions, object movements). To explore
possibilities for testing ADSs in the physical world, Guo et al. [95] proposed
a systematic physical-world adversarial inputs generation approach, named
DeepBillboard, which targets a specific driving scenario: drive-by billboards.
DeepBillboard generates adversarial perturbations that can be added to
roadside billboards in either a simulated/physical world and mislead CNN-based
steering models.

Several approaches focusing on deep learning (DL) testing also demonstrate the
potential for testing DNNs in ADSs. Guo et al. [32] proposed DLFuzz, a
differential fuzzing testing framework, to guide DL systems exposing incorrect
behaviors. Xie et al. [92] proposed DeepHunter, a coverage-guided fuzz testing
framework, for testing DNNs. DeepHunter detects potential defects of general-
purpose DNNs by generating new semantically-preserved test inputs. Ma et al.
[60] proposed a mutation testing framework, named DeepMutation, which directly
injects faults into DL models through mutation operators. Later on, Hu et al.
[40] extended DeepMutation and hence proposed DeepMutation++ to cover more
types of DNN models, such as feed-forward neural networks (FNNs) and stateful
recurrent neural networks (RNNs).

To measure the test adequacy for DNNs, various metrics [68, 40, 69, 45] for
evaluating the test quality have been proposed. For example, Pei et al. [68]
proposed DeepXplore, which introduces the neuron coverage for measuring the
number of rules in a DNN that have been exercised by a set of inputs, to
maximize both the neuron coverage and the number of potentially erroneous
behaviors without requiring manual labels. Kim et al. [45] proposed SADL,
which introduces surprise adequacy and surprise coverage to measure the test
adequacy for DNNs. Such metrics have been applied for guiding the testing of
DNNs of ADSs [68, 86] to achieve higher coverages of activated neurons.
However, due to an ADS being more complicated than a single DNN model, such
DNN testing methods exhibit limitations when being applied to test an ADS with
multiple DNN models. Moreover, it has been argued whether metrics such as
neuron coverage are meaningful for testing a real-world DNN in ADSs [37].

Offline testing techniques tend to be non-adaptive to contexts where a
prediction model needs to adapt to continuous system status changes, which is
exactly the case for ADSs’ operating environment. This is mainly because such
testing techniques test DNNs independent of their ADSs, and based on
individual inputs without considering that a a single DNN prediction error may
have an influence on future predictions and driving decisions [83], leading to
system failures. Therefore, although offline testing can detect single
prediction errors in DNNs, it shows limitations in identifying system-level
failures.

###  3.2 Online ADS Testing

Online testing approaches have been proposed to test ADSs in a
simulated/physical operating environment. Various techniques have been applied
in these approaches, including search algorithms and RL.

Search algorithms have been typically applied for generating test scenarios
for ADSs and ADASs [1, 2, 11, 8, 12]. These approaches mostly focus on the
automated test generation with optimization objectives such as minimizing
distances to obstacles or unsafe area [1], maximizing the speed of a vehicle
at the time of collision [1], violating safety requirements [2], and
minimizing time to collision [11, 8]. Some works apply multi-objective search
algorithms to select and/or generate safety-critical scenarios. Abdessalem et
al. [8] proposed NSGAII-SM, which combines multi-objective search algorithm
NSGA-II [23] with surrogate models [42] to test an ADAS with three objectives.
Abdessalem et al. [1] also proposed another approach named NSGAII-DT, which
considers two objectives (i.e, speed at the time of collision, distance to
obstacles) to generate critical scenarios for vision-based control systems by
combining NSGA-II with decision tree classification models. To detect failures
caused by feature interactions, FITEST [2] integrates a set of hybrid test
objectives designed based on distance functions measuring how far of violating
system safety requirements (e.g., no collision with pedestrians, stopping at a
stop sign). Such interactions involve features like automated emergency
braking (AEB), adaptive cruise control (ACC), and traffic sign recognition
(TSR). For instance, a feature interaction may arise when a braking command
issued by ABE is overridden by ACC’s command of maintaining the same speed as
that of the front vehicle. Calò et al. [12] adapted multi-objective search
algorithms (i.e., NSGA-II) to search for collisions and ADS configurations
that can avoid such collisions.

While SBT approaches show promising results in supporting online testing of
ADSs, they introduce practical challenges in terms of time and computational
overhead to evaluate test scenarios [51]. Moreover, another challenge of SBT
approaches is that their ability to deal with dynamic and continuously-
changing operating environments is limited, which is mainly because they do
not take advantage of the interaction between individuals (often encoding test
scenarios) with the environment when searching critical scenarios. However,
this interaction information has been proven to be efficient for decision-
making in RL, especially in an open and dynamic environment under uncertainty
[49, 77].

Several RL-based ADS online testing approaches have been proposed [14, 35,
58]. Chen et al. [14] developed an RL-based adaptive testing framework to
generate time-sequential adversarial environments specific to lane-changing
driving models. Haq et al. [35] proposed MORLOT, an online testing approach,
by combining RL and multi-objective search. MORLOT uses RL to adaptively
generate sequences of environmental changes that can cause requirement
violations and adopts multi-objective search to determine the changes that can
cover as many requirements as possible. Lu et al. [58] proposed DeepCollision,
an RL-based approach, which generates safety-critical testing scenarios by
configuring the operating environment of an ADS. Despite the promising results
of the current RL-based approach, there is no work that uses real-world
weather data when generating test scenarios. Besides, the literature mainly
uses a few parameters to encode RL states, which may have limitations when
representing a high dimensional state space of an autonomous driving
environment. In addition, designing a proper reward function is vital to an
RL-based testing approach, which requires further empirical studies.

To compare with the literature, DeepQTest, we propose in this paper, is
different from existing RL-based approaches because 1) DeepQTest does not try
to control the changes of weather conditions, while it introduces real-world
weather data to the simulation, which can improve the realism of weather
conditions and their changes over time in simulation and therefore improves
the realism of test scenarios; 2) DeepQTest encodes RL state with multi-modal
sensor data, which can better represent the environment and system states; and
3) DeepQTest integrates three different safety/comfort-related reward
functions and evaluates their effectiveness from various perspectives.

##  4 DeepQTest Methodology

In Section 4.1, we present the overview of DeepQTest, followed by a domain
model describing all the configurable environment parameters and their
relationships. We then describe how we introduce real-world weather data to
the simulator (Section 4.3) and mathematically formalize the environment
configuration problem as an MDP (Section 4.4). In Section 4.5, we present the
preprocessing of sensor data for encoding multimodal states and the Q-network
architecture in Section 4.6.

###  4.1 Overview

DeepQTest learns environment configurations with RL, with the ultimate goal of
identifying test scenarios for effectively testing autonomous vehicles, i.e.,
Autonomous Vehicles Under Test (AVUT). As shown in Figure 1, DeepQTest employs
a Simulator (e.g., LGSVL [75]) to simulate and configure a Testing
Environment, in which the (virtual) AVUT drives in its simulated Operating
Environment. DeepQTest also integrates with an Autonomous Driving System
(e.g., the Baidu Apollo [27]), which is deployed on the AVUT to enable its
autonomous driving.

Figure 1: Overview of DeepQTest

DeepQTest utilizes DQN to generate actions to configure the operating
environment of the AVUT, e.g., adding a pedestrian crossing the road. As
Figure 1 shows, during the configuration process, the DQN agent observes a
state $S_{t}$ describing the current states of the AVUT and its operating
environment. With the state, DeepQTest decides an action $A_{t}$ based on the
Q-Network and the behavior policy. With our developed Environment
Configuration REST API, such an action $A_{t}$ is realized as an HTTP request
for accessing the simulator to introduce environment configurations. The
realism of the newly configured environment is ensured by Realistic
Constraints (defined on environment configuration parameters) and Real-world
Weather Generator, which simulates real-world weather conditions.

After the AVUT drives in the newly configured environment for a fixed time
period, i.e., at $t+1$, both the AVUT and its operating environment enter a
new state observed as $S_{t+1}$, and action $A_{t}$ produces a set of outputs.
Based on these outputs, Reward Calculator calculates reward $R_{t}$ for
$A_{t}$ and $S_{t}$ at $t+1$. Then the DQN agent stores them (as $<S_{t}$,
$A_{t}$, $R_{t}$, $S_{t+1}>$) into the replay memory buffer. Once the replay
memory is full, the Q-Network is updated as $Q(s,a;\theta)$, using the loss
function by a mini-batch randomly sampled from the updated replay memory.
Meanwhile, the target network parameters $\theta^{-}$ are updated with
Q-Network parameters $\theta$ after a fixed number of steps and remain
unchanged between two updates. In addition, with $S_{t+1}$, the (updated)
Q-Network with behavior policy decides the next action: $A_{t+1}$.

In DeepQTest, an episode is finished once the AVUT arrives at its destination,
the AVUT cannot move for a defined duration, or a collision happens. At each
configuration step, information about the AVUT (e.g., its driving and
collision status) and its operating environment (e.g., its status and driving
scenarios) are stored as Environment Configuration Logs for further analyses
and replaying.

###  4.2 Configurable Environment Parameters

As part of this work, we developed a collection of environment configuration
actions as REST API endpoints for manipulating the ADS operating environment
by configuring parameters in simulation. These actions are utilized by
DeepQTest for enabling testing under various operating environment
configurations. Figure 2 presents a domain model (in the UML class diagram
notations) capturing theConfigurable Parameters of the operating environment,
based on which, Constraints can be specified to ensure (to a certain extent)
the realism of configured operating environment.

Figure 2: Domain model of the configurable parameters of the ADS operating
environment

Configurable Parameters. In reality, the operating environment of ADSs
constantly changes. However, when testing ADSs in a simulated environment, in
practice, the number of parameters that can be manipulated is limited and
dependent on the capability of the simulator being used. These configurable
parameters and their valid configuration values form the action space. Based
on the types of objects being configured and properties of effect to create,
we classify these parameters into three categories: parameters for configuring
Objects (Static Objects, Dynamic Objects), Road and Weather and Time.

(1) Configurable Parameters for Objects. In the simulated environment, Object
can be manipulated by configuring its initial position (i.e., initialPosition
typed with datatype Position), retrieving its current position (i.e.,
position), and get a distance with other Object with caclulateDistanceWith.
initialPosition can be configured only when the Object is introduced into the
simulated environment. Such introductions of Objects can be performed during
testing setup or during testing by an automated testing approach (such as
DeepQTest). We further classified Object into Static Object and Dynamic
Object.

For Static Objects, configuration values of the current position (i.e.,
position) remain unchanged within the specified Simulation Time. We involve
Traffic Cone and Traffic Light as Static Objects in our ADS testing as shown
in Figure 2. To test ADS, we allow introducing Traffic Cone during testing
(e.g., a road accident or a traffic accident could happen when driving), while
Traffic Light can only be introduced by setup. During testing, configurable
parameters of Traffic Light include its color (i.e., color typed with
enumeration Traffic Light Color) and duration when the corresponding color is
active (activeDuration typed with Real).

In a simulated environment, Dynamic Objects include AVUT, pedestrians and NPC
(Non-Player Character) vehicles, and values of their properties (e.g.,
position) change over time as shown by classes Dynamic Object (with properties
position inherited from Object, rotation and speed). AVUT can be configured
only in a test setup for a certain objective of testing ADSs, then denoted as
grey background. Pedestrians and NPC vehicles can be generated during testing.
In addition to the three properties inherited from Dynamic Object, a
pedestrian has one additional property characterizing itself, i.e., its
behavior (typed with enumeration Pedestrian Behavior). An NPC vehicle has
three additional properties: its behavior (typed with enumeration NPC
Behavior), color (typed with NPC Color), and type (typed with enumeration NPC
Type).

Since pedestrians and NPC vehicles can have a lot of behaviors in real driving
environments, the literature mainly focuses on safety-critical behaviors, such
as those related to inevitable collisions or traffic rule violations [12, 55].
Such behaviors mainly include overtaking, lane maintenance, lane switching,
road crossing, etc. We, consequently, classify behaviors of pedestrians and
NPC vehicles and specify them as two enumerations shown in Figure 2:
Pedestrian Behavior and NPC Behavior.

Realism. To ensure the realism of generations of Objects, we defined
constraints specified with Object Constraint Language [66] based on the
configurable parameters. When introducing a new Object into the simulated
environment, the Object should keep a safe distance from the AVUT and other
objects, restricting where the Object can be generated with initalPosition.
Any violation of the safe distance constraint might result in unrealistic
scenarios, e.g., colliding with a traffic cone that is just introduced in
front of the AVUT, heavy traffic congestion due to generated NPC Vehicles
which are close to each other. According to Ro et al. [73], a vehicle should
keep a safety distance of at least 5 meters from its surrounding objects,
however, the volume of Object and potential uncertainty in the simulator need
to be considered. Then, based on a pilot study, we define the safety distance
as 8 meters for Traffic Cone, Pedestrian, and NPC Vehicle with its type of
Sedan, SUV, Jeep, and Hatchback, and 10 metrics for NPC Vehicle with its type
of SchoolBus and BoxTruck. The OCL constraint is defined as:

⬇

context Object

inv: Object.allInstances $\rightarrow{}$ excluding(self) $\rightarrow{}$
forAll{o| ((self.oclIsKindOf(TrafficCone) or self.oclIsKindOf(Pedestrian) or
(self.oclIsKindOf(NPCVehicle) and Set{NPCType::Sedan, NPCType::SUV,
NPCType::Jeep, NPCType::Hatchback} $\rightarrow{}$
includes(self.asTypeOf(NPCVehicle).type)) implies
self.calculateDistanceWith(o) >= 8) or ((self.oclIsKindOf(NPCVehicle) and
Set{NPCType::SchoolBus, NPCType::BoxTruck} $\rightarrow{}$
includes(self.asTypeOf(NPCVehicle).type)) implies
self.calculateDistanceWith(o) >= 10)}

For Traffic Light, its color changes should also remain realistic. We restrict
that the color of traffic lights can be changed only by following the order,
i.e., red, green, yellow, then red again. Regarding the active duration for
each color, we follow the traffic signal timing manual of the United States
Department of Transportation [52], i.e., red 24 seconds, green 30 seconds, and
yellow 6 seconds. Then we define the constraint as:

⬇

context TrafficLight

inv: (self.color =TrafficLightColor::Red implies
(self.getPreviousValue().color =TrafficLightColor::Yellow and
self.activeDuration=24)) or (self.color =TrafficLightColor::Green implies
(self.getPreviousValue().color =TrafficLightColor::Red and
self.activeDuration=30)) or (self.color =TrafficLightColor::Yellow implies
(self.getPreviousValue().color =TrafficLightColor::Green and
self.activeDuration=6))

(2) Configurable Parameters for Road. Road can be configured in terms of
damage conditions, such conditions would impact ADS that need to be considered
in autonomous driving testing [61, 33]. Road damage can be classified into
four levels according to Ferlisi et al. [29]: negligible (damageLevel $\in$
[0%, 25%]), low (damageLevel $\in$ (25%, 50%]), moderate (damageLevel $\in$
(50%, 75%]), and severe (damageLevel $\in$ (75%, 100%]).

Realism. Regarding Road, its damageLevel cannot be configured (i.e.,
forbidConfiging is true) when AVUT is driving on it. Then, we define a
constraint on Road as:

⬇

context Road

inv: (not self.isObjectOn(AVUT)) xor self.forbidConfiguring

(3) Configurable Parameters for Weather and Time. As shown in Figure 2,
Weather can be configured with various Weather Condition and Time of Day.
Configuring the time of day has a great impact on illumination conditions such
as shadows, direct sunlight, or over/underexposed, which can lead to poor
performance of vision-based modules of an ADS [97], thereby important for
testing. Similarly, weather conditions are one of the important factors
causing accidents for both normal driving and autonomous driving [93, 9]. To
test ADSs, we consider four Weather Conditions, i.e., Cloudiness, Rain, Fog
and Wetness, and define different levels for each condition based on real
weather dataset as:

  * •

Configuring Cloudiness impacts how much the sky in the simulated environment
is covered by clouds. To test ADSs with various degree of Cloudiness, we
defined five levels, i.e., clear sky (cloudinessLevel $\in$ [0%, 11%]), few
clouds (cloudinessLevel $\in$ (11%, 25%]), scattered clouds (cloudinessLevel
$\in$ (25%, 51%]), broken clouds (cloudinessLevel $\in$ (51%, 84%]), overcast
clouds (cloudinessLevel $\in$ (84%, 100%]).

  * •

Configuring Rain impacts how heavy the rain should fall in the simulated
environment. Five levels are defined for Rain, i.e., light rain (rainLevel
$\in$ [0%, 20%]), moderate rain (rainLevel $\in$ (20%, 40%]), heavy intensity
rain(rainLevel $\in$ (40%, 60%]), very heavy rain(rainLevel $\in$ (60%, 80%]),
and extreme rain(rainLevel $\in$ (80%, 100%]).

  * •

Configuring Fog impacts how tick the fog is in the simulated environment. Five
levels are defined for Fog, i.e., light fog (fogLevel $\in$ [0%, 20%]),
moderate fog (fogLevel $\in$ (20%, 40%]), heavy fog (fogLevel $\in$ (40%,
60%]), very heavy fog (fogLevel $\in$ (60%, 80%]), and extreme heavy fog
(fogLevel $\in$ (80%, 100%]).

  * •

Configuring Wetness impacts how much the road in the simulated environment is
covered by water in our context. Five levels are defined for Wetness, i.e.,
light wetness (wetnessLevel $\in$ [0%, 20%]), moderate wetness (wetnessLevel
$\in$ (20%, 40%]), heavy wetness (wetnessLevel $\in$ (40%, 60%]), very heavy
wetness (wetnessLevel $\in$ (60%, 80%]), and extreme heavy wetness
(wetnessLevel $\in$ (80%, 100%]).

Realism. To ensure the realism of weather and time, in Section 4.3, we design
a mechanism that enables to introduce weather conditions based on real-world
historical weather dataset with the corresponding time of the day in the
simulated environment.

The literature has shown that existing RL techniques cannot handle a large
number of discrete actions, which may easily lead to scalability issues [26,
25]. Moreover, since the agent needs to evaluate all possible actions at each
step, the larger the action space, the larger the training cost (e.g., time)
would be. For this reason, we specify valid values of the configurable
parameters as enumeration literals, except for the time of day and the speed
of any dynamic object, which takes a real value. The overall aim is to reduce
the size of the action space.

Eventually, invocations of configurable environment parameters are realized
via DeepQTest APIs we implemented. For this purpose, we implemented in total
142 REST API endpoints [74], which forms the entire action space in our
current implementation of DeepQTest.

###  4.3 Real-world Weather Generation

As shown in Figure 2, there are various ways of changing weather conditions,
such as the time of day, whether it is raining at one moment, and what is the
current fog level. In the current design of DeepQTest, we decide not to
control the change of weather conditions since it is hard to simulate
realistic and ever-changing weather conditions. Note that it’s also hard to
predict changes in weather conditions over time, even in the real world [80].
Existing works on testing ADSs mainly focus on simulating a fixed weather
condition [8, 1] or applying Generative Adversarial Networks (GAN) to generate
static weather condition inputs (e.g., GAN-generated images) [93, 86]. These
methods, however, cannot generate weather conditions that realistically change
over time during a simulation.

Considering the above-mentioned limitations of existing methods, DeepQTest
directly builds a mapping of weather conditions of the real world to its
simulated world. To realize this, we opt for OpenWeather, an open-source
online weather database, which provides rich information on history, and
current, short-term, and long-term weather forecasts at any location of the
globe, and this information can be accessed via APIs.

To map real-world weather conditions to a simulated world, we consider weather
data sources from two domains: $\mathcal{W_{R}}$, characterized with real-
world weather parameters $\\{w_{r}^{0},w_{r}^{1},w_{r}^{2},...\\}$ (e.g.,
humidity, rain, wind), and $\mathcal{W_{S}}$, described with simulated-world
weather parameters $\\{w_{s}^{0},w_{s}^{1},w_{s}^{2},...\\}$ (e.g., rain,
wetness from a simulator), where $\mathcal{R}$ (or $r$) and $\mathcal{S}$ (or
$s$) denote the real-world and simulated world, respectively. Given a specific
city, since the weather condition in real-world changes over time in a day, we
then first map the date and time of day to the corresponding real-world
weather condition in the city,
$\mathcal{G_{R}}:(coor;d,t)_{R}\rightarrow\mathcal{W}^{(coor;d,t)_{R}}_{R}$,
where $coor$ denotes the coordinates of the given city, $d$ denotes a specific
day (in the format of 2021-08-07, for instance), and $t$ specifies the time in
a day (e.g., 20:00:00). Given a specific timestamp $(d,t)_{R}$ of a given city
(e.g., San Francisco), the weather condition in real-world can be determined
as $\mathcal{W}^{(coor;d,t)_{R}}_{R}$. To build a mapping of weather
conditions of the real world to its simulated world, we first map the
coordinates of the given city in the real world to the simulated world,
$\mathcal{M_{COOR}}:coor_{\mathcal{R}}\rightarrow coor_{\mathcal{S}}$. Then,
the timestamp $(d,t)_{R}$ in the real-world is mapped to the simulated world,
$\mathcal{M_{T}}:(d,t)_{R}\rightarrow(d,t)_{S}$. Hence, a weather condition of
a specific city in the real world with a timestamp $(d,t)_{R}$ can be mapped
as,
$\mathcal{M_{COOR,T}}:\mathcal{W}^{(coor;d,t)_{R}}_{R}\rightarrow\mathcal{W}^{(coor;d,t)_{S}}_{S}$.
Thus, with $\mathcal{W}^{(coor;d,t)_{S}}_{S}$, we can simulate the weather
condition of a specific timestamp of a specific city of the real world in a
simulator.

Below we describe how we build $\mathcal{G_{R}}$, $\mathcal{M_{COOR}}$,
$\mathcal{M_{T}}$ and $\mathcal{M_{COOR,T}}$ in detail.

$\mathcal{G_{R}}$ is built using the OpenWeather APIs. The coordinates $coor$
of a city in the real world are determined by the latitude and longitude of
the city: $(latitude,longitude)$. The date and time $(d,t)$ is transformed to
a Unix timestamp111The Unix timestamp is a way to track time as a running
total of seconds. This count starts at the Unix Epoch on January 1st, 1970 at
UTC. (e.g., 2021-08-07 20:00:00 is represented as 1628337600 in the Unix
timestamp format). Then, with the coordinates $coor$ and timestamp $(d,t)$, we
can get access to corresponding weather condition data of the real world via
the OpenWeather APIs.

$\mathcal{M_{COOR}}$ and $\mathcal{M_{T}}$ map the real-world coordinates and
timestamp to the simulated world. For $\mathcal{M_{COOR}}$, DeepQTest supports
importing High-Definition (HD) maps for testing ADSs in different cities, a HD
map contains details including information about coordinates, road shape, and
road marking, which are not normally presented on traditional maps [89]. Thus,
with the help of HD maps, we can easily map coordinates from the real world to
the simulated world. The timestamp mapping $\mathcal{M_{T}}$ is already
supported by the simulator (i.e., LGSVL) itself.

Weather conditions of the real world obtained via the OpenWeather APIs
$\mathcal{W_{R}}$ are characterized by a variety of parameters that can be
observed from the real world, including temperature, pressure, humidity,
wetness, wind, cloudiness, rain, snow, fog and etc. However, due to the
limitations of the simulator we currently use, we can only manipulate 4 types
of weather parameters (Figure 2) to simulate weather conditions in the
simulated world, which are cloudiness, rain, fog, and wetness. Thus,
$\mathcal{W_{S}}$ is characterized with the parameters below:

$\mathcal{W_{S}}=\\{w_{s}^{0},w_{s}^{1},w_{s}^{2},w_{s}^{3}\\}=\\{cloudiness_{s},rain_{s},fog_{s},wetness_{s}\\}$

Moreover, we select four real-world parameters corresponding to the parameters
in the simulator to define $\mathcal{W_{R}}$:

$\mathcal{W_{R}}=\\{w_{r}^{0},w_{r}^{1},w_{r}^{2},w_{r}^{3}\\}=\\{cloudiness_{r},rain_{r},fog_{r},wetness_{r}\\}$

Since weather parameters in the real world are described with real values, we
correspondingly define real values (shown in Figure 2) for mapping real-world
weather conditions to the simulated world. For example, the cloudiness level
in the real world varies from 0% to 100%. In contrast, in the simulator we
use, the cloudiness level ranges from 0 to 1, where, 1 is the maximum
intensity of cloudiness, which is equal to 100% in the real world.

We acknowledge that our current mapping strategy has limitations in terms of
not being able to cover a full list of parameters (e.g., temperature,
pressure, wind) due to the limitation of the simulator. However, these covered
parameters have been proven to be effective in testing ADSs [93, 9]. Moreover,
DeepQTest can be easily adapted, in future work, to cover more parameters for
mapping as long as the simulator being used allows.

###  4.4 Formulating Environment Configuration Learning as an MDP

####  4.4.1 State Encoding

In the context of autonomous driving, perception of the driving environment
and encoding it to extract features are the key to constructing safety ADSs.
In recent years, prior works adopt different approaches to encode the
operating environment of an ADS for constructing an object detector [70, 17]
or training an end-to-end autonomous driving model [15, 19]. For instance,
Codevilla et al. [19] proposed a multi-modal perception method for
constructing end-to-end autonomous driving models, and their experiment
results indicate that an end-to-end driving model can be improved with multi-
modal sensor data (Section 2), instead of just relying on a single modality.
To this end, in DeepQTest, we adopt multi-modal sensor fusion as the overall
strategy of our state encoding. Specifically, a state inputted to the RL model
is composed of the following three parts:

  * •

Camera RGB Image: a front view image containing information on the road
structure and obstacles ahead;

  * •

Lidar Bird’s Eye View: an eye view representation encoded with height,
intensity, and density, containing information of the surrounding environment
of the vehicle;

  * •

Vehicle’s State Measurement: measuring the driving state of the vehicle (e.g.,
speed, acceleration, jerk).

After a state is observed and inputted into the RL model, features will be
extracted, based on which the RL agent consequently determines which
environment configuration action to take. Details about how a state is
processed by the RL model will be presented in Section 4.6.

####  4.4.2 Action Space

The action space in DeepQTest is a set of actions with discrete integer values
representing the actions’ IDs. These actions are used to configure the driving
environment of an ADS, which forms test scenarios for testing the ADS. Each
action is associated with a simulation time denoted by T (in seconds) and a
time step denoted by t (in seconds). The simulation time T indicates the time
we let the simulation run after invoking an action. The simulation time is
divided into time steps with equal time duration t. Additionally, an action is
associated with several outputs, defined as Environment Configuration Output.

Outputs of Environment Configuration Actions. In our context, invoking an
environment configuration action produces the following three types of
outputs.

  * •

Time-To-Collision (TTC) measures the time left for a vehicle to collide with
obstacles. In our current design of DeepQTest, for calculating TTC, we adapted
the prediction-based method from the Self-Driving Cars Specialization online
course [82] provided by the University of Toronto. The pseudocode of the
calculation is presented in Algorithm 1.

  * •

Distance-To-Obstacles (DTO) measures the distance between AVUT and the
obstacles, which is closely related to driving safety [30].

  * •

JERK measures the change rate of the acceleration of AVUT, which is one of the
important indicators of the degree of comfort of passengers [41].

In DeepQTest, values of TTC, DTO and JERK are collected every time step t,
simultaneously, and after a simulation time T of an action being invoked,
three lists ($TTC_{buff}$, $DTO_{buff}$, $JERK_{buff}$) containing the
corresponding outputs are returned.

Algorithm 1 Prediction-Based Time-To-Collision Calculation

1:

2:Let D be a set of dynamic obstacles; T be time period an environment
configuration action will last; dt be time step between simulation steps

3:

4:A buffer of TTC between AVUT with all dynamic obstacles

5:

6:$t\leftarrow 0$

7:$TTC_{buff}\leftarrow[]$ $\triangleright$ initialize an empty buffer to
store TTC

8:while t <T do

9: t = t + dt;

10: $Pos_{avut},Velo_{avut}\leftarrow getPosition(avut)$ $\triangleright$ get
position and velocity of avut

11: for each $d\in|D|$ do

12: $Pos_{d},Velo_{d}\leftarrow getPosition(d)$ $\triangleright$ get position
and velocity of dynamic obstacle d

13: $Pos_{coll}\leftarrow
collisionPrediction(Pos_{avut},Velo_{avut},Pos_{d},Velo_{d})$

14:$\triangleright$ Predict the collision point between AVUT and d

15: $TTC_{avut,d}\leftarrow
ttcEstimation(Pos_{avut},Velo_{avut},Pos_{d},Velo_{d},Pos_{coll})$

16:$\triangleright$ Estimate time to collision between AVUT and d

17: Put $TTC_{avut,d}$ into $TTC_{buff}$

18: end for

19:end while

20:return $TTC_{buff}$

Since DeepQTest uses RL with a proper reward function to find test scenarios
in a cost-effective manner, we design the reward function based on the outputs
of environment configuration actions. Prior works on ADS testing have shown
that using Time-To-Collision, Distance-To-Obstacles as objectives can guide
the algorithms to generate safety-critical scenarios [8, 1], and in [6] it is
demonstrated that jerk is an important factor to passengers’ riding
experience. We however acknowledge that there might exist other types of
outputs, which can be investigated in the future.

####  4.4.3 Reward Function

The reward function is defined based on the environment configuration outputs
(Section 4.4.2). More specifically, to calculate reward, we define three
rewards corresponding to the three outputs, denoted as: Time-To-Collision
Reward ($TTC_{Reward}$), Distance-To-Obstacles Reward ($DTO_{Reward}$), and
JERK Reward ($JERK_{Reward}$), respectively.

Time-To-Collision Reward, $TTC_{Reward}$. A smaller TTC indicates a higher
collision risk and vice versa [90]. In the context of testing ADSs, we aim to
put the AVUT at risk, meaning that smaller TTC values lead to higher reward
values.

As shown in Algorithm 1, after an environment configuration action is
executed, a buffer of TTC (i.e., $TTC_{buff}$) will be returned as an output,
and the algorithm then takes the minimum TTC in $TTC_{buff}$ for calculating
$TTC_{Reward}$. To apply TTC as a metric indicating the risk to collisions, a
TTC threshold should be determined, denoted as $ttc_{thre}$, which is
configured as 7 seconds, in the current design of DeepQTest, based on the
guideline from [98]. The calculation of $TTC_{Reward}$ is shown in Equation 7.
If a TTC value is less than or equal to $ttc_{thre}$, the reward will be
positive; otherwise, a punishment being -1 will be returned.

$TTC_{Reward}=\left\\{\begin{aligned}
&-\ln{\dfrac{nor(TTC)}{nor(ttc_{thre})}},&0<TTC\leq ttc_{thre}\\\
&-1,&TTC>ttc_{thre}\end{aligned}\right.$ (7)

Distance-To-Obstacles Reward, $DTO_{Reward}$. Prior works have shown that
different distances to obstacles during driving will cause risks of varying
severity, and a smaller distance to obstacles will lead to a higher risk of
collision, especially when the safety distance is violated [73]. In DeepQTest,
we take the minimum $DTO$ value from the $DTO_{buff}$ to calculate
$DTO_{Reward}$. The equation for calculating $DTO_{Reward}$ is similar to the
calculation of $TTC_{Reward}$, shown in Equation 8, where, $dto_{thre}$ is the
safety distance indicating the minimum distance by which the AVUT avoids a
collision with the obstacles. $dto_{thre}$ is related to the kinematics
parameters (e.g., speed, acceleration) of the AVUT and obstacles, and in
DeepQTest, we take the default value from Berkeley algorithm [7] which is 10
meters.

$DTO_{Reward}=\left\\{\begin{aligned}
&-\ln{\dfrac{nor(DTO)}{nor(dto_{thre})}},&0<DTO\leq dto_{thre}\\\
&-1,&dto>dto_{thre}\end{aligned}\right.$ (8)

JERK Reward, $JERK_{Reward}$. Since the jerk of the AVUT has a strong
influence on the comfort of passengers; the higher the jerk, the less
comfortable the passengers [6]. When a list of jerks ($JERK_{buff}$) is
returned after an environment configuration action is executed, we then take
the maximum $JERK$ value in $JERK_{buff}$ for calculating $JERK_{Reward}$. We
also need a JREK threshold ($jerk_{thre}$) in the calculation, and according
to our preliminary study, we found that for normal driving, the jerk values
are lower than $5m/s^{3}$. Therefore, we set the threshold as $5m/s^{3}$ since
we want to maximize $JERK$.

$JERK_{Reward}=\left\\{\begin{aligned}
&e^{\dfrac{nor(JERK)}{nor(jerk_{thre})}}-1,&JERK\geq jerk_{thre}\\\ &-1,&0\leq
JERK<jerk_{thre}\end{aligned}\right.$ (9)

Considering that environment configuration outputs (TTC, DTO, and JERK) may be
not comparable, in the above calculations, we apply the normalization function
[31], $nor(F_{x})=(F_{x}-F_{min})/(F_{max}-F_{min})$, to ensure all values
fall into $[0,1]$, where, $F_{x}$ is an environment configuration output to be
normalized; max and min represent the maximum value and minimum value of the
environment configuration output, respectively.

###  4.5 Sensor Data Preprocessing

Some preprocessing steps for camera images and lidar point cloud data in
multimodal state encoding are necessary because working directly with raw data
can be computation and memory demanding [63]. In DeepQTest, a camera image is
an RGB image of $1920\times 1080$ pixel frames at each color channel, we crop
off the top rectangle area of the image so that the picture in front of the
vehicle is centered in the image, then resize the cropped image to $160\times
376$ pixel frames at each color channel while keeping its aspect ratio
constant.

A lidar sensor generates a point cloud P containing $N$ points:
$P=\\{p_{1},p_{2},...,p_{N}\\}$, $p_{i}=(x,y,z,r)^{T}$, i
$\in\\{1,2,...,N\\}$, where $(x,y,z)$ denotes a 3D position in space and $r$
denotes the reflectance of point $p_{i}$. To get a bird’s eye view
representation from the point cloud, we follow the steps from MV3D [17] to
encode a bird’s eye view representation with height, intensity, and density.
Hence, the point cloud is discretized into a 2D grid with a resolution of 0.1
meters. The height of each cell in the grid is calculated as the maximum
height of the points. The intensity is the reflectance value of the maximum
height point. The density is computed using the number of the points in the
cell ($n$) as $min(1.0,\dfrac{log(n+1)}{log(64)})$. To encode more detailed
height information, the point cloud is divided equally into $M$ slices.
Finally, the bird’s eye view is encoded as $(M+2)$-channel features. In
DeepQTest, we are using a lidar sensor with 128 laser beams, which can
generate 9391 points in one point cloud. Thus, in total the bird’s eye view is
a 15-channel feature with size $300\times 300$ at each channel.

###  4.6 Network Architecture and Training Algorithm

####  4.6.1 Network Architecture

Deep Q-Learning (Section 2.1) utilizes a neural network (Deep Q-Network) to
approximate and store Q-values and the design of the Q-Network plays a key
role in learning tasks. In the context of autonomous driving, a good network
architecture is conducive to the learning tasks, such as the success in image
classification (e.g., VGGNet [81], Alexnet [53]), object detection (e.g., MV3D
[17]) and pedestrian prediction [44]. Focusing on multimodality and sensor
data fusion, various network architectures have been proposed as well as
various fusion schemes. As discussed in Section 2.2, the middle fusion scheme
has demonstrated promising performance in various autonomous driving
perception tasks, which gives us the confidence to adopt the middle fusion
scheme to construct the Q-network in DeepQTest.

Assume that each state s = <i, b, m> comprises an image i, a lidar bird’s eye
view b, and a low-dimensional vector m referring to vehicle state
measurements. The deep neural network (DNN) in a DQN algorithm takes a state
as the input and produces an action with the maximum Q-value as its output. As
shown in Figure 3, the network includes an image-processing CNN module, taking
image i as the input to extract image features C(i); a lidar-processing CNN
module which takes lidar bird’s eye view b as the input to extract lidar
bird’s eye view features, C(b); and a module of fully-connected neural network
(FNN) which takes vehicle state measurements as the input to extract
measurement features, F(m). After a state is processed by these three modules,
the output features (i.e., C(i), C(b), F(m)) are concatenated into a joint
representation:

$j=J(i,b,m)=<C(i),C(b),F(m)>$ (10)

The final decision module, implemented as an LSTM [39], followed by two fully-
connected layers, takes the joint representation j as input and outputs an
action with the maximum Q-value.

Figure 3: Q-Network Architecture. The RGB image, bird’s eye view, and vehicle
status measurement are the inputs of Q-Network. The output is the environment
configuration action.

More specifically, the image-processing CNN module consists of 4 convolutional
layers and 2 fully-connected layers. The input i consists of a $160\times
376\times 3$ image. The first hidden layer convolves 32 filters of $5\times 5$
with stride 4. The second hidden layer convolves 64 filters of $3\times 3$
with stride 2. The third hidden layer convolves 128 filters of $3\times 3$
with stride 2, followed by the final convolutional layer that convolves 256
filters of $3\times 3$ with stride 2. This is followed by a hidden and fully-
connected layer with its neuron number (128 neurons) equal to the output of
the last convolutional layer of the module. The lidar-processing CNN module
has the same design as the image-processing CNN module, but with its input b
being a $300\times 300\times 15$ image. The FNN module with its input as
measurement m is designed as a four-layer fully-connected neural network with
the architecture of an input layer with 1 neuron, 200 hidden layers with 200
neurons for each, and one output layer with 64 neurons. The final decision
module consists of an LSTM with 704 neurons as the input, 64 hidden neurons,
and 2 recurrent layers, which is followed by a fully-connected hidden layer
with 64 neurons and another fully-connected layer for outputting an action
with the maximum Q-value. To ensure stability, prevent overfitting, and
accelerate the convergence of the network training process, we perform batch
normalization after each convolutional layer, then apply the Rectified Linear
Unit (ReLU) nonlinearity after each normalization. We also apply the ReLU
nonlinearity after each fully-connected layer and use 10% dropout after LSTM.

##  5 Experiment Design

###  5.1 Research Questions

To assess our approach, we carried out an empirical study to answer the
following three main research questions (RQs):

RQ1: Does DeepQTest achieve better performance compared to Random and Greedy
Strategies? RQ1 aims to do a sanity check that the problem we address is
complex and it is hard to be solved by naive Random and Greedy Strategies.

RQ2: Among the three reward functions, which one performs the best? RQ2 aims
to identify the best design(s) (Section 4.4.3), which can guide DeepQTest to
generate more effective environment configurations for testing AVUT.

RQ3: How does the DeepQTest perform compared to the start-of-the-art
technique? RQ3 aims to demonstrate the effectiveness of DeepQTest compared to
the start-of-the-art technique, i.e., DeepCollision.

Table 1 shows an overview of our experiment design. In the rest of this
section, we present comparison baselines (Section 5.2), experiment settings
(Section 5.3), evaluation metrics (Section 5.4), and statistical test (Section
5.5).

Table 1:  Description of tasks, employed approaches, road settings, weather
condition settings, metrics, and statistical test for each RQ

RQs | Tasks | Approaches | Roads | Weather | Metrics (Section 5.4) | Statistical Test
---|---|---|---|---|---|---
RQ1 |  | Compare DeepQTest with RS and GS
---
| DeepQTest
---
RS, GS
|  |  | Safety and Comfort Metrics
---
| Mann-Whitney U test
---
Vargha-Delaney A measure
RQ2 | Identify the best reward function of DeepQTest |  | $DeepQTest_{TTC}$
---
$DeepQTest_{DTO}$
$DeepQTest_{Jerk}$
| R1
---
R2
R3
R4
| Rainy Day
---
Rainy Night
Sunny Day
Rainy Day
| Safety and Comfort Metrics
---
Diversity Metrics
| Mann-Whitney U test
---
Vargha-Delaney A measure
Spearman’s rank correlation
coefficient
RQ3 |  | Compare DeepQTest with the state-of-the-art
---
in terms of the effectiveness of detecting unrealistic
collision scenarios, and the diversity of generated
scenarios.
| $DeepQTest_{TTC}$
---
DeepCollision
|  |  | Realism Metrics
---
Diversity Metrics
| Mann-Whitney U test
---
Vargha-Delaney A measure

###  5.2 Comparison Baselines

To evaluate DeepQTest, we selected three baseline techniques, i.e., a random
strategy (i.e., RS), a greedy strategy (i.e., GS), and DeepCollision [58]. RS
is commonly used as the baseline for a sanity check on whether an optimization
problem is complex enough. GS has been used as the comparison baseline in the
literature for several RL-based approaches, including RL-based decision-making
for autonomous lane changing [64] and RL-based navigation optimization [3].
DeepCollision is a recent study that is an RL-based ADS testing strategy
proposed by Lu [58] for testing AVUT with various environment configurations.
Detailed implementations and setup for each baseline are:

  1. 1.

RS (Algorithm 2): RS randomly selects an action to configure the environment
at each environment configuration step.

  2. 2.

GS (Algorithm 3): GS was implemented to select the best configuration at each
step. To determine the next action to be executed, GS executes all the actions
(Lines 7–14), then selects an action that achieves the best performance based
on a defined reward (Line 15). For GS, we implemented three rewards as
DeepQTest (i.e., TTC, DTO, and Jerk), and comparison was conducted by
employing the same reward (e.g., $DeepQTest_{TTC}$ vs. $GS_{TTC}$). To ensure
that the comparison among actions is fair, we implemented a rollback mechanism
(see Line 13) that facilitates, at each iteration, executing each action from
the same state of the testing environment. A sequence of the best actions is
returned at the end of the search.

  3. 3.

DeepCollision [58]: DeepCollision learns environment configurations with RL
guided by the collision probability to maximize collision occurrences. There
are four models trained in DeepCollision, and we selected the recommended one
[58], i.e., M6 model, in our experiment. In DeepCollision, a state of the
driving environment is encoded based on 8 environmental parameters, while
DeepQTest adopts multi-modal sensor fusion to encode the state. Compared to
DeepCollision, we further consider realism by defining realistic constraints
in DeepQTest to ensure that AVUT can be tested with realistic scenarios. To
better explore testing of ADS with various environment configurations, in
DeepQTest, we involved 90 more environment configurations APIs than
DeepCollision, i.e., 142 APIs in DeepQTest vs. 52 APIs in DeepCollision.

Algorithm 2 RS-based Environment Configuration

1:

2:Let TEnv be the test environment; AS be the environment configuration action
space; terminate be the stopping criteria.

3:

4:$Act_{list}$: a list of actions selected from AS

5:

6:$Act_{list}$ $\leftarrow$ []

7:s $\leftarrow$ observe a state from TEnv

8:while $\neg$ terminate do

9: $act$ $\leftarrow$ randomly select an action from $AS$

10: terminate, reward, $s^{\prime}$ $\leftarrow$ step($act$, s)
$\triangleright$ execute the selected action in state s

11: Put $act$ into $Act_{list}$

12: $s\leftarrow s^{\prime}$

13:end while

14:return $Act_{list}$

Algorithm 3 GS-based Environment Configuration

1:

2:Let TEnv be the test environment; AS be the environment configuration action
space; terminate be the stopping criteria.

3:

4:$Act_{list}$: a list of actions selected from AS

5:

6:$Act_{list}$ $\leftarrow$ []

7:s $\leftarrow$ observe a state of TEnv

8:$TEnv_{pre}$ $\leftarrow$ SaveEnv(TEnv, s) $\triangleright$ save the TEnv
with state $s$

9:while $\neg$ terminate do

10: rewardmax $\leftarrow$ 0

11: $act_{optimal}$ $\leftarrow$ 0

12: for each action act in AS do $\triangleright$ try each action in the
action space

13: _, reward, _ $\leftarrow$ step(act, s)

14: if reward >rewardmax then

15: rewardmax $\leftarrow$ reward

16: $act_{optimal}$ $\leftarrow$ act

17: end if

18: TEnv $\leftarrow$ RollBackEnv($TEnv_{pre}$, $s$)

19: end for

20: terminate, $reward$, $s^{\prime}$ $\leftarrow$ step($act_{optimal}$)
$\triangleright$ execute the action that achieves the maximum reward

21: Put $act_{optimal}$ into $Act_{list}$

22: $TEnv_{pre}$ $\leftarrow$ SaveEnv(TEnv, $s^{\prime}$)

23: $s\leftarrow s^{\prime}$ $\triangleright$ move to the next environment
state

24:end while

25:return $Act_{list}$

###  5.3 Experiment Settings

####  5.3.1 Subject System and Simulator

To evaluate DeepQTest, we adopt Baidu’s open-source autonomous driving
platform Apollo [85] as the subject system under test, which is a high-
performance ADS with various modules responsible for various tasks, such as
traffic light recognition, obstacle perception and avoidance, and trajectory
planning and routing. Apollo is a flexible architecture with high-driving
automation, aiming to support the development, testing, and deployment of
autonomous vehicles. Concretely, we used the Apollo Open Platform 5.0, which
can operate without human interactions in most circumstances and handle
complex road scenarios with enhanced perception deep learning models.

We adopt LGSVL Simulator [75] to simulate the autonomous vehicle and its
operating environment. Specifically, LGSVL is an open-source, high-fidelity
autonomous driving simulation platform that provides an essential vehicle
dynamic model for vehicle simulation and supports a set of sensors, including
cameras, LiDAR, GPS, and Radar. LGSVL can easily connect to autopilot
platforms such as Apollo and Autoware [43], enabling us to perform software-
in-the-loop and hardware-in-the-loop ADS testing. In our experiment, we
employed LGSVL Simulator 5.0. We selected the San Francisco HD map, a digital
re-creation of a section of the South of Market Street (SoMa) in San Francisco
with various driving environment characteristics, e.g., traffic light
intersections and multi-lane streets. Regarding the AVUT, we used
Lincoln2017MKZ, a four-door Sedan car equipped with various sensor
configurations.

####  5.3.2 Model Training

We selected 4 different types of real-world weather conditions (shown in Table
2) in San Francisco from the OpenWeather dataset. Next, we trained 12 (3
reward settings $\times$ 4 real-world weather conditions) DeepQTest models.
Accordingly, we defined 12 RS and 12 GS strategies. We use convention
$\textit{DeepQTest}_{[reward][real-world-weather]}$ to denote each trained
model, and use $\textit{GS}_{[reward][real-world-weather]}$,
$\textit{RS}_{[reward][real-world-weather]}$ to denote each baseline strategy
(Section 5.2). For example, $\textit{DeepQTest}_{TTC_{RD}}$ denotes the model
trained in the rainy day (RD) with reward function $TTC_{Reward}$.

All models were trained with the same network architecture, learning
algorithm, reward design, and hyperparameter settings to ensure fair
comparisons. For training each model, we used the Adam algorithm [94] with
mini-batches of size 64 as the adaptive optimization algorithm. To manage the
trade-off between exploration and exploitation, we applied $\epsilon$-greedy
as the behavior policy during training with $\epsilon$ annealed from 1.0 to
0.2 over the first 10000 observed states and fixed at 0.2 thereafter. Such a
setting of behavior policy lets the agent explore more at the beginning of the
training process when little is known about the problem environment, and as
the training progresses, the agent gradually conducts more exploitation than
exploration. We trained for a total of 40000 observed states and used a replay
memory with a size of 6000.

Table 2: Real-world weather conditions applied in the experiment

| Rainy Day (RD) | Rainy Night (RN) | Sunny Day (SD) | Sunny Night (SN)
---|---|---|---|---
Date | 2021-08-07 | 2021-08-07 | 2021-07-24 | 2021-07-24
Time | 8:00:00 | 20:00:00 | 8:00:00 | 20:00:00
Description | Heavy intensity rain | Heavy intensity rain | Clear sky | Clear sky

Based on our pilot study, we found that directly training on a huge HD map
with many roads is not easy. Because we are trying to generate complex driving
scenarios for an AVUT driving from origin to destination, thus if the driving
path is too long, then it will take much more time for one episode. Moreover,
as the training progresses, the environment will be more complex for the AVUT
arriving at the destination, therefore, collisions tend to occur early in the
driving task. Thus, we divided the map into road segments with lengths of
about 1km to 2km. Next, we trained each model on each road segment to gain a
final model. This allows the agent to finish one episode within a reasonable
time and ensures that the whole road is fully explored and exploited.

The values of all hyperparameters are determined based on the parameter
settings from [63, 67]. We provide the settings of all hyperparameters in our
online repository (see Section 6.5).

####  5.3.3 Experiment Design and Execution

Roads. To ensure that the experiments are run in the same environment, we used
the same roads adopted in DeepCollision [58], which are selected based on the
road structure definition in [21]. Figure 4 graphically depicts their
characteristics.

(a) R1 (1.0km)

(b) R2 (1.2km)

(c) R3 (1.0km)

(d) R4 (1.5km)

Figure 4: Graphical representations of the roads from [58]

Driving Scenarios. A driving scenario S describes the temporal development
between several scenes, where a scene describes a snapshot of the environment
including the AVUT, static and dynamic obstacles, and environmental conditions
such as weather and traffic rules [87]. We, therefore, formally define a
driving scenario as a tuple with scenes:
S=$<scene^{1},scene^{2},...,scene^{n},ST>$, where ST is the time period that
the scenario spans and n denotes the number of scenes in the scenario. A
driving scene is a 3-tuple <AVUT Operation, AVUT Speed, Environment State>,
denoting AVUT operations such as cruise, a speed level of the AVUT, e.g., zero
or slow, and 3) environment state about weather condition, time of date,
traffic rules, obstacles, and their behaviors, etc. More specifically, we use
11 properties (column 3, Table 3) to characterize AVUT ’s states (rows 1 and
2, Table 3) and the environment (rows 3 to 11, Table 3). Note that NPC
vehicles, Pedestrians, Static obstacles, Traffic Lights, and Sidewalks are
collected within the sensing range of the radar deployed on the AVUT.
Moreover, in our current design, the time period that the scenario spans
(i.e., ST) is set to 3 seconds.

Table 3: Properties characterizing scenes in the formal experiment

# |  | Property | Property Value
---|---|---|---
1 |  AVUT | Operation | Stop; Cruise; SpeedUp; SpeedCut; EmergencyBrake; SwitchLaneToRight; SwitchLaneToLeft; TurnLeft; TurnRight
2 | Speed (m/s) | Zero (0 <speed $\leq$ 1); Slow (1 <speed $\leq$ 5); Moderate (5 <speed $\leq$ 12); Fast (speed >12)
3 | Env | Weather: rain | None (rainlevel = 0); Light (0 <rain${}_{level}\leq$ 0.2); Moderate (0.2 <rain${}_{level}\leq$ 0.5); Heavy (rain${}_{level}>0.5$)
4 | Weather: fog | None (foglevel = 0); Light (0 <fog${}_{level}\leq$ 0.2); Moderate (0.2 <fog${}_{level}\leq$ 0.5); Heavy (fog${}_{level}>0.5$)
5 | Weather: wetness | None (wetnesslevel = 0); Light (0 <wetness${}_{level}\leq$ 0.2); Moderate (0.2 <wetness${}_{level}\leq$ 0.5); Heavy (wetness${}_{level}>0.5$)
6 | Time of the day | Morning (10am); Noon (12am); Night (8pm)
7 | NPC vehicle* |  Volume ($m^{3}$): Small (volume $\leq$ 10); Medium (10 < volume $\leq$ 60); Large (volume >60)
Operation: Stop; SwitchLane; LeftLaneDriving; RightLaneDriving;
CurrentLaneDriving
Speed (m/s): Zero (0 <speed $\leq$ 1); Slow (1 <speed $\leq$ 5); Moderate (5
<Speed $\leq$ 12); Fast (speed >12)
Distance from AVUT (m):  Zero ($\lvert d\rvert$ = 0); Very near (0 <$\lvert
d\rvert$ $\leq$ 8); Near (8 <$\lvert d\rvert$ $\leq$ 18); Far (18 <$\lvert
d\rvert$ $\leq$ 28); Very far ($\lvert d\rvert$ >28)
8 | Pedestrian* |  Volume ($m^{3}$): Small (volume <1)
Operation: Stop; Crossing the road; FrontLaneWalking
Distance from AVUT (m):  Zero ($\lvert d\rvert$ = 0); Very near (0 <$\lvert
d\rvert$ $\leq$ 8); Near (8 <$\lvert d\rvert$ $\leq$ 18); Far (18 <$\lvert
d\rvert$ $\leq$ 28); Very far ($\lvert d\rvert$ >28)
9 | Static obstacles* |  Volume ($m^{3}$): Small (volume $\leq$ 3); Medium (3 < volume $\leq$ 10); Large (volume >10)
Distance from AVUT (m):  Zero ($\lvert d\rvert$ = 0); Very near (0 <$\lvert
d\rvert$ $\leq$ 8); Near (8 <$\lvert d\rvert$ $\leq$ 18); Far (18 <$\lvert
d\rvert$ $\leq$ 28); Very far ($\lvert d\rvert$ >28)
10 |  | Traffic Rule: traffic light | None; Green (allow to pass but slow at intersection); Yellow (stop for a while); Red (do not run a red light)
11 |  | Traffic Rule: side walk | None; SlowDown

Execution. To answer the RQs (Section 5.1), each trained DeepQTest model, RS,
GS, and DeepCollision were run 20 times on each of the four roads (R1…R4). The
trained DeepQTest models were evaluated with an $\epsilon$-greedy behavior
policy with $\epsilon$=0.05. As suggested by Mnih [63], this setting is
adopted to minimize the possibility of overfitting during evaluation. In
total, we obtained results of 2880 executions (20 runs $\times$ 4 roads
$\times$ 3 strategies $\times$ 3 reward functions $\times$ 4 Real-World
Effects). All the experiments were executed on three machines with identical
configurations with a 2.4GHz Intel Xeon E5-2680 v4 CPU, an 11GB NVIDIA GeForce
GTX 1080 Ti GPU, and 32GB RAM. The operating systems are all Ubuntu 18.04.6
LTS.

###  5.4 Evaluation Metrics

In this section, we present the definition of the evaluation metrics: Safety
and Comfort Metrics, Realism Metrics, and Diversity Metrics. As shown in Table
1, for RQ1, we use Safety and Comfort Metrics to evaluate the performance of
DeepQTest when comparing with RS and GS. We adopt Safety and Comfort Metrics,
and Diversity Metrics to evaluate the performance of the three reward
functions of DeepQTest (RQ2). Regarding the comparison with DeepCollision
(RQ3), we use Realism Metrics to evaluate the realism of the generated
scenarios because both DeepQTest and DeepCollision have different mechanisms
to ensure the scenario realism, and Diversity Metrics is used for evaluating
the diversity of environment configurations and scenarios of the two
approaches.

####  5.4.1 Safety and Comfort Metrics

In DeepQTest, we defined three reward functions based on TTC, DTO, and Jerk,
respectively, which are related to driving safety or comfort. In our
evaluation, we employed them to study the performance of the reward functions
and their potential correlations. These metrics are formally defined as
Equation 11, where $k$ denotes the $k$th execution, and $i$ denotes the $i$th
simulation time T (see Section 4.4.2) in the execution.

$SCM_{k}=\dfrac{\sum_{i=1}^{n}SCM^{i}_{k}}{n},SCM\in\\{TTC,DTO,Jerk\\},k=1...20$
(11)

In addition, during each execution $k$, we collected the number of collisions
$\\#Collision_{k}$. $\\#Collision_{k}$ could be 0 if no collision occurred.
For DeepQTest, $\\#Collision_{k}\in\\{0,1\\}$ as it terminates the execution
once a collision is identified. For DeepCollision, $\\#Collision_{k}$ could be
more than one, because DeepCollision allows the AVUT to continue to move
forward after the occurrence of a collision. We also calculated
$CollisionTime_{k}$, which measures how long a collision can be observed on
average.

####  5.4.2 Realism Metrics

To evaluate DeepQTest and DeepCollision in terms of whether they generate
realistic scenarios, in addition to the realistic constraints on Objects and
Roads (Section 4.2), we further define a set of realistic constraints on the
parameters for weather and time. Specifically, for weather and its change over
time, we ensure its realism based on four weather-related measurements which
can be observed in the simulator, i.e., rain, cloudiness, fog, and wetness. By
analyzing real-world historical weather data from an open weather dataset,
i.e., OpenWeather222https://openweathermap.org/, we calculate the range of
realistic changes over time of these four weather-related measurements and
then define the following constraints for ensuring the realism of the weather
and its change.

  * •

Rain reflects the intensity of the rainfall, to be realistic, the rain level
change within 1 hour should be less than 20%.

⬇

context Rain

inv: self.rainLevel <= (self.getPreviousValue(1h).rainLevel+0.2).max(1.0) and
self.rainLevel >= (self.getPreviousValue(1h).rainLevel-0.2).min(0.0)

  * •

Cloudiness refers to the extent to which the atmosphere is covered by clouds
(measured by cloudinessLevel in Figure 2). For instance, cloudiness which is
less than 30% represents a clear sky while near 100% cloudiness represents an
overcast sky. To be realistic, the cloudiness level change within an hour
should be less than 25%. For example, if the current cloudiness is 25%, the
realistic cloudiness within one hour should be between 0% and 50%.

⬇

context Cloudiness

inv: self.cloudinessLevel <=
(self.getPreviousValue(1h).cloudinessLevel+0.25).max(1.0) and
self.cloudinessLevel >=
(self.getPreviousValue(1h).cloudinessLevel-0.25).min(0.0)

  * •

Fog impacts the visibility of the vehicle, according to the analysis of its
changes based on real-world weather data, we consider it realistic that the
change of fog level within one hour is within 10%.

⬇

context Fog

inv: self.fogLevel <= (self.getPreviousValue(1h).fogLevel+0.1).max(1.0) and
self.fogLevel >= (self.getPreviousValue(1h).fogLevel-0.1).min(0.0)

  * •

Wetness (expressed as a percentage) reflects how the road surfaces should be.
The realistic wetness level changes within an hour should be less than 5%. For
example, if the current wetness level is 80%, the realistic wetness level in
one hour should be between 75% and 85%.

⬇

context Wetness

inv: self.wetnessLevel <=
(self.getPreviousValue(1h).wetnessLevel+0.05).max(1.0) and self.wetnessLevel
>= (self.getPreviousValue(1h.wetnessLevel)-0.05).min(0.0)

  * •

Regarding time of day, its changes should follow the passage of time in the
real world. However, in the simulated world, the simulator has its own clock.
So, we consider the passage of time to be realistic if the passage of time
follows or is slower than the simulation time.

⬇

context TimeOfDay

def: t = secondinsimulation

inv: self.timeofday <= self.getPreviousValue(t).timeofday + t

By validating if generated scenarios satisfy the above constraints in terms of
realism, we further classified the generated scenarios into four types by
considering collisions, i.e., Realistic Collision Scenarios (RCS), Unrealistic
Collision Scenarios (UCS), Realistic Non-Collision Scenarios (RNS), and
Unrealistic Non-Collision Scenarios (UNS). For each execution $k$, we
collected the total number of the generated test scenarios as
$\\#\textit{TS}_{k}$, the number of these four types of scenarios as
$\\#\textit{RCS}_{k}$, $\\#\textit{UCS}_{k}$, $\\#\textit{RNS}_{k}$, and
$\\#\textit{UNS}_{k}$, and proportion of the four types out of all scenarios
as $RCS\%_{k}$, $UCS\%_{k}$, $RNS\%_{k}$, and $UNS\%_{k}$. In addition, we
also calculated the average time it takes for a realistic collision scenario
(i.e., $\textit{RCS}_{k}$) to happen as Realistic Collision Time
($RCT_{{RCS}_{k}}$).

####  5.4.3 Diversity Metrics

To measure Diversity in one execution, we defined two metrics: API Diversity
(i.e., $Div_{API}$), and Scenario Diversity (i.e., $Div_{Scenario}$).

API Diversity ($Div_{API}$) measures the diversity of the environment
configuration APIs invoked. $Div_{API}$ is calculated for each execution $k$
as ${Div_{API}}_{k}=\dfrac{\\#UniqueAPI_{k}}{\\#InvokedAPI_{k}}$, where
$\\#UniqueAPI_{k}$ represents the number of the unique environment
configuration APIs invoked in execution $k$ and $\\#InvokedAPI_{k}$ represents
the total number of the invoked APIs in execution $k$.

Figure 5: The process for scenario identification in the $k$th execution. $k$
denotes the $k$th execution, and $T$ is the simulation time after an
environment configuration action is invoked. $scene_{k,x}$ is the $xth$ scene
captured in the $k$th execution.

Scenario Diversity ($Div_{Scenario}$) measures the diversity of generated
driving scenarios. A driving scenario (see Section 5.3.3) is regarded as a
sequence of scenes over a time period, i.e.,

$S_{k,i}=<scene_{k,i}^{1},scene_{k,i+1}^{2},...,scene_{k,i+n-1}^{n},ST>$ (12)

where $k$ is the $k$th execution, $i$ is the $i$th scenario that occurred in
the execution, $scene_{k,x}$ is the $xth$ scene captured in the execution, $n$
is the number of scenes in the scenario, and $ST$ is the time period that the
scenario spans. In our current design, we set $ST$ as 3 seconds, which is the
same as the simulation time (i.e., T) after invoking an environment
configuration action, and capture a scene every 0.5 seconds; therefore, each
scenario contains 6 scenes, i.e., $n=6$. Figure 5 shows an example of how
scenarios are identified in the $k$th execution. For an execution $k$,
$Div_{Scenario}$ is calculated by comparing occurred scenarios based on the 11
properties characterizing scenes (Table 3). For each pair of scenarios (i.e.,
$S_{k,i}$, $S_{k,j}$ and $i\neq j$) in the $k$th execution, we first calculate
$similarity$ between $S_{k,i}$ and $S_{k,j}$ based on Algorithm 5, which is
inspired by the Ratcliff-Obershelp similarity algorithm [10] which is
originally designed for measuring the similarity of two strings [50].
Algorithm 5 calculates $Sim_{S_{k,i},S_{k,j}}$ by finding a set of consecutive
scenes that can maximize the similarity between $S_{k,i}$ and $S_{k,j}$:

$Sim_{S_{k,i},S_{k,j}}=\textsc{scenarioSimilarity}(S_{k,i},S_{k,j}),Sim_{S_{k,i},S_{k,j}}\in[0,1];$
(13)

then, we define their $diversity$ ($Div_{S_{k,i},S_{k,j}}$) based on the
$similarity$ as:

$Div_{S_{k,i},S_{k,j}}=1-Sim_{S_{k,i},S_{k,j}};$ (14)

Scenario Diversity is calculated based on all such pairwise $diversity$ of the
scenarios in the $k$th execution as:

${Div_{Scenario}}_{k}=\dfrac{\sum_{i=1}^{m-1}\sum_{j=i+1}^{m}Div_{S_{k,i},S_{k,j}}}{m},$
(15)

where $m$ is the number of scenarios generated in execution $k$.

###  5.5 Statistical Test

To account for the randomness caused by the RL algorithm (i.e., DQN) and the
ADS itself, it is essential to use statistical tests to compare the
performance of different strategies [5, 38]. The selection of appropriate
statistical techniques is vital to answer the RQs correctly. As suggested by
Arcuri and Briand [5], we first checked if our samples are normally
distributed using the Kolmogorov-Smirnov test [13], and results show that they
are not normally distributed. Thus, we applied the non-parametric statistical
techniques to compare samples generated by DeepQTest and baseline strategies.

Specifically, we use the Mann and Whitney U test [62] for assessing the
statistical significance and calculate the effect size with Vargha and Delaney
metric $\hat{A}_{12}$. Given an evaluation metric, $\mathcal{M}$,
$\hat{A}_{12}$ was used to compare the probability (i.e., how often) of
yielding higher values of the metric $\mathcal{M}$ for two strategies, A and
B. If $\hat{A}_{12}$ is 0.5, then they are equal. If $\hat{A}_{12}$ is greater
than 0.5, then A has a higher chance to obtain higher values of $\mathcal{M}$
than B, and vice versa. The Mann–Whitney U test calculates a $p$-value to
determine if the performance difference between A and B is significant. A
$p$-value less than 0.05 indicates the significant difference between A and B.
In addition, by following the guidelines proposed by Kitchenham et al. [48],
we divide the Vargha and Delaney effect size magnitude of $\hat{A}_{12}$ into
four levels: negligible ($\hat{A}_{12}$ $\in$ (0.444, 0.556)), small
($\hat{A}_{12}$ $\in$ [0.556, 0.638) or (0.362, 0.444]), medium
($\hat{A}_{12}$ $\in$ [0.638, 0.714) or (0.286, 0.362]), large ($\hat{A}_{12}$
$\in$ [0.714, 1.0] or [0, 0.286]).

In addition to investigating the performance of different strategies, we also
want to investigate the correlation among the three selected measures, i.e.,
TTC, DTO, Jerk. We choose to use Spearman’s rank correlation ($\rho$) test,
which is a non-parametric, rank-based assessment of correlation test. The
$\rho$ value ranges from $-1.0$ to 1.0, i.e., there is a positive correlation
if $\rho$ is close to 1.0 and a negative correlation when $\rho$ closes to
$-1.0$. If $\rho$ is closer to 0, then there is no correlation between the two
measures. We also reported the significance of the correlation using a
$p$-value, i.e., a $p$-value less than 0.05 tells that the correlation is
statistically significant.

##  6 Experiment Results and Analysis

###  6.1 Results for RQ1

To answer RQ1, we compare each of the three reward settings of DeepQTest
(i.e., $DeepQTest_{TTC}$, $DeepQTest_{DTO}$, $DeepQTest_{Jerk}$) with the RS
and GS strategies. We repeated the experiment 20 times under all real-world
weather conditions on all roads (i.e., 20 runs $\times$ 4 real-world weather
conditions $\times$ 4 roads = 320 samples for each of the three strategies).
The comparison analysis was performed with Safety and Comfort Metrics using
the Mann and Whitney U test and Vargha and Delaney effect size. Results are
summarized in Table 4, and the detailed statistical results on each road for
the three reward settings can be seen in Table 10, 11, and 12 in Appendix
Appendix.

As can be seen from Table 4, DeepQTest with all settings significantly
outperformed RS and GS in terms of all metrics.

Table 4: Results of pair comparison of DeepQTest and RS/GS in terms of Safety
and Comfort Metrics using the Vargha and Delaney statistics and the
Mann–Whitney U test - RQ1

DeepQTest vs. (RS, GS) | TTC | DTO | Jerk | #Collision | CollisionTime
---|---|---|---|---|---
$\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$
$DeepQTest_{TTC}$ | GS | 0.095 | <0.05 | 0.117 | <0.05 | 0.735 | <0.05 | 0.834 | <0.05 | 0.149 | <0.05
RS | 0.091 | <0.05 | 0.125 | <0.05 | 0.724 | <0.05 | 0.784 | <0.05 | 0.179 | <0.05
$DeepQTest_{DTO}$ | GS | 0.172 | <0.05 | 0.058 | <0.05 | 0.639 | <0.05 | 0.802 | <0.05 | 0.162 | <0.05
RS | 0.186 | <0.05 | 0.064 | <0.05 | 0.661 | <0.05 | 0.797 | <0.05 | 0.176 | <0.05
$DeepQTest_{Jerk}$ | GS | 0.285 | <0.05 | 0.422 | <0.05 | 0.635 | <0.05 | 0.709 | <0.05 | 0.279 | <0.05
RS | 0.269 | <0.05 | 0.437 | <0.05 | 0.619 | <0.05 | 0.711 | <0.05 | 0.274 | <0.05

  * ∗

$p$ is p-value; a bold $\hat{A}_{12}$ with a $p<0.05$ implies that DeepQTest
is significantly better than GS/RS. $\hat{A}_{12}$ magnitude: negligible
($\hat{A}_{12}$ $\in$ (0.444, 0.556)), small ($\hat{A}_{12}$ $\in$ [0.556,
0.638) or (0.362, 0.444]), medium ($\hat{A}_{12}$ $\in$ [0.638, 0.714) or
(0.286, 0.362]), large ($\hat{A}_{12}$ $\in$ [0.714, 1.0] or [0, 0.286]).

In terms of $\hat{A}_{12}$, we found that for TTC, and CollisionTime,
$\hat{A}_{12}$ is at large magnitude level (i.e., $\geq$ 0.714 or $\leq$
0.286) for all the cases. For DTO, $\hat{A}_{12}$ is at the large magnitude
level (i.e., $\leq$ 0.286) except for $DeepQTest_{Jerk}$ with which we
observed the small magnitude level results. For Jerk, $\hat{A}_{12}$ is at
least at the large magnitude level (i.e., $\geq$ 0.714) for $DeepQTest_{TTC}$,
the medium magnitude level (i.e., $\geq$ 0.638) for $DeepQTest_{DTO}$, and the
small magnitude level for $DeepQTest_{Jerk}$ (i.e., $\geq$ 0.556). For the
#Collision metric, we can observe that $\hat{A}_{12}$ is at the large
magnitude level (i.e., $\geq$ 0.714) for $DeepQTest_{TTC}$ and
$DeepQTest_{DTO}$, and at medium magnitude level (i.e., $\geq$ 0.638) for
$DeepQTest_{Jerk}$.

In addition, to study the distributions of each metric, we present violin
plots for DeepQTest, RS, and GS for each reward setting in Figure 6. From the
figure, we can observe that all settings of DeepQTest outperformed RS and GS
in terms of the average values (red dots in Figure 6) of all evaluation
metrics. We looking at the distributions, we can see that DeepQTest achieved
less variability, except for Jerk, implying that DeepQTest performed more
stably in terms of TTC, DTO, #Collision, and CollisionTime. For Jerk, although
DeepQTest performed less stably, it still achieved higher Jerk values on
average. One plausible explanation is that $DeepQTest_{Jerk}$ may not be as
effective as $DeepQTest_{TTC}$, $DeepQTest_{DTO}$) in terms of training a
stable DeepQTest model. More discussions about this observation will be
provided in Section 6.2.

* $DQT$: DeepQTest; RS: Random Strategy; GS: Greedy Strategy.

Figure 6: Descriptive statistics of the evaluation metrics achieved by
DeepQTest, RS and GS– RQ1

Conclusion for RQ1: Compared to RS and GS, DeepQTest achieved significant
improvements in terms of all Safety and Comfort Metrics. This represents that
DeepQTest is more effective in generating environment configurations that lead
to shorter time to collide with obstacles (TTC), shorter distance to obstacles
(DTO), a lower degree of passenger comfort (Jerk), and more collision
occurrences (#Collision), and shorter (CollisionTime). In summary, the problem
we address is complex enough, which cannot effectively be addressed with RS
and GS.

###  6.2 Results for RQ2

To answer RQ2, we compare the performance achieved by each of the models under
three reward function settings (i.e., $DeepQTest_{TTC}$, $DeepQTest_{DTO}$,
$DeepQTest_{Jerk}$) on all four roads for each weather condition (i.e., RD,
RN, SD, SN). We repeated the experiment 20 times. Thus, for each weather
condition, there are in total of 80 (i.e., 20 runs $\times$ 4 Roads) samples
for each reward function. Table 5 reports the results of pair-wise comparisons
of the three reward functions in terms of Safety and Comfort Metrics and
Diversity Metrics for each weather condition. More detailed results for each
road can be found in Table 13 in Appendix.

Regarding Safety and Comfort Metrics, for all the weather conditions, we found
that $DeepQTest_{TTC}$ and $DeepQTest_{DTO}$ consistently achieved the best
performance; $DeepQTest_{TTC}$ is the most effective in generating environment
configurations that lead to less time for AVUT to collide with obstacles (TTC)
while $DeepQTest_{DTO}$ is the most effective in generating environment
configurations that lead to less distance between AVUT and obstacles (DTO), as
expected. For Jerk, it is surprising that the best results are achieved by
$DeepQTest_{TTC}$ but not $DeepQTest_{Jerk}$. Recall that Jerk is calculated
as the rate of changes of acceleration, therefore, to figure out the reason
that $DeepQTest_{TTC}$ outperformed $DeepQTest_{Jerk}$, we further analyzed
the changes in acceleration and the corresponding Jerk values by checking
scenarios generated by $DeepQTest_{Jerk}$ and $DeepQTest_{TTC}$. We found that
$DeepQTest_{Jerk}$ generates scenarios that result in higher Jerk over a
period of time. For instance, a sequence of acceleration ($m/s^{2}$)/Jerk
values over a period of time can be:

$T_{0}$: 2.70/2.44, $T_{1}$: 0.70/3.82, $T_{2}$: -2.22/6.12, $T_{3}$:
1.73/10.42.

However, $DeepQTest_{TTC}$ could generate scenarios where AVUT collides with
obstacles in a less period of time, and such scenarios would likely result in
a higher Jerk value, i.e., a lower degree of comfort for passengers. For
instance, in a run of $DeepQTest_{TTC}$, a sequence of acceleration
($m/s^{2}$)/Jerk values over three steps is:

$T_{0}$: 3.30/4.64, $T_{1}$: -0.91/8.58, $T_{2}$: 2.18/8.02.

There might exist correlations among reward functions based on their
corresponding metrics. To study the correlations, for each reward function, we
calculated TTC, DTO, Jerk at each step for all 20 runs on all of the four
roads, then analyzed results using Spearman’s rank correlation ($\rho$) test.
Results show a significantly positive correlation between TTC and DTO (i.e.,
$p<0.05$ and $\rho=0.423$), and significantly negative correlations observed
in TTC-Jerk (i.e., $p<0.05$ and $\rho=-0.254$) and DTO-Jerk (i.e., $p<0.05$
and $\rho=-0.292$). It indicates that a lower TTC (less time to collide with
obstacles) would lead to a lower DTO (i.e., less distance to obstacles) and a
higher Jerk (i.e., a lower degree of comfort).

In addition, we observed similar pair comparison results among reward
functions for metrics #Collision and CollisionTime. No significant difference
is observed between $DeepQTest_{TTC}$ and $DeepQTest_{DTO}$ under all four
kinds of weather conditions. Both $DeepQTest_{TTC}$ and $DeepQTest_{DTO}$
outperformed $DeepQTest_{Jerk}$ consistently on the four weather conditions,
and the differences are significant on RN, SD, and SN. It indicates that
reward functions based on TTC and DTO might have more chances to guide RL to
introduce environment configurations that result in collisions.

In Table 5, we also analyzed the diversity among the scenarios generated by
each reward function in each weather condition. Results show that
$DeepQTest_{Jerk}$ performed the best in terms of both diversity-related
metrics, i.e., invoking more diverse APIs ($Div_{API}$) and generating more
diverse scenarios ($Div_{Scenario}$). More specifically, $DeepQTest_{Jerk}$
outperformed $DeepQTest_{TTC}$ and $DeepQTest_{DTO}$ in terms of $Div_{API}$
and $Div_{Scenario}$ in all weather conditions, except $Div_{API}$ in RD. As
for $Div_{API}$ in RD, $DeepQTest_{Jerk}$ outperformed $DeepQTest_{DTO}$, and
$DeepQTest_{Jerk}$ and $DeepQTest_{TTC}$ performed equivalently in statistics.
Regarding $DeepQTest_{TTC}$ and $DeepQTest_{DTO}$, there is no significant
difference in terms of $Div_{API}$ and $Div_{Scenario}$. But in terms of
$Div_{API}$, $DeepQTest_{TTC}$ is slightly better than $DeepQTest_{DTO}$ as
$\hat{A}_{12}$ of comparing $DeepQTest_{TTC}$ with $DeepQTest_{TTC}$ is
greater 0.5 in all weather conditions.

Table 5: Results of pair comparisons among the three reward functions in terms
of Safety and Comfort Metrics and Diversity Metrics using the Vargha and
Delaney statistics and the Mann–Whitney U test - RQ2

Reward Comparison | TTC | DTO | Jerk | #Collision | CollisionTime | $Div_{API}$ | $Div_{Scenario}$
---|---|---|---|---|---|---|---
$\hat{A}_{12}$ | p | $\hat{A}_{12}$ | p | $\hat{A}_{12}$ | p | $\hat{A}_{12}$ | p | $\hat{A}_{12}$ | p | $\hat{A}_{12}$ | p | $\hat{A}_{12}$ | p
$DeepQTest_{TTC_{RD}}$ | $DeepQTest_{DTO_{RD}}$ | 0.281 | <0.05 | 0.789× | <0.05 | 0.606 | <0.05 | 0.525 | 0.475 | 0.499 | 0.980 | 0.530 | 0.503 | 0.461 | 0.475
$DeepQTest_{Jerk_{RD}}$ | 0.210 | <0.05 | 0.228 | <0.05 | 0.621 | <0.05 | 0.562 | 0.086 | 0.409 | <0.05 | 0.420 | 0.079 | 0.374× | <0.05
$DeepQTest_{DTO_{RD}}$ | $DeepQTest_{Jerk_{RD}}$ | 0.332 | <0.05 | 0.117 | <0.05 | 0.529 | 0.533 | 0.537 | 0.314 | 0.411 | <0.05 | 0.388× | <0.05 | 0.412× | <0.05
$DeepQTest_{TTC_{RN}}$ | $DeepQTest_{DTO_{RN}}$ | 0.297 | <0.05 | 0.811× | <0.05 | 0.625 | <0.05 | 0.475 | 0.442 | 0.571 | 0.111 | 0.610 | <0.05 | 0.568 | 0.094
$DeepQTest_{Jerk_{RN}}$ | 0.247 | <0.05 | 0.177 | <0.05 | 0.609 | <0.05 | 0.600 | <0.05 | 0.366 | <0.05 | 0.409× | <0.05 | 0.378× | <0.05
$DeepQTest_{DTO_{RN}}$ | $DeepQTest_{Jerk_{RN}}$ | 0.432 | <0.05 | 0.067 | <0.05 | 0.501 | 0.984 | 0.625 | <0.05 | 0.309 | <0.05 | 0.306× | <0.05 | 0.317× | <0.05
$DeepQTest_{TTC_{SD}}$ | $DeepQTest_{DTO_{SD}}$ | 0.304 | <0.05 | 0.826× | <0.05 | 0.636 | <0.05 | 0.525 | 0.421 | 0.535 | 0.435 | 0.553 | 0.235 | 0.527 | 0.639
$DeepQTest_{Jerk_{SD}}$ | 0.185 | <0.05 | 0.188 | <0.05 | 0.650 | <0.05 | 0.606 | <0.05 | 0.344 | <0.05 | 0.365× | <0.05 | 0.386× | <0.05
$DeepQTest_{DTO_{SD}}$ | $DeepQTest_{Jerk_{SD}}$ | 0.346 | <0.05 | 0.073 | <0.05 | 0.524 | 0.604 | 0.581 | <0.05 | 0.325 | <0.05 | 0.330× | <0.05 | 0.360× | <0.05
$DeepQTest_{TTC_{SN}}$ | $DeepQTest_{DTO_{SN}}$ | 0.371 | <0.05 | 0.787× | <0.05 | 0.625 | <0.05 | 0.519 | 0.551 | 0.536 | 0.417 | 0.529 | 0.523 | 0.490 | 0.832
$DeepQTest_{Jerk_{SN}}$ | 0.185 | <0.05 | 0.182 | <0.05 | 0.581 | 0.078 | 0.600 | <0.05 | 0.339 | <0.05 | 0.323× | <0.05 | 0.338× | <0.05
$DeepQTest_{DTO_{SN}}$ | $DeepQTest_{Jerk_{SN}}$ | 0.347 | <0.05 | 0.082 | <0.05 | 0.457 | 0.352 | 0.581 | <0.05 | 0.335 | <0.05 | 0.333× | <0.05 | 0.349× | <0.05

  * ∗

RD: Rainy Day; RN: Rainy Night; SD: Sunny Day; SN: Sunny Night; $p$ is
p-value; a bold $\hat{A}_{12}$ with a $p<0.05$ implies that the former model
is significantly
better than the latter, whereas a $\hat{A}_{12}$ decorated by symbol "×"
indicates the former model performed significantly worse than the latter; a
$p>0.5$ means no
significant difference between two models. $\hat{A}_{12}$ magnitude:
negligible ($\hat{A}_{12}$ $\in$ (0.444, 0.556)), small ($\hat{A}_{12}$ $\in$
[0.556, 0.638) or (0.362, 0.444]), medium
($\hat{A}_{12}$ $\in$ [0.638, 0.714) or (0.286, 0.362]), large ($\hat{A}_{12}$
$\in$ [0.714, 1.0] or [0, 0.286]).

Table 6: Ranking of $DeepQTest_{TTC}$, $DeepQTest_{DTO}$, and
$DeepQTest_{Jerk}$ in terms of metrics and real-world weather conditions - RQ2

| $TTC$ | $DTO$ | $Jerk$ | $\\#Collision$ | $CollisionTime$ | $DIV_{API}$ | $DIV_{Scenario}$
---|---|---|---|---|---|---|---
$RD$ |  $DQT_{T}$, $DQT_{D}$, $DQT_{J}$ |  $DQT_{D}$, $DQT_{T}$, $DQT_{J}$ |  $DQT_{T}$, $DQT_{D}$/$DQT_{J}$ |  $DQT_{T}$/$DQT_{D}$/$DQT_{J}$ |  $DQT_{D}$/$DQT_{T}$, $DQT_{J}$ |  $DQT_{J}$,$DQT_{T}$/$DQT_{D}$ |  $DQT_{J}$,$DQT_{D}$/$DQT_{T}$
$RN$ |  $DQT_{T}$, $DQT_{D}$, $DQT_{J}$ |  $DQT_{D}$, $DQT_{T}$, $DQT_{J}$ |  $DQT_{T}$, $DQT_{J}$/$DQT_{D}$ |  $DQT_{D}$/$DQT_{T}$, $DQT_{J}$ |  $DQT_{T}$/$DQT_{D}$, $DQT_{J}$ |  $DQT_{J}$,$DQT_{T}$/$DQT_{D}$ |  $DQT_{J}$,$DQT_{T}$/$DQT_{D}$
$SD$ |  $DQT_{T}$, $DQT_{D}$, $DQT_{J}$ |  $DQT_{D}$, $DQT_{T}$, $DQT_{J}$ |  $DQT_{T}$, $DQT_{D}$/$DQT_{J}$ |  $DQT_{T}$/$DQT_{D}$, $DQT_{J}$ |  $DQT_{T}$/$DQT_{D}$, $DQT_{J}$ |  $DQT_{J}$,$DQT_{T}$/$DQT_{D}$ |  $DQT_{J}$,$DQT_{T}$/$DQT_{D}$
$SN$ |  $DQT_{T}$, $DQT_{D}$, $DQT_{J}$ |  $DQT_{D}$, $DQT_{T}$, $DQT_{J}$ |  $DQT_{T}$,$DQT_{J}$/$DQT_{D}$ |  $DQT_{T}$/$DQT_{D}$, $DQT_{J}$ |  $DQT_{T}$/$DQT_{D}$, $DQT_{J}$ |  $DQT_{J}$,$DQT_{T}$/$DQT_{D}$ |  $DQT_{J}$, $DQT_{D}$/$DQT_{T}$
$Rec_{M}$ | $DQT_{T}$ | $DQT_{D}$ | $DQT_{T}$ | $DQT_{T}$ | $DQT_{T}$ | $DQT_{J}$ | $DQT_{J}$

  * ∗

$DQT_{T}$: $DeepQTest_{TTC}$, $DQT_{D}$: $DeepQTest_{DTO}$, $DQT_{J}$:
$DeepQTest_{Jerk}$. RD: Rainy Day; RN: Rainy Night; SD: Sunny Day; SN: Sunny
Night;
a reward function before "," is statistically significantly better than the
reward function after ","; a "/" means two reward functions have no
statistically significant
difference, and a reward function before "/" achieved better (or the same)
performance than the reward function after "/" in terms of mean metric values.
$Rec_{M}$:
recommended by metric.

Based on Table 5, we summarized the results obtained by the three reward
functions in each weather condition for each metric using ranking and provided
a recommendation of reward function for each metric in Table 6. For all
metrics, we found that the ranking results of the three reward functions do
not vary much in weather conditions. $DeepQTest_{TTC}$ achieved the overall
best performance in terms of all metrics.

Conclusion for RQ2: Among all three reward functions (i.e., $DeepQTest_{TTC}$,
$DeepQTest_{DTO}$, and $DeepQTest_{Jerk}$), $DeepQTest_{TTC}$ achieved the
overall best performance. Regarding Safety and Comfort Metrics,
$DeepQTest_{TTC}$ performed the best in terms of TTC and Jerk, and the second
best in terms of DTO. As for #Collision and CollisionTime, $DeepQTest_{TTC}$
and $DeepQTest_{DTO}$ both performed the best. Regarding Diversity Metrics,
$DeepQTest_{Jerk}$ performed the best, followed by $DeepQTest_{TTC}$.

###  6.3 Results for RQ3

To answer RQ3, we compared DeepQTest with DeepCollision [58] regarding Realism
Metrics and Diversity Metrics. Table 7 reports results of scenarios in terms
of realism along with the occurrence of collisions, achieved by the best
reward function (i.e., $DeepQTest_{TTC}$) and DeepCollision on all of the four
roads (i.e., R1–R4) under the four weather conditions (i.e.,
$DeepQTest_{TTC_{RD}}$, $DeepQTest_{TTC_{RN}}$, $DeepQTest_{TTC_{SD}}$,
$DeepQTest_{TTC_{SN}}$). Table 8 represents the results of pair comparisons of
$DeepQTest_{TTC}$ and DeepCollision using Vargha and Delaney statistics
($\hat{A}_{12}$) and the Mann–Whitney U test ($p$-value).

The termination criterion of DeepCollision is either to reach the specified
destination or to run out of the specified time budget, which allows AVUT to
continue driving even if a collision happens. But, for DeepQTest, besides
reaching the destination or running out of the budget, it also terminates
testing once a collision occurs. Thus, compared to DeepQTest, DeepCollision
generates more test scenarios, as shown in column #TS) in Table 7.

As for Realism Metrics, based on results shown in Table 7, all scenarios
generated by $DeepQTest_{TTC}$ are realistic scenarios (with RCS % and RNS %
being 100%, and unrealistic scenarios with UCS % and UNS % being 0%). This is
because DeepQTest is designed by considering realistic constraints (Section
4.2), and all scenarios generated by DeepQTest conform to these constraints.
Instead, DeepCollision achieved a limited performance in generating realistic
scenarios on R1, R3, and R4: the percentages of generated realistic scenarios
(RCS % and RNS %) are 40.93% (0.55% + 40.38%), 3.49% (0.38% + 3.44%) and 2.68%
(0.04% + 2.64%), respectively. On R2, DeepCollision generated 89.36% realistic
scenarios out of the 3440 scenarios.

Regarding realistic collision scenarios, $DeepQTest_{TTC}$ generated more
realistic collision scenarios (#RCS) than DeepCollision on R2, R3 and R4.
Especially for R3 and R4, with 20 runs, $DeepQTest_{TTC}$ generated a minimum
of 13 and a maximum of 18 realistic collision scenarios, while DeepCollision
produced only 2 realistic collision scenarios. On R1, although DeepCollision
generated 19 realistic collision scenarios, the percentage of realistic
collision scenarios (i.e., RCS % = 0.55%) is much smaller than that for
DeepQTest (i.e., at least 2.02%), implying that on R1, DeepCollision needed to
generate a higher number of scenarios (3440) to get a comparable number of
realistic collision scenarios as DeepQTest. Besides, the proportions of
collision scenarios among all realistic scenarios achieved by DeepCollision
are all lower than DeepQTest. In addition, the significant outperformance of
DeepQTest over DeepCollision, with large effect size magnitude, can be
observed in Table 8, indicated as $p$-$value<0.05$ and $\hat{A}_{12}>0.825$.
On R1, DeepCollision generated the most realistic collision scenarios (i.e.,
19), but the difference is modest (i.e., 19 vs. 16) and not significant (i.e.,
$p$-$value>0.05$ and $\hat{A}_{12}\in[0.425,0.450]$). Note that the low
percentage of realistic collision scenarios (RCS %) by $DeepQTest_{TTC}$
(i.e., the maximum is 3.44% with $DeepQTest_{TTC_{SD}}$ on R3) relates to how
we identify and collect test scenarios. As a change in the operating
environment can impact ADS continuously in the real world, we identify a test
scenario with a time span ST that is composed of a successive sequence of
scenes (see Equation 12), then collect test scenarios every time step (t) in
one execution (see an example in Figure 5). Such identification and collection
aim to depict the test scenarios over time in detail, but it increases the
number of collected test scenarios. Thus, it might result in low RCS % as one
execution by DeepQTest can observe at maximum one collision scenario.

We further analyzed the average realistic collision time (i.e., $CT_{RCS}$).
Based on $CT_{RCS}$ in Tables 7 and 8, $DeepQTest_{TTC}$ significantly
outperformed DeepCollision on all four roads, i.e., $DeepQTest_{TTC}$ took
less time to generate realistic scenarios that can lead to collisions than
DeepCollision. For example, one can observe from Table 7 that on R1,
DeepCollision took on average 18 seconds to find a realistic collision
scenario, while DeepQTest took on average 11.58 seconds (maximum 12.4 with
$DeepQTest_{TTC_{RD}}$, and minimum 9.92 with $DeepQTest_{TTC_{SD}}$).

Regarding the effectiveness of DeepQTest in terms of triggering realistic
collision scenarios, we found that, with the results on four roads under four
weather conditions, $DeepQTest_{TTC}$ identified on average 16 realistic
collision scenarios out of 20 runs (i.e., 16/20=80% per run), and it took on
average 10.58 seconds per realistic collision scenario.

Table 7:  Results of a number of test scenarios (#TS), a number/percentage of
realistic collision scenarios (#RCS/%), average time spent on observing each
realistic collision scenario ($CT_{RCS}$ seconds), a number/percentage of
unrealistic collision scenarios (#UNS/%), a number/percentage of realistic
non-collision scenarios (#RNS/%) and a number/percentage of unrealistic non-
collision scenarios (#RCS/%) achieved by $DeepQTest_{TTC}$ and DeepCollision.

DeepQTest vs. DeepCollision |  | Collision | Non-Collision |  | Collision | Non-Collision
---|---|---|---|---|---|---
#TS | #RCS/% | $CT_{RCS}$ | #UCS/% | #RNS/% | #UNS/% | #TS | #RCS/% | $CT_{RCS}$ | #UCS/% | #RNS/% | #UNS/%
| R1 | R2
$DeepQTest_{TTC_{RD}}$ | 770 | 16/2.08% | 12.40 | 0/0% | 754/97.92% | 0/0% | 614 | 15/2.44% | 15.67 | 0/0% | 599/97.56% | 0/0%
$DeepQTest_{TTC_{RN}}$ | 794 | 16/2.02% | 12.00 | 0/0% | 778/97.98% | 0/0% | 548 | 17/3.10% | 8.20 | 0/0% | 531/96.90% | 0/0%
$DeepQTest_{TTC_{SD}}$ | 662 | 16/2.42% | 9.92 | 0/0% | 646/97.58% | 0/0% | 602 | 16/2.66% | 11.14 | 0/0% | 586/97.34% | 0/0%
$DeepQTest_{TTC_{SN}}$ | 680 | 17/2.50% | 12.00 | 0/0% | 663/97.50% | 0/0% | 548 | 17/3.10% | 11.44 | 0/0% | 531/96.90% | 0/0%
DeepCollision | 3440 | 19/0.55% | 18.00 | 23/0.67% | 1389/40.38% | 2009/58.40% | 3440 | 13/0.38% | 18.00 | 9/0.26% | 3061/88.98% | 357/10.38%
| R3 | R4
$DeepQTest_{TTC_{RD}}$ | 770 | 14/1.82% | 8.67 | 0/0% | 756/98.18% | 0/0% | 662 | 17/2.57% | 9.60 | 0/0% | 645/97.43% | 0/0%
$DeepQTest_{TTC_{RN}}$ | 764 | 13/1.70% | 10.71 | 0/0% | 751/98.30% | 0/0% | 752 | 15/1.99% | 9.92 | 0/0% | 737/98.01% | 0/0%
$DeepQTest_{TTC_{SD}}$ | 524 | 18/3.44% | 7.50 | 0/0% | 506/96.56% | 0/0% | 536 | 17/3.17% | 9.00 | 0/0% | 519/96.83% | 0/0%
$DeepQTest_{TTC_{SN}}$ | 644 | 16/2.48% | 7.33 | 0/0% | 628/97.52% | 0/0% | 680 | 16/2.35% | 13.67 | 0/0% | 664/97.65% | 0/0%
DeepCollision | 4220 | 2/0.05% | 21.00 | 94/2.23% | 145/3.44% | 3979/94.29% | 4700 | 2/0.04% | 30.00 | 145/3.09% | 124/2.64% | 4429/94.23%

  * ∗

$R1$: $Road1$; $R2$: $Road2$; $R3$: $Road3$; $R4$: $Road4$. RD: Rainy Day; RN:
Rainy Night; SD: Sunny Day; SN: Sunny Night. #TS: Total Scenarios; RCS:
Realistic Collision Scenario; $CT_{RCS}$: realistic collision time for RCS,
UCS: Unrealistic Collision Scenario; RNS: Realistic Non-Collision Scenario,
UNS:
Unrealistic Non-Collision Scenario.

Table 8: Results of pair comparisons of $DeepQTest_{TTC}$ and DeepCollision
using Vargha and Delaney statistics ($\hat{A}_{12}$) and the Mann–Whitney U
test ($p$-value) in terms of a number/percentage of realistic collision
scenarios (#RCS/%), average realistic collision time ($CT_{RCS}$ seconds), a
number/percentage of unrealistic collision scenarios (#UNS/%), a
number/percentage of realistic non-collision scenarios (#RNS/%) and a
number/percentage of unrealistic non-collision scenarios (#RCS/%).

| Collision | Non-Collision |  |
---|---|---|---|---
$DeepQTest_{TTC}$ vs. | #RCS |  RCS % | $CT_{RCS}$ | #UCS |  UCS % | #RNS |  RNS % | #UNS |  RNS %
DeepCollision | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $P$
| $R1$ |  |
$DeepQTest_{TTC_{RD}}$ | 0.425 | 0.164 | 0.805 | <0.05 | 0.174 | <0.05 | 0.150 | <0.05 | 0.150 | <0.05 | 0.255× | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
$DeepQTest_{TTC_{RN}}$ | 0.425 | 0.164 | 0.805 | <0.05 | 0.188 | <0.05 | 0.150 | <0.05 | 0.150 | <0.05 | 0.285× | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
$DeepQTest_{TTC_{SD}}$ | 0.425 | 0.164 | 0.805 | <0.05 | 0.201 | <0.05 | 0.150 | <0.05 | 0.150 | <0.05 | 0.172× | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
$DeepQTest_{TTC_{SN}}$ | 0.450 | 0.310 | 0.854 | <0.05 | 0.130 | <0.05 | 0.150 | <0.05 | 0.150 | <0.05 | 0.203× | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
| $R2$ |  |
$DeepQTest_{TTC_{RD}}$ | 0.550 | 0.506 | 0.794 | <0.05 | 0.340 | <0.05 | 0.300 | <0.05 | 0.300 | <0.05 | 0.016× | <0.05 | 0.635 | 0.141 | 0.075 | <0.05 | 0.075 | <0.05
$DeepQTest_{TTC_{RN}}$ | 0.600 | 0.154 | 0.876 | <0.05 | 0.151 | <0.05 | 0.300 | <0.05 | 0.300 | <0.05 | 0.018× | <0.05 | 0.629 | 0.164 | 0.075 | <0.05 | 0.075 | <0.05
$DeepQTest_{TTC_{SD}}$ | 0.575 | 0.302 | 0.835 | <0.05 | 0.194 | <0.05 | 0.300 | <0.05 | 0.300 | <0.05 | 0.015× | <0.05 | 0.701 | <0.05 | 0.075 | <0.05 | 0.075 | <0.05
$DeepQTest_{TTC_{SN}}$ | 0.600 | 0.154 | 0.876 | <0.05 | 0.138 | <0.05 | 0.300 | <0.05 | 0.300 | <0.05 | 0.010× | <0.05 | 0.751 | <0.05 | 0.075 | <0.05 | 0.075 | <0.05
| $R3$ |  |
$DeepQTest_{TTC_{RD}}$ | 0.850 | <0.05 | 0.850 | <0.05 | 0.275 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05 | 0.800 | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
$DeepQTest_{TTC_{RN}}$ | 0.825 | <0.05 | 0.825 | <0.05 | 0.325 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05 | 0.723 | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
$DeepQTest_{TTC_{SD}}$ | 0.950 | <0.05 | 0.950 | <0.05 | 0.350 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05 | 0.738 | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
$DeepQTest_{TTC_{SN}}$ | 0.900 | <0.05 | 0.900 | <0.05 | 0.275 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05 | 0.723 | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
| $R4$ |  |
$DeepQTest_{TTC_{RD}}$ | 0.925 | <0.05 | 0.925 | <0.05 | 0.375 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05 | 0.850 | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
$DeepQTest_{TTC_{RN}}$ | 0.875 | <0.05 | 0.875 | <0.05 | 0.175 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05 | 0.900 | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
$DeepQTest_{TTC_{SD}}$ | 0.925 | <0.05 | 0.925 | <0.05 | 0.375 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05 | 0.805 | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05
$DeepQTest_{TTC_{SN}}$ | 0.900 | <0.05 | 0.900 | <0.05 | 0.275 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05 | 0.835 | <0.05 | 1.000 | <0.05 | 0.000 | <0.05 | 0.000 | <0.05

  * ∗

$R1$: $Road1$; $R2$: $Road2$; $R3$: $Road3$; $R4$: $Road4$. RD: Rainy Day; RN:
Rainy Night; SD: Sunny Day; SN: Sunny Night. RCS: Realistic Collision
Scenario;
UCS: Unrealistic Collision Scenario; RNS: Realistic Non-Collision Scenario,
UNS: Unrealistic Non-Collision Scenario. $p$ is p-value; a bold $\hat{A}_{12}$
with a $p<0.05$
implies that $\textit{DeepQTest}^{*}$ is significantly better than
DeepCollision, whereas a $\hat{A}_{12}$ decorated by symbol "×" indicates
$\textit{DeepQTest}^{*}$ performed significantly worse
than DeepCollision; a $p>0.5$ means no significant difference between
$\textit{DeepQTest}^{*}$ and DeepCollision. $\hat{A}_{12}$ magnitude:
negligible ($\hat{A}_{12}$ $\in$ (0.444, 0.556)), small
($\hat{A}_{12}$ $\in$ [0.556, 0.638) or (0.362, 0.444]), medium
($\hat{A}_{12}$ $\in$ [0.638, 0.714) or (0.286, 0.362]), large ($\hat{A}_{12}$
$\in$ [0.714, 1.0] or [0, 0.286]).

Moreover, we studied unrealistic scenarios generated by DeepCollision by
replaying them on the four roads. We found that the generation of unrealistic
scenarios is mainly caused by the four types of unrealistic environment
configurations, i.e., Unrealistic Time Changes (UTC), Unrealistic Weather
Changes (UWC), Violation of Safety Distance (VSD), and Overlapping Areas (OA).
Examples of each type are shown in Figure
LABEL:fig:RQ3.1_unrealistic_pictures. We further explain the four types of
unrealistic environment configurations as follows:

  * •

Unrealistic Time Changes (UTC) refers to the unrealistic manipulation of time
changes. As Figure LABEL:fig:u1 shows, the time was manipulated and suddenly
changed from the day (12 am) to the night (8 pm), which caused the AVUT to
collide with the pedestrian in front.

  * •

Unrealistic Weather Changes (UWC) refers to unrealistic weather changes. As
shown in Figure LABEL:fig:u5, an environment configuration action could
immediately shift the weather condition from sunny to foggy. As the foggy
weather condition affects the visibility of AVUT, such an instant change might
leave less time for AVUT to react and hence lead to collisions (e.g.,
colliding with the vehicle in the front in Figure LABEL:fig:u5). Considering
that the weather condition changes over a period of time, such a sudden change
is unrealistic.

  * •

Violation of Safety Distance (VSD) happens when obstacles (e.g., NPC vehicles,
pedestrians) are generated with initial positions violating the safety
distances of AVUT from the obstacles. For testing purposes, we could introduce
new obstacles into the driving environment. But such an introduction should be
in accord with real-world scenarios. For instance, it is impossible for a
truck to suddenly appear beside AVUT (Figure LABEL:fig:u9). In such a case,
AVUT did not have time to react and therefore collided with the truck. As
driving tasks on R3 and R4 need to go through a T-junction and then turn left
from a four-lane road to another four-lane road at the beginning (see Figure
4), we found that DeepCollision generated many collision scenarios by
introducing new obstacles when AVUT was turning left or entering the new lane.
This is a reason why most of the collision scenarios on R3 and R4 are
unrealistic (see Table 7).

  * •

Overlapping Areas (OA) is the case that an obstacle is generated in an area
overlapping the areas covered by the AVUT and the newly introduced obstacles
due to a lack of consideration of the volume of the new obstacles. Such
introductions will directly lead to collisions. Figure LABEL:fig:u11 is an
example of a collision caused by generating a truck in the same area of AVUT.
Such introductions of obstacles might mislead the approach by introducing
large obstacles such as trucks.

Furthermore, we compared $DeepQTest_{TTC}$ and DeepCollision in terms of
Diversity Metrics. DeepQTest achieved an overall better performance than
DeepCollision in terms of Diversity Metrics. Results of the pair-wise
comparison are shown in Table 9. In terms of $Div_{API}$, we found that
$DeepQTest_{TTC}$ achieved significantly better results than DeepCollision,
which indicates that, compared to DeepCollision, $DeepQTest_{TTC}$ could test
AVUT under more diverse combinations of environment configurations in one run.
In terms of $Div_{Scenario}$, $DeepQTest_{TTC}$ significantly outperformed
DeepCollision on R1 and R2. On R3 and R4, $DeepQTest_{TTC}$ is either
significantly better than or statistically equivalent to DeepCollision. The
results of $Div_{Scenario}$ indicate that $DeepQTest_{TTC}$ might have more
chance to test AVUT under more diverse test scenarios. Note that $Div_{API}$
measures the diversity of applying environment configurations, while
$Div_{Scenario}$ measures the diversity of test scenarios resulting from the
environment configurations.

Conclusion for RQ3: $DeepQTest_{TTC}$ outperformed DeepCollision in terms of
Realism Metrics and Diversity Metrics. Concretely, as for Realism Metrics,
$DeepQTest_{TTC}$ achieved a higher proportion of realistic scenarios among
all the generated ones, and it also generated more realistic collision
scenarios with less time. On the four roads under the four weather conditions,
$DeepQTest_{TTC}$ identified on average 16 realistic collision scenarios out
of 20 runs (i.e., 16/20=80% per run), and it took on average 10.58 seconds to
trigger a realistic collision scenario. In addition, DeepQTest is effective in
avoiding the generation of four kinds of unrealistic environment
configurations. Regarding Diversity Metrics, DeepQTest achieved an overall
better performance than DeepCollision in introducing diverse environment
configurations (i.e., $Div_{API}$) and generating diverse scenarios (i.e.,
$Div_{Scenario}$).

Table 9: Results of pair-wise comparisons of $DeepQTest_{TTC}$ and
DeepCollision in terms of Diversity Metrics using the Vargha and Delaney
statistics and the Mann–Whitney U test - RQ3

| $R1$ | $R2$ | $R3$ | $R4$
---|---|---|---|---
$DeepQTest_{TTC}$ vs. | $Div_{API}$ | $Div_{Scenario}$ | $Div_{API}$ | $Div_{Scenario}$ | $Div_{API}$ | $Div_{Scenario}$ | $Div_{API}$ | $Div_{Scenario}$
DeepCollision | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$ | $\hat{A}_{12}$ | $p$
$DeepQTest_{TTC_{RD}}$ | 0.880 | <0.05 | 0.909 | <0.05 | 0.750 | <0.05 | 0.739 | <0.05 | 0.786 | <0.05 | 0.767 | <0.05 | 0.761 | <0.05 | 0.570 | 0.455
$DeepQTest_{TTC_{RN}}$ | 0.839 | <0.05 | 0.877 | <0.05 | 0.730 | <0.05 | 0.820 | <0.05 | 0.774 | <0.05 | 0.749 | <0.05 | 0.838 | <0.05 | 0.762 | <0.05
$DeepQTest_{TTC_{SD}}$ | 0.870 | <0.05 | 0.811 | <0.05 | 0.805 | <0.05 | 0.860 | <0.05 | 0.785 | <0.05 | 0.728 | <0.05 | 0.719 | <0.05 | 0.453 | 0.615
$DeepQTest_{TTC_{SN}}$ | 0.795 | <0.05 | 0.844 | <0.05 | 0.844 | <0.05 | 0.799 | <0.05 | 0.746 | <0.05 | 0.679 | 0.054 | 0.765 | <0.05 | 0.556 | 0.549

  * ∗

$R1$: $Road1$; $R2$: $Road2$; $R3$: $Road3$; $R4$: $Road4$. RD: Rainy Day; RN:
Rainy Night; SD: Sunny Day; SN: Sunny Night. $p$ is p-value; a bold
$\hat{A}_{12}$ with a
$p<0.05$ implies that DeepQTest is significantly better than DeepCollision,
whereas a $\hat{A}_{12}$ decorated by symbol "×" indicates DeepQTest performed
significantly
worse than DeepCollision; a $p>0.5$ means no significant difference between
DeepQTest and DeepCollision. $\hat{A}_{12}$ magnitude: negligible
($\hat{A}_{12}$ $\in$ (0.444, 0.556)),
small ($\hat{A}_{12}$ $\in$ [0.556, 0.638) or (0.362, 0.444]), medium
($\hat{A}_{12}$ $\in$ [0.638, 0.714) or (0.286, 0.362]), large ($\hat{A}_{12}$
$\in$ [0.714, 1.0] or [0, 0.286]).

###  6.4 Threats to Validity

Internal Validity. Threats to internal validity are concerned about the design
factors that might have an impact on the conclusion. To migrate the potential
threat to the internal validity caused by MDP formulation and DQN parameter
settings, we trained the 12 DeepQTest models following identical state
encoding, action space, Q-network architecture, learning algorithm, training
details, and hyperparameter settings, to ensure fair comparison among them.
Another threat to internal validity is related to the potential faults within
our algorithm infrastructure. To control this threat, we used the open-source
machine learning framework, PyTorch [67], which has been widely applied and
tested in both academics and industry. Furthermore, we realized that the
hyperparameter tuning of DQN may have an influence on the performance of
DeepQTest, therefore, we followed the default hyperparameter settings from
Zhou [96] when training all of the 12 DeepQTest models. We understand that
tuning hyperparameters of DQN might improve the performance of DeepQTest,
which unfortunately cannot be covered in this paper because it requires
extensive and dedicated empirical studies.

External Validity. The threat is related to the currently applied subject
system and simulator and the possible generalization to other case studies. In
our evaluation, we conducted the empirical study with an industrial-scale ADS
(i.e., Apollo) and a commonly applied simulator (i.e., LGSVL). We understand
that conducting more case studies with different ADSs and simulators would
help to better evaluate and generalize DeepTest, and using our already
developed REST API endpoints, other ADSs, and simulators can be easily
integrated with DeepQTest with minimum effort. However, it is important to
mention that experiments on testing ADSs in the simulation are very
computationally expensive, which limited the number of case studies we used in
our experiment.

Construct Validity. Threat to construct validity concerns whether the metrics
for evaluation can precisely reflect the variables we want to measure in the
experiment. As discussed in Section 5.4, we present three types of metrics
(i.e., Safety and Comfort Metrics, Realism Metrics, and Diversity Metrics)
including 16 comparable metrics (e.g., TTC and #Collision) to measure the
effectiveness and efficiency of DeepQTest.

Conclusion Validity. The threat to conclusion validity is related to the use
of appropriate analytical methods and the reliability of conclusions. To draw
a reliable conclusion, we followed a rigorous procedure to collect the data
and employed statistical methods to analyze the collected data. Specifically,
20 independent runs of each experiment setting were performed to account for
randomness. In addition, following the guideline by Arcuri and Briand [5], we
performed pairwise comparisons with the Mann-Whitney U test and used the
Vargha-Delaney $\hat{A}_{12}$ metric for effect size.

###  6.5 Data Availability

To enable the reproducibility of our research findings, we provide the
replication package in our GitHub online
repository333https://github.com/Simula-COMPLEX/DeepQTest. The replication
package contains the following contents: 1) all related algorithms and source
code for conducting the experiment; 2) All the raw data for the experiment
results and analyses; and 3) The REST API endpoints for configuring the
environment.

##  7 Discussion

Recording and replaying scenarios for further diagnosis and analysis. Due to
the complexity and uncertainty of the operating environment, as well as the
complexity of the driving tasks, it is always very time-consuming to use
simulations to evaluate scenarios of an ADS testing approach. Thus, it is
necessary to record the generated scenarios to mitigate the cost for further
possible analysis and usage. For example, the recorded scenarios could be
utilized for supporting further diagnoses of ADSs, and can also be used for
regression testing.

To facilitate the recording and reusing process of test scenarios, we first
proposed a Domain-Specific Language (DSL) for scenario representation and
evaluation, named DeepScenario [59], which is based on the Driving Scenario
definition in Section 5. Additionally, to support automatically collecting and
replaying driving scenarios when testing ADSs by DeepQTest, we developed an
ScenarioCollector and an ScenarioRunner to easily collect and replay scenarios
using DeepQTest. With ScenarioCollector and DeepQTest, driving scenarios that
have been used for testing ADSs can be automatically recorded for further