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

Wenyun Li, Zejian Deng, Chen Sun · 2026

Read Map-Agnostic And Interactive Safety-Critical Scenario Generation via Multi-Objective Tree Search by Wenyun Li, Zejian Deng, Chen Sun (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-03978.txt.

Introduction

Wenyun Li and others present a method for generating safety-critical traffic scenarios via multi-objective Monte Carlo Tree Search. The method turns trajectory feasibility and naturalistic conduct into tuning goals inside one tests function, surfacing varied collision events while keeping realism. A hybrid Upper Confidence Bound and Lower Confidence Bound search plan balances exploratory speed with risk-averse choice-making. Tests in four Hong Kong accident zones show an 85% collision failure rate with strong feasibility and comfort.

Catalog record

CREATORWenyun Li, Zejian Deng, Chen Sun
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29252
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.03978

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Map-Agnostic And Interactive Safety-Critical Scenario Generation via Multi-Objective Tree Search Wenyun Li, Zejian Deng, Chen Sun Abstract Generating safety-critical scenarios is essential for validating the robustness of autonomous driving systems, yet existing methods often struggle to produce collisions that are both realistic and diverse while ensuring explicit interaction logic among traffic participants. This paper presents a novel framework for traffic-flow level safety-critical scenario generation via multi-objective Monte Carlo Tree Search (MCTS). We reframe trajectory feasibility and naturalistic behavior as optimization objectives within a unified evaluation function, enabling the discovery of diverse collision events without compromising realism. A hybrid Upper Confidence Bound (UCB) and Lower Confidence Bound (LCB) search strategy is introduced to balance exploratory efficiency with risk-averse decision-making. Furthermore, our method is map-agnostic and supports interactive scenario generation with each vehicle individually powered by SUMO’s microscopic traffic models, enabling realistic agent behaviors in arbitrary geographic locations imported from OpenStreetMap. We validate our approach across four high-risk accident zones in Hong Kong’s complex urban environments. Experimental results demonstrate that our framework achieves an 85% collision failure rate while generating trajectories with superior feasibility and comfort metrics. The resulting scenarios exhibit greater complexity, as evidenced by increased vehicle mileage and CO 2 emissions. Our work provides a principled solution for stress testing autonomous vehicles through the generation of realistic yet infrequent corner cases at traffic-flow level. I Introduction In modern transportation systems, intelligent agents are increasingly assuming roles historically entrusted to human operators [ 15 ] . Irrespective of whether such systems are model-based or data-driven, their deployment necessitates rigorous safety validation [ 12 ] . Adaptive Stress Testing (AST) addresses this imperative by generating rare yet plausible extreme scenarios designed to probe the robustness and safety of a System Under Test (SUT)—typically an autonomous vehicle, robot, or alternative control policy. Accordingly, the systematic generation of realistic yet infrequent corner cases constitutes a pivotal endeavor in the safety assurance pipeline. Existing methodologies have leveraged Reinforcement Learning (RL) to synthesize trajectories for stress testing, wherein reward functions incentivize agents to actively and efficiently traverse the state space in pursuit of trajectories that elicit failure or performance degradation in the SUT. Notwithstanding their efficacy, these approaches lack explicit objectives on states antecedent to the terminal condition, thereby compromising both the plausibility and naturalistic fidelity of the generated search outcomes. In contrast, the Multi-Objective Monte Carlo Tree Search (MCTS) framework proposed herein incorporates smoothness and feasibility metrics alongside rationality and naturalistic criteria as explicit constraints during trajectory optimization, thereby ensuring that resultant collision scenarios manifest both realism and plausibility. Furthermore, empirical evaluations substantiate that the traffic-flow level scenario generation methodology adopted in this work not only yields collision events but also produces scenarios of heightened complexity and emissions demands, thereby imposing more stringent requirements on the SUT’s capacity to navigate intricate traffic conditions with augmented efficiency. A fundamental limitation in data-driven scenario generation approaches resides in their propensity to execute scene modifications either devoid of physical plausibility and interactive dynamics or accompanied by only tenuous physical guarantees. Conversely, methodologies grounded in interactive dynamics offten suffer from insufficient scenario complexity—confined to simplistic highway configurations and limited agent counts—rendering them ill-equipped to accommodate the urban traffic flows confronting contemporary autonomous driving systems. Table I summarizes the feature comparison between our approach and prior studies, highlighting these gaps in previous work. To surmount these shortcomings, the present study directly imports maps from Hong Kong’s characteristically narrow and congested streetscape, wherein vehicles within the search space are instantiated as individual models powered by the SUMO (Simulation of Urban MObility) [ 2 ] simulator. This configuration facilitates interactive search within densely interactive scenarios, engendering corner cases that manifest increasingly realistic and plausible collision events. Upper Confidence Bound (UCB) [ 8 ] constitutes a prevalent heuristic within MCTS, facilitating efficient exploration of the search space. However, within the specific context of collision scenario generation, considerations must extend beyond mere search efficiency to encompass the optimization of multiple objectives embedded within generated trajectories. To address this exigency, we employ Lower Confidence Bound (LCB) to effectuate risk-averse yet robust decision-making, selecting actions whose performance remains satisfactory even under pessimistic estimates, as illustrated in Figure 1 . This dual strategy judiciously balances the exploratory vigor of UCB with the decisional robustness afforded by LCB, while obviating the arduous task of tuning evaluation function weights encountered in MCTS frameworks. The principal contributions of this work are threefold: • Multi-Objective Trajectory Generation: We introduce a multi-objective MCTS framework that explicitly enforces smoothness, feasibility, rationality, and naturalistic criteria during optimization, thereby generating traffic-flow level corner cases that are both physically plausible and behaviorally realistic. • Map-Agnostic Interactive Scenario Synthesis: Our methodology accommodates arbitrary geographic inputs by directly importing maps from diverse regions—exemplified herein through Hong Kong’s intricate streetscape—thereby demonstrating broad applicability. By leveraging SUMO-powered individual vehicle models within the search space, we enable interactive scenario exploration wherein generated corner cases emerge from logically consistent vehicle interactions. • Hybrid UCB-LCB Search Strategy: We propose a hybrid search strategy that combines UCB’s exploratory efficiency with LCB’s decision-theoretic robustness. This integrated approach not only ensures efficient traversal of the search space but also enhances decision stability under uncertainty, while simultaneously circumventing the parameter-tuning overhead associated with conventional evaluation functions in MCTS. The rest of the paper is organized as follows: Section II introduces the related work. Section III presents the proposed framework, detailing its core modules. Section IV describes the experimental setup, presents validation results, and provides in-depth analysis of the findings. Section V concludes the paper with a summary of key contributions and discusses promising directions for future research. Fig. 1 : Illustration of best path selection in tree search. The color intensity of each node represents its LCB value, with darker shades indicating higher (i.e., more favorable) lower confidence bounds. The red segments denote the selected best path, where the UCB-LCB strategy preferentially selects nodes with larger LCB values during final generation, thereby yielding more realistic collision scenarios. TABLE I : Feature comparison with prior work Method Smooth/Feasible Rational/Naturalistic Ours ✓ ✓ AdvSim [ 18 ] ✓ Adaptive Search [ 5 ] ✓ Learning2Collide [ 4 ] ✓ ReGentS [ 20 ] ✓ AccidentSim [ 21 ] ✓ ✓ Method Interactive Map Import Scale Ours ✓ ✓ Traffic Flow AdvSim [ 18 ] 1-5 Agents Adaptive Search [ 5 ] ✓ 1-5 Agents Learning2Collide [ 4 ] 2 Agents ReGentS [ 20 ] Max 32 Agents AccidentSim [ 21 ] 1-4 Agents II Related Work Adaptive Stress Testing has emerged as a prominent framework for identifying safety-critical failures in autonomous systems across aerospace, driving, and maritime domains. Early work by Lee et al. [ 11 ] applied AST with Monte Carlo Tree Search to overcome partial observability in air collision avoidance systems. Subsequent research has extended this paradigm across diverse domains and fidelity levels. In autonomous driving, multiple studies have leveraged AST within simulation environments such as CARLA and Highway-Env to generate challenging scenarios for various controllers, ranging from PID and intelligent driver models to deep reinforcement learning policies [ 4 , 9 , 5 , 18 ] . Methodological advancements include refined reward design that evolves from simple collision detection to considering longitudinal and lateral safety margins

Read the complete text