Abstract
In order to solve the problems of multiple constraints, many different calculations of nonlinear equations which lead to major errors in the process of vehicle lane changing with minimum time, an adaptive mesh refinement and collocation optimization method is proposed. Firstly, the problem of vehicle lane changing with minimum time has been divided into nonlinear programming problems in different grids. The Lagrange interpolation polynomial was used to approximate the solution of the optimization problem in the grid, and the absolute and relative errors were resolved. Then, a mesh was determined for the unsmooth part according to the curvature of the trajectory, and the location and number of meshes were further determined according to the relationship between the maximum relative error and the allowable error. At the same time, the solution accuracy was improved by adding an adaptive calculation to the smooth interval which does not meet the tolerance error. Finally, the simulation example of comparison with the traditional optimization method was proposed. The results showed that the algorithm presented in the paper had a higher solution efficiency under the same calculation accuracy.
Highlights
 The method can adaptively increase the number of collocation and reduce the number of mesh.
 The method can generate fewer total collocation in the solution area reducing the number of nonlinear programming equations after discretization.
 The algorithm presented in the paper has a higher solution efficiency under the same calculation accuracy.
1. Introduction
The rapid development of automobile technology has brought great convenience to human travel and life, and has also driven the rapid growth of automobile ownership in recent years. At present, automobile has become one of the pillar industries of national economy in various countries. However, due to some improper operations of drivers in complex traffic scenes, more and more traffic accidents seriously threaten the safety of human life. The longitudinal and lateral movements of vehicles are not completely independent, but there is a nonlinear coupling relationship. In some cases, the longitudinal and lateral coupling nonlinear characteristics will be very significant, and will affect the accuracy of vehicle motion control and even tracking, and even cannot ensure the vehicle stability in serious cases. For example, when an intelligent vehicle encounters sudden dangerous situations such as sudden braking in front of a static obstacle in the same lane or sudden emergency braking in front of the preceding vehicle, it can learn from an experienced driver to make a lateral lane change with a large range of steering operations. And at the same time, a certain braking operation is introduced to better increase the distance from the dangerous obstacles. At this time, the motion state of the intelligent vehicle traveling with large longitudinal and lateral accelerations may exceed the boundary of the power domain corresponding to the steady state condition, leading the vehicle to enter a strong transient condition with significant nonlinear dynamic characteristics of longitudinal and lateral coupling. Under such a strong transient condition, the longitudinal component of the lateral force of the vehicle will aggravate the impact on the longitudinal speed of the vehicle. And the change of the longitudinal speed will also cause the change of the centrifugal force and the vertical load, causing interference to the lateral motion state of the vehicle. With the action range of longitudinal and lateral acceleration further approaching to the limit boundary value of the dynamic domain provided by road adhesion, the vehicle will obtain a critical instability condition. In order to ensure the control margin of the vehicle, the intelligent driving system usually limits the lateral acceleration in its trajectory plan. Therefore, under the critical instability condition, the vehicle is often accompanied by a large longitudinal acceleration, which causes a large change in the longitudinal speed, leading to a more significant nonlinear dynamics of the vehicle longitudinal and lateral coupling. As the current control strategy considers the longitudinal and lateral designs of intelligent vehicle motion separately and lacks comprehensive consideration of the above longitudinal and lateral coupling nonlinear dynamic characteristics, the vehicle motion control performance may decline significantly under strong transient, critical instability and other working conditions, which lead to vehicle instability too [1].
In the field of intelligent vehicle research, the content related to autonomous lane changing has always been one of the research hotspots in the industry. According to incomplete statistics, vehicle traffic accidents when vehicles change lanes occur every year in the quantity of about 15 %20 %. In addition, traffic jams caused by changing lanes account for about 25 % of the total. Lane changing is a complex vehicle behavior, which not only affects the safety, efficiency and comfort of the vehicle itself, but also greatly affects the performance of the entire traffic system as a part of the traffic flow. Therefore, it is of great significance to develop a set of intelligent vehicle automatic lane changing system to meet multiobjective optimization. From the current market situation, a very mature vehicle automatic lane change system that has reached the mass production level has not yet appeared [2].
The problem of vehicle lane change motion planning has been widely studied. A brief review is presented in the following.
Naskath et al. [3] analyzed the connectivity of highspeed mobility and lane changing based on discretionary lane changing approach for V2V environment. Muhamad et al. [4] proposed a yaw rejection control for a singletrailer truck using a steerable wheel located at the middle axle of the truck. Tolga et al. [5] analyzed autonomous electric vehicles and compared their potential environmental impacts with other public transport types, carpooling, walking, cycling, and various transportation policy applications. Cao et al. [6] designed a lane change algorithm based on a lookahead concept for the vehicle driving in front of the emergency vehicle to avoid emergency situations. Jiang et al. [7] presented a lanelevel vehicle counting system which was based on V2X communications and centimeterlevel positioning technologies. Yang et al. [8] presented a road environment representation method based on a dynamic occupancy grid for the lane changing assistance strategy. Vaishnavi et al. [9] developed a lane optimization model for the CAV system for solving the complexities of multilane merging areas. Amit et al. [10] proposed a microscopic traffic flow model which was intended to explain accurately the lane changing activity using Cellular Automata. Xiao et al. [11] proposed a nonlanedisciplinebased carfollowing model for solving the problem of vehicle lane changing. Huang et al. [12] proposed a neural networkbased method to predict the future status of the local vehicle using the information from V2X, and estimate the future energy consumption of each lane. Panagiotis et al. [13] proposed a methodology for modeling the likelihood of lane changing at intersections to quantify the favorability of the surrounding environment towards lane changing and simple LSTM modeling structures. Wang et al. [14] adopted a generalized dynamic model for automatic lanechanging to solve the limitations of macroscopic evaluation. H. Hamedi et al. [15] studied the vehicles’ lane change trajectories to present three novel prediction models for trajectorygrounded position. In order to investigate the characteristics of double fire sources, Guo et al. [16] performed four fullscale fire experiments in the Jiangpu road tunnel. Sharma et al. [17] proposed a novel hierarchical software architecture for the prediction of lane changing behavior on highways. Zhou et al. [18] proposed a hierarchical control strategy for the vehicle stability control. Wang et al. [19] proposed a twostage crash causation analysis method based on the precrash scenarios and a crash causation derivation framework that systematically categorized and analyzed contributing factors. Wei et al. [20] proposed a prediction model based on an attentionaided encoderdecoder structure and deep neural network (DNN) to solve the problems of low prediction accuracy, difficulty in longterm prediction. Zhang et al. [21] carried out a naturalistic driving study on a highway, from which a large amount of onroad data consisting of lanekeeping and lanechanging left and right maneuvers were collected. Tajalli et al. [22] presented a methodology for optimal control of connected automated vehicles in freeway segments with a lane drop. He et al. [23] proposed a novel observation adversarial reinforcement learning approach for robust lane change decision making of autonomous vehicles. Shi, et al. [24] proposed an integrated deep learningbased twodimension trajectory prediction model which could predict combined behaviors. Li et al. [25] proposed a lane change decisionmaking framework based on deep reinforcement learning to find a riskaware driving decision strategy with the minimum expected risk for autonomous driving to ensure the driving safety.
Some of the methods provided in the above documents have large solution errors, some cannot converge to the optimal solution, and some have low accuracy. In order to solve the above problems, the relative demerits were first eliminated in discrete grids based on the hpadaptive pseudospectral method as a direct method. Then, the mesh to be refined is determined according to the curvature of state and control variables. Finally, according to the relationship between relative and tolerance error, the number of sub grids and the number of collocations in the grid are determined, and then a solution method for vehicle lane changing with minimum time is constructed. A typical example is used to verify the effectiveness of the method. In the process of solving minimum time lane changing problem of vehicle handling inverse dynamics by a direct method, a large number of nodes need to be added to improve the accuracy of solution. So, it will lead to a dense Jacobian matrix for solving nonlinear programming problems, high order of interpolation polynomial, large amount of required calculations. Moreover, the increase of nodes will also lead to the poor convergence of the algorithm. Therefore, it is necessary to optimize the mesh and collocation. For the problem of minimum time lane changing of vehicle handling inverse dynamics, the number of subgrid divisions is provided by using the relative error, and the location of subgrid divisions is determined by using the density function. The adaptive mesh and refinement and collocation optimization method can approach the optimal solution by densifying the mesh and adding collocation points nearby. In areas with high smoothness, fewer collocations can be used with the strong adaptability. In the process of optimization, the mesh should not be refined for the smooth parts that do not meet the requirements of allowable error, while the collocation should be added. The method can adaptively increase the number of collocation and reduce the number of meshes, so that the total number of collocations generated in the solution area is less, reducing the number of discrete nonlinear programming equations, improving the speed of solving the optimal trajectory by the SQP method.
2. Mathematical model of vehicle lane change problem
2.1. Mathematical model of vehicle lane change problem
A nonlinear 7DOF vehicle model shown in Fig. 1 is used to describe the vehicle lane change problem.
In the state space form, it is [26]:
The state equation can be described as:
where $x\left(t\right)$ and $z\left(t\right)$ are the state and the input which are denoted respectively as $x\left(t\right)={\left[{v}_{x}\left(t\right),{v}_{y}\left(t\right),r\left(t\right),x\left(t\right),y\left(t\right)\right]}^{T}$, $z\left(t\right)=\left[\delta \right(t){]}^{T}$.
The parameters and the corresponding definitions can be found in Table 1.
Fig. 1Nonlinear 7DOF vehicle model
Table 1Parameter and definition
Parameter  Definition 
${v}_{x}$  Longitudinal speed 
${v}_{y}$  Lateral speed 
$r$  Yaw rate of vehicle 
$m$  Vehicle mass 
${I}_{z}$  Moment of inertia around z axis 
$\beta $  Sideslip angle 
${B}_{w}$  Wheelbase of vehicle 
${l}_{f}$  Distances of front axle from center of gravity 
${l}_{r}$  Distances of rear axle from tcenter of gravity 
${F}_{xij}$  Longitudinal tire force 
${F}_{yij}$  Lateral tire force 
${\delta}_{f}$  Front steering angle 
where $i=f$ or $r$, $j=l$ or $r$, and $fl$ means the front left, $fr$ means the front right, $rl$ means the rear left, $rr$ means the rear right 
2.2. Tire model
This article adopts the “Magic formula” tire model which expression is:
The parameters and the corresponding definitions in Eqs. (3)(5) can be found in Table 2.
Table 2Parameter and definition
Parameter  Definition 
$B$  Stiffness factor 
$C$  Shape factor 
$D$  Amplitude factor 
$E$  Curvature factor 
${S}_{h}$  Curve offset on the $x$axis 
${S}_{v}$  Curve offset on the $y$axis 
$X$  Input variable 
$Y\left(X\right)$  Output variable 
2.3. Optimal control object of lane change motion planning problem
The minimum time problem of lane change motion planning can be regarded as the optimal control problem in the control theory. Therefore, the minimum time performance indicator is:
where:
is the initial time, ${D}_{ki}\in {R}^{N\times (N+1)}$ is the final time.
2.4. Constrains
The initial and terminal states are described as:
In order to accomplish the lane change motion planning maneuver successfully, the constraints set on the longitudinal and lateral lines as well as the lateral acceleration are $0\le x\le {x}_{b}$, ${B}_{0}\le y\le {B}_{1}$, $\left{a}_{y}\right\le $ 3 m/s^{2}. Where ${x}_{b}$ is the longitudinal distance between vehicle and obstacle; ${B}_{0}$and${B}_{1}$ are the minimum lateral displacements required for completing lane change motion planning process and the left boundary of adjacent lane respectively [27].
When the braking maneuver is applied to decelerate the vehicle, the constraints on ${F}_{xf}$, ${F}_{xr}$ can be rewritten in the following manner:
3. Lane changing with minimum time
3.1. Problem description
For the sake of convenience, the problem of Lane Changing with Minimum Time is transformed into a Mayer problem.
The Bolza cost function is:
where $J$ is the cost function; $\psi (\cdot )$ is the Mayer type cost function; $g(\cdot )$ is the Lagrange type cost function; $f(\cdot )$ indicates the dynamic equation; $E(\cdot )$ is the boundary constraint; $C(\cdot )$ is the path constraint; $x\in {R}^{n}$ and $z\in {R}^{m}$ represent the state and control variables respectively; ${t}_{0}$ is the initial time; ${t}_{f}$ is the final time; $x(1)$ and $x\left(1\right)$ are the initial and final values of the state variable. Because the solution interval is [–1, 1], $t$ should be transformed as follows:
In the discrete process using the HP method, the solution interval $\tau \in [\mathrm{1,1}]$ will be divided into $N$ grids, i.e. ${S}_{k}=\left[{T}_{k1},{T}_{k}\right]$, $k=\mathrm{1,2},\cdots ,N$, meeting $1={T}_{0}<{T}_{1}<\cdots <{T}_{k}=1\text{,}$${\bigcup}_{k=1}^{N}{S}_{k}=[\mathrm{1,1}]$.
It is set that ${x}^{\left(k\right)}\left(\tau \right)$ and ${z}^{\left(k\right)}\left(\tau \right)$ represent the state and control variables of ${S}_{k}$ respectively. Then the above optimal control Bolza problem can be transformed as:
Because the state is continuous at the end of the grid, $x\left({T}_{k1}^{+}\right)=x\left({T}_{k}^{}\right)$ should be met at the connection point.
The pseudospectral method can be divided into four categories according to different orthogonal polynomials. But the discrete principle is basically the same among all polynominals. The paper takes the Radau pseudospectral method as an example to illustrate discrete principle of the pseudospectral method.
The Bolza optimal control problem is discretized on ${S}_{k}$ grid using LGR (LegendreGaussRadau) collocation points [28]:
where:
where ${L}_{j}^{\left(k\right)}\left(\tau \right)$$(j=\mathrm{1,2},\cdot \cdot \cdot ,{M}_{k}+1)$ is the Lagrange interpolating polynomials; $({\tau}_{1}^{\left(k\right)},{\tau}_{2}^{\left(k\right)},\cdots ,{\tau}_{{M}_{k}}^{\left(k\right)})$ are the collocation points of LGR in interval ${S}_{k}=\left[{T}_{k1},{T}_{k}\right]$. But ${\tau}_{{M}_{k}}^{\left(k\right)}+1={T}_{k}$ is not the collocation point. ${X}^{\left(k\right)}$ is the approximation of ${x}^{\left(k\right)}$.
Eq. (15) can be obtained by operating difference to $\tau $:
Approximation of the dynamic equation on the grid ${S}_{k}$ is:
where:
where ${D}_{ij}^{\left(k\right)}$ is the ${M}_{k}\times ({M}_{k}+1)$dimensional LGR differential matrix on grid ${S}_{k}$. Then Eq. (12) can be discretized as:
where $i=\mathrm{1,2},\cdots ,{M}_{k}$; $k=\mathrm{1,2},\cdots ,N$.
According to the above transformation method, the optimal control problem is transformed into a constrained nonlinear programming problem (NLP), which can be solved by the Sequential Quadratic Programming (SQP) method.
4. Adaptive optimization of mesh refinement and collocation
When the smoothness of the state and control variables is low, the solution using the global interpolation polynomial will affect its accuracy greatly. In order to improve the efficiency and accuracy of the solution, it is necessary to solve the discrete error to determine whether it is necessary or not to mesh the interpolated nodes.
4.1. Discrete error solution
It is assumed that the nonlinear programming problem shown in Eq. (10) has been already solved in interval ${S}_{k}=\left[{T}_{k1},{T}_{k}\right]$, $k\in \left[\mathrm{1,2},\cdots ,N\right]$. There are ${M}_{k}+1$ LGR collocation points i.e. $({\widehat{\tau}}_{1}^{\left(k\right)},\cdots ,{\widehat{\tau}}_{{M}_{k}}^{\left(k\right)},{\widehat{\tau}}_{{M}_{k}+1}^{\left(k\right)})$ in ${S}_{k}=\left[{T}_{k1},{T}_{k}\right]$, where ${\widehat{\tau}}_{1}^{\left(k\right)}={\tau}_{1}^{\left(k\right)}={T}_{k1}$, ${\widehat{\tau}}_{{M}_{k}+1}^{\left(k\right)}={T}_{k}$. It is set that the approximation of state variables in $({\widehat{\tau}}_{1}^{\left(k\right)},\cdots ,{\widehat{\tau}}_{{M}_{k}}^{\left(k\right)},{\widehat{\tau}}_{{M}_{k}+1}^{\left(k\right)})$ is $\left(X\right({\widehat{\tau}}_{1}^{\left(k\right)}),\cdots ,X({\widehat{\tau}}_{{M}_{k}}^{\left(k\right)}),X({\widehat{\tau}}_{{M}_{k}+1}^{\left(k\right)}\left)\right)$. $Z\left({\widehat{\tau}}_{1}^{\left(k\right)}\right)$ is the approximation of control variables in ${\tau}_{i}^{\left(k\right)}$.
Additionally, the control in ${S}_{k}$ is approximated using Lagrange interpolating polynomials as:
where ${\widehat{L}}_{j}^{\left(k\right)}\left(\tau \right)=\prod _{l=1,l\ne j}^{{M}_{k}+1}\frac{\tau {\tau}_{l}^{\left(k\right)}}{{\tau}_{j}^{\left(k\right)}{\tau}_{l}^{\left(k\right)}}$, $1\le L\le {M}_{k}+1$, and ${M}_{k}$ is the number of the collocation points in interval ${S}_{k}$.
Integrating the expression in Eq. (18), Eq. (20) is expressed as:
where ${I}_{ji}^{\left(k\right)}(j,l=\mathrm{1,2},\cdots ,{M}_{k};k=\mathrm{1,2},\cdots ,N)$ is a ${M}_{k}\times {M}_{k}$ LGR integral matrix of LGR collocation point in $({\widehat{\tau}}_{1}^{\left(k\right)},{\widehat{\tau}}_{2}^{\left(k\right)}\cdots ,{\widehat{\tau}}_{{M}_{k}}^{\left(k\right)})$:
So, the relative and absolute error can be defined according to $X\left({\widehat{\tau}}_{l}^{\left(k\right)}\right)$ and $\widehat{X}\left({\widehat{\tau}}_{l}^{\left(k\right)}\right)$. The relative error ${E}_{i}^{\left(k\right)}\left({\widehat{\tau}}_{l}^{\left(k\right)}\right)$ and absolute error ${e}_{i}^{\left(k\right)}\left({\widehat{\tau}}_{l}^{\left(k\right)}\right)$ of the state variables in interval ${S}_{k}$ can be expressed as:
where $l=\mathrm{1,2},\cdots ,{M}_{k}+1$,$i=\mathrm{1,2},\cdots ,{n}_{x}$. And ${n}_{x}$ is number of the state variable.
Then the maximum relative error can be defined as^{}[29]:
4.2. Error range determination
Relationship between the estimated value $(\widehat{y},\widehat{u})$ of LGR discrete interval and its analytical solution $({y}^{*},{u}^{*})$ is:
where ${c}_{1}$ is a constant; $N$ is number of the collocation point; $h$ is the interval width; $q$ is the minimum value of the order of consecutive derivatives solved and $N$; ${\Vert \u2022\Vert}_{\infty}$ is interval norm.
4.3. Mesh refinement method
The solution result of Section 4.1 is used to determine whether the maximum relative error exceeds the tolerance error $\epsilon $ or not. If there is a grid relative error exceeding the tolerance error$\epsilon $, then the grid will be divided into smaller grids or the number of collocation point can be increased within the grid. When the state and control variables in the mesh are less smooth, the solution accuracy can be improved by refining the mesh. At the same time, when the state and control variables are smooth enough, the number of collocation points in the mesh is increased. Then the solution accuracy is improved by increasing the order of the interpolation polynomial.
4.3.1. Unsmooth mesh determination
It is assumed that the optimal solution on the $m$th interval, i.e. ${S}_{m}$, has been solved using the Radau pseudospectral method. And it is set that the solution of the state variable in $M$th iteration is ${X}^{\left(m\right)}\left(\tau \right)=\left[{X}_{1}^{\left(m\right)}\left(\tau \right),\cdots ,{X}_{{n}_{y}}^{\left(m\right)}\left(\tau \right)\right]$. Then continuous trajectory of the state and the control variable can be obtained by operating Lagrange interpolation on the state variable in ${S}_{m}$. So, the curvature of the trajectory can be expressed as:
where ${k}_{i}^{m}\left(\tau \right)$ is the curvature of the $i$th state variable in ${S}_{m}$. Since each state variable has a different curvature change in ${S}_{m}$, the maximum value is taken as a judgment to determine whether the trajectory is smooth or not:
If the curvature is satisfied with:
where $\stackrel{}{k}$ is the set curvature value, indicating that the trajectory is relatively smooth in the interval, and the interval needs to be further divided. Otherwise, the trajectory is smooth in the interval, and the accuracy of the solution can be improved by increasing the number of points.
For control variables, the same method can be used to define the changes of the control variable.
4.3.2. Mesh refinement method
4.3.2.1. Determination of subgrids number
It is assumed that the curvature in grid ${S}_{m}$ in the $m$th iteration meets Eq. (27), and it is known from the above analysis that the mesh needs to be refined. Taking equal sign for Eq. (24), then Eq. (28) can be obtained:
In order to obtain the desired minimum relative error $\epsilon $ in the $\left(M+1\right)$th iteration, Eq. (29) is obtained:
Since the grid ${S}_{m}$ has been refined, let ${N}_{m}^{(M+1)}={N}_{m}^{\left(M\right)}$, that is, the interval of ${S}_{m}^{M}$ in the $m$th interval and the iteration ${S}_{m}^{M+1}$ in $\left(M+1\right)$th iteration have the same number of collocation points. Eq. (30) can be obtained by combining Eq. (28) and Eq. (29):
where $H$ is the number of subgrids to be divided at the next step. The relative error in $\left(M1\right)$th iteration is:
$q$ can be solved by combining Eq. (28). And then the number of subintervals can be determined according to Eq. (30). Eq. (24) demonstrates that the number of subintervals newly divided is at least $H$ to ensure that the relative error in the iterative process can meet the requirements. But for a specific problem, $H$ may be larger, so this will lead to a rapid increase in the amount of calculations, so it is necessary to set upper limit of $H$. In the study of the paper, the number of the largest subinterval of ${S}_{m}$ is obtained based on the ratio of relative and set error:
where $\left[\u2022\right]$ indicates taking an integer down. Eq. (32) gives the range of the largest subinterval. Its division process is as follows. When ${e}^{\left(m\right)}\to \epsilon $, Eq. (32) may cause the value of ${H}_{max}$ to be too large, resulting in the subgrid being redundancy. When ${e}^{\left(m\right)}\to \epsilon $, ${H}_{max}$ decreases until it is 0 gradually. So ${H}_{max}$ always provides a reasonable number of subintervals. Then ${S}_{m}$ will be divided into:
Eq. (33) gives the number of divided meshes but does not give the meshing position.
4.3.2.2. Determination of subgrid position
In order to determine the location of the subgrid, density function and cumulative distribution function are defined firstly. Let $f:\left[x,y\right]\to {R}^{+}\left(x,y\in R\right)$ be a nonnegative Lebesgue integrable function, and ${\int}_{x}^{y}f\left(t\right)dt=1$, as well as $f$ be a density function. Then the integral of the density function on the defined domain is defined as the cumulative distribution function:
If $L$ collocation points ${\left\{{\tau}_{i}\right\}}_{i=1}^{L}=1$(${\tau}_{1}={T}_{k1},{\tau}_{L}={T}_{k}$) are inserted in interval $\left[{T}_{k1},{T}_{k}\right]$, and if position of ${\tau}_{i}$ is determined, then the position of ${\tau}_{i+1}$ is:
The density function based on the curvature has a dense distribution at the position where the curvature is large, and the node distribution is sparse in a small curvature. Therefore, the cumulative distribution function can be used to determine the position of the newly added grid point. The density function can be defined by Eq. (25):
where ${c}_{2}$ is a selected constant and meeting the following constraint:
Then the cumulative distribution function can be obtained:
The position of the subgrid is determined according to Eq. (33) and Eq. (34):
4.3.3. Distribution addition method
It is assuming that the solution in the grid ${S}_{m}$ does not satisfy the set error and Eq. (27). The default trajectory is smooth on interval ${S}_{m}$. Collocation points should be added to increase the order of the polynomial and to reduce its solution error. It is set that ${e}_{m}^{\left(M\right)}$ denote an error of the $M$th iteration on the interval ${S}_{m}$, and the grid width in the $\left(M+1\right)$th iteration is the same as in the $M$th iteration, i.e. ${h}_{k}^{M}={h}_{k}^{(M+1)}$. Then ${N}_{m}^{(M+1)}$ can be solved as:
where ${N}_{m}^{\left(M\right)}$ is the number of collocation points of the $M$th iteration on grid ${S}_{m}$. Since the number of collocation points is an integer, Eq. (40) should be transformed into:
In order to ensure that the order of the polynomial on grid ${S}_{m}$ is not too high, ${N}_{max}$ is used to limit the order of the polynomial. If ${N}_{m}^{\left(M+1\right)}>{N}_{max}$, the number of collocation points on the grid is ${N}_{max}$.
4.4. Mesh refinement and collocation process updating
The process of grid refinement and collocation point number optimization is as follows:
Step 1. Setting the initial grid and the number of collocation points in each grid.
Step 2. Resolving the nonlinear planning problem shown in Eq. (18) using the SNOPT software package.
Step 3. If the relative error resolved is less than the set relative error $\epsilon $, the calculation is terminated, and the result is outputted; otherwise, Step 4 is to be done.
Step 4. Determining whether the curvature of the trajectory meets the set value $k$, if it does not meet the requirement, go to step 4.1; otherwise, go to step 4.2.
Step 4.1. Dividing the grids according to the method in Section 4.3.2 and setting the number of collocation points.
Step 4.2. Adding the number of collocation points according to the method in Section 4.3.3 or dividing the grid.
Step 5. After all the grids and collocation points have been updated, the calculation result of previous step is taken as the initial value, and then go to Step 2.
5. Numerical simulations and experimental verification
5.1. Numerical simulations
In order to verify the effectiveness of the method proposed in this paper, the simulations are made in MATLAB. They show that the vehicle parameters are according to Ref. [28].
5.1.1. Double Lane Changing Condition
In the test of driving stability of ordinary vehicles as well as in the test of tracking ability of intelligent vehicles, the double lane changing condition is a test section used frequently. However, since the track function of standard double lane changing condition is a piecewise function with poor continuity, in order to restore the true driving track under the double lane changing condition, the hyperbolic function is used to perform nonlinear fitting. And the following results are obtained:
where $X$ and $Y$ are the longitudinal and lateral positions respectively.
Fig. 2 shows the results of the lateral displacement, steering wheel angle, lateral acceleration, yaw rate and longitudinal speed under the double lane change road condition with the initial speed of 108 km/h.
From Fig. 2(a), it can be seen that the vehicle can track the double lane change road basically with the control of the proposed algorithm.
From Fig. 2(b), it can be seen that a large steering wheel angle is required to enter and exit the corners of the double lane change road. Especially, when entering the first corner and exiting the fourth corner of the double lane change road, the steering wheel angle reaches its maximum values.
From Fig. 2(c), it also can be seen that the lateral acceleration is higher at 60 m, 100 m, 430 m and 490 m; that indicates that when entering and exiting the corners of the double lane change road, the vehicle will generate the highest lateral acceleration.
From Fig. 2(d), it also can be seen that the yaw rate is higher at 60 m, 100 m, 430 m and 490 m; that indicates that when entering and exiting the corners of the double lane change road, the vehicle will generate a greater yaw rate.
From Fig. 2(e), it also can be seen that to complete the process of passing the double lane change road with minimum time, the vehicle must establish continuous acceleration.
Fig. 2Simulation results of the state variables under the double lane change condition
a) Lateral displacement
b) Steering wheel angle
c) Lateral acceleration
d) Yaw rate
e) Longitudinal speed
5.1.2. Overtaking condition
Overtaking is a common operation mode in the process of vehicle driving.
Figs. 3(a)(d) show the simulation results under the overtaking condition.
From Fig. 3(a), it can be seen that the vehicle can complete the processing of overtaking basically with the control of the proposed algorithm.
From Fig. 3(b), it can be seen that a large steering wheel angle is required to enter the adjacent lane from the current lane. Especially, in order to maintain stability after entering the adjacent lane, a large steering wheel angle is still required.
From Fig. 3(c), it also can be seen that a high lateral acceleration is required when entering the adjacent lane from the current lane.
From Fig. 3(d), it also can be seen that the yaw rate is greater at 15 m, 36 m; that indicates that when entering and exiting the current lane, the vehicle will generate a greater yaw rate.
Fig. 3Simulation results of state variables under overtaking condition
a) Lateral displacement
b) Steering wheel angle
c) Lateral acceleration
d) Yaw rate
5.2. Accuracy and efficiency verification
A comparison is made in order to verify the superiority of this method over the AMRC and GPM methods.
5.2.1. Double lane changing condition
Figs. 4(a)(c) show the simulation results of the steering wheel angle and the error of steering wheel angle obtained by the AMRC and GPM methods in the double lane changing condition.
From Fig. 4(a), it can be seen that the trend of the curves of the steering wheel angle obtained by AMRC and GPM methods is basically consistent. However, it can be seen from Fig. 4(b) that the error of steering wheel angle calculated by the AMRC is smaller than that of the GPM method. This is because the method in this paper has fewer collocation and discrete equations and sparse Jacobian matrix, so it improves the speed of solving NLP and reduces the time of optimization. Fig. 4 indicates that under the same condition, it is required a less number of collocations and meshes, so the calculation accuracy is higher. This ensures the superiority of the proposed method. And also, it can be seen from Fig. 4(c) that the mean value of estimation error of steering wheel angle of the GPM method is 0.06 deg, while the one of the AMRC method is 0.028 deg, which is smaller than that of the GPM method. This ensures the higher calculation accuracy of the proposed method.
5.2.2. Overtaking condition
In order to analyze the computational efficiency of the proposed method, the calculation accuracy is compared between the proposed method and the GPM method. The comparison results are shown in Table 3. It can be seen from the table that for the same calculation accuracy, the number of iterations and the calculation time of the hybrid method were lower than that in the direct multiple shooting method. This demonstrated that the proposed hybrid method had better solving efficiency.
Fig. 4Comparison results between AMRC and GPM under double lane changing condition
a) Steering wheel angle
b) Error of steering wheel angle
c) Mean value of estimation error of steering wheel angle
Table 3Comparison of number of iterations and calculation time of each method.
Calculation accuracy (m)  Number of iterations  Time of calculation (s)  
AMRC  GPM  AMRC  GPM  
10^{2}  2  4  27.36  69.47 
5.3. Experimental verification
A virtual test adopting the CarSim software is conducted to verify the feasibility of the simulated results.
CarSim vehicle dynamics software can quickly build a vehicle dynamics model and driving scene of the simulated vehicle by configuring parameters, and can also conduct a realtime simulation. The vehicle dynamics model is developed in the CarSim, which is a professional vehicle system simulation software. It is adopted by many automobile manufacturers and parts suppliers in the world, and it is the standard software of the vehicle industry. CarSim adopts a systemoriented parametric modeling method. Users only need to select each vehicle component module from the model database and configure the corresponding parameters as required to complete quickly the construction of the vehicle dynamics model. CarSim offers a variety of vehicle models including sedans, pickups, and SUVs. Carsim is the vehicle state research software that uses the Vehicle Sim technology based on the vehicle dynamics and takes the simulation as the technical method. During the project development and research, the use of Carsim can greatly reduce the time spent on development, testing and planning, and allow proposing better vehicle dynamics decisionmaking methods. For the research projects, such simulation technology can theoretically prove the expected results, which can provide a theoretical basis for a later research and development.
In this paper, the vehicle dynamics model of the driving simulation system is quickly built in the CarSim by configuring the parameters, and the control platform and motion simulation platform are developed by using its data interface. This improves the complexity of vehicle dynamics modeling in the process of the driving simulation system development, can reduce the difficulty of vehicle dynamics modeling in the driving simulation system, and simplify the development process.
From Fig. 5, it can be seen that for the lateral displacement and the steering wheel angle as well as longitudinal speed, there are discrepancies between the simulated and the virtual test values. This is because that the model in the virtual test ignores the nonlinearity of the steering system and suspension system. However, the trend of the curves in Figs. 5(a)(c) is enough to illustrate the correctness of the proposed method.
Fig. 5Experimental results of lateral displacement and steering wheel angle as well as longitudinal speed
a) Lateral displacement
b) Steering wheel angle
c) Longitudinal speed
6. Conclusions
To solve the problem of minimum time lane changing problem of vehicle handling inverse dynamics, this paper proposes an adaptive mesh refinement and collocation optimization method on the basis of traditional pseudospectral method and based on a nonlinear 7DOF vehicle dynamics model as well as the Magic formula tire model. The simulation results show that the adaptive mesh refinement and collocation optimization method proposed in this paper can solve the problem of minimum time lane changing problem of vehicle handling inverse dynamics with high accuracy by approximating the optimal solution by densifying the mesh and adding collocation nearby. In the process of optimization solution, the method proposed in this paper can adaptively increase the number of collocations and reduce the number of meshes which can generate fewer total collocation in the solution area reducing the number of nonlinear programming equations after discretization, and improving the solving speed of the SQP method.
References

