Complexity Evaluation of Test Scenarios for Autonomous Vehicle Safety Validation Using Information Theory

2.1. Complexity Quantification

2.2. Scenario-Based Validation Testing

3.1. Kinematic Model for Vehicle Position and Dynamics

3.2. Dynamic Scenario Complexity Calculation

3.3. Sample-Based Search Algorithm

Figure 3. Trajectory boundary definition.

Figure 3. Trajectory boundary definition.

4.1. Scenarios and Complexity Calculation

D1.

Cut-in Scenario A: In this scenario, Vehicle A is in traffic behind Vehicle B, and another vehicle, C, is making a “cut-in” maneuver toward Vehicle A’s lane. Vehicle A is the subject vehicle, and the scenario complexity is calculated from the perspective of this vehicle. The vehicle motions of Vehicle B and Vehicle C are known as shown in Figure 4.

Table 1 below describes for each trajectory of the subject vehicle if other vehicles must be considered in the entropy calculation or not. This consideration depends on whether the vehicle motion intersects with a trajectory within the fan-shaped area of the subject vehicle or if a traffic participant is directly within the fan-shaped area. For example, Vehicle C is considered for the entropy calculation of the subject vehicle for the leftmost trajectory ($\tau$ = −5) because of the intersection. For the specific trajectory ($\tau$ = 0), just Vehicle B is considered because this vehicle is in the fan-shaped area of the subject Vehicle A.

For all driving scenarios D1–D6, Vehicle A has the same trajectory choices and weights. The difference between scenarios is the placement, trajectory, and involvement of Vehicles B and C. To compare scenarios concisely, we adapt Equation (3) to reflect the pattern in Table 1:

$$C_{\mathrm{D}}=\sum H_{\mathrm{Subject}}\left(\tau =i\right)=\sum H_A\left(\tau =i\right)+\sum {\lambda }_B{H}_B\left(\tau =i\right)+\sum {\lambda }_C{H}_C\left(\tau =i\right)$$

(4)

where i is the index of the fifteen (15) possible discretized trajectories:

$$i\in \{-5,-4,-3,-2,-1.5,-1,-0.5,0,0.5,1,1.5,2,3,4,5\}$$

In this representation, $C_{\mathrm{D}}$ is the sum of all entity trajectories that overlap with the subject vehicle’s trajectories. Since the surrounding dynamic entities in this driving scenario are vehicles, the influence of those in scenarios D1–D5 is ${\lambda }_B={\lambda }_C=1$.

In this driving scenario example, we will calculate the entropy of the subject vehicle, Vehicle A, for all scenarios D1–D6. Vehicle A has 15 possible trajectories that it may select. In this step, we find the entropy $H_A$ of all potential trajectories for Vehicle A:

$$\begin{array}{c}{H}_A(\tau =-5)=-p({\tau }_{-5}){log}_2{(}_{-5})=-1.49({10}^{-6}){log}_2(1.49({10}^{-6}))=2.9({10}^{-5})\\ H_A(\tau =-4)=-p({\tau }_{-4}){log}_2{(}_{-4})=-0.000134{log}_2(0.000134)=0.001724\\ H_A(\tau =-3)=-p({\tau }_{-3}){log}_2{(}_{-3})=-0.004432{log}_2(0.004432)=0.034649\\ H_A(\tau =-2)=-p({\tau }_{-2}){log}_2{(}_{-2})=-0.053991{log}_2(0.053991)=0.227364\\ H_A(\tau =-1.5)=-p({\tau }_{-1.5}){log}_2{(}_{-1.5})=-0.129518{log}_2(0.129518)=0.38192\\ H_A(\tau =-1)=-p({\tau }_{-1}){log}_2{(}_{-1})=-0.241971{log}_2(0.241971)=0.495337\\ H_A(\tau =-0.5)=-p({\tau }_{-0.5}){log}_2{(}_{-0.5})=-0.352065{log}_2(0.352065)=0.53024\\ H_A(\tau =0)=-p({\tau }_0){log}_2{(}_0)=-0.398942{log}_2(0.398942)=0.528897\\ H_A(\tau =0.5)=-p({\tau }_{0.5}){log}_2{(}_{0.5})=-0.352065{log}_2(0.352065)=0.53024\\ H_A(\tau =1)=-p({\tau }_1){log}_2{(}_1)=-0.241971{log}_2(0.241971)=0.495337\\ H_A(\tau =1.5)=-p({\tau }_{1.5}){log}_2{(}_{1.5})=-0.129518{log}_2(0.129518)=0.38192\\ H_A(\tau =2)=-p({\tau }_2){log}_2{(}_2)=-0.053991{log}_2(0.053991)=0.227364\\ H_A(\tau =3)=-p({\tau }_3){log}_2{(}_3)=-0.004432{log}_2(0.004432)=0.034649\\ H_A(\tau =4)=-p({\tau }_4){log}_2{(}_4)=-0.000134{log}_2(0.000134)=0.001724\\ H_A(\tau =5)=-p({\tau }_5){log}_2{(}_5)=-1.49({10}^{-6}){log}_2(1.49({10}^{-6}))=2.9({10}^{-5})\end{array}$$

