J. Cent. South Univ. (2018) 25: 2164-2181

DOI: https://doi.org/10.1007/s11771-018-3905-6

Cooperative driving model for non-signalized intersections with cooperative games

YANG Zhuo(杨卓), HUANG He(黄何), WANG Guan(王冠), PEI Xin(裴欣), YAO Dan-ya(姚丹亚)

Department of Automation, Tsinghua University, Beijing 100084, China

Central South University Press and Springer-Verlag GmbH Germany, part of Springer Nature 2018

Abstract: Cooperative driving around intersections has aroused increasing interest in the last five years. Meanwhile, driving safety in non-signalized intersections has become an issue that has attracted attention globally. In view of the potential collision risk when more than three vehicles approach a non-signalized intersection from different directions, we propose a driving model using cooperative game theory. First, the characteristic functions of this model are primarily established on each vehicle’s profit function and include safety, rapidity and comfort indicators. Second, the Shapley theorem is adopted, and its group rationality, individual rationality, and uniqueness are proved to be suitable for the characteristic functions of the model. Following this, different drivers’ characteristics are considered. In order to simplify the calculation process, a zero-mean normalization method is introduced. In addition, a genetic algorithm method is adopted to search an optimal strategy set in the constrained multi-objective optimization problem. Finally, the model is confirmed as valid after simulation with a series of initial conditions.

Key words: cooperative driving; multi-vehicles-cross process; cooperative games; Shapley value; genetic algorithm

Cite this article as: YANG Zhuo, HUANG He, WANG Guan, PEI Xin, YAO Dan-ya. Cooperative driving model for non-signalized intersections with cooperative games [J]. Journal of Central South University, 2018, 25(9): 2164–2181. DOI: https://doi.org/10.1007/s11771-018-3905-6.

1 Introduction

The multi-vehicles-cross process happens when more than three vehicles approach a non- signalized intersection from different directions. It is a complex and interactive scenario. As an independent actor, each driver in this process must make corresponding decisions about how to pass through this area safely. Unfortunately, it is difficult for drivers to make accurate decisions with subjective judgments. A lack of comprehensive consciousness about the current driving environment is one of the most important factors in such cases, as it contradicts assumptions that separate drivers can acquire vehicle state information from one another. Issues of how to assist drivers in avoiding potential conflicts in this process using information exchanges have emerged. Therefore, it is essential to propose an effective algorithm for vehicle collision avoidance systems (CAS) to solve issues of driving safety.

The concept of cooperative driving was first described by the Association of Electronic Technology for Automobile Traffic and Driving in Japan in the early 1990s [1]. Since then, many studies based on this concept have been carried out.

In previous research [2, 3], an automated guided vehicle system (AGVS) was presented, where a simple case involving two vehicles was analyzed using dynamic game theory with incomplete information. Assuming that no communication existed between the two vehicles, and the action of one was a disturbance to the other, a series of differential strategies were generated. Cooperative driving methods with communication obviously perform better than cases without communication. Moreover, it is especially necessary when simultaneously dealing with three or more vehicles (multi-vehicles-cross process). In recent years, the feasibility and benefits of cooperative driving modes have been widely discussed. These include the PATH project in the USA [4], Demo 2000 cooperative driving scenario in Japan [5], the Chauffeur project in the EU [6], and the i-VICS project in China [7].

The significance of communication to cooperative driving is also discussed in Sakaguchi’s work [8]. The data transmission algorithm was described for both unidirectional and omni- directional media in a platoon. Simulation results showed that the throughput rate was larger than that of a conventional system when the number of vehicles was less than 15. Meanwhile, a merging control algorithm was also presented to make the best use of the inter-vehicle communications.

With a basic and modified solution tree generation algorithm, the idea of a cooperative driving platoon was extended to collision-free driving in a non-signalized intersection [9]. This greatly benefited vehicle groups by improving efficiency at the intersection. In LIU’s study [10], a simple two-vehicles-cross process involving only safety and rapidity factors was introduced using dynamic games. The acceleration value was a fixed set of {–2, 2} in the strategies, which resulted in four combinations for comparison. However, this method is not rational in real-world circumstances.

A cooperative driving model based on reduplicate dynamic games was presented [11]. In this research, a series of acceleration vectors are strategies in the game. Moreover, the range of strategies in their model was set as a continuous interval [–3, 3]. Nevertheless, it was difficult to produce a global optimal solution for all players owing to the subjectivity of players in a non-cooperative game. The more vehicles there are, the more difficult it is to get the best profit in a multi-vehicles-cross process.

