A Maneuver Evaluation Algorithm for Lane-Change Assistance System

Abstract

This paper proposes a maneuver evaluation approach to enhance driving safety by providing decision aids. Based on the deliberative understanding of environmental semantic information, the proposed algorithm evaluates the risk of candidate driving maneuvers, including aggressive lane-change maneuver, passive lane-change maneuver, lane-change abort maneuver, and lane-keeping maneuver. The effectiveness of the proposed method is validated through various simulation experiments. The experimental results demonstrate that the proposed approach is capable of efficiently evaluating the feasibility and the cost of each candidate driving maneuver. The approach also provides suggestions on how to adjust the speed, and when to initiate a lane-change maneuver.

1. Introduction

In order to ensure the safety of driving and improve the efficiency of transportation, intelligent driving technology is developing rapidly. Nowadays, intelligent driving assistance systems and partially automated driving technologies are gradually entering the market. The SAE On-Road Automated Vehicle Standards Committee introduced various levels of driving automation [1], including Level 1 (Driver Assistance), L2 (Partial Automation), Level 3 (Conditional Automation), Level 4 (High Automation), and Level 5 (Full Automation). Automated lane change systems have already been integrated in some commercial applications of Level 2 systems, such as Tesla Autopilot and GM Super Cruise [2]. Some institutions are testing the deployment of Level 4 systems, such as Waymo, GM, Daimler, BMW, Ford, Volvo, and Baidu [3]. There still remains many unresolved problems for automated driving in complex traffic scenarios, including perception, decision-making, and trajectory planning. UNECE recently published an official regulation on automated lane keeping systems (ALKS) [4]. In its current form, the regulation limits the speed of ALKS to a maximum of 60 km/h. Due to technical limitations and people’s acceptance of automated driving technology, it is crucial that intelligent driving assistance systems should be sufficiently developed before the realization of automated driving.

There are different strategies for the machine to assist the driver. The assistance system can help the driver make safe decisions or realize assistant control. In [5], a radical strategy is utilized. When the situation is judged to be dangerous, the system intervenes, and the machine determines the final decision and steering angle. In [6], a conservative strategy is adopted. If the driver represents the intention of the lane-change maneuver, or the system predicts that the driver wants to change lane, the decision algorithm can evaluate whether it is safe to change lane. The assistance system provides decision-making assistance and allows the driver to make the final decision.

There are some works that have been conducted to improve the capabilities of the system, including trajectory prediction, threat assessment, and recommendations regarding lane-change decisions. The turning signal is the most exact message that can express the intention of lane change. Other indicators, including the steering angle, heading angle, latitudinal distance to lane markers, and the time to cross lane (TLC), can also be employed to determine whether the driver wants to initiate a lane-change maneuver. Some scholars have studied the vehicle trajectory prediction problem based on machine learning and model-based methods [7,8,9,10]. In [6], a Bayesian classifier for the identification of lane-change intention is established by learning from the data of the distance gap and closing speeds. In [11], the parameters of the lane change model extracted from the Next Generation Simulation (NGSIM) dataset are used to predict vehicle trajectory. In our previous work [12,13], the lane-change intention of the drivers is predicted by using a dynamic Bayesian network framework.

Single behavior threat metrics have been widely used for threat assessment. Time-related metrics, including the time-to-collision (TTC) [14], time-to-react (TTR), or time-to-brake (TTB) [15,16,17], and acceleration related metrics [18,19] are used to evaluate the threat. The heading angle of the vehicle changes while avoiding obstacles. In collision avoidance scenarios, these indicators cannot reflect the influence of changes in the heading angle. Due to such limits, it is difficult to obtain the accurate safety critical value of the metrics for safety assessment. When using this type of indicator, a conservative strategy is usually adopted in order to prevent collisions. The risk can be defined as the probability of collision [20]. The authors of [19] conducted threat assessment by calculating the collision probability with consideration of the multiple traffic reachable set. In [21], the authors used extended Kalman filters (EKF) to predict the future state and then calculated the collision probability. The algorithm determines whether the vehicle-body-shaped polygons of the host vehicle and traffic participants can be intersected. By applying formalized verification methods, the safety of lane change maneuvers are verified in [22]. In [23], the authors evaluate whether the reserved spaces is suitable for lane change to determine the feasibility of lane change maneuver.

The proposed maneuver evaluation method in this paper is different from the above papers. In this paper, the proposed maneuver evaluation algorithm not only verifies the risk of the traffic scenario, but also quantifies the candidate driving maneuvers. At the same time, the optimal maneuver is obtained. Suggestions regarding the speed adjustment strategy and lane-change timing for the lane-change maneuver are provided. The framework of the proposed maneuver evaluation algorithm is shown in Figure 1.

