FREA: Feasibility-Guided Generation of Safety-Critical Scenarios with Reasonable Adversariality
Authors: Keyu Chen
Yuheng Lei
Hao Cheng
Haoran Wu
Wenchao Sun
Sifa Zheng
Venue: CoRL 2024 (2024)
Keywords: Feasibility
Scenario Generation
Autonomous Driving
TL;DR: FREA incorporates feasibility as guidance to generate adversarial yet AV-feasible, safety-critical scenarios for autonomous driving.

Abstract: Generating safety-critical scenarios, which are essential yet difficult to collect at scale, offers an effective method to evaluate the robustness of autonomous vehicles (AVs). Existing methods focus on optimizing adversariality while preserving the naturalness of scenarios, aiming to achieve a balance through data-driven approaches. However, without an appropriate upper bound for adversariality, the scenarios might exhibit excessive adversariality, potentially leading to unavoidable collisions. In this paper, we introduce FREA, a novel safety-critical scenarios generation method that incorporates the Largest Feasible Region (LFR) of AV as guidance to ensure the reasonableness of the adversarial scenarios. Concretely, FREA initially pre-calculates the LFR of AV from offline datasets. Subsequently, it learns a reasonable adversarial policy that controls critical background vehicles (CBVs) in the scene to generate adversarial yet AV-feasible scenarios by maximizing a novel feasibility-dependent objective function. Extensive experiments illustrate that FREA can effectively generate safety-critical scenarios, yielding considerable near-miss events while ensuring AV's feasibility. Generalization analysis also confirms the robustness of FREA in AV testing across various surrogate AV methods and traffic environments.

FREA: Feasibility-Guided Generation of Safety-Critical Scenarios with Reasonable Adversariality
Keyu Chen', Yuheng Lei", Hao Cheng', Haoran Wu', Wenchao Sun', Sifa Zheng!
School of Vehicle and Mobility, Tsinghua University Thhe University of Hong Kong
Generating safety-critical scenarios, which are essential yet difficult collect scale, offers an effective method evaluate the robustness of au- tonomous vehicles (AVs). Existing methods focus optimizing adversariality while preserving the naturalness of scenarios, aiming to achieve a balance through data-driven approaches. However, without an appropriate upper bound for adver- sariality, the scenarios might exhibit excessive adversariality, potentially leading to unavoidable collisions. In this paper, we introduce FREA, a novel safety-critical scenarios generation method that incorporates the Largest Feasible Region (L.R) of AV as guidance ensure the REasonableness of the Adversarial scenarios. Concretely, FREA initially pre-calculates the LFR of AV from offline datasets. Subsequently, it learns reasonable adversarial policy that controls the scene's 's critical background vehicles (CBVs) to generate adversarial yet AV-feasible sce- narios by maximizing a novel feasibility-deeenden adversarial objective function. Extensive experiments illustrate that FREA can effectively generate safety-critic scenarios, yielding considerable near-miss events while ensuring AV's feasibility, Generalization analysis also confirms the robustness of FREA AV testing across various surrogate AV methods and traffic environments. For more information, visit the project website: https:/currrcche777.. http:///uurrchheee7.gggttiddEEE
Abstract:
Keywords: Feasibility, Scenario Generation, Autonomous Driving
1 Introduction
Rapid advancements in Al-driven autonomous driving technologies have enabled autonomous ve- hicles (AVs) to operate efficiently, safely, and comfortably in most daily scenarios [1]. However, their performance in the complex real-world remains uncertain due to safety-critical yet rare sce- narios, which are hard collect scale. Accurately generating these safety-critical scenarios and evaluating the AV performance is crucial for advancing autonomous driving systems [2].
Existing approaches primarily utilize metrics such as collision rate or minimum distance to AV to measure adversariality [3, 4, 5, 6]. These approaches aim to increase adversariality while comply- ing with specific constraints. Methods based on Deep Generative Models (DGM) typically employ behavioral characteristics of traffic participants from natural datasets [6, 7] or apply domain-specific knowledge [8, 10] to guide the generation of adversarial scenarios. Similarly, optimization-base methods [5, 11] incorporate additional regularization terms maintain the rationality of agent be- haviors. RL-based methods measure discrepancies between generated scenarios and macroscopic traffic distributions directly [12] or indirectly [3, 4] to ensure the naturalness of the adversarial sce- narios. However, pursuing maximum adversariality in AV testing often leads to excessive adversarial scenarios. These scenarios typically result in unavoidable collisions, where no driving policy can ensure safety. This conflicts with our purpose of testing and improving the AV systems in scenarios
8th Conference Robot Learning (CoRL. 2024), Munich, Germany.

---