In this work, we propose a modified cooperative driving model with cooperative games, in which vehicles’ profit functions and the model’s characteristic functions are established. Based on the Shapley theorem, the functions of group rationality, individual rationality and uniqueness are verified. Furthermore, a genetic algorithm is utilized to acquire a series of analytical solutions during the multi-vehicles-cross process. In the following sections, some basic assumptions and definitions for cooperative driving with cooperative games are described. A multi-vehicles-cross model is then proposed to solve a new constrained multi-objective optimization problem, and some essential attributes are subsequently proved. An algorithm flow is designed to show how the CAS works. Finally, several simulation results are presented to show the feasibility of the proposed model.

2 Problem presentation

A non-signalized intersection with three one-way traffic streams is shown in Figure 1. Vehicle 1 and Vehicle 2 drive to the intersection from definite directions with velocity v₁, v₂ and acceleration a₁, a₂. Here, Vehicle 3 approaches from the north, and it will turn left (to the east) once arriving the intersection with the parameters v₃, a₃. In their driving paths, there are three potential conflict points: red No. 1, brown No. 2, and blue No. 3. The distances to Point 1 are L₁₂ from Vehicle 1 and L₂₁ from Vehicle 2. The distances to Point 2 are L₂₃ from Vehicle 2 and L₃₂ from Vehicle 3. The distances to Point 3 are L₁₃ from Vehicle 1 and L₃₁ from Vehicle 3.

Figure 1 Illustration of multi-vehicles-cross process at non-signalized intersection

We assume that all the three vehicles’ information can be freely exchanged using the V2V communication systems. Most importantly, whether or not the driving situation is safe should be judged by the collision avoidance system (CAS) in real time.

Three aspects will be discussed in the multi-vehicles-cross process. The first is conflict judgment among vehicles, which judges vehicle safety states and determines the efficacy of the CAS. The second is cooperatives games component, which describes cooperative game theory and the Shapley theorem. Finally, the optimization algorithm demonstrates how to solve a constrained multi-objective optimization problem within the cooperative games.

2.1 Conflict judgment among vehicles

To analyze whether there is a potential conflict among vehicles in the intersection, the criteria for judgment must first be explained (Figure 1). Time-to-Collision (TTC) is a widely-used parameter, but is better suited for rear-end collisions occurring in the same lane. As shown in Figure 1, it is obvious that the positions of the conflict points are relatively fixed in the intersection. Therefore, time-difference-to-collision (TDTC, T_dtc) is a more useful parameter to solve this problem [11]. A kind of orthogonal collision form is considered, and the TDTC parameter is given as:

    (1)

where L_k is the position of vehicles’ kth conflict point in the intersection, v _i, v _j are the vehicle velocities, and L_i, L_j are the distances from their current positions to the conflict point; T_M is a time threshold set to judge the driving safety state. If Eq. (1) holds, a potential collision risk exists.

As shown in Figure 2, if the situation meets (1), the CAS will work immediately at T_start, where

      (2)

Figure 2 Illustration of CAS works when condition meets

2.2 Cooperative games

Game theory has traditionally been divided into two categories: non-cooperative and cooperative. The former merely emphasizes the maximization of individual profit in a game, making it more difficult to achieve true maximal profit owing to competition. On the contrary, the latter will achieve superior profit via coalition through a consensus among individuals. When solving a multi-vehicles-cross problem, a cooperative game model is sometimes preferable. In addition, it is a useful method for determining how to rationally distribute profit in a cooperative model. Thus, it can be considered a kind of compromise mechanism. The most significant fact is that the profits of individuals and the whole are increased with cooperative games.

The multi-vehicles-cross process is considered to be a static game, as all drivers are requested to make decisions [10–13]. For a cooperative game, the following three definitions must be emphasized [14]:

Definition 1 (superadditivity)

A cooperative game is superadditive if its characteristic function satisfies the following inequality:

   (3)

This means that profit is larger in the consolidated coalition than the two separate coalitions S and T.

Definition 2 (Individual rationality)

A set of vectorsis the solution of a cooperative game. If it satisfies

                         (4)

it has individual rationality. This means that each participant could receive more profit with this solution than before.

Definition 3 (Group rationality)

A set of vectorsis the solution of a cooperative game. If it satisfies

                 (5)

it has group rationality. This means that the sum of each participant’s profit is equal to the coalition’s profit.

It has long been difficult to establish the concept of a unified solution in cooperative games [14]. Thus, a novel method was proposed by Lloyd Shapley, which is useful in determining the contribution rate of each participant to a coalition.

Theorem 1 (Shapley theorem)

A set of vectorsis the solution of a cooperative game. It can be called Shapley value, if

                                (6)

where is the number of members in the coalition S.

Regarding cooperative game theory [14], a normal cooperative game contains three elements: players, strategies, and profits. Here, those elements can be used for the entire multi-vehicles-cross process

 (7)

