Search-Based Testing (SBT) and the Curse of Dimensionality

Scenario Hierarchy and ODD Context

Every AV operates within an Operational Design Domain (ODD), defining the conditions under which the system is intended to operate—roads, traffic rules, weather, and environmental constraints. Within this ODD, individual situations are captured as scenarios at different abstraction levels:

• Abstract: Human-readable description (e.g., "uncontrolled intersection with cross traffic").
• Logical: Parameter ranges that define the abstract scenario (e.g., vehicle speeds, positions, accelerations).
• Concrete: Specific parameter assignments executable in simulation.

In this article, the intersection scenario we use as an example is one logical scenario within its ODD.

The Curse of Dimensionality: 4-Car Intersection Example

Let’s look at a standard unsignalized intersection with four vehicles (ego + three traffic participants). We fix the ego vehicle's acceleration (allowing the planner to control it) but vary its initial state. This gives us:

• Ego Vehicle: Initial velocity (v₀) and Initial position (p₀) [2 parameters]
• 3 Traffic Participants: Initial velocity (v₀), Initial position (p₀), and Acceleration (a₀) each [3 × 3 = 9 parameters]

That gives us an 11-dimensional space to cover. With a coarse discretization of 10 steps per parameter, brute-force simulation would require:

10¹¹ = 100,000,000,000 concrete scenarios

And this toy setup is aggressively simplified. We have not modeled:

Yet even this minimal scenario already produces a continuous parameter space large enough that naive brute sweeps are completely impossible to compute.

Assuming an optimistic simulation engine running 100 simulations per second, the runtime would be:

100,000,000,000 scenarios / 100 sims/sec = 1,000,000,000 sec ≈ 31.7 years!

Note: Achieving 100 simulations per second is only feasible with lightweight, low-fidelity simulations. In reality, each scenario would take much longer to simulate.

Even under optimistic assumptions, brute-force evaluation of all possible combinations doesn't scale.

Why Brute-Force Fails

Running every single variation is a massive waste of resources on uninteresting scenarios where the AV performs well. The critical events — collisions, near-misses, and edge cases — occupy only small subregions of the parameter space. Identifying them requires a method that focuses exploration where it matters.

The solution: instead of evaluating everything, evaluate only what's likely to matter.

Why Search-Based Testing Works

SBT treats testing like an optimization problem, typically using genetic algorithms, Bayesian optimization, or surrogate models, guided by a Key Performance Indicator (KPI). For example:

• KPI: Minimum bounding box distance during an intersection crossing.
• Objective: Minimize this distance to uncover near-misses or collisions.

Iterative Process of SBT:

1. Coarse Sampling: Sample initial points across the logical scenario space.
2. KPI Evaluation: Run simulations and compute the KPI for each scenario.
3. Surrogate Model Training: Build a fast approximation (e.g., Gaussian Process, neural network) of the KPI function based on evaluated samples. This model predicts KPI values without running expensive simulations.
4. Region Refinement: Use the surrogate model to identify promising regions and focus subsequent samples where the KPI indicates potential critical events.
5. Continuous Improvement: As new samples are evaluated, the surrogate model is continuously retrained and refined, improving prediction accuracy in critical regions while maintaining computational efficiency.
6. Repeat: Iterate between surrogate updates and targeted sampling until convergence or computational budget is exhausted.

Surrogate models are the secret weapon of production SBT: instead of running expensive simulations for every candidate scenario, the search algorithm queries a fast approximation to eliminate obviously uninteresting regions. Only the most promising candidates get full simulation treatment, reducing evaluations potentially by multiple orders of magnitude. That said, building a good surrogate is easier said than done — getting the training set right is half the battle.

Illustration of SBT vs Full Grid Sampling:

The Critical Role of KPI Selection

The KPI is the compass guiding the search. For the simple intersection scenario above, minimum bounding box distance works well, but real-world scenarios are rarely this straightforward—different scenario types demand different metrics:

• KPI Sensitivity: Time-to-collision (TTC) vs. distance-to-collision yield fundamentally different critical scenario sets—TTC prioritizes velocity mismatches, while distance emphasizes spatial proximity.
• Multi-Objective KPIs: Combine multiple safety concerns (e.g., collision risk + passenger comfort + regulatory compliance) into a weighted composite metric, enabling the search to balance competing objectives.
• Domain Expertise Required: Each logical scenario type (lane change, merge, pedestrian crossing) needs carefully designed KPIs that capture the relevant safety properties.

KPI Design Principles: What Works and What Fails

Designing KPIs is where theory meets reality. The textbooks won't tell you this, but the most common failure mode isn't mathematical—it's choosing metrics that optimize for something you don't actually care about.

Monotonicity and Gradients:

• ❌ Poor Choice: Binary crash/no-crash flag (discontinuous). The search algorithm has no gradient to follow near the safety boundary—it's blindly guessing.
• ✅ Better Choice: Minimum distance during trajectory (continuous). Provides smooth gradient that guides the search toward critical boundaries, even from safe initial conditions.

Other Critical Considerations:

Beyond continuity, effective KPIs must be resistant to exploitation—a metric that only measures time-to-collision can be gamed by scenarios where vehicles never enter the intersection. Teams often don't discover this until weeks into a test campaign, when they realize their "critical scenarios" are just clever ways to avoid the intersection entirely.

KPIs should also capture temporal dynamics over entire trajectories, not just static spatial snapshots. Where possible, leverage formal safety frameworks like RSS (Responsibility-Sensitive Safety) to provide regulation-aligned, interpretable metrics.

Interactive Demonstration

In the following simplified intersection with two vehicles, you can play with initial velocities using grid resolutions from 20–80 steps. The simulation uses realistic bounding box collision detection, where a crash occurs when the vehicle bounding boxes actually touch or overlap. Two strategies are compared:

• Full grid sweep (exhaustive brute-force sampling)
• SBT refinement (adaptive sampling guided by the KPI)