# Finding Critical Scenarios for Automated Driving Systems: A Systematic
Literature Review

Xinhai Zhang, Jianbo Tao, Kaige Tan, Martin Törngren, José Manuel Gaspar
Sánchez, Muhammad Rusyadi Ramli, Xin Tao, Magnus Gyllenhammar, Franz Wotawa,
Naveen Mohan, Mihai Nica, and Hermann Felbinger  X. Zhang is with Sigma
Technology Consulting AB and the autonomous group of Scania CV AB in Sweden.
He was with the Mechatronics division of KTH for most of the time when the
paper was writing.
E-mail<EMAIL_ADDRESS>J. Tao, M. Nica and H. Felbinger are with AVL. K. Tan,
M. Törngren, J. Gaspar, M. R. Ramli, M. Gyllenhammar and N. Mohan are with the
Mechatronics division at KTH, Stockholm, Sweden X. Tao is with the Integrated
Transport Research Lab (ITRL) of KTH. M. Gyllenhammar is with Zenseact AB,
Gothenburg, Sweden F. Wotawa is with the CD Laboratory for Quality Assurance
Methodology for Autonomous Safety Critical Systems (QAMCAS), Inst. for
Software Technology, TU Graz, Graz, Austria

###### Abstract

Scenario-based approaches have been receiving a huge amount of attention in
research and engineering of automated driving systems. Due to the complexity
and uncertainty of the driving environment, and the complexity of the driving
task itself, the number of possible driving scenarios that an ADS or ADAS may
encounter is virtually infinite. Therefore it is essential to be able to
reason about the identification of scenarios and in particular critical ones
that may impose unacceptable risk if not considered. Critical scenarios are
particularly important to support design, verification and validation efforts,
and as a basis for a safety case. In this paper, we present the results of a
systematic literature review in the context of autonomous driving. The main
contributions are: (i) introducing a comprehensive taxonomy for critical
scenario identification methods; (ii) giving an overview of the state-of-the-
art research based on the taxonomy encompassing 86 papers between 2017 and
2020; and (iii) identifying open issues and directions for further research.
The provided taxonomy comprises three main perspectives encompassing the
problem definition (the why), the solution (the methods to derive scenarios),
and the assessment of the established scenarios. In addition, we discuss open
research issues considering the perspectives of coverage, practicability, and
scenario space explosion.

###### Index Terms:

Critical Scenario, Automated Driving, Literature Review.

##  1 Introduction

The long and winding road towards high levels of automated driving is
fascinating and highly representative of an ongoing technological paradigm
shift, see e.g., [1] and further references therein. The past years have seen
enormous amounts of funding going into a new automated driving ecosystem of
startups, new players and the existing automotive industry, [2], attracting in
excess of 80 billion US dollars during the period 2014 to 2017 [3], with
likely more than 100 billion US dollars invested the past decade, [4]. As a
result, impressive advances have been made and technology has matured.
However, the resulting complexity still poses formidable socio-technical
challenges for introducing automated driving on a larger scale.

One key challenge refers to reasoning about what can happen during automated
driving with relevance for safety engineering activities, from design to
assurance. The complexity and uncertainty of the driving environment, and the
complexity of the driving task itself, imply that the number of possible
scenarios that an Automated Driving Systems (ADS) or Advanced Driving-
Assistance Systems (ADAS) may encounter is virtually infinite. It is clear
that traditional mileage validation is infeasible for the safety validation of
ADS and ADAS, and moreover that ”driven miles” and disengagement reports are
far from sufficient for reasoning about risk, see e.g., [5, 4]. This has led
to a strong interest in virtual evaluation and verification, allowing for
”safe testing” and exploration, and potentially for cost-efficient assurance
based on the created evidence. However, this still begs the following
questions: Assuming you have a faithful simulation environment (a challenge on
its own), what tests are you to select (i.e. which are critical), how do you
derive them, and how do you reason about coverage and the completeness of the
safety analysis?

A typical approach to limit the potentially infinite scope of what an ADS may
encounter, including unknowns and uncertainty, is to limit the Operational
Design Domain (ODD), i.e., the operating conditions under which a given ADS or
one or more of its features are designed to function, [6]. This is indeed the
most common approach taken for current roll-outs of ADS at high levels of
automation. A complementary proposed approach is to attempt to define and
limit the behaviors to be encountered on the roads, see e.g., [7]. While this
may be very promising in the long term, it is hard to accomplish in the short
term given mixed-mode traffic (e.g., manually driven cars together with
vehicles at level 4 of automated driving), the complexity of automated
driving, and the need to agree on what represents a suitable risk level
(compromise between performance and safety). A third avenue would be to
leverage collaborating driving and smart infrastructure, however this requires
multi-stakeholder coordination, infrastructure investments and dealing with
new security related threats, thus complicating and delaying such an approach,
see e.g., [4].

In any case, it becomes essential to be able to reason about the
identification of scenarios - as ”the temporal development between several
scenes in a sequence of scenes”, [8]. Scenarios could be seen as ”test cases”
within an ODD. As such, scenarios are tangible and concrete and support ADS
design and evaluation, with the key challenge that the number of possible
driving scenarios that an AD or ADAS may encounter is virtually infinite, and
correspondingly for covering a given ODD. In particular, for the purpose of
supporting safety engineering, it becomes imperative how ”critical” scenarios
are identified, motivated and used. With ”critical” scenarios we refer to
situations which cause potential risk of harm (safety risks), that need
explicit consideration for risk investigation and potential risk reduction
measures (note: we summarize the key terms used in this paper in Section 2).

It is thus not surprising that scenario-based approaches are receiving a huge
amount of attention in research and engineering regarding the development,
verification and validation (V&V) of ADAS and ADS.

The area is very active in terms of research, standardization, and
engineering, encompassing, for example, scenario and ODD modeling, exchange
formats, methods for scenario generation, and scenario space exploration,
scenario catalogs and standards/guidelines, see e.g., [9, 10, 11, 12, 13, 14,
15].

During our research and work, we also discovered that many different
approaches are taken for how to reason about scenarios and critical scenarios,
ranging from different abstraction levels, assumptions, methods for scenario
generation, exploration, etc. Moreover, we were missing a way to classify the
different approaches we found, as a way to organize and compare them, and we
were not, to the best of our ability, able to find existing comprehensive
surveys on this topic.

This led us to formulate a systematic literature review focused on Critical
Scenario Identification (CSI) methods for ADS and ADAS. Our literature review
focuses on approaches to identify critical scenarios to support the
development of ADS and ADAS. This, for example, means that scenario modeling
languages like OpenScenario are out of the scope of the survey, other than
when used as part of a CSI method. The detailed scope of the literature review
is described in Section 3.1. Other directions of scenario-based methods are
briefly introduced and exemplified in Section 8.

The main contributions of the paper are as follows:

  * •

A comprehensive taxonomy of CSI methods for the development of ADS and ADAS
based on a systematic literature review.

  * •

An overview of the reviewed CSI methods based on the taxonomy.

  * •

Identified open issues and directions for further research.

The rest of the paper is organized as shown in Fig. 1. Section 2 introduces
key concepts, related standards and surveys of relevance for CSI methods for
ADS/ADAS systems. Section 3 describes the employed literature review
methodology, including the detailed scope, the research questions and the
processes to search for relevant primary studies, to analyze the selected
studies and to document the findings. The main result of this literature
review includes a taxonomy for the studied CSI methods (Section 4) and the
corresponding classification of the primary studies (Sections 5, 6 and 7).
Other related topics (but outside the scope of this literature review) are
identified and briefly introduced in Section 8. Before concluding the paper in
Section 10, Section 9 summarizes and discusses all the findings from this
systematic literature review, and accordingly suggests future work.

Figure 1: Graphical outline of the rest of the paper

##  2 Key Terminology and Related Surveys

This section introduces the background knowledge and key concepts/terminology
to facilitate the explanation of the taxonomy in Section 4. The definitions of
the terms are given in TABLE I based on the following standards: SAE J3016
[6], ISO 26262 [16], ISO/PAS 21448 [10], BSI/PAS 1883 [17], UL4600 [11] and
ISO 3450 series under development [18, 19, 20]. In TABLE I, definitions
without a citation refer to definitions proposed by the authors of this survey
to serve the explanation of the taxonomy. If a definition has multiple
citations, it means that the term has been defined in all those citations, and
the definition in this paper considers all those definitions.

TABLE I: Summary of Relevant Definitions Terminology | Definition
---|---
ADAS |  | The term ADAS (Advanced Driving-Assistance
---
System) is used to describe assistant
systems based on Level 3 or active safety
systems.
ADS |  | The term ADS (Automated Driving System) is
---
used specifically to describe a Level 3, 4, or 5
driving automation system.
Active Safety |  | Vehicle systems that sense and monitor
---
conditions inside and outside the vehicle
for the purpose of identifying perceived
present and potential dangers to the vehicle. [6]
Safety | The absence of unreasonable risk of harm.
FuSa |  | Functional Safety: The absence of unreasonable
---
risk due to hazards caused by malfunctioning
behavior of E/E systems [16]
SOTIF |  | Safety of the intended functionality: The absence
---
of unreasonable risk due to hazards caused by
the functional limitations of the intended
functionality [10]
Harm |  | Physical injury or damage to the health of
---
persons [16]
| Risk of
---
Harm
| Combination of the probability of occurrence of
---
harm and the severity of that harm [16]
| Hazardous
---
Event
| Combination of a hazard and an operational
---
situation [16]
Hazard |  | Potential source of harm caused by malfunction-
---
ing behavior of the implementation of a vehicle-
level function [16]
Failure |  | Termination of an intended behavior of a system
---
due to a fault manifestation [16]
Fault |  | Abnormal condition that can cause a system to
---
fail [16]
| Unintended
---
Behavior
| Behavior going beyond the intended behavior of
---
a system due to functional insufficiencies
| Functional
---
Insufficiency
| Incomplete specification or insufficient imple-
---
mentation of the intended functionality with an
unreasonable level of risk [10]
| Triggering
---
Condition
| Specific conditions of a scenario that serve as an
---
initiator for a subsequent system reaction,
possibly leading to a hazardous behavior [10]
| Safety-Critical
---
Operational
Situation
| Traffic conditions (within the ODD), where a
---
hazard is very likely to propagate to a harm
[16, 10, 21]
| Influential
---
(Scenario)
Factors
| A parameterized scenario factor (e.g., sun
---
angle or road friction), which may affect
the performance of at least one AD function.
Scenario |  | The temporal development between several
---
scenes in a sequence of scenes. [8]
Scene |  | A snapshot of the environment including the
---
scenery and movable objects, as well as all
actors’ and observers’ self-representations, and
the relationships among those entities. [8]
| Critical
---
Scenario
| Scenarios that cause potential risks of harm,
---
which need explicit consideration for risk inves-
tigation and potential mitigation measures
CSI Method |  | Methods to find triggering conditions, safety-
---
critical operational situations, or combinations
of the two that will lead to harm
ODD |  | Operational Design Domain: Operating condi-
---
tions under which a given ADS or AD feature
thereof is specifically designed to function [6].
It contains the set of all the influential factors
and the possible combinations of these factors.
| Functional
---
Scenario
| Scenario space representation on a semantic or
---
a high level of abstraction via linguistic
notations [22]
| Logical
---
Scenario
| Scenario space representation on a state-space
---
level with parameter ranges [22]
| Concrete
---
Scenario
| A concretization of a logical scenario with
---
concrete parameter values [22]

###  2.1 ADS and ADAS

We adopt relevant ADAS and ADS terminology from the SAE J3016(TM) ”Standard
Road Motor Vehicle Driving Automation System Classification and Definition”
[6].

ADS: In J3016, the term ADS (Automated Driving System) is used specifically to
describe a highly-automated driving system, which can perform the entire
Dynamic Driving Task (DDT) on a sustained basis without human supervision.
[6]. Figure 2 shows the main functions of ADS according Autoware111Autoware:
https://www.autoware.auto/ [23, 24], Apollo222Apollo:
https://apollo.auto/developer.html [25] and Elektrobit open
robinos333Elektrobit open robinos:
https://www.elektrobit.com/products/automated-driving/eb-robinos/ [26].

ADAS: The term “Advanced Driver Assistance Systems” (ADAS) is defined in J3016
[6] to describe a broad range of features. ADAS system also includes the
active safety systems, which are excluded from the scope of this driving
automation taxonomy because they do not perform part or all of the DDT on a
sustained basis, but rather provide momentary intervention during potentially
hazardous situations, such as lane keeping assistance (LKA) systems and
automatic emergency braking (AEB) systems.

In our paper, we used the definition of levels of automation from the SAE
J3016 [6] to classified the systems in this survey into L3+ (with a human
driver), L3- (without a human driver), and active safety system (no continues
control of the vehicle). Detailed definitions of these three classes are given
in Section 5.1.1.