In detail, the longitudinal state of a vehicle is only controlled by the throttle and brake pedals, which means that the variation of acceleration is fundamental to the safety of the vehicle. Therefore, acceleration consists of three different forms in Eq. (7).

Moreover, the following hypotheses are essential for the simplified model in Figure 1.

As seen in Figure 1, L₃₁ includes straight distance and steering distance. The latter’s value is 10 m in this model (as an approximate calculation). The distance between conflict points 1 and 2 is 5 m. The same is true for points 1 and 3.

2.3 Optimization algorithm

The acceleration set (a₁, a₂, …, a_n) of the vehicle j=1, 2, …, n is the key data point for the entire multi-vehicles-cross process. The best solution can be calculated using Shapley value method (Theorem 1) in each cycle of the whole process. However, there are still two unanswered questions:

1) The Shapley allocation is each player’s expected contribution to any possible sequencing of players joining the grand coalition. Hence, how do we determine which acceleration set provides the optimal solution?

2) Assuming that the corresponding acceleration set has been obtained, how do we determine whether it is an optimal solution in this model?

Thus, an optimization problem must also be resolved. Here, is the profit of the vehicle j calculated by the system according to Theorem 1 in the ith cycleHence, the solution is described as follows during the whole multi-vehicles-cross process:

 (8)

where,

                    (9)

To maximize the profit of each vehicle in the cooperative game, the best strategy will be chosen by:

                (10)

where a_min, a_max are the minimum and maximum acceleration, respectively. As a constraint condition, the velocity v_j must be kept between the minimum velocity V_min and the maximum velocity V_max.

A series of intelligent search algorithms can be utilized to solve this constrained multi-objective optimization problem (10).

3 Cooperative driving model

An appropriate and reasonable characteristic function is key to a cooperative game. This section will focus on the selection of this characteristic function.

3.1 Characteristic function selection

2ⁿ carriers are required in the ith cycle of vehicles-cross process; specifically, , First, the profit function of each vehicle will be examined. As described in Ref. [11], a profit function consists of three parts: safety, rapidity, and comfort.

3.1.1 Safety indicator

Safety is the most important indicator in a CAS, which is designed to ensure driver safety. Here, this is given as [10, 11]:

         (11)

where superscript i denotes the ith cycle and subscripts j, k denote vehicles j and k; Furthermore V_min, V_max are the minimum and maximum velocities in the intersection;denotes the TDTC of vehicles j and k in the ith cycle.

3.1.2 Rapidity indicator

Rapidity is also a principal indicator in this model. Its form is given as [10, 11]:

      (12)

where is the acceleration of vehicle j in the ith cycle, and is time interval between the ith and the i-1th cycles in the model.

3.1.3 Comfort indicator

In the actual driving experience, it is easy to cause incommodity by switching brake and throttle pedals frequently. Moreover, excessive acceleration or deceleration also provides a bad driving experience. As discussed in Ref. [11], the comfort indicator is given as:

         (13)

In detail, bad acceleration is defined as a condition that causes severe discomfort to the driver. Here, it is expressed in the following three instances [11]:

1) when orwhen

2) whenor

3) or lasts for 3 cycles or more.

A weighted sum of all the three indicators is given as follows:

              (14)

where α_j, β_j, γ_j are the weight coefficients corresponding to the driver j.

However, there is only one vehicle in the carrier {i}, which means that this vehicle does not care if there is a potential collision. Thus, in Eq. (14) will be omitted. To further simplify the model, the behavior characteristics of the three drivers are set to the same as α, β and γ. Henceforth, superscript i will be omitted to obtain a concise formula.

Thus, characteristic functions of the 2ⁿ carriers are given in Eq. (15).

As a cooperative game with the transferable payoff, the greatest profit is reasonable. To acquire more profit for the grand coalition, is adopted in Eq. (15), where

 (15)

3.2 Characteristic function proof

A Shapley value is established on the basis of definitions 1, 2 and 3. Thus, reasonable characteristic functions should be satisfied with individual rationality, group rationality, and uniqueness [14]. Here, they are proved using the selected characteristic functions in Eq. (15).

To simplify Eq. (15) and the following proofs intuitively, some simplified symbols are given in Table 1.

Thus, vehicle i’s profit, assigned using the Shapley theorem, can be described as in Eq.(16).

Table 1 Interpretation of simplified symbols

     (16)

3.2.1 Group rationality proof

Proof: According to Eq. (16) and Table 1, the Shapley value of the vehicle i is:

Hence,

3.2.2 Individual rationality proof

Here, three sub-propositions are proved:

1)

Proof: According to Eq. (16) and Table 1,

Hence, the inequality holds:

2)

Proof: According to Eq. (16) and Table 1,

Here,Hence, the inequality holds:

3)

Proof: According to Eq. (16) and Table 1,

whereand Hence, the inequality holds.

