# Selecting Non-Line of Sight Critical Scenarios for Connected Autonomous Vehicle Testing
## 2 Related Work
### Evolutionary Algorithm  
An evolutionary algorithm is an optimisation-based approach that uses the design variables, the constraints, the fitness function, and the optimiser (i.e., the solver) to search the scenario space for critical scenarios [66]. The fitness function is the quantified criticality measure and has been further discussed in Section 3.1. The problem formulation, particularly the transparency and complexity of the underlying models, has a significant impact on the optimiser chosen. When estimating criticality measures, a simulator is frequently used. Because of high model complexity, simulation and system analysis of the system of interest (SoI) can be computationally expensive in many cases. As a result, the SoI's behaviour is treated as a black box. Thus, the corresponding search procedure can be considered as a black-box optimisation problem. The relationship between the input (i.e., scenario parameters) and the output (i.e., simulation results) for a black-box optimisation problem can only be analysed by external observation through simulations [67]. Various heuristic methods, such as a genetic algorithm [68; 69; 70], Bayesian optimisation [71; 72] and simulated annealing [68], can be used to approximate the fitting function and find the global minimum iteratively to solve this problem. Furthermore, domain-specific heuristic techniques, such as rule-based searching [73], heuristic simulation-based gradient descent [74] and zoom-in sampler [75], help to identify multiple local minimums of feasible solutions. [PERSON] et al. [76; 77] formulated scenario searching as a two-step optimisation problem. The first step in the optimisation process is to find as many local optimal solutions as possible. The neighbourhood of the local optimal solutions is searched in the second step to find all the scenarios whose criticalities are within a certain threshold. It is a well-known approach to use genetic algorithms for test generation and optimisation. [PERSON] [78] demonstrated in his Ph.D. thesis in 1995 that using genetic algorithms to generate test data is an order of magnitude more efficient than using random selection. [PERSON] et al. [69] were also inspired by the idea of using evolutionary algorithms. They demonstrated in their paper that evolutionary algorithms are well-suited for testing vision-based control systems and characterising critical input space regions. In addition, [79] proposed a genetic algorithm-based approach for testing an autonomous parking system. [PERSON] et al. [80] used a similar technique to perform evolutionary functional testing of a vehicle brake assistant system, concluding that system errors discovered by evolutionary function testing are fairly unlikely to be discovered using traditional testing techniques. \begin{table}
\begin{tabular}{c c c c} \hline
**Indicator** & **Description** & **Collision Type** & **Reference** \\ \hline \multirow{4}{*}{Time-to-accident (TA)} & The time-to-accident (TA) is the amount of time it takes for an accident to occur from the time one of the road users begins an evasive action and continues at the same speed and direction. & As a result of a rear-end collision, turning/weaving, hitting objects/parked vehicles, crossing, hitting a pedestrian and vehicle–vehicle collision. & [61; 62] \\ \hline \multirow{4}{*}{Post-encroachment time (PET)} & The time between the moment that a road user (vehicle) leaves the area of potential collision and the other road user arrives at the collision area. & Mostly for right-angle or crossing crashes that result in a pedestrian being hit. Head-on collision when merging/diverging (to a certain extent). & [63; 64] \\ \cline{1-1} \cline{2-4}  & & & \\ \cline{Acknowledging the power of evolutionary algorithms to search through solution spaces to identify optimum solutions based on certain criteria and associated constraints, in this research a genetic algorithm approach is used to select NLOS safety-critical scenarios which require communication in order to avoid a collision.