PaperlayerView exact revision on arXiv

Source-linked AI summary

Testing Scenario Library Generation for Connected and Automated Vehicles, Part II: Case Studies

Shuo Feng, Yiheng Feng, Haowei Sun, Shao Bao, Yi Zhang, Henry X. Liu

arXiv:1905.03428v3cs.ROcs.AI

TL;DR

High-dimensional scenario evaluation faces exponentially growing computation, and the authors report that existing evaluation methods cannot handle such cases. The paper studies three testing-scenario library generation cases and enhances the method with temporal-difference reinforcement learning; across the cases, it reports evaluation 255 to 3.75 × 10^5 times faster than NDD with the same accuracy.

  • Problem

    High-dimensional scenario evaluation faces exponentially growing computation, and the authors report that existing evaluation methods cannot evaluate such cases.

    Source: §V · p. 8

  • Method

    The paper demonstrates scenario-library generation and CAV evaluation in cut-in, highway-exit, and car-following cases, using temporal-difference reinforcement learning for high-dimensional scenarios.

    Source: §I · p. 1, §V · p. 9, §VII · p. 11

  • Results

    255 to 3.75 × 10^5 times faster evaluation than NDD, with the same accuracy, was reported across the three cases.

    Source: §VII · p. 11

  • Takeaways & Limitations

    The study provides implementation guidelines for systematic TSLG across low- and high-dimensional scenarios, different performance metrics, and varying CAV models.

    Source: §VII · p. 11

    Efficiency depends on surrogate-model/CAV dissimilarity; human-driving models were used as surrogates, and adapting them to different CAVs needs further investigation.

    Source: B. Limitations of the proposed method · p. 11

Abstract

from arXiv · show

Testing scenario library generation (TSLG) is a critical step for the development and deployment of connected and automated vehicles (CAVs). In Part I of this study, a general methodology for TSLG is proposed, and theoretical properties are investigated regarding the accuracy and efficiency of CAV evaluation. This paper aims to provide implementation examples and guidelines, and to enhance the proposed methodology under high-dimensional scenarios. Three typical cases, including cut-in, highway-exit, and car-following, are designed and studied in this paper. For each case, the process of library generation and CAV evaluation is elaborated. To address the challenges brought by high dimensions, the proposed methodology is further enhanced by reinforcement learning technique. For all three cases, results show that the proposed methods can accelerate the CAV evaluation process by multiple magnitudes with same evaluation accuracy, if compared with the on-road test method.

I. INTRODUCTION · II. REVISIT THE PROPOSED METHOD IN PART I · A. Problem Formulation

The paper applies and extends the general TSLG method from Part I [8] through three case studies, including an RL-enhanced approach for high-dimensional scenarios. It frames library generation as evaluating CAV performance while addressing the high test burden of rare events in naturalistic driving.

I. INTRODUCTION

  • Prior TSLG methods have limitations in scenario types, applicable CAV models, or evaluable performance metrics, while high-dimensional searches can grow exponentially in complexity.The introduction notes that exhaustive search and importance-function calibration are problematic for high-dimensional scenarios.Source: §I · p. 1
  • Part I [8] proposes a general method for different scenario types, CAV models, and performance metrics, prioritizing scenarios by maneuver challenge and real-world exposure frequency.Scenario criticality combines maneuver challenge with exposure frequency, unlike approaches that usually overvalue worst-case scenarios.Source: §I · p. 1
  • Cut-in illustrates library generation and evaluation, highway exit examines functionality, and car-following demonstrates RL-enhanced handling of high-dimensional scenarios.The paper uses cut-in’s low dimensionality to make results easier to visualize; highway exit focuses on quantifying functionality-related maneuver challenge.Source: §I · pp. 1–2
  • Across all three cases, the framework accelerates CAV evaluation by multiple magnitudes with the same evaluation accuracy as on-road testing.The cases are cut-in, highway exit, and car-following.Source: §I · p. 2

