# Optimal Vehicle Lane Change Trajectory Planning in Multi-Vehicle Traffic Environments
## 1 Introduction  
With rapid economic growth, artificial intelligence will be more widely applied to automobile development. At present, Automatic Driving Systems (ADSs) are being developed to prevent accidents and reduce carbon emissions [1]. If automatic driving can be achieved, traffic congestion will be alleviated. In addition, if accidents and fuel consumption are reduced [2], the annual social benefits of autonomous driving systems are expected to reach nearly $800 billion by 2050 [3]. However, automatic driving systems are not yet mature for use in urban environments, and have already resulted in many traffic accidents, making many people vary of using them [4]. As early as 2005, in the DARPA competition, five teams completed the cross-country project. The biggest difficulty of automatic driving technology is not cross-country, but rather, urban environments [5]. On structured roads, the traffic environments are very complex, and vehicles need to interact with multiple vehicles during the lane-changing process [6]. Therefore, the development of a safe and feasible active lane-changing system remains a challenge. A complete automatic lane change system includes environmental perception, behavior decision, trajectory planning and trajectory tracking control [7]. Trajectory planning comprises the calculation of a lane change trajectory after receiving a lane change signal [8]. Path planning only plans a reference trajectory without considering traffic conditions. Trajectory planning should take into account the complex traffic environment. In this respect, there are five types of methods: the Graph Search Algorithm, the Sampling-based Algorithm, the Interpolating Curve Algorithm and the Optimization Algorithm [9]. Sampling-based algorithms may be divided into two kinds: Probabilistic Road Maps (PRMs) and Rapidly Explore Random Tree (RRTs) [10]. The basic principle of the sampling-based algorithm is to collect the path points between the initial point and the end point, thereby connecting the points to form a trajectory. In this way, a safe and smooth path is proposed as a reference trajectory [11]. [PERSON] et al. from Nanchang University of Aeronautics and Astronautics [12] improved the probabilistic road map algorithm and applied the genetic algorithm to optimal path planning. The biggest advantage of their approach was the reduced algorithm operation time. [PERSON] et al. from Boston University [13] planned a safe overtaking trajectory using a second-order RRT algorithm. Although it was computationally efficient, the planned path was not smooth enough [14], which presented a major challenge for trajectory tracking control. The graph search algorithm comprises the A* and Dijkstra algorithms. The optimized Dijkstra algorithm was used by researchers at the Korea University of Science and Technology to plan the shortest lane change trajectory [15]. The A* algorithm was optimized by [PERSON] (Sun Yat-sen University) et al. [16], allowing it to solve the collision avoidance problem and plan the shortest trajectory that can be applied to curves. The biggest drawback of the graph search algorithm is that it cannot avoid collisions with moving obstacles, and it is ineffective in multi-vehicle traffic environments. The basic principle of the optimization algorithm, e.g., artificial potential field algorithm, model prediction algorithm, numerical optimization algorithm, is to establish an optimization index and constraint, and then to solve the optimal control quantity to calculate the optimal reference trajectory [17]. The artificial potential field algorithm is widely used in the field of robotics. The principle is that the potential field of the target position is low, that of the obstacle is high, and that of vehicles tends to be low [18]. Professor [PERSON] of Chongqing University [19] solved the collision avoidance problem of vehicles in dynamic environments based on an artificial potential field. [PERSON] et al.