S. Cheng, L. Li, M.M. Mei, Y.L. Nie, and L. Zhao, “Multipleobjective adaptive cruise control system integrated with DYC,” IEEE Transactions on Vehicular Technology, Vol. 68, No. 5, pp. 4550–4559, May 2019, https://doi.org/10.1109/tvt.2019.2905858

P. Wang, S. Gao, L. Li, B. Sun, and S. Cheng, “Obstacle avoidance path planning design for autonomous driving vehicles based on an improved artificial potential field algorithm,” Energies, Vol. 12, No. 12, p. 2342, Jun. 2019, https://doi.org/10.3390/en12122342

J. Naskath, B. Paramasivan, Z. Mustafa, and H. Aldabbas, “Connectivity analysis of V2V communication with discretionary lane changing approach,” The Journal of Supercomputing, Vol. 78, No. 4, pp. 5526–5546, Mar. 2022, https://doi.org/10.1007/s11227021040868

M. A. M. Yussof, N. H. Amer, Z. A. Kadir, K. Hudha, M. S. Rahmat, and M. H. Harun, “Yaw stability control of singletrailer truck using steerable wheel at middle axle: hardwareintheloop simulation,” International Journal of Dynamics and Control, Vol. 10, No. 6, pp. 2072–2094, Dec. 2022, https://doi.org/10.1007/s40435022009433