Figure 2: Nominal AD functions according to Autoware[24], Apollo[25] and
Elektrobit open robinos[26]

###  2.2 Safety and the Sources of Harm

In this paper, safety is considered as a combination of Functional Safety
(FuSa) [16] and the Safety Of The Intended Functionality (SOTIF) [10] within a
specified operational design domain (ODD) [6]. According to ISO 26262 [16] and
ISO/PAS 21448 [10], FuSa and SOTIF have the goal to mitigate residual risk
associated with different sources of harm. Extending the discussion in [27],
Fig. 3 illustrates the potential sources of harm considered in this paper.

Figure 3: Sources of harm according to ISO 26262, ISO/PAS 21448 and SAE J3016

FuSa considers the malfunctioning behavior caused by systematic faults and
random hardware faults. It assumes that the design intent of the system is
safe. In other words, it assumes that if the vehicle implementation perfectly
follows its specification, the vehicle is safe. However, this assumption is
not always valid for ADS for the following two reasons:

Reason 1: Due to the openness of the driving environment, the ADS may be
exposed to a nearly infinite set of environmental conditions. Therefore the
specifications of AD functions may not be sufficient (i.e., not all the
conditions are completely considered, e.g., an incomplete traffic sign beside
the road). Consequently, some unidentified conditions may lead to safety
problems.

Reason 2: Deviation from the intended functionality can also stem from
inevitable performance limitations of some advanced functions due to the
complexity or the inductive nature (e.g., learning-based methods) of the
employed algorithm.

To this end, SOTIF complements FuSa by considering the malfunctioning
behaviors stemming from functional inefficiencies, which include the
aforementioned insufficient specifications and performance limitations. As
shown in Fig. 3, a functional insufficiency will lead to an unintended
behavior of that function (e.g., mis-detection of the front vehicle) under a
certain triggering condition (e.g., glare). If this unintended behavior is not
resolved by the resilience of the downstream functions (e.g., object tracking
and sensor fusion) [21], it may propagate to a vehicle level hazard (e.g., a
failure to detect a pedestrian implying that braking is not initiated in
time).

A hazard may propagate to harm if it occurs in a safety-critical operational
situation (e.g., the ego vehicle is running on a highway with a small distance
to the front vehicle). For ADS with lower levels of automation, this
propagation also depends on the reaction of the involved person (e.g., the
driver of an L2 ADS).

Note that the propagation from an unintended behavior to a vehicle-level
hazard is not necessarily deterministic owing to the resilience of the system.
For example, if the camera-based vehicle detection function fails to detect
the front vehicle at one frame because of a sudden glare, this unintended
behavior will very likely be fixed by the downstream object tracking function.
In addition, hazards stemming from the triggering conditions may not lead to a
harm without a safety-critical operational situation.

Another source of harm considered in [27] is the misbehavior of other traffic
participants. In our framework, an ADS should be able to tolerate a certain
level of misbehavior of other traffic participants. The set of all tolerable
behaviors should be covered in the (functional) ODD. If an ADS could not
survive a tolerable misbehavior of another traffic participant, it will be
considered as a functional insufficiency. 444If this misbehavior is explicitly
specified in the logical scenario, it will be considered as a performance
limitation, otherwise it will be considered as a specification insufficiency.
If the other traffic participants behave beyond the ODD and cause a safety
problem, it will be considered as a hazardous ODD exit. However, as far as the
authors know, there is no method to completely define an ODD, therefore the
boundary between functional insufficiency and ODD exit might be vague.

###  2.3 Scenarios

The term ”scenario-based testing” was first applied to the development of
software systems. [28] A standardized definition of the term scenario in the
context of verification and validation of automated vehicles is introduced in
ISO/PAS 21448 [10].

####  2.3.1 Scenario, Scene and ODD

In this paper, the definitions of scenario and scene are directly reused from
[8] as follows.

Scenario: “A scenario describes the temporal development between several
scenes in a sequence of scenes. Every scenario starts with an initial scene.
Actions & events as well as goals and values may be specified to characterize
this temporal development in a scenario. Other than a scene, a scenario spans
a certain amount of time.” [8] As assumed in [10] and illustrated in Fig. 3, a
scenario can be described by a set of influential factors.

Scene: “A scene describes a snapshot of the environment including the scenery
and movable objects, as well as all actors’ and observers’ self-
representations, and the relationships among those entities. Only a scene
representation in a simulated world can be all-encompassing (objective scene,
ground truth). In the real world it is incomplete, incorrect, uncertain, and
from one or several observers’ points of view (subjective scene).” [8]

All the relevant scenarios that conform to the same scenario description
compose a scenario space. An important scenario space defined in [6] is the
Operational Design Domain (ODD), within which, the ego vehicle is supposed to
drive safely. The definition of ODD is as follows:

ODD: “Operating conditions under which a given driving automation system or
feature thereof is specifically designed to function, including, but not
limited to, environmental, geographical, and time-of-day restrictions, and/or
the requisite presence or absence of certain traffic or roadway
characteristics”.[6] ODD essentially defines the operating environment, for
which an ADS is designed.

The Pegasus project [29] presented a 6-layer scenario description model to
categorize the influential factors for scenario and ODD description. The 6
layers are introduced in TABLE II. To facilitate the discussion in later
sections, an additional layer L0 (Internal Ego-vehicle) is added to describe
the internal states of the ego-vehicle and the behavior of the driver.
Detailed description of these layers can be found in TABLE II.

TABLE II: The 6-layer scenario description model [30] Layer | Name | Description and Examples
---|---|---
L0 | Internal ego-vehicle |  | Internal states of the other systems of the ego-vehicle
---
other than the SOI + the states or behavior of the driver
L1 | Road-level | Road topology, road surface, road elevation (slope, waviness)
L2 | Traffic infrastructure | Including traffic rules
L3 | Temporary manipulation of L1 and L2 | Geometry, topology (overlaid)
L4 | Objects |  | Moving objects (traffic-related objects, e.g. vehicles, pedestrians,
---
movement relative to the vehicle being measured)
L5 | Environment | Weather, wind (may affect control), temperature (may affect camera)
L6 | Communication | V2X information, digital map

####  2.3.2 Scenario Representation

Menzel et al. [22] classified scenario representations into three levels of
abstraction, namely functional scenario, logical scenario and concrete
scenario. Functional scenario and logical scenario describe scenario spaces on
two different levels of abstraction, while concrete scenario describes a
particular scenario.

Functional scenario: A scenario space representation on a semantic level with
linguistic scenario notations. [22] ”The vocabulary used for the description
of functional scenarios is specific for the use case and the domain and can
feature different levels of detail.” [22]

Logical scenario: A scenario space representation on a state-space level with
parameter ranges in the state space. Each parameter correlates to one
influential factor. The parameter ranges can optionally be specified with
probability distributions. A logical scenario includes a formal notation of
the scenario space. [22] Additionally, ”the relations of the parameter ranges
can optionally be specified with the help of correlations or numeric
conditions.” [22] In this paper, it is assumed that a logical scenario cannot
fully reflect its corresponding functional scenario since relevant parameters
cannot be completely listed.

Concrete scenario: A parameterized representation of a particular scenario.
Each concrete scenario is an instantiation of a logical scenario, with a
concrete value for each parameter. [22]

According to a concrete scenario, an executable scenario can be constructed,
which can be either a simulation model or a real test. An executable scene
refers to an image from a camera or a point cloud from a LiDAR.

In the rest of this paper, functional scenario, logical scenario and concrete
scenario are also used to denote a scenario space or a scenario represented
with the corresponding levels of abstraction. Fig. 4 depicts the transitions
between the three levels of abstraction, which are defined as follows:

Figure 4: Relationships between scenario description at different levels of
abstraction

Reasoning: This refers to the methods that reason (inductively or deductively)
about critical functional scenarios based on knowledge, experience, and
information described in the ODD.

Formalization: Using input from the ODD definition, a functional scenario will
be formalized and parameterized to a logical scenario with all the parameter
definition and their value ranges. In this paper, even though the formalized
logical scenario contains more information than its functional scenario, it
represents a smaller scenario space since not all the influential factors may
have been identified and considered.

Instantiation: In this phase sampling or optimization approaches are used to
instantiate the concrete scenario by naive search or guided search methods.

Construction: The concrete scenarios will be converted into executable
scenarios with the help of formats like OpenX (OpenDRIVE, OpenSCENARIO)[9],
for use in simulators.

Since an ODD is also a scenario space, ODD definitions can also be classified
as functional ODD or logical ODD, explained as follows:

  * •

Functional ODD: It describes the entire intended ODD on a high level of
abstraction. e.g. a particular highway in Stockholm in sunny weather.

  * •

Logical ODD: It refers to a parameterized ODD description. It can support the
design of the ODD exit detection algorithm. It can also support the
formalization of functional scenarios.

Similar as the relation between a functional scenario and its logical
scenario, functional ODD represents a bigger scenario space. The misalignment
between the functional ODD and the logical ODD constitutes a major source of
specification insufficiency. In the rest of this paper, ODD refers to the
functional ODD. In Fig. 4, it is the logical ODD that supports the
formalization of a functional scenario.

###  2.4 Critical Scenarios

The concept of a critical scenario is defined in a number of (different) ways
in the research literature. Some papers also use related terms (sometimes used
as direct synonyms), such as edge case or corner case. This section lists the
standard definitions of these synonyms and provides our definition of critical
scenario.

Corner case and Edge case: In many cases, corner cases and edge cases are
related terms and are often used as synonyms. The probability of occurrence is
the most significant difference between them. Corner cases are combinations of
normal operational parameters and a rare or unusual condition [10]. [31]
states that not all edge cases are corner cases, and vice versa. Only corner
cases with a special combination of conditions that are both uncommon and
novel are considered edge cases. According to [31] the definition of rare is
relative, and it generally refers to situations or conditions that occur
frequently enough in a fully deployed fleet to be a problem, but are not
documented during the design or requirements process.

Critical scenario: In this survey, critical scenarios are defined as relevant
scenarios for system design, safety analysis, verification or validation, with
a potential risk of harm. In ISO 26262 [16], risk of harm is defined based on
the likelihood of the scenario and the severity of the consequential harm. In
this survey, we consider critical scenarios as all the scenarios that may lead
to harm. As shown in Fig. 3, a critical scenario may contain a triggering
condition and a safety-critical operational situation.

###  2.5 Critical Scenario Identification Methods

One major goal of ISO/PAS 21448 [10] is to identify unknown critical
scenarios, and thereafter make them safe. Triggering conditions and safety-
critical operational situations are two major components of a critical
scenario within an ODD. Therefore, an unknown critical scenario can stem from
either an unknown triggering condition or an unknown safety-critical
operational situation. In addition, Annex B2 of ISO/PAS 21448 [10] further
assumes that a scenario condition/situation can be modeled as a combination of
several influential scenario factors (e.g., heavy rain, glare, slippery road
surface, a sudden cut-in of another vehicle, etc.). Under this assumption, an
unknown critical scenario can be attributed to either an unknown scenario
factor or an unknown combination of known scenario factors.

Figure 5: Sources of unknown critical scenarios

To this end, Critical Scenario Identification (CSI) Methods are defined as the
methods to find triggering conditions, safety-critical operational situations,
or combinations of the two that will lead to harm. An ODD definition is
considered as the input of a CSI method to delimitate the scenario space.

As shown in Fig. 6, the identified critical scenarios will support the
refinement of the automated driving functions to make the ADS safer. They may
also help to complete the ODD definition, especially when an identified
critical scenario points to an unconsidered aspect of the ODD definition.
Meanwhile, functional refinement may also lead to an ODD change, which will
initiate a new CSI process in the next iteration.

Figure 6: An iterative process to improve the safety of the intended
functionality

###  2.6 Related Survey Papers

While there is a vast amount of literature on various aspects of CSI methods,
there are much fewer related survey papers. Other related topics, although
outside the scope of this review, are briefly introduced in Section 8.

According to our literature search, to the best of our knowledge, related
relevant survey papers are [32] and [33]. Neurohr et al. [32] reviewed and
analyzed the literature about the scenario-based testing method for automated
vehicles. The authors presented fundamental arguments, principles and
assumptions of the scenario-based approach. They also proposed a generic
framework (from scenario elicitation to test evaluation) for scenario-based
testing and analyzed in detail the individual steps based on the reviewed
articles. As a result, they presented various considerations for using and
implementing scenario-based testing to support automated vehicle homologation.

Riedmaier et al. [33] performed a survey of scenario-based approaches for
safety assessment of automated vehicles. The authors provided an overview of
various approaches. They also developed a taxonomy for the scenario-based
approach and compared the summarized methods with each other. In the end, this
paper integrated the formal verification with the scenario-based approach as
an alternative concept.

The differences between this paper and those two survey papers are:

  * •

This paper is dedicated to CSI methods, which is a subset of the focus of the
other papers’ scenario-based methods.

  * •

This paper provides a systematic literature review.

  * •

