Path generation algorithm for automated lane centering and lane changing control system

[0001] 1. Field of the Invention

[0002] This invention relates generally to a system and method for providing path generation for lane centering and lane changes in an autonomously driven vehicle and, more particularly, to a system and method for providing path generation for lane centering and lane changing in an autonomously driven vehicle that considers vehicle motion control.

[0003] 2. Discussion of the Related Art

[0004] The operation of modern vehicles is becoming more autonomous, i.e., the vehicles are able to provide driving control with less and less driver intervention. Cruise control systems have been on vehicles for a number of years where the vehicle operator can set a particular speed of the vehicle, and the vehicle will maintain that speed without the driver operating the throttle. Adaptive cruise control systems have been recently developed in the art where not only does the system maintain the set speed, but also will automatically slow the vehicle down in the event that a slower moving preceding vehicle is detected using various sensors, such as radar and cameras. Certain modern vehicles also provide autonomous parking where the vehicle will automatically provide the steering control for parking the vehicle. Some vehicle systems intervene if the driver makes harsh steering changes that may affect vehicle stability. Some vehicle systems attempt to maintain the vehicle near the center of a lane on the road. Further, fully autonomous vehicles have been demonstrated that can drive in simulated urban traffic up to 30 mph, observing all of the rules of the road.

[0005] As vehicle systems improve, they will become more autonomous with the goal being a completely autonomously driven vehicle. For example, future vehicles probably will employ autonomous systems for lane changing, passing, turns away from traffic, turns into traffic, etc. As these systems become more prevalent in vehicle technology, it will also be necessary to determine what the drivers role will be in combination with these systems for controlling vehicle speed and steering, and overriding the autonomous system.

[0006] Smooth maneuvering and automated lane centering and lane changing control is important for driver and passenger comfort in autonomous vehicles. However, as a result of sensor and actuator latency, measured vehicle states may be different from actual vehicle states. This difference may cause improper path generation, which will affect lane changing harshness. Therefore, what is needed is a system and method for providing smooth maneuvering for lane centering and lane changing in an autonomous or semi-autonomous vehicle that is directed towards passenger comfort.

[0007] In accordance with the teachings of the present invention, a system and method are disclosed for providing path generation for lane centering and/or lane changing purposes in an autonomous or semi-autonomous vehicle. The path generation system includes a desired path generation processor that receives signals detecting the roadway on which the vehicle is traveling, a request for a lane change and a steering angle of the vehicle. The system also includes a path prediction processor that predicts the vehicle path for the next few seconds of time based on vehicle state information including vehicle longitudinal speed, vehicle lateral speed, vehicle yaw-rate vehicle steering angle. The desired path information and the predicted path information are compared to generate an error signal that is sent to a lane change adaptive cruise control (LXACC) system that provides a steering angle signal to turn the vehicle and reduce the error signal. The steering angle signal is sent to a vehicle steering control sub-system that steers the vehicle, and provides measurements of vehicle states that are used by the path prediction processor. In one embodiment, the desired path generation processor uses a fifth order polynomial equation to determine the desired path of the vehicle based on the inputs.

[0008] Additional features of the present invention will become apparent from the following description and appended claims, taken in conjunction with the accompanying drawings.

[0016] The following discussion of the embodiments of the invention directed to a system and method for providing path generation for smooth lane centering or lane changing in an autonomous or semi-autonomous vehicle is merely exemplary in nature, and is in no way intended to limit the invention or its applications or uses.

[0017] FIG. 1 is an illustration of a vehicle system 10 including an LXACC core algorithm 12 that includes path generation, as will be discussed in detail below. Known LXACC systems provide a unified framework for automated lateral motion controls, such as automated lane changing and lane centering functions. Because the lateral dynamics of a vehicle is related to its longitudinal motion, the longitudinal motion control is usually considered in the same framework.