3.2.3 Uniqueness proof

Proof: The parameters are calculated by the system in each cycle throughout the process with Eq. (16). Furthermore, these parameters are unique according to Theorem 1. Hence, the characteristic functions selected are unique.

Therefore, the characteristic functions in Eq. (15) are all reasonable.

3.3 Normalization

Considering the different dimensions of the three inputs on the right side in Eq. (14), a zero-mean normalization method was adopted and expressed as:

                             (17)

where y^* represents the normalized input vectors, and y represents the original input vectors. Furthermore, μ_y is the expectations of y, and σ_y is a standard deviation of y.

3.4 Genetic algorithm

As previously mentioned, it is critical to acquire the best solution (a₁, a₂, …, a_n) according to the corresponding Shapley value (Φ₁, Φ₂, …, Φ_n). Thus, a genetic algorithm (GA) method was adopted; a binary matrix was used as the population of the accelerations.

Solution precision was set as 0.1 m/s² in the model. Hence, the acceleration range contained 60 different values owing to The length of each single chromosome in the GA was 6:

                            (18)

The other parameters refer to a standard genetic algorithm [15, 16]. The optimal strategy for the entire multi-vehicles-cross process is expressed in Eq. (10).

4 Algorithm design

The CAS operational flow chart is shown in Figure 3. The five steps in the model are as follows:

1) Judge n vehicles’ situations

When the system operates is dependent on n vehicles’ situations. If any vehicle is leaving the intersection, the number of vehicles will become n–1, and the system jumps to step 4); otherwise, it continues to step 2).

2) Select n vehicles’ driving modes

In real time, the CAS compares the values of TDTC(t) and T_M in Eq. (1). If the value of the former is greater, usual driving mode will be chosen for n drivers. This means that CAS is inoperative, all drivers can maintain their driving habits, and the system returns to step 1). Otherwise, the system continues to next step 3).

3) Select n vehicles’ driving modes

Where the CAS was engaged, cooperative game theory was adopted in this model and the Shapley value was calculated using Eqs. (8) and (9). Next, the constrained MOP Eq. (10) was solved using the GA method, and the new acceleration set was obtained. Following this, drivers continued the vehicles-cross process with new velocities and new positions . Finally, the system returned to step 1).

4) Select n–1 vehicles’ driving modes

If any vehicle leaves the intersection, the system judged the situations of n–1 vehicles. In this step, the CAS determined the n–1 vehicles’ states and decided which driving modes were required for the remaining vehicles. Following this, the CAS returned to step 2).

5) Terminate multi-vehicles-cross process

If n<2, only one vehicle was approaching the intersection at that moment, and the CAS stopped working immediately.

5 Primary simulation

To verify the effectiveness of the proposed model, a simulation experiment was performed and the results were analyzed.

5.1 Parameters setting

Vehicle 1’s initial velocity v₁=60 km/h, initial acceleration a₁=0 m/s², and initial distance L₁₂=200 m from conflict Point 1 and L₁₃=195 m from conflict Point 3 are shown in Figure 1. Vehicle 2’s initial parameters were v₂=50 km/h, a₂=0 m/s², L₂₁=145 m and L₂₃=150 m. Likewise, these values were v₃=40 km/h, a₃=0 m/s², L₃₁=100 m, L₃₂=90 m for Vehicle 3. The time interval of the CAS was △t=0.2 s. Furthermore, α, β and γ were set (0.34, 0.33, 0.33) as neutral considerations. In this work, the CAS threshold time was T_M=3 s. The GA parameters are shown in Table 2.

Figure 3 A flow chart of how CAS works

5.2 Results and analyses

The results of three-vehicles-cross process with cooperative games are shown in Figure 4.

At t₁=0 s, the TDTC was 1.08 s, which is less than the system threshold. Thus, the CAS works immediately at t₁ (Figure 4(e)). This indicates the initializing of the cooperative games. Next, a grand coalition is formed among vehicles 1, 2, and 3. All three vehicles entered the safe zone again at t₂=2.4 s and remained there until completion. After t₃, the TDTC curve increased from 3.12 s to 3.35 s, as △T_min≤△T₁₂. Vehicles 1 and 2 were continuously driving in the safe zone; a system of only two vehicles from t₃ to end is ineffective.

Table 2 List of parameters in primary simulation

The profit curves varied from t₁ to t₂(Figure 4(a)), which represents the payoff being rationed among the three vehicles. During this cooperative-driving period, vehicle’s profit was greater than 0, meaning that each all vehicles were profitable in each cycle after adopting the cooperative driving mode. After t₂=2.4 s, three vehicles entered the safe zone, and the cooperative driving pattern was replaced by the usual driving mode. At this time, each vehicle’s characteristic function becameand the profit curves returned to 0.