This paper provides a taxonomy for critical scenarios identification
approaches.

##  3 Literature Review Methodology

This literature review follows the guidelines proposed by Keele [34], which
divides the whole literature review process into three stages: planning,
conducting and reporting. Based on this guideline, our literature review
protocol is illustrated in Fig. 7 and detailed in the rest of this section.

Figure 7: Overview of the literature review process

###  3.1 Planning the Review

This section describes the research questions and the planned scope of this
literature review.

As discussed in the previous sections, the goal of this paper is to propose a
framework to categorize and analyze the CSI methods for ADS and ADAS. Based on
this objective, the following research questions are derived.

  1. RQ1:

What would be a taxonomy that allows to systematically categorize and compare
state-of-the-art CSI methods for ADS and ADAS?

  2. RQ2:

What is the current status of CSI methods research with respect to this
taxonomy?

  3. RQ3:

What are the remaining problems and challenges for further investigation?

The taxonomy in RQ1 can provide a systematic structure of common
characteristics to enable the classification and comparison of different CSI
methods. With this taxonomy, further researchers or engineers can easily
pinpoint a CSI method on the big picture, and thereby understand its strength
and limitations. The answer to RQ2 presents the state of the art of CSI
methods. It can also help new researchers or engineers in this field have a
quick and comprehensive understanding of these methods. RQ3 tries to identify
the further directions of this research topic.

To clarify the scope of this literature review, as suggested in [34], the
research questions are broken down into individual facets (Population,
Intervention, Comparison, Outcomes and Context - PICOC [35]) as:

  * •

Population: Software-intensive ADS or ADAS;

  * •

Intervention: Approaches applied during development time to identify Critical
scenarios;

  * •

Comparison: Not applicable;

  * •

Outcomes: Improved safety;

  * •

Context: Peer-reviewed publications from academia and industry.

The scope of this literature review can be further narrowed down by clarifying
the definitions of scenario and criticality. As discussed in Section 2.3.1,
the definition of a scenario should follow the one given in [8], and cover at
least one layer of the 6-layer model[30]. The included studies must
distinguish critical scenarios from other scenarios. General-purpose scenario
modeling methods, such as [36], are excluded if they do not consider the
identification or generation of critical scenarios. For a similar reason, we
also excluded general-purpose data augmentation approaches for training
machine learning models (e.g., [37, 38]).

In addition, since CSI methods play an important role for SOTIF [10], this
literature review only considers the studies published after the initiation of
the SOTIF standard, ISO/PAS 21448 (i.e. 2017).

To this end, the following inclusion and exclusion criteria are formulated.
The included papers should satisfy all the inclusion criteria, and should not
be covered by any of the exclusion criteria.

  1. I1:

Studies describing approaches to identify critical scenarios for ADS or ADAS
during development time;

  2. I2:

The scenario considered in the study should contain environmental aspects,
i.e. content covered by the 6-layer model;

  3. I3:

The identified critical scenarios should serve the development of a software
intensive system;

  4. I4:

Studies published between January 2017 to August 2020;

  5. I5:

Peer-reviewed studies written in English, and available in full text;

  6. E1:

Papers with main focus on cyber security;

  7. E2:

Approaches to identify misuse scenarios;

  8. E3:

On-line methods, e.g., online risk assessment;

  9. E4:

Approaches to identify critical scenarios for a hardware component, e.g.,
radar or LiDAR;

  10. E5:

Papers focusing on how to model scenarios and how to identify influential
factors;

  11. E6:

Papers introducing a framework for scenario-based methodology instead of a
particular method to identify critical scenarios;

###  3.2 Conducting the review

As illustrated in Fig. 7, to answer the research questions, three research
tasks were conducted. This section provides the details of these three
research tasks.

####  3.2.1 Literature search and selection

The primary studies for this literature review are collected through an
iterative process with automatic search and snowballing as shown in Fig. 8.
This section describes the details of how we conducted each stage.

Figure 8: The stages to collect the primary studies. The numbers on the arrows
indicate the numbers of studies given to the next stage

Stage 1: A comprehensive initial search string can reduce the number of
iterations to determine the final search string as described in Stage 3. To
better define the initial search strings, an initial set of relevant studies
was gathered from two sources. The first source was publications from recent
relevant research projects including AutoDrive, Prystine, Pegasus, Enable-S3
and AdaptIVe. The second source are the relevant papers included in the two
relevant survey papers [33, 32] introduced in Section 2.6. The initial set
contains 151 potentially relevant studies. After being filtered by the
inclusion and exclusion criteria, 49 studies remained.

Stages 2 and 6: To filter a given set of potentially relevant studies, we
reviewed the title abstract and author keywords of each paper with respect to
the inclusion and exclusion criteria defined in Section 3.1. After reviewing,
each paper was labelled as either ”included”, ”excluded” (together with the
violated criterion) or ”unclear”. Unclear studies were further checked by
going through their introduction, conclusion and some other parts. When
necessary, a discussion among multiple researchers would be conducted to
determine the inclusion of an unclear study.

Stage 3: We performed an automatic literature search with the same search
string on different databases.

To cover as many relevant studies as possible, we conducted an automatic
search on the five major electronic databases on computer science, electronic
engineering and automotive technology, namely: IEEE Xplore Digital Library,
ACM Digital Library, Scopus, ScienceDirect and SAE Mobilus.

According to the PICOC analysis presented in Section 3.1, the search string is
designed as:

$\textnormal{Search String}=\$AD\textbf{ AND }\$CS\textbf{ AND
}\textnormal{"safe*"}$

where $\$AD$ denotes the identified synonyms of automated driving, and $\$CS$
represents the synonyms of critical scenario or CSI methods. These synonyms
are listed in Table III. $\$AD$ and ”safe*”are searched within the whole text,
and $\$CS$ is searched only in title, abstract and author keywords. After
stage 7, new synonyms of $\$AD$ and $\$CS$ could be identified to extend the
search string. This process was iterated three times until no more synonyms
could be found. Table III lists the final set of all the identified synonyms.
The search result from each database is illustrated in the second column
(Found) of Table IV.

TABLE III: Synonyms in $\$AD$ and $\$CS$ | Synonyms
---|---
$\$AD$ |  |  ((automated OR autonomous OR intelligent) AND
---
(vehicle OR driving)) OR ”self-driving” OR ADAS
$\$CS$ |  |  ((critical OR challenging OR risky OR “high-risk” OR
---
hazardous OR complex OR ”safety-relevant” OR
accident) AND scenario) OR ”corner case” OR
”falsification” OR ((stress OR adversarial) AND test*)
OR ”test* scenario” OR ”test case”
TABLE IV: Literature search and selection result before snowballing Database | Found | Selected | Unclear | Included
---|---|---|---|---
Initial set | 151 | 49 | 0 | 49
ScienceDirect | 29 | 3 | 2 | 4
Scopus | 261 | 61 | 27 | 67
IEEE | 311 | 35 | 10 | 32
ACM | 112 | 1 | 6 | 3
SAE | 152 | 14 | 19 | 18
Total | Found: 929 | Included: 126

Stage 4: Compared to stages 2 and 6, stage 4 had a much larger input set. To
share the workload, and also to guarantee the correctness of the filtering,
this stage was conducted by two researchers. Since Scopus has overlaps with
all the other databases, we assigned one researcher for Scopus and the other
for the rest of the databases. The percentage of conflicts (studies that were
included by one researcher but excluded by the other) on the overlap was used
as a metric to evaluate the explicitness of the criteria and the quality of
the filtering. The result of this evaluation is analyzed in Section 3.4.

Each conflict was resolved by a discussion among the two researchers
conducting stage 4 and an additional senior researcher.

The result of this stage is listed in Table IV. Studies selected by this stage
might also be excluded in Stage 7.

Stage 5: Snowballing was conducted in parallel with deep filtering and data
extraction. When reading through each study, relevant references were
collected. The relevance of each reference was judged by its title and how it
is described in the study under review.

Stage 7: The exclusion criteria E5 and E6 are sometimes difficult to evaluate
by only reading the title and abstract. This stage examines the papers
(selected by the previous stages) with a special focus on E5 and E6.

####  3.2.2 Data Extraction

This task is to answer RQ1. Relevant information needs to be extracted from
the primary studies according to a taxonomy. Meanwhile, the taxonomy needs to
be updated during the extraction. To start, an initial taxonomy was proposed
based on (1) the relevant industrial standards introduced in Section 2, (2)
the concepts identified from the initial set of the primary studies, and (3)
the previous project experience of the authors. The structure of the taxonomy
was inspired by [39]. The initial taxonomy was, thereafter, iteratively
updated when reviewing the primary studies, following the process illustrated
in Fig. 9. This section elaborates how each stage in this process was
conducted.

Figure 9: The stages to extract data from primary studies

Stage 1: All the primary studies were thoroughly read by at least one
researcher to extract information according to the taxonomy, and to identify
new concepts to update the taxonomy.

Stage 2: As suggested by Keele [34], the extracted information was coded
according to the taxonomy and documented in a data extraction form, which can
be found in [40]. The result for each study was reviewed by another two
researchers to guarantee correctness. For the information that could not be
explicitly found in the study, it was marked as ”not given” in the data
extraction form and if possible, a reasonable assumption was given according
to our understanding.

Stage 3: The taxonomy was iteratively updated when (1) a new concept, which
had not been included in the taxonomy, was identified from stage 1; or (2) a
mismatch (i.e. a study that cannot be reasonably classified by the taxonomy)
was detected from stage 2. When the taxonomy was updated, the extracted data
would also be updated according to the new taxonomy.

Section 4 presents the final taxonomy, and the data extraction form can be
found online as [40]. This task is also the basis of the next task to answer
RQ2 and RQ3.

####  3.2.3 Data Analysis

The goal of this task is to answer RQ2 and RQ3. In the previous task,
information was extracted from each primary study according to the taxonomy.
This task analyzes the extracted information with systematic and statistical
approaches. The analysis results answer RQ2. The findings from the analysis
answer RQ3. The analysis results and findings are presented in Sections 5, 6
and 7 and discussed in Section 9.

###  3.3 Reporting the review

The reporting contains two parts. The first part is this paper, which presents
the relevant terminology, the literature review methodology, and the answers
to the research questions. The second part is the data extraction form [40],
which summarizes each primary study according to the taxonomy.

###  3.4 Threats to Validity

This section discusses the potential threats to the completeness of the
literature search and our mitigation approaches. One of the main threats to
the validity of this systematic literature review is incompleteness. The risk
of this threat highly depends on the selected search string, the limitation of
the employed search engine, and the quality of the literature filtering
(stages 2,4 and 6 in Fig. 8). To reduce the risk of an incomplete search
string, the search string was constructed iteratively until no new synonyms of
$\$AD$ and $\$CS$ could be added to Table IV. In order to omit the limitations
of the employed search engines, multiple search engines were used on different
databases with overlaps. To avoid the exclusion of relevant papers during
literature filtering, the label unclear was introduced for the case where the
inclusion of a paper could not be determined with high confidence. This label
guaranteed that papers were excluded with high confidence. In addition, the
risk of incorrect exclusion could be implicitly evaluated by the number of
conflicting papers (i.e. papers that were included by one researcher but
excluded by the other) within the overlap between Scopus and other databases.
Among the total 77 overlapping papers, there were only 3 conflicts. After
further confirmation, only 1 paper (out of 3) was included.

Another important threat is the robustness of the taxonomy to describe any CSI
method. To guarantee the taxonomy has sufficient concepts to cover all the
selected papers, an iterative approach was conducted to update the taxonomy
and the extracted data until the taxonomy converged. Furthermore, the
capability of the taxonomy to describe a new paper was verified by the 9
papers (after deep filtering) found in the snowballing phase. All these papers
were successfully classified by the taxonomy without the need to add any new
concepts.

##  4 Overview of the Taxonomy

Employing the methodology introduced in Section 3.2.2, a hierarchical taxonomy
for CSI methods was identified as depicted in Fig. 10.

Figure 10: The taxonomy for critical scenarios identification approaches,
achieved from the reviewed literature

Inspired by [39], the first level of the taxonomy hierarchy structures the
studied CSI approaches with the following three fundamental categories, which
reflect the common logic of a complete research.

  * •

Problem Definition: What kind of scenario is being identified? Why are these
identified scenarios important? (Section 5)

  * •

Solution: What techniques are applied to identify the critical scenarios? What
external information / data is needed? (Section 6)

  * •

Evaluation: How are the validity of the approach and the identified critical
scenarios assessed? (Section 7)

Each of these three top-level categories is decomposed into multiple
subcategories. Each leaf category in the taxonomy has a number of possible
values to categorize CSI methods. The rest of this section introduces all the
subcategories.

###  4.1 Subcategories of Problem Definition

The Problem Definition category specifies the problem that the approaches aim
to solve. It is decomposed into the following subcategories.