[0018] The system 10 includes various cameras 14 and various radar devices 16 that detect lane marks and objects. This information is provided to a lane and object detection processor 18 that combines the detected objects and lane information. The lane and object detection information is provided to the LXACC core algorithm 12. Additionally, vehicle state estimation information at box 22 is also provided to the LXACC core algorithm 12, such as vehicle yaw rate, vehicle heading angle, vehicle speed, etc. Human machine interface (HMI)/driver control inputs at box 24 are provided to the LXACC core algorithm 12 for providing driver commands. Signals from an adaptive cruise control (ACC) sub-system 26 are provided to the LXACC core algorithm 12 and signals from the LXACC core algorithm 12 are provided to the ACC sub-system 26. The ACC sub-system 26 provides adaptive cruise control signals to a vehicle longitudinal controller 28 that in turn controls vehicle braking and throttle at box 30.

[0019] The LXACC core algorithm 12 includes a desired path generation processor 36 that generates a desired vehicle path, and is the subject of the present invention, as will be discussed in detail below. The LXACC core algorithm 12 also includes a vehicle path estimation and prediction processor 38 that estimates a vehicle path. Signals from the processors 36 and 38 are provided to lane centering control at box 40 and lane changing control at box 42. The vehicle control signals from the LXACC core algorithm 12 are provided to a vehicle lateral motion controller 44 that controls an active front steering (AFS) or electrical power steering (EPS) at box 46. Further, the lane centering control and lane changing control signals are provided to an HMI controller and logistics manager 48 to inform the driver of the LXACC status using a display unit, haptic seat or warning chimes at box 50.

[0020] The path planning produces an achievable desired path for smooth lane changing maneuvers. The motion controller uses the predicted lateral offsets and vehicle heading angles, and compares them with the desired trajectory at multiple look-ahead points. The controller generates the steering angle command at each time step. A forward vision camera is used for the lane mark detection. The lateral offset and the vehicles heading angle with respect to the current lane are obtained by processing the lane marks recognized, and further predicted over the pre-defined lane change operation time. Several inertial sensors, such as rate gyros and accelerometers, can be combined with the vision camera to estimate the vehicles motion states, such as yaw-rate and lateral speed, as well as to improve the estimation of the lateral offset and the heading angle.

[0021] The smoothness of the lateral motion is one important measure of the LXACC core algorithm 12 performance. The path-planning function generates the desired paths. The paths should satisfy the vehicles dynamic capability and be smooth. The design consideration proposed herein is to generate the desired path without an abrupt change in the sense of the vehicles second order dynamic motion. Further complication in the path planning is that the vehicle will reach the target state from any initial state. There are many approaches in the literature to solve this problem, which are based on different assumptions about the hardware and the environment.

[0022] FIG. 2 is a schematic block diagram of an LXACC system 60 that provides a desired path for the vehicle to follow when changing lanes, either on a straight road or a curved road, and that provides lane centering in an autonomous or semi-autonomous vehicle system, such as the system 10 shown in FIG. 1. The system 60 includes a desired path generation processor 62 that receives a driver's request for lane change from, for example, the inputs from the box 24 in FIG. 1. As will be discussed in detail below, the desired path generation processor 62 generates a smooth path for the vehicle when turning that does not have abrupt changes that would otherwise provide passenger discomfort. The system 60 produces a steering angle command to guide the vehicle along the generated path.

[0023] The desired path is represented as a series of lateral offsets, heading angles and longitudinal distances over a time period that the lane change will take place. This path information is provided to a comparator 64 that receives a signal from a path prediction processor 66 and provides an error signal between the desired path and the predicted path. The error signal is applied to a lane change controller 68 that provides a steering angle command signal δ_cmd for the lane change. The lane change controller 68 generates a sequence of future steering angle commands that minimize the orientation and offset errors between the vehicles desired path and the predicted vehicle path.

[0024] The steering angle command signal δ_cmd is then sent to a steering controller 70 that provide the steering control signal to a vehicle steering system 54 on a vehicle 52. As the vehicle turns, various sensors 56 on the vehicle, such as a steering angle sensor, speedometer and yaw rate sensor, provide measured signals of the vehicle motion. These measured vehicle motion signals δ_meas are sent back to the desired path generation processor 62. The vehicle 54 also includes vision devices 58, such as cameras. The vehicle motion information is provided to a vehicle state estimation processor 72 that provides estimated vehicle state signals, namely, vehicle longitudinal speed, vehicle lateral speed and vehicle yaw-rate. The vehicle state estimation processor 72 uses a vehicle model to filter the estimated vehicle state signals. The state signals are sent to the path prediction processor 66 that will be able to predict the vehicle path for the next few instances in time based on that information. The path prediction processor 66 estimates the vehicle future path based on the current vehicle speed, yaw-rate and steering angle.