The velocity curves are shown in Figure 4(c). The speed of Vehicle 3 continuously increased from t₁ to t₂, and its speed was 55.70 km/h at t₂=2.4 s. To avoid a collision, the CAS decided to reduce Vehicle 1’s speed. However, the speed was still sufficient to maintain the rapidity indicator. We can see that Vehicle 1’s speed was 56.23 km/h at t₂. In contrast, the Vehicle 2’s speed varied slightly, and was 56.17 km/h at t₂.

The distance curves (Figure 4(d)) continuously fell during entire whole multi-vehicle-cross process for all three vehicles. Vehicle 3 was the first vehicle to leave the intersection at t₃=6.6 s, and its distance curve began to rise. After t₃, the CAS switched to the two-vehicle-cross process; usual driving mode was adopted by Vehicle 3 from then on. The simulation was complete when Vehicle 2 left the intersection at t=9.8 s.

As shown in Figure 4(b), the accelerations of the three vehicles did not immediately return to zero from t₂=2.4 s to t=3.0 s, as the randomness of driver operations was considered in this simulation. Under a normal driving psychology, drivers are willing to gradually move the vehicle to a uniform state. Thus, the amplitude of acceleration variation is limited by:

              (19)

According to the results of the 100 random simulations (Figure 5), the acceleration curves converged to zero at approximately 1.1 s.

Some indicators were adopted to evaluate the CAS (Table 3).

There was occasionally a negative profit for Vehicle 3 at t=0.4 s (Figure 4(a)). However, the average profit during the entire process was positive: andThus, every vehicle received an acceptable profit. Compared with the negative average profit in Ref. [11], this reflects the superior performance of the cooperative game model.

Vehicle 3 was the first to leave the intersection (Figure 4(d)) and had the highest priority in this simulation. Some profit from Vehicles 1 and 2 became a transferable payoff, which was contributed to Vehicle 3. Vehicle 1 continuously decreased its speed from t₁ to t₂ (Figure 4(d)), thereby transferring its rapidity profit to the transferable payoff. The number of bad accelerations for Vehicle 2 was 9 (Table 3), and its comfort profit was moved to the transferable payoff.

The system took 2.4 s to guide three vehicles to the safe zone. Thus, this model was shown to be an efficient system. As previously mentioned, the simulation results also relate to the driver behavior characteristics α, β and γ. In general, the larger the parameter α, the shorter the system response t₂–t₁.

It must be emphasized that steps 4) and 5) are critical, although they do not work in this simulation. It is difficult to ensure that △T₁₂>T_M when the cooperative driving pattern of two vehicles begins, as the driver behavior can be At the termination point of the cooperative driving pattern of three vehicles, the distance between vehicles was d₁₂(t₂)=49.06 m, d₁₃(t₂)= 96.81 m and d₂₃(t₂)=47.74 m, with velocities of v₁(t₂)=54.23 km/h, v₂(t₂)=56.06 km/h and v₃(t₂)=58.81 km/h (Table 3). Finally, at the termination point in the simulation, the distance between vehicles 1 and 2 was d₁₂(t_end)=48.20 m, with velocities of v₁(t_end)=54.23 km/h and v₂(t_end)=56.06 km/h. The CAS performed very well.

Figure 4 Primary Simulation results of proposed model with cooperative games:

Figure 5 100 random simulations on acceleration curves uncertain in usual driving mode.

Table 3 Evaluation indicators of proposed model with cooperative games

6 Extended simulation

As an extended simulation, a scenario involving two or more vehicles in some lanes should be considered, as the feasibility of the n vehicles game has been described by the Shapley theorem and the rationality of the characteristic function has been mathematically proven.

To ensure each curve in the simulation can be displayed clearly, we analyzed a five-vehicles-cross process (Figure 6).

Figure 6 Illustration of five-vehicle-cross process at non-signalized intersection

Here, vehicle 1 is the lead vehicle and vehicle 4 follows in the north-south lane. In the east-west lane, vehicle 2 is the lead vehicle and vehicle 5 follows. To prevent a rear-end accident, the TDTC parameter was modified in Eq. (1) between vehicles 1 and 4 (and between vehicles 2 and 5):

 (20)

where L_k is the position of vehicles’ kth conflict points in the intersection; v_h, v_f are the velocities of the lead and following vehicles; and L_h, L_f are the distances from the lead and following vehicles to the conflict point; T_M is a time threshold set to judge the driving safety states. If Eq. (1) holds, there is a potential collision risk between the two vehicles.

To verify the efficacy of this model, a simulation experiment was performed and the simulation results were analyzed.

6.1 Parameters setting