In this paper, the proposed method belongs to Level 1 according to the SAE driving automation standard [1]. The driving scenario awareness module receives perception information from on-board sensors. To guarantee a better understanding of the traffic situation, the environment semantics are analyzed to identify candidate driving maneuvers. In the driving decision module, the unreasonable candidate driving maneuvers are eliminated, and the remaining candidate maneuvers are quantified and evaluated. Finally, the driving decision is provided.

The contributions of this work are twofold. First, the safe distances considering lateral motion and longitudinal motion for continuing lane-change maneuver and canceling lane-change maneuver are discussed. To the author’s knowledge, only a few studies have discussed the safe distance for canceling lane-change maneuver. Second, a maneuver evaluation algorithm for lane-change decision-making is proposed, and the feasibility for each candidate maneuver is quantified and evaluated. The hard constraints on safety distance combined with the soft constraint that suggests that the vehicle should not interfere with the normal driving of other vehicles are taken into consideration.

The remainder of this paper is organized as follows: In Section 2, the driving scenario awareness module is introduced. In Section 3, the safe distance requirements for lane keeping, lane change, and canceling lane change are described. In Section 4, we propose the algorithm for evaluating candidate driving maneuvers. In Section 5, the experiment results are shown. Conclusions are drawn in Section 6.

2. Driving Scenario Awareness

Driving maneuvers are largely dependent on the context. Each series of actions that a driver can take corresponds to a maneuver, such as lane keeping, lane change, left turn, and right turn. The lane-change decision-making algorithm should have the ability to reason the driver’s candidate maneuver patterns. According to the relative position of surrounding vehicles, the preliminary candidate corridors can be obtained. Each corridor corresponds to a specific driving maneuver. A double-lane traffic scenario is shown in Figure 2, in which the red vehicle is the host vehicle.

In the dynamic traffic scenario shown in Figure 2a, the red vehicle represents the host vehicle, and the speed of the left rear blue vehicle on the right lane is higher than that of the front vehicle. Considering the spatio-temporal information, the host vehicle has two candidate lane-change maneuvers and a lane-keeping maneuver, as shown in Figure 2b. The host vehicle may perform an aggressive maneuver and overtake the left rear vehicle. Moreover, it can perform passive maneuvers and change lane after the left rear vehicle passes it. The host vehicle may also perform the lane-keeping maneuver. The decision-making module should have the ability of reasoning and evaluate the safety of optional maneuvers.

3. Safe Distance for Candidate Driving Maneuvers

The motion of the host vehicle is subject to a variety of constraints, including the vehicle kinematic limits, and collision avoidance with the road and obstacles. In this paper, the safe distance required for lane keeping, lane change, and canceling lane change is discussed. Hallerbach et al. [24] introduced a toolchain for identifying critical scenarios. The authors used standard safety metrics, such as TTC and TTB; the required deceleration $a_{req}$; and combined traffic quality metrics to evaluate the traffic. The paper only considered the metrics in terms of longitudinal motion. The lateral motion cannot be reflected exactly by the used metrics. Since the outer boundary of the vehicle is affected by the heading angle of the vehicle, different lateral positions and heading angles of the host vehicle may lead to different results in identifying critical scenarios, which was not considered in [24]. In this paper, the lateral motion and longitudinal motion are taken into consideration for calculating the safe distance during lane change. The influence of the outer boundary of the host vehicle on safe distance can be more accurately reflected.

3.1. Driving Maneuver of Lane Keeping

The scenario for the lane-keeping maneuver is shown in Figure 3. Inspired by the responsibility-sensitive safety (RSS) model proposed by Mobileye [25], the safe distance for the lane-keeping maneuver is defined below.

The velocity of the front vehicle A is $v_f$, and the longitudinal velocity of the rear vehicle B is $v_r$. The safe distance is obtained assuming that vehicle A decelerates at $a_{f,brake}$ until it stops, while vehicle B drives at $a_{accel}$ during the reaction time $t_{\delta }$ and decelerates at $a_{r,brake}$ until it stops. If the two vehicles do not collide during the entire process, then the distance is safe.

$$D_{safe,kp}=v_r{t}_{\delta }+\frac{1}{2}{a}_{\mathit{accel}}{t}_{\delta }^2+\frac{{\left(v_r+a_{\mathit{accel}}{t}_{\delta }\right)}^2}{2a_{r,\mathit{brake}}}-\frac{v_f^2}{2a_{f,\mathit{brake}}}$$

(1)

3.2. Driving Maneuver of Lane Change

In this paper, to simplify the calculation of safe distances of lane-change maneuver in structured roads, the motion is divided into lateral motion and longitudinal motion in the lane frame. The lane-change process is divided into three stages, namely, the preparation period, the transition period, and the post period, as shown in Figure 4.