[0025] The camera signals from the vision devices 58 and the filtered sensor signals from the processor 72 are provided to a lane mark detection processor 74 that corrects the parameters of the lane markings from the devices 58 based on the motion of the vehicle. The lane mark detection processor 74 recognizes the lane marking and represents them with the parameters of lane curvature, tangential angle and lateral offset, where the output of the lane marked detection processor 74 is a heading angle and curvature of the road. The position of the lane markings relative to the vehicle is then sent to desired path generation processor 62 to provide the desired path generation updating. The path generation processor 62 generates a smooth desired path for a lane change according to the vehicle dynamics and the detected lane marks.

[0026] FIG. 3 is an illustration of a vehicle 80 traveling on a roadway 82 showing a detected lane center 84 that is identified by the vehicle cameras and other sensors, and a predicted lane center 86 that is generated by the path prediction processor 66. The latency of the detector and the steering actuator causes a discrepancy between the measured vehicle states and the actual vehicle states. The following discussion provides a description as to how the path prediction processor 66 predicts the path of the vehicle, and then how that predicted path is used to generate the error signal between the predicted path 86 and the detected lane center 84, as discussed above.

[0027] There are certain situations where multiple paths need to be predicted if an obstacle, such as another vehicle, is detected in the path of the vehicle 80. The present invention treats that situation in multiple segments where a first segment is from the vehicle 80 to the obstacle and a second segment is from the obstacle and beyond. The present invention provides continuity between the segments to avoid abrupt changes in vehicle motion.

[0028] According to one embodiment of the present invention, the path generation processor 62 generates the desired path based on the predicted lane center, and uses a fifth order polynomial equation, as will be discussed in detail below. The fifth order polynomial equation has six unknowns at the beginning of the process for calculating the desired path. The normalized path problem is independent of the vehicle states, where the vehicle states will be used at the stage of the coordinate conversion for normalized coordinates to vehicle coordinates. The continuity requirement for the segment can be easily accommodated into the algorithm when multiple segments need to be concatenated.

[0029] The vehicle 80 is equipped with a forward vision camera that detects lane marks of the roadway 82 and represents the lane marks in polynomial equations. The vision system is responsible for recovering estimates of the position and orientation of the lane with respect to the center of the vehicle. FIG. 4 shows the vehicle 80 traveling on a curve 90 of a roadway 92. The roadway 92 is modeled as two segments of second order polynomial equations as:
y_seg1(x)=A₁x²+B₁x+C₁, 0<x<x₁  (1)
y_seg2(x)=A₂x²+B₂x+C₂, 0<x<x₂  (2)
Where x₁ and x₂ represent the end points along the x-axis of the first segment and the second segment y_seg1 and y_seg2 represents the lateral offset of the roadway with respect to the vehicle coordinate system R_v(t). The measurements provided by the vision system include yaw angle φ_r,1 of the vehicle 80 with respect to the first segment of the roadway, lateral offset y_r,1 of the vehicle's center of gravity from the lane, and roadway curvature ρ₁ and ρ₂ of the first segment and the second segment.

[0030] From the geometric relationship between roadway and the lane representation, the coefficients of equations (1) and (2) can be related as:

[0031] $\begin{array}{cc}{A}_1=\frac{{\rho }_1}{2}& \left(3\right)\\ A_2=\frac{{\rho }_2}{2}& \left(4\right)\\ B_1=\tan {\phi }_1& \left(5\right)\\ C_1=y_{r,1}& \left(6\right)\end{array}$

[0032] It is assumed that the roadway runs without discontinuity, that is, the two segments of each road representation connect smoothly without an abrupt change at the transition point x₁. Only the zeroth and first order continuity are assumed herein, so equations (7) and (8) below hold at the transition point x₁.