In Figure 6, vehicles 1 and 4 travelled from south to north. Their distances to conflict points 1 and 3 were L_1–1=200 m, L_1–3=195 m, L_4–1=220 m and L_4–3=215 m, respectively. Vehicle 2 and 5 come from east to west, their distances to the conflict point 1 and 2 are L_2–1=145 m, L_2–2=150 m, L_5–1= 225 m, and L_5–2=230 m. Vehicle 3 travelled from north to south. Its distances to the conflict points 2 and 3 were L_3–2=90 m and L_3–3=100 m. The simulation parameters are listed in Table 4.

6.2 Results and analyses

The simulation curves are shown in Figures 7–10.

The profit curves of vehicles 1–5 are shown in Figure 7(a). The total profit of the grand coalition is mathematically described as N={1, 2, 3, 4, 5} and marked with the black dotted line. The profit values were set as 0 during usual driving mode, which means no vehicles were involved in the game. The total profit curve was always positive and always higher than that of any individual vehicle during the cooperative driving pattern stage. Thus, it is feasible to produce more profit for the coalition using the cooperative game.

Table 4 List of parameters in extended simulation

The acceleration curves of vehicles 1–5 are shown in Figure 7(b). The final cycle of the five-vehicle cooperative game began at t₁=2.4 s, and each vehicle entered the safe zone at t=2.6 s. During this game stage, vehicle 3 was allowed to travel through this area as fast as possible, as it was determined to be the first arriving vehicle (FAV) in the intersection by the system. As shown in Figure 7(b), vehicle 3’s acceleration curve (red) maintained a non-negative state during this period. To match the priority of vehicle 3, all other vehicles in the grand coalition changed their acceleration accordingly. Vehicles 1, 2, and 3 left the intersection at t=13.2 s (Figure 7(d)), and the game for vehicle 4 ran from t₂=13.4 s to t=15.4 s (Figure 7(e)). As a new FAV, vehicle 4 has priority to through the area with sustained positive acceleration.

The velocity curves of vehicles 1–5 are shown in Figure 7(c). From t=0 s to t₁=2.4 s, vehicle 3’s speed continuously increased, and vehicle 2’s speed was approximately 53 km/h with a slight fluctuation. Meanwhile, the velocity curves of vehicles 1 and 4 were in near continuous decline. In contrast, vehicle 5’s speed remained steady, as its state (composed of velocity and distance) was considered safe by the system. According to the acceleration analysis (Figure 7(b)), vehicle 4’s velocity curve showed an increasing trend from t₂=13.4 s to t=15.4 s.

The distance curves of vehicles 1–5 are shown in Figure 7(d). Each curve fell continuously until the vehicle arrived at the conflict point, at which point its curve began to rise. Vehicle 3 arrived at the intersection at t=7.0 s, and vehicles 2 (t=10.2 s), 1 (t=13.2 s) and 4 (t=16.0 s) followed. As the last vehicle, the distance of vehicle 5 to the junction was 32.59 m when simulation terminated.

The TDTC curve is shown in Figure 7(e). We can see that CAS worked in two instances. The CAS responded the first time because the necessary conditions were met at t=0 s. Five vehicles entered the safe zone under CAS guidance at t₁=2.4 s. The TDTC curve increased slightly when vehicle 2 left this area (t=10.4 s). This is a normal phenomenon, given that △T_min(5)≤△T_min(4)≤△T_min(3) has been previously proven. However, the TDTC curve suddenly dropped at t₂=13.4 s. At this time, vehicles 4 and 5 become the lead vehicles in their own lanes, which are no longer subject to the previous lead vehicle’s constraints. Thus, this is reasonable whether the trend of TDTC curve is rising, falling, or maintaining its original status. This showed a downward trend from t=13.2 s to t₂=13.4 s in this simulation.

As previously mentioned, the lead vehicle’s constraints on following vehicles mean that a following vehicle cannot overtake its lead vehicle. The driving processes of these vehicle pairs (1 and 4, 2 and 5), are shown in Figure 8.

During the first game period from t=0 s to t=2.4 s, the variation trends of velocity curves between the lead and following vehicles were similar (vehicles 1 and 4 in Figure 8(a), vehicles 2 and 5 in Figure 8(c)). The same is true for the distance curves (vehicles 1 and 4 in Figure 8(b), vehicles 2 and 5 in Figure 8(d)).

However, as two lead vehicles, vehicles 4 and 5 continued the second game period from t=13.4 s to t=15.4 s (in Figure 9).

As shown in Figure 9(d), the value of the TDTC was 2.08 s, which is less than the system threshold of t=13.4 s. This indicates that the CAS performed well. Vehicles 4 and 5 entered the safe zone after 1.8 s. Judged to be a new FAV in the second game period, vehicle 4 passed through the intersection quickly with great mean acceleration (Figure 9(a)) and mean speed values (Figure 9(b)).

