# Applying Heuristics to Generate Test Cases for Automated Driving Safety Evaluation
### Related Work  
Basic requirements for AD testing are summarized in [12], with a major focus on efficiency and effectiveness. Efficiency refers to economic, reproducible, and safe procedures for testing, whereas effectiveness refers to quality assessment through representative, valid, and variable test cases [12]. The need to efficiently and effectively test an immense parameter space applies to the fields of software and AD-system safety testing, in particular. Therefore, a review of the work, related to test case generation methods in software testing, is introduced first, followed by a review of the work that addresses the specific requirements of AD testing as, e.g., including physical dependencies. Therefore, the literature overview is followed by specific work on test case parameterization, in the context of scenario-based testing for automated vehicle safety evaluation.  
Combinatorial approaches in software testing aim at the required testing coverage by systematically combining input parameters under consideration of relevant systems' dependencies and verifying the results of the output data [13; 14; 15; 16]. Sensitivity analysis varies each input parameter individually, while keeping the other parameters constant at their mean value [17]. Heuristics, which is a sub-category of search-based testing, aims at identifying nearly-optimal test cases with a reasonable effort by applying case-specific objective functions and iteratively assigning test cases [14; 18; 19].  
Recent work within the field of scenario-based testing can be clustered into three steps: identification of relevant functional scenarios [20; 21], parameterization of scenarios, and the efficient (virtual) execution of the priorly-defined testing scope. There is an effort to combine the first two steps by directly deriving relevant scenarios for testing from real driving data [22; 23].  
Explicit scenario parameterization for AD safety is commonly supported by expert knowledge, which limits the test suite to scenarios which have been identified as critical in advance [24]. Monte Carlo methods consider the frequency of real-world events for single parameters, but they lack of appropriate consideration of parameter dependencies [25]. This limitation can be overcome by incorporating linear pairwise dependencies between parameters [26], but other possible multi-dimensional dependencies remain out of consideration. Moreover, importance sampling techniques allows a biased sample through the importance function, but do not consider parameter dependencies explicitly [27]. An alternative approach is to fit a Gaussian mixture model, from which relevant test cases (that account for multi-dimensional dependencies) are derived [28]. Although this methodology considers multi-dimensional dependencies, the accurate reflection of safety-relevant corner cases remains questionable.  
Additionally, all the previously introduced methodologies restrict the application of criticality metrics to a posteriori evaluation. The search-based approach, within the domain of automated driving, compromises of the optimization of the AD system's configuration [29; 30], the minimization of required test cases by introducing a cost function [31], or the clustering of scenarios from real traffic data [32].  
To the best knowledge of the authors of this paper, neither search-based techniques for explicit scenario parameterization that addresses all the above limitations nor the sub-category of heuristics have been applied to generate test cases for automated vehicle safety evaluation.