In each stage, the host vehicle follows different longitudinal position constraints. In the preparation period, the host vehicle adjusts the speed and position to obtain enough space for lane change. During the transition period, the host vehicle crosses the lane line, and the position is constrained by the four vehicles in the target lane and in the original lane. In the post period, the position of the host vehicle is only constrained by the front and rear vehicles in the target lane. The longitudinal position constraints during the lane change process are as follows.

$$\begin{array}{cc}\hfill s_{max,pre}=& s_{L0}-D_{L0}\hfill \end{array}$$

(2a)

$$\begin{array}{cc}\hfill s_{min,pre}=& s_{F0}+D_{F0}\hfill \end{array}$$

(2b)

$$\begin{array}{cc}\hfill s_{max,tran}=& min\left(s_{Ld}-D_{Ld},s_{L0}-D_{L0}\right)\hfill \end{array}$$

(2c)

$$\begin{array}{cc}\hfill s_{min,tran}=& max\left(s_{Fd}+D_{Fd},s_{F0}+D_{F0}\right)\hfill \end{array}$$

(2d)

$$\begin{array}{cc}\hfill s_{max,post}=& s_{Ld}-D_{Ld}\hfill \end{array}$$

(2e)

$$\begin{array}{cc}\hfill s_{min,post}=& s_{Fd}+D_{Fd}\hfill \end{array}$$

(2f)

$s_{L0}$ and $s_{F0}$ are the longitudinal positions of the front and rear vehicles in the original lane. $s_{Ld}$ and $s_{Fd}$ are the longitudinal positions of the front and rear vehicles in the target lane. $D_{Ld}$, $D_{L0}$, $D_{Fd}$, and $D_{F0}$ are the required longitudinal safe distances. $s_{max,pre}$ and $s_{min,pre}$ are the maximum and minimum longitudinal positions in the preparation period. $s_{max,tran}$ and $s_{min,tran}$ are the maximum and minimum longitudinal positions in the transition period. $s_{max,post}$ and $s_{min,post}$ are the maximum and minimum longitudinal positions in the post period.

In this paper, motion is divided into lateral motion and longitudinal motion. A lateral motion model is utilized, in which the lateral acceleration is assumed to be a sinusoid function of time.

$$\begin{array}{cc}\hfill a_{lat}=& \frac{2\pi H}{t_{lat}^2}sin\left(\frac{2\pi }{t_{lat}}\right)\hfill \end{array}$$

(3a)

$$\begin{array}{cc}\hfill y\left(t\right)=& -\frac{H}{2\pi }sin\left(\frac{2\pi }{t_{lat}}t\right)+\frac{H}{t_{lat}}t+y_{start}\hfill \end{array}$$

(3b)

$$\begin{array}{cc}\hfill H=& {|y}_{target}-y_0|\hfill \end{array}$$

(3c)

where $a_{lat}$ is the lateral acceleration in the lane frame, H is the total lateral distance to complete the lane-change process the in lane frame, $t_{lat}$ is the total lateral motion time, $y_{start}$ is the lateral position before the lane-change maneuver, and $y_{target}$ is the terminal lateral position, as shown in Figure 5. The longitudinal motion is assumed to be uniformly accelerated.

$$v_{lon}\left(t\right)=v\left(0\right)+at$$

(4)

Thus, the heading angle during the process of lateral motion can be obtained.

$$tan\phi \left(t\right)=v_{lat}\left(t\right)/v_{lon}\left(t\right)$$

(5)

Based on the lateral motion model, assuming that the heading angle equals $\phi$, the time $t_{\phi }$ required from the vehicle initiating lateral motion can be derived.

$$t_{\phi }=\frac{t_{lat}}{2\pi }·\mathrm{arc}cos\left(-\frac{t_{lat}}{H}\left(vtan\phi -\frac{H}{t_{lat}}\right)\right)$$

(6)

If a lateral terminal position $y_{target}$ in the lane frame and the current lateral terminal position $y_{current}$ are determined, $y_{start}$ and $t_{\phi }$ can be obtained by sampling the $y_{start}$ and comparing $y\left(t_{\phi }\right)$ with $y_{current}$.

In [26], Jula et al. derived the safe longitudinal distance for lane change. However, the safe longitudinal distance during lateral motion was not derived. In this paper, we modify the safe distance to obtain the safe longitudinal distance during lateral motion. In order to calculate the longitudinal safe distance, the following critical lateral positions for the host vehicle are defined, as shown in Figure 6.

The time $t_{c,x}$ required to move from the current state to the critical position can be calculated. Since the longitudinal motion time equals the lateral motion time, given the prediction horizon T, the safe longitudinal distance for the current state can be obtained.

