Algorithm

Discretization

Process (computing)

Computational complexity theory

Ecology

Biology

Operating system

Computer science

Mathematical optimization

Decomposition

Computer network

Mathematics

Nash equilibrium

Mathematical analysis

Mathematical economics

Game theory

Queue

Queueing theory

Engineering Applications of Artificial Intelligence

This study presents a cellular lane-changing model where the traffic lanes are discretized into cells and formulates the lane-changing process as a multi-player non-zero-sum non-cooperative game in a connected environment where the real-time surrounding traffic data is shared. In a congested traffic scenario where a large quantity of mandatory lane-changing maneuvers are required simultaneously, the size of the game is extended dynamically (i.e., 2–5 players in this case, and it can be extended more if necessary) based on the traffic situation. Discretionary lane-changing maneuvers are also considered in the decision-making process to maximize the use of the capacity of each traffic lane, i.e., distributing the vehicles to each traffic lane as uniform as possible. Moreover, the competing vehicle on the target lane has more flexible actions (i.e., changing to other lanes) except for accelerating and decelerating actions. Thus, its temporary benefit is sometimes sacrificed by taking these actions to pursue the global benefit so that other vehicles could complete mandatory lane-changing maneuvers. It is a known fact that the space complexity expands exponentially as the game size increases, so a novel decomposition algorithm based on game theory is proposed to reduce the complexity and improve computational efficiency. Finally, a rule-based approach, a classic Nash equilibrium approach and the proposed decomposition algorithm are compared by the critical indicators such as the number of lane-changing vehicles, the maximum incoming queues during the process, the mean of computational time per iteration, etc. The performance shows no significant difference in the efficacy of lane-changing maneuvers among these approaches under the uncongested traffic condition. At the same time, the decomposition algorithm is more efficient in computing time than the classic Nash equilibrium approach. As the traffic gets congested, the game theory-based approaches prove more effective in lane-changing behaviours than the rule-based approach. Meanwhile, the decomposition algorithm outperforms the classic Nash equilibrium approach more significantly in terms of computational time.

Lane-changing decision modelling in congested traffic with a game theory-based decomposition algorithm