Figure 7 Extended Simulation curves of proposed model with cooperative games:

In contrast, vehicle 5 continued to decelerate to match the priority of vehicle 4 until it left the area.

To visually represent the entire five-vehicles- cross process, we utilized the 3D simulation software developed by our research team. The entire process is recorded in the attached video file. The screenshots of eight key moments is shown in Figure 10 and the relevant descriptions are listed in Table 5.

Some indicators are adopted to evaluate the CAS in Table 6. As seen in Figure 7(e), CAS does not work when the coalition is either four (N={1, 2,4, 5}) or three (N={1, 4, 5}). Thus, only the situation of N={1, 2, 3, 4, 5} and N={4, 5} are analyzed in Table 6.

Figure 8 Simulation curves between lead vehicle and following vehicle in the same lane:

Compared with the previous situation of three lead vehicles only, these simulation results are more complex. The five conclusions of this simulation are as follows:

1) The total profit curve has always been positive and was always higher than any individual vehicle’s profit curve when the CAS was operative (Figure 7(a)). It is possible to produce more profit for the coalition with cooperative game.

2) Expression (20) is crucial when there are multiple vehicles in the same lane, as it can effectively prevent rear-end accidents during the multi-vehicles-cross process.

3) If there is one vehicle (lead vehicle) in the lane, the corresponding conflict point will disappear when it leaves the area. However, when a following vehicle becomes the new lead, one should be careful when more vehicles enter the same lane. For example, vehicle 5 joins the new coalition (N={1, 4, 5}) with vehicles 1 and 4 after vehicle 2 passes through the area (from t=10.2 s to t=13.2 s in Figure 7(e)).

4) The passing order of the five vehicles in this simulation is as follows: Vehicle 3 → Vehicle 2 → Vehicle 1 → Vehicle 4 → Vehicle 3 (Figure 7(d)). It appears that all the five vehicles passed through the intersection safely in 16 s. Therefore, the efficiency of proposed algorithm is verified.

5) The CAS worked successfully for two periods (Figure 7(e)) when the necessary conditions were met; timeliness and effectiveness were verified.

Figure 9 Simulation curves of vehicle 4 and 5’s game:

7 Conclusions

We have proposed an algorithm to solve the problem of collisions at non-signalized intersections. In this paper, a driving model was proposed based on cooperative game theory. First, the characteristic functions of the multi-vehicles-cross process were established using each vehicle’s profit function; namely, safety, rapidity and comfort indicators. Second, the Shapley value was employed as an effective method to rationally distribute profit for each player. However, the characteristic functions created must satisfy some basic properties of Shapley theorem. Thus, the characteristic functions were verified for all relevant conditions, such as group rationality, individual rationality and uniqueness. Furthermore, considering the influence on the profit functions with different drivers’characteristics, definitive parameters such as α, β, and γ were used in the model. Then, to simplify the calculation, we have introduced Zero-mean Normalization method. In addition, the GA method was applied to determine an optimal solution in a constrained MOP. Finally, this model was simulated with a series of initial conditions; simulation results confirmed the efficacy of this system.

By improving upon existing research in the domain of cooperative driving, this paper contains several innovative aspects:

1) An application of cooperative game theory in the field of vehicle active safety.

Figure 10 Key screenshots of Extended Simulation by 3D simulation software

When several vehicles approached the same non-signalized intersection from different directions, many sequences existed among them. Furthermore, every sequence can represent a possible benefit, such as time, safety, right of way, etc. In the past, every driver has been treated as a unique, independent individual; however, their decisions have not always been appropriate. The majority of conflicts could not be avoided owing to a lack of agreement among them. Some criteria can be fundamentally established using cooperative game theory, making the exchange of information among vehicles with vehicle-vehicle (V2V) communication systems a reality.

Table 5 Descriptions of eight key moments during five-vehicles-cross process

Table 6 Results of five vehicles’ cooperative game

2) A new driving model for energy conservation and environmental protection. As is well known, frequent switching between brake and throttle pedals wastes a significant amount of energy and produces more vehicle exhaust. However, it is difficult to ensure that a driver can accurately control a vehicle using only their vision or experience. If vehicles are equipped with this new driving model, strategy sets can be generated by the system according to the vehicle’s current environment. Safety, rapidity, and comfort will be aligned (to some extent) in this model. Furthermore, the acceleration strategy is optimized for drivers to replace some blind operations, wherever possible.

3) Selection of the warning timing. Early warnings are easily ignored by drivers. Therefore, research to determine the optimal warning time is also important.

References

[1] TSUGAWA S. Inter-vehicle communications and their applications to intelligent vehicles: An overview [C]// Proceedings of Intelligent Vehicle Symposium. 2002, 2: 564–569.

