# Critical concrete scenario generation using scenario-based falsification

Dhanoop Karunakaran1, Julie Stephany Berrio1, Stewart Worrall1, Eduardo Nebot1
1D.Karunakaran, J. S. Berrip, S. Worrall, E. Nebot are with the Australian
Centre for Field Robotics (ACFR) at the University of Sydney (NSW, Australia).
E-mails: {d.karunakaran, j.berrio, s.worrall<EMAIL_ADDRESS>
###### Abstract

Autonomous vehicles have the potential to lower the accident rate when
compared to human driving. Moreover, it is the driving force of the automated
vehicles’ rapid development over the last few years. In the higher Society of
Automotive Engineers (SAE) automation level, the vehicle’s and passengers’
safety responsibility is transferred from the driver to the automated system,
so thoroughly validating such a system is essential. Recently, academia and
industry have embraced scenario-based evaluation as the complementary approach
to road testing, reducing the overall testing effort required. It is essential
to determine the system’s flaws before deploying it on public roads as there
is no safety driver to guarantee the reliability of such a system. This paper
proposes a Reinforcement Learning (RL) based scenario-based falsification
method to search for a high-risk scenario in a pedestrian crossing traffic
situation. We define a scenario as risky when a system under testing (SUT)
does not satisfy the requirement. The reward function for our RL approach is
based on Intel’s Responsibility Sensitive Safety(RSS), Euclidean distance, and
distance to a potential collision. Code and videos are available online at
https://github.com/dkarunakaran/scenario_based_falsification.

##  I Introduction

J3016-2018 is an automotive standard from the Society of Automotive Engineers
(SAE) that defines the six levels of automation in vehicles[1]. In the higher
SAE automation levels, the passengers’ and vehicle’s safety accountability
transitions from the human driver to the autonomous system. So, evaluating the
SUT thoroughly before deploying it on public roads is essential. Traditional
testing methods are not suitable for evaluating the Highly Automated Vehicle
(HAV) as many challenges such as non-determinism in testing arise due to the
ML and probabilistic algorithms[2].

Figure 1: Experiment in a CARLA simulation: a pedestrian crossing the street
while the vehicle is driving.

Road testing is a common approach to evaluating HAV. However, the majority of
the driving task is low risk and of little value for testing[3]. Scenario-
based testing is a promising approach as it focuses only on meaningful
scenarios so that it can reduce the test effort required in safety evaluation
[4, 5, 6, 7]. There are three abstraction levels for a scenario
representation: functional, logical, and concrete scenario [8]. A functional
scenario is at the top of the abstraction level and is often represented by a
linguistic description of a scenario. The logical scenario defines different
parameters along with their range/distribution. Finally, the concrete scenario
specifies a fixed value from the range/distribution for each of the
parameters. This representation is used to describe test cases to evaluate the
SUT. In this paper, a risky or challenging scenario is referred to as a
dangerous concrete scenario.

There are two types of techniques in scenario-based safety evaluation: testing
and falsification [9]. Testing determines whether the SUT satisfies the safety
requirement by assessing the system over a finite set of concrete scenarios.
The falsification approach finds the system’s weakness by searching for a
critical scenario in which SUT violates the safety requirement. Even though
falsification does not create statistical safety arguments, it is useful for
identifying the systems’ weaknesses. This approach can complement the testing
techniques for a more reliable safety assessment of Highly Automated Vehicles.

This paper proposes a Reinforcement Learning (RL) based scenario-based
falsification method to search for critical scenarios in a pedestrian
crossing. This technique aims to search for a critical concrete scenario that
have a maximum reward in the explored space. In other words, the method
searches for the pedestrian trajectory that result in high-risk scenario or
even collision with a Vehicle Under Test (VUT). The method will encounter many
dangerous scenarios during the overall process, but it learns towards a
problematic scenario that can gain maximum reward in the explored space
through the reward function. Our method focuses on identifying the parameter
settings of a concrete scenario at the beginning of each episode. In contrast,
other RL-based approaches[10, 11] in the literature concentrate on identifying
the parameter settings at each time step to create a detailed trajectory.

In this experiment, we create the reward function for RL using Intel’s
Responsibility-Sensitive Safety (RSS) metric [12], the Euclidean distance of
pedestrian with respect to the ego-vehicle, and a cost that detects a
collision. The pedestrian crossing illustrated in Figure 1 is the selected
traffic situation to test our method. We have used five parameters, each with
an average number of twelve values. Even though we have chosen only five
parameters to represent the traffic situation’s search space/parameter space,
it can create approximately $12^{5}=248832$ possible concrete scenarios.
Adding more parameters increases the search space exponentially. The brute
force is an exhaustive search that usually takes many iterations to find the
critical scenario in an ample search space. This leads to spending more time
for testing a production vehicle. In [13], authors argued that Random search
methods such as Crude Monte Carlo (CMC) take longer to find rare scenarios or
edge cases. Thus, optimisation algorithms such as Reinforcement Learning (RL)
are suitable to achieve the desired outcome.

In a pedestrian crossing, a critical scenario is a collision between a vehicle
and a pedestrian. As shown in Equation 1, we have defined the safety
requirement in Signal temporal logic (STL). STL is mainly used for cyber-
physical systems (CPS) such as AV, and we use the STL requirement from the
work of [14].

$req=\square(\lnot\pi_{i,clash})$ (1)

where $\pi_{i,clash}=dist(i,ego)<\epsilon_{dist}$.

The requirement states that the ego vehicle should not collide with any
traffic participants. $i$ indicates a traffic participant such as a vehicle
and pedestrian that share the environment with the ego vehicle. The
$dist(i,ego)$ gives the Euclidean distance between traffic participant, $i$
and ego-vehicle. $\epsilon_{dist}$ is a minimum safe distance between two
parties required to avoid accidents.

The proposed method aims to search and find a challenging concrete scenario in
which SUT violates the safety requirement defined in Equation 1. The result
shows that our RL-based approach converges to a critical scenario with maximum
reward in the explored parameter space. In this paper, we are interested in
evaluating the SUT by finding a critical concrete scenario specific to the
system. It may or may not be critical to other systems.

##  II Related work

In this section, we present the existing literature related to scenario-based
falsification for assessing Automated Vehicles.

The authors in [15] parameterise the real-world scenarios and then extract
those scenario parameters to store them in a database. In the next step, they
fit a distribution to parameters for creating scenarios by sampling from the
fitted distribution. The generation of scenarios utilises Monte-Carlo
simulation and Importance Sampling. However, Monte-Carlo is a random search
and cannot guarantee finding edge cases even when employing Importance
Sampling to create more critical scenarios. In [16], Zhao Et.al. build a
statistical model of the SUT’s behaviour by processing the collected real-
world data. This work is focused on creating the model in a lane-following
traffic situation. As most real-world data is not challenging, they skewed the
model to create problematic scenarios. Nevertheless, one drawback of the
model-based approach is that the result is inaccurate if the model
approximation to real-world behaviour is incorrect.

Bayesian optimisation (BO) can be employed to optimise expensive-to-evaluate
functions or systems. The core idea in BO is the use of Bayes rule to train
the model to generate challenging scenarios. The scenario is created with
parameters ’$X$’ and ’$Y$’ representing input parameters and output,
respectively. Before the optimisation starts, a few data points are created by
randomly selecting input parameters $X$, from the search space and executing
them in a simulation. The model is initially fitted with random data points.
In the iteration stage, the acquisition function samples the search space and
selects the best $X$ based on the fitted model’s prediction. In the next step,
the simulation runs the generated scenario using input parameters provided by
the acquisition function and produces the actual output $Y$. These results are
added to the data points used to fit the model. This process repeats until the
end criteria is reached. In [17], the authors introduced the BO to find
challenging scenarios for evaluating HAVs. They use the learned model to find
the challenging scenarios once the optimisation process has found an
approximation of the model. However, BO has a theoretical limit on the number
of parameters it could be used.

In [18] Althoff et al. proposed an evolutionary algorithm (EA) to search for
critical concrete scenarios. The method enables searching for the optimal
global solution (critical concrete scenario) with respect to a fitness
function. The algorithm follows the process of natural selection, where the
fittest individuals are selected to generate a new generation of individuals.
The fitness function checks how fit the chosen individuals are. Similarly, the
function identifies the parent scenarios to create a new scenario. This
process repeats until a termination criteria is reached. Even though it can
generate diverse scenarios, sampling the edge cases from the learned
generative models remains unsolved since the edge cases have a low probability
of occurrence [19].

The underlying principle of combinatorial testing is that most failures are
the result of the interaction between a small number of parameters[20]. The
study from the [21] argued that there are six or fewer parameters that caused
the majority of the known failures. The most common type of combinatorial
approach is pairwise testing, which relies on the argument that the
interaction of two parameters causes many failures. [22] uses combinatorial
testing to evaluate the Deep Learning (DL) based object detection algorithm.
The author argued that DL-based systems are sensitive to variations of a few
parameters, and combinatorial testing is best suited for evaluating such a
system. In [23], the author introduced combinatorial testing to find the
critical scenario for assessing the Autonomous Emergency Braking (AEB) System.
The challenge with this approach is selecting the salient parameters, which in
most cases are hard to identify.

A model-free approach to creating challenging scenarios in the cyber-physical
system using simulated annealing is proposed in [24]. The simulated annealing
process comes from metallurgy, where heating and controlled cooling are used
to reduce defects. Similarly, the temperature parameter controls the
exploration and exploitation of the optimisation. During the initial stage,
the temperature value will be high, enabling the exploration of various
scenarios. Towards the end, the temperature value decreases, reducing the
exploration and moving towards the exploitation stage. It means that the
method started to choose the scenarios as possible critical scenarios. The
primary concerns with this approach are that the algorithm may take a long
time to complete.

Some work in the literature uses Reinforcement Learning (RL) to generate
challenging scenarios for the assessment of Autonomous Vehicles. In [10],
Koren presents an RL-based approach to find the most likely failure scenarios.
The method enables the learning of pedestrian trajectories that end up in a
collision with the SUT. Mainly, the experiment has three parameters:
acceleration of the pedestrian and two noise parameters representing the
uncertainty in the SUT’s estimated position and velocity. The result shows
that their method learns the parameter values required at each timestep to
create a collision trajectory. It indicates that the SUT fails to avoid the
collision with a pedestrian and requires further design changes before
releasing it on public roads. [11] uses Reinforcement Learning to search for
collision scenarios in an intersection. They use parameters for the ego-
vehicle (speed and position) and other vehicles (speed, position, and heading)
to create dangerous trajectories. Similar to [10], their method learns what
parameter values are required at each timestep to create challenging
scenarios. The previously mentioned RL approaches do not include the
parameters such as weather with the different presets. The main reason is that
these parameters do not vary in each timestep.

Neural architecture search (NAS) is a hyperparameter optimisation approach to
automate the design of a neural network for a specific task [25]. The authors
applied the policy gradient RL method called REINFORCE to teach the method to
predict the hyperparameters of the Neural Network for a defined task. We apply
this method to the falsification problem. In our work, the parameters are used
to generate a specific scenario. A RL algorithm learns the combination of
parameters that correspond to a critical concrete scenario. In [26], Xu et al.
uses NAS to search for the worst perception scenarios using a vehicle
detection algorithm within three publicly available perception datasets. The
main focus of their approach is to find critical perception scenarios. Our
work also applies NAS to search for critical scenarios but concentrates on
events in which the behaviour of the SUT does not meet the defined safety
requirement. We use an autonomous emergency braking (AEB) driving function as
SUT, which combines perception and decision-making components. Then focuses
more on the whole SUT’s behavioural aspect instead of one part of the entire
driving function.

##  III Background

This section introduces the concepts of reinforcement learning (reinforce),
CARLA simulator and responsibility sensitive safety metric used in proposed
method presented in this paper.

###  III-A REINFORCE

A reinforcement learning (RL) algorithm finds an optimal policy that maximizes
a reward by interacting with the environment that is modelled as a Markov
Decision Process (MDP) [27]. In MDP, all states satisfy the Markov property,
referring to the fact that the future depends on the current state only [27].
We can implement Reinforcement Learning(RL) in three ways: dynamic
programming, Monte-Carlo Methods, and Temporal-Difference Learning. REINFORCE
is a Monte-Carlo method [28]. An agent applies an action to the current state
and will then navigate to the goal state to compute the next reward. In
contrast, Temporal Difference Learning and Dynamic programming use
bootstrapping techniques to speed up the learning. REINFORCE is a policy
gradient algorithm that directly manipulates the policy to reach the optimal
policy that maximises the expected return. If we are using Neural Network (NN)
as the agent or controller, then the weights of the NN are the policy. The
learning process enables the weights’ update to find the optimal policy that
predicts the desired action given a state. The pseudo-code for the REINFORCE
[28] is shown is shown in Algorithm 1.

Result: Optimal policy $\pi_{\theta}$

while  _optimal policy $\pi_{\theta}$ is not found_ do

1\. Sample N trajectories using policy $\pi_{\theta}$;

2\. Evaluate the gradient of the objective function J using the below
expression:  $\nabla J(\theta)\approx\frac{1}{N}\sum_{\tau\in
N}\sum_{t=0}^{T-1}\nabla_{\theta}log\pi_{\theta}(a_{t},s_{t})R(\tau)$ (2)
Where N is the number of trajectories and R is the total return of a
trajectory;

3\. Update the policy parameters  $\theta=\theta+\alpha\nabla J(\theta)$ (3)

end while

Algorithm 1 Pseudocode for the REINFORCE

We use the cross-entropy loss representing the grad-log policy in the policy
gradient expression. It opens up the use of NN as the functional approximator
to describe the stochastic policy $\pi_{\theta}$.

###  III-B Responsibility Sensitive Safety (RSS)

Intel’s Mobileye proposed a metric that computes the minimum safe distance
required to keep the vehicle safe [12]. The ultimate goal of RSS as a formal
method is to guarantee that an agent will not cause an accident rather than to
ensure that an agent will not be involved in an accident. We can compute RSS
longitudinally and laterally based on the proposed formulas. In this paper, we
focus on the safe longitudinal distance. By definition, the safe longitudinal
distance $d_{min}$ is the minimum distance required for the ego vehicle to
stop in time if a vehicle in front brakes abruptly.

$d_{min}=\left[v_{r}\rho+\frac{1}{2}a_{max,a}\rho^{2}+\frac{(v_{r}+\rho
a_{max,a})^{2}}{2a_{min,b}}-\frac{v_{f}^{2}}{2a_{max,b}}\right]$ (4)

where $v_{r}$ and $v_{f}$ are the velocity of the agent vehicle and front
vehicle, respectively, $a_{min,b}$ is the minimum reasonable braking force of
the agent vehicle, $a_{max,b}$ is the maximum braking force of the front
vehicle, $a_{max,a}$ is the maximum acceleration of the front vehicle, and
$\rho$ is the agent vehicle response time.

In this work, we use RSS as one of the metrics to compute the reward function
that enables the RL agent’s learning.

###  III-C CARLA

CARLA is an open-source simulator for developing, training, and validating
autonomous urban driving systems[29]. It is a commonly used simulation tool
for academic research based on Unreal Engine to run the simulation. The
simulator provides Python and C++ APIs to control it. This tool allows the
complete control of digital assets such as static and dynamic actors to create
scenarios. CARLA supports many sensors available in the Highly Automated
Vehicle, making it suitable for developing autonomous systems. Furthermore,
the ROS bridge provided by CARLA enables the integration of the simulator with
any ROS-based systems.

##  IV Scenario-based falsification method

Our proposed method searches for a problematic concrete scenario in a
pedestrian crossing. Figure 2 illustrates the pedestrian crossing example. The
method enables the learning towards the critical scenario where the SUT fails
to meet the safety requirement. The following two subsections explain various
components of the falsification method and implementation details.

Figure 2: Pedestrian crossing intersection

###  IV-A Components

Figure 3 depicts the architecture of the proposed method. The detailed
description of each component is explained below.

Figure 3: This figure illustrates in detail the architecture of the proposed
method. The aim is to find challenging scenarios with the maximum return by
optimising the controller. Each action produced by the controller is a
combination of parameter values taken from the search space, finally the
weights of the controller are updated by the reward.

####  IV-A1 System Under Test (SUT)

In this paper we use CARLA’s emergency braking system as SUT. The system
controls the vehicle’s speed to avoid a collision when it detects an object
within its field of view. Safety evaluation against the requirement is done at
the end of the development lifecycle in the traditional engineering process.
At this stage of the process, a test engineer may not know the internal
specifications of the system. Similarly, the actual system specification is
unknown if a third party performs the evaluation. So, it is essential to
develop safety assessment methodologies that treat the SUT as a black-box
system.

Figure 4: Detection range of CARLA’s emergency braking system

####  IV-A2 Parameter space

This work uses parameter space as an alternative term for the logical
scenario. It contains the frequency distribution of each parameter. We have
considered five parameters in this experiment: offset from ego-vehicle’s
original position (ego-offset-pos), pedestrian acceleration (ped-accel),
pedestrian velocity (ped-vel), offset from the pedestrian orginal position
(ped-offset-pos), and weather. The list of parameters and their distribution
is shown in Table I. The CARLA simulator places the ego-vehicle and pedestrian
in a user defined position. In order to change the longitudinal position of
the ego-vehicle and pedestrian, we use the offset parameter. Carla has 15
weather settings, and we use 10 out of these values in the weather parameter.
Each value represents the weather preset. For instance, zero points to the
’Clear Noon’, whereas fourteen indicates ’Wet Sunset’.

The number of samples is an indicator of how many values are sampled from the
distribution of each parameter.

TABLE I: List of simulation parameters Parameter | Distribution | No. of samples
---|---|---
ego-offset-pos | $\mathcal{U}(1,10)m$ | 10
ped-accel | $\mathcal{U}(0,0.1)m/s^{2}$ | 10
ped-vel | $\mathcal{N}(1.46,\,0.24)m/s$ | 25
ped-offset-pos | $\mathcal{U}(3,4.5)m$ | 4
weather | $\mathcal{U}(0,14)$ | 10

####  IV-A3 State space and action space

The proposed method aims to generate the best parameter combination that
provides the highest return. The action contains the selected parameter
combination to create a scenario in simulation. The method learns how to
optimise the action so it contains the best parameter combination. In RL, the
agent provides the action given a state, but this experiment has no separate
states; instead, the previous action is given as the current state. The reason
for it is we only need to learn the right parameter combination, which does
not depend on any state.

There are five parameters in the search space, so action contains the value
taken from each parameter. So, action is a list of 5 parameter values.

####  IV-A4 Reward function

A reward function gives the score based on the state of the environment once
the agent applies the action. We compute three types of rewards in this
experiment. Firstly, we measure how many timesteps the Euclidean distance
between the vehicle and the pedestrian is less than the RSS distance. Such
timesteps are classified as high-risk, and we use notation,
$highrisk_{ts}^{RSS}$, to represent the total risky timesteps. We noted in the
experiment that the higher the number of risky timesteps, the more likely it
is to have a collision. So, this type of reward encourages the RL to search
for scenarios that produce more high-risk timesteps. We normalised the reward
to a small value range $new_{x}$ as we noted that a large value could affect
the controller’s ability to learn.

$new_{x}=(b-a)*\frac{x-min}{max-min}+a$ (5)

Where $x$ is the total number of high-risk timesteps, the minimum (min) value
is zero in this case, and the maximum(max) value is the total no. of timesteps
in an episode. The minimum value $a$ is -0.01 and the maximum value $b$ is
0.01. These values were found through experimentation, where a lower reward
produced an extensive exploration without converging quickly into the local
maxima/minima.

The second type of reward is based on the Euclidean distance between
pedestrian and ego-vehicle. At the end of every episode, we calculate the
final distance. When the distance gets smaller, it is more likely to have a
potential collision. So we compute the higher reward for smaller distances and
the lesser for longer distances. The value of the reward ranges between -0.01
and 0.01.

The collision is the ultimate scenario we need to find, and rewarding the
higher value for such scenarios can teach the controller to bias toward the
problematic scenarios. We wanted a higher value than 0.01, which is the
highest reward for other metrics. Also, a reasonable lesser reward such as a
way it can promote learning and avoid the quickly stuck into the local minima.
We choose 0.25 as the reward for collision through the trial and error method.

Equation 6 shows the reward function with all three types of rewards, and the
output of the reward function will be the sum of all three types.

$R=\Bigg{\\{}\begin{matrix}-0.01\ to\ 0.01&\ highrisk_{ts}^{RSS}\\\ -0.01\ to\
0.01&\ Euclidean\ distance\\\ 0.25&\ collision\\\ \end{matrix}$ (6)

####  IV-A5 Controller

The main task of the controller is to optimise the action so that it generates
a critical scenario with a maximum reward. The overall architecture enables
the learning using a policy gradient RL algorithm called REINFORCE. The
controller’s goal is to learn the policy that maximises the return in RL
terms. The controller in this paper is a Recurrent Neural Network (RNN), and
learning is enabled by updating its weights. We use the rewards to update the
weights of the RNN, in this process the RNN learns the optimal policy capable
to generate the critical scenario with a high reward.

Figure 5: The plot depicts the architecture of the controller. It has a input
layer, two hidden LSTM layers, and a final layer with 5 output. Each output
layer represents a different parameter.

As shown in Figure 5, the controller has an input layer, followed by two
hidden layers, and finally, the output layer contains five units. The whole
architecture is LSTM based, so the input layer expects sequential data. We
sequentially provide previous action data; an example is shown in Equation
7.The output layer has an output unit for each parameter. We would need to
increase the number of output units according to the parameter count.

$action,a=[3\ 0.051\ 1.178\ 3.5\ 8]$ (7)

The Neural Network (NN) training process in REINFORCE is slightly different
from standard NN applied in other tasks. In standard NN, one compute the
gradient of the loss function at every epoch and backpropagate the gradient to
update the network weights. In this case, we need the ground truth in a
supervised learning setting to compute the proper gradient using the loss
function. In contrast, model-free RL is a trial and error method and does not
have any ground truth to compute the gradient. The reward works as an
indicator of how good the predicted output is. The REINFORCE is a model-free
RL algorithm where the reward is multiplied by the gradient log of NN’s output
as shown in Equation 2. Based on Equation 3, we update the weights of the NN,
$\theta$, with the gradient expression computed in Equation 2. In this way, we
can teach the controller to learn toward the maximum reward.

We choose this value to balance exploration versus exploitation. In each
update, our method learns how to generate critical scenarios. If we have a
value lower than 25, the method learns fast, reducing exploration. In
contrast, higher values increase the exploration but take more time to
converge.

###  IV-B Implementation

Initially, the parameter space is created by sampling from the distribution
shown in Table I. The generated action contains five parameter values. The
method uses these values to construct a scenario in the CARLA simulator. In
this work, we focus on developing a critical case (collision with a
pedestrian) in a pedestrian crossing.

During the initial stage, the controller produces actions randomly. A later
stages, the controller learns the optimal policy to create an action that
leads to a challenging/risky scenario for the SUT. The final reward is
computed at the end of each episode based on the reward function. A high
reward applies to the action that leads to a failure (i.e. collision), and a
low reward denotes less risky scenarios.

We have set the controller to operate for 4000 episodes in this work. This
number depends on the amount of parameters and possible values they can take.

##  V Results

Our method searches for a problematic scenario by biasing the learning toward
such a scenario in which the emergency braking system violates the safety
requirement. We use ’do not collide’ as the safety requirement since collision
is a dangerous scenario. We set up the reward function so that common scenario
will have low rewards compared to the high rewards for risky scenarios. As
discussed in the controller and REINFORCE section, the highest reward can
influence the controller to learn how to generate potential collision
scenarios.

Figure 6: Average reward per episode, showing the overall learning of the
controller. After the 1500th episode, the approach learned the action to
obtain a maximum return in explored space. It indicates that the controller
has started to predict an action that maximises the return in explored space
around the 1500th episode. The reward is almost constant from the 2000th
episode onwards. At this stage, generated actions are similar.

(a) Challenging scenario

(b) Non-challenging scenario

Figure 7: The plot shows the Euclidean distance between pedestrian and ego-
vehicle over timesteps for challenging and non-challenging scenarios.
Euclidean distance closer to zero suggests that traffic participants end up in
a collision. We mark all the areas under less than one meter Euclidean
distance as collision zone. Figure 7(a) shows the challenging scenario learned
by the method that has the highest reward. In this scenario, the final
Euclidean distance finishes in a collision zone. It also depicts a more
significant number of high-risk timesteps towards the end, indicating many
high-risk timesteps can lead to collision scenarios. Figure 7(b) explains the
typical non-challenging scenario in the experiment. The Euclidean distance
does not touch the collision zone and implies that the vehicle stopped before
hitting the pedestrian. The figure also shows the safe scenario has a fewer
high-risk timestep.

As shown in Figure 6, the proposed method begins to converge after the 1500th
episode. The average reward remains almost constant from the 2000th episode
onwards. The controller learned to predict the correct action, creating
challenging cases with maximised reward. As shown in the figure, ultimately,
it converges into a critical scenario with maximum reward in explored space.

TABLE II: parameter values for a challenging and non-challenging scenario Parameter | Challenging | Non-challenging
---|---|---
ego-offset-pos | 9.0 $m$ | 7.0 $m$
ped-accel | 0.007 $m/s^{2}$ | 0.076 $m/s^{2}$
ped-vel | 1.237 $m/s$ | 1.808 $m/s$
ped-offset-pos | 3.5 $m$ | 3.5 $m$
weather | 8.0 | 8.0

The challenging scenario learned by the proposed method is depicted in Figure
7(a), and corresponding learned parameter values are shown in Table II. The
diagram illustrates the Euclidean distance between the ego-vehicle and
pedestrian. In the figure, we mark the area under one meter distance as a
collision zone. If the Euclidean distance is closer to zero, it implies that
the ego-vehicle ends up in a collision with the pedestrian. Figure 7(a) is a
challenging scenario as the Euclidean distance finishes at the collision zone.
We also show high-risk and low-risk timesteps in red and green, respectively.
This work defines a timestep as high-risk when the Euclidean distance is lower
than the minimum safe distance computed by RSS. Other timesteps are called
low-risk timesteps. The plot shows that the last part of the scenario has
numerous high-risk timesteps, indicating the vehicle did not reduce the speed
required to avoid the collision while the pedestrian was crossing. The reason
for the crash is that vehicle wasn’t aware of the pedestrian crossing
throughout the scenario due to the short field of view of the perception
system used by the emergency braking system. This example shows that method
finds the scenario in which the emergency braking system violates the safety
requirement as defined in Equation 1.

Figure 7(b) and parameter values in the non-challenging section of Table II
illustrates a non-challenging scenario. The Euclidean distance finishes six-
meter ahead of the collision zone, stating the vehicle sees the pedestrian at
the crossing and stops before hitting. All the generated scenarios have
similar initial ego-vehicle speeds, and the speed variation depends on whether
the SUT detects the pedestrian at the later stages. However, these variations
are not huge, so it is expected to have a few high-risk timesteps in the non-
challenging scenarios compared to the risky scenarios. In this case, a
pedestrian walked with higher acceleration than the pedestrian in the
challenging scenario. As a result, the speed of the pedestrian is higher and
reaches the centre of the road long before the vehicle arrives at the crossing
area. It made the pedestrian in the field of view of the vehicle, and the
emergency braking system activated to stop the vehicle before hitting the
pedestrian. As we can see in Table II, the velocity of the pedestrian in the
non-challenging scenario is higher than the problematic scenario that puts the
pedestrian in the field of view of the vehicle.

Figure 8: The plot illustrates the percentage of high-risk timesteps for
challenging and non-challenging scenario as shown in Figure 7. It is based on
the percentage of time where the system displays high-risk behaviour. The plot
shows that the problematic scenario has more high-risk timesteps than the non-
challenging scenario. We assume that risky time steps in the scenario’s
initial period may not be as impactful as the last part. Based on that
assumption, we have calculated the high-risk percentage from the second half.

We assume that high risk timesteps at the initial stage of the scenario may
not have as much impact as in the later stage. Because of this, we calculate
the high-risk percentage from the second half of the scenario. The bar chart
in Figure 8 shows that over $95\%$ of the time, SUT exhibits high-risk
behaviour in a challenging scenario(figure 7(a)), whereas it is less than
$15\%$ in the non-challenging scenario. As shown in the collision scenario
example, more disagreement with RSS and distance between both participants can
lead to collision.

Figure 9: The plot shows the Euclidean distance between vehicle and pedestrian
for 14 scenarios. The red coloured lines indicate collision scenarios, and the
green colour indicates the non-challenging scenarios.

In Figure 9, we have selected 14 scenarios to show their Euclidean distance
over time and which three of those scenarios end up in a collision zone.
During the learning process, the method encounters many dangerous scenarios,
and in the end, it optimises toward a risky scenario. We have shown three
critical scenarios in this plot, represented in red and 11 non-challenging
scenarios in green colour.

##  VI Discussion and Conclusion

This paper presents a scenario-based falsification method to generate a
critical concrete scenario to evaluate a system under test. We have defined
the safety requirement to find a concrete scenario in which SUT violates them.
The result shows that the method can search and detect such critical
scenarios. The method is not deterministic because the values of the
parameters are explored randomly in the early stage. Due to the initial random
search, each experiment has a different explored space. So, the values are not
repeatable in the subsequent experiment. However, it allows us to find diverse
parameter combinations for collision scenarios within a parameter space.

The parameter space is built in this work based on expert knowledge. But, it
is essential to represent the parameter space with real-world traffic
participant behaviour. In the extended work, we are building lane-change
scenario parameter space from real-world data and use this method to find
critical concrete scenarios from it

## Acknowledgment

This work has been funded by the Australian Centre for Field Robotics (ACFR),
University of Sydney and Insurance Australia Group (IAG) and iMOVE CRC and
supported by the Cooperative Research Centres program, an Australian
Government initiative.

## References

  * [1] S. Standard, “J3016-taxonomy and definitions for terms related to driving automation systems for on-road motor vehicles,” 2018.
  * [2] P. Koopman and M. Wagner, “Challenges in autonomous vehicle testing and validation,” _SAE International Journal of Transportation Safety_ , vol. 4, no. 1, pp. 15–24, 2016.
  * [3] Z. Xinxin, L. Fei, and W. Xiangbin, “Csg: Critical scenario generation from real traffic accidents,” in _2020 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, pp. 1330–1336.
  * [4] A. Pütz, A. Zlocki, J. Bock, and L. Eckstein, “System validation of highly automated vehicles with a database of relevant traffic scenarios,” _situations_ , vol. 1, pp. 19–22, 2017.
  * [5] H. Elrofai, D. Worm, and O. O. den Camp, “Scenario identification for validation of automated driving functions,” in _Advanced Microsystems for Automotive Applications 2016_. Springer, 2016, pp. 153–163.
  * [6] C. Amersbach and H. Winner, “Functional decomposition—a contribution to overcome the parameter space explosion during validation of highly automated driving,” _Traffic injury prevention_ , vol. 20, no. sup1, pp. S52–S57, 2019\.
  * [7] T. Ponn, M. Breitfuß, X. Yu, and F. Diermeyer, “Identification of challenging highway-scenarios for the safety validation of automated vehicles based on real driving data,” in _2020 Fifteenth International Conference on Ecological Vehicles and Renewable Energies (EVER)_. IEEE, 2020, pp. 1–10.
  * [8] T. Menzel, G. Bagschik, and M. Maurer, “Scenarios for development, test and validation of automated vehicles,” in _2018 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2018, pp. 1821–1827.
  * [9] S. Riedmaier, T. Ponn, D. Ludwig, B. Schick, and F. Diermeyer, “Survey on scenario-based safety assessment of automated vehicles,” _IEEE access_ , vol. 8, pp. 87 456–87 477, 2020.
  * [10] M. Koren, S. Alsaif, R. Lee, and M. J. Kochenderfer, “Adaptive stress testing for autonomous vehicles,” in _2018 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2018, pp. 1–7.
  * [11] Y. Liu, Q. Zhang, and D. Zhao, “A reinforcement learning benchmark for autonomous driving in intersection scenarios,” in _2021 IEEE Symposium Series on Computational Intelligence (SSCI)_. IEEE, 2021, pp. 1–8.
  * [12] S. Shalev-Shwartz, S. Shammah, and A. Shashua, “On a formal model of safe and scalable self-driving cars,” _CoRR_ , vol. abs/1708.06374, 2017. [Online]. Available: http://arxiv.org/abs/1708.06374
  * [13] D. Zhao, H. Lam, H. Peng, S. Bao, D. J. LeBlanc, K. Nobukawa, and C. S. Pan, “Accelerated evaluation of automated vehicles safety in lane-change scenarios based on importance sampling techniques,” _IEEE transactions on intelligent transportation systems_ , vol. 18, no. 3, pp. 595–607, 2016.
  * [14] C. E. Tuncali, G. Fainekos, D. Prokhorov, H. Ito, and J. Kapinski, “Requirements-driven test generation for autonomous vehicles with machine learning components,” _IEEE Transactions on Intelligent Vehicles_ , vol. 5, no. 2, pp. 265–280, 2019.
  * [15] E. de Gelder and J.-P. Paardekooper, “Assessment of automated driving systems using real-life scenarios,” in _2017 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2017, pp. 589–594.
  * [16] D. Zhao, X. Huang, H. Peng, H. Lam, and D. J. LeBlanc, “Accelerated evaluation of automated vehicles in car-following maneuvers,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 19, no. 3, pp. 733–744, 2017.
  * [17] B. Gangopadhyay, S. Khastgir, S. Dey, P. Dasgupta, G. Montana, and P. Jennings, “Identification of test cases for automated driving systems using bayesian optimization,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2019, pp. 1961–1967.
  * [18] M. Althoff and S. Lutz, “Automatic generation of safety-critical test scenarios for collision avoidance of road vehicles,” in _2018 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2018, pp. 1326–1333.
  * [19] W. Ding, B. Chen, M. Xu, and D. Zhao, “Learning to collide: An adaptive safety-critical scenarios generating method,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 2243–2250.
  * [20] D. R. Kuhn, R. N. Kacker, and Y. Lei, _Introduction to combinatorial testing_. CRC press, 2013.
  * [21] D. R. Kuhn, D. R. Wallace, and A. M. Gallo, “Software fault interactions and implications for software testing,” _IEEE transactions on software engineering_ , vol. 30, no. 6, pp. 418–421, 2004.
  * [22] C. E. Tuncali, “Search-based test generation for automated driving systems: From perception to control logic,” Ph.D. dissertation, Arizona State University, 2019.
  * [23] H. Felbinger, F. Klück, Y. Li, M. Nica, J. Tao, F. Wotawa, and M. Zimmermann, “Comparing two systematic approaches for testing automated driving functions,” in _2019 IEEE International Conference on Connected Vehicles and Expo (ICCVE)_. IEEE, 2019, pp. 1–6.
  * [24] A. Aerts, B. T. Minh, M. R. Mousavi, and M. A. Reniers, “Temporal logic falsification of cyber-physical systems: An input-signal-space optimization approach,” in _2018 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)_. IEEE, 2018, pp. 214–223.
  * [25] B. Zoph and Q. V. Le, “Neural architecture search with reinforcement learning,” _arXiv preprint arXiv:1611.01578_ , 2016.
  * [26] L. Xu, C. Zhang, Y. Liu, L. Wang, and L. Li, “Worst perception scenario search for autonomous driving,” in _2020 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2020, pp. 1702–1707.
  * [27] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [28] S. Levine, “Cs 294: Deep reinforcement learning,” 2017. [Online]. Available: \url{http://rail.eecs.berkeley.edu/deeprlcourse-fa17/}
  * [29] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “CARLA: An open urban driving simulator,” in _Proceedings of the 1st Annual Conference on Robot Learning_ , 2017, pp. 1–16.