II. REVISIT THE PROPOSED METHOD IN PART I

  • Section II briefly revisits Part I’s [8] method, covering problem formulation, library generation, and CAV evaluation.It also lists related variable notations in Table I.Source: §II · p. 2

A. Problem Formulation

  • The method generates critical scenarios to evaluate CAV performance indices, with event probability conditioned on scenario variables, the feasible set, and predetermined ODD parameters.The ODD parameters can include road type, lane count, and weather conditions.Source: A. Problem Formulation · p. 2
  • Because rare events require intolerably many naturalistic-driving tests for reasonable precision, importance sampling can reduce test needs, but constructing a proper importance function remains challenging.The number of tests needed for a given precision depends on the importance function.Source: A. Problem Formulation · p. 2

B. Library Generation · C. CAV Evaluation

Library generation searches for critical scenarios using a criticality measure that combines maneuver challenge and exposure frequency. CAV evaluation samples from the library with an ε-greedy policy, estimates performance, and stops when estimation precision meets a threshold.

B. Library Generation

  • Criticality combines maneuver challenge, expressed as P(S|x, θ), and exposure frequency, expressed as P(x|θ), to identify scenarios for the library.Here, P(S|x, θ) is the occurrence probability of event S in scenario (x, θ).Source: B. Library Generation · p. 3
  • Because many local optima make naive critical-scenario search inefficient, the method uses multi-start optimization and seed-fill searching guided by an auxiliary objective.The surrogate model and auxiliary objective are discussed case by case.Source: B. Library Generation · p. 3

C. CAV Evaluation

  • Testing scenarios are sampled from the library with an ε-greedy policy, and their results are used to estimate the performance index P(A|θ).The per-scenario quantity P(A|x_i, θ) is estimated from testing results.Source: C. CAV Evaluation · p. 3
  • The ε-greedy sampling distribution uses N(X) for the feasible-scenario count, Φ for the critical-scenario set, and W as a normalization factor.The selection of ε is analyzed theoretically in Corollary 1 of the Part I paper.Source: C. CAV Evaluation · p. 3
  • The testing process stops when the estimate’s relative half-width falls below the predetermined threshold β [11][12].A minimal number of tests is required to achieve the desired estimation precision.Source: C. CAV Evaluation · p. 3
  • The confidence level is 100(1 − α)%, and estimation variance Var(μ̂) = σ²/n decreases as the number of tests n increases.The stopping expression uses zα and the estimate μ̂ = P̂(A|θ).Source: C. CAV Evaluation · p. 3

III. CUT-IN CASE STUDY · A. Problem Formulation · B. Library Generation

The cut-in case study follows a testing workflow from problem formulation through library generation and CAV evaluation. It formulates a two-dimensional scenario, uses accident rate as the safety measure, and identifies three components of library generation.

III. CUT-IN CASE STUDY

  • For all three case studies, the testing procedure presents problem formulation, library generation, and CAV evaluation in that order.The cut-in case study follows the same sequence.Source: §III · p. 3

B. Library Generation

  • Cut-in library generation addresses auxiliary-objective design, NDD analysis for exposure frequency, and SM construction for maneuver frequency.The generated library is then used to test and evaluate a typical CAV.Source: §III · p. 3, B. Library Generation · p. 4
  • The study designs an auxiliary objective function to search for critical cut-in scenarios.Source: §III · p. 3

A. Problem Formulation

  • The cut-in case simplifies decision variables to two dimensions, following existing studies [4].The two variables are range R and range rate ˙R at the cut-in moment.Source: A. Problem Formulation · p. 3
  • The cut-in formulation assumes the background vehicle maintains constant velocity after cut-in and fixes road-environment parameters as θ.Source: A. Problem Formulation · p. 3
  • Accident rate measures CAV safety performance in the cut-in case, with simulated on-road testing used as the baseline estimate.Source: A. Problem Formulation · pp. 3–4

1) Auxiliary Objective Function Design: · 2) NDD Analysis:

The cut-in method guides critical-scenario search with an auxiliary objective combining estimated maneuver challenge and exposure frequency. Naturalistic driving data (NDD) define exposure, calibrate objective parameters, and support the scenario model.