T. Ercan, N. C. Onat, N. Keya, O. Tatari, N. Eluru, and M. Kucukvar, “Autonomous electric vehicles can reduce carbon emissions and air pollution in cities,” Transportation Research Part D: Transport and Environment, Vol. 112, p. 103472, Nov. 2022, https://doi.org/10.1016/j.trd.2022.103472

W. Cao and H. Zhao, “Lane change algorithm using rulebased control method based on lookahead concept for the scenario when emergency vehicle approaching,” Artificial Life and Robotics, Vol. 27, No. 4, pp. 818–827, Nov. 2022, https://doi.org/10.1007/s10015022007836

J. Jiang, Y. Yang, Y. Li, R. Wang, and S. Zeng, “Lanelevel vehicle counting based on V2X and centimeterlevel positioning at urban intersections,” International Journal of Intelligent Transportation Systems Research, Vol. 20, No. 1, pp. 11–28, Apr. 2022, https://doi.org/10.1007/s13177021002714

Z. Yang, Z. Gao, F. Gao, X. Wu, and L. He, “Lane changing assistance strategy based on an improved probabilistic model of dynamic occupancy grids,” Frontiers of Information Technology and Electronic Engineering, Vol. 22, No. 11, pp. 1492–1504, Nov. 2021, https://doi.org/10.1631/fitee.2000439