[2] ARORA S, RAINA A K, MITTAL A K. Collision avoidance among AGVs at junctions [C]// Proceedings of the IEEE Intelligent Vehicles Symposium. Dearborn (MI), USA, 2000: 585–589.

[3] LACHNER R. Collision avoidance as a differential game: Real-time approximation of optimal strategies using higher derivatives of the value function [C]// Proceedings of IEEE International Conference on Systems. 1997, 3: 2308–2313.

[4] GIRARD R, de SOUSA J B, MISENER J A, HEDRICK J K. A control architecture for integrated cooperative cruise control and collision warning systems [C]// Proceedings of the 40th IEEE Conference on Decision and Control. Orlando, Florida, USA, 2001: 1491–1496.

[5] KATO S, TSUGAWA S, TOKUDA K, MATSUI T, FUJII H. Vehicle control algorithms for cooperative driving with automated vehicles and intervehicle communications [J]. IEEE Transaction on Intelligent Transportation Systems, 2002, 3(3): 155–161.

[6] GEHRING O, FRITZ H. Practical results of a longitudinal control concept for truck platooning with vehicle to vehicle communications [C]// Proceedings of IEEE Conference on Intelligent Transportation System. 1997: 117–122.

[7] CHEN X B, YAO D Y, ZHANG Y, SU Y, ZHANG Y. Design and implementation of cooperative vehicle and infrastructure system based on IEEE 802.11n [J]. Transportation Research Record: Journal of the Transportation Research Board, 2011, 2243(1): 158–166.

[8] SAKAGUCHI T, UNO A, KATO S, TSUGAWA S. Cooperative driving of automated vehicles with inter-vehicle communications [C]// Proceedings of the IEEE Intelligent Vehicles Symposium. Dearborn (MI), USA, 2000: 516–521.

[9] LI L, WANG F Y. Cooperative driving at blind crossings using intervehicle communication [J]. IEEE Transactions on Vehicular Technology, 2006, 55(6): 1712–1724.

[10] LIU X M, ZHENG S H. Study of vehicle-cross action model for unsignalized intersection based on dynamic game [C]// Proceedings of International Conference on Mechanic Automation and Control Engineering. 2010: 1297–1302. (in Chinese)

[11] YANG Z, HUANG H, YAO D Y, ZHANG Y. Cooperative driving model for non-signalized intersections based on reduplicate dynamic game [C]//Proceedings of IEEE Conference on Intelligent Transportation System. Rio de Janeiro, Brazil, 2016: 1366–1371.

[12] SAYED T, ZEIN S. Traffic conflict standards for intersections [J]. Transportation Planning and Technology, 1999, 22(4): 309–323.

[13] LAURESHYN A, SVENSSON A, HYDEN C. Evaluation of traffic safety based on micro-level behavioural data: Theoretical framework and first implementation [J]. Accident Analysis and Prevention, 2010, 42(6): 1637–1646.

[14] BARRON E N. Game theory: An introduction, second edition [M]. Hoboken, New Jersey: John Wiley & Sons, Inc., 2013.

[15] WANG Zhong-yu, JIANG Wen-song, WANG Yan-qing. Application of camera calibrating model to space manipulator with multi-objective genetic algorithm [J]. Journal of Central South University, 2016, 23(8): 1937–1943.

[16] DEB K, PRATAP A, AGARWAL S, MEYARIVAN T. A fast and elitist multiobjective genetic algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182–197.

(Edited by FANG Jing-hua)

中文导读

基于合作博弈的无信号交叉口车辆协同驾驶模型研究

摘要：交通安全问题一直是世界范围内的重大议题，而无信号交叉口因其高事故率备受人们的关注。近年来，交叉口车辆的协同驾驶行为研究成为一大热点。分析了多辆车驶向某无信号交叉口时的潜在冲突危险，提出了一种基于合作博弈的车辆协同驾驶模型。首先，以车辆的安全性、快速性、舒适性为指标构建交叉口车辆行驶过程的特征函数；其次，采用Shapley定理对这一插车过程进行建模，并在数学上严格证明了特征函数满足Shapley条件下的集体理性、个体理性、唯一性；然后，在模型中加入区分驾驶员行为特性的参数；接着，采用Zero-mean的标准化方式简化数值运算，并通过遗传算法求解该模型的最优策略集；最后，通过一系列的仿真实验，验证了该模型的有效性。

关键词：协同驾驶；多车插车过程；合作博弈；Shapley利值；遗传算法

Foundation item: Project(61673233) supported by the National Natural Science Foundation of China; Project(D171100006417003) supported by Beijing Municipal Science and Technology Program, China

Received date: 2017-06-02; Accepted date: 2018-02-26

Corresponding author: YAO Dan-ya, PhD, Professor; Tel: +86–13901167625; E-mail: yaody@tsinghua.edu.cn