$$\begin{array}{cc}\hfill D_{Fd}=& \underset{t}{max}\left({\int }_0^t{\int }_0^{\lambda }\left(a_{Fd}\left(\tau \right)-a_m\left(\tau \right)\right)d\tau d\lambda +\left(v_{Fd}-v_m\right)t\right),\forall t\in \left[t_{c,Fd},T\right]\hfill \end{array}$$

(7a)

$$\begin{array}{cc}\hfill D_{Ld}=& \underset{t}{max}\left({\int }_0^t{\int }_0^{\lambda }\left(a_m\left(\tau \right)-a_{Ld}\left(\tau \right)\right)d\tau d\lambda +\left(v_m-v_{Ld}\right)t\right),\forall t\in \left[t_{c,Ld},T\right]\hfill \end{array}$$

(7b)

$$\begin{array}{cc}\hfill D_{F0}=& \underset{t}{max}\left({\int }_0^t{\int }_0^{\lambda }\left(a_{F0}\left(\tau \right)-a_m\left(\tau \right)\right)d\tau d\lambda +\left(v_{F0}-v_m\right)t\right),\forall t\in \left[0,t_{c,F0}\right]\hfill \end{array}$$

(7c)

$$\begin{array}{cc}\hfill D_{L0}=& \underset{t}{max}\left({\int }_0^t{\int }_0^{\lambda }\left(a_m\left(\tau \right)-a_{L0}\left(\tau \right)\right)d\tau d\lambda +\left(v_m-v_{L0}\right)t\right),\forall t\in \left[0,t_{c,L0}\right]\hfill \end{array}$$

(7d)

3.3. Driving Maneuver of Canceling Lane Change

During the transition period of the lane-change process, the insufficient gap may make the lane change infeasible if the surrounding vehicles are driving uncooperatively. The driving assistance system should continuously evaluate the safety of continuing the lane-change maneuver and judge whether the lane change should be canceled. We divided the lane-change canceling process into two major stages, as shown in Figure 7. In the first stage, the vehicle adjusts the lateral velocity and the heading angle. In the second stage, the vehicle continues to travel to the original lane.

During the first stage, it is assumed that the host vehicle moves at constant lateral acceleration $a_{lat}$. At time $t_1$, the vehicle’s heading is paralleled to the lane line, and the lateral velocity is zero.

$$\begin{array}{cc}\hfill t_1=& v_{lat}/a_{lat}\hfill \end{array}$$

(8a)

$$\begin{array}{cc}\hfill y\left(t_1\right)=& y_{current}+v_{lat}{t}_1-\frac{1}{2}{a}_{lat}{t}_1^2\hfill \end{array}$$

(8b)

According to the lateral position at $t_1$, the lane-change abort scenario can be divided into two cases. As shown in Figure 7a, if the host vehicle has not entered the target lane at $t_1$, the position is constrained by the front and rear vehicle in the original lane. The host vehicle can adjust its velocity in lane-keeping mode. Otherwise, if the host vehicle enters the target lane at $t_1$ (Figure 7b), the position is constrained by the vehicles in both lanes. The traffic scenario at time $t_1$ is the same as the right lane-change scenario.

For the second case, the lane-change abortion process is divided into three stages, namely, the adjustment period, the transition period, and the post period. In the adjustment period, the host vehicle adjusts the lateral velocity and heading angle. In the transition period, the host vehicle returns to the original lane. In the post period, the host vehicle adjusts the speed and position in the original lane. In each phase, the host vehicle follows different constraints in the longitudinal position. Similarly to the left lane-change scenario, the critical lateral position for the right lane-change can be defined as shown in Figure 8.

$$\begin{array}{cc}\hfill D_{F0}=& \underset{t}{max}\left({\int }_0^t{\int }_0^{\lambda }\left(a_{F0}\left(\tau \right)-a_m\left(\tau \right)\right)d\tau d\lambda +\left(v_{F0}-v_m\right)t\right),\forall t\in \left[t_1+t_{c,F0},T\right]\hfill \end{array}$$

(9a)

$$\begin{array}{cc}\hfill D_{L0}=& \underset{t}{max}\left({\int }_0^t{\int }_0^{\lambda }\left(a_m\left(\tau \right)-a_{L0}\left(\tau \right)\right)d\tau d\lambda +\left(v_m-v_{L0}\right)t\right),\forall t\in \left[t_1+t_{c,L0},T\right]\hfill \end{array}$$

(9b)

$$\begin{array}{cc}\hfill D_{Fd}=& \underset{t}{max}\left({\int }_0^t{\int }_0^{\lambda }\left(a_{Fd}\left(\tau \right)-a_m\left(\tau \right)\right)d\tau d\lambda +\left(v_{Fd}-v_m\right)t\right),\forall t\in \left[0,t_1+t_{c,Fd}\right]\hfill \end{array}$$