1) Auxiliary Objective Function Design:

  • The cut-in auxiliary objective combines estimated maneuver challenge and exposure frequency to guide search toward critical scenarios.Its balance weight may introduce roughness, which is acceptable because the objective provides search directions rather than a final evaluation.Source: 1) Auxiliary Objective Function Design · p. 4
  • mnpETTC estimates maneuver challenge using normalized positive enhanced time-to-collision; ETTC is a widely used safety index for varying-velocity scenarios [14].ETTC values are obtained by simulation, and the normalization factor UI is calibrated through NDD analysis.Source: 1) Auxiliary Objective Function Design · p. 4
  • Negative ETTC values, which denote safe situations, are set to one before calculating mnpETTC.This handling is part of the normalized positive ETTC measure.Source: 1) Auxiliary Objective Function Design · p. 4
  • Exposure frequency is estimated by distance to a common set of high-frequency scenarios, with dimension-specific normalization factors calibrated through NDD analysis.The distance uses the decision-variable dimension and normalization factor for each dimension.Source: 1) Auxiliary Objective Function Design · p. 4

2) NDD Analysis:

  • 414,770 qualified cut-in events were extracted from SPMD data using speed and range criteria of (2m/s, 40m/s) and (0.1m, 90m), respectively.Cut-in moments were identified when the preceding vehicle crossed a lane marking; range and range rate at that moment were recorded. The criteria are attributed to [16].Source: 2) NDD Analysis · p. 4
  • The SPMD NDD covers 34.9 million travel miles from 2,842 equipped vehicles; 98 sedans with MobilEye measured distances at 10 Hz.The database was collected in Ann Arbor, Michigan, and its lateral-distance data enabled identification of cut-in events.Source: 2) NDD Analysis · p. 4
  • The common set is a minimal rectangle of scenarios with P(x|θ) > 10^-3; for cut-ins, its range and range-rate bounds are [6, 88] and [-2.4, 1.2].For more complex scenarios, the common set may be simplified to the most frequent scenario, such as R = 14 and Ṙ = 0.Source: 2) NDD Analysis · pp. 4–5
  • The range-rate normalization factor is set to 18 because the maximal distance between scenarios and the common set is smaller than 18.Normalization factors are determined from the maximal distance between scenarios and the common set.Source: 2) NDD Analysis · p. 5

3) Surrogate Model Construction: · 4) Library Generation:

The sections describe an IDM-based surrogate model and a cut-in scenario library generated using normalized criticality. The library combines maneuver challenge with exposure frequency and contains 184 scenarios, about 5.38% of all scenarios.

3) Surrogate Model Construction:

  • Because little open CAV driving data is available, the proposed surrogate model is calibrated using naturalistic human driving data to represent generic CAV behaviors.These generic features include basic behaviors such as maintaining safe distances from surrounding vehicles.Source: 3) Surrogate Model Construction · p. 5
  • A calibrated intelligent driving model (IDM) is selected as the surrogate model for the car-following case.Source: 3) Surrogate Model Construction · p. 5
  • The IDM description includes a desired-spacing relation and adds acceleration and velocity constraints to make the model more practical and represent accident-prone behavior.Source: 3) Surrogate Model Construction · p. 5
  • An accident is defined as vehicle range falling below dacci, and the surrogate model’s accidents are shown in the yellow region of its safety-performance figure.Source: 3) Surrogate Model Construction · p. 5, Figure 5 · p. 5

4) Library Generation:

  • 50 initial points seeded the Part I optimization and seed-fill search; γ was set to 2.9 × 10^-4 across 3,420 discretized range/range-rate cells.Cells use 2 m and 0.4 m/s intervals over ranges (0, 90] m and [−20, 10] m/s.Source: 4) Library Generation · p. 5
  • The library includes scenarios whose criticality exceeds γ, and its probability distribution accounts for both maneuver challenge and exposure frequency.Scenario probabilities are calculated from normalized criticality.Source: 4) Library Generation · p. 5, Figure 6 · p. 6
  • 184 scenarios—about 5.38% of all scenarios—make up the generated cut-in library.The generated-library figure colors scenarios by testing probability.Source: 4) Library Generation · p. 5, Figure 6 · p. 6