(a) Conservative Scenario
(b) Excessive Adversarial Scenario
(c) Ideal Adversurial Scenario
AV
AV
AV
SAV
$1
CBV
AV
DV
Infeasible Region
Largest Feasible Region
Figure I: Illustration of adversarial yet AV-feasible scenarios in two-lane traffic setting. The CBV employs three distinct policies, resulting in different scenarios: (a) Conservative scenario, where the policy less adversarial; (b) Excessive adversarial scenario, resulting in unavoidable collision; and (c) Ideal adversarial scenario, effectively balancing adversarial and AV's feasibility.
where collisions could have been avoided by taking proper actions. Therefore, the motivation of this work is to generate safety-critical scenarios with reasonable adversariality.
Inspired by the concept of feasibility in Safe Reinforcement Learning (Safe RI.) [13, 14, 15], we propose an innovative approach using the feasibility of the AV to define the upper bound for adver- optimal policy
sariality in safety-critical scenarios. Specifically, under given critical scenario, exists that allows the AV to avoid potential collisions, then the current state of the AV is within its Largest Feasible Region (LFR), as detailed in Section 3.1. Therefore, naturally use the boundary of the AV's LFR as the upper bound for the scenario's ' adversariality to ensure that even the most adversarial scenario generated still satisfies the AV's s feasibility.
We illustrate several typical scenarios in Figure demonstrate adversarial yet AV-feasible scenar- ios intuitively. In Figure I()), the AV remains comfortably within its LFR, representing conserva- tive scenario. In contrast, Figure ((b) depicts the AV entering the infeasible region, indicative of an excessive adversarial scenario that results in unavoidable collision. Ideally, as demonstrated in Figure I(c), the AV should remain within its LFR while closely approaching its boundary, thereby representing an adversarial yet AV-feasible scenario.
In this paper, we propose FREA, a novel method designed to generate adversarial yet AV-feasible scenarios. To address the "curse of dimensionality" [16], similar to approaches in [3, 4], ma- nipulate the behavior of some critical background vehicles (CBVs) at pivotal moments reduce computational complexity. Morcover, incorporate the AV's feasibility guidance to ensure that the adversariality of CBV policy remains within reasonable range. Specifically, FREA involves two-stage framework: initially, we pre-train the optimal feasible value network of AV using offline datasets; subsequently, we introduce a feasibility-dependeer adversarial objective that enables CBV to learn reasonable adversarial policy. Experimental results demonstrate that gauidd adversarial policy facilitates the generation of near-miss events while significantly reducing over- adversarial scenarios and unavoidable collisions. Further performance evaluation of AVs confirms the robustness and generalization ability of FREA in AV testing across various surrogate AV methods and environments. The main contributions of this work are concluded as follows:
1. We propose FREA, a safety-critical scenario generation method that leverages the Largest Fea- sible Region (LFR) of AV as guidance to ensure the adversarial reasonableness of the Critical Background Vehicles (CBVs), thereby generating adversarial yet AV-feasible scenarios.
2. We show that FREA facilitates generating near-miss events while ensuring AV's feasibility, and it also exhibits robustness in AV testing across various surrogate AV methods and environments.

---

2 Related Work
Safety-Critical Scenarios Generation. Recently, the Deep Generative Model (DGM) method has gained significant attention in scenario generation for its ability to construct neural networks that model data distributions and generate scenarios by sampling from these models [6. 7, 9, 10, 17]. Commonly, these methods output vehicle trajectories that may not always adhere to dynamic con- straints or exhibit the necessary smoothness, raising concerns about their dynamic authenticity. In contrast, optimization-baser methods [5, 11, 18] optimize the actions of all vehicles in scene, ensuring that these actions stay within predefined constraints and maintain continuity to guarantee authenticity. These methods typically incorporate various regularization terms to enhance the ratio- nality of the actions. However, with more vehicles, the "curse of dimensionality" [16] often hampers optimization- based methods from finding plausible trajectories, reducing performance [5, 11]. RL- based strategies [3, 4, 12, 19] address this by controlling only Critical Background Vehicles (CBVs) at crucial moments, aiming to enhance adversariality while ensuring consisteney with natural dataset distributions. These methods typically evaluate adversarialiyy using metrics like collision rate [3, 4), collision likelihood [19], the minimum distance [12] to the AV. Although they emphasize macro- scenarios' naturalness, pursuing maximum adversariality still results in excessive adversarial sce- narios. To mitigate these concerns, we introduce a fcasibility-guider adversarial policy of CBV that ensures AV's feasibility while optimizing scenario adversariality.
Safe RL with Hard Constraint. Safe RL is usually modeled as Constrained Markov Decision Process (CMDP) defined by M (S,A, p,r, h, c, (,7,, where S and A represent the state and action spaces, P describes the transition dynamics, is the constraint violation function, c S - [0, Cmax] is a bounded cost function, and y is the discount factor within (0, 1). Typically, c(s) = max (h(). 0). The goal is to optimize a policy t to maximize rewards while adhering to safety constraints, especially worst-case constraints in safety-critical domains like autonomous driving. To enhance safety, various strategies have been developed: [20] proposes a safety index that ensures persistent safety for energy -iirrggtdiii policies, while [21, 13, 14] employ reachability certificates to ensure the worst-case constraints remain non- positive during online policy optimization. [15] decouples the learning of the reachability certificate from policy optimization, performing it offline for more stable training. As we need the LFR of the AV and online training with fixed-policy AV only yields subset of LFR, following [15], we adopt an offline method to comprehensively learn the AV's LFR, enhancing training stability.
S x A + R is the reward function, h S - R
3 Methodology
In this section, integrate AV's feasibility into adversarial policy learning for the Critical Back- ground Vehicle (CBV), formulating FREA as shown in Algorithm 1. The offline part (Section 3.1) trains the AV's optimal feasible value network using the offline dataset to approximate the Largest Feasible Region (LFR) of the AV. In the online part (Section 3.2), we propose a feasibility-dependeer adversarial objective for CBV training with the predetermined LFR. For clarity, the elements asso- ciated with AV are denoted with .AV while CBV-related elements have no special superseripts.
3.1 Largest Feasible Region of AV
Given the efficacy of Hamilton-Jacobi Reachability (HJR) [22] in the domain of Safe RL, we adopt the HJR framework instantiate LFR. First, we provide brief overview of HJR (Definition 1) and then dive into the detailed instantiation of the LFR under the HJR framework (Definition 2).
Definition 1 (Optimal feasible value function). Based on [13, 15, 22], the optimal feasible state- value function Vū and the optimal feasible action-value function Qj, are defined in Eqs. (1) and (2).
(5 = min max h (s
AV AV = AAV AA ,0 ~ π (-1 (V
(1)
AAY CEN
(5 aAv := min max h (s s SAY AN = AV a.41 AV (.1 (1s
(2)
W TEN
3

---

The optimal feasible value functions exhibit the following properties:
(s*)) & + AV m h (st") S O, that is, when Ví ( is not larger than zero, there exists an optimal policy for the AV that satisfies the hard constraints.
(s*M)
Vn maxxen h (sfV) > O, that is, when (s*V) is larger than zero, no policy ensure the safety of AV under the hard constraints.
Therefore, the optimal feasible value function serves as an indicator of whether there exists a policy of AV that achieves hard constraints. Consequently, we can easily derive the following definition.
Definition 2 (Largest Feasible Region (LFR)). The largest feasible region is the sub-zero level set of the optimal feasible state-value function.
Sj = { ( 50}
Although HJR effectively enforces hard constraints, deriving the optimal feasible value function typ- ically requires Monte Carlo estimations through environmental interactions. However, in scenario generation, the AV usually adopts fixed policy throughout these interactions. Consequently, the feasible region derived through interaction is merely subset of LFR.
To accurately obtain the LFR, we adopt the method proposed in [15], which involves pre-collecting driving trajectories using different AV algorithms and then deriving the LFR through offline learn- ing. The optimal feasible value functions Vi (s) and Q7, ( can be obtained, respectively, by minimizing the following objective functions:
Cv, (w) = IED [4 (Q .aVi)) (a(s"\W)))
(3)
Lqn (0) = ED (((1 ())s))((s + max (Ms*"),, Vn (s :w))) Qn(s") (
(4)
where (u) |r -ir-T(y T(u > O)lu² for r E (0.5, 1) and D is the offline dataset, comprising both safe and unsafe trajectories. Further dataset collection details are in Appendix C.I.
With the well-trained V77 (sAV), we can easily assess whether the AV is within the LFR based on its current state gAV Additionally, by interpreting the AV's state as a scenario description and applying the viewpoint transformation function g(-), we derive AA from g(s), where s is the CBV's state. This links the AV's LFR the CBV's adversarial policy learning, showing V%5 (V)) = Vž (g(s)) thus connecting the AV's feasibility with CBV policy.
3.2 Teasibility-Dependen Adversarial Objective of CBV
With the predetermined LFR of AV from Section 3.1 and the relation between AV and s, the CBV can access AV's LFR through s to evaluate feasibility. This enables us to form a standard CMDP framework for CBV to encourage adversarial behavior while ensuring reasonableness.
The standard feasibility-dependeett objective function usually adopts distinct objects in the feasible and infeasible regions, with the principle of maximizing expected cumulative reward in the fea- sible region while minimizing constraint violations as much as possible in the infeasible region [13, 14, 15J. With the predetermined LFR and the data (s, a, 8 sampled from the rollout buffer, we modificd the on- on-policy version of the ccasibility-dependen objective function from [13], incor- porating stricter constraints, as shown Eqs. (5) and (6). Intuitively, we hope to maximize CBV's adversarial rewards when the current state AV = g (s) and the next state sA = g (s') of the AV are within L.RR and minimize the AV's s constraint violations otherwise (Appendix A. demonstrates the theoretical relationships between Eq. (6) and the origin advantage function in [13]).
L(0)= =Emo, [min (0) T (s, a), clip (ri(0), c, 1 +) T (s,a))l
(5)
To (s, a) =A, Toe (s.a) a) T(s, 8') AB W a
T(s, s'));
(6)
where (0) = =o(a|s) is the ratio, A, n (s. a) = O Tok (s, a) v, - (s) is CBV's reward advantage, nee (a|s)
As .A4) ) is AV's feasibility advantage, and (s, s') 1V (. is the indicator.

---

Algorithm sraasibllitygguideee reasonable adversarial policy (FREA)
1: Offline Part (Section 3.1)
2: Initialize feasibility value networks Vh, Qh-
3: for each gradient step do
4: Update V/, using Eq. (3)
# Optimal feasible State-value function learning
5: Update Qn using Eq. (4) # Optimal feasible action-value function learning
6: end for
7: Online Part (Section 3.2)
8: Initialize policy parameters ou. reward value function parameters 4/u
9: for == 0,
2,...... do
10:
Collect set of trajectories B = {Ti) with policy THe where Ti is T step episode,
11:
Compute reward advantage A," (s, a). using generalized advantage estimator (GAE [23]).
12:
Compute feasibility advantage using Eq. (9).
13:
Derive overall advantage using Eq. (6) # Advantage calculating
14:
Fit reward value function, by Smooth L1 Loss. # Value function learning
15:
Update the policy parameters 0 by maximizing Eq. (5). # #Policy learning
end for
According Eq. (2), (s ax)) depends exclusively on h(-), which is in turn influenced by s,Y t E N. The action AV affects only the next state sAV' through the environment transition func- tion. Furthermore, when the BVs follow deterministic policy, we can reasonably assume that the environment, excluding the CBV and AV, is deterministie. Therefore, we can express the next state of the AV as 5AV' (sAV AV ,8; a), where P represents the deterministic environment transition function. This framework allows for the assertion that given the data sample, (sAV a s, a), the next state of the AV is thereby determined, allowing to derive the following lemma:
Lemma 1. As the BVs follow deterministic policy, the optimal feasible action-value function of AV can be achieved by AV's current state and next state (see Appendix A.2 for proof).
(AA) max(h(s"")
M(AV') 2 h(SAV) h(s < h(sAV)
Qh (s aa
With Lemma I and the viewpoint transformation function AA (8), we can derive AV's feasibil- ity advantage through CBV's current state and next state s' as:
(s AV) Q% (s a AV) VIT (sA))
(8)
Vn (g (8') Vī (s)
2 ( (s') < (g
max(h (g (s)) Vn (g (/
By integrating Eqs. (5), (6) and (9), we formulate the online part of FREA Algorithm 1.
Experiments
Following the experimental setup (Section 4.1), we conducted several experiments to affirm: The Largest Feasible Region (LFR) of the AV is reasonable through offline training (Section 4.2); FREA effectively generates near-miss events while maintaining AV's feasibility (Section 4.3); FREA shows generalization in AV testing across various surrogate AVs and environments (Section 4.4); and FREA continuously creates adversarial yet AV-feasible scenarios in complex traffic (Section 4.5).
4.1 Experiment Setup
Environment. We developed our environment using the Carla Simulator [24] in accordance with SafeBench [25], and combined "Scenario6" and "Scenario7" into "Scenario9", spanning across "Town05" and "Town02". In "Scenario9". the AV navigates predefined routes through various june- tions, avoiding randomly placed background vehicles (BVs). To implement reasonable adversarial
5

---

attacks, we applied the FREA method to Critical Background Vehicles (CBVs), attacking the sur- rogate AV with a goal-based adversarial reward to create adversarial yet AV-feasible, safety-critical scenarios. More experimental details are provided in Appendix B.
Baselines. We evaluate FREA against three other CBV methods baselines: (1) Standard: rule-based autopilot policy from Carla; (2) PPO: PPO-based adversarial policy without feasibility guidance; (3) FPPO-RS: PPO-based adversarial policy that includes fixed penalty to the reward whenever the AV enters the infeasible region. (Further algorithm details are in Appendix B.3)
4.2 Largest Feasible Region Learning of AV
According to Eqs. (3) and (4), learning the optimal feasible value functions incorporates the con- straint violation function h(sAV, ). A simple definition of h(sAA) is (i...e dl( d(AV, BV*), where d(AV, BV") represents the minimum distance between the bounding boxes of AV and BV How- ever, since the minimum distance is non-negative, we adopt sparse design for h(**V, which helps to maintain stable training balance of positive and negative samples, as advised by [15]:
[-1 M if mi..ge, d(AV, BV) S deh
min;e(,.....N)) d(AV BV") > der
h(sAV)
(10)
where N is the total number of BVs and de, and M are safety-related hyperparameters. Further training and application details about the LFR are provided in Appendix C.
Figure depicts the well-trained LFR of the AV in varying traf- fie scenarios. Figure 2(a) and (b) reveal that the infeasible re- gion expands as the AV's speed increases, indicating higher col- lision risks. Figure 2(c) and (d) confirm the LFR's consistency across scenarios. These cases show the pre-trained LFR's reli- ability under various scenarios, providing solid basis for CBV policy training.
Larpot Redile Rejoe (onne)) Inkoaitée Rejicn Crasse)
Fodilly honday (locaed) Badgnard Velak (BV)
JV Volicty Veter 1/
AV Vileaty Vadue (amre))
(m/s))
Vae (m/ss
(c) Vie (m/ss)
(d) Vay (m/ss)
Figure Visualization of well-trained LFR various scenarios.
4.3
Quantitative Analysis of Generated Scenarios
To verify that FREA can generate adversarial yet AV feasible scenarios, we quantified the near-miss events and the AV's feasibility across various CBV methods. To ensure consistency and faimness in our quantitative analysis, we employed the same surrogate AV method, "Expert" [26], throughout the experiments. Further analysis about the surrogate AV methods discussed in Section 4.4.
Evaluation of Near-miss Events. Previous research indicates that all safety-related incidents share common origins with miaremisses [27, 28, 291, highlighting the importance of analyzing near-miss events in the generation of safety-critical scenarios. Consistent with [4], we use time-to-collision (TTC) [30] and post-encroachment time (PET) in [4] as metrics to quantify these near-miss events.
Figure 3(a) and (b) show the distributions of TTC and PET across different CBV methods. The PPO produces the most adversarial scenarios across all maps. Conversely, FPPO-RS and FREA exhibit similar near-miss results but with a higher frequency of near-miss than Standard traffic flow. Given our focus on AV-feasible near-miss events, further analysis of AV's feasibility is required.
Evaluation of AV's Feasibility. While near-miss events are crucial for generating safety-critical scenarios, it is also vital avoid over-collision events caused by excessive adversarial CBV policy. To ensure that FREA effectively minimizes over-collision events, we analyze the scenarios under different CBV methods with four metries: (1) Collision Rate (CR); (2) Infeasible Ratio (IR); (3)

---

Somero Dend
SONEO TowN
Toed)
boald
Iomesa Toads
Villow Orremnns
(a) Time to collision distribution
(b) Post encroachment time distribution
Figure 3: Evaluating near-miss events across different CBV methods with Expert [26] AV
Semerd Trwat?
Scourid Towed
Socaied Towal
Scario Toual
Colliice frcuuie (00g))
Colicion Jepkkelee
Callaiin Volacyy
Callabe Valcety (nvl)
Expen
Experp
Exjent
(b) Collision velocity distribution Figure 4: Evaluating collision severity across different CBV methods with Expert [26] as AV Table 1: Feasibility evaluation using Expert [26] AV under different CBV methods. Results the average of 10 runs in "Scenario9" with varied seeds.
(a) Collision impulse distribution
Town05 intersections
Town02 intersections
CBV
Feasibility
CR (1)
IR (L)
ID (L)
CR
(L)
ID (J)
KING(5)
x
76.67%
65.97%
7.54m
N/A
N/A
N/A
PPO
X 37.5%
35.56%
10.57m
30.0%
51.18%
12.40m
EPPO-RS
V
11.25%
34.92%
9.13m
24.29%
45.36%
9.16m
FREA
5.0%
31.10% %
6.25m
5.71%
27.18%
4.94m
Infeasible Distance (ID); and (4) Collision Severity, including collision speed and impulse. See Appendix E.2 for metric details and Appendix B.3 for detailed reimplementation of KING [5].
As shown in Figure 4 and Table 1, without the feasibility constraint, the PPO and KING [5] lead to many severe collisions, indicative of excessive adversarial behavior. In contrast, under the feasibility constraint, both FPPO-RS and FREA significantly reduce the severity of these events. However, FPPO-RS still struggles with hard constraints, leading to many infeasible events. Conversely, FREA balances adversarial intensity with AV's feasibility, thereby achieving the least severe collisions.
In conclusion, our analysis confirms that FREA effectively generates considerable near-miss events while ensuring AV's feasibility, thus creating adversarial yet AV-feasible scenarios.
4.4 Generalization Analysis of AV Testing.
To evaluate the generalization FREA across various surrogate AVs and enviromments in AV test- ing, we assessed the driving performance of PlanT [31] and Expert [26] under different CBVs that were pre-trained with specific surrogate AVs on "Town05" and "Town02". The performance metrics follow the setting in [25], where the OS represents the overall score (details in Appendix E.3).
Table 2 illustrates that the PPO method, pre-trained with various surrogate AV methods, exhibits no- table variance AV testing. This variance suggests that, without feasibility constraints, the CBV's adversarial policy closely depends on the specific surrogate AV method. In contrast, FREA demon- strates remarkable stability in AV testing. This stability is primarily due to goal-based adversarial rewards and feasibility constraints, both independent of the specific surrogate AV method employed. Furthermore, FREA consistently aligns its relative AV testing results with standard traffic flows, sug- gesting that FREA facilitates safety-critica scenario generation while ensuring unbiased AV testing.

---

Wart stack
frish
CBV anack
Near-mis
Cunen
Cument
attack
Pie vious attack
sttakk
(a) Intersection attacks
(h) Straight road attacks
Figure 5: Representative scenarios: Red: AV (Expert [26]). Blue: BV. Purple: CBV (FREA).
Table 2: Comparative performance of AVs across different maps, using CBV methods pre-trained
with various surrogate AVs. Results are the average of 10 runs in "Scenario9" with varied seeds.
TTwwl05 intersections
Towal2 intersections
CBV
Sum AV
AV
CR
(4)
(3)
UC
OS (1)
CR
(L)
RF (L)
UC
(1)
OS
Standard
x
Expert PlanT
1.0%
0.0m
0.0m
7.0m
7.0m
6%
1%
55s
70s
90.0
1.0%
0.0%
0.0m
0.0m
6.0m
6.0m
6%
2%
638
768
90.0
Expert 36.0%
0.0m
6.0m
8%
66s
76.0
40.0%
0.0m
6.0m
15%
66s
72.0
PPO Expert
PlanTT
61.0%
1.0m
7.0mn
11%
70s
65.0
70.0%
0.0m
6.0m
27%
648
$7.0
Experi
0.0m
0.0m
PPO
PlanT
PlanT
45.0%
0.0m
7.0m
7%
69%
72.0
51.0%
0.0m
6.0m
18%
70s
67.0
Expert
4.0%
0.0m
7.0m
7%
67%
89.0
9.0%
0.0m
6.0m
16%
75s
83.0
FREA
Expert
PlanT
10.0%
0.0m
7.0m
5%
73s
86.0
10.0%
0.0m
7.0m
24%
868
79.0
Expert
0.0m
82.0
FREA
PlanT
PlanT
9.0%
0.0mn
7.0m
6%
73s
87.0
17.0%
0.0m
7.0m
18%
838
79.0
4.5
Analysis of Representative Scenarios
To confirm the validity of scenarios generated by FREA, we analyze representative cases. Figure 5(a) illustrates a scenario at an intersection where the AV, attempting right turn, is cut off by faster CBV also turning right prematurely, forcing the AV to stop and wait. Subsequently, another vehicle to the right the AV is selected as the next CBV for further attack. Figure 5(b) depicts a scenario on straight road where multiple CBVs sequentially adopt different strategies attack the AV. These examples demonstrate that FREA is capable of creating series of continuous, adversarial yet AV- feasible scenarios in complex traffic environments. (Further analysis be found in Appendix F)
5 Conclusion
In conclusion, FREA employs the concept of the Largest Feasible Region (LFR) to establish the upper bound of adversariality in safety-critical scenario generation. This approach aims to maximize adversariality while ensuring AV's feasibility. Specifically, FREA employs a two-stage framework that begins by pre-training the AV's optimal feasible value network using offline datasets to establish LFR. Then, learns a reasonable adversarial policy for Critical Background Vehicles (CBVs) based on feasibility- adversarial objective, thereby creating adversarial yet AV-feasible scenarios. Experimental results illustrate that the scenarios generated by FREA contain considerable near-miss events while effectively reducing unavoidable collision events. Moreover, guided by the AV's feasibility and the goal-bac boal-based adversarial reward, FREA demonstrates enhanced robustness and generalization ability in AV testing across various environments and surrogate AV methods.
Limitation. With all the advantages FREA discussed, some limitations of our method also suggest directions for future work. As detailed in Appendix C.I. the LFR of AV exhibits instability under different hyperparameters. This instability is primarily due to the limited offline data size, concern also highlighted in [15], which adversely affects the accuracy of LFR assessments. In addition, FREA lacks certain traffic common sense and is prone to violating traffic regulations, as discussed in Appendix F.2. In the future, integrating intelligent agents like LLMs to address these deficiencies and ensure compliance with traffic rules will be an important research direction.

---

Acknowledgments
This research was supported by the National Natural Science Foundation of China under Grant 52221005 and the Tsinghua-Toyota Joint Research Institute Interdisciplinaryy Project under Grant 20223930039.
References
[]] C. D. Motor Vehicles. California department of motor vehicle disengagement re- port, 2023. URL https://www dmv http::///ww..mmmc.cg.ooooooaaal ca.gov//potta//vehicll. iewiinntn-uerrttaee
Accessed 2023-05-23.
[2] W. Ding, C. Xu, M. Arief, H. Lin, B. Li, and D. Zhao. A survey safety-critical driving scenario generation- methodological perspective. IEEE Transactions on Intelligent Trans- portation Systems, 2023.
[3] Feng, X. Yan, H. Sun, Y. Feng, and H. X. Liu, Intelligent driving intelligence test for autonomous vehicles with naturalistic and adversarial environment. Nature communications, 12(1):748, 2021. 2021.
[4] S. Feng, H. Sun, X. Yan, H. Zhu, Z. Zou, S. Shen, and H. X. Liu. Dense reinforcement learning for safety validation of autonomous vehicles. Nature, 615(7953):620-627, 2023.
[5] N. Hanselmann, Renz, K. Chitta, A. Bhattacharyya, and A. Geiger. King: Generating safety-critical driving scenarios for robust imitation via kinematics gradients. In European Conference Computer Vision, pages 335-352. Springer, 2022.
[6] S. Suo, K. Wong, J. Xu, J. Tu, A. Cui, S. Casas, and R. Urtasun. Mixsim: A hierarchical framework for mixed reality traffic simulation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9622-9631, 2023.
[7] Suo, Regalado, Casas, and R. Urtasun. Trafficsim: agent behaviors. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10400-10409, 2021.
Learning to simulate realistic multi-
[8] W. Ding, H. Lin, B. Li, and D. Zhao. Causalaf: Causal autoregressive flow for safety-critical driving scenario generation. In 6th Annual Conference on Robot Learning, 2022.
[9] W. Ding, H. Lin, B. Li, K. J. Eun, and D. Zhao. Semantically adversarial driving scenario generation with explicit knowledge integration. arXiv preprint arXiv:2 100.046606 1, 2021.
[10] Z. Zhong, D. Rempe, Y. Chen, B. Ivanovic, Y. Cao, D. Xu, M. Pavone, and B. Ray. Language- guided traffic simulation via scene-level diffusion. arXiv preprint 23ti:23006.03444 2023.
[11] J. Wang, A. Pun, Tu, S. Manivasagam, A. Sadat, S. Casas, M. Ren, and R. Urtasun. Advsim: Generating safety-critical scenarios for self-driving vehicles. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9909-9918, 2021.
[12] K. Hao, W. Cui, Y. Luo, L. Xie, Y. Bai, J. Yang. S. Yan, Y. Pan, and Z. Yang. Adversarial safety-critical scenario generation using naturalistic human driving priors. IEEE Transactions on Intelligent Vehicles, 2023.
[13] D. Yu, H. Ma, S. Li, and Chen. Reachability constrained reinforcement learning. In Inter- national Conference on Machine Learning, pages 25636-25655. PMLR, 2022.
[14] D. Yu, W. Zou, Y. Yang, H. Ma, S. E. Li, Yin, Chen, and J. Duan. Safe model-based reinforcement learning with uncertainty- aware reachability certificate. IEEE Transactions on Automation Science and Engineering, 2023.

---

[15] Y. Zheng, J. Li, D. Yu, Y. Yang. S. E. Li, X. Zhan, and J. Liu. Safe offline reinforcement learning with cessibility-guidee diffusion model. arXiv preprint arXiv:2401. 2024.
[16] H. X. Liu and S. Feng. curse of rarity" for autonomous vehicles. arXiv preprint arXiv:2207 2022.
[17] W. Ding, B. Chen, B. Li. J. Eun, and Zhao. Multimodal safety-critical scenarios genera- tion for decision-making algorithms evaluation. IEEE Robotics and Automation Letters, 6(2): 1551-1558, 2021.
[18] W. Ding, Chen, M. Xu, and D. Zhao. Learning to collide: An adaptive safety-critical sce- narios generating method. In 2020 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 2243-2250. IEEE, 2020.
[19] L. Zhang, Z. Peng, Q. Li, and B. Zhou. Cat: Closed-loop adversarial training for safe end-to- end driving. In 7th Annual Conference on Robot Learning. 2023.
[20] H. Ma, C. Liu, S. E. Li, S. Zheng, and Chen. Joint synthesis of safety certificate and safe control policy using constrained reinforcement learning. In Learning for Dynamics and Control Conference, pages 97-109. PMLR, 2022.
[21] J. F. Fisac, N. F. Lugovoy, V. Rubies-Royo, S. Ghosh, and C. J. Tomlin. Bridging hamilton- jacobi safety analysis and reinforcement learning. In 2019 International Conference on Robotics and Automation (ICRA), pages 5550-8556. IEEE, 2019.
[22] S. Bansal, M. Chen, S. Herbert, and C. J. Tomlin. Hamilton-jacohi reachability: A brief overview and recent advances. In 2017 IEEE 56th Anmual Conference on Decision and Control (CDC), pages 2242-223 22533. IEEE, 2017.
[23] J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint
2015.
[24] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun. Carla: An open urban driving simulator. In Conference on robot learning, pages 1-16. PMLR, 2017.
[25] C. Xu, W. Ding, W. Lyu, Liu, S. Wang, Y. He, H. Hu, D. Zhao, and B. Li. Safebench: benchmarking platform for safety evaluation of autonomous vehicles. Advances in Neural Information Processing Systems, 35:25667-25682 2022.
[26] K. Chitta, A. Prakash, B. Jaeger, Yu, K. Renz, and A. Geiger. Transfuser: Imitation with transformer- based sensor fusion for autonomous driving. IEEE Transactions on Pattern Anal- ysis and Machine Intelligence, 2022.
[27] L. Yorio and S. M. Moore. Examining factors that influence the existence of heinrich's 's safety triangle using site-specific h&s data from more than 25,000 establishments. Risk analysis, 38 (4):839-857) 852,, 2018
[28] F. Orsini, G. Gecchele, R. Rossi, and M. Gastaldi. conflict-based approach for real-time road safety analysis: Comparative evaluation with crash-based models. Accident Analysis & Prevention, 161:106382, 2021.
[29] W. D. Glauz, K. Bauer, and D. J. Migletz. Expected traffic conflict rates and their use in predicting accidents. Transportation Research Record, 1026:1-12, 1985.
[30] Y. Jiao. A fast calculation of two-dimensional time-to-collision. https://github.com Yiru- Jiaoo hima-JJjao/too-immnniooonnlll - To-Collisionn 2023.
[31] K. Renz, K. Chitta, O.-B. Mercea, A. Koepke, Z. Akata, and A. Geiger. Plant: Explain- able planning transformers via object-level representations. arXiv preprint arX1v:2210.14222. 2022.
10

---

[32] AlexanderFabisch. distance3d. http:///gghthh..ooc/llmcarrraaer 2024.
[33] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint 177.v:170..063477, 2017.

---

A Theoretical Analysis
A.1 Feasibility-depend Advantage Function
advantage function relates to A, (s. a) and A A as we use the Largest Feasible Region (LFR) the AV the guidance to train the CBV policy and the predetermined LFR is independent of the CBV policy н, A,," (s, a) can be substituted with A (s a Thus, the combined advantage function is defined as:
In [13], the
(s. a). However,
* (s, a) A, * (s, + (s()) A ( a.
(11)
where (8) acts indicator function. For feasible states, (s(s) 0 is finite, and for unfeasible states, (8) + +00. Consequently, the feasibility-deeendent advantage function simplifies to:
T (s, a) = A, Th (s, a) sEs; + As (A Iags;
(12)
Aligning with Definition 2 and the viewpoint transformation fuucciio g(-), we reinterpret Sj using the optimal feasible state-value function ViA which is relative to the AV's state:
T (s, a) = A," (s, a) (ygo))) + A , -Lyg((()))
(13)
Given that the PPO-based method calculates the advantage solely from the trajectories stored in the buffer, we propose imposing stricter constraints on A, t (s, a). Specifically, if the AV's next state falls outside the LFR, the optimization should prioritize minimizing feasibility violations over maximizing adversarial rewards. Consequently, we formulate the final advantage function in Eq. (6).
A.2 Proof of Lemma
Given that other BVs adhere to a consistent rule- based policy, we can reasonably assume that the environment, excluding the CBV and AV, deterministic. Thus, we can redefine Eq. (2) as follows:
Q% (s aV = min max { (50 (s AN
EEN
s AV ag a 80 = 8, 00
a, s = P (st aa St, at) 8641 = 9 (5 AV
0++1 ~ π AV (- AV ae+1 π CBV (. 8e+1), (14)
where and the state-action pair of the CBV and P is the deterministic transition function excluding the CBV and AV.
Additionally, based on Definition I and Eq. (14), we identify two cases:
Casel: if ((s 2 h(sAV), then: Qi a
min max {h (sa") h (s/H = min max (h (s = (sAr)) a EEN
w/
CEN
(15)
Case2: if h(sAV\)) < h(sAV), then: (v .v
min max (sdV) h (s(X1) max(h((AV), Vi (sAV)) AA
(16)
EEN
Building upon Eqs. (15) and (16), we conclude in Eq. (17) that (5 a aV) primarily depends on the states of the AV. The actions of both the AV and the CBV mainly influence state transitions.
(sAr") max maxx(h(p (h(sAV), Vi (sAV'))
h(sav\)) 2 ((sAv) h(sAv') h(SAV)
(V aa AV =
(17)
12

---

B Experiment Details
Building on foundational concepts from [3, 4], we apply our FREA method to critical background vehicles (CBVs) within traffic flows. We first outline the mechanisms for specifying and withdraw- ing CBVs, as detailed in Appendix B.1. We then discuss the safe RL-based setting implemented in FREA method, described in Appendix B.2. Finally, provide implementation details of the baseline methods in Appendix B.3.
B.1 Specifying and Withdrawal of CBVs
To appropriately select CBVs and exclude unsuitable BVs, we established criteria to filter out ineli- gible candidates:
Casel: The BV is located in the opposing lane relative the AV.
Case2: The distance between the BV and AV exceeds meters.
Case3: The BV is positioned behind the AV with a relative yaw angle greater than 90 degrees, indicating no interaction.
Case4: The BV has previously served as CBV and has reached its goal in the scenario.
Based the predefined criteria, system assesses the scenario each simulation step in Carla. If the number of active CBVs drops below predefined threshold, the nearest candidate the AV is automatically selected as new CBV. To prevent disruptions in normal traffic flow during training, we implemented a withdrawal mechanism for CBVs that specifies conditions for their removal, whether they complete their tasks or not.
Casel: The CBV achieves its objective is then terminated and reverts to standard BV).
Case2: The BV is positioned behind the AV with a relative yaw angle greater than degrees (it truncated and reverts standard BV).
Case3: The CBV obstructs traffic flow or exceeds the maximum allowed duration (it is truncated and reverts to standard BV).
Case4: The CBV collides with any BV the AV (it terminated and removed from the simulation).
This selection and withdrawal mechanism effectively manages the CBV training process. However, considering the potential limitations of these rules, developing more intelligent strategies remains future research direction.
B.2 Safe RL-based Setting
In this framework, each CBV acts as an RL agent tasked with attacking the AV while maintaining the AV's feasibility. Previous works [5, 12] primarily focused minimizing the distance between CBV and AV, often leading unavoidable collisions and unrealistic scenarios, discussed in Section 2. To mitigate this, replace the collision reward with the goal-based adversarial reward, which encourages the CBV to reach potential conflict point with the AV. The configuration details are as follows:
State. The state of each CBV is represented by an array of dimensions (V + 2) F, where V represents the number of nearby vehicles and F the features of these vehicles, the AV, and the goal point. Recorded features include relative and y positions, object extent along the X and Y axes, relative yaw angle, and absolute speed. For the goal point, speed is replaced by relative distance. The features of the AV and the goal point are positioned in the first and second rows of the array. respectively.
Action. Following the guidelines in [25], define a continuous action space with specific con- straints to prevent unreasonable actions. The acceleration range is set between -3 and and the steering angle is limited to maximum absolute value of 0.3.
13

---

Reward. As previously discussed, we have replaced the collision reward with goal-based reward. This adjustment encourages the CBV to navigate toward a potential conflict point while avoiding collisions with other BVs. In practice, we set the reference point in the global route of the AV as the potential conflict point, which forms the overall reward function:
R = ) (CBVe. Goale) + 15 ri callision +15 * *T;
finish
(18)
where d (CBV,, Goale) denotes the Euclidean distance between the CBV and its goal point at time t, the collision reward ri prolission is set to -1 if the CBV collides with any BVs at time t, and the goal-reaching reward It
fimish is set to 1 if the CBV is within meters radius of the goal at time L.
B.3
Implementation Details of Baselines.
B.3.1 Algorithms.
To evaluate the performance of FREA, propose three CBV methods baselines for a compre-
hensive quantitative comparison:
Standard. This method utilizes a rule-based autopilot policy implemented in the Carla Simulator [24] to generate realistic urban traffic flows.
PPO. This method employs an adversarial CBV policy based on PPO that aims to reach potential conflict point with the AV, utilizing the adversarial reward outlined in Eq. (18).
FPPO-RS. This method integrates a feasibility penalty term into the PPO-based adversarial policy, which penalizes violations the AV's feasibility constraints in the adversarial reward function. The modified adversarial reward function used during training is specified as follows:
clip (Vr (g(8e)) fmax) Pmnar
Rtea
(19)
Smaz
where fmaz represents the upper bound for feasible value clipping, and Pmaz is the upper bound for penalty rewards.
KING. This method reimplements the optimization- safety-critical scenario generation ap- proach, KING, as presented in [5]. Given the differences between our general experimental setup and that of KING, we made several necessary adjustments. For example, KING's experimental setup includes background vehicle counts limited to 1, 2, and 4, while we employ a continuous traffic flow with more than 10 vehicles. Additionally, the target speed for the AV in KING is set at 4 m/s, whereas we use a typical speed of 6 m/s. KING's experiments are conducted across Town03 to Town06, while our work focuses on Town05 and Town02. Therefore, KING not directly com- parable with the mentioned baselines in experiments that quantify near-miss events and assess the generality of AV testing. As result, we limit our comparison of KING with the baselines to AV's feasibility experiments, which are less influenced by variations in traffic flow settings. Specifically, adjust the target speed of the AV in KING from 4 m/s to 6 m/s and restrict comparative analysis to results from Town05 to ensure fairness.
B.3.2 Hyperparameters.
Table 3 shows the hyperparameters of baseline methods.
Training Curves about CBV methods. To ensure robustness in our training process, we aggregated results from three different random seeds, as shown in Figure 6. This illustration confirms that all three CBV methods converge well in various scenarios. Furthermore, the PPO method achieves the highest adversarial reward, reflecting focus on adversarial objectives. Conversely, FPPO-RS and FREA need to balance adversariality and AV's feasibility, resulting lower adversarial reward. Given our focus creating reasonable adversarial scenarios, achieving appropriate adversariality is more important than merely pursuing high adversarial rewards.
14

---

Scenario9 Town02
Sccnario9 Town05
80
50
40
Episodd Retur
20
Eppisode
-10
-40
Train stop
Train stop
AViEspen AViExpen CBV-FPPO-RS
AViExper CBV:PPO
Figure 6: Episode return of different CBV methods.
Table 3: Detailed hyperparameters of FREA and baselines.
Parameter
Value
PPO, FPPO-RS, FREA shared.
Optimizer
Adam (e le 5) Multi-layer Perceptron
Approximation function
Number of hidden layers
Number of hidden units per layer
256
Nonlincarity of hidden layer
RELU
Nonlinearity of output layer
linear
Critic learning rate Reward discount factor (?)
Linear annealing 3e 4 0
0.98
GAE parameters (A)
0.98
entropy parameters
0.01
Batch size
256
horizon length
2048
update repeat times:
Max episode length (N)
2000
Actor learning rate
Linear annealing 3e
Clip ratio
0.2
FPPO-RS
feasible value clip upper bound fmar penalty reward upper bound Pmoa
Largest Feasible Region: Training and Application
C.1 Training Details about LFR
Offline Datasets. As highlighted in [15], extensive coverage of the state space datasets is crucial for determining the LFR of AVs using offline RL. Following this guideline, we employed the Expert [26] and Behavior [24] agents as surrogate AVs, collecting 100k instances of interaction data under standard traffic conditions for each. Additionally, to introduce randomness, employed the PPO method as CBV with the Expert as AV, gathering another 100% instances of interaction data. This re- sulted in a comprehensive dataset of 300k interaction data for LFR training. As depicted in Figure 7, the offline dataset extensively covers most of the potential state space, satisfying the requirements for training an optimal feasible value function.
Constrain Function Setting. As outlined in Eq. (10), the hyperparameters M and dua- along with the minimum distance between vehicles' bounding boxes, are crucial for defining (SAV). Specifi-
15

---

Retamee Caveeinee of
Abesl Spent OT CCD1)
600
02
Relaive Cf (B1)
Mirinam Dooraz Intware AV (0xem
Reative Your (mc)
AV Threll (d)
(4)
(b)
(c)
Figure 7: The offline data distribution.
Succty Drs lanee holilss
Sality Do Tham bollise))
Theelt,
Sem Kilm
0U4
Sore www.deilieeet....m ad
0.5
2.0
-0.1
1197
0.50
0.75
1.25
1.75
0.33
0.30
0.75
1,00
1.25
1.50
2000
Step
Step
(a) Qn. loss
(b) V2, mean value
Figure 8: Learning curves in LFR training
cally, we employed the method described in [32] to calculate the minimum distance, which is always non-negative. To ensure a balance between positive and negative samples, we experimented with various settings for and deh-
In experiment, set dea 0.1 meters and 0.5 meters in separate trials to find the optimal parameter combination. Drawing the findings from [15], determined that optimal performance is achieved when the mean of the feasible value function is close to zero. Through empirical testing, we established dea = 0.1m, M = 18 and des 0.5m, MM = 12 as the optimal settings. Given that these parameters are used to train across multiple towns, it is crucial to balance their optimality for various environments. Figure 8 illustrates the learning curves for these settings, confirming that the chosen parameters effectively maintain the mean values of the feasible value function in different towns close
The visualization results for dea = 0.1m, M = 18 are presented in Figure 2, while those for den = 0.5m, M = 12 are shown in Figure 9. The former parameter set proved to be more effective in identical scenarios, leading us to select dea = 0.1m, M 18 for subsequent CBV training.
Detailed hyperparameter settings for the feasible value function be found in Table 4.
C.2 Application Details of LFR
During the feasibility-guided adversarial policy training for CBV, we encountered significant chal- lenge: the optimal feasible value function produces single scalar value at each timestep. In scenar- ios with multiple CBVs, is difficult to identify which CBV renders the AV's operation unfeasible. To address this issue, we introduced "pseudo" state for each CBV at every timestep. This "pseudo" state captures information relevant both the AV and CBV from the perspective of the AV. Cru- cially, this "pseudo" state is utilized solely assess the threat posed by each CBV to the AV at each timestep. By employing this method, climinate the need for the viewpoint transformation
16

---

Largest Feasible Region (Jearned)
Feasibility boundary (leaned)
BV Velocity Vector
V/2
Infeasible Rogion (learned)
Background Vehicle (BV)
AV Volocity Voctor
(learzed)
-9
-6
(a) Vav [m/s)
(b) Vav 6 (m/s)
3
0
(c) Vav 4 (m/s)
(d) VAv 4 (m/s)
Figure 9: LFR visualization with 0.5m der under various traffic scenarios.
Table 4: Detailed hyperparameters of feasible value function training.
Parameter
Value
Optimizer
Adam (e (6=10 le 5)
Approximation function
Multi-layer Perceptron
Number of hidden layers
2
Number of hidden units per layer
64
Nonlinearity of hidden layer
RELU
Nonlinearity of output layer
linear
learning rate Batch size
Linear annealing 3c + 0
1024
Training steps
2e6
Discount factor 7
0.98
Expectile
0.9
Soft update
5e-3
de
0.1
M
18
function g()), previously described in Eqs. (6) and (9). Instead, the "pseudo" state directly derived from the information available each timestep, simplifying the process and enhancing the accuracy of LFR.
D Robustness of AV Pre-trained with Various CBV Methods
To explore the impact of reasonable adversarial scenarios on AV policy learning, we employed PPO [33] as the AV policy, which utilized the same forms of input and output as detailed for the CBV policy in Appendix B.2. By leveraging the AV's reward function described in [25], trained the PPO policy across various surrogate CBV methods. Subsequently, evaluations on these well-trained AV policies, presenting the results in Table 5.
conducted robustness
As shown Table 5, our proposed FREA method, when used as the CBV policy for AV training, improves the Overall Score (OS) and reduces the Collision Rate (CR), thereby enhancing AV policy robustness. This improvement primarily stems from the reasonable adversarial CBV policy. In normal traffic, the rarity of safety-critica scenarios limits AVs' ability to learn effective avoidance policies, especially for learning- based methods. Conversely, excessively adversarial policies like
17

---

Table 5: Comparative performance of AVs pretrained with various CBV methods across different maps. Results are the average of 10 runs "Scenario9" with varied seeds.
Town05 intersections
Town02 intersections
Sum. CBV
CBV
(L)
(1)
(L)
UC (L)
(L) (1)
CR (1)
(L)
(L)
(L)
(1)
(1)
Standard PPO
11%
4m
19m
68s
85
39%
8m
20m
18%
57s
70
Standard
17%
17m
66s
82
40%
19m
15%
63s
70
FREA
3%
6m
18m
1%
75s
89
40%
3m
18m
19%
56s
71
Standard
39%
6m
17m
7%
66s
73
79%
3m
17m
35%
45s
51
PPO
FREA
36%
15m
21m
66s
74
79%
4m
14m
37%
FREA
31%
12m
17m
5%
71s
76
73%
3m
20m
28%
51s
55
PPO often result in unavoidable collisions, hindering the development of correct avoidance policies since policy can ensure AV safety. By increasing the frequency of AV-feasible near-miss events, our FREA method provides effective data for AV training, thus improving policy robustness.
E Detail Explanation about the Metrics
E.1 Near-miss Event Metrics
In traffic safety and vehicle dynamics, time-to-collision (TTC) and post-encroachment time (PET) are two commonly used metrics to quantify near-miss events[4). Here are the formal definitions for these terms:
ur where d represents the distance between the two vehicles or between a vehicle and an obstacle and v, is the relative velocity, which is the speed of one vehicle relative the other the obstacle.
TTC
PET = 12 - h. where 4 is when the first vehicle passes through the intersection point and l2 is when the second vehicle passes through the same point.
In our work, the TTC metric was calculated using publicly available code library [30], and the PET metric computed using the code provided in [4].
E.2 Feasibility Metrics
In Section 4.3, we introduce four key metrics to evaluate the feasibility of AV along collision tra- jectories induced by various CBV methods. Among these, the Infeasible Ratio (IR) and Infeasible Distance (ID) are novel metrics proposed in this paper. Their definitions and implications are de- tailed as follows:
IR: Infeasible Ratio. This metric quantifies the proportion of infeasible states for the AV along the collision trajectory induced by specific CBV method. As the CBV approaches the AV, the likelihood of infeasibility naturally increases. The IR assesses the severity of collision risk by ex- amining the percentage of these infeasible states, serving as measure of the overall aggressiveness of the CBV collision trajectory. Since these trajectories inevitably lead to collisions, they must in- clude segments where infeasible states occur. Therefore, evaluating the relative performance of IR crucial.
ID: Infeasible Distance. This metric records the distance between the CBV and the AV when the AV first enters the infeasible region along the collision trajectory. Since CBVs may initiate their attacks from various starting points, the initial locations of collision trajectories can vary significantly. This variability means the IR metric alone may not fully capture the inevitability of collision. The Infeasible Distance (ID) therefore introduced to record the distance between the AV and CBV at the first instance when the AV's feasibility value exceeds zero. Intuitively, larger ID indicates more adversarial CBV approach, while shorter ID suggests that the CBV allows the AV to remain feasible for longer, indicating potentially avoidable collision.
18

---

Table Detailed parameters of evaluation metrics.
Metric
Weight w² Maximum allowed value maa
CR
0.4
OR
0.1
10 (m)
RF
0.1
(m)
UC
0.3
TS
0.1
30 (s)
E.3 Evaluation Metric of the AV
To fairly evaluate the performance of AV methods across different adversarial scenarios, we adopt the evaluation metrics from SafeBench [25], focusing on two main categories: Safery level and Func- tionality level. It is important to note that while the Etiquette level discussed in the SafeBench paper, it has not been implemented in the actual code. This exclusion is likely due the prioritiza- tion of safety and functionality in safety-critical scenarios, where etiquette is less essential. To avoid confusion, our evaluations strictly follow the implementation details specified in the SafeBench code, rather than the descriptions in the paper.
Within the Safery level and Functionalityy level, we define several specific metrics that contribute to an overall score, which is defined weighted sum of all evaluation metrics.
Safety Level. This level evaluates the safety performance of AV methods using two primary metries: collision rate (C)R) and average distance driven out of road (OR). We define т as the scenario trajectory collected through interaction. The number of collisions c(T), and the distance driven out of the road is denoted as d(r). Therefore, the metrics are calculated as follows: CR [c]]] and OR = [d(r)).
scenario is represented by
Functionality Level. This level measures the functional capabilities of AV agents in completing designated routes within testing scenarios. It employs three metrics: route-following stability (RF), average percentage of uncompleted route (UC), and average time spent to complete the route (TS). RF quantifies the average distance between the AV and the reference route during testing, expressed as RF E, [min
<e(r), 1 11 where Imar represents the maximum allowable deviation. UC
Fmux
reflects the complement of the average completion percentage of the route, calculated as UC
1 E [p(r], where p(T) is the percentage of route completion of each testing scenario. TS is defined as the average time required to complete a route, computed only for fully completed routes:
TS = [,(t(T))p(1 = 100%], where t(T) denotes the time cost of each testing scenario.
Overall Score. The overall quality of AV methods is quantified by overall score (OS), which aggregates the five metrics using a weighted sum formula: OS Dim w x g(m'), where each m² is a specific metric, w is its weight, and g(m') adjusts the metric based on its desirability:
m'is the higher the better
g(m')
minar'
(20)
m'is the lower the better
where m is constant representing the maximum allowed value for each metric m Further details about of and m are provided in Table 6.
F Scenario Analysis
F1 Successful Scenarios
To demonstrate that the FREA method can generate AV-feasible adversarial events across various traffic scenarios, present additional visualizations from different towns and intersections, as shown in Figure 10. Specifically, Figure 10(a) illustrates scenarios where the AV is preparing to make right turn, while the CBV exhibits adversarial behavior by overtaking and executing early
19

---

right turn. Figure 10(b) displays situations where the CBV makes a U-turn from its lane, leading to a potential collision with the AV and creating adversarial scenarios. Figure 10(c) highlight the adversarial behavior the CBV within an intersection, where CBV pre-empts the AV while passing through. These scenarios highlight the FREA method's adaptability to different traffic infrastructures and its effectiveness in generating safety-critical scenarios with reasonable adversariality.
(a) Right-turn attack
(b) Turn-over attack
(c) Intersection attack
Figure 10: Successful scenarios. Red: AV (Expert). Blue: BV. Purple: CBV (FREA).
F.2 Failure Scenarios
While the FREA method makes progress in generating adversarial yet reasonable safety-critical scenarios, particularly on the reasonableness of adversarial attacks, it also has several limitations, as illustrated by the failure cases depicted in Figure 11.
As illustrated in Figure (a),,, after completing its attack, the CBV released normal vehicle narrow road. However, its turning radius exceeds the width of the road, forcing it onto the pavement and resulting in an unreasonable scenario. In Figure 11 after an unsuccessful initial attack due to the AV's obstacle avoidance maneuvers, the CBV attempts a second attack through reverse maneuver. Although technically feasible, this approach deviates from typical driving objec- tives, compromising the scenario's reasonableness. Figure 11(c) shows a scenario where the CBV crosses solid yellow line initiate an attack. Since the state information FREA lacks map de- tails, violations of traffic nules are foresecable. Future studies will focus enhancing adherence to traffic regulations. Finally, Figure 1 (1d)) depicts traffic jam scenario at intersections caused by unreasonable attacks.
20

---

(a) Turning around on the pavement
(b) Reverse attack
(c) Traffic rules violation
(d) Traffic congestion
Figure 11: Failure scenarios: Red: AV (Expert). Blue: BV. Purple: CBV (FREA).
conclusion, this paper acknowledges specific limitations generating adversarial yet reasonable safety-critical scenarios. These limitations primarily include the lack of traffic regulation compliance and the challenge of aligning CBV behaviors during attacks with their driving objectives. Address- ing these issues is crucial for developing more reasonable adversarial scenarios.
21


Reviews:
[{"review_id": "GtPQk3nngz", "reviewer": "Reviewer_B6vA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "This paper presents a method for generating near-miss driving scenarios. The method involves precomputing a representation of the LFR, then leveraging constrained RL to train environmental agents to approach Ego vehicle but not force collision.", "summary_of_recommendation": "Weak accept. Good method, but some additional analyses would help, and improving clarity of the methodology is needed.", "technical_quality": 3, "clarity_of_presentation": 3, "potential_impact": 3, "robotics_focus": 3, "quality_of_limitations": 2, "questions_for_rebuttal": "- Contribution 2 is same as 1?\n- (locally) Jointly optimizing for N agents doesn’t suffer from curse of dimensionality. Can be performed at roughly same cost as N* cost of optimizing for 1 agent.  e.g. see GNEP etc. It appears your reference doesn’t discuss this point anyways but is rather talking about rare events in high dimensional data/strategy space. \n- Constrained/Safe RL: probability of constraint violation is zero? defining function on random variable => output of h(x) is random variable, not meaningful to constrain that \n- Same in definition 1. Assuming your policy is stochastic, (as is indicated by ~ symbol) then unless h maps from distributions over state space to reals, this is not meaningful definition \n- 130 what is “optimal” feasible value function? The value function simply is what it is, there is no notion of optimality \n- 131 minimizing over what? Parameterization of the functions V/Q? not specified\n- This optimization procedure/ dataset assumes that S_0^{AV} is known and fixed for all datapoints? \n- S^{AV} is overloaded. Training example points but also “current state” of AV at some query point. \n- Section 3.2 is not very clear on how CBV policies are actually generated. What is the “progress” objective?  Is goal to traverse to zero level set? \n- Lemma 1, not clear why a^{AV} = g(s’) for some s’? Need Lemma 1 to stand alone without referencing to appendix.\n- Equation 5 and 6 motivation is not presented clearly\n- Figure 2a, why is LFR region at rear of obstacles not flat/symmetric?  How accurate are these LFRs actually, compared to e.g. those computed by HJ reachability?\n- Define TTC and PET formally", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5qH37a90Pw", "reviewer": "Reviewer_2ukq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "The paper presents a method to generate reasonable safety-critical scenarios  with an upper-bound on the adversariality of the scenarios using the feasibility of the autonomous vehicle (AV). It calls the method FREA that uses the Largest **F**easibility Region (LFR) of the AV to  ensure the **RE**asonableness of the generated **A**dversarial scenarios. After calculating the LFR of the AV, FREA learns a feasibility-guided adversarial policy to control the critical-background vehicles (CBV) to generate adverse safety-critical scenarios.   The framework is inspired from the work of [FISOR (FeasIbility-guided Safe Offline RL)](https://arxiv.org/pdf/2401.10700). In a two stage framework:  FREA, first, uses offline data to learn an optimal feasible state-value network that is used to assess if the AV is within LFR.  With the LFR, FREA learns/optimizes (online) a feasibility-dependent adversarial objective to learn a policy for the CBVs that ensures AV’s feasibility.  The paper conducted experiments to demonstrate that FREA is capable of generating near-miss events (that represents reasonable adversariality) while maintaining the AV feasibility (that represents there exists policy that can ensure safety of the AV under maximum adversarial scenarios).", "summary_of_recommendation": "Adversarial scenarios are long-tail scenarios in real-traffic scenes and hard to scale.  This work would help in getting more robust self-driving policies trained on more and better adversarial scenarios. Overall, this framework to generate reasonable (maximum adversarial scenarios) that can still help to learn feasible policies can be helpful for future research using Safe-RL for autonomous driving. Therefore, I would recommend accepting this paper.", "technical_quality": 4, "clarity_of_presentation": 4, "potential_impact": 3, "robotics_focus": 3, "quality_of_limitations": 3, "questions_for_rebuttal": "**Questions and Suggestions**\n\nQ1: Can we have a system/metric to check the chance/likelihood of the generated scenarios in the distribution of real-traffic scenarios? Ideally they should be in the long-tail of the distribution?\n\nQ2: How can we keep the CBV policies or scenarios close to realistic driving or how are we preserving the naturalness of the generated scenarios?\n- Was there an attempt to try to filter out the non-realistic CBV policies while training or an experiment to show how much such scenarios might affect the feasibility or robustness of the learned AV policies?\n\nQ3: Line 103: “...under the proper assumption,...”: Could this be clarified? Is it the same as the assumption that the BVs follow deterministic policy or is it different? \n\nQ4: Line 200: text should be “Figure 2(c) and (d)”", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5WyRqEJ6X9", "reviewer": "Reviewer_oVnR", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 4, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "Targeting the safety critical scenario generation, the paper first builds a value function measure the feasibility of the ego policy then uses that value function to form constraints and apply safe RL (constrained PPO) to find adversarial policy.", "summary_of_recommendation": "The proposed method is sound and promising in safety-critical scenario generation.", "technical_quality": 4, "clarity_of_presentation": 3, "potential_impact": 3, "robotics_focus": 1, "quality_of_limitations": 3, "questions_for_rebuttal": "1. Missing an important relevant work: CAT: Closed-loop Adversarial Training for Safe End-to-End Driving\n2. The reward encouraging collision might create unrealistic behavior. (See weaknesses 2)\n \nI don't have much question because the paper covers most of the details.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a method to generate near-miss driving scenarios while maintaining the AV feasibility.

Strengths
- The approach is scalable to the real-world complexity of autonomous driving.
- The method performs well compared to existing baselines by capturing more near-miss events than the general traffic flow and by reducing the infeasible scenarios as compared to other CBV methods.

Limitations
- The paper needs to comment on the reliability of the LFR. The learned LFR can be noisy. It is important to do a proper analysis of how that affects the ability to generate near-miss scenarios.
- The CBV policies can result in unrealistic driving behaviors.  How does this affect the naturalness of the generated scenarios?
- The paper needs to improve its exposition and clarity.

**Comments post rebuttal**

The revised version has improved the paper's clarity. The reviewers also appreciate the inclusion of comfort-related metrics and the effect of extreme adversarial CBVs on the AV policies, as well as additional results on the stability of LFR. The authors should incorporate the results from the rebuttal in the final paper.
Decision: Accept