(9c)

$$\begin{array}{cc}\hfill D_{Ld}=& \underset{t}{max}\left({\int }_0^t{\int }_0^{\lambda }\left(a_m\left(\tau \right)-a_{Ld}\left(\tau \right)\right)d\tau d\lambda +\left(v_m-v_{Ld}\right)t\right),\forall t\in \left[0,t_1+t_{c,Ld}\right]\hfill \end{array}$$

(9d)

where $t_1$ is the time used to adjust the lateral velocity to zero in the adjustment period, and $t_{c,x}$ is the lateral movement time it takes to move from the lateral position $y\left(t_1\right)$ at time $t_1$ to the critical lateral position $y\left(t_{c,x}\right)$. T is the prediction horizon.

4. Evaluation of Candidate Driving Maneuvers

4.1. Elimination of Unreasonable Driving Maneuvers

The candidate driving maneuvers can be truncated according to the limitation of motion and the basic spatial-temporal constraints. The motion can be divided into lateral and longitudinal motion in the lane frame. The longitudinal motion of a vehicle is affected by its power and deceleration ability. The acceleration of the host vehicle is limited by the friction force, longitudinal weight transfer, bank and grade affect, etc.. The permissible speed is limited by curvature of the path and maximum allowed speed by traffic rules. The vehicle should follow the constraints in

Table 1. The motion limits.

Kinematic Constraints	Description
$a_{max,lat}$	Maximum lateral acceleration
$a_{max,lon}$	Maximum longitudinal acceleration
$a_{min,lon}$	Minimum longitudinal acceleration
$v_{max,lon}$	Maximum longitudinal speed
$v_{min,lon}$	Minimum longitudinal speed

.

Considering the spatial-temporal constraint, the lateral motion is constrained by the vehicles in the original lane and the target lane. To explain the spatial-temporal constraint clearly, we take a simple scenario of one vehicle in the current lane and one in the adjacent lane as an example, as shown in Figure 2. The host vehicle has three candidate maneuvers, including overtaking the left vehicle, following the left vehicle, and lane keeping. The S-T graph is shown in Figure 9.

In Figure 9, the yellow area represents the set of longitudinal positions that the vehicle can reach in the prediction time domain. At time $t_0$, the positions of the front and the left vehicle are $x_{cf}$ and $x_{lr}$, respectively. If the surrounding two vehicles drive at a constant speed, they will arrive at the same longitudinal position $x_c$ at time $t_c$. Due to the limitation of acceleration, the longitudinal position of the vehicle will be between $x_{min}\left(t_1\right)$ and $x_{max}\left(t_1\right)$ at time $t_1$. If the driver chooses to overtake the vehicle in the left lane, the host vehicle should enter the left lane before time $t_c$, and the longitudinal position of the host vehicle should be greater than $x_c$ at $t_c$, and $x_{max}\left(t_1\right)>x_c$ needs to be satisfied. The host vehicle moves at the required minimum longitudinal acceleration to overtake the left vehicle, as shown by the solid red line in Figure 9. If the driver chooses to follow the vehicle in the left lane, the longitudinal position of the host vehicle should be smaller than the left vehicle when the host vehicle enters the left lane. Therefore, the solid red line in Figure 9 represents the longitudinal motion when the host vehicle moves at maximum longitudinal acceleration to follow the left vehicle.

4.2. Evaluation of Remaining Driving Maneuvers

After the unreasonable candidate maneuvers are eliminated, the remaining candidate maneuvers are evaluated. An algorithm is proposed to evaluate the feasibility of the driving maneuver, as shown in Algorithm 1. If the current situation does not meet the requirements of the safe lane-change maneuver, the algorithm evaluates whether the constraints can be met by accelerating or decelerating. The sub-optimal speed adjustment solution $S_i$ with the longitudinal acceleration range $\left[a_{min,i},a_{max,i}\right]$, the feasible interval of time $\left[t_{min,i},t_{max,i}\right]$, and the cost $J_i$ for each driving maneuver $c_i$ is obtained. Therefore, the optimal driving maneuver with the lowest cost and the speed adjustment solution can be achieved.

Algorithm 1 Maneuver evaluation

Input: Candidate maneuvers $c_i\in C,i\in \left\{1,2,\dots \right\}$, state $X\left(0\right)$

Output:  Speed adjustment solution set $S_i$, longitudinal acceleration range $\left[a_{min,i},a_{max,i}\right]$, initiating time interval $\left[t_{min,i},t_{max,i}\right]$, cost $J_i$ for each corridor $c_i$