Usage of the Scenarios: This category classifies the CSI methods according to
how the identified critical scenarios are supposed to be used. Subcategories
include 1) the System of Interest (SoI), i.e. the AD system/function whose
development is supported by the identified scenarios; and 2) how are the
identified critical scenarios used in different development phases. For
example, Li et al. [41] proposed a method to find critical scenarios as test
cases (purpose) for the verification (phase) of a whole ADS (SoI).

Target ODD: As depicted in Fig. 4, a clear and sufficient ODD definition is
necessary for the reasoning of critical functional scenarios and the
formalization of a functional scenario to a logical scenario. This category
analyzes how ODD is defined and used in each primary study.

Definition of Criticality: The studied CSI methods aim to select or generate
critical scenarios, which are distinguished from other scenarios from a
specific perspective. Even though the definitions of criticality are not
explicitly given in most of the primary studies, this category explicitly
classifies the criticality according to the characteristics of the identified
scenarios.

Level of Abstraction: This category classifies the studied approaches
according to their inputs and outputs in terms of the levels of abstraction of
their scenario representation, as described in Section 2.3.2. For example, the
approach proposed by Li et al. [41] identifies critical concrete scenarios
within a given logical scenario. Therefore this approach is classified as
”logical $\rightarrow$ concrete”. Similar approaches to identify critical
scenarios according to a scenario with a higher level of abstraction are
called deductive approaches. In contrast, inductive approaches find critical
scenarios based on a set of lower-level scenarios.

###  4.2 Subcategories of Solution

The category Solution classifies the primary studies according to how they
find critical scenarios within the constructed scenario space. This section
explains all its subcategories.

Scenario Space Construction: To systematically identify critical scenarios,
scenarios need to be consistently represented to construct a scenario space.
This category classifies the CSI methods in terms of 1) Content: what aspects
are included in the scenario model regarding the 6-layer model introduced in
Table II; and 2) Representation: how they are represented (e.g., formally,
semi-formally or qualitatively).

Scenario Space Exploration: Under this category, the studied CSI approaches
are categorized in terms of 1) which algorithm or technique is adopted to
explore the scenario space; 2) how the criticality of a scenario is assessed
during the exploration; and 3) what mechanisms are used to guarantee or
improve the coverage of the exploration. Since the criticality of a scenario
can hardly be directly measured, a surrogate measure is commonly used for
criticality assessment. One common example of a surrogate measure is the time-
to-collision (TTC) with the front vehicle in simulation. However, since a
surrogate measure cannot completely reflect the criticality of a scenario, as
shown in Fig. 11, the set of potential critical scenarios (identified
according to a surrogate measure) may slightly mismatch with the set of all
the critical scenarios in reality. The criticality assessment category
collects all the surrogate measures used in the primary studies, and maps them
to different criticality definitions.

Figure 11: Relationship between critical scenarios and potential critical
scenarios identified according to a surrogate measure

Required Information: This category summarizes the necessary information each
CSI method needs to identify critical scenarios, such as relevant databases,
assumed vehicle dynamic/kinematic models, functional models or implementations
of the SoI, pre-defined surrogate measures for criticality assessment and
environmental information provided by a simulator (e.g., CARLA or PreScan,
etc.).

In Section 6, CSI approaches are clustered into several groups according to
the similarity between the approaches based on all the subcategories under the
Solution category.

###  4.3 Subcategories of Evaluation

For the Evaluation category of the taxonomy, three subcategories are
considered. They are explained as follows:

Approach Verification: This category describes the techniques used to assess
the availability and efficiency of the approaches proposed in the primary
studies.

Criticality Validation: In contrast to the Approach Verification, this
category focuses on the evaluation of the identified scenarios. As shown in
Fig. 11, identified potential critical scenarios based on surrogate measures
may not fully overlap with the set of all the critical scenarios. Reasons for
this mismatch include, but are not limited to, the low fidelity of the
employed simulator, the assumptions made to simplify the exploration and the
limitations of the selected surrogate measure. This category summarizes the
approaches to validate the criticality of the identified critical scenarios.

Coverage Assessment: This category enumerates the approaches to assess the
coverage of the identified scenarios with respect to the whole scenario space.

##  5 The Problem Definition Category

This section presents the classification result of the primary studies
according to the problem definition category of the taxonomy.

###  5.1 Usage of the Identified Scenarios

In the primary studies, the identified critical scenarios can be used for
different Systems of Interest (SoI) under different development phases.

####  5.1.1 Systems of Interest

Section 2.1 introduces the common functions of ADS or ADAS. As discussed in
Section 3.1, the studied CSI approaches are used to support the safety
analysis, verification and validation of the whole ADS (or ADAS) or a
particular function of the ADS (or ADAS).

Many of the primary studies do not explicitly specify their Systems of
Interest (SoIs). In this section, SoIs of the primary studies are classified
according to their targeted levels of automation and their functionality.

Section 2.1 introduces how ADS and ADAS can be classified according to the
level of automation. Accordingly, the SoIs of the primary studies are
classified into the following categories based on the corresponding criteria.

  * •

L3+: CSI methods will be classified into this category if their SoIs have both
longitudinal and lateral control, and they do not require a driver.555Since
most of the primary studies are classified in this category, references to the
primary studies are only given for the other two categories. The rest of the
primary studies belong to this category.

  * •

L3-: CSI methods will be classified into this category if their SoIs have only
longitudinal control [42, 43, 44, 45, 46, 47] or a driver’s operations [48]
are required.

  * •

Active Safety: CSI methods will be classified into this category if their SoIs
cannot provide continuous control of the vehicle [49, 50, 51, 52, 48, 53, 54,
55, 56].

It is assumed that CSI methods for higher levels of automation can also work
for lower levels. Therefore, if a CSI method is designed for multiple levels
(e.g., the methods to find safety critical operational situations can be used
for all the levels), it is classed into the highest level. The statistical
result of this classification is shown in Fig. 12 (a).

Figure 12: Number of primary studies in each SoI category

An SoI can be the entire ADS (or ADAS) or a particular functionality of it.
From this perspective, the primary studies are classified into the following
categories based on the corresponding criteria derived from Fig. 5 and Fig. 2.
The statistical result of this classification is shown in Fig. 12 (b).
Detailed classification of all the primary studies can be found in the data
extraction form [40].

  * •

Perception: CSI methods in this category try to find triggering conditions of
unintended behaviors (e.g., wrong object detection and wrong object
classification) of the perception functions. A CSI method will be classified
into this category if the inputs of its SoI are the driving environment, and
the outputs are the information in the Perceived World Model.

  * •

Planning and Motion Control: CSI methods in this category try to find
triggering conditions of unintended behaviors (e.g., collision or other risky
behaviors) of the planning and motion control functions. The input of these
functions is the Perceived World Model, and the outputs are the control
commands to the actuators (e.g., the steering wheel, the throttle and the
brake.) Therefore a CSI method will be classified in this category if it
assumes the Perceived World Model is given as ground truth, or ground truth
with added noises [57, 58, 59, 60].

  * •

The Whole System: CSI methods in this category try to find 1) potential
safety-critical operational situations; or 2) critical scenarios as
combinations of both triggering conditions and safety-critical operational
situation. The input of the whole system is the driving environment, and the
outputs are the control commands. A CSI method will be classified into this
category if it does not assume the Perceived World Model is given and tries to
find scenarios that may lead to vehicle level hazards (e.g., unintended brake)
or accidents (e.g., crash).

Unintended behaviors of different functionalities may have different
triggering conditions attributed to scenario factors on different layers
introduced in TABLE II [15]. TABLE V illustrates the numbers of primary
studies that consider influential factors on a particular layer for a
particular SoI. Detailed models of these influential factors are analyzed in
Section 6.

TABLE V: Relations between SoIs and influential factors on different layers | L0 | L1 | L2 | L3 | L4 | L5 | L6
---|---|---|---|---|---|---|---
Perception | 0 | 0 | 0 | 0 | 0 | 0 | 0
Planning and Control | 0 | 5 | 2 | 0 | 37 | 2 | 0
The Whole System | 3 | 31 | 5 | 0 | 44 | 28 | 0
Total | 3 | 36 | 7 | 0 | 81 | 30 | 0

####  5.1.2 Phase and Purpose

As illustrated in Fig. 13, in the primary studies, the identified critical
scenarios are used in every phase of the development V model. The gray boxes
in Fig. 13 list what the identified critical scenarios can support in the
corresponding development phase.

Figure 13: How CSI methods support different development phases

Requirement Analysis:

This phase analyzes functional requirements or safety requirements at the
vehicle level. In ISO 26262, Hazard Analysis and Risk Assessment (HARA) is an
essential step to identify all the potential hazardous events. As depicted in
Fig. 3, each hazardous event is a combination of a hazard and an operational
condition. With the methods proposed in [61, 30, 62, 63], the identified pre-
crash functional scenarios can be used as the set of all the operational
conditions for HARA as described in [64].

Most of the studied CSI approaches treat the identified critical scenarios as
test cases used in the verification and validation phases. The failed test
cases or the identified critical scenarios through simulation can also support
the identification of specification insufficiency.

Some of the studied CSI approaches can also support the analysis of
influential factors by determining the critical regions (i.e. particular
values or value ranges of a set of parameters) where critical scenarios are
significantly more probable [65, 57, 58, 59, 60, 66]. The identification of
unknown influential factors is out of the scope of this survey but is briefly
discussed in Section 8.5.

System Design:

This phase decides the system configuration and the decomposition of vehicle
level requirements to component level. However, in this survey, no CSI
approach was found to support requirement decomposition. System configuration
includes the selection of sensors [55] and sensor ranges [67].

Component Design:

In this phase, the SoIs are certain AD functions, whose requirements are
decomposed from the vehicle level. Since different AD functions may be
sensitive to different environmental factors, influential factors are commonly
analyzed on the component level rather than the vehicle level [15]. One type
of approach is to evaluate whether the variance of a particular parameter will
significantly affect the criticality of the scenario [68]. For example, if
changing the color of a vehicle in front will significantly affect the success
rate to detect it, vehicle color will be considered as an influential factor.
Critical regions can also be determined for a certain AD function such as the
perception [57], and the planning and control functions [57, 69, 70, 71, 47].
In addition, for machine learning based algorithms, identified critical scenes
can also be added to the training set to support targeted data augmentation
[68]. If the critical scenarios are used as test cases, the failed test cases
can help with the identification of functional insufficiency, which includes
specification insufficiency and performance limitations.

Component and System Verification:

Nearly 55% of the CSI methods proposed in the primary studies focus on the
identification of critical concrete scenarios, which are used in the
verification phase as test cases. The generated test cases can be used to
verify the whole AD system (e.g., [41] ) or a particular AD function (e.g.,
[42] ). Detailed analysis of these methods can be found in Sections 6.1 and
6.2.

System Validation:

A common validation method is to estimate the accident rate or failure rate
through the Monte-Carlo simulation. Since critical scenarios are relatively
rare, Monte-Carlo simulation with a small sample size may lead to a bad
coverage of the critical scenarios and hence increase the estimation error. As
a variant of Monte-Carlo simulation, importance sampling reduces the
estimation error by assigning more samples to the critical but relatively rare
scenarios. Therefore importance sampling methods entail the identified
critical scenarios or critical regions as input.

In addition, as discussed in [72, 11], test cases that are potentially
critical for most of the ADS implementations can also serve validation
purposes, e.g., scenarios with heavy fog or a sudden cut-in in front of the
ego vehicle. This type of critical scenario is defined in Section 5.3 as a
non-implementation-specific critical scenario. More analysis on how to find
these scenarios can be found in Section 6.

###  5.2 Targeted ODD

As shown in Fig. 4, a clear ODD definition is necessary for the reasoning of
critical functional scenarios, and the formulation (together with
improvisation) of a functional scenario to a logical scenario. As discussed in
Section 3.1, improvisation and formulation are out of the scope of this
literature review. Therefore this section only focuses on how ODD supports the
reasoning of critical functional scenarios. A clear ODD definition is
essential to derive a complete set of critical concrete scenarios. However,
none of the primary studies provide an explicit ODD definition. Some of the
primary studies explicitly or implicitly provide the scope of the ODD, e.g.,
driving on a highway [61, 30] and driving on a structured road [62, 63, 73,
74]. Methods in these studies make assumptions about the environment (e.g.,
the behavior of other vehicles) within the ODD, and propose systematics to
reason about critical functional scenarios based on these assumptions.

###  5.3 Definitions of Criticality

As discussed in Section 2.4, in this paper, critical scenarios are considered
to be more important than non-critical scenarios in terms of safety analysis
or verification. The definitions of criticality are tightly connected with the
usages of the identified critical scenarios. However, most of the primary
studies do not provide an explicit definition of criticality. Instead, they
explicitly define the employed surrogate measures for criticality. In this
survey, these measures of criticality are classified according to two
dimensions, as illustrated in Table VI. This classification is also used to
specify the definition of criticality in each primary study. The two
dimensions are explained in the rest of this section. The surrogate measures
are detailed in Section 6.