T. Vaishnavi and C. Sheeba Joice, “A novel self adaptiveelectric fish optimizationbased multilane changing and merging control strategy on connected and autonomous vehicle,” Wireless Networks, Vol. 28, No. 7, pp. 3077–3099, Oct. 2022, https://doi.org/10.1007/s11276022030229

A. K. Das and U. Chattaraj, “Cellular automata model for lane changing activity,” International Journal of Intelligent Transportation Systems Research, Vol. 20, No. 2, pp. 446–455, Aug. 2022, https://doi.org/10.1007/s13177022003028

J. Xiao, M. Ma, S. Liang, and G. Ma, “The nonlanedisciplinebased carfollowing model considering forward and backward vehicle information under connected environment,” Nonlinear Dynamics, Vol. 107, No. 3, pp. 2787–2801, Feb. 2022, https://doi.org/10.1007/s11071021069998

C. Huang, L. Li, S. Fang, S. Cheng, and Z. Chen, “Energy saving performance improvement of intelligent connected PHEVs via NNbased lane change decision,” Science China Technological Sciences, Vol. 64, No. 6, pp. 1203–1211, Jun. 2021, https://doi.org/10.1007/s1143102017463

P. Fafoutellis, J. PlymenosPapageorgas, and E. I. Vlahogianni, “Enhancing lane change prediction at intersections with spatiotemporal adequacy information,” Journal of Big Data Analytics in Transportation, Vol. 4, No. 1, pp. 73–84, Apr. 2022, https://doi.org/10.1007/s42421022000556