[0033] $\begin{array}{cc}{y}_{\mathrm{seg}1}\left(x_1\right)=y_{\mathrm{seg}2}\left(x_1\right)& \left(7\right)\\ {{\frac{d{y}_{\mathrm{seg}1}}{dx}}_{x=x1}=\frac{d{y}_{\mathrm{seg}2}}{dx}}_{x=x1}& \left(8\right)\end{array}$

[0034] Substituting equations (3)-(8) into equations (1) and (2) provides:
C₂=y_seg1(x₁)  (9)
B₁=2A₁x₁+B₁  (10)

[0035] By integrating equations (3)-(6), (9) and (10), equations (1) and (2) can be rewritten in terms of the measurements of the vision system as:

[0036] $\begin{array}{cc}\begin{array}{cc}{y}_{\mathrm{seg}1}\left(x\right)=\frac{{\rho }_1}{2}{x}^2+\tan \left({\phi }_1\right)x+y_{r,1},& 0<x<x_1\\ y_{\mathrm{seg}2}\left(x\right)=\frac{{\rho }_2}{2}{x}^2+\left({\rho }_1·x_1+\tan \left({\phi }_1\right)\right)x+y_{\mathrm{seg}1}\left(x_1\right),& x_1<x<x_2\end{array}& \begin{array}{c}\left(11\right)\\ \\ \left(12\right)\end{array}\end{array}$

[0037] Assuming that the vehicle 80 is running at a longitudinal speed v_x and there are no obstacles in the roadway, then the driver/passengers comfort depends on the vehicle's lateral acceleration a_y and the lateral acceleration a_y is a function of the vehicle speed v_x and the steering angle δ. A time variable t_LX is specified to complete a lane change maneuver independent of vehicle longitudinal speed unless the calculated lateral acceleration a_y is predicted to be over a certain limit during the lane change maneuvering. If the lateral acceleration a_y is over the limit, a new path is calculated with a new extended lane change maneuvering time.

[0038] The vehicle longitudinal speed v_x is measured by the vehicle speedometer, and the lateral offset, heading angle and roadway curvature ρ are measured by the forward vision system. The desired path generation is formulated for the lane change maneuvering as a boundary condition problem. Assume that the lane change control begins at t=0 and define (x(t),y(t)) as the vehicle position at time t with respect to the origin R_v(0) coordinate system.