TABLE VI: Surrogate measures of each criticality definition | Implementation-specific | Non-implementation-specific
---|---|---
Safety-Critical |  |  KPIs in Simulation: C1 [41] [42] [43] [44] [45] [50] [51] [53]
---
[75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88]
[89] [90] [91] [92] C2 [59] [93] C3 [55] [73] [94]
Collision: C1 [49] [52] [48] [95] C2 [46] [58] [60] [96] [97][98]
C3 [99] [100] [100] [101] [94] C4 [32]
Formal Specification: C1 [65] [57] C2 [102] [103]
Performance Boundary: C1 [65] [67] C2 [66]
Hazardous Event (ISO 26262): C4 [32]
|  KPIs in Simulation: C1 [104] [105] [86] [106] [107] [108]
---
Driveable Area: C1 [69] [70]
Collision: C2 [91] [109] C3 [110] [54] [56] [74] [109]
C4 [61] [30] [62] [63] [32] [111]
Function-Critical |  |  Consequence Aware:
---
KPIs in simulation: C1 [75] C2 [47]
Formal Specification: C1 [57] C2 [102]
Failures: C3 [101] C5 [68] [112] [113] [114]
Consequence Unaware:
Performance Boundary: C1 [77]
Differential Behaviors: C5 [115] [116]
|  Consequence Unaware:
---
Complexity: C1 [117] [118] [119] [120] C5 [68] [121] [122] [123]
Predictability: C5 [124]
Other |  |  Fuel consumption: C1 [77]
---
Comfort: C1 [78] C2 [71] (KPI)
Overall Traffic Quality: C1 [125]

The first dimension specifies whether the identified scenarios are
implementation-specific. An implementation-specific critical scenario is only
determined to be critical for a particular implementation of an AD function or
system (set of functions). It may or may not be critical for other
implementations of the same function or system. In contrast, non-
implementation-specific critical scenarios refer to the ones that are critical
for most of the implementations of the same function or system. For example,
scenarios with a heavy fog are critical for most of the camera-based object
detection/classification functions.

The second dimension classifies criticality according to consequence.
Scenarios that are highly likely to cause a hazardous event are defined as
safety-critical, while scenarios that may lead to a malfunctioning behavior
are classified as function-critical. According to Fig. 3, both safety-critical
and function-critical scenarios can support the identification of unknown
functional insufficiency and the corresponding triggering conditions. There
are also primary studies whose criticality definition includes other
perspectives such as comfort and traffic impact. These perspectives are out of
the scope of this survey.

Function-critical scenarios can be further classified according to the
awareness of the consequential malfunctioning behavior. If the consequential
malfunctioning behavior is pre-defined, (e.g., a collision or a
misclassification of a certain object), the criticality of the identified
scenarios is consequence-aware. Approaches to find consequence-unaware
critical scenarios tend to find scenarios where malfunctioning behaviors are
tend to be triggered. These scenarios may help to find unknown influential
scenario factors [124, 115, 116, 121].

Different primary studies may implicitly adopt different definitions of
criticality. TABLE VI explicitly classifies the definitions of criticality
according to the aforementioned three dimensions. As shown in TABLE VI, most
of the primary studies focus on the identification of safety-critical
scenarios. The number of primary studies that find implementation-specific
critical scenarios is larger than those finding non-implementation-specific
critical scenarios.

Different criticality definition entails different surrogate measures, which
are further summarized in TABLE VI and discussed in the next section.

###  5.4 Level of Abstraction

Critical scenarios can be identified on different levels of abstraction. As
introduced in Section 4.1, this section classifies the CSI methods according
to their inputs and outputs in terms of the level of abstraction of scenario
description. The classification result is given in Table VII.

TABLE VII: Number of studies classified according to their inputs and outputs In. Out. | Functional | Logical | Concrete | Criticality
---|---|---|---|---
Others | 2 | 2 | 0 | 0
Functional | 2 | 0 | 4 | 0
Logical | 0 | 2 | 52 | 6
Concrete | 3 | 0 | 12 | 6

Most of the studied CSI methods find concrete critical scenarios within a
given logical scenario (i.e., logical $\rightarrow$ concrete). An important
step within this process is to evaluate the criticality of a given concrete
scenario (i.e. concrete $\rightarrow$ criticality). These two classes cover
most of the CSI methods introduced in Sections 6.1, 6.2 and 6.5.

As shown in Fig. 4, critical functional scenarios can be reasoned from the ODD
definition and/or functional specifications and/or previous project
experience, etc. (i.e. others $\rightarrow$ functional) [61, 30, 32]. In some
papers, these reasoned functional scenarios are also formulated into logical
scenarios (i.e. others $\rightarrow$ logical) [62, 63]. These methods are
analyzed in Section 6.4.

Critical functional scenarios can also be induced from accident databases.
Depending on whether the accidents in the database are described qualitatively
or quantitatively, these methods can be classified as functional $\rightarrow$
functional [110] or concrete $\rightarrow$ functional [54]. These methods are
introduced in Section 6.3. Another type of functional $\rightarrow$ functional
method is to combine triggering conditions with hazardous operational
situations [32].

Studies evaluating the criticality of a logical scenario (i.e. logical
$\rightarrow$ criticality) actually evaluate the failure rate of an SOI under
the given logical scenario. These studies estimate the failure rate through
importance sampling [80, 81, 82, 83, 85, 42], which is a variant of Monte-
Carlo simulation, considering the distribution of critical scenarios in the
space of the given logical scenario. It should be noticed that the focus of
this survey does not include how the failure rate is evaluated. We only care
about how the critical region can be discovered at the first step of the
importance sampling.

There are two types of concrete $\rightarrow$ concrete methods. The first type
refines a concrete scenario to make it more critical by tuning its parameters
[65, 57, 88, 71, 47, 121, 115, 116]. These methods can be found in Sections
6.1, 6.2 and 6.5. The second type requires multiple critical concrete
scenarios to synthesize new critical scenarios [73, 74, 94, 109]. This type of
method is introduced in Section 6.3.

##  6 The Solution Category

According to the similarities on the problem formulations and solutions,
studied CSI approaches are grouped into the following five clusters. Fig. 14
illustrates the number of primary studies in each cluster.

  1. C1:

Exploring logical scenarios without parameter trajectories (Section 6.1)

  2. C2:

Exploring logical scenarios with parameter trajectories (Section 6.2)

  3. C3:

Inductive reasoning methods (Section 6.3)

  4. C4:

Deductive reasoning methods (Section 6.4)

  5. C5:

Finding critical scenes for CV-based functions (Section 6.5)

Figure 14: Number of primary studies in each cluster

As depicted in Fig. 4, a logical scenario can be instantiated into multiple
concrete scenarios. The parameters of a logical scenario can be classified as
illustrated in Fig. 15. Assumed parameters have fixed values for all the
instances (i.e. concrete scenarios), e.g. the number of vehicles in a scenario
and the number of lanes. Parameters of interest construct the scenario space
to be explored. These parameters include the ones that are constant over time
(e.g. the weather condition or the position of a stationary obstacle on the
road) and the ones that are variable over time (e.g. the speed of a
surrounding vehicle or the perception error). If a parameter is variable over
time, it can be represented as a parameter trajectory. Values of the
parameters can be either categorical (e.g. weather, color and vehicle model)
or numerical. Numerical values can be either continuous (e.g. speed, heading
and sensor noise) or discrete (e.g. the number of other vehicles, the number
of lanes and speed limit).

Figure 15: Classification of parameters of a logical scenario

The approaches to explore a logical scenario are elaborated in both C1 and C2.
The difference between these two clusters is that the logical scenarios in C1
do not contain parameter trajectories. C3 analyzes the methods to induce
critical scenarios from different data sets. C4 discusses systematic
approaches to deduce critical functional scenarios. Most of the computer-
vision (CV) based functions (e.g. object detection or classification) take a
scene (i.e. a camera image) as input at each time step. The performance of
such a function is mainly affected by the input scene rather than how the
scene develops over time. Methods to find critical scenes for CV-based
functions are summarized in C5.

The following subsections respectively introduce our analysis of these
clusters. Except in C4, CSI approaches in each cluster are summarized with a
gated tree, i.e. Fig. 17, 22, 23 and 24. Each node of these trees represents a
component of a CSI solution. A parent node is connected with its children
through either an ”AND” gate or an ”OR” gate. The ”AND” gate implies that the
parent note is constructed with all its children as necessary components. For
example in Fig. 17, all the methods in C1 (i.e. the root node) contain three
components, namely a logical scenario model, an exploration method and a
criticality assessment approach. If they are connected with an ”OR” gate, the
children will be the alternative solutions of the parent node. In other words,
in a particular paper (e.g. [41]), the parent node (e.g. the Exploration
Method node in Fig. 17) will choose one of its children (e.g. Combinatorial
Testing) as a solution. Not so many papers have been found in C4. Such a
systematic figure is not given for C4, since a conclusion drawn from such few
samples will not be representative. A systematic classification of CSI methods
in C4 will be part of the future work.

###  6.1 Exploring Logical Scenarios Without Parameter Trajectory

This section focuses on approaches to explore a logical scenario that does not
contain a parameter trajectory. The exploration methods for logical scenarios
with parameter trajectories are analyzed in Section 6.2. The exploration
processes in this cluster are formulated as Design Space Exploration (DSE) or
Search-based Testing (SBT) problems [89], whose flow chart is shown in Fig.
16. Given a logical scenario, a set of concrete scenarios are generated with a
parameter space exploration method. Among these generated concrete scenarios,
critical ones are identified with a pre-defined criticality assessment method.
Criticality assessment can be seen as a function that maps a point in the
scenario space to a point in the scoring space. The scoring space is the
quantitative evaluation of criticality for concrete scenarios. The evaluation
is achieved through the surrogate measures since the criticality can hardly be
measured directly. If the criticality is defined on multiple dimensions, each
dimension in the scoring space refers to a criticality measure. Based on Fig.
16 and the taxonomy in Fig. 10, all the CSI methods in this cluster are
summarized in Fig. 17. The analysis of Fig. 17 follows the taxonomy of
_Solution_ category in Fig. 10.

Figure 16: Critical concrete scenario identification process

Regarding the analysis in Table VII, most of the approaches in this cluster
take logical scenarios as inputs and generate a set of critical concrete
scenarios, which are further used to construct test cases or simulation cases.
Exceptions include the approaches that focus on the criticality assessment of
a given concrete scenario [92, 107], and the refinement of a logical scenario
[69, 70]. Criticality assessment is considered in this cluster because it is
one of the essential steps to search for critical scenarios, as shown in Fig.
16. If a primary study only focuses on a criticality assessment approach, it
usually implies that the given concrete scenario is generated from its
previous step. Logical scenario refinement methods are included in this
cluster only if they employ search-based methods. Instead of finding
individual critical scenarios in the scenario space, they optimize the lower
and upper bounds of the parameters of interest to derive the critical region.
It can be treated as a prepossessing step of CSI methods to reduce the
searching space.

The rest of this section explains Fig. 17 based on all the primary studies in
this cluster.

Figure 17: Instantiation methods without parameter trajectories

####  6.1.1 Scenario Model

In this cluster, a logical scenario is modeled as a scenario space. Each
dimension is a parameter of interest whose value can be either categorical or
continuous. A logical scenario also specifies their value ranges or
distributions. A concrete scenario is a vector in this scenario space with a
fixed value for each dimension. As mentioned in Fig. 3, each parameter of
interest correlates to one known scenario factor at one layer, as described in
TABLE II. From the perspective of test (or simulation) case construction, each
parameter specifies either:

  * •

an initial condition including, e.g., the initial position, speed, or heading
of the ego vehicle or other traffic participant;

  * •

a constant condition including the weather condition (e.g., sunny, foggy, or
raining) and the road topology;

  * •

or a parameter of an assumed model including, e.g., the size, field of view,
or constant speed of a vehicle model

Parameter distributions can help to estimate the likelihood of exposure of a
given concrete scenario. 9 out of 45 studies in this cluster consider
realistic distributions of parameters ([42, 79, 92, 45, 80, 81, 82, 83, 85])
during the exploration. Other studies assume that the parameters follow a
uniform distribution. The realistic parameter distributions are taken into
account mainly for the following reasons:

  * •

To estimate the failure rate of the SoI in all situations: As discussed in
Section 5.4, estimating the failure rate with importance sampling needs
critical scenarios or critical region as input. In addition, it also needs to
know the likelihood of exposure of each sampled concrete scenario, which can
be approximated based on the parameter distributions.

  * •

To consider commonality as part of the criticality definition: Compared to
rare cases, those with higher probabilities to exposure in the real world are
of significant interest. To this end, the commonality of a scenario is
introduced into the definition of criticality [42, 79, 92], so that the
exploration method can find common and hazardous scenarios. This commonality
can be quantified with the help of parameter distributions in real traffic.