1: $Init:$set${\mathbf{S}}_i\leftarrow \varnothing$   2: for each $c_i$ do   3:     for each $a_j$ do, $a_j\in \left[a_{min},a_{max}\right]$   4:         for each $t_k$ do, $t_k\in \left[0,T\right]$   5:            ${\mathbf{X}}_{i,j,k}$←State-prediction($\mathbf{X}\left(\mathbf{0}\right)$)   6:            ${\mathbf{M}}_{i,j,k}$←CalcSafeDistance(${\mathbf{X}}_{i,j,k}$)   7:            if host vehicle is in $M_{i,j,k}$ then   8:                $\left\{P_{i,j}\right\}\leftarrow \left\{P_{i,j}\right\}\cup s$   9:            end if 10:         end for 11:         if $t_2-t_1<\Delta t_{threshold}$ then 12:            $\left\{P_{i,j}\right\}\leftarrow \left\{P_{i,j}\right\}\backslash P_{i,j}$ 13:         end if 14:         ${\mathbf{S}}_{ij}\leftarrow {\mathbf{S}}_{ij}\cup \left\{P_{i,j}\right\}$ 15:     end for 16:     ${\mathbf{S}}_i\leftarrow {\mathbf{S}}_i\cup \left\{S_{ij}\right\}$ 17:     ${\mathbf{J}}_i$←CalcCost(${\mathbf{S}}_{\mathbf{i}}$) 18: end for 19: return${\mathbf{S}}_i$, $J_i$

A cost function is designed to compare the solutions to each driving maneuver. The goal of optimization is to achieve a balance among the lane-change starting time, longitudinal acceleration, and gap with other vehicles. For the lane-change maneuver, we consider the following min–max problem with the parameters $a_m$, $t_{adj}$, and $P_{lc}$, where $a_m$ is the longitudinal acceleration for speed adjustment; $t_{adj}$ is the lane-change starting time; and $P_{lc}$ is the penalty, which reflects the gap with other vehicles. We obtain the earliest safe initiating time $t_1$ and the last safe initiating time $t_2$ for each $a_m$. To ensure that the driver has ample operation time to prepare for the lane-change maneuver, the time interval between $t_1$ and $t_2$ should be no less than $\Delta t_{threshold}$ if the driver has not initiated the lane-change maneuver.

$$\underset{a_m\in A,t_{adj}\in T}{min}J(a_m,t_{adj},P_{lc})$$

(10a)

$$s.t.J_{lc}(a_m,t_{adj},P_{lc})={\lambda }_0{a}_m^2+{\lambda }_1{t}_{{}_{adj}}^2+{\lambda }_2{P}_{lc}^2$$

(10b)

$$P_{lc}=max({\omega }_i·a_{r,brake,i})$$

(10c)

$$v\in \left[v_{min},v_{max}\right]$$

(10d)

$$s_m\in \left[s_{min},s_{max}\right]$$

(10e)

$$a_m\in \left[a_{min},a_{max}\right]$$

(10f)

$$t_{adj}\in \left[0,T\right]$$

(10g)

$$s_{max}=min\left(s_{L0}-\epsilon ,D_{2,Ld},D_{2,L0}\right)$$

(10h)

$$s_{min}=max\left(s_{F0}+\epsilon ,D_{2,Fd},D_{2,F0}\right)$$

(10i)

$$t_2-t_1\ge \Delta t_{threshold}$$

(10j)

For each pair of host vehicle and safe-related traffic vehicle ($F_0$, $F_d$, $L_d$, and $L_0$), we calculated the safe acceleration-related indicator to reflect the degree of safety. Assuming the distance at critical times $t_{c,Fd}$, $t_{c,Ld}$, $t_{c,F0}$, and $t_{c,L0}$ between the two vehicles before braking is d, the front vehicle brakes at acceleration $a_{f,brake,max}$, and the rear vehicle moves at acceleration $a_r$ during the reaction time $\left[0,\delta \right]$ and then starts to brake at $a_{r,brake}$ to ensure no collision occurs. The minimum required deceleration $a_{r,brake}$ for the rear vehicle can be obtained.

$$a_{r,brake}=\frac{{\left(v_r+a_r\delta \right)}^2}{2\times \left(d+\frac{v_f^2}{2a_{f,brake,max}}-v_r\delta -\frac{1}{2}{a}_r{\delta }^2\right)}$$

(11)

For the rear vehicle, the smaller required $a_{r,brake}$ means that it is safer. Based on the distance from host vehicle to $F_0$, $F_d$, $L_d$, and $L_0$ during the lane-change process, $a_{r,brake}$ can be derived. The cost $J_{lc}$ for each lane-change maneuver can be obtained. For the lane-keeping maneuver, the cost can be defined as presented below, where $a_{r,brake,L0}$ is computed based on the distance from the front vehicle $L_0$.

