## 2 Optimal Lane Change Path Planning Based on the NSGA-II and TOPSIS Algorithms
### Collision Avoidance Algorithm  
In order to avoid traffic accidents, the vehicle should ensure that there is enough safe distance with the surrounding vehicles when changing lanes. [PERSON] et al. realized obstacle avoidance by calculating the safe distance to meet the lane change requirements [34]. [PERSON] et al. established a rectangular vehicle model and used a heuristic lane changing collision algorithm to screen out the safe lane changing trajectory [32]. [PERSON] et al. used a dynamic circle with the diameter of the vehicle width to surround the whole vehicle and detect a collision to solve the safety problem of lane changing [35]. In order to express succinctly and calculate simply, the rectangular model is used for geometric modeling of vehicles in this study, as shown in Figure 3. In the figure, \(l\) and \(w\) represent vehicle length and width, respectively.  
Assume that the size of the ego vehicle is the same as that of other traffic vehicles, and the surrounding traffic vehicles keep constant velocity in a straight line during the lane change process. According to the lane change trajectory function of Equation (1), the coordinates of the centroid of the ego vehicle at time \(t\) can be calculated, and the coordinates of the vertices \(A\), \(B\), \(C\), and \(D\) at time \(t\) can be obtained by combining the heading angle \(\varphi(t)\). The calculation method is as follows:  
\[\begin{bmatrix}x_{A}(t)&x_{B}(t)&x_{C}(t)&x_{D}(t)\\ y_{A}(t)&y_{B}(t)&y_{C}(t)&y_{D}(t)\end{bmatrix}=\begin{bmatrix}\cos\varphi(t)& -\sin\varphi(t)\\ \sin\varphi(t)&\cos\varphi(t)\end{bmatrix}\times\tfrac{1}{2}\begin{bmatrix}l& l&-l&-l\\ w&-w&-w&w\end{bmatrix} \tag{5}\] \[+\begin{bmatrix}x(t)&x(t)&x(t)&x(t)\\ y(t)&y(t)&y(t)\end{bmatrix}\]  
\[\varphi(t)=\arctan\frac{dy}{dx}(t) \tag{6}\]  
Similarly, vertex coordinates of other traffic vehicles at time \(t\) can be obtained as follows:  
\[\begin{bmatrix}x_{iA}(t)&x_{iB}(t)&x_{iC}(t)&x_{iD}(t)\\ y_{iA}(t)&y_{iB}(t)&y_{iC}(t)&y_{iD}(t)\end{bmatrix}=\frac{1}{2}\begin{bmatrix}l& l&-l&-l\\ w&-w&-w&w\end{bmatrix}+\begin{bmatrix}x_{i}(t)&x_{i}(t)&x_{i}(t)&x_{i}(t)\\ y_{i}(t)&y_{i}(t)&y_{i}(t)\end{bmatrix} \tag{7}\]  
where \(i=V_{ft},V_{fc},V_{rc}\).  
This study further simplifies collision detection during lane changing by creating an axially aligned bounding box. Firstly, the ego vehicle and the surrounding traffic vehicles are projected in the coordinate axis direction. When the two coordinate axes overlap, the two vehicles are judged to have a collision, as shown in the red area in Figure 4. In other words, if the coordinates of the ego vehicle and surrounding vehicles meet Equation (8)  
Figure 3: Rectangular vehicle model.  
in the lane changing process, no collision will occur, and lane changing collision will be detected every 0.5 s.  
\[\left\{\begin{array}{l}x_{\min}>x_{i,\max}\\ y_{\min}>y_{i,\max}\\ x_{i,\min}>x_{\max}\\ y_{i,\max}>y_{\max}\end{array}\right. \tag{8}\]  
When the lane changing trajectory constraint conditions of Section 2.1.1 in which the velocity of the ego vehicle is 50 km/h <= \(v_{e}<=\) 60 km/h are added, the minimum lane changing time is 1.171 s, collision avoidance meets the algorithm of Section 2.2, and the feasible lane changing trajectory cluster is finally obtained, as shown in Figure 5. The ego vehicle is relatively safe and comfortable to drive with these trajectories.  
Figure 4: Schematic diagram of collision during lane changing.  
Figure 5: Feasible lane changing trajectory cluster.