Decentralized Multi-Vehicle Motion Planning for Platoon Forming in Mixed Traffic Using Monte Carlo Tree Search

Connected and Automated Vehicles (CAV) platoon is regarded as a promising means of improving traffic efficiency and safety. This study focuses on addressing a Multi-Vehicle Motion Planning (MVMP) problem for CAVs aiming to form a platoon in the mixed traffic flow with both CAVs and Human-Driven Vehicles (HDV), which utilizes the cooperative capabilities of the multi-vehicle queue. Generally, the MVMP problem would be formulated into a centralized form, which is numerically intractable due to the computational complexity. In addition, the uncertainty of human drivers' behavior in mixed traffic presents a challenge in motion planning for multiple CAVs simultaneously. To overcome these issues, we propose a decentralized MVMP framework based on the Monte Carlo Tree Search (MCTS) algorithm, which splits the MVMP problem into a series of lane change tasks. The MCTS algorithm is applied to determine an optimal lane change decision, facilitating the advancement of platoon formation based on the current vehicle state. Subsequently, we establish both the longitudinal position adjustment model and the lane change motion planning model to efficiently execute the lane change maneuver, as well as taking into account some evaluation factors such as safety, rapidity, and comfort. Finally, we develop a simulation platform using SUMO and MATLAB to simulate a three-lane freeway with mixed traffic. The simulation results demonstrate that the proposed approach can efficiently organize individual CAVs in the three lanes into a platoon under 20 scenarios including multiple traffic demands and CAV ratios. Furthermore, compared to the existing methods, the proposed approach achieves a better performance in terms of platooning proportion, time consumption, and time delay.