[0039] FIG. 5 is an illustration of the vehicle 80 traveling on a roadway 94 around a curve 96, and identifies boundary conditions for the desired path generation. Note that the coordinates system R_v(0) is the vehicle coordinate system captured at time t=0 and the position and the heading angle of the vehicle 80 at t=0 are aligned with R_v(0). Thus (x(t=0, y(t=0))=(0,0) and y′(0)=0 can be set without loss of generality.

[0040] The initial and final states (y,y′,y″)_t=0 and (y,y′,y″)_t=tLX of the vehicle 80 can then be obtained by manipulating the roadway representation equations (11) and (12). The value (x(t_LX),y(t_LX)) corresponds to the desired position of the vehicle 80 at time t=t_LX, where x(t_LX) can be estimated by integrating the vehicle longitudinal speed v_x and the value y(t_LX) can be obtained by the lane width and the roadway geometry. Note that y_r in equations (3)-(6) represents the lateral offset of the roadway from the center of the vehicle 80, and here y represents the vehicle location with respect to R_v(0).

[0041] Selecting a fifth order polynomial equation for x and y positions of the vehicle 80 gives:
y(x)=a₅x⁵+a₄x⁴+a₃x³+a₂x²+a₁x+a₀  (13)

[0042] Considering the initial and final conditions gives:

[0043] $\begin{array}{cc}{\left(y\left(x\right),y^{\prime }\left(x\right),y^{″}\left(x\right)\right)}_{t=0}=(0,0,y_{\mathrm{seg}1}^{″}\left(x\left(0\right)\right)\mathrm{if}{x}_1<x\left(t_{\mathrm{LX}}\right)<x_2& \left(14\right)\\ {\left(y\left(x\right),y^{\prime }\left(x\right),y^{″}\left(x\right)\right)}_{t=t_{\mathrm{LX}}}=\left\{\begin{array}{cc}\left(y_{\mathrm{seg}1}\left(x\left(t_{\mathrm{LX}}\right)\right),y_{\mathrm{seg}1}^{\prime }\left(x\left(t_{\mathrm{LX}}\right)\right),y_{\mathrm{seg}1}^{″}\left(x\left(t_{\mathrm{LX}}\right)\right)\right),& \mathrm{if}0<x\left(t_{\mathrm{LX}}\right)<x_1\\ \left(y_{\mathrm{seg}2}\left(x\left(t_{\mathrm{LX}}\right)\right),y_{\mathrm{seg}2}^{\prime }\left(x\left(t_{\mathrm{LX}}\right)\right),y_{\mathrm{seg}2}^{″}\left(x\left(t_{\mathrm{LX}}\right)\right)\right),& \mathrm{if}{x}_1<x\left(t_{\mathrm{LX}}\right)<x_2\end{array}\right\}& \left(15\right)\end{array}$

[0044] The problem can be solved by the following linear equation:

[0045] $\begin{array}{cc}\left[\begin{array}{c}{a}_0\\ a_1\\ a_2\\ a_3\\ a_4\\ a_5\end{array}\right]={\left[\begin{array}{cccccc}1& x\left(0\right)& x^2\left(0\right)& x^3\left(0\right)& x^4\left(0\right)& x^5\left(0\right)\\ 0& 1& 2x\left(0\right)& 3x^2\left(0\right)& 4x^3\left(0\right)& 5x^4\left(0\right)\\ 0& 0& 2& 6x\left(0\right)& 12x^2\left(0\right)& 20x^3\left(0\right)\\ 1& x\left(t_{\mathrm{LX}}\right)& x^2\left(t_{\mathrm{LX}}\right)& x^3\left(t_{\mathrm{LX}}\right)& x^4\left(t_{\mathrm{LX}}\right)& x^5\left(t_{\mathrm{LX}}\right)\\ 0& 1& 2x\left(t_{\mathrm{LX}}\right)& 3x^2\left(t_{\mathrm{LX}}\right)& 4x^3\left(t_{\mathrm{LX}}\right)& 5x^4\left(t_{\mathrm{LX}}\right)\\ 0& 0& 0& 6x\left(t_{\mathrm{LX}}\right)& 12x^2\left(t_{\mathrm{LX}}\right)& 20x^3\left(t_{\mathrm{LX}}\right)\end{array}\right]}^{-1}\hspace{1em}\left[\begin{array}{c}y\left(x\left(0\right)\right)\\ y^{\prime }\left(x\left(0\right)\right)\\ y^{″}\left(x\left(0\right)\right)\\ y\left(x\left(t_{\mathrm{LX}}\right)\right)\\ y^{\prime }\left(x\left(t_{\mathrm{LX}}\right)\right)\\ y^{″}\left(x\left(t_{\mathrm{LX}}\right)\right)\end{array}\right]& \left(16\right)\end{array}$

[0046] The path generation problem can be simplified by normalization of the coordinate. Denoting the normalized coordinates as (x_n(t),y_n(t)) gives:

[0047] $\begin{array}{cc}{x}_n\left(t\right)=\frac{x\left(t\right)}{x\left(t_{\mathrm{LX}}\right)}& \left(17\right)\\ y_n\left(x\left(t\right)\right)=\frac{y\left(x\left(t\right)\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}& \left(18\right)\end{array}$

[0048] Substituting equations (17) and (18) into equation (13) and redefining the coefficients of the polynomial equation, y_n can be obtained by the following equation:

[0049] $\begin{array}{cc}{y}_n\left(x_n\right)=a_{n,5}{x}_n^5+a_{n,4}{x}_n^4+a_{n,3}{x}_n^3+a_{n,2}{x}_n^2+a_{n,1}{x}_n+a_{n,0}& \left(19\right)\end{array}$

[0050] Applying the normalized coordinates of equations (17) and (18) into the initial and final conditions, the normalized coordinates can be rewritten to the conditions as:

[0051] $\begin{array}{cc}{\left(y_n\left(x_n\right),{y^{\prime }\left(x_n\right)}_n,{y^{″}\left(x_n\right)}_n\right)}_{t=0}=\left(0,0,y_{\mathrm{seg}1}^{″}\left(x\left(0\right)\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(t_{\mathrm{LX}}\right)}\right)& \left(20\right)\\ {\left(y_n\left(x_n\right),{y^{\prime }\left(x_n\right)}_n,{y^{″}\left(x_n\right)}_n\right)}_{t=t_{\mathrm{LX}}}=\left\{\begin{array}{cc}\begin{array}{c}(1,y_{\mathrm{seg}1}^{\prime }\left(x\left(t_{\mathrm{LX}}\right)\right)·\frac{x\left(t_{\mathrm{LX}}\right)}{y\left(t_{\mathrm{LX}}\right)},\\ y_{\mathrm{seg}1}^{″}\left(x\left(t_{\mathrm{LX}}\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(t_{\mathrm{LX}}\right)}\right))\end{array},& \mathrm{if}0<x<x_1\\ \begin{array}{c}(1,y_{\mathrm{seg}2}^{\prime }\left(x\left(t_{\mathrm{LX}}\right)\right)·\frac{x\left(t_{\mathrm{LX}}\right)}{y\left(t_{\mathrm{LX}}\right)},\\ y_{\mathrm{seg}2}^{″}\left(x\left(t_{\mathrm{LX}}\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(t_{\mathrm{LX}}\right)}\right))\end{array},& \mathrm{if}{x}_1<x<x_2\end{array}\right\}& \left(21\right)\end{array}$

[0052] The linear equation problem of equation (16) can then be simplified as:

[0053] $\begin{array}{cc}\left[\begin{array}{c}{a}_{n,0}\\ a_{n,1}\\ a_{n,2}\\ a_{n,3}\\ a_{n,4}\\ a_{n,5}\end{array}\right]={\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 1& 1& 1& 1& 1& 1\\ 0& 1& 2& 3& 4& 5\\ 0& 0& 2& 6& 12& 20\end{array}\right]}^{-1}\left[\begin{array}{c}{y}_n\left(0\right)\\ y_n^{\prime }\left(0\right)\\ y_n^{″}\left(0\right)\\ y_n\left(1\right)\\ y_n^{\prime }\left(1\right)\\ y_n^{″}\left(1\right)\end{array}\right]& \left(22\right)\end{array}$

[0054] Note that the roadway conditions are captured only by the y-vector, and the matrix is a constant matrix regardless of the initial condition, the final condition or the road geometry. Therefore, the solution of equation (22) can be obtained by a few simple algebraic computations. Once the solution is calculated, equation (19) represents the desired path to complete the current lane change maneuvering in normalized coordinates. Applying equation (18) can yield the desired path profile in the vehicle coordinates.

[0055] Recall the initial position of the vehicle (x(t=0), y(t=0))=(0,0) and the initial heading angle y′(0)=0 because the vehicle motion is described by the vehicle coordinate system captured at t=0,R_v(0). In curved road cases, as shown in FIG. 5, the boundary conditions can be written as:
(y(x(0)) y′(x(0)) y″(x(0)))=(0 0 y″_seg(0))  (23)
(y(x(t_LX)) y′(x(t_LX)) y″(x(t_LX)))=y_seg(x(t_LX))+L y′_seg(x(t_LX)) y″_seg(x(t_LX)))  (24)
Where L is the lane width and x(t_LX) is the x-coordinate at time t_LX that corresponds to the longitudinal distance of travel to complete the lane change maneuvering. The value x(t_LX) can be estimated by integrating the vehicle speed v_x.

[0056] In normalized form, the initial and final conditions are:

[0057] $\begin{array}{cc}(y_n\left(x_n=0\right)y_n^{\prime }\left(x_n=0\right)y_n^{″}\left(x_n=0\right)=\left(00y_{\mathrm{seg}}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}\right)& \left(25\right)\\ (y_n\left(x_n=1\right)y_n^{\prime }\left(x_n=1\right)y_n^{″}\left(x_n=1\right)=\left(1y_{\mathrm{seg}}^{\prime }\left(x\left(t_{\mathrm{LX}}\right)\right)·\frac{x\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}{y}_{\mathrm{seg}}^{″}\left(x\left(t_{\mathrm{LX}}\right)\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}\right)& \left(26\right)\end{array}$

[0058] Substituting equations (25) and (26) into the linear equation (22) results in the following solution:

[0059] $\begin{array}{cc}{a}_{n,0}=a_{n,1}=0,a_{n,2}=0.5y_{\mathrm{seg}}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}& \left(27\right)\\ \left[\begin{array}{c}{a}_{n,3}\\ a_{n,4}\\ a_{n,5}\end{array}\right]={\left[\begin{array}{ccc}1& 1& 1\\ 3& 4& 5\\ 6& 12& 20\end{array}\right]}^{-1}\left[\begin{array}{c}{y}_n\left(1\right)-0.5y_{\mathrm{seg}}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}\\ y_n^{\prime }\left(1\right)-0.5y_{\mathrm{seg}}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}\\ y_n^{″}\left(1\right)-0.5y_{\mathrm{seg}}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}\end{array}\right]& \left(28\right)\end{array}$

