Map-Agnostic And Interactive Safety-Critical Scenario Generation via Multi-Objective Tree Search

1. Problem Statement

The deployment of autonomous driving systems (ADS) requires rigorous safety validation through Adaptive Stress Testing (AST), which aims to generate rare, plausible, and safety-critical scenarios (corner cases) to probe system robustness. Existing methodologies face three primary limitations:

• Lack of Realism: Many Reinforcement Learning (RL) approaches prioritize finding any failure, often generating trajectories that are physically implausible or lack naturalistic interaction logic (e.g., agents behaving irrationally just to crash).
• Insufficient Complexity: Methods based on interactive dynamics are often confined to simplified highway environments with few agents, failing to capture the complexity of dense urban traffic flows.
• Map Dependency: Many approaches are tied to specific map geometries, limiting their applicability to diverse geographic regions.

The core challenge is to generate diverse, realistic, and interactive collision scenarios in complex urban environments without compromising the physical feasibility or naturalistic behavior of traffic participants.

2. Methodology

The authors propose a novel framework based on Multi-Objective Monte Carlo Tree Search (MCTS) integrated with the SUMO (Simulation of Urban MObility) microscopic traffic simulator.

A. Problem Formulation

The task is formalized as a Markov Decision Process (MDP) where the goal is to find an optimal action sequence for a "target agent" that maximizes a cumulative reward while other agents follow default behavioral policies (e.g., Extended Intelligent Driver Model - EIDM).

• State Space ($S$): Includes dynamic agents and static environmental elements.
• Action Space ($A$): Discretized steering angles and acceleration rates for the target agent.
• Objective: Maximize the probability of inducing a collision while maintaining trajectory quality.

B. Multi-Objective Evaluation Function

Instead of treating feasibility and naturalism as hard constraints (which can make the search space infeasible), the authors reframe them as optimization objectives within a unified reward function:
$$R(s_t, a_t) = R_{collision} + C_{rationality} + C_{naturalistic}$$

• $R_{collision}$: Rewards collision events and includes a diversity bonus to prevent mode collapse (generating the same crash repeatedly).
• $C_{rationality}$: A cost function penalizing kinematic discomfort (excessive acceleration/deceleration, sharp turns, and large lateral offsets).
• $C_{naturalistic}$: A cost function (negative value) encoding realism using safety metrics like Time-to-Collision (TTC) and Deceleration Rate to Avoid a Collision (DRAC).

C. Hybrid UCB-LCB Search Strategy

To balance exploration (finding new failure modes) and exploitation (finding robust, realistic failures), the paper introduces a hybrid search strategy:

• Upper Confidence Bound (UCB): Used for efficient exploration of the search space, encouraging the selection of less-visited nodes.
• Lower Confidence Bound (LCB): Used for risk-averse decision-making. It selects actions that perform well even under pessimistic estimates, ensuring the final trajectory is robust and realistic.
• Switching Mechanism: The algorithm dynamically switches between UCB and LCB based on tree depth and visitation counts. Early stages use UCB for broad exploration; as the search converges or near critical decision points, it switches to LCB to ensure the selected path is safe and plausible.

D. Map-Agnostic Interactive Simulation

• Map Import: The system imports maps directly from OpenStreetMap (OSM), allowing for arbitrary geographic locations (demonstrated with Hong Kong's complex streets).
• Interaction: Unlike methods that decouple agents, every vehicle in the simulation is powered by SUMO's microscopic models. This ensures that the target agent's actions trigger realistic reactions from surrounding traffic, creating emergent, interactive corner cases.

3. Key Contributions

1. Multi-Objective MCTS Framework: A unified approach that treats trajectory feasibility and naturalistic behavior as optimization objectives rather than hard constraints, enabling the generation of physically plausible collision scenarios.
2. Map-Agnostic Interactive Synthesis: A scalable method that supports arbitrary geographic inputs and leverages microscopic traffic models for all agents, enabling realistic interaction logic in dense urban flows.
3. Hybrid UCB-LCB Strategy: A novel search policy that combines the exploratory efficiency of UCB with the decision-theoretic robustness of LCB, eliminating the need for manual weight tuning in evaluation functions while ensuring high-quality trajectory generation.

4. Experimental Results

The framework was validated in four high-risk accident zones in Hong Kong's urban environment.

• Collision Generation Capability:
  • Achieved an 85% collision failure rate (inducing crashes in 85% of search episodes), significantly outperforming the baseline without multi-objective constraints (75.6%).
  • Generated 428.33 novel collision trajectories per run, demonstrating superior diversity compared to baselines.
• Trajectory Quality & Comfort:
  • The Hybrid UCB-LCB approach produced trajectories with significantly better comfort metrics (lower longitudinal/lateral acceleration, fewer sharp turns) compared to UCB-only methods.
  • Metrics like TTC and DRAC indicated that the generated scenarios remained within acceptable bounds of driving safety requirements, avoiding "suicidal" or irrational maneuvers.
• Scenario Complexity:
  • The generated scenarios exhibited higher total vehicle mileage and CO2 emissions compared to baselines, indicating that the scenarios were not only more complex but also imposed greater operational demands on the System Under Test (SUT).
• Action Distribution:
  • Visual analysis showed that with multi-objective constraints, the search concentrated on hard braking maneuvers (consistent with real-world crash causation), whereas unconstrained searches produced uniform, unrealistic distributions.

5. Significance

This work provides a principled solution for stress-testing autonomous vehicles by bridging the gap between "finding any failure" and "finding realistic, diverse failures."

• Realism over Efficiency: It proves that enforcing naturalistic behavior and physical feasibility does not hinder the ability to find critical corner cases; rather, it enhances the quality and diversity of the discovered failures.
• Scalability: The map-agnostic design allows safety validation to be conducted in any real-world city without retraining models or rebuilding simulation environments.
• Interactive Fidelity: By leveraging microscopic traffic models for all agents, the method captures the complex, emergent behaviors of dense traffic, offering a more rigorous test for ADS than static or scripted scenarios.

In conclusion, this framework offers a robust, scalable, and realistic methodology for generating safety-critical scenarios, essential for the safe deployment of autonomous driving systems in unpredictable real-world environments.