Y. Wang, X. Cao, and X. Ma, “Evaluation of automatic lanechange model based on vehicle cluster generalized dynamic system,” Automotive Innovation, Vol. 5, No. 1, pp. 91–104, Feb. 2022, https://doi.org/10.1007/s4215402100171z

H. Hamedi and R. Shad, “Contextaware similarity measurement of lanechanging trajectories,” Expert Systems with Applications, Vol. 209, p. 118289, Dec. 2022, https://doi.org/10.1016/j.eswa.2022.118289

C. Guo, T. Zhang, Q. Guo, T. Yu, Z. Fang, and Z. Yan, “Fullscale experimental study on fire characteristics induced by double fire sources in a twolane road tunnel,” Tunnelling and Underground Space Technology, Vol. 131, p. 104768, Jan. 2023, https://doi.org/10.1016/j.tust.2022.104768

O. Sharma, N. C. Sahoo, and N. B. Puhan, “Highway lanechanging prediction using a hierarchical software architecture based on support vector machine and Continuous Hidden Markov model,” International Journal of Intelligent Transportation Systems Research, Vol. 20, No. 2, pp. 519–539, Aug. 2022, https://doi.org/10.1007/s13177022003082

Y. Zhou, R. Wang, R. Ding, D. Shi, and Q. Ye, “Investigation on hierarchical control for driving stability and safety of intelligent HEV during carfollowing and lanechange process,” Science China Technological Sciences, Vol. 65, No. 1, pp. 53–76, Nov. 2021, https://doi.org/10.1007/s1143102118918