$$J_{keep}={\lambda }_3{a}_{r,brake,L0}^2$$

(12)

5. Experiments and Discussion

5.1. Driving Maneuver Evaluation before Lane-Change Process

To validate the proposed algorithm in traffic scenarios, simulation experiments were conducted using the Prescan simulation environment [27]. The traffic participants move at a constant speed. The red vehicle is the host vehicle, which drives forward along the right lane. The three decision-level driving maneuvers are shown in Figure 10.

The host vehicle may implement an aggressive maneuver of speeding up and then initiate a lane-change maneuver for corridor 1. Alternatively, the vehicle may implement a passive maneuver of waiting until there is enough space for corridor 2. For corridor 3, the host vehicle follows the front vehicle in lane-keeping mode. The parameters for simulation are shown in

Table 2. The simulation configuration.

Parameter	Value
The initial velocity of the host vehicle	40 km/h
The velocity of other vehicles on the right lane	30 km/h
The velocity of other vehicles on the left lane	36 km/h
Threshold $\Delta t_{threshold}$	2 s
$a_{max,lon}$	3 m/s${}^2$
$a_{min,lon}$	−4 m/s${}^2$
$v_{max,lon}$	100 km/h
$v_{min,lon}$	0 km/h
$t_{lat}$	5 s

.

The feasibility of each driving maneuver is evaluated. The cost, speed adjustment solution, and suggested time to initiate lane- change maneuver are obtained during the process of driving forward. When the safety constraints are satisfied, the algorithm provides a signal that suggests initiating a lane-change maneuver. The code is implemented in C++ using Intel I7-10750 cpu running at 3.9 GHz, the average total time used is about 5 ms.

(a) $a_{lon}$ = 0

Figure 11 shows the simulation results of the host vehicle moving forward at constant velocity.

In Figure 11a,b the solid red line represents the maximum safe longitudinal acceleration, the dashed blue line represents the minimum safe longitudinal acceleration, and the solid green line represents the recommended longitudinal acceleration with the lowest cost. In Figure 11c, the solid blue line represents the required minimum longitudinal deceleration for lane keeping. In Figure 11d, the dashed red line represents the cost for corridor 1, and the blue line represents the cost for corridor 2. In Figure 11e, when the signal is 1, it means that the driver can perform a lane-change maneuver safely. As shown in Figure 11a, for corridor 1, the recommended acceleration is about 1 m/s${}^2$ from the beginning to 3.8 s. The velocity of the left lane is greater than that of the right lane, the gap for changing lane decreases, and the cost increases gradually. After 3.8 s, the cost for corridor 1 becomes a large value, and lane-change is infeasible. As shown in Figure 11b, for corridor 2, the recommended acceleration is initially about −2 m/s${}^2$, and then it increases gradually. Corridor 2 is feasible if the host vehicle can slow down and obtain enough space to change lane. Figure 11e shows that during the whole process, the lane-change maneuver is not recommended under the current velocity. For corridor 3, the speed of the host vehicle is greater than that of the front vehicle. As the host vehicle approaches the vehicle in front of it, the required deceleration increases.

(b) $a_{lon}$ = −2.5 m/s${}^2$

Figure 12 shows the simulation results when the host vehicle moves forward at a constant acceleration of −2.5 m/s${}^2$.

For corridor 1, as shown in Figure 12a, the algorithm suggests that the host vehicle should speed up. As the host vehicle decelerates, the cost for lane keeping in corridor 1 increases until corridor 1 is infeasible after 1.5 s, the cost of which is shown in Figure 12c. For corridor 2, the algorithm recommends that the vehicle should slow down to gain enough space for a lane-change. From 2 to 2.7 s, the host vehicle can start changing lane (Figure 12b). Within the simulation time, the lane-change maneuver is advised from 2 to 2.7 s (Figure 12e). For corridor 3, the required deceleration decreases as the host vehicle moves forward.

(c) $a_{lon}$ = 2 m/s${}^2$

Figure 13 shows the simulation results when the host vehicle moves forward at a constant acceleration of 2 m/s${}^2$.

For corridor 1, as shown in Figure 13a, the algorithm suggests that the host vehicle should accelerate with a small acceleration from the beginning to 0.7 s. Then, the space to front vehicle decreases, the algorithm suggests that the vehicle should decelerate to maintain safe distance to the front vehicle until 1.4 s. After 1.4 s, the safety constraints to initiate a lane-change maneuver are not satisfied, and corridor 1 is infeasible (Figure 13d). From 0.7 s to 1.4 s, the host vehicle is recommended to perform a lane-change maneuver for corridor 1, as shown in Figure 13e. For corridor 2, the algorithm suggests that the host vehicle should decelerate until the lane-change maneuver is infeasible after 1.4 s (Figure 13b). After 1.4 s, safety constraints to initiate a lane-change maneuver for corridor 2 are not satisfied. For corridor 3, the required deceleration increases as the host vehicle accelerates (Figure 13c).

