Performance Comparison of Two Search-Based Testing Strategies for ADAS System Validation

Florian Klück, Martin Zimmermann, Franz Wotawa, Mihai NicaICTSS 2019 · DOI

TL;DR

This paper tackles the challenge of efficiently testing Advanced Driver Assistant Systems (ADAS) by comparing genetic algorithms (GA) and simulated annealing (SA) for automatically generating critical test scenarios. The GA emerged as the most effective, requiring significantly fewer test executions to identify scenarios that trigger ADAS malfunctions, highlighting its suitability for complex automotive validation.

What Problem Does This Paper Address?

The increasing complexity and autonomy of vehicles, particularly with the advent of Advanced Driver Assistant Systems (ADAS), necessitates rigorous testing to ensure safety. ADAS functions, like lane keeping and emergency braking, operate within a vast and continuous input domain, making traditional testing methods insufficient. The core problem is how to efficiently and automatically discover critical driving scenarios – those that push the ADAS to its limits and potentially lead to near-crash or crash situations – to validate its functionality. This is crucial because failing to identify such scenarios can have severe consequences. The paper aims to find an automated method for generating these critical test scenarios by comparing different search-based testing strategies.

Methods

The paper compares three search-based testing strategies: a genetic algorithm (GA), simulated annealing (SA) (both a basic version and an improved version by Locatelli), and random testing (RA). These algorithms are used to optimize test parameters, aiming to find parameter combinations that lead to critical driving scenarios.

  • Genetic Algorithm (GA): Inspired by natural selection, the GA starts with a population of potential solutions (parameter sets) and iteratively improves them through selection, crossover, and mutation.
  • Simulated Annealing (SA): This algorithm is inspired by the metallurgical process of heating and cooling metals. It explores the solution space by accepting not only better solutions but also, with a certain probability, worse solutions, especially at higher "temperatures" (iterations), to avoid getting stuck in local optima. The Locatelli version of SA shrinks the search space around the current solution as the temperature decreases.
  • Random Testing (RA): This serves as a baseline, where parameter values are chosen randomly.

The core of the methodology involves setting up a simulation framework using AVL Model.Connect and Vires VTD to execute these generated test scenarios. The criticality of a scenario is evaluated using Time-to-Collision (TTC), with a TTC below 0.3 seconds indicating a critical situation. The performance metric is the number of test executions required to find such a critical scenario.

Datasets

Not discussed in the paper. The paper uses a simulated environment for testing ADAS functions, specifically an autonomous emergency braking (AEB) system.

Key Insights and Ideas

  • GA's Efficiency: The genetic algorithm consistently outperformed both simulated annealing and random testing in terms of the number of test executions needed to find critical scenarios. This suggests that its evolutionary approach is particularly well-suited for navigating the complex, multi-dimensional parameter space of ADAS testing.
  • SA's Inconsistency: While simulated annealing can find solutions, its performance was highly variable. It either found solutions quickly or failed to find them within the iteration limit, indicating a sensitivity to the initial solution and the potential for getting trapped in local optima.
  • The Importance of Search Strategy: The comparison highlights that simply exploring the parameter space randomly is less efficient than guided search strategies like GA and SA. However, the effectiveness of guided search depends heavily on the algorithm's design and its ability to escape local optima.
  • TTC as a Robust Oracle: Using Time-to-Collision (TTC) as the evaluation metric (oracle function) proved effective in identifying critical rear-end collision scenarios, providing a clear and quantifiable measure of test scenario criticality.

Key Results

The study compared the performance of GA, SA (basic and Locatelli's improved version), and RA over seven experimental runs for each method, with a maximum of 500 iterations.

  • Genetic Algorithm (GA): Required the fewest test executions on average (42) and median (35) to find a critical scenario. It also demonstrated consistent performance across all runs.
  • Random Testing (RA): Required an average of 84 executions and a median of 53. While less efficient than GA, it was more consistent than SA.
  • Simulated Annealing (SA):
    • Basic SA: Required an average of 269 executions and a median of 213.
  • Locatelli's SA: Required an average of 229 executions and a median of 49. This version showed a significant gap between its average and median results, indicating its high variability.

The GA consistently found critical scenarios with the lowest number of required test executions.

Limitations and Future Work

  • Limited Data Set: The authors acknowledge that the results from only seven test runs per method might not be sufficient for definitive statistical analysis.
  • SA's Sensitivity: The simulated annealing algorithms, particularly Locatelli's version, showed a strong dependence on the initial solution, leading to either rapid success or failure.
  • Future Work:
    • Further investigate and improve the Locatelli SA by introducing a new internal stopping criterion that restarts the algorithm if no suitable solution is found within a certain number of test executions.
  • Conduct larger experiments with more and larger case studies from the autonomous driving domain to further validate the findings.
  • Explore other search-based optimization techniques.

Summary updated

BibTeX
@inproceedings{kluck2019performance,
  author = {Florian Klück and Martin Zimmermann and Franz Wotawa and Mihai Nica},
  title = {{Performance Comparison of Two Search-Based Testing Strategies for ADAS System Validation}},
  booktitle = {ICTSS},
  year = {2019},
  doi = {10.1007/978-3-030-31280-0\_9},
}
Figure