The trajectories of Vehicle A overlap only themselves. Thus, the total entropy for $H_A$ is:

$$\sum H_A\left(\tau =i\right)=3.871423$$

(5)

We apply our dynamic scenario complexity calculation and calculate the entropy of the surrounding Vehicle B and Vehicle C in this driving scenario. We know the motion of Vehicles B and C. Vehicle B follows its current path that corresponds to the trajectory $\tau =0$. The other vehicle, C, does a “cut-in” maneuver toward vehicle A’s lane. This movement corresponds to trajectory $\tau =3$. We solve the entropy equations for surrounding Vehicles B and C using Equation (1). The trajectory of vehicle B overlaps seven (7) trajectories of Vehicle A. We solve for the influence of vehicle B:

$$\sum {\lambda }_B{H}_B\left(\tau =i\right)=7{\lambda }_B{H}_B(\tau =0)=(7)(1)\left(-p({\tau }_0){log}_{2}p({\tau }_0)\right)=(7)(-0.398942){log}_2(0.398942)=3.70227$$

(6)

The trajectory of Vehicle C overlaps five (5) trajectories of Vehicle A. We solve for the influence of Vehicle C:

$$\sum {\lambda }_C{H}_C\left(\tau =i\right)=5{\lambda }_C{H}_C\left(\tau =i\right)=(5)(1)\left(-p({\tau }_3){log}_{2}p({\tau }_3)\right)=(5)(-0.004432){log}_2(0.004432)=0.17324$$

To calculate the scenario complicity for scenario D1, we sum the influence of all vehicles as described by Equation (4):

$$C_{\mathrm{D}1}=\sum H_{\mathrm{Subject}}\left(\tau =i\right)=3.871423+3.70227+0.17324=7.746933$$

The scenario complexity score is 7.746933.

D2.

Cut-in Scenario B: In this scenario, Vehicle A is in traffic behind Vehicle B, and another Vehicle C is making a “cut-in” maneuver towards Vehicle A’s lane. Compared to the previous cut-in scenario, Vehicle B is never considered in the calculation because it is not in the drivable area of the subject Vehicle A. Figure 5 shows that Vehicle C is considered for the calculation of the entropy of the subject vehicle for trajectories $\tau =-5$, $\tau =-4$, $\tau =-3$ and $\tau =-2$.

The trajectory of Vehicle C overlaps with four (4) trajectories of Vehicle A. We solve for the influence of Vehicle C:

$$\sum {\lambda }_C{H}_C\left(\tau =i\right)=(4)(1)(-0.004432){log}_2(0.004432)=0.138596$$

$H_A$ is unchanged from Equation (5) and $H_B=0$. Thus, the scenario complexity is calculated as follows:

$$C_{\mathrm{D}2}=\sum H_{\mathrm{Subject}}\left(\tau =i\right)=3.871423+0+0.138596=4.010019$$

D3.

2-Lanes Traffic Scenario: In this scenario (Figure 6), Vehicle A is in traffic behind Vehicle B. Vehicle C continues straight in the lane next to the subject Vehicle A’s lane. Vehicle C is not considered in the scenario complexity calculation because it is not in the drivable area of the subject Vehicle A. Vehicle B is considered for the entropy calculation for the trajectories $\tau =-1.5$, $\tau =-1$, $\tau =-0.5$, $\tau =0$, $\tau =0.5$, $\tau =1$ and $\tau =1.5$.