X. Wang, Q. Liu, F. Guo, S.E. Fang, X. Xu, and X. Chen, “Causation analysis of crashes and near crashes using naturalistic driving data,” Accident Analysis and Prevention, Vol. 177, p. 106821, Nov. 2022, https://doi.org/10.1016/j.aap.2022.106821

C. Wei, F. Hui, Z. Yang, S. Jia, and A. J. Khattak, “Finegrained highway autonomous vehicle lanechanging trajectory prediction based on a heuristic attentionaided encoderdecoder model,” Transportation Research Part C: Emerging Technologies, Vol. 140, p. 103706, Jul. 2022, https://doi.org/10.1016/j.trc.2022.103706

H. Zhang, Y. Guo, C. Wang, and R. Fu, “Stacking‐based ensemble learning method for the recognition of the preceding vehicle lane‐changing manoeuvre: A naturalistic driving study on the highway,” IET Intelligent Transport Systems, Vol. 16, No. 4, pp. 489–503, Apr. 2022, https://doi.org/10.1049/itr2.12154

M. Tajalli, R. Niroumand, and A. Hajbabaie, “Distributed cooperative trajectory and lane changing optimization of connected automated vehicles: Freeway segments with lane drop,” Transportation Research Part C: Emerging Technologies, Vol. 143, p. 103761, Oct. 2022, https://doi.org/10.1016/j.trc.2022.103761

