# Optimal Vehicle Lane Change Trajectory Planning in Multi-Vehicle Traffic Environments
## 2 Methods
### Collision Avoidance Algorithm  
The traditional method for studying safe lane change is the minimum safe distance algorithm, which is most widely used in the forward warning of automatic emergency braking system. Classic safety distance models include the Berkeley model, the Honda safe distance model and the Mazda safe distance model; The forward warning system is too conservative, which leads to frequent automatic braking, and the driver and passenger will feel uncomfortable. There are few application scenarios for the safety distance model algorithm: it is applied in a one-way two lane environment, and the surrounding vehicles have no intention to change lanes, in the multi-vehicle traffic environment, the minimum safe distance method is ineffective because it can not be applied to the scenario where  
Figure 4: Three-dimensional plot of lane change time versus vehicle speed and coefficient of adhesion. other vehicles have to change lanes. Therefore, heuristic collision avoidance algorithm is used to deal with the problem of lane changing in multi-vehicle traffic environment. The algorithm has a safety rule, all dangerous trajectory clusters are eliminated based on safety rules, and the remaining lane-changing trajectory clusters meet the requirements of safe lane-changing which are called safe trajectory clusters. Then the collision avoidance algorithm includes two rules: first, if the traffic vehicle is in a straight-line driving state, the subject vehicle will not collide with the traffic vehicle when changing lanes; Second, if the traffic vehicle also needs to change lanes, the subject vehicle will not collide with the traffic vehicle. Whether two vehicles collide is equivalent to whether two rectangles intersect at the same time. As shown in Figure 5: the intersection of two rectangles includes the following four situations. Assuming that there are vehicles \(i\) and \(j\) in the same scene, the first situation is that a vertex of the two rectangles is inside each other, and the second situation is that all the vertices of the two rectangles do not fall inside the rectangle, but penetrate each other. Assuming that rectangle \(i\) keeps going straight, and rectangle \(j\) collides with rectangle \(i\) when changing lanes, it is certain that rectangle \(i\) has a vertex inside rectangle \(j\). If the collision continues, the two rectangles will pass through. none of the vertices are inside the rectangle \(j\), according to the judgment, it can be seen that the second situation must occur after the first situation. In order to make the point p outside the rectangle ABCD, an algebraic inequality based on the area of the graph can be used to establish a constraint condition. If the following area conditions are satisfied, it can be proved that the two vehicles will not collide. \[S_{\Delta\text{PAB}}+S_{\Delta\text{PBC}}+S_{\Delta\text{PCD}}+S_{\Delta\text{ PDA}}>S_{\Delta\text{ABCD}} \tag{16}\]  
In Formula (16), \(S_{\Delta}\) is the area of the triangle, and \(S_{\alpha}\) is the area of the rectangle. The geometric description is shown in Figure 6.  
The lane-changing trajectory of the vehicle is determined by the end time of the lane-changing [27], and the position of the vertex of the rectangle at any time in Formula (17). \[ \begin{bmatrix}x_{k1}(t)&y_{k1}(t)\\ x_{k2}(t)&y_{k2}(t)\\ x_{k3}(t)&y_{k3}(t)\\ x_{k4}(t)&y_{k4}(t)\end{bmatrix} =\frac{1}{2} \begin{bmatrix}-l_{H}&-w_{H}&0&0\\ l_{H}&-w_{H}&0&0\\ l_{H}&w_{H}&0&0\\ -l_{H}&w_{H}&0&0\end{bmatrix}\begin{bmatrix}\cos\varphi_{k}(t)&\cos\varphi_{k }(t)\\ -\sin\varphi_{k}(t)&\sin\varphi_{k}(t)\\ 0&0\\ 0&0\end{bmatrix} + \begin{bmatrix}x_{k}(t)&y_{k}(t)\\ x_{k}(t)&y_{k}(t)\\ x_{k}(t)&y_{k}(t)\end{bmatrix}  \tag{17}\]  
Figure 5: (**a**) A rectangle exists where a vertex collides with another rectangle; (**b**) A rectangle exists where a vertex collides with another rectangle. (**c**) Two rectangles with vertices colliding with each other; (**d**) Through collision.