Technical Summary: Automatic Testing of Interacting Autonomous Vehicles

Problem Statement

Autonomous vehicles (AVs) require rigorous testing to ensure safety standards are met. While scenario-based testing in virtual simulation is a cost-effective alternative to field testing, current state-of-the-art approaches predominantly focus on testing a single AV (the "ego-vehicle") against pre-programmed Non-Playable Characters (NPCs) or simplistic traffic models. The authors argue that these single-AV approaches fail to capture critical safety issues that emerge from the mutual interactions of multiple AVs. As the number of AVs on public roads increases, the likelihood of hazardous situations arising from complex, multi-way interactions grows. Existing methods often overlook these emergent behaviors because they do not account for the combinatorial explosion of interactions or the fact that an AV's trajectory adjustments depend on the real-time reactions of other AVs, not just static or pre-scripted obstacles.

Methodology: EVITA

To address these limitations, the authors propose EVITA (EVolutionary Interaction Testing Approach), a methodology for automatically generating critical driving scenarios involving multiple interacting AVs.

Core Concept: Interaction Testing

EVITA introduces "interaction testing," a methodology designed to systematically explore emergent behaviors resulting from the interplay between AVs and other traffic-influencing factors (e.g., traffic lights, road signs, other vehicles). Unlike approaches that simply maximize collision counts, EVITA focuses on maximizing the variety and number of interactions while minimizing scenario complexity (i.e., the number of AVs required).

Interaction Identification

EVITA identifies interactions by analyzing the "sense-plan-act" loop of AVs. It detects an interaction when:

1. Trajectory Replanning (C1): An AV significantly alters its planned trajectory between consecutive time steps (measured via cumulative Euclidean distance between predicted states).
2. Causality (C2): The replanning is likely caused by a specific scenario element (e.g., another vehicle, a traffic light, or a road sign).

Interactions are classified into nine types (Forward, Forward-Left, Forward-Right, Left, Right, Backwards, etc.) based on the relative change in the planned trajectory. These are mapped onto a 2D "interaction map" to quantify the diversity of interactions triggered.

Search Algorithm

EVITA formulates scenario generation as a multi-objective optimization problem solved using the NSGA-II (Non-Dominated Sorting Genetic Algorithm II) algorithm. The algorithm evolves a population of scenarios to optimize three conflicting objectives:

1. Interaction Fitness (Maximize): Maximize the cumulative number of interactions observed.
2. Interaction Diversity Fitness (Maximize): Maximize the variety of interaction types (measured by the distance of the current interaction vector from previously generated scenarios).
3. Number of Vehicles Fitness (Minimize): Minimize the number of AVs in the scenario to keep tests simple and debuggable.

The search space includes variables for AV initial positions, velocities, goal areas, and traffic light configurations (colors and durations). EVITA includes a validation step to ensure generated scenarios are valid (e.g., goals are reachable, no initial collisions) and interesting (e.g., AVs are not spawned directly inside their goals).

Experimental Evaluation

The authors evaluated EVITA against DoppelTest, the only known state-of-the-art open-source approach capable of generating multi-AV scenarios. The evaluation utilized two distinct experimental setups:

• Highway/Suburban: Using the FrenetiX motion planner and CommonRoad simulation framework across five road networks (Cho, Cologne, US101 variants).
• Urban: Using Baidu Apollo and a simulation framework based on the Borregas Ave urban block.

Key Results

The experimental results, analyzed using statistical tests (Mann-Whitney U test), demonstrate that EVITA outperforms DoppelTest in several key areas:

• Interaction Exposure (RQ1): EVITA consistently triggers a higher total number of interactions and a broader diversity of interaction types across highway and suburban networks. In urban settings, while DoppelTest showed a marginal advantage in variety, it did so only by generating significantly more complex scenarios with more vehicles.
• Collision Exposure (RQ2): EVITA generates more unique collisions (classified by point of impact, relative velocity, and angle) than DoppelTest, particularly in highway and suburban environments.
• Traffic Rule Violations (RQ3): In urban scenarios, EVITA detected significantly more violations of traffic lights, stop signs, and speed limits compared to DoppelTest.
• Scenario Complexity (RQ4): EVITA generates simpler scenarios, typically involving fewer vehicles (2–4) to trigger critical interactions, whereas DoppelTest relies on scenarios with higher vehicle counts (5–8) to achieve similar coverage.
• Effectiveness (RQ5): EVITA demonstrates high effectiveness, generating a high volume of valid scenarios (negligible invalid scenario rate) within the allocated time budgets (3 hours for FrenetiX, 12 hours for Apollo).

Significance and Contributions

The paper claims the following contributions to the field of AV testing:

1. Definition of Interaction Testing: It defines a methodology for exploring emergent behaviors caused by the interplay of multiple AVs and environmental factors, moving beyond single-vehicle testing.
2. The EVITA Approach: It proposes a multi-objective search-based approach that systematically generates critical scenarios involving multiple AVs, balancing interaction diversity with scenario simplicity.
3. Extensive Evaluation: It presents a rigorous evaluation across multiple simulators (CommonRoad/FrenetiX and Baidu Apollo), diverse road environments (highway, suburban, urban), and different AV systems.

The authors conclude that testing AVs against system-level interactions is essential for revealing safety-critical hazards that single-AV testing misses. EVITA provides a foundation for testing AVs at scale, particularly for interactions between vehicles from different manufacturers or with different driving policies, without requiring complex, high-fidelity models of all road users. The source code and replication package are made available to support further research.