The trajectory of vehicle B ($\tau =0$) overlaps with seven (7) trajectories of Vehicle A. The influence is already calculated in Equation (6) to be $H_B=3.70227$. Thus, the scenario complexity is calculated as follows:

$$C_{\mathrm{D}3}=\sum H_{\mathrm{Subject}}\left(\tau =i\right)=3.871423+3.70227+0=7.573693$$

D4.

2-Lanes No Traffic Scenario: In this scenario, there is no traffic participant other than subject Vehicle A (Figure 7), which means $H_B=H_C=0$. The scenario complexity is calculated as follows:

$$C_{\mathrm{D}4}=\sum H_{\mathrm{Subject}}\left(\tau =i\right)=3.871423+0+0=3.871423$$

D5.

3-Lanes Traffic Scenario: Figure 8 shows the configuration of the fifth scenario. In this scenario, Vehicle A is in the middle traffic lane between Vehicle B and Vehicle C. Vehicle A is the subject vehicle, and the scenario complexity is calculated from the perspective of this vehicle. Vehicle B and Vehicle C go straight into their lane. Vehicle B is not considered in the scenario complexity calculation because it is not in the drivable area of the subject Vehicle A. Vehicle C is considered for the entropy calculation of the subject vehicle for the trajectory $\tau =-5$.

The trajectory of Vehicle C ($\tau =0$) overlaps with one (1) trajectory of Vehicle A. We solve for the influence of Vehicle C:

$$\sum {\lambda }_C{H}_C\left(\tau =i\right)=(1)(1)(-0.398942){log}_2(0.398942)=0.528897$$

The scenario complexity is calculated as follows:

$$C_{\mathrm{D}5}=\sum H_{\mathrm{Subject}}\left(\tau =i\right)=3.871423+0+0.528897=4.40032$$

D6.

2-Lanes No Traffic with Pedestrian Crossing Scenario: In this last scenario, the subject vehicle is surrounded by no other vehicle, but a pedestrian is crossing the subject vehicle’s path (Figure 9). The pedestrian is considered for the entropy calculation of the subject vehicle for the trajectories $\tau =2$ and $\tau =3$.

The trajectory of Pedestrian P ($\tau =0$) overlaps with two trajectories of Vehicle A, and as a pedestrian, the influence is $\lambda =0.8$. We solve for the influence of Pedestrian P:

$$\sum {\lambda }_P{H}_P\left(\tau =i\right)=(0.8)(2)(-0.398942){log}_2(0.398942)=0.8462352$$

The scenario complexity is the sum of all influences in the scenario, which are $H_A$ and $H_P$. Thus, the scenario complexity is calculated:

$$C_{\mathrm{D}6}=\sum H_{\mathrm{Subject}}\left(\tau =i\right)=\sum {\lambda }_P{H}_P\left(\tau =i\right)+\sum {\lambda }_P{H}_P\left(\tau =i\right)=3.871423+0.8462352=4.717658$$

4.2. Simulation Scenarios and Complexity Classification

4.2.2. Simulation Scenarios Setup

A summary of the scenario setups is presented in Table 2. The two drivable cut-in scenarios (D1 and D2) are combined in one scenario (L1) that satisfies both configurations (See Figure 10). The remaining drivable scenarios are also abstracted into logical scenarios:

• L2 is 2-lanes with traffic scenario (Figure 11).
• L3 is 2-lanes without traffic scenario (Figure 12).
• L4 is 3-lanes with traffic scenario (Figure 13).
• L4 is a pedestrian crossing scenario (Figure 14).

Figure 10. SUMO simulation of Scenario L1.

Figure 10. SUMO simulation of Scenario L1.

Table 2. Scenario Setup.

Table 2. Scenario Setup.