Parameter distributions are derived from an existing real-life driving
database (i.e., the Naturalistic Driving Study (NDS) or Field Operational Test
(FOT) data). The parameters can be assumed either mutually independent [107,
108] or dependent [79]. Akagi et al. [79] considered the parameter
distribution and approximate it by a Gaussian Mixture Model (GMM), where
parameter probability distributions represent the covariance of variables.
Methods to approximate parameter distributions from a given data set are
summarized in [126].

####  6.1.2 Exploration Methods

Fig. 17 lists all the methods to explore the scenario space employed in the
primary studies in this cluster. These exploration methods can be divided into
two types: (1) naive search (i.e., _Sampling_ and _Combinatorial Testing_) and
(2) guided search (i.e., _Optimization_ and _Learning-based Testing_).

A naive approach for scenario exploration is to search randomly or
systematically over the scenario space. In other words, samples are mutually
independent. Therefore these approaches can be implemented in a parallel
manner to reduce the exploration time. However, if critical scenarios are
rare, these approaches can be inefficient as the probability of sampling a
critical scenario is low. On the other hand, the guided search methods have
the potential to be more efficient, since the searching direction at each
iteration is adjusted according to the search result of the previous
iteration, so as to converge the exploration to critical regions. Each
exploration method under these two types is briefly introduced in the rest of
this section.

Sampling: The sampling method instantiates a concrete scenario by randomly
assigning each parameter’s value in a logical scenario space. A predetermined
number of samples are taken statistically based on probability distributions
of parameters, and its sampling size is determined by the required coverage
and computation time for simulation. The applied sampling methods are
summarized in Fig. 18. According to the parameter descriptions in logical
scenarios, the sampling approach can be classified based on whether the
parameter distributions are taken into account. We assume that a uniform
distribution is adopted if the parameter distribution is not mentioned. Near-
random sampling, such as Latin Hypercube sampling [67], can improve the
coverage when the sampling size is small. It splits the multi-dimensional
parameter space into even grids and selects samples in each grid with a given
number.

As mentioned in Section 6.1.1, parameter distribution is considered for two
purposes: failure rate estimation and commonality consideration. Since the
failure rate estimation by importance sampling barely appears during the
scenario space exploration phase, in this section we only consider parameter
distribution used to model the commonality of the scenarios. Moreover, when
considering the parameter distributions, relationships between parameters can
be assumed either dependent or independent. Different assumptions require
different sampling methods. Studies [107, 108] investigated the parameter
distributions before sampling. In these studies, each dimension in sampled
scenarios is viewed as independent and identically distributed (i.i.d.). The
covariance among different parameters is not considered, and their values can
be determined independently. Nevertheless, correlations among variables are
also investigated in some other studies[79, 104]. When considering the
relationship among variables, more restrictions are imposed on the sampling.
Instead of Monte-Carlo sampling, the Markov Chain Monte Carlo (MCMC) method
[79] can be applied efficiently with the knowledge of parameter distribution
and covariance. The proposed approach in [79] applies a risk index from
naturalistic driving data to select risky traffic conditions efficiently.

If the scenario space is fully discrete and reasonably small, an exhaustive
search is applicable to guarantee full coverage. As shown in Fig. 18, it is
considered as an extreme case of sampling. If the scenario database is
available, the exhaustive search can be achieved through checking every test
case derived from NDS/FOT data [53]. Otherwise, the exhaustive search can
discretize continuous parameters and perform a full-scale grid search to
examine every existing test case in the scenario space [43, 104, 86].

Figure 18: Sampling method in scenario exploration

Combinatorial testing: Combinatorial Testing (CT) is a commonly used software
testing method focusing on the identification of failures triggered only by
particular combinations of inputs [127]. The core of CT is to generate a
minimum set of test cases (i.e. a covering array) that satisfy N-wise
coverage666N-wise coverage states that all N-tuples of parameter values must
be tested at least once, given an SoI model with the parameter list, values,
and constraints to define parameter interactions [128]. Under the context of
CSI for ADS, CT can be used to find the unknown combinations of influential
factors that may fail the ADS or a particular AD function. An example is when
a pedestrian crosses a road in front of the ego vehicle in the evening. The
criticality is significantly influenced by the combination of different
scenario parameters, such as the initial speed of the ego vehicle, visibility,
and distance between the pedestrian and the vehicle. The covering array, as a
matrix that stores the testing configurations, specifies test data where each
row of the array can be regarded as a set of parameter values for a specific
test[129]. For example, if the required coverage is three-wise, the generated
covering array should cover all combinations of values from arbitrary three
parameters, where three specifies the number of parameters in combination. A
good covering array can significantly reduce computational cost and improve
test efficiency. However, finding the minimum covering array is an NP-hard
problem [127]. A test database comprises all test scenarios in the covering
array, and it can cover all possible combinations of parameter values at a
predefined degree.

N-wise coverage can only be defined on discrete parameter space. However, in a
real-life scenario, both continuous and discrete variables are prevalent in
the parameter space of the logical scenario. A common method to handle
continuous parameters is discretization, which is a process of quantizing
continuous attributes by converting the continuous data into a finite set of
intervals and assigning some specific data values to each interval [130]. In
some other studies, Tuncali et al. [65] circumvented the problem by a two-step
approach. The first step performs CT on all the discrete parameters. In the
second step, for each combination of the discrete parameters, they conducted
optimization by simulated annealing on all the continuous parameters. The
optimization is used as the falsification process to identify critical
scenarios.

Instead of focusing on the minimum number of test cases in the covering array,
covering array generation methods can also be customized. For example, in
[117, 118, 119, 120], the generated covering array fulfills not only the
N-wise coverage but also maximizes the overall complexity of all the
scenarios.

Optimization: Studies in this class formulate the CSI approaches into
optimization problems, which generically contain four parts, namely the design
variables, the constraints, the objective functions, and the optimizer (i.e.
the solver) [131]. The design variables have already been analyzed in Section
6.1.1 and their ranges are restricted by the constraints. Therefore, as shown
in Fig. 17, this section mainly analyzes the objective functions and the
selected optimizers.

In the vast majority of studies in this class, the objective functions
represent quantified criticality measures, which are discussed in Section
6.1.3 in detail. Other than criticality, the objective function can also
include the similarity between scenarios (i.e. the distance in the scenario
configuration space) to maximize the diversity of the identified critical
scenarios [80, 81].

The choice of optimizer highly depends on the problem formulation, especially
the transparency and complexity of the underlying models. A simulator is
commonly employed when estimating criticality measures. Due to the high model
complexity and unavailability of the interior structure of plant models, in
many cases simulation and system analysis of the SoI can be computationally
expensive. For this reason, the behavior of the SoI is treated as a black box.
Thus, the corresponding search process can be regarded as a black-box
optimization problem. For a black-box optimization problem, the input (i.e.
scenario parameters) and output (i.e. simulation results) relationship can
only be analyzed by exterior observation through simulations [132]. To tackle
this problem, various heuristic methods can be applied to approximate the
fitting function and find the global minimum iteratively, including genetic
algorithm [49, 50, 105], Bayesian optimization [95, 89], and simulated
annealing [51]. In addition, the domain-specific heuristic technique, where
the optimizer only suffices in a certain system, helps to identify multiple
local minimums of feasible solutions by rule-based searching [108], heuristic
simulation-based gradient descent [44] and zoom-in sampler [52]. Scenario
searching is formulated as a two-step optimization problem in [80, 81, 82].
The first step of the optimization tries to find multiple local optimal
solutions. In the second step, the neighborhood of the local optimal solutions
is searched to find all the scenarios whose criticalities are within a given
threshold.

Learning-based testing: Learning-based testing methods [133] aim to
automatically generate a large number of high-quality test cases by combining
a model checking algorithm with an efficient model inference algorithm, and
integrating these two with the SoI in an iterative loop. It learns the
properties of the SoI during optimization by training a surrogate model. The
diversity can be optimized by maximizing the distances between samples in
either the scenario space or the scoring space. Mullins et al. [77] used a
surrogate model for training to improve the sampling coverage. It takes a set
of samples as input and returns the estimated diversity (i.e. the mean
distance) on the scoring space of the input samples. Nabhan et al. [78] used
learning-based methods to try to maximize the distance between scenarios. It
also considers non-safety-critical qualities (such as deceleration and jerk
effects indicating passenger’s comfort) during the scenario generation.

Others: This category refers to other methods to generate test cases and
detect critical scenarios not included in our research, such as Tabu search,
hill-climbing, and grammatical evolution. The review of common search
algorithms in software testing can be found in [134, 135].

####  6.1.3 Criticality Assessment Methods

After attaining concrete scenarios from the CSI methods mentioned above, most
of the primary studies adopt testing-based approaches to verify the
criticality of derived scenarios, as shown in Fig. 19. Different definitions
of criticality are discussed in Section 5.3. This section discusses how to
assess the criticality of a concrete scenario under different criticality
definitions.

Figure 19: Test case generation from concrete scenarios and testing-based
criticality assessment

In the criticality assessment phase, most of the studies utilize an X-in-the-
loop simulation to estimate the criticality of a concrete scenario, where X
represents the model, software, or hardware of the SoI as a black-box.
Criticalities are assessed on the simulation results based on the predefined
surrogate measures summarized in Table VI. Nevertheless, the criticality can
also be assessed without X-in-the-loop simulations. Validation can be realized
through real-world testing to analyze the performance of the proposed
exploration method [86, 81].

As discussed before, criticality assessment is a function whose input is a
concrete scenario, and whose output is a quantified criticality index. Most of
the studied CSI methods in this cluster implement this function deductively
with analytical approaches, while the others implement it inductively with
machine learning approaches [77, 78].

Inductive criticality assessment is generally applied in the data-driven
approach. Instead of evaluating scenario criticality by the black-box
simulation, it constructs an approximation model to emulate the real system
behavior with the database. The database is composed of existing scenario data
with labels, which indicates the criticality of the scenarios and is used in
the training process of the approximation models. The labels of criticality
measures can be attained directly from the training data in the scenario
database. It can also be derived by simulation of concrete scenarios, where
the simulation result is regarded as the ground truth.

Since criticality can hardly be measured directly, deductive criticality
assessment is based on a surrogate measure to evaluate the criticality of a
concrete scenario quantitatively. The surrogate measures can be either Boolean
or numerical in the scoring space, depending on the types of exploration
methods. For naive search methods, criticality measures are Boolean, since
each sampled scenario needs to be evaluated as critical or non-critical. For
guided search methods, since criticality is a part of the objective function,
the criticality measure has to be quantified as numerical. Under each
criticality definition, one or more surrogate measures were proposed in
different primary studies, as summarized in Table VI. More measures of
criticality can be found in [136]. Based on Table VI, the surrogate
criticality measures used in this cluster are summarized as follows.

KPI-based measures are commonly used in this cluster due to the simplicity of
implementation. It describes the proximity to a critical state through
simulations driven by black-box testing. KPI-based methods calculate metrics
by assessing a posterior measurement of the vehicle state. The metrics are
used to evaluate the criticality in a scene, and the criticality of a scenario
can be subsequently indicated by the worst scene. In the context of the
safety-critical scenario measurement, KPI metrics refer to Time-to-X metrics
(e.g., Time-to-Collision, Time-to-Brake, and Time-to-React), distance-based
metrics (e.g., longitudinal and lateral distance), velocity-based metrics
(e.g., relative speed), and acceleration-based metrics (e.g., required
deceleration). A comprehensive analysis of KPI comparison can be found in
[137]. The metrics above are usually used as the measures of a particular
function. However, compared to the implementation-specific category, the non-
implementation-specific ones can be found only with the generic features of
the SoI, for example, a highly abstract simulation model which is generic
enough to represent different implementations of the SoI or a criticality
measure that is only based on the environmental aspects. The critical
scenarios are detected without information of the implemented function, which
makes it possible to apply scenarios for system design [107] and early phase
of verification [86]. Also, the driveable area [69, 70] can be viewed as a
special measure in this category, where the criticality is defined directly on
a logical scenario by examining the range of relevant parameters. The SoI
(e.g., general motion planning algorithms) will be more critical if the
solution space is smaller with a less drivable area. Meanwhile, besides
safety-critical applications, KPI-based approaches can also be applied in
functional-critical studies. Unlike safety-critical measures, function-
critical assessment emphasizes the performance of a particular module of the
SoI (e.g., sensor, decision-making, and actuator), which does not necessarily
propagate to an accident.

Besides the KPIs mentioned above, in order to increase the efficiency of
critical scenario detection, complexity can be regarded as an auxiliary
property of criticality in some studies [117, 118, 119, 120]. Compared to
traditional software testing, critical scenario generation focuses on finding
triggering conditions instead of explicit software bugs. Different value
selections correspond to different levels of complexity, which is treated as a
priori knowledge before performing the test case generation. By our definition
in Section 5.3, they are viewed as non-implementation-specific and
consequence-unaware, since the complexity is not exclusively oriented to any
particular malfunction type.