5.2. Driving Maneuver Evaluation during the Lane-Change Process

In this paper, a simulation experiment is carried out to evaluate the candidate driving maneuvers during the lane-change process. As shown in Figure 14, the host vehicle crosses the lane line towards the left lane. The parameters for the simulation are shown in

Table 3. The simulation configuration.

Parameter	Value
The initial velocity of the host vehicle	36 km/h
The velocity of other vehicles in the right lane	36 km/h
The velocity of other vehicles in the left lane	54 km/h
$a_{max,lon}$	3 m/s${}^2$
$a_{min,lon}$	−4 m/s${}^2$
$v_{max,lon}$	100 km/h
$v_{min,lon}$	0 km/h
$t_{lat}$	5 s

.

The speed of the vehicles in the left lane is higher than that of the vehicles in the right lane. The host vehicle crosses the lane line. The other traffic participants move at a constant speed. The host vehicle has two candidate driving maneuvers, including continuing lane change and canceling lane change. The proposed maneuver evaluation algorithm can evaluate the feasibility of the two driving maneuvers. The code is implemented in C++ using Intel I7-10750 cpu running at 3.9 GHz, the average total time used is about 5 ms.

Figure 15 and Figure 16 show the simulation results at 0.65 and 0.95 s when the host vehicle moves forward at a constant speed. In Figure 15a,b and Figure 16a,b, the solid red line represents the maximum safe longitudinal acceleration, the dashed blue line represents the minimum safe longitudinal acceleration, and the solid green line represents the recommended longitudinal acceleration with the lowest cost. In Figure 15c and Figure 16c, the solid blue line represents the cost of canceling lane change, and the dashed red line represents the cost of continuing lane change.

As shown in Figure 15a, since the speed of the vehicles in the left lane is higher than that of the host vehicle, if the host vehicle continues to change lanes, the algorithm suggests that the vehicle should accelerate. The maximum acceleration is constrained by the motion limitation and the safe distance to the front vehicle in both lanes. As shown in Figure 15b, for the canceling lane-change driving maneuver, since the speed of the rear vehicle in the left lane is higher, the minimum required acceleration increases as the rear vehicle approaches. As shown in Figure 15c, both canceling and continuing lane change are feasible before 0.65 s, and the cost of canceling lane change is lower than that of continuing lane change.

As shown in Figure 16c, the continuing lane-change maneuver is infeasible after 0.7 s since the rear vehicle is too close, and it is too late for the host vehicle to speed up to continue lane-change. The canceling lane-change maneuver is infeasible after 0.8 s since the rear vehicle is too close. At 0.7 s, the $t_{adj}$ for adjusting the heading angle to be parallel to the lane line is 0.89 s, and the time $t_{c,Fd}$ for the lane-change motion model to arrive at the critical lateral position is 1.6 s. Therefore, the total required time is about 2.5 s for the host vehicle to avoid the restriction of the rear vehicle. The scene of the critical position to avoid the rear vehicle is shown in Figure 8b. The velocity of the left rear vehicle is higher than that of the host vehicle. Since the acceleration of the host vehicle is limited, at 0.7 s, the longitudinal distance between the host vehicle and the left rear vehicle is not sufficient to at the position shown in Figure 8b. It is not safe to cancel lane change in the predefined range of acceleration.

6. Conclusions

In this paper, a maneuver evaluation algorithm for lane-change assistance system is proposed. According to the relative position of surrounding vehicles in the lane frame, the candidate driving corridors at the decision level are obtained. The computing efficiency is improved by eliminating the inappropriate driving maneuvers according to the limitation of motion and the basic spatial-temporal constraints. The remaining candidate driving maneuvers corresponding to the driving corridors are quantified and evaluated. A function for quantifying the driving maneuvers is proposed. The hard constraint of safety distance combined with the soft constraint that suggests that the vehicle should not interfere with the normal driving of other vehicles is taken into consideration. The proposed algorithm is validated via simulation environments in the Prescan. The experimental results show the ability of the proposed algorithm to efficiently analyze the safety of candidate driving maneuvers and evaluate the cost of each candidate driving maneuver. Suggestions regarding the speed adjustment strategy and lane-change timing for the lane-change maneuver are provided. For the tested scenarios, the average computation time is about 5 ms. The method proposed in this paper can be used in real-time applications. In future work, we will continue to study decision-making in more complex traffic scenarios.