C. CAV Evaluation … B. Library Generation

The cut-in evaluation shows that the proposed library-based method reaches the target accident-rate estimation accuracy with far fewer tests than NDD sampling. For the highway-exit case, the paper focuses on functionality evaluation and its auxiliary objective function.

C. CAV Evaluation

  • The evaluation uses a simulated CAV combining adaptive cruise control and autonomous emergency braking, with NDD-distributed scenarios as baseline and library scenarios for the proposed method.The proposed method uses ϵ-greedy sampling with ϵ = 0.05, selected according to Corollary 1 in Part I paper.Source: C. CAV Evaluation · p. 6

IV. HIGHWAY EXIT CASE STUDY

  • In the highway-exit case, the CAV must change lanes right and exit within a specified distance.Functionality evaluation differs from safety evaluation in how it searches for critical scenarios: it designs an auxiliary objective function using task, task solution, task solution difficulty, and task difficulty.Source: §IV · p. 6

C. CAV Evaluation

  • 51 tests versus 9.63×10^4 tests achieved the target accident-rate estimation confidence (α = 0.95, β = 0.3), making the proposed method about 1,888 times faster than NDD evaluation.Both methods accurately estimate the accident rate for the predetermined relative half-width.Source: Figure 7 · p. 6, C. CAV Evaluation · p. 6

A. Problem Formulation

  • The high-dimensional scenario variables include the CAV’s initial state, the number of BVs, and each BV’s trajectory; this case fixes the CAV’s initial position and velocity and considers two BVs.The BVs maintain their initial speeds unless their separation falls below dcf, when the following BV matches the leading BV’s speed.Source: A. Problem Formulation · p. 6

B. Library Generation

  • Highway-exit library generation uses the same methods as the cut-in case, with the paper elaborating only the auxiliary objective function for functionality evaluation.Source: B. Library Generation · p. 6

1) Auxiliary Objective Function Design: · 2) NDD Analysis:

The highway-exit auxiliary objective combines estimated exposure frequency with maneuver challenge, which is framed through task and task-solution difficulty. Exposure frequency is derived from filtered IVBSS car-following data, while feasible lane-change solutions define the task’s challenge.

1) Auxiliary Objective Function Design:

  • The auxiliary objective combines estimated exposure frequency and maneuver challenge, with frequent scenarios forming the common set Ω.Its weight is denoted by w, and the parameter values are listed in Table V.Source: 1) Auxiliary Objective Function Design · p. 7
  • Task difficulty sums task-solution difficulties W(f), where W(f) is negative and larger values indicate greater difficulty.A task solution is a feasible CAV trajectory f ∈ F.Source: 1) Auxiliary Objective Function Design · p. 7
  • The task-difficulty definition captures both the difficulty of finding a feasible solution and the difficulty of completing it.Source: 1) Auxiliary Objective Function Design · p. 7
  • For the highway-exit case, the task is to change right before the off-ramp, and a solution f = (t, p) is a feasible lane-change point.The feasible zone depends on velocity bounds, exit location, safe time-to-collision gaps, and acceleration bounds.Source: 1) Auxiliary Objective Function Design · p. 7
  • The feasible lane-change zone can comprise three isolated regions separated by surrounding-vehicle trajectories, while its boundary depends on velocity bounds and off-ramp location.Source: 1) Auxiliary Objective Function Design · p. 7
  • Assuming equal difficulty for all task solutions, task difficulty is estimated from feasible-zone area S(F) and normalized by US, the area enclosed by the lane-change boundary.Source: 1) Auxiliary Objective Function Design · p. 7

