# Applying Heuristics to Generate Test Cases for Automated Driving Safety Evaluation
## 2 Heuristics Methodology
### Heuristic Generation of Test Cases  
This section presents the actual application of a heuristics search-based methodology to generate the test cases, based on the fitted distributions and the regression models previously developed. Since the objective function differs between severity and exposure test cases, an explanation focused on severity is provided first, followed by clarifications concerning exposure. The proposed heuristics methodology is adapted from the software testing related work described in [38] and summarized in Figure 1. The severity test cases were derived from the fitted distributions and the regression models obtained from the critical subset of scenarios. The generation of a single test case comprised three main steps (\"Test case initialization\", \"Test case candidate generation\", and \"Selection of best candidate\"), from which the latter two were part of an iteration loop. Figure 1: Procedure to assign a severity test case to the final test suite. In the \"Test case initialization\" step, an initial solution was obtained by randomization, based on each parameter's fitted distribution. To ensure a wide spread of cases, the initial values for each parameter from the randomization were set to differ at least 20% from the corresponding value of the previous assigned test case. This procedure accounts for the coverage of the search space for the methodology, as well as for the representativeness, by considering the frequency of occurrence of the parameters. The \"Test case candidate generation\" step, applied the initialized random test case from the previous step to generate a pre-determined number of test case candidates. For each candidate, each parameter value from the initial random solution was varied, within a range of 20% around the first obtained randomized solution, as well as based on the fitted distribution. Hereafter, each of these values were assigned the influencing variables, following the regression models that had a minimum R\({}^{2}\)-value of 0.7, and the current values were overwritten, according to the following rules:  
1. Set parameters only influenced by independent parameters;
2. Set parameters influenced by either parameters set, according to rule 2 or by independent parameters;
3. Set all remaining dependent parameters, according to their regression models from lower to higher R\({}^{2}\) order. In the current study, to provide a high coverage when analyzing the parameter combinations as potential test cases, an arbitrary number of 1000 test case candidates was defined. As previously mentioned, the \"Test case candidate generation\" and \"Selection of best candidate\" steps were part of an iteration loop. For the assignment of a test case, the iteration loop was repeated until no better candidate test case could be identified or until an arbitrary number of 100 iteration steps was reached. In either case, the current solution was assigned to the final test suite as the best test candidate. To select the best test case candidate, both safety dimensions were assessed, either being optimized or meeting a pre-defined level. Specifically, for the severe test cases, the RPF was optimized, while a certain newness value was ensured. Therefore, severe test cases that covered the relevant parameter space were derived by this verification-in-the-loop procedure. Subsequently, the process was restarted from the test case initialization step for the next test case. The process to assign exposure test cases to the final test suite is analogue to the process to assign the severity test cases, with the following differences. First, the normal driving subset of scenarios was used to fit the distributions and develop the regression models, instead of the critical subset of scenarios. Second, in the step \"Selection of best candidate\", a maximum RPF value was pre-defined to ensure focus on normal driving scenarios. Furthermore, the newness value was optimized to reach the goal of covering the parameter space of normal driving to the best achievable level.