Compared to KPI-based methods, collision is a more straightforward measure in
the safety-critical assessment. It generates binary output according to
whether a crash happens in a simulated scenario. However, some real-world
collision scenarios may not manifest on simulation due to the low fidelity of
the simulation model. In this cluster, collision analysis only appears in the
implementation-specific category since collision avoidance has to be realized
with certain types of ADAS/ADS.

A more complex and specific measure in implementation-specific class can be
represented by formal specifications such as signal temporal logic (STL) [65,
57]. This kind of method can be applied to either safety-critical or function-
critical use cases. The safety-critical approach examines the scenarios that
may lead to accidents, while the function-critical measure aims to find
anomalies in subsystem-level function and test its robustness.

In addition, implementation-specific criticality can also be characterized by
performance boundary, which can be divided into two types. The first type is
the predefined boundary, where the exploration methods try to separate
critical scenarios to non-critical ones through the boundary and find
avoidable collisions [67]. In the second type, the performance boundary is
unknown at the beginning. Several performance modes are derived through
clustering the scoring space. Scenarios around the boundaries of the
performance modes are of great interest since slight changes of parameter
values can contribute to the behavior change. It is assumed that faults tend
to manifest in those scenarios [65]. Moreover, we distinguish the study in
[77] as the consequence-unaware type for the function-critical use case, since
a scenario is regarded as critical if a small change of its configuration
leads to significant changes in the SoI performance. By this definition,
consequential malfunctioning behavior is not explicitly given. In the above-
mentioned types of studies, the criticality assessment is realized by
simulation.

Apart from the safety-critical and function-critical consideration, quality of
service (QoS) indices can also be applied as surrogate measures. In this
cluster, the normal operations of the vehicle are assumed, and QoS is
quantified to judge the performance of a system, such as by fuel consumption
[77], passengers’ comfort [78], and overall traffic quality [125].

####  6.1.4 Coverage

For safety argumentation, coverage must be considered when exploring a logical
scenario. However, not all the primary studies in this cluster explicitly
discuss coverage. As shown in Fig. 20, this section summarizes the
consideration of coverage and the mechanisms to increase the diversity of the
identified critical scenarios in this cluster.

Figure 20: Mechanisms for coverage of scenario space exploration methods

Combinatorial coverage (i.e. N-wise coverage) [138, 41, 65, 57, 117] and
sampling size [67, 86, 107] are the two metrics found in the primary studies
in this cluster to measure the coverage of the exploration. These two coverage
metrics are detailed in Section 6.1.2.

Another definition related to coverage is the diversity of the identified
critical scenarios. Similar scenarios have a high potential to reflect the
same triggering condition. Diverse critical scenarios can help to identify
different functional insufficiencies and hazardous events. The rest of this
section discusses mechanisms to increase the diversity of the identified
critical scenarios.

In the primary studies, diversity is quantitatively defined based on the
distance in the scenario space. For sampling-based exploration methods,
distances are generally estimated in the Euclidean space. Different measures,
such as Voronoi interpolation [89], can be used at sampling to ensure no tests
exist in close proximity. Moreover, various sampling methods, such as Latin
Hypercube Sampling [67], can also improve the diversity of samples. It divides
each parameter into intervals and ensures the scenario space is evenly
covered.

On the other hand, for optimization or learning-based methods, diversity can
be considered part of either the objective or the constraint. The diversity
can be realized either by examining the distance among scenarios [77], or by
exploring multiple local minima [88, 95]. For the latter approach, Wagner et
al. [88] extracted key features from critical scenarios by principal component
analysis (PCA) and added noise in a lower-dimensional component space to
reconstruct more varied critical scenarios. Gangopadhyay et al. [95] applied
Bayesian Optimization to identify multiple minima regions from a non-convex
function, where critical scenarios are situated in minima regions. Both
methods mentioned above aim to find critical scenarios with diverse failure
conditions.

####  6.1.5 Required Information

When identifying critical concrete scenarios from a logical scenario, a CSI
method needs a logical scenario as input and one or more surrogate measures to
support criticality assessment. These have been discussed respectively in
Sections 6.1.1 and 6.1.3. Research in this cluster normally verifies the case
study by simulation-based approaches. In the context of simulation, the
completeness of a test case includes four parts, namely simulation objects
(i.e. SoI), simulator and environment, criticality, and database. The
simulation objects and criticality have been discussed in previous sections.
Herein, we mainly focus on the simulator and database.

Simulator: The simulator provides the platform to implement and express SoI
properties in vehicle dynamics and ADAS/AD function through modeling language.
Many high-fidelity simulators (e.g., PreScan, CarMaker) also support virtual
test driving to visualize simulation environments. We regard a simulator as
the ad-hoc simulation platform if the simulator is developed in-house or not
mentioned in the article. MATLAB, together with other programming language
simulators, are viewed as low-fidelity simulation platforms as the system
dynamics are simplified, or virtualization is omitted. The main target of the
low-fidelity simulator is the realization of a system dynamics description and
to enable the process of sampling, thus the model fidelity is not the focus.

Database: All primary studies referring to the database in this cluster employ
it to analyze parameter distribution as prior knowledge. Based on our
findings, we cluster the database into three types: naturalistic driving data
[106, 87, 86, 88], traffic flow data [79, 53] and collision accident data
[104]. It is worth noting that NDS databases exclusive to autonomous driving
(e.g., Safety Pool) are available but have not been found applied in the field
of this cluster.

###  6.2 Exploring Logical Scenarios with Parameter Trajectories

In the previous section, the behavior of other actors (e.g., vehicles or
pedestrians) is determined by several parameters of a predefined motion model
(e.g., the velocity of a constant velocity model). In this way, possible
behaviors of other actors are restricted, especially their reactions to the
behaviors of the ego vehicle. A more arbitrary way to determine the behavior
of another actor is to model it as a motion trajectory (position trajectory or
acceleration trajectory). This can also be extended to any parameters whose
development over time is of interest (e.g., the angle of the sun). In general,
the variable over time parameters, also called parameter trajectories, are the
values of the scenario that change during the simulation. Methods to explore a
logical scenario including such parameter trajectories are discussed in this
section. Such problems are also called stress testing in [58, 93, 60] or
adversarial testing in [102].

Replacing one parameter with a trajectory of parameters will significantly
increase the exploration space. Therefore, the methods introduced in the
previous section are not fully suitable for the problem in this cluster. The
rest of this section discusses the methods in the primary studies for this
type of problem.

In these studies, the SoI is challenged by a scenario in which the behavior
(or the perceived behavior) of the other actors is set to make the system fail
under a certain metric. Some methods treat the SoI as a back box e.g. [70, 69]
while others may need to know the model of the system as part of the
optimization process e.g. [71], or at least the order of the model [47]. Fig.
21, based on [139], shows the relationship between the SoI, the environment
and the adversarial agents. The SoI generates actions based on the
observations obtained from the environment, which is also influenced by the
adversarial agents. All the connections represented in this diagram, the
actions and observations from the SoI, and the states and disturbances from
the adversarial agents, are parameter trajectories.

Figure 21: Relation between the SoI, the environment and the adversarial
agents [139]

An overview of methods found in this cluster can be seen in Fig. 22. These
methods require a scenario model, an exploration method, and a criticality
assessment based on the taxonomy in Fig. 10. The scenario model contains
information about the constraints imposed to the scenario. The exploration
method searches for a scenario that may lead the SoI to a hazardous event (as
described in Fig. 3) based on the criticality assessment. This criticality is
assessed based on a pre-defined surrogate measure.

Figure 22: Instantiation methods with parameter trajectories

The categories proposed in [139] have been used to classify the exploration
methods of this section. Even though the scope of [139] is not within the
automotive domain, and the methods analyzed only consider black-box safety
validation, the proposed categories are still useful for the purpose of
classifying the exploration methods of the present study.

####  6.2.1 Scenario model

A scenario model includes a set of parameters. Some of them have a predefined
value (assumed parameters) while others (parameters of interest) should be
optimized to find a critical concrete scenario, as shown in Fig. 22. Examples
of assumed parameters in the primary studies are the number of other actors
(moving traffic participants) [91], the number of lanes [69], and the position
of the crosswalk [58].

Referring to Fig. 15, parameters of interest in this cluster may include both
constant (over time) parameters and parameter trajectories, or only parameter
trajectories. An example of constant parameters is the the number of agents in
a particular scenario in [91], which is explored within a predefined range.

The exploration method aim to find the optimal parameter trajectories to
challenge the SoI. These parameters generally include the motion profiles of
other actors and the level of noise (e.g., [58]). Parameter trajectories can
also be used to model other factors such as weather conditions or traffic
light patterns, as mentioned in [102].

Motion profiles can be restricted to longitudinal motion, as in [46], or they
can also include lateral positions. The lateral positions can be expressed
with respect to the center of the lane, as in [103] or using absolute
coordinates, as in [58]. Besides positional restrictions, there can be other
types of constraints, as in [103], where the lateral velocity and the yaw rate
were specified to be within certain values.

Including parameter trajectories significantly increases the searching space.
In addition, the values of the same parameter at different time steps are not
independent. Therefore, methods introduced in Section 6.1 are not optimal for
the problems in this cluster. Instead, most of the approaches in this cluster
formulate the exploration as a sequential decision-making problem.

####  6.2.2 Exploration method

The exploration method aims to find a set of values and trajectories for the
parameters of interest that force the SoI to fail under a certain metric. As
mentioned before, for the classification of the methods, the categories
proposed in [139] have been followed, where these exploration algorithms are
divided into optimization, path planning, and reinforcement learning:

Optimization:

These methods are similar to the ones introduced in the previous section. They
assume that the values at different time steps of a trajectory are independent
and include a cost function designed to guide the search for a trajectory that
forces the SoI to fail. In [139], simulated annealing, genetic algorithms and
Bayesian optimization are included in this category. [97] is the only
publication related to this category that has been identified. It uses
Bayesian optimization to generate adversarial scenarios. Bayesian optimization
is an algorithm proposed to optimize functions that are expensive to evaluate
without knowledge about the structure of the function e.g. concavity or
linearity [140]. In [97], the optimization is not directly used to generate a
trajectory. It is used to optimize the policy of the adversarial agents that
decided their behavior based on their observations. No study has been found
during our study that uses optimization techniques to directly generate
trajectories. One of the reasons might be the complexity of the environment,
which might make these methods impractical due to the exponential growth of
the state space.

Path Planning:

Path planning algorithms aim to navigate the state space from a starting state
to a goal state. In this case, the goal is to get from an initial state to one
of the failure states using disturbances as control inputs [139]. In this
category, the following algorithms have been identified:

Rapidly exploring random trees (RRT): RRT is a search algorithm for path
planning designed to handle high degrees of freedom [141]. This method is used
in [46] to make an ACC system fail by generating motions of the leading
vehicle. They use two methods to explore the tree: forward search and backward
search. Forward search starts at a randomly generated safe state and generates
the tree based on the actions of the leading vehicle aim to get the ego
vehicle into an unsafe state. Backward search starts at a random unsafe state
and searches backwards in time trying to reach a safe state. In both methods,
they randomly generate the behavior of the leading vehicle and, based on that,
they generate the response of the ego vehicle. In [66], the aim is to find
almost-avoidable collisions or near-misses. To promote this kind of collision,
RRT was used together with a custom cost function that estimated how avoidable
a collision was based on the ratio of the collision surface, the collision
speed, and the minimum time to collision. In both studies, each node of the
tree includes the state of the system so that, when the tree grows, only a
partial simulation is executed from an existing node of the tree to the new
node, instead of running the simulation from the initial state.

Optimal control: This is a control strategy that aims to optimize an objective
function. It originated as an extension of the calculus of variations [142].
In [47], the process to search for critical scenarios is formulated as an
optimal control problem, which finds the optimal sequence of control input (in
the case study, it is the acceleration profile of the leading vehicle and the
time instances of critical scenes) to optimize the objective function.

Controller synthesis: Controller synthesis aims to generate of a controller
given the complete model of a system and the environment that is guaranteed to
achieve a specification [143]. In [103], the authors use controller synthesis
to generate scenarios where it is guaranteed to be possible to satisfy a set
of formally defined specifications.

Reinforcement learning:

Reinforcement learning aims to program agents by giving a reward based on
their actions without specifying how the task should be accomplished [144].
Actions might affect not only the current reward, but also the future ones
[145]. The algorithms analyzed in this section model the problem as a Markov
decision process (MDP). The methods found in this category are the following:

Monte Carlo tree search: a heuristic search algorithm for decision making that
takes random samples in the decision space and uses that information to build
a search tree [146]. In [58], the authors compare its performance against
deep-reinforcement learning and Trust Region Policy Optimization (TRPO) to
solve the MDP used to model the scenario.