X. He, H. Yang, Z. Hu, and C. Lv, “Robust lane change decision making for autonomous vehicles: an observation adversarial reinforcement learning approach,” IEEE Transactions on Intelligent Vehicles, Vol. 8, No. 1, pp. 184–193, Jan. 2023, https://doi.org/10.1109/tiv.2022.3165178

K. Shi, Y. Wu, H. Shi, Y. Zhou, and B. Ran, “An integrated carfollowing and lane changing vehicle trajectory prediction algorithm based on a deep neural network,” Physica A: Statistical Mechanics and its Applications, Vol. 599, p. 127303, Aug. 2022, https://doi.org/10.1016/j.physa.2022.127303

G. Li, Y. Yang, S. Li, X. Qu, N. Lyu, and S. E. Li, “Decision making of autonomous vehicles in lane change scenarios: Deep reinforcement learning approaches with risk awareness,” Transportation Research Part C: Emerging Technologies, Vol. 134, p. 103452, Jan. 2022, https://doi.org/10.1016/j.trc.2021.103452

T. A. Wenzel, K. J. Burnham, M. V. Blundell, and R. A. Williams, “Dual extended Kalman filter for vehicle state and parameter estimation,” Vehicle System Dynamics, Vol. 44, No. 2, pp. 153–171, Feb. 2006, https://doi.org/10.1080/00423110500385949

