Automated Generation of Critical Test Scenarios by Search and Falsification

The problem

The parameter space of even a simple cut-in scenario is too large to test exhaustively, and critical cases are rare. Random or grid testing wastes most simulations on easy cases. Search-based testing treats scenario generation as an optimisation problem that steers simulations towards failures, but how well different methods work, and how diverse their findings are, is an open research question.

Objectives

• Define parameterised logical scenarios and a function under test with formal requirements.
• Formulate criticality objectives, including signal temporal logic robustness.
• Implement random, Latin hypercube, Bayesian optimisation, CMA-ES and genetic search.
• Compare methods on failures found, diversity and time to first failure.
• Validate found scenarios in a second simulator and analyse failure causes.

What you need

Key concepts

Search-based testing

Using an optimisation algorithm to choose scenario parameters that minimise a criticality measure, so simulations concentrate where failures are likely.

Falsification

Searching for an input that violates a formal requirement. A counterexample shows the requirement does not hold for the system.

STL robustness

Signal temporal logic expresses requirements such as 'always gap greater than 2 m'; its robustness is a real number that is negative when violated and measures by how much.

Failure diversity

Many found failures may be near-copies of one case. Clustering failures in parameter space and by cause shows how many distinct problems a method really found.

Step-by-step guide

1. 1

   Define the system and requirements

   Choose a function under test with known weaknesses, such as an ACC with an AEB fallback built from Automated Driving Toolbox examples and your own logic. Formalise three to five requirements in STL-like form: always gap greater than 2 m, deceleration never above a limit unless an imminent collision exists, and the controller reaches steady following within a set time after a cut-in. Define three logical scenarios: cut-in, lead braking and cut-out to a stationary vehicle.

   Checkpoint: Formal requirement statements and three logical scenarios, each with five to eight parameters and ranges.

2. 2

   Build a fast simulation harness

   Implement each logical scenario as a MATLAB function that builds a driving scenario from a parameter vector, runs the closed loop and returns the trajectories. Optimise for speed: use statistical sensor models, a simple vehicle dynamics model and parallel workers with parfor or parsim. Measure the simulation time per run and check determinism by repeating runs. The search budget of later steps depends on this throughput.

   Checkpoint: A harness that runs one scenario in a stated time, deterministically, from a parameter vector.

3. 3

   Define criticality objectives

   Implement objective functions from the trajectories: minimum TTC, minimum gap, required deceleration to avoid collision, and STL robustness for each requirement computed from the signals. Robustness is negative when violated, so minimising it drives the search towards failures. Check that each objective behaves smoothly enough to guide the search by plotting it along one parameter while fixing others, and note where it is flat or discontinuous.

   Checkpoint: Objective landscapes along chosen parameters with flat and discontinuous regions identified.

4. 4

   Implement baseline samplers

   Implement uniform random sampling and Latin hypercube sampling at fixed budgets, for example 200, 500 and 1,000 simulations. Run each with several seeds and record every evaluated point with its objectives. Count failures, defined as negative robustness on any requirement, and record the time to the first failure. These baselines show how rare failures are and set the bar for the search methods.

   Checkpoint: Failure counts and time to first failure for both baselines over several seeds and budgets.

5. 5

   Implement search methods

   Implement Bayesian optimisation with bayesopt on the robustness objective, a genetic algorithm with ga, and CMA-ES through the Python cma package called from your harness or in a Python port. Use identical budgets and parameter bounds. Since a search tends to converge to one failure, add a restart or archive strategy: after a failure is found, penalise its neighbourhood so later evaluations explore elsewhere, and keep all failures in an archive.

   Checkpoint: Each method runs at the same budgets and fills a failure archive, with settings documented.

6. 6

   Measure diversity of failures

   Cluster archived failures in normalised parameter space, for example with DBSCAN, and also by cause, by looking at which requirement failed and what the controller did, such as late brake onset or wrong target selection. Report distinct failure clusters per method and budget. Add a coverage measure of the failure region, such as the share of a fine grid cell set that contains at least one found failure, verified with a dense reference sampling.

   Checkpoint: A table of failures, distinct clusters and failure-region coverage per method and budget.

7. 7

   Run the comparison study

   Run every method on every logical scenario with at least ten seeds per budget. Report mean and spread of failures found, distinct clusters, time to first failure and wall-clock cost, including the optimiser's own overhead for Bayesian optimisation. Use non-parametric statistical tests, such as Wilcoxon rank-sum with effect sizes, to compare methods. Keep raw data so every figure can be regenerated.

   Checkpoint: Comparison tables with statistical test results for each scenario and budget.

8. 8

   Confirm in a high-fidelity simulator

   Re-create a representative sample of found critical scenarios in CARLA, using a common description such as OpenSCENARIO or a parameter mapping, and run the same controller logic in Python. Measure how many failures reproduce and how criticality changes with the different vehicle dynamics and sensors. Analyse failures that do not transfer, because a search can exploit simplifications of the fast model rather than real weaknesses.

   Checkpoint: A transfer rate of found failures from the fast model to CARLA with reasons for non-transfer.

9. 9

   Analyse root causes and fix

   For the main failure clusters, trace the cause in the controller logs: object selection during lane change, braking ramp too slow, or mode-switching delay. Fix one or two causes and rerun the search to check that those clusters disappear and see whether new ones appear. This closes the loop from automated testing back to design, and shows the value of the method beyond counting failures.

   Checkpoint: Root-cause descriptions for each main cluster and search results after fixes.

10. 10

    Write the research chapters

    Write up the problem formulation, objectives, methods, experimental design, results with statistics, transfer study and root-cause analysis. State the threats to validity: simplified models, choice of logical scenarios, objective shape and budgets. Release the harness, search code, raw results and analysis notebooks. Frame conclusions as conditional on the setup rather than general rankings of algorithms. Include a short section on how a validation team could adopt the best-performing method alongside its existing test catalogue.

    Checkpoint: Thesis chapters and a public artefact package that reproduces the main tables and figures.

Testing & validation

• Determinism and throughput of the simulation harness.
• Failure counts and clusters per method compared with random and Latin hypercube baselines.
• Statistical significance and effect sizes of method differences.
• Transfer rate of found failures to CARLA.
• Disappearance of fixed failure clusters after design changes.

Expected results

A comparative study of critical-scenario generation methods with quantified efficiency, diversity and transferability of found failures, plus fixes for real design weaknesses they exposed.

Take it further

• Add surrogate models that predict criticality to skip simulations.
• Use reinforcement learning agents as adversarial traffic participants.
• Search over sensor degradation parameters as well as traffic parameters.
• Extend to multi-objective search balancing criticality and scenario realism.

Viva and review questions

Learn it at DIYguru

These DIYguru courses and programmes teach what this project needs.