Deep reinforcement learning: uses deep neural networks to approximate the
value function, the policy or the model of reinforcement learning [147]. [58]
extended Adaptive Stress Testing (AST) originally proposed in [148] to test
aircraft collision avoidance systems. AST formulates the scenario as an MDP
and uses a Monte Carlo tree search to solve it. In [58], the authors proposed
to extend AST by using deep reinforcement learning to solve the MDP and apply
it to a set of autonomous vehicle scenarios. [59] and [93] improve the reward
function previously proposed by using RSS [7] to find scenarios where the ego
vehicle performs improper actions and including a trajectory dissimilarity
reward to find diverse failures. In [60], the authors extend the work
performed in [58] by replacing the original Multi-layer Perceptron Network
with a Recurrent Neural Network. In [102], the authors use Deep Q-learning (a
deep reinforcement learning method) to learn the behavior of the adversarial
agents. The ego vehicle and the agents have Rulebooks (originally proposed in
[149]) associated with them to constrain their behaviors.

####  6.2.3 Criticality assessment

The criticality assessment is used to define whether the SoI has failed to
accomplish its requirements. This assessment can be categorized based on the
surrogate measure used to determine the failure and based on whether the
avoidability of the failure is analyzed or not.

The surrogate measures used in the literature of this study can be categorized
as follows:

Collision based: Only a collision is considered when analyzing the performance
of the SoI. In [58], any collision is considered critical by the algorithm,
regardless of how the collision occurs. For this reason, in some of the
results obtained, the pedestrian is considered responsible after studying the
scenario. In [46], the scenario model only allows for the generation of rear-
end collisions caused by the ego vehicle, removing the need of having to
identify the liable actor.

Specification based: [59] uses the rules from RSS [7] to define the improper
actions evaluated in the reward function. The reward function guides the
search for scenarios in which the ego vehicle behaves inappropriately. In
[102], the objective function is based on a Rulebook [149]. In [47], the
behavior of the other actors is optimized to make the system violate its
requirements.

Looking at how the avoidability of the failure is taken into account, the
following classification can be made:

Avoidability not considered: Most of the studies reviewed do not consider
whether the failure could have been avoided or not. They simply compute that
it was a failure.

Avoidability considered: In [66] the aim is to generate test cases in the
boundary where the autonomous vehicle can no longer avoid a collision (almost-
avoidable collisions or near-misses). To achieve that, they propose their
version of RRT with a custom cost function that promotes collisions that are
almost avoidable. [103] proposes a method to find avoidable critical scenarios
using controller synthesis. Avoidability is derived with a controlled
invariant set (a subset of the safe states). States in this set are such that,
as long as the disturbance is within a certain range, it is always possible to
find a control input so that the next state is also in this set.

A complete classification of all the papers analyzed in this study based on
the surrogate measure can be found in Table VI.

####  6.2.4 Coverage

Coverage is not mentioned by most of the papers in this section. Some of them
include a measure to promote better coverage, but none of them address it as
the main focus. In [66], a novelty function is computed based on the
Mahalanobis distance to achieve better coverage and avoid local minimum. [59]
includes a trajectory dissimilarity reward to promote the discovery of highly
diverse failure scenarios.

####  6.2.5 Required information

All the studies analyzed in the section require a simulator. Some studies
require access to the internal state of the simulator, as in [58], while
others treat them as a black-box as in [60]. In [46], as mentioned before, a
backward search is performed, where their method tries to get to a safe state
from a future unsafe state. Due to the impossibility of computing the inverse
of the ACC control law, the authors generate random inputs for the ACC vehicle
to try to get the vehicle in the previous state. Then they simulate forward to
ensure getting into an unsafe state again.

###  6.3 Inductive Reasoning

This section focuses on inductive reasoning methods. With these methods, the
critical (functional or concrete) scenarios are induced from different data
sources. The main data sources identified in the primary studies are
summarized into two types: 1) based on accident scenarios only (Section
6.3.1), and 2) based on various types of data and scenarios (Section 6.3.2).
The former source relies on the accident database, including raw accident
data, accident reports or records, while the latter source refers to the
existing logical or concrete scenarios, natural driving data, traffic data or
sensor data. CSI methods in this cluster are summarized as shown in Fig. 23,
which is also used as a basis for the structure of the following subsections
(data type, reasoning methods and criticality assessment).

Figure 23: Inductive reasoning methods to find critical scenarios

####  6.3.1 Based on accident scenarios

These methods aim to find the common features for critical scenario
identification from a variety of accidental scenarios. As shown in Fig. 23, we
analyzed each type from three perspectives: data type, reasoning methods and
criticality assessment.

Data type:

The articles [110, 99, 100, 100, 54, 55, 56, 73] used accident database (e.g.,
NHTSA[150], GIDAS[151], IGLAD[152] to find the critical pre-crash scenarios.
The used data type of the data source can be mainly grouped into sensor data,
unstructured accident records (e.g., natural language document) and structured
accident records (e.g., meta-data database). The sensor data refers to the
recorded time series data in accidents (such as video data from the equipped
camera sensor and GPS speed, yaw rate, acceleration, and target vehicle
information from equipped radar sensor[55]). The unstructured accident records
are the police accident reports or protocols. In these reports, information
for each scenario includes time, location, vehicle and driver details, before-
crash maneuver, triggering events, crash descriptions of police officers, etc.
These data are used for scenario classification and textual analysis. The
structured accident records are meta data, characteristic data and categorized
attribute data set from database[54, 56, 73]. These data types are mainly used
for clustering analysis.

Reasoning methods:

The main reasoning methods we identified are clustering, textual analysis, and
reconstruction & simulation. As a typical technique for statistical data
analysis, clustering is widely used in many fields and domains. In the
autonomous driving domain, clustering is also used for deriving and extracting
typical or relevant driving scenarios from real driving data or databases
which contain a large number of scenario instances. In this section, as the
first observed reasoning method, clustering was applied to find typical pre-
crash scenarios from accident scenarios databases[54, 56, 153]. The derived
scenarios are mostly functional scenarios, and they can be used to supplement
the existing test suite or as new specific scenarios. In these papers,
clustering methods need to be applied to well-defined data. Therefore the
first step of these methods is to interpret source data into a pre-defined
feature vector (an n-dimensional vector of numerical features that represent
some scenario variables or attributes). The selection of clustering methods
depends on the data types of the features. The data type of each feature can
be either numerical or categorical. If the feature vector contains categorical
data, clustering methods based on euclidean distance cannot be directly
adopted, such as the case in[54]). Clustering methods for categorical data are
introduced in [154]. Features are selected based on different analyses, such
as correlation analysis or relevance analysis [56, 153](Most articles do not
explain how these features are selected, more content regarding features could
be found in section ontology 8.5.) The data is subsequently prepared for
clustering. Typical clustering methods include k-means and k-medoids[54, 56,
153]. After clustering, scenario groups or clusters are formed based on the
clustering results. One typical scenario is selected from one cluster with
different methods. In the end, the derived pre-crash scenarios can be used as
inspiration for the V&V testing activities. In addition, they will be used to
compare against the current test suite and to supplement it.

The second observed method is textual analysis. Since accidents in accident
databases are normally recorded with plain text or structured plain text,
textural analysis or Natural Language Processing (NLP) techniques can help to
extract features of accidental scenarios. Using NLP techniques, the accident
description was parsed according to a pre-defined scenario ontology and
generated typical critical scenarios based on a pre-defined sentence
template[99, 100, 100]. Information about the crash contributing factors (like
weather, lighting, roads and the vehicles involved in the crash) were
extracted from the reports. According to the parsed information, simulations
were generated which can represent the accident scenarios depicted in the
database. Trajectories of dynamic objects are modeled as a vector of way
points. One vehicle in the simulation was then replaced with the ego-vehicle
which was checked then to see if its behavior passes the oracle, which is to
safely reach a goal point within a given time.

The simulation’s primary role in this case is to use the simulator to ensure
the safety and performance of SoI in accident scenarios. The main steps are to
analyze the incident database scenarios, reconstruct them, define the oracles,
and finally execute the simulation with the scenarios. Reconstruction in this
case means that the data described in the database was reconstructed to the
executable scenario in a simulator. Based on simulation results, critical
scenarios are identified using a pre-defined set of KPIs to represent the
criticality. The scenarios are derived from an accident database and the ADS
is run to elicit the corresponding decisions from the system. In[55], the
authors first select accident scenarios from intersection accident data
according to two sensor systems (camera-based and radar-based). All the
selected scenarios are classified into sixteen vehicle-to-vehicle pre-crash
classes. Corresponding Safety Remaining Distances (SRDs) were calculated for
each scenario for the two sensor systems. An SRD greater than zero suggests
that it is possible to prevent an accident. Prevention rates for each system
in each scenario class are calculated and subsequently compared with the
compliance rate of each corresponding scenario to evaluate which sensor system
is necessary for each scenario class.

Criticality assessment: As shown in table VI, since all the papers in this
part took the data source based on accident scenarios only, the criticality
definition of these articles is all related to safety-critical. The papers
[110, 54, 56] use an accident database and adopt clustering methods to find
pre-crash scenarios. Therefore, their criticality definitions are all non-
implementation-specific. On the other hand, [55] and [73] used reconstructed
scenarios and then simulated them using collision as criticality to find
critical scenarios.Therefore, they are all implementation-specific. [99, 100,
100] used NLP techniques and also collision as criticality simulation.
Therefore they are also implementation-specific.

####  6.3.2 Based on various types of data and scenarios

Compared to the previous section, articles [101, 74, 94, 109] in this section
do not use accident databases as the data source to find the critical pre-
crash scenarios. Their used data type can be mainly grouped into sensor data,
traffic data and others.

Data type: The sensor data in this section refers to real sensor data from
field operations. This data is mainly used for the virtual assessment of
ADAS/AD functions to find critical scenarios. As shown in Fig. 23, traffic
data was also used here as a data type, refering to the public map data and
traffic flow data. This data was used for microscopic traffic simulation
(i.e., each vehicle and its dynamics are modeled individually, no detailed
individual sensor models and function inside) parameterization to find
critical scenarios. The other data types are concrete scenarios from available
analyses or simulations. These data types are mainly used for the generation
of new accident scenarios from prerecorded data.

Reasoning methods: The main reasoning methods identified in this section are
safety analysis, Virtual Assessment of Automation in Field Operation (VAAFO),
simulation and others. Safety analysis was used as a method for scenario
analysis and simplification for reducing the number of test scenarios for HAV
test and evaluation[101]. First, the concrete scenarios set are analyzed.
Second, by analyzing concrete scenarios through the traversal of trajectories,
trajectories that lead to collisions or test tasks uncompleted are obtained.
By analyzing these trajectories, the SCPs (scenario characteristic parameters)
of the corresponding scenario are obtained using functional decomposition
[15], combined with fault tree analysis (FTA). By analyzing the overlap or
relationship among the SCPs, the inclusion relationship among scenarios is
obtained according to the SCPs included in different scenarios. By searching
for the combination that contains the fewest scenarios but still covers all
the SCPs, and using this set of scenarios to replace the original combination
of test scenarios, the redundant evaluation scenarios were deleted. Using
simulation as the method, the authors in[74] used public traffic data to
calibrate SUMO (simulation tool, Simulation of Urban MObility) to perform
traffic simulation. Based on the simulation results, the data is post-
processed to extract concrete crash scenarios.

VAAFO [94] is used as a method in parallel with human driving for critical
scenario identification. In VAAFO (Virtual Assessment of Automation in Field
Operation), the vehicle is driven by a human. It receives information from all
sensors, but is not connected to the actuators and instead operates in
parallel while the human driver drives the vehicle. AD functions are running
(simulating) within the perceived world. The trajectory planned by the AD
function is compared with the human driving trajectory. The AD function may
take a different decision than the human driver. This difference may
consequently affect the behavior of other vehicles. The authors in [94] state
that accident scenarios made by human drivers will be recorded by the police.
Potential critical scenarios are filtered further to identify real critical
scenarios after correction of the world model and criticality metrics. The
VAAFO method will identify scenarios that are risky for the AD but not for
human drivers.

As another method, the authors in[109] uses Long Short Term Memory (LSTM)
networks to generate new collision data from prerecorded data. The data used
to train the Recurrent Neural Networks (RNNs) comes from a simulation
environment, but it could also make use of real accident data. In the example
developed in the study, the data includes speed, the direction of vehicles and
traffic light data. Once trained, the network can be used to generate new
collision data starting from an initial seed that contains the initial speed,
direction and traffic light state.

Criticality assessment: The criticality definitions of the articles in this
section are also shown in TABLE VI. The criticality definition in [101] is
based on safety analysis. This paper uses the term hazardous scenario, which
refers to a scenario that may lead to harm, caused by the functional
limitation or failures of the system. A scenario is critical if it is possible
to have a collision in this scenario due to FuSa (Functional Safety) or a
SOTIF problem with the ego vehicle. In [94], the criticality was defined via