Y. Liu and Y. Liu, “Research on lane change motion planning steering input based on optimal control theory,” Mathematical Problems in Engineering, Vol. 2022, pp. 1–12, Jun. 2022, https://doi.org/10.1155/2022/8467627

Y. Liu and J. Jiang, “Optimum pathtracking control for inverse problem of vehicle handling dynamics,” Journal of Mechanical Science and Technology, Vol. 30, No. 8, pp. 3433–3440, Aug. 2016, https://doi.org/10.1007/s1220601607019

F. Liu, W. W. Hager, and A. V. Rao, “Adaptive mesh refinement method for optimal control using nonsmoothness detection and mesh size reduction,” Journal of the Franklin Institute, Vol. 352, No. 10, pp. 4081–4106, Oct. 2015, https://doi.org/10.1016/j.jfranklin.2015.05.028
About this article
This research was supported by the Science and Technology Program Foundation of Weifang under Grant 2015GX007. And also, this research was financially supported by the Open Research Fund from the State Key Laboratory of Rolling and Automation, Northeastern University, under Grant 2021RALKFKT008. The first author gratefully acknowledges the support agency.
The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.
Yingjie Liu: mathematical model and the simulation techniques. Dawei Cui: spelling and grammar checking as well as virtual validation. Wen Peng: virtual validation.
The authors declare that they have no conflict of interest.