# Selecting Non-Line of Sight Critical Scenarios for Connected Autonomous Vehicle Testing
## 3 Methodology
### Genetic Algorithm  
A GA is an optimisation algorithm that is utilised in the current context to identify a set of safety-critical scenarios from the set of all NLOS scenarios for a given road layout. For proof of concept, this research will use a T-junction as an example of NLOS scenarios as illustrated in Figure 6. This scenario consists of a road layout as well as an obstacle to obscure vehicle perception. The GA will seek to identify critical scenarios by determining the fitness value of a scenario given a set of input parameters. For the purpose of this experiment, we will fix the number of road users to two: the ego vehicle and the connected autonomous vehicle. The speed ranges use UK government data [89] acquired from the probability of speed distribution given a particular speed limit; a function for the probability distribution is an input to the GA. The scenario space for each individual scenario is made up of a set of parameters which are inputted to the GA. The scenario space has these parameters:  
* Position of the ego vehicle [X\({}_{\text{Ego}}\), Y\({}_{\text{Ego}}\), Z\({}_{\text{Ego}}\)]. * Position of the CAV [X\({}_{\text{CAV}}\), Y\({}_{\text{CAV}}\), Z\({}_{\text{CAV}}\)]. * The position is based on bounding box range as shown in Figure 2. Upper and lower limits for the X and Y position of the ego vehicle and CAV are within NLOS range. As mentioned above, this has been determined through simulation. * Speed of the ego vehicle. * Speed of the CAV. The speed for the initial population is selected from the speed distribution depicted in Figure 7. The likelihood of a speed being selected is directly proportional to its probability within the speed probability distribution. A MATLAB function has been defined to facilitate this selection. Algorithm 1 below shows the genetic algorithm steps. Figure 6: T\(-\)junction scenario. Algorithm 1 below shows the genetic algorithm steps. ```
Input: Population size, \(n\) Maximum number of iterations, MAX Output: Critical scenario Begin: Generate initial population (randomly) of \(n\) chromosomes Yi (\(i\) = 1, 2,..., \(n\))  Set iteration counter \(t\) = 0  Compute the fitness values of each chromosome while (\(t\) < MAX) Step 1: The individuals are ranked according to fitness value Step 2: The elitism rate is checked and, depending on the value, the appropriate number of individuals are taken over to the next generation Step 3: Select a pair of chromosomes from the current generation based on fitness Step 4: Apply crossover operation on the selected pair with crossover probability Step 5: Select a chromosome from the current generation based on fitness Step 6: Apply mutation on the selected individual with mutation probability Step 7: Replace the old population with a newly generated population Step 8: Increment the current iteration \(t\) by 1  end while  return the critical scenario end
```  
**Algorithm 1**Genetic algorithm for NLOS critical scenario selection  
The input parameters to the GA are as follows: population size, number of generations, probability of crossover (Pc), probability of mutation (Pm) and elitism rate (Er). The values  
Figure 7: Speed distribution for different speed limits. Adopted from [89]. for these have been determined empirically through experimentation. The chromosomes are represented using real-value encoding. The genes of each chromosome include _Position of the Ego_, _Position of the Car_, _Speed of the Ego and Speed of the Car_. The fitness function evaluates the fitness value f (Y) of each individual, Y\({}_{i}\), in the population. To determine the fitness value of each individual, the metric that represents the criticality of the scenarios is used (as discussed in Section 3.1). The fitness value is then evaluated (by using a normalised value of the difference between TTC and TST) by comparing the TTC and the TST (TTC < TST). The lower the fitness value, the lower the difference between TTC and TST. A roulette wheel selection function [90] is used to select individuals with lower fitness values for the next generation.