2) NDD Analysis:

  • IVBSS data provide highway-exit exposure information from car-following events involving two BVs in the rightmost lane.The data cover 108 drivers using 16 Honda Accords for over 40 days; filtering for highway travel, speeds of at least 20 m/s, inactive cruise control, dry roads, and daylight yielded 5 × 10^4 events and 1.47 × 10^6 trajectory points.Source: 2) NDD Analysis · p. 7
  • Exposure estimation uses a uniform distribution for the leading BV’s initial position and the NDD trajectory distribution for initial speeds and relative position.The relative position is R = p0,1 − p0,2.Source: 2) NDD Analysis · p. 7

3) SM Construction: … V. CAR-FOLLOWING CASE STUDY

The highway-exit evaluation reaches the same stated estimation precision with far fewer tests than NDD evaluation, while the car-following case formulates high-dimensional scenario-library generation using an MDP and reinforcement learning.

3) SM Construction:

  • MPC predicts pre-lane-change trajectories and selects the lane-change solution with higher MOBIL utility, using a politeness factor near zero such as 0.1.The utility accounts for acceleration changes involving the CAV and the new and old followers.Source: 3) SM Construction · p. 8

4) Library Generation:

  • The highway-exit library contains 1,895 critical scenarios, about 0.12% of all scenarios, after critical-scenario search.The search uses 100 uniformly sampled initial starting points; the feasible variable counts are 61 for p0,i and 21 for v0,i.Source: 4) Library Generation · p. 8

C. CAV Evaluation

  • At β = 0.2, the proposed method reaches task-failure-rate estimation precision in 2.6 × 10^3 tests versus 6.6×10^5 for NDD, about 255 times faster.Both methods obtain unbiased failure-rate estimates at the stated relative half-width.Source: Figure 9 · p. 8, C. CAV Evaluation · p. 8

V. CAR-FOLLOWING CASE STUDY

  • A 30-second car-following scenario has 33 dimensions when the leading BV is controlled every second, creating a curse of dimensionality that existing evaluation methods cannot address.The scenario variables comprise the leading BV's initial velocity, initial range and range rate, and acceleration sequence.Source: §V · p. 8
  • The car-following TSLG problem is represented as an MDP decision tree, where each feasible branch from the initial state to a terminal state defines a scenario.The state comprises BV speed, range, and range rate; the action is the BV's acceleration, assumed to depend on its current speed.Source: §V · pp. 8–9
  • Scenario criticality uses Q(s, u) to combine the probability of event S after a state-action pair with the probability of taking that action in the state.The first probability measures maneuver challenge, and the second represents exposure frequency.Source: §V · p. 9
  • Temporal-difference reinforcement learning estimates Q(s, u), with BV agents interacting with the deterministic-SM CAV environment and updates based on the next state-action value.The paper states that after training, Q converges to the defined values when the TD error is defined as specified; the learning rate example is 0.1.Source: §V · p. 9
  • Pruning uncritical state-action pairs leaves a critical-scenario library containing all branches with V(x|θ) > 0.The paper illustrates critical scenarios as branches of consecutive red nodes and arrows.Source: §V · p. 9, Figure 10 · p. 9

A. Problem formulation for the car-following case

The car-following case evaluates safety using accident rate, with the scenario state defined by leading-vehicle speed, range, and range rate. The leading vehicle’s acceleration is the action, and discretization yields a large scenario space but smaller state and state-action spaces.

  • Safety is the performance metric, represented by accident rate, and the state comprises leading-BV speed, range to the test CAV, and range rate.Source: A. Problem formulation for the… · p. 9
  • For a 30-second case, discretization produces 45,885 states and approximately 1.4 × 10^5 state-action pairs, versus a scenario space of 21 × 115 × 19 × 3130.The leading BV’s acceleration is the action, controlled every second; range, range rate, velocity, and acceleration are discretized by 1 m, 1 m/s, 1 m/s, and 0.2 m²/s, respectively.Source: A. Problem formulation for the… · p. 9

B. Library Generation · C. CAV Evaluation

The car-following library uses NDD-derived exposure frequencies and reinforcement learning to generate testing scenarios, then evaluates a CAV against NDD evaluation at the same estimation precision with far fewer tests.

B. Library Generation

  • Car-following events estimate state exposure P(s), while free-driving events estimate action exposure P(u|s), using the highway-exit case’s NDD.Source: B. Library Generation · p. 9
  • States are classified as collision, dangerous, or safe; P(S|uk, sk) is 1 in the collision zone and 0 in the safe zone.The collision zone comprises states within the accident-distance threshold, while safe states cannot lead to an accident even under maximal lead-vehicle deceleration.Source: B. Library Generation · p. 9
  • A non-trivial scenario starts at a dangerous root state and ends at a collision or safe terminal state, and a critical scenario must contain a collision-zone state.Simulation identifies about 5,000 dangerous states, or 10% of all states.Source: B. Library Generation · pp. 9–10
  • RL training initializes Q values from NDD, uses a uniform training policy, and stops when |δt| < δ0; convergence took about 20 minutes and 3 × 10^6 iterations.The example threshold is δ0 = 10^-10.Source: B. Library Generation · p. 10
  • At dangerous state s = (38, 6, −2), the generated action distribution is more aggressive than NDD, with its highest probability at u = −3.4 m/s2 rather than u = −4 m/s2.Source: B. Library Generation · p. 10, Figure 12 · p. 10

C. CAV Evaluation

  • Scenario sampling uses an ϵ-greedy policy with ϵ = 0.1, allowing accelerations greater than −3 and initial safe states to be sampled with small probability.These accelerations are outside the library’s generated action distribution, where their probability is zero.Source: C. CAV Evaluation · p. 10
  • 50 tests versus 1.875×10^7 tests achieved the same accident-rate estimation precision (β = 0.2), making the proposed method about 3.75 × 10^5 times faster than NDD evaluation.The same CAV car-following model was evaluated with the generated library; NDD evaluation was the baseline.Source: C. CAV Evaluation · p. 10

VI. DISCUSSIONS … VII. CONCLUSIONS

The discussion weighs the method’s advantages and limitations, while the conclusion reports its evaluation results and identifies directions for further work.

A. Advantages of the proposed method

VI. DISCUSSIONS

  • Across cases, acceleration varied with dissimilarity between the scenario model and tested CAV, which affects the method’s efficiency.Common human-driving models performed reasonably well as starting points, but adaptive model modification warrants further investigation; developers can use the CAV model directly for scenario generation.Source: §VI · p. 10, B. Limitations of the proposed method · p. 11

B. Limitations of the proposed method

  • Applying the method requires large-scale NDD to calculate scenario exposure frequency, though sensors may make such data more accessible and less costly to collect.The passage cites research institutes and companies including Waymo, Tesla, and Mobileye as data collectors.Source: B. Limitations of the proposed method · p. 11

VII. CONCLUSIONS

  • The method accelerated evaluation 255 to 3.75 × 10^5 times compared with the NDD evaluation method, with the same accuracy across all three cases.Source: §VII · p. 11
  • The combined papers present the first systematic framework and implementation guidelines across scenario dimensions, performance metrics, and CAV models.Future work includes adaptive updates to the scenario model and library, and improving RL-enhanced generation for extremely high-dimensional settings such as urban driving with hundreds of background vehicles.Source: §VII · p. 11

APPENDIX A PROOF OF THEOREMS

The appendix proves a scenario-criticality calculation based on decision-tree exposure frequency and establishes TD-RL convergence of Q(u, s) under the specified TD-error definition.

APPENDIX A PROOF OF THEOREMS

  • Theorem 1 derives scenario criticality from decision-tree exposure frequency, the criticality definition, Bayesian equation, and law of total probability.The proof substitutes the resulting relations into the criticality expression to conclude the theorem.Source: Appendix A · p. 12
  • After training, TD-RL’s Q(u, s) converges to the values defined in Eq. (26) when the TD error is defined as specified.The proof uses the deterministic scenario model when deriving an equivalence and relates the TD error to the next-state estimate.Source: Appendix A · p. 12
Loading 1905.03428v3…