# Trajectory Planning with Time-Variant Safety Margin for Autonomous Vehicle Lane Change +
## 2 Methodology
### Gap Evaluation
#### 2.1.1 Traffic Prediction with Gray Prediction Model  
Assuming the total number of vehicles to consider is \(N\), for the \(i\)th vehicle (\(1\leqslant i\leqslant N\)), we denote its speed series measured at discrete time instances \(\{1,2,\ldots,m\}\) as \(\{v_{i}(1),v_{i}(2),\ldots,v_{i}(m)\}\), where \(m\) is the present time instance. To balance the algorithm complexity and efficiency, here a Gray Prediction Model is employed to approach the traffic prediction [20]. The sequence of future vehicle speeds \(\{v_{i}(m+1),v_{i}(m+2),\ldots,v_{i}(n)\}\) for discrete time instances \(\{m+1,\ldots,n\}\) can be obtained by the following calculations. We denote \(\{X_{i}(1),X_{i}(2),\ldots,X_{i}(m)\}\) as the accumulation of \(v_{i}\):  
\[X_{i}(k)=\sum_{j=1}^{k}v_{i}(j),\quad 1\leqslant k\leqslant m \tag{1}\]  
Here \(X_{i}\) is a monotonically increasing sequence, which is suitable for the exponential fitting. Assuming \(X_{i}\) in general satisfies the following differential equation:  
\[\Delta X_{i}(k)+aX_{i}(k)=u \tag{2}\]  
where \(a\) and \(u\) are constant scalar parameters, then solving for \(X_{i}\) by an exponential sequence gives  
\[X_{i}(k+1)=[X_{i}(1)-\frac{u}{a}]e^{-ak}+\frac{u}{a} \tag{3}\]  
Since \(\Delta X_{i}(k)=X_{i}(k)-X_{i}(k-1)=v_{i}(k)\), and \(X_{i}(k)\) can be replaced by the approximation \(\frac{1}{2}[X_{i}(k-1)+X_{i}(k)]\), the Equation (2) can be rewritten in matrix form as  
\[v_{i}(k)=\left[-\frac{1}{2}(X_{i}(k-1)+X_{i}(k))\quad 1\right]\begin{bmatrix}a \\ u\end{bmatrix} \tag{4}\]  
Let  
\[Y_{i}=\begin{bmatrix}v_{i}(2)&\ldots&v_{i}(m)\end{bmatrix}^{T} \tag{5}\]  
\[B_{i}=-\frac{1}{2}\begin{bmatrix}X_{i}(1)+X_{i}(2)&-2\\ X_{i}(2)+X_{i}(3)&-2\\ \vdots&\vdots\\ X_{i}(m-1)+X_{i}(m)&-2\end{bmatrix} \tag{6}\]  
By the least square method, the estimation of \(a\) and \(u\) is solved as  
\[(a_{i},u_{i})^{T}=\left(B_{i}^{T}B_{i}\right)^{-1}B_{i}^{T}Y_{i} \tag{7}\]  
The speed prediction for discrete time instances \(\{m+1,\ldots,n\}\) is calculated as  
\[v_{i}(k)=X_{i}(k)-X_{i}(k-1),\quad m+1\leqslant k\leqslant n \tag{8}\]  
Figure 2: An illustration of available gaps for lane change. The circled vehicle is host vehicle \(V_{H}\), the bright area around it is available gaps. The gray area is the blind zone which is unavailable gaps.  
where the prediction of \(X_{i}(k)\) is obtained by the fitting result according to the exponential rule  
\[X_{i}(k)=\left(X_{i}(1)-\frac{u_{i}}{a_{i}}\right)e^{-a_{i}(k-1)}+\frac{u_{i}}{a _{i}} \tag{9}\]  
Due to traffic randomness, the accuracy of prediction by Gray Prediction Model can deteriorate quickly as prediction horizon extends. Since typical lane changes have a duration of 3-6 s, during the prediction of each traffic vehicle status, we set the prediction horizon \(t_{p}=4\) s. Based on general road standards and vehicular kinetic characteristics, the velocity and acceleration of host vehicle \(V_{H}\) is subject to the parameter limitations listed in Table 1. These parameters is set to allow enough maneuverability for regular driving, while retaining an acceptable level of ride comfort.