[0060] As seen in equation (28), the first two coefficients of the polynomial equation are always zero. Further the rest of the coefficients can be calculated with a few algebraic computations with the boundary conditions.

[0061] For straight road cases, the path generation problem can be further simplified. FIG. 6 is an illustration of the vehicle 80 traveling in a lane 102 of a roadway 100 that is straight. The road curvature ρ is zero throughout the lane change maneuvering and the desired heading angle at the end of the lane change will be also zero. Thus, initial and final conditions are:
(y(x(0)) y′(x(0)) y″(x(0)))=(0 0 0)  (29)
(y(x(t_LX)) y′(x(t_LX)) y″(x(t_LX)))=(L 0 0)  (30)
Where L is the lane width.

[0062] In normalized form, the initial and final conditions can be written as:
(y_n(x_n=0) y′_n(x_n=0) y″_n(x_n=0)=(0 0 0)  (31)
(y_n(x_n=1) y′_n(x_n=1) y″_n(x_n=1)=(1 0 0)  (32)

[0063] Finally, substituting the conditions of equations (31) and (32) in the linear equation leads to the following solution:

[0064] $\begin{array}{cc}{a}_{n,0}=a_{n,1}=a_{n,2}=0& \left(33\right)\\ \left[\begin{array}{c}{a}_{n,3}\\ a_{n,4}\\ a_{n,5}\end{array}\right]={\left[\begin{array}{ccc}1& 1& 1\\ 3& 4& 5\\ 6& 12& 20\end{array}\right]}^{-1}\left[\begin{array}{c}{y}_n\left(1\right)\\ y_n^{\prime }\left(1\right)\\ y_n^{″}\left(1\right)\end{array}\right]=\left[\begin{array}{c}10\\ -15\\ 6\end{array}\right]& \left(34\right)\end{array}$

[0065] As seen in equation (34), the coefficients of the polynomial equation for the straight road are constant regardless of the lane change maneuvering distance, that is, the desired path is predetermined and no online computation is needed for the lane change maneuvering for straight road circumstances.

[0066] In the discussion above, it was assumed that the forward vision system can detect the lane marks far enough to cover the entire travel distance needed for the lane change maneuvering. This assumption may not be valid in certain cases, in particular, for high speed of vehicle motion or uneven road conditions. Considering these cases, the roadway can be extrapolated with the first order continuity assumption.

[0067] FIG. 7 illustrates the vehicle 80 traveling in a lane 104 of a roadway 106 showing the scenario where the range of the vision system is limited so that the vision system is not able to see the entire travel distance needed for the lane change maneuvering.

[0068] Recall the roadway representation of equations (11) and (12).

[0069] $\begin{array}{cc}\begin{array}{cc}{y}_{\mathrm{seg}1}\left(x\right)=\frac{{\rho }_1}{2}{x}^2+\tan \left({\phi }_1\right)x+y_{r,1},& 0<x<x_1\\ y_{\mathrm{seg}2}\left(x\right)=\frac{{\rho }_2}{2}{x}^2+\left({\rho }_1·x_1+\tan \left({\phi }_1\right)\right)x+y_{\mathrm{seg}1}\left(x_1\right),& x_1<x<x_2\end{array}& \begin{array}{c}\left(35\right)\\ \\ \left(36\right)\end{array}\end{array}$

[0070] The value x₂ is the end point of the second segment and corresponds to the range of the vision system. If x₂<x(t_LX), that is the range of the vision system is shorter than the distance needed for the current lane change maneuver, then the roadway measurement can be extrapolated from x₂ to x(t_LX) with the first order continuity assumption. Then, the roadway 106 can be represented by the following three equations:

[0071] $\begin{array}{cc}\begin{array}{cc}{y}_{\mathrm{seg}1}\left(x\right)=\frac{{\rho }_1}{2}{x}^2+\tan \left({\phi }_1\right)x+y_{r,1},& \mathrm{for}0<x<x_1\\ y_{\mathrm{seg}2}\left(x\right)=\frac{{\rho }_2}{2}{x}^2+\left({\rho }_1·x_1+\tan \left({\phi }_1\right)\right)x+y_{\mathrm{seg}1}\left(x_1\right),& \mathrm{for}{x}_1<x<x_2\\ y_{\mathrm{seg}3}\left(x\right)=y_{\mathrm{seg}}^{\prime }\left(x_2\right)·\left(x-x_2\right)+y_{\mathrm{seg}}\left(x_2\right),& \mathrm{for}{x}_2<x<x\left(t_{\mathrm{LX}}\right)\end{array}& \begin{array}{c}\left(37\right)\\ \\ \left(38\right)\\ \left(39\right)\end{array}\end{array}$

[0072] The first two segments are road representations based on the roadway measurement and the third segment is a virtual roadway extended with the continuity assumption. Considering the extended roadway representation, the initial and final conditions are obtained by:
(y(x(0)) y′(x(0)) y″(x(0)))=(0 0 y″_seg1(0)  (40)
(y(y(t_LX)) y′(x(t_LX)) y″(x(t_LX)))=(y′_seg(x₂)·(x(t_LX)−x₂)+y_seg2(x₂)+L y′_seg(x₂))0)  (41)

[0073] Normalized coordinates gives:

[0074] $\begin{array}{cc}\left(y_n\left(x_n=0\right)y_n^{\prime }\left(x_n=0\right)y_n^{″}\left(x_n=0\right)\right)=\left(00y_{\mathrm{sseg}1}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}\right)& \left(42\right)\\ \left(y_n\left(x_n=1\right)y_n^{\prime }\left(x_n=1\right)y_n^{″}\left(x_n=1\right)\right)=\left(1y_{\mathrm{sseg}2}^{″}\left(x_2\right)·\frac{x\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}0\right)& \left(43\right)\end{array}$

[0075] The polynomial coefficients of the desired path can be obtained by substituting the conditions of equations (42) and (43) into equation (28) as:

[0076] $\begin{array}{cc}{a}_{n,0}=a_{n,1}=a_{n,2}=0.5y_{\mathrm{seg}}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}& \left(44\right)\\ \left[\begin{array}{c}{a}_{n,3}\\ a_{n,4}\\ a_{n,5}\end{array}\right]={\left[\begin{array}{ccc}1& 1& 1\\ 3& 4& 5\\ 6& 12& 20\end{array}\right]}^{-1}\left[\begin{array}{c}{y}_n\left(1\right)-0.5y_{\mathrm{seg}}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}\\ y_n^{\prime }\left(1\right)-0.5y_{\mathrm{seg}}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}-\\ -0.5y_{\mathrm{seg}}^{″}\left(0\right)·\frac{x^2\left(t_{\mathrm{LX}}\right)}{y\left(x\left(t_{\mathrm{LX}}\right)\right)}\end{array}\right]& \left(45\right)\end{array}$

[0077] Note that the solution of the polynomial coefficients of equation (45) is obtained with the assumption of the first order continuity at the end, which means that the roadway is assumed as a straight road without a discontinuity after the sensor range. As the vehicle moves, the uncertainty of the roadway after the sensor range disappears and the path generated with the assumption is corrected corresponding to the detected roadway information.

[0078] The foregoing discussion discloses and describes merely exemplary embodiments of the present invention. One skilled in the art will readily recognize from such discussion and from the accompanying drawings and claims that various changes, modifications and variations can be made therein without departing from the spirit and scope of the invention as defined in the following claims.