Logical
Scenario:	L1	L2	L3	L4	L5
Driving	D1
Scenario:	D2	D3	D4	D5	D6
Road Network Configuration
lanes	2	2	2	3	2
actors	3	3	1	3	2
ped X-ing					✔
Actor Placement
lane 2				C
lane 1	C	C		A
lane 0	AB	AB	A	B	A
sidewalk					P
Parameter Ranges
$s_{0_A}$	✔	✔	✔	✔	✔
$s_{0_B}$	✔	✔		✔
$s_{0_C}$	✔	✔		✔
${\mathrm{dist}}_{BA}$	✔	✔		✔
${\mathrm{dist}}_{CA}$	✔	✔		✔
${\mathrm{dist}}_{PA}$					✔
${\mathrm{dist}}_{P_0}$					✔
lcd	✔
Performance Metrics
$C_D$	✔	✔	✔	✔	✔
${\mathrm{collision}}_A$	✔	✔	✔	✔	✔
max(decelA)	✔	✔	✔	✔	✔
min(dtcAB)	✔	✔			✔
min(dtcAC)	✔	✔			✔
min(dtcAP)				✔
min(ttcAB)	✔	✔			✔
min(ttcAC)	✔	✔			✔
min(ttcAP)				✔

Using SUMO and TraCI, which allows micro-control of the SUMO simulator, scenarios are implemented on road networks with lanes 3.5 m wide, sidewalks 2 m wide, and maximum network speed set to 50 mps. The vehicle parameters used are a maximum speed of 15 mps, a wheelbase of 2.63 m, and a maximum steering angle of 10 degrees. The vehicle AI used is the SUMO no-collision AI, which attempts to keep a gap of 2.5 m between vehicles and utilizes a driving plan that prevents the need for excessive braking when possible, i.e., braking force > 4.5 mps². The pedestrian in the simulations always begins at a speed of 0 mps, has a maximum speed of 1.2 mps, and acceleration of 1.5 mps².

The parameter ranges used in the scenarios vary according to the scenario requirements, as shown in Table 2. For each scenario, as depicted in Figure 10, Figure 11, Figure 12, Figure 13 and Figure 14, the blue vehicle is the subject Vehicle A, the red vehicle represents Vehicle B, and the green vehicle represents Vehicle C. The parameter ranges for these scenarios are defined as follows:

• The initial speed of Vehicle A 0 mps $\le s_{0_A}\le$ 15 mps by $0.27$ mps increments.
• The initial speed of Vehicle B 0 mps $\le s_{0_B}\le$ 15 mps by $0.27$ mps.
• The initial speed of Vehicle C 0 mps $\le s_{0_C}\le$ 15 mps by $0.27$ mps.
• The initial lateral distance of Vehicle B from Vehicle A ${\mathrm{dist}}_{BA}$. For scenarios L1 and L2. 10 m ≤ ${\mathrm{dist}}_{BA}\le$ 30 m by 1 m. For scenario L4 0 m ≤ ${\mathrm{dist}}_{BA}\le$ 30 m by 1.
• The initial lateral distance of Vehicle C from Vehicle A 0 m ≤ ${\mathrm{dist}}_{CA}\le$ 30 m by 1 m.
• The initial lateral distance of Pedestrian P from Vehicle A 0 m ≤ ${\mathrm{dist}}_{PA}\le$ 30 m by 1 m.
• The distance Pedestrian P begins from the start of the crosswalk measured from right-to-left of the front of Vehicle A 0 m ≤ ${\mathrm{dist}}_{P_0}\le$ 5 m by 1 m.
• The duration of time a vehicle takes to transition from one lane to another during a lane-change maneuver, i.e., lane-change duration (lcd), 0.5 s ≤ lcd ≤ 5 s by 0.1 s.

Scenarios are evaluated using several performance metrics. Distance to collision (DTC) and TTC are commonly used to define these metrics. Hence, it is important to define DTC and TTC. DTC is the Euclidean distance between two positions, p and q, at the time instant i:

$${\mathrm{dtc}}_i(p_i,q_i)=\sqrt{{(q_{x_i}-p_{x_i})}^2+{(q_{y_i}-p_{y_i})}^2}$$

The point of reference for the position is the center of the front of the vehicle or pedestrian. TTC at the time instant i for two vehicles is:

$${\mathrm{TTC}}_i={\displaystyle \frac{{\mathrm{dtc}}_i}{s_{{\mathrm{rel}}_i}}}$$

where $s_{{\mathrm{rel}}_i}$ is the relative speed between two vehicles at moment i. With DTC and TTC defined, the performance metrics can be listed as follows:

• $C_D$, scenario complexity prediction.
• collision_A, whether Vehicle A is involved in a collision (collision_A = 1) or not (collision_A = 0).
• max(decel_A), the maximum deceleration force of Vehicle A observed during the testing window.
• min(dtc_AB), the minimum DTC between Vehicles A and B observed during the testing window.
• min(dtc_AC), the minimum DTC between Vehicles A and C observed during the testing window.
• min(dtc_AP), the minimum DTC between Vehicle A and Pedestrian P observed during the testing window.
• min(ttc_AB), the minimum TTC between Vehicles A and B observed during the testing window.
• min(ttc_AC), the minimum TTC between Vehicles A and C observed during the testing window.
• min(ttc_AP), the minimum TTC between Vehicle A and Pedestrian P observed during the testing window.

Table 2 shows the performance metrics used for each simulation scenario. Both distance and time metrics are used as part of the performance metrics. DTC metrics provide a concise estimation of the closeness between actors using the terminology of the ODD, thus allowing the performance metric to be compared as a ratio to vehicle properties such as length and min gap. Likewise, TTC directly estimates the collision risk using DTC and the relative speed of actors, allowing the performance metric to be compared as a ratio of relative actor speeds and distances.

A limitation of the TTC metric is the assumption that the speed of actors is constant when calculating the time to a possible collision. However, the limitation comes with the trade-off of reduced time and resource costs during simulation tests. In this paper, no further performance metrics are used; however, there exist other supplementary performance metrics which may be considered:

• Deceleration Rate to Avoid Collision (DRAC) represents the rate at which a vehicle must decelerate to avoid a collision with another actor or object. DRAC may be defined as:

  $$\mathrm{DRAC}={\displaystyle \frac{v^2}{2d}}$$

  where v is the relative speed of the vehicle and d is the distance to the other actor or object.
• Modified Time to Collision (MTTC) takes into account relative acceleration a, which provides a more accurate estimation of TTC where relative velocity v is assumed to be constant. MTTC may be defined as:

  $$\mathrm{MTTC}={\displaystyle \frac{-v\pm \sqrt{v^2-2ad}}{a}}$$

  where v is relative velocity, a is relative acceleration, and d is relative distance between two actors. The MTTC equation is quadratic and, as such, evaluates to two solutions. The negative solution may be mathematically valid but physically irrelevant, e.g., the objects are not at their current positions.
• Proportion of Stopping Distance (PSD) quantifies the ratio of the distance available to stop a vehicle $d_a$ to the physically required stopping distance under current conditions $d_r$. PSD may be defined as:

  $$\mathrm{PSD}={\displaystyle \frac{d_a}{d_r}}$$

  where $d_a$ is the available stopping distance and $d_r$ is the required stopping distance. When PSD ≥ 1, the vehicle has adequate space to stop safely with normal braking force. When PSD < 1, the vehicle has inadequate space to stop safely, which means the vehicle must find another means to avoid a collision, e.g., going around the obstacle.

Using the performance metrics, a ranking system for the scenarios can be determined by categorizing the scenarios in three ways:

• Collision: The subject vehicle collides with another dynamic traffic participant. If an accident happens, the performance metrics TTC and DTC are both zero.
• Near Collision: In these scenarios, the subject vehicle is not involved in a collision, but the braking exceeds the normal braking force of 4.5 mps. This category represents situations in which the subject vehicle must make an immediate decision to slow down to avoid a collision.
• Normal Operation: The subject vehicle operates normally and as expected within the environment. The subject vehicle is not involved in any collision, and the braking forces do not exceed 4.5 mps.

A driving scenario is considered complex if collisions or near-collisions occur during simulation. By implementing simulation testing according to the explained approach, the driving scenarios are modeled and evaluated. Each scenario is tested 10,000 times using the parameter ranges, and the testing window is set to 3 s. The results for each of the scenarios are presented in the following subsections.