# Patent

## Title
Method of path planning for evasive steering maneuver

## Abstract

A system and method for providing path planning and generation in a manually driven vehicle that provides a steering correction for collision avoidance purposes. The method includes determining a predicted path of the vehicle based on vehicle motion sensing data and vehicle parameters. The method also includes detecting a moving object in front of the vehicle and determining if a collision between the vehicle and the object will occur if the vehicle travels along the predicted path at the current vehicle speed. The method solves a fifth-order polynomial equation to define a collision avoidance path from the current vehicle position to a waypoint a safe distance from the object and a return path from the waypoint to the lane center that the vehicle is automatically steered along.

## Background
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to a system and method for providing path planning and generation in a manually driven vehicle and, more particularly, to a system and method for providing path planning and generation in a manually driven vehicle that includes changing the vehicle steering path in response to a detected moving object in front of the vehicle, where the object may be moving in either a transverse or longitudinal direction relative to the vehicle motion.
2. Discussion of the Related Art
The operation of modern vehicles is becoming more autonomous, i.e., 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 at 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.
As vehicle systems improve, they will become more autonomous with the goal being a complete autonomously driven vehicle. For example, future vehicles probably will employ autonomous systems for lane changing, passing, turns away from traffic, turns into traffic, etc. Smooth maneuvering and automated lane centering and lane changing control is important for driver and passenger comfort in autonomously driven 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.
U.S. Pat. No. 8,170,739 issued May 1, 2012, titled, Path Generation Algorithm for Automated Lane Centering and Lane Changing Control System, assigned to the assignee of this application and herein incorporated by reference, discloses a system for providing path generation for automated lane center and/or lane changing purposes. The system employs one or more forward-looking cameras that detect lane markings in front of the vehicle for identifying a travel lane on which the vehicle is traveling. A desired path generation processor receives the signals from the camera, vehicle state information and a steering angle of the vehicle, and a request for a vehicle lane change. The system also includes a path prediction processor that predicts the vehicle path based on the vehicle state information including vehicle longitudinal speed, vehicle lateral speed, vehicle yaw-rate and 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 controller that provides a steering angle signal to turn the vehicle and reduce the error signal, where the path generation processor employs a fifth-order polynomial equation to determine the desired path of the vehicle based on the input signals.
U.S. Patent Application Publication No. 2010/0082195 to Lee et al., titled, Method to Adaptively Control Vehicle Operation Using an Autonomic Vehicle Control System, assigned to the assignee of this application and also herein incorporated by reference, discloses improvements to the path generation algorithm disclosed in the '739 patent that includes determining a preferred travel path for the vehicle based on a predicted travel path and an estimated roadway position.
Both the '739 patent and the '195 application do not provide desired path generation and automatic vehicle steering in a semi-autonomous or autonomously driven vehicle for collision avoidance purposes if a moving object is detected in front of the vehicle.
SUMMARY OF THE INVENTION
The present disclosure describes a system and method for providing path planning and generation in a manually driven vehicle that provides a steering correction for collision avoidance purposes. The method includes determining a predicted path of the vehicle based on vehicle motion sensing data and vehicle parameters. The method also includes detecting a moving object in front of the vehicle and determining if a collision between the vehicle and the object will occur if the vehicle travels along the predicted path at the current vehicle speed. The method determines whether vehicle braking alone will prevent the collision with the object if it is determined that the collision will occur and if not, determines a steering path around the object. The method determines if the moving object is traveling in a transverse or longitudinal direction relative to the vehicle path, and if the object is moving in a transverse direction, the method solves a fifth-order polynomial equation to define a collision avoidance path from the current vehicle position to a waypoint a safe distance from the object and a return path from the waypoint to the lane center that the vehicle is automatically steered along. If the object is moving in a longitudinal direction, the method determines the collision avoidance path to the waypoint then a cruise path adjacent to the object, and then the return path back to the lane center.
Additional features of the present invention will become apparent from the following description and appended claims, taken in conjunction with the accompanying drawings.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is an illustration of a vehicle including components necessary for providing path prediction and generation in a semi-autonomous or autonomously driven vehicle;
FIG. 2 is a block diagram of a path prediction and generation system;
FIG. 3 is an illustration of a vehicle traveling on a roadway including a transverse moving object in front of a vehicle;
FIG. 4 is an illustration of a vehicle traveling on a roadway including a longitudinal moving object in front of a vehicle;
FIG. 5 is an illustration of a vehicle traveling on a roadway showing a predicted vehicle path;
FIG. 6 is an illustration of vehicle motion model; and
FIG. 7 is a flow chart diagram showing a process for evading a moving object.



DETAILED DESCRIPTION OF THE EMBODIMENTS
The following discussion of the embodiments of the invention directed to a system and method for providing path planning and generation and collision avoidance with a moving object in a manually driven vehicle is merely exemplary in nature, and is in no way intended to limit the invention or its applications or uses.
FIG. 1 is an illustration of a vehicle 10 including a controller 12 that performs all of the necessary processes, calculations, algorithms, etc. discussed herein to provide path prediction, generation and control of the vehicle 10 driven in a semi-autonomous or autonomous manner, where the controller 12 can be any number of independent or combined processors, electronic control units (ECUs), devices, etc. The controller 12 receives signals from one or more forward looking vision cameras 14 that detect lane markings and objects on or in the roadway or otherwise in front of the vehicle 10, where the camera 14 can be any suitable detection device for this purpose, such as a charge-coupled device (CCD) camera, complementary metal oxide semiconductor (CMOS) video image sensors, etc. The vehicle 10 also includes a number of sensors, represented generally as sensor 16, that provides vehicle motion information including, but not limited to, vehicle speed, yaw-rate, steering angle, lateral and longitudinal acceleration, lateral and longitudinal speed, etc. The vehicle 10 further includes a GPS receiver 18 that receives GPS signals identifying the location of the vehicle 10, which are provided to a map database 20 that provides an indication to the controller 12 of the location of the vehicle 10 on the roadway, for example, as spaced apart roadway points. The vehicle 10 also includes a sensor 22 representing any number of sensors, such as cameras, Lidar, radar, etc. that are able to detect objects in front of the vehicle 10. Based on the desired path of the vehicle 10 and whether the vehicle 10 is being semi-autonomously or autonomously driven, the controller 12 may provide output signals to a vehicle brake system 24, a vehicle throttle 26 and/or a vehicle steering system 28.
FIG. 2 is a general schematic block diagram of a lane changing and lane centering system 30 that provides a desired path for the vehicle 10 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. The system 30 includes a desired path generation processor 32 that may receive a driver's request for a lane change from box 34. The desired path prediction processor 32 also receives lane marking detection processor 36 provided by the camera 14 and object detection sensing at box 36 provided by the sensors 22. The lane mark detection processor 36 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 36 is a heading angle and curvature of the road. The desired path generation processor 32 generates a smooth path for the vehicle 10 when turning that does not have abrupt changes that would otherwise provide passenger discomfort.
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 40 that receives a signal from a path prediction processor 42 and provides an error signal between the desired path and the predicted path. The error signal is sent to a high-level lane change controller 44 and a low-level lane change controller 46 that provides a steering angle command signal δcmd for the lane change or lane centering. The lane change controllers 44 and 46 generate a sequence of future steering angle commands that minimize the orientation and offset errors between the vehicles desired path and the predicted vehicle path.
The steering angle command signal δcmd is then sent to a vehicle dynamics controller 48 that provides the steering control signal δcmd to the vehicle steering system 28 on the vehicle 10. As the vehicle 10 turns, the sensors 16 on the vehicle 10, such as a steering angle sensor, speedometer and yaw rate sensor, provide measured signals of the vehicle motion at box 50. The vehicle motion information is provided to a vehicle state estimation processor 52 that provides estimated vehicle state signals, namely, vehicle longitudinal speed, vehicle lateral speed and vehicle yaw-rate. The vehicle state estimation processor 52 uses a vehicle model to filter the estimated vehicle state signals. The state signals are sent to the path prediction processor 42 that will be able to predict the vehicle path for the next few instances in time based on that information. The path prediction processor 42 estimates the vehicle future path based on the current vehicle speed, yaw-rate and steering angle.
FIG. 3 is an illustration 60 of a vehicle 62 traveling on a lane 66 of a roadway 64 having an estimated lane center line 68 at the center of the lane 66 that has been determined by a lane center estimate algorithm from various sensing measurements, e.g., forward-looking camera and GPS/map database, where the roadway 64 also includes an adjacent lane 70 to the lane 66. The vehicle 62 is equipped with all of components necessary for path prediction and generation including a forward-looking vision camera that detects lane marks on the roadway 64, where a series of points along the lane 66 identify the desired position of the vehicle 62 at the camera sampling times as the vehicle 62 travels along or proximate the center line 68, and where the points are an average distance between markings at the right and left edge of the lane 66. It is noted that the position of the vehicle 62 is provided in vehicle coordinates as x, y, where x is the longitudinal direction relative to the vehicle heading and y is the lateral direction of the vehicle relative to the vehicle heading. It is desired that the desired path of the vehicle 62 be exactly overlapped with the lane center line 68. However, in reality, there would be a discrepancy between the desired path that the vehicle 62 needs to follow and the actual center of the lane 66. One reason for the discrepancy is that the initial vehicle position is not in the center of the lane and the moving direction of the vehicle 62 is not perfectly aligned with the lane center line 68. In the illustration 60, the vehicle 62 is traveling along a lane centering path 72, where the algorithm is attempting to center the vehicle 62 on the lane center line 68 so that the path 72 and the line 68 overlap and the vehicle 62 is in the center of the lane 66.
As mentioned above, the '739 patent employs a forward looking camera and a path prediction and generation algorithm, such as may be employed in the controller 12 and/or the system 30, to generate a desired vehicle path to maintain the vehicle 62 at the lane center and a path for lane changing purposes. The desired path is represented as a series of lateral offsets, heading angles and longitudinal distances over a certain time period. The controller 12 generates the desired path based on a predicted lane center using a fifth-order polynomial equation. 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 are used for coordinate conversion for normalized coordinates to vehicle coordinates. Continuity assumptions are employed in the algorithm for a smooth path and include the start position and the orientation angle of the desired path aligned with the current vehicle position and the vehicle moving direction, where a lane change path should finish at the center of the destination lane and align with the lane in the first and second order derivatives.
The process for determining the lane centering path 72 from the '739 patent is partially recreated below. The camera 14 provides estimates of the position and orientation of the lane 66 with respect to the center of the vehicle 62. In this embodiment, the roadway 64 is modeled as two sections of second-order polynomial equations as:

ysec1(x)=A1x2+B1x+C1, 0<x<x1,  (1)

ysec2(x)=A2x2+B2x+C2, x1<x<x2,  (2)

where x1 and x2 represent the end points along the x-axis of the first section and the second section and ysec1 and ysec2 represent the lateral offset of the roadway 64 with respect to the vehicle coordinate system Rv(t). The measurements provided by the camera 14 include yaw angle φr,1 of the vehicle 62 with respect to the first section of the roadway 64, lateral offset yr,1 of the vehicle's center of gravity from the lane 66, and roadway curvature ρ1 and ρ2 of the first section and the second section.

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




  
    
      
        
          
            A
            1
          
          =
          
            
              ρ
              1
            
            2
          
        
        ,
      
    
    
      
        (
        3
        )
      
    
  
  
    
      
        
          
            A
            2
          
          =
          
            
              ρ
              2
            
            2
          
        
        ,
      
    
    
      
        (
        4
        )
      
    
  




B1=tan φ1,  (5)

C1=yr,1.  (6)

It is assumed that the roadway 64 runs without discontinuity, that is, the two sections of each roadway representation connect smoothly without an abrupt change at the transition point x1. Only the zeroth and first order continuity are assumed herein, so equations (7) and (8) below hold at the transition point x1.

ysec1(x1)=ysec2(x1),  (7)





  
    
      
        
          
            
              d
              
                y
                
                  sec
                  ⁢
                  
                    
                  
                  ⁢
                  1
                
              
            
            
              d
              x
            
          
          ⁢
          
            |
            
              x
              =
              
                x
                ⁢
                
                  
                
                ⁢
                1
              
            
          
        
        =
        
          
            
              d
              
                y
                
                  sec
                  ⁢
                  
                    
                  
                  ⁢
                  2
                
              
            
            
              d
              x
            
          
          ⁢
          
            |
            
              x
              =
              
                x
                ⁢
                
                  
                
                ⁢
                1
              
            
          
          .
        
      
    
    
      
        (
        8
        )
      
    
  




Substituting equations (3)-(8) into equations (1) and (2) provides:

C2=ysec1(x1),  (9)

B1=2A1x1+B1.  (10)

By integrating equations (3)-(6), (9) and (10), equations (1) and (2) can be rewritten in terms of the measurements of the camera 14 as:




  
    
      
        
          
            
              y
              
                sec
                ⁢
                
                  
                
                ⁢
                1
              
            
            ⁡
            
              (
              x
              )
            
          
          =
          
            
              
                
                  ρ
                  1
                
                2
              
              ⁢
              
                x
                2
              
            
            +
            
              
                tan
                ⁡
                
                  (
                  
                    φ
                    1
                  
                  )
                
              
              ⁢
              x
            
            +
            
              y
              
                r
                ,
                1
              
            
          
        
        ,
        
          0
          <
          x
          <
          
            x
            1
          
        
      
    
    
      
        (
        11
        )
      
    
  
  
    
      
        
          
            y
            
              sec
              ⁢
              
                
              
              ⁢
              2
            
          
          ⁡
          
            (
            x
            )
          
        
        =
        
          
            
              
                
                  ρ
                  2
                
                2
              
              ⁢
              
                x
                2
              
            
            +
            
              
                (
                
                  
                    
                      ρ
                      1
                    
                    ·
                    
                      x
                      1
                    
                  
                  +
                  
                    tan
                    ⁡
                    
                      (
                      
                        φ
                        1
                      
                      )
                    
                  
                
                )
              
              ⁢
              x
            
            +
            
              
                
                  y
                  
                    seg
                    ⁢
                    
                      
                    
                    ⁢
                    1
                  
                
                ⁡
                
                  (
                  
                    x
                    1
                  
                  )
                
              
              .
              
                
              
              ⁢
              
                x
                1
              
            
          
          <
          x
          <
          
            x
            2
          
        
      
    
    
      
        (
        12
        )
      
    
  




Assuming that the vehicle 62 is operating at a longitudinal speed vx and there are no obstacles in the roadway 64, then the driver/passengers comfort depends on the vehicle's lateral acceleration ay and the lateral acceleration ay is a function of the vehicle speed vx and the steering angle δ. A time variable tLX is specified to complete a lane change maneuver independent of the vehicle longitudinal speed vx unless the calculated lateral acceleration ay is predicted to be over a certain limit during the lane change maneuver. If the lateral acceleration ay is over the limit, a new path is calculated with a new extended lane change maneuvering time.
The vehicle longitudinal speed vx is measured by the vehicle speedometer, and the lateral offset, heading angle and roadway curvature ρ are measured by the camera 14. The desired path generation is formulated for the lane change maneuver 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 Rv(0) of the coordinate system. Note that the coordinate system Rv is the vehicle coordinate system captured at time t=0 and the position and the heading angle of the vehicle 62 at t=0 are aligned with Rv(0). Thus, (x(t=0, y(t=0))=(0,0) and y′(0)=0 can be set without loss of generality.
The initial and final states (y,y′,y′′)t=0 and (y,y′,y′′)t=tLX of the vehicle 62 can then be obtained by manipulating the roadway representation equations (11) and (12). The value (x(tLX), y(tLX)) corresponds to the desired position of the vehicle 62 at time t=tLX, where x(tLX) can be estimated by integrating the vehicle longitudinal speed vx and the value y(tLX) can be obtained by the lane width and the roadway geometry. Note that yr in equations (3)-(6) represents the lateral offset of the roadway from the center of the vehicle 62, and here y represents the vehicle location with respect to Rv(0).
Selecting a fifth-order polynomial equation for the x and y positions of the vehicle 62 gives:

y(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0.  (13)

Considering the initial and final conditions gives:

(y(x),y′(x),y′′(x))t=0=(0,0,y′′seg1(x(0)),  (14)





  
    
      
        
          
            (
            
              
                y
                ⁡
                
                  (
                  x
                  )
                
              
              ,
              
                
                  y
                  ′
                
                ⁡
                
                  (
                  x
                  )
                
              
              ,
              
                
                  y
                  ′′
                
                ⁡
                
                  (
                  x
                  )
                
              
            
            )
          
          
            t
            =
            
              t
              LX
            
          
        
        =
        
          
            {
            
              
                
                  
                    
                      (
                      
                        
                          
                            y
                            
                              seg
                              ⁢
                              
                                
                              
                              ⁢
                              1
                            
                          
                          ⁡
                          
                            (
                            
                              x
                              ⁡
                              
                                (
                                
                                  t
                                  LX
                                
                                )
                              
                            
                            )
                          
                        
                        ,
                        
                          
                            y
                            
                              seg
                              ⁢
                              
                                
                              
                              ⁢
                              1
                            
                            ′
                          
                          ⁡
                          
                            (
                            
                              x
                              ⁡
                              
                                (
                                
                                  t
                                  LX
                                
                                )
                              
                            
                            )
                          
                        
                        ,
                        
                          
                            y
                            
                              seg
                              ⁢
                              
                                
                              
                              ⁢
                              1
                            
                            ′′
                          
                          ⁡
                          
                            (
                            
                              x
                              ⁡
                              
                                (
                                
                                  t
                                  LX
                                
                                )
                              
                            
                            )
                          
                        
                      
                      )
                    
                    ,
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        0
                      
                      <
                      
                        x
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                      <
                      
                        x
                        1
                      
                    
                  
                
              
              
                
                  
                    
                      (
                      
                        
                          
                            y
                            
                              seg
                              ⁢
                              
                                
                              
                              ⁢
                              2
                            
                          
                          ⁡
                          
                            (
                            
                              x
                              ⁡
                              
                                (
                                
                                  t
                                  LX
                                
                                )
                              
                            
                            )
                          
                        
                        ,
                        
                          
                            y
                            
                              seg
                              ⁢
                              
                                
                              
                              ⁢
                              2
                            
                            ′
                          
                          ⁡
                          
                            (
                            
                              x
                              ⁡
                              
                                (
                                
                                  t
                                  LX
                                
                                )
                              
                            
                            )
                          
                        
                        ,
                        
                          
                            y
                            
                              seg
                              ⁢
                              
                                
                              
                              ⁢
                              2
                            
                            ′′
                          
                          ⁡
                          
                            (
                            
                              x
                              ⁡
                              
                                (
                                
                                  t
                                  LX
                                
                                )
                              
                            
                            )
                          
                        
                      
                      )
                    
                    ,
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        
                          x
                          1
                        
                      
                      <
                      
                        x
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                      <
                      
                        x
                        2
                      
                    
                  
                
              
            
            }
          
          .
        
      
    
    
      
        (
        15
        )
      
    
  




The problem can be solved by the following linear equation:




  
    
      
        
          [
          
            
              
                
                  a
                  0
                
              
            
            
              
                
                  a
                  1
                
              
            
            
              
                
                  a
                  2
                
              
            
            
              
                
                  a
                  3
                
              
            
            
              
                
                  a
                  4
                
              
            
            
              
                
                  a
                  5
                
              
            
          
          ]
        
        =
        
          
            
              [
              
                
                  
                    1
                  
                  
                    
                      x
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                  
                  
                    
                      
                        x
                        2
                      
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                  
                  
                    
                      
                        x
                        3
                      
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                  
                  
                    
                      
                        x
                        4
                      
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                  
                  
                    
                      
                        x
                        5
                      
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        ⁡
                        
                          (
                          0
                          )
                        
                      
                    
                  
                  
                    
                      3
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          2
                        
                        ⁡
                        
                          (
                          0
                          )
                        
                      
                    
                  
                  
                    
                      4
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          3
                        
                        ⁡
                        
                          (
                          0
                          )
                        
                      
                    
                  
                  
                    
                      5
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          4
                        
                        ⁡
                        
                          (
                          0
                          )
                        
                      
                    
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    2
                  
                  
                    
                      6
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        ⁡
                        
                          (
                          0
                          )
                        
                      
                    
                  
                  
                    
                      12
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          2
                        
                        ⁡
                        
                          (
                          0
                          )
                        
                      
                    
                  
                  
                    
                      20
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          3
                        
                        ⁡
                        
                          (
                          0
                          )
                        
                      
                    
                  
                
                
                  
                    1
                  
                  
                    
                      x
                      ⁡
                      
                        (
                        
                          t
                          LX
                        
                        )
                      
                    
                  
                  
                    
                      
                        x
                        2
                      
                      ⁡
                      
                        (
                        
                          t
                          LX
                        
                        )
                      
                    
                  
                  
                    
                      
                        x
                        3
                      
                      ⁡
                      
                        (
                        
                          t
                          LX
                        
                        )
                      
                    
                  
                  
                    
                      
                        x
                        4
                      
                      ⁡
                      
                        (
                        
                          t
                          LX
                        
                        )
                      
                    
                  
                  
                    
                      
                        x
                        5
                      
                      ⁡
                      
                        (
                        
                          t
                          LX
                        
                        )
                      
                    
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                    
                  
                  
                    
                      3
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          2
                        
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                    
                  
                  
                    
                      4
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          3
                        
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                    
                  
                  
                    
                      5
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          4
                        
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                    
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    
                      6
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                    
                  
                  
                    
                      12
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          2
                        
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                    
                  
                  
                    
                      20
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          3
                        
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                    
                  
                
              
              ]
            
            
              -
              1
            
          
          ⁢
          
             
            
              
                [
                
                  
                    
                      
                        y
                        ⁡
                        
                          (
                          
                            x
                            ⁡
                            
                              (
                              0
                              )
                            
                          
                          )
                        
                      
                    
                  
                  
                    
                      
                        
                          y
                          ′
                        
                        ⁡
                        
                          (
                          
                            x
                            ⁡
                            
                              (
                              0
                              )
                            
                          
                          )
                        
                      
                    
                  
                  
                    
                      
                        
                          y
                          ′′
                        
                        ⁡
                        
                          (
                          
                            x
                            ⁡
                            
                              (
                              0
                              )
                            
                          
                          )
                        
                      
                    
                  
                  
                    
                      
                        y
                        ⁡
                        
                          (
                          
                            x
                            ⁡
                            
                              (
                              
                                t
                                LX
                              
                              )
                            
                          
                          )
                        
                      
                    
                  
                  
                    
                      
                        
                          y
                          ′
                        
                        ⁡
                        
                          (
                          
                            x
                            ⁡
                            
                              (
                              
                                t
                                LX
                              
                              )
                            
                          
                          )
                        
                      
                    
                  
                  
                    
                      
                        
                          y
                          ′′
                        
                        ⁡
                        
                          (
                          
                            x
                            ⁡
                            
                              (
                              
                                t
                                LX
                              
                              )
                            
                          
                          )
                        
                      
                    
                  
                
                ]
              
              .
            
          
        
      
    
    
      
        (
        16
        )
      
    
  




The path generation problem can be simplified by normalization of the coordinates. Denoting the normalized coordinates as (xn(t), yn(t)) gives:




  
    
      
        
          
            
              x
              n
            
            ⁡
            
              (
              t
              )
            
          
          =
          
            
              x
              ⁡
              
                (
                t
                )
              
            
            
              x
              ⁡
              
                (
                
                  t
                  LX
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        17
        )
      
    
  
  
    
      
        
          
            y
            n
          
          ⁡
          
            (
            
              x
              ⁡
              
                (
                t
                )
              
            
            )
          
        
        =
        
          
            
              y
              ⁡
              
                (
                
                  x
                  ⁡
                  
                    (
                    t
                    )
                  
                
                )
              
            
            
              y
              ⁡
              
                (
                
                  x
                  ⁡
                  
                    (
                    
                      t
                      LX
                    
                    )
                  
                
                )
              
            
          
          .
        
      
    
    
      
        (
        18
        )
      
    
  




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

y1(xn)=an,5xn5+an,4xn4+an,3xn3+an,2xn2+an,1xn+an,0.  (19)

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:




  
    
      
        
          
            
              (
              
                
                  
                    y
                    n
                  
                  ⁡
                  
                    (
                    
                      x
                      n
                    
                    )
                  
                
                ,
                
                  
                    
                      y
                      ′
                    
                    ⁡
                    
                      (
                      
                        x
                        n
                      
                      )
                    
                  
                  n
                
                ,
                
                  
                    
                      y
                      ′′
                    
                    ⁡
                    
                      (
                      
                        x
                        n
                      
                      )
                    
                  
                  n
                
              
              )
            
            
              t
              =
              0
            
          
          =
          
            (
            
              0
              ,
              0
              ,
              
                
                  
                    y
                    
                      seg
                      ⁢
                      
                        
                      
                      ⁢
                      1
                    
                    ′′
                  
                  ⁡
                  
                    (
                    
                      x
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                    )
                  
                
                ·
                
                  
                    
                      x
                      2
                    
                    ⁡
                    
                      (
                      
                        t
                        
                          L
                          ⁢
                          
                            
                          
                          ⁢
                          X
                        
                      
                      )
                    
                  
                  
                    y
                    ⁡
                    
                      (
                      
                        t
                        
                          L
                          ⁢
                          
                            
                          
                          ⁢
                          X
                        
                      
                      )
                    
                  
                
              
            
            )
          
        
        ,
      
    
    
      
        (
        20
        )
      
    
  








  
    
      
        
          
            (
            
              
                
                  y
                  n
                
                ⁡
                
                  (
                  
                    x
                    n
                  
                  )
                
              
              ,
              
                
                  
                    y
                    ′
                  
                  ⁡
                  
                    (
                    
                      x
                      n
                    
                    )
                  
                
                n
              
              ,
              
                
                  
                    y
                    ′′
                  
                  ⁡
                  
                    (
                    
                      x
                      n
                    
                    )
                  
                
                n
              
            
            )
          
          
            t
            =
            
              t
              
                L
                ⁢
                
                  
                
                ⁢
                X
              
            
          
        
        =
        
          
            {
            
              
                
                  
                    (
                    
                      1
                      ,
                      
                        
                          
                            y
                            
                              seg
                              ⁢
                              
                                
                              
                              ⁢
                              1
                            
                            ′
                          
                          ⁡
                          
                            (
                            
                              x
                              ⁡
                              
                                (
                                
                                  t
                                  
                                    L
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    X
                                  
                                
                                )
                              
                            
                            )
                          
                        
                        ·
                        
                          
                            x
                            ⁡
                            
                              (
                              
                                t
                                LX
                              
                              )
                            
                          
                          
                            y
                            ⁡
                            
                              (
                              
                                t
                                LX
                              
                              )
                            
                          
                        
                      
                      ,
                    
                  
                
                
                  
                    
                      
                        y
                        
                          seg
                          ⁢
                          
                            
                          
                          ⁢
                          1
                        
                        ′′
                      
                      ⁡
                      
                        (
                        
                          
                            x
                            ⁡
                            
                              (
                              
                                t
                                
                                  L
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  X
                                
                              
                              )
                            
                          
                          ·
                          
                            
                              
                                x
                                2
                              
                              ⁡
                              
                                (
                                
                                  t
                                  
                                    L
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    X
                                  
                                
                                )
                              
                            
                            
                              y
                              ⁡
                              
                                (
                                
                                  t
                                  
                                    L
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    X
                                  
                                
                                )
                              
                            
                          
                        
                        )
                      
                    
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      0
                    
                    <
                    x
                    <
                    
                      x
                      1
                    
                  
                
              
              
                
                  
                    (
                    
                      1
                      ,
                      
                        
                          
                            y
                            
                              seg
                              ⁢
                              
                                
                              
                              ⁢
                              2
                            
                            ′
                          
                          ⁡
                          
                            (
                            
                              x
                              ⁡
                              
                                (
                                
                                  t
                                  
                                    L
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    X
                                  
                                
                                )
                              
                            
                            )
                          
                        
                        ·
                        
                          
                            x
                            ⁡
                            
                              (
                              
                                t
                                LX
                              
                              )
                            
                          
                          
                            y
                            ⁡
                            
                              (
                              
                                t
                                LX
                              
                              )
                            
                          
                        
                      
                      ,
                    
                  
                
                
                  
                    
                      
                        y
                        
                          seg
                          ⁢
                          
                            
                          
                          ⁢
                          2
                        
                        ′′
                      
                      ⁡
                      
                        (
                        
                          
                            x
                            ⁡
                            
                              (
                              
                                t
                                
                                  L
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  X
                                
                              
                              )
                            
                          
                          ·
                          
                            
                              
                                x
                                2
                              
                              ⁡
                              
                                (
                                
                                  t
                                  
                                    L
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    X
                                  
                                
                                )
                              
                            
                            
                              y
                              ⁡
                              
                                (
                                
                                  t
                                  
                                    L
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    X
                                  
                                
                                )
                              
                            
                          
                        
                        )
                      
                    
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        1
                      
                    
                    <
                    x
                    <
                    
                      x
                      2
                    
                  
                
              
            
            ⁢
            
              
            
            }
          
          ⁢
          
            
          
          .
        
      
    
    
      
        (
        21
        )
      
    
  




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




  
    
      
        
          [
          
            
              
                
                  a
                  
                    n
                    ,
                    0
                  
                
              
            
            
              
                
                  a
                  
                    n
                    ,
                    1
                  
                
              
            
            
              
                
                  a
                  
                    n
                    ,
                    2
                  
                
              
            
            
              
                
                  a
                  
                    n
                    ,
                    3
                  
                
              
            
            
              
                
                  a
                  
                    n
                    ,
                    4
                  
                
              
            
            
              
                
                  a
                  
                    n
                    ,
                    5
                  
                
              
            
          
          ]
        
        =
        
          
            
              
                [
                
                  
                    
                      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
                    
                  
                
                ]
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    
                      
                        y
                        n
                      
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                  
                
                
                  
                    
                      
                        y
                        n
                        ′
                      
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                  
                
                
                  
                    
                      
                        y
                        n
                        ′′
                      
                      ⁡
                      
                        (
                        0
                        )
                      
                    
                  
                
                
                  
                    
                      
                        y
                        n
                      
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                  
                
                
                  
                    
                      
                        y
                        n
                        ′
                      
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                  
                
                
                  
                    
                      
                        y
                        n
                        ′′
                      
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                  
                
              
              ]
            
          
          .
        
      
    
    
      
        (
        22
        )
      
    
  




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 maneuver in normalized coordinates. Applying equation (18) can yield the desired path profile in the vehicle coordinates.
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, Rv(0). In curved roadway cases, the boundary conditions can be written as:

(y(x(0)) y′(x(0)) y′′(x(0)))=(0 0 y′′seg(0)),  (23)

(y(x(tLX)) y′(x(tLX)) y′′(x(tLX)))=(yseg(x(tLX))+L y′seg(x(tLX)) y′′seg(x(tLX))),  (24)

where L is the lane width and x(tLX) is the x-coordinate at time tLX that corresponds to the longitudinal distance of travel to complete the lane change maneuver. The value x(tLX) can be estimated by integrating the vehicle speed vx over time. Note that yseg can be either yseg1 and yseg2 depending on which segment x(tLX) belongs to, i.e.:





  
    
      
        
          y
          
            s
            ⁢
            
              
            
            ⁢
            e
            ⁢
            
              
            
            ⁢
            g
          
        
        =
        
          
            {
            
              
                
                  
                    
                      
                        y
                        
                          seg
                          ⁢
                          
                            
                          
                          ⁢
                          1
                        
                      
                      ⁡
                      
                        (
                        
                          x
                          ⁡
                          
                            (
                            
                              t
                              
                                L
                                ⁢
                                
                                  
                                
                                ⁢
                                X
                              
                            
                            )
                          
                        
                        )
                      
                    
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      0
                    
                    <
                    
                      x
                      ⁡
                      
                        (
                        
                          t
                          
                            L
                            ⁢
                            
                              
                            
                            ⁢
                            X
                          
                        
                        )
                      
                    
                    <
                    
                      x
                      1
                    
                  
                
              
              
                
                  
                    
                      
                        y
                        
                          seg
                          ⁢
                          
                            
                          
                          ⁢
                          2
                        
                      
                      ⁡
                      
                        (
                        
                          x
                          ⁡
                          
                            (
                            
                              t
                              
                                L
                                ⁢
                                
                                  
                                
                                ⁢
                                X
                              
                            
                            )
                          
                        
                        )
                      
                    
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        1
                      
                    
                    <
                    
                      x
                      ⁡
                      
                        (
                        
                          t
                          
                            L
                            ⁢
                            
                              
                            
                            ⁢
                            X
                          
                        
                        )
                      
                    
                    <
                    
                      x
                      2
                    
                  
                
              
            
            }
          
          .
        
      
    
    
      
        (
        25
        )
      
    
  




In normalized form, the initial and final conditions are:




  
    
      
        (
        
          
            
              
                
                  y
                  n
                
                ⁡
                
                  (
                  
                    
                      x
                      n
                    
                    =
                    0
                  
                  )
                
              
              ⁢
              
                
              
              ⁢
              
                
                  y
                  n
                  ′
                
                ⁡
                
                  (
                  
                    
                      x
                      n
                    
                    =
                    0
                  
                  )
                
              
              ⁢
              
                
              
              ⁢
              
                
                  y
                  n
                  ′′
                
                ⁡
                
                  (
                  
                    
                      x
                      n
                    
                    =
                    0
                  
                  )
                
              
            
            =
            
              (
              
                0
                ⁢
                
                  
                
                ⁢
                0
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      y
                      seg
                      ′′
                    
                    ⁡
                    
                      (
                      0
                      )
                    
                  
                  ·
                  
                    
                      
                        x
                        2
                      
                      ⁡
                      
                        (
                        
                          t
                          
                            L
                            ⁢
                            
                              
                            
                            ⁢
                            X
                          
                        
                        )
                      
                    
                    
                      y
                      ⁡
                      
                        (
                        
                          x
                          ⁡
                          
                            (
                            
                              t
                              
                                L
                                ⁢
                                
                                  
                                
                                ⁢
                                X
                              
                            
                            )
                          
                        
                        )
                      
                    
                  
                
              
              )
            
          
          ,
        
      
    
    
      
        (
        26
        )
      
    
  
  
    
      
        (
        
          
            
              
                
                  y
                  n
                
                ⁡
                
                  (
                  
                    
                      x
                      n
                    
                    =
                    1
                  
                  )
                
              
              ⁢
              
                
              
              ⁢
              
                
                  y
                  n
                  ′
                
                ⁡
                
                  (
                  
                    
                      x
                      n
                    
                    =
                    1
                  
                  )
                
              
              ⁢
              
                
              
              ⁢
              
                
                  y
                  n
                  ′′
                
                ⁡
                
                  (
                  
                    
                      x
                      n
                    
                    =
                    1
                  
                  )
                
              
            
            =
            
              (
              
                1
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      y
                      seg
                      ′
                    
                    ⁡
                    
                      (
                      
                        x
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                      )
                    
                  
                  ·
                  
                    
                      x
                      ⁡
                      
                        (
                        
                          t
                          
                            L
                            ⁢
                            
                              
                            
                            ⁢
                            X
                          
                        
                        )
                      
                    
                    
                      y
                      ⁡
                      
                        (
                        
                          x
                          ⁡
                          
                            (
                            
                              t
                              
                                L
                                ⁢
                                
                                  
                                
                                ⁢
                                X
                              
                            
                            )
                          
                        
                        )
                      
                    
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    
                      y
                      seg
                      ′′
                    
                    ⁡
                    
                      (
                      
                        x
                        ⁡
                        
                          (
                          
                            t
                            LX
                          
                          )
                        
                      
                      )
                    
                  
                  ·
                  
                    
                      
                        x
                        2
                      
                      ⁡
                      
                        (
                        
                          t
                          
                            L
                            ⁢
                            
                              
                            
                            ⁢
                            X
                          
                        
                        )
                      
                    
                    
                      y
                      ⁡
                      
                        (
                        
                          x
                          ⁡
                          
                            (
                            
                              t
                              
                                L
                                ⁢
                                
                                  
                                
                                ⁢
                                X
                              
                            
                            )
                          
                        
                        )
                      
                    
                  
                
              
              )
            
          
          ,
        
      
    
    
      
        (
        27
        )
      
    
  




Substituting equations (26) and (27) into the linear equation (22) results in the following solution:

an,0=an,1=0,  (28)





  
    
      
        
          
            a
            
              n
              ,
              2
            
          
          =
          
            0.5
            ⁢
            
              
                y
                
                  seg
                  ⁢
                  
                    
                  
                  ⁢
                  1
                
                ′′
              
              ·
              
                
                  
                    x
                    2
                  
                  ⁡
                  
                    (
                    
                      t
                      
                        L
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                    
                    )
                  
                
                
                  y
                  ⁡
                  
                    (
                    
                      x
                      ⁡
                      
                        (
                        
                          t
                          
                            L
                            ⁢
                            
                              
                            
                            ⁢
                            x
                          
                        
                        )
                      
                    
                    )
                  
                
              
            
          
        
        ,
      
    
    
      
        (
        29
        )
      
    
  








  
    
      
        
          [
          
            
              
                
                  a
                  
                    n
                    ,
                    3
                  
                
              
            
            
              
                
                  a
                  
                    n
                    ,
                    4
                  
                
              
            
            
              
                
                  a
                  
                    n
                    ,
                    5
                  
                
              
            
          
          ]
        
        =
        
          
            
              
                [
                
                  
                    
                      1
                    
                    
                      1
                    
                    
                      1
                    
                  
                  
                    
                      3
                    
                    
                      4
                    
                    
                      5
                    
                  
                  
                    
                      6
                    
                    
                      12
                    
                    
                      20
                    
                  
                
                ]
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    
                      
                        
                          y
                          n
                        
                        ⁡
                        
                          (
                          1
                          )
                        
                      
                      -
                      
                        0.5
                        ⁢
                        
                          
                            
                              y
                              seg
                              ′′
                            
                            ⁡
                            
                              (
                              0
                              )
                            
                          
                          ·
                          
                            
                              
                                x
                                2
                              
                              ⁡
                              
                                (
                                
                                  t
                                  
                                    L
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    x
                                  
                                
                                )
                              
                            
                            
                              y
                              ⁡
                              
                                (
                                
                                  x
                                  ⁡
                                  
                                    (
                                    
                                      t
                                      
                                        L
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        x
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                          
                        
                      
                    
                  
                
                
                  
                    
                      
                        
                          y
                          n
                          ′
                        
                        ⁡
                        
                          (
                          1
                          )
                        
                      
                      -
                      
                        0.5
                        ⁢
                        
                          
                            
                              y
                              seg
                              ′′
                            
                            ⁡
                            
                              (
                              0
                              )
                            
                          
                          ·
                          
                            
                              
                                x
                                2
                              
                              ⁡
                              
                                (
                                
                                  t
                                  
                                    L
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    x
                                  
                                
                                )
                              
                            
                            
                              y
                              ⁡
                              
                                (
                                
                                  x
                                  ⁡
                                  
                                    (
                                    
                                      t
                                      
                                        L
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        x
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                          
                        
                      
                    
                  
                
                
                  
                    
                      
                        
                          y
                          n
                          ′′
                        
                        ⁡
                        
                          (
                          1
                          )
                        
                      
                      -
                      
                        0.5
                        ⁢
                        
                          
                            
                              y
                              seg
                              ′′
                            
                            ⁡
                            
                              (
                              0
                              )
                            
                          
                          ·
                          
                            
                              
                                x
                                2
                              
                              ⁡
                              
                                (
                                
                                  t
                                  
                                    L
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    x
                                  
                                
                                )
                              
                            
                            
                              y
                              ⁡
                              
                                (
                                
                                  x
                                  ⁡
                                  
                                    (
                                    
                                      t
                                      
                                        L
                                        ⁢
                                        
                                          
                                        
                                        ⁢
                                        x
                                      
                                    
                                    )
                                  
                                
                                )
                              
                            
                          
                        
                      
                    
                  
                
              
              ]
            
          
          .
        
      
    
    
      
        (
        30
        )
      
    
  




Note that yseg can be either yseg1 or yseg2 depending on which segment x(tLX) belongs to.

As seen in equation (30), 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.
For straight road cases, the path generation problem can be further simplified. The road curvature ρ is zero throughout the lane change maneuver 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),  (31)

(y(x(tLX)) y′(x(tLX)) y′′(x(tLX)))=(L 0 0),  (32)

where L is the lane width.

In normalized form, the initial and final conditions can be written as:

(yn(xn=0) y′n(xn=0) y′′n(xn=0)=(0 0 0),  (33)

(yn(xn=1) y′n(xn=1) y′′n(xn=1)=(1 0 0).  (34)

Finally, substituting the conditions of equations (33) and (34) in the linear equation leads to the following solution:

an,0=an,1=an,2=0,  (35)





  
    
      
        
          [
          
            
              
                
                  a
                  
                    n
                    ,
                    3
                  
                
              
            
            
              
                
                  a
                  
                    n
                    ,
                    4
                  
                
              
            
            
              
                
                  a
                  
                    n
                    ,
                    5
                  
                
              
            
          
          ]
        
        =
        
          
            
              
                [
                
                  
                    
                      1
                    
                    
                      1
                    
                    
                      1
                    
                  
                  
                    
                      3
                    
                    
                      4
                    
                    
                      5
                    
                  
                  
                    
                      6
                    
                    
                      12
                    
                    
                      20
                    
                  
                
                ]
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    
                      
                        y
                        n
                      
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                  
                
                
                  
                    
                      
                        y
                        n
                        ′
                      
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                  
                
                
                  
                    
                      
                        y
                        n
                        ′′
                      
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                  
                
              
              ]
            
          
          =
          
            
              [
              
                
                  
                    10
                  
                
                
                  
                    
                      -
                      15
                    
                  
                
                
                  
                    6
                  
                
              
              ]
            
            .
          
        
      
    
    
      
        (
        36
        )
      
    
  




As seen in equation (36), the coefficients of the polynomial equation for the straight road are constant regardless of the lane change maneuver distance, that is, the desired path is predetermined and no online computation is needed for the lane change maneuver for straight road circumstances.
The discussion above can be generalized as follows. The camera 14 detects the lane markings on the ground and reports the center line 68 of the lane 66 as a third-order polynomial equation:

ylane(x)=c3·x3+c2·x2+c1·x+c0,  (37)

where c1, c2 and c3 are camera measurements identifying the center of the lane 66, the current position of the vehicle 62 is zero, and where the vehicle 62 is aligned with the second derivative of the curve.

The lane centering controller then generates the lane centering path 72, i.e., a path from the current vehicle position to the lane center line 68, at every time step as a single fifth-order polynomial equation:

yLC(x)=a0,LC+a1,LCx+a2,LCx2+a3,LCx3+a4,LCx4+a5,LCx5,  (38)

for 0<x≦xcam—range and where a0,LC, a1,LCx, a2,LCx2, a3,LCx3, a4,LCx4 and a5,LCx5 are determined by the lane centering path generating algorithm.

The discussion above provides the calculations and operations that are employed to model the path 72 as a fifth-order polynomial equation for the vehicle 62 to follow as defined by measurements from the camera 14 and as set forth in the '739 patent. However, that discussion does not consider the situation where a moving object, either travelling in a transverse direction or a longitudinal direction, is detected in front of the vehicle 62 and in a collision path therewith and how to take an evasive steering action to steer around the object if it is determined that braking alone will not avoid the collision.
As will be discussed below, the present invention describes path generation in a semi-autonomous or autonomously driven vehicle that avoids a collision with a moving object, referred to as collision avoidance path (AP) generation, a steering path around the moving object, referred to as cruise path (CP) generation, and path generation to return to the original lane centered path after passing the object, referred to as return path (RP) generation.
While the path generation process is being performed and the vehicle 62 is being automatically steered towards the center line 68 of the lane 66, the object detection sensor 22 will be monitoring and providing object detection of objects in front of the vehicle 62. The illustration 60 shows a moving object 74, here a bicycle, moving transversely across the lane 66 in front of the vehicle 62. The object detecting sensor 22 will detect the object 74 and provide an indication of the moving direction, speed, location and size of the object 74 based on the available technology. Further, based on this information, the algorithm determines a time-to-collision value tTTC based on the current vehicle speed and the position of the object 74. Also, the algorithm determines a collision boundary 76 that identifies the location that a collision with the object 74 is likely to be considering the speed of the object 74, the size of the object 74 and the value tTTC. The collision boundary 76 will be large enough to provide a suitable safety margin. The algorithm determines if the lane centering path 72 of the vehicle 62 passes through the collision boundary 76, and if not, there is not a collision threat and the vehicle 62 proceeds along the path 72 at the determined speed.
If the algorithm determines that the lane centering path 72 at the vehicle speed will cross the collision boundary 76, the algorithm determines if an evasive braking maneuver will avoid a collision with the object 74. Particularly, given the current vehicle speed and the distance to the object 74, the algorithm calculates the required deceleration to avoid the collision with the object 74 as:




  
    
      
        
          
            a
            
              x
              ,
              req
            
          
          =
          
            -
            
              
                v
                x
                2
              
              
                2
                ⁢
                
                  
                
                ⁢
                
                  s
                  f
                
              
            
          
        
        ,
      
    
    
      
        (
        39
        )
      
    
  




where vx is the current vehicle speed and sf is the distance to the object 74.

The algorithm then compares the required deceleration ax,req with a maximum possible deceleration limit ax,max of the vehicle 62, and if |ax,req| is less than ax,max, the algorithm calculates the vehicle speed profile as:

v(t)=vx+ax,reqt.  (40)

However, if |ax,req| is greater than ax,max, then braking alone cannot avoid a collision with the object 74 and the algorithm proceeds with determining an evasive steering maneuver around the object 74 as will be discussed below.
The collision boundary 76 includes two waypoints 78 and 80 that are determined from the current vehicle position as the location where the vehicle 62 must move to avoid a collision with the object 74. A collision avoidance path 82 from the vehicle 62 to the point 78 is one possible path to avoid the object 74 and a collision avoidance path 84 from the vehicle 62 to the point 80 is another possible path to avoid the object 74. The algorithm determines if both of the two waypoints 78 and 80 are within the roadway boundary or outside of the roadway boundary in a non-drivable area. If both of the waypoints 78 and 80 are within the roadway boundary, the algorithm calculates a lateral distance DLC from the vehicle position to each of the waypoints 78 and 80 from the lane center path 72 and selects the waypoint 78 or 80 that causes the smaller lateral deviation of the vehicle 62 from the lane centering path 72. In the example shown in FIG. 3, the path 84 is outside of the roadway boundary, and is disregarded as a possible path for the vehicle 62 to avoid the object 74. Therefore, the path 82 is selected as the collision avoidance path yAP for the vehicle 62 to avoid the object 74.
The collision avoidance path 82 is determined in the manner discussed above as a fifth-order polynomial equation:

yAP(x)=a5,APx5+a4,APx4+a3,APx3+a2,APx2+a1,APx+a0,AP,  (41)

for 0<t<tTTC and where a0,AP, a1,AP, a2,AP, a3,AP, a4,AP and a5,AP are unknown coefficients.

Initial conditions at the beginning of the collision avoidance path 82 are defined as:

yAP(0)=0,  (42)

y′AP(0)=0,  (43)

y′′AP(0)=2c2.  (44)

From the initial conditions and equations (42)-(44), the unknown coefficients a0,AP, a1,AP and a2,AP can be determined as:

a0,AP=0,  (45)

a1,AP=0,  (46)

a2,AP=c2.  (47)

Boundary conditions of the collision avoidance path 82 are defined as:

yAP(vxtTTC)=ylane(vxtTTC)+DLC,  (48)

y′AP(vxtTTC)=y′lane(vxtTTC),  (49)

y′′AP(vxtTTC)=y′′lane(vxtTTC).  (50)

The boundary conditions provide three equations (48)-(50) having three unknown coefficients a3,AP, a4,AP and a5,AP which can be solved as:

c2·(vxtTTC)2+a3,AP·(vxtTTC)3+a4,AP·(vxtTTC)4+a5,AP·(vxtTTC)5=ylane(vxtTTC)+DLC,  (51)

2c2·(vxtTTC)+3a3,AP·(vxtTTC)2+4a4,AP·(vxtTTC)3+5a5,AP·(vxtTTC)4=y′lane(vxtTTC),  (52)

2c2+6a3,AP·(vxtTTC)+12a4,AP·(vxtTTC)2+20a5,AP·(vxtTTC)3=y′′lane(vxtTTC).  (53)

After the collision path 80 is solved, and for the situation of a cross-moving object, the algorithm then calculates a return path (RP) from the waypoint 78 to the center line 68 of the original lane 66 as identified by return path 86 in the illustration 60. Using the deviation DLC, a time-to-return value tTTR from the waypoint 78 to the center line 68 of the original lane 66 can be estimated as:

tTTR=tTTC+ΔTLXDLC/L,  (54)

where ΔTLX is a typical lane change time, such as 5 or 6 seconds.

As above, the return path 86 is defined as a fifth-order polynomial equation:

yRP(x)=a5,RPx5+a4,RPx4+a3,RPx3+a2,RPx2+a1,RPx+a0,RP,  (55)

for tTTC<t<tTTR and where the coefficients a0,RP, a1,RP, a2,RP, a3,RP, a4,RP and a5,RP are unknown.

Initial conditions of the return path 86 are defined as:

yRP(vxtTTC)=yAP(vxtTTC),  (56)

y′RP(vxtTTC)=y′AP(vxtTTC),  (57)

y′′RP(vxtTTC)=y′′AP(vxtTTC),  (58)

and boundary conditions of the return path 86 are defined as:

yRP(vxtTTR)=ylane(vxtTTR),  (59)

y′RP(vxtTTR)=y′lane(vxtTTR),  (60)

y′′RP(vxtTTR)=y′′lane(vxtTTR).  (61)

Because there are six equations and the six unknown coefficients a0,RP, a1,RP, a2,RP, a3,RP, a4,RP and a5,RP, the coefficients can be determined from equations (56)-(61) and the return path 86 is solved as:

a0,RP+a1,RP(vxtTTC)+a2,RP·(vxtTTC)2+a3,RP·(vxtTTC)3+a4,RP·(vxtTTC)4+a5,RP·(vxtTTC)5=yAP(vxtTTC),  (62)

a1,RP+2a2,RP·(vxtTTC)+3a3,RP·(vxtTTC)2+4a4,RP·(vxtTTC)3+5a5,RP·(vxtTTC)4=y′AP(vxtTTC),  (63)

2a2,RP+6a3,RP·(vxtTTC)+12a4,RP·(vxtTTC)2+20a5,RP·(vxtTTC)3=y′′AP(vxtTTC),  (64)

a0,RP+a1,RP(vxtTTC)+a2,RP·(vxtTTC)2+a3,RP·(vxtTTC)3+a4,RP·(vxtTTC)4+a5,RP·(vxtTTC)5=ylane(vxtTTC),  (65)

a1,RP+2a2,RP·(vxtTTC)+3a3,RP·(vxtTTC)2+4a4,RP·(vxtTTC)3+5a5,RP·(vxtTTC)4=y′lane(vxtTTC),  (66)

2a2,RP+6a3,RP·(vxtTTC)+12a4,RP·(vxtTTC)2+20a5,RP·(vxtTTC)3=y′′lane(vxtTTC),  (67)

The discussion above is for the object 74 that is moving in a transverse direction relative to the vehicle travel direction and as such only the collision avoidance path 82 and the return path 86 need to be calculated to avoid the object 74. However, if the object sensors 22 determine that the object is moving in a collision path in front of the vehicle 62 in a longitudinal direction relative the vehicle travel direction or the object 74 is too long to be avoided by the collision avoidance path 82 and the return path 86, then the algorithm calculates a cruise path (CP) between the collision avoidance path 82 and the return path 86.
FIG. 4 is an illustration 100 similar to the illustration 60, where like elements are identified by the same reference number, depicting this situation where a moving object 102, here a bicycle, is traveling in front of the vehicle 62 and with substantially the same heading. A cruise path 104 is shown adjacent to the object 102 between the collision avoidance path 80 and the return path 86 that allows the vehicle 62 to travel around the object 102, where the cruise path 104 starts at the waypoint 78 and follows the lane boundary with the lane offset DLC. As shown, the collision boundary 106 is modified in size and shape to consider the moving direction of the object 102.
The length of the cruise path 104 is defined by a time-to-cruise value tTTS that is determined from the speed of the object 102 and its direction as:




  
    
      
        
          
            t
            
              T
              ⁢
              
                
              
              ⁢
              T
              ⁢
              
                
              
              ⁢
              S
            
          
          =
          
            
              t
              
                T
                ⁢
                
                  
                
                ⁢
                T
                ⁢
                
                  
                
                ⁢
                C
              
            
            +
            
              
                
                  v
                  x
                
                -
                
                  v
                  
                    x
                    ,
                    
                      o
                      ⁢
                      
                        
                      
                      ⁢
                      b
                      ⁢
                      
                        
                      
                      ⁢
                      s
                    
                  
                
              
              l
            
            +
            
              t
              margin
            
          
        
        ,
      
    
    
      
        (
        68
        )
      
    
  




where vx is vehicle speed, vx,obs is the speed of the object 102, l is the length of the object 102, and tmargin is a safety margin in the cruise time.

As above, the cruise path 104 is defined as a fifth-order polynomial equation:

yCP(x)=a5,CPx5+a4,CPx4+a3,CPx3+a2,CPx2+a1,CPx+a0,CP,  (69)

for tTTC<t<tTTS and where the coefficients a0,CP, a1,CP, a2,CP, a3,CP, a4,CP and a5,CP are unknown.

Initial conditions of the cruise path 104 are defined as:

yCP(vxtTTC)=yAP(vxtTTC),  (70)

y′CP(vxtTTC)=y′AP(vxtTTC),  (71)

y′′CP(vxtTTC)=y′′AP(vxtTTC),  (72)

and boundary conditions of the cruise path 104 are defined as:

yCP(vxtTTS)=ylane(vxtTTS)+DLC,  (73)

y′CP(vxtTTS)=y′lane(vxtTTS),  (74)

y′′CP(vxtTTS)=y′′lane(vxtTTS).  (75)

Since there are six equations and six unknowns, the cruise path 104 is determined or solved by calculating the coefficients a0,CP, a1,CP, a2,RP, a3,CP, a4,CP and a5,CP from the initial and boundary conditions as:

a0,CP+a1,CP(vxtTTC)+a2,CP·(vxtTTC)2+a3,CP·(vxtTTC)3+a4,CP·(vxtTTC)4+a5,CP·(vxtTTC)5=yAP(vxtTTC).  (76)

a1,CP+2a2,CP·(vxtTTC)+3a3,CP·(vxtTTC)2+4a4,CP·(vxtTTC)3+5a5,CP·(vxtTTC)4=y′AP(vxtTTC),  (77)

2a2,CP+6a3,CP·(vxtTTC)+12a4,CP·(vxtTTC)2+20a5,CP·(vxtTTC)3=y′′AP(vxtTTC),  (78)

a0,CP+a1,CP(vxtTTS)+a2,CP·(vxtTTS)2+a3,CP·(vxtTTS)3+a4,CP·(vxtTTS)4+a5,CP·(vxtTTS)5=ylane(vxtTTS),  (79)

a1,CP+2a2,CP·(vxtTTS)+3a3,CP·(vxtTTS)2+4a4,CP·(vxtTTS)3+5a5,CP·(vxtTTS)4=y′lane(vxtTTS),  (80)

2a2,CP+6a3,CP·(vxtTTS)+12a4,SP·(vxtTTS)2+20a5,CP·(vxtTTS)3=y′′lane(vxtTTS).  (81)

The return path 86 is then calculated from the end of the cruise path 104 in the same manner as for equations (62)-(67) above with the same boundary conditions, but with different initial conditions as follows:

yRP(vxtTTS)=yCP(vxtTTS),  (82)

y′RP(vxtTTS)=y′CP(vxtTTS),  (83)

y′′RP(vxtTTS)=y′′CP(vxtTTS),  (84)

a0,RP+a1,RP(vxtTTS)+a2,RP·(vxtTTS)2+a3,RP·(vxtTTS)3+a4,RP·(vxtTTS)4+a5,RP·(vxtTTS)5=yAP(vxtTTS),  (85)

a1,RP+2a2,RP·(vxtTTS)+3a3,RP·(vxtTTS)2+4a4,RP·(vxtTTS)3+5a5,RP·(vxtTTS)4=y′AP(vxtTTS),  (86)

2a2,RP+6a3,RP·(vxtTTS)+12a4,RP·(vxtTTS)2+20a5,RP·(vxtTTS)3=y′′AP(vxtTTS),  (87)

According to another embodiment of the invention, similar processes as those discussed above can be used to provide collision avoidance with a moving object in both the transverse and longitudinal direction during manual or semi-autonomous vehicle driving. For manual vehicle driving, the vehicle is not following a calculated vehicle path that is determined for lane centering and as such the algorithm does not know what path the vehicle is following. However, using vehicle motion sensing data and vehicle dynamics, the path of the vehicle can be predicted in the path prediction processor 42, and this predicted vehicle path can be used to determine if a collision with a moving object could occur, and if so, take automatic evasive steering action.
FIG. 5 is an illustration 90 of the roadway 64 where like elements to the illustrations 60 and 100 are identified with the same reference numeral. In this embodiment, as will be discussed in detail below, the vehicle 62 is not following the lane centering path 72, but is following a predicted path 92 that is determined from vehicle motion sensing data and vehicle parameters in the path prediction processor 42.
FIG. 6 is an illustration 110 of a motion model showing how the vehicle predicted path 92 can be determined as a time series based on the vehicle steering angle δ relative to a vehicle center of gravity 112 by solving differential equation (88) from the vehicle motion sensing data vx, r and δ and the vehicle parameters m, I, Cf, Cr, a and b.




  
    
      
        
          [
          
            
              
                
                  
                    y
                    .
                  
                  pred
                
              
            
            
              
                
                  
                    φ
                    .
                  
                  pred
                
              
            
            
              
                
                  
                    v
                    .
                  
                  y
                
              
            
            
              
                
                  r
                  .
                
              
            
          
          ]
        
        =
        
          
            [
            
              
            
            ⁢
            
              
                
                  0
                
                
                  
                    v
                    x
                  
                
                
                  1
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  1
                
              
              
                
                  0
                
                
                  0
                
                
                  
                    -
                    
                      
                        
                          C
                          f
                        
                        +
                        
                          C
                          r
                        
                      
                      
                        m
                        ⁢
                        
                          
                        
                        ⁢
                        
                          v
                          x
                        
                      
                    
                  
                
                
                  
                    
                      
                        
                          b
                          ⁢
                          
                            
                          
                          ⁢
                          
                            C
                            r
                          
                        
                        -
                        
                          a
                          ⁢
                          
                            
                          
                          ⁢
                          
                            C
                            f
                          
                        
                      
                      
                        m
                        ⁢
                        
                          
                        
                        ⁢
                        
                          v
                          x
                        
                      
                    
                    -
                    
                      v
                      x
                    
                  
                
              
              
                
                  0
                
                
                  0
                
                
                  
                    
                      
                        b
                        ⁢
                        
                          
                        
                        ⁢
                        
                          C
                          r
                        
                      
                      -
                      
                        a
                        ⁢
                        
                          
                        
                        ⁢
                        
                          C
                          f
                        
                      
                    
                    
                      I
                      ⁢
                      
                        
                      
                      ⁢
                      
                        v
                        x
                      
                    
                  
                
                
                  
                    
                      
                        
                          a
                          2
                        
                        ⁢
                        
                          C
                          f
                        
                      
                      +
                      
                        
                          b
                          2
                        
                        ⁢
                        
                          C
                          r
                        
                      
                    
                    
                      I
                      ⁢
                      
                        
                      
                      ⁢
                      
                        v
                        x
                      
                    
                  
                
              
            
            ]
          
          ·
          
             
            
              
                [
                
                  
                    
                      
                        y
                        pred
                      
                    
                  
                  
                    
                      
                        φ
                        pred
                      
                    
                  
                  
                    
                      
                        v
                        y
                      
                    
                  
                  
                    
                      r
                    
                  
                
                ]
              
              +
              
                
                  [
                  
                    
                      
                        0
                      
                    
                    
                      
                        0
                      
                    
                    
                      
                        
                          
                            C
                            f
                          
                          m
                        
                      
                    
                    
                      
                        
                          
                            a
                            ⁢
                            
                              
                            
                            ⁢
                            
                              C
                              f
                            
                          
                          I
                        
                      
                    
                  
                  ]
                
                ·
                
                  δ
                  .
                
              
            
          
        
      
    
    
      
        (
        88
        )
      
    
  




where ypred is the lateral position of vehicle, φpred is the vehicle heading angle, vx is the vehicle longitudinal speed, vy is the vehicle lateral speed, r is the vehicle yaw rate, δ is the steering angle, m is vehicle mass, I is vehicle inertia, Cf and Cr are vehicle front and rear cornering stiffness, respectively and a and b are distances to the vehicle front and rear axle, respectively, from the center of gravity 112.

The curvature of the predicted path 92 can be determined based on the deviation of the lateral position ypred at different distances from the current location of the vehicle 62. Using the predicted path 92 of the vehicle 62, the algorithm can determine a location of the vehicle 62 at different waypoints 94 along the predicted path 92 as (xpred,1, ypred,1), (xpred,2, ypred,2), (xpred,3, ypred,3), etc., where the values 1, 2 and 3 represent sample times. If the sample time is 0.1 sec, for example, then (xpred,1, ypred,1) is the waypoint sampled at time t=0.1 sec. Stated differently, solving equation (88) provides the series of sample waypoints 94, which is a time series solution. The time series solution is obtained at each sample time, such as 0.1 sec. For example, ypred,1 is the solution of equation (88) at t=0.1 sec, ypred,2 is the solution of equation (88) at t=0.2 sec, etc. The value xpred,1 is calculated as vx*0.1 sec, xpred,2 is calculated as vx*0.2 sec, etc.
Once (xpred,1, ypred,1), (xpred,2, ypred,2), (xpred,3, ypred,3), etc., are obtained, then the curve fitting algorithm determines the best fitting curve through (xpred,1, ypred,1), (xpred,2, ypred,2), (xpred,3, ypred,3), etc., and the predicted path yPP of the vehicle 62 can be defined by a third-order polynomial equation:

ypp(x)=p3·x3+p2·x2+p1·x+p0,  (89)

where the parameter p1, p2, p3 and p4 are unknowns, and are calculated by a least-squares method minimizing the cost function J:





  
    
      
        
          J
          =
          
            
              1
              2
            
            ⁢
            
              
                ∑
                i
              
              ⁢
              
                [
                
                  
                    (
                    
                      
                        y
                        
                          pred
                          ,
                          i
                        
                      
                      -
                      
                        
                          y
                          PP
                        
                        ⁡
                        
                          (
                          
                            x
                            =
                            
                              x
                              
                                pred
                                ,
                                i
                              
                            
                          
                          )
                        
                      
                    
                    )
                  
                  2
                
                ]
              
            
          
        
        ,
      
    
    
      
        (
        90
        )
      
    
  




where the solution of the cost function J is given by:





  
    
      
        
          [
          
            
              
                
                  p
                  3
                
              
            
            
              
                
                  p
                  2
                
              
            
            
              
                
                  p
                  1
                
              
            
            
              
                
                  p
                  0
                
              
            
          
          ]
        
        =
        
          
            
              [
              
                
                  
                    
                      x
                      
                        pred
                        ,
                        1
                      
                      3
                    
                  
                  
                    
                      x
                      
                        pred
                        ,
                        1
                      
                      2
                    
                  
                  
                    
                      x
                      
                        pred
                        ,
                        1
                      
                    
                  
                  
                    1
                  
                
                
                  
                    ...
                  
                  
                    ...
                  
                  
                    ...
                  
                  
                    1
                  
                
                
                  
                    
                      x
                      
                        pred
                        ,
                        n
                      
                      3
                    
                  
                  
                    
                      x
                      
                        pred
                        ,
                        n
                      
                      2
                    
                  
                  
                    
                      x
                      
                        pred
                        ,
                        n
                      
                    
                  
                  
                    1
                  
                
              
              ]
            
            
              -
              1
            
          
          ·
          
            
              [
              
                
                  
                    
                      y
                      
                        pred
                        ,
                        1
                      
                    
                  
                
                
                  
                    
                      y
                      
                        pred
                        ,
                        2
                      
                    
                  
                
                
                  
                    ...
                  
                
                
                  
                    
                      y
                      
                        pred
                        ,
                        n
                      
                    
                  
                
              
              ]
            
            .
          
        
      
    
    
      
        (
        91
        )
      
    
  




If the cost function J at a waypoint xpred,i exceeds a certain limit J≧Jthreshold, the algorithm ends a first segment of the path 92 at point xpred,i and starts a new predicted path as:

yPP,seg2=p3,seg2·x3+p2,seg2·x2+p1,seg2·x+p0,seg2.  (92)

Once the predicted path 92 has been determined as above, the algorithm proceeds to determine if a collision with a moving object is a concern as also discussed above, and if so, whether braking can prevent the collision, or if steering is required. If steering is required, the algorithm proceeds to determine the collision boundary 76, the waypoints 78 and 80, the collision avoidance path 82, the cruise path 104 and the return path 86 as discussed above, where the vehicle controller will take over steering of the vehicle 62 from the vehicle driver and those paths will be calculated as fifth-order polynomial equations in the same manner as discussed above.
FIG. 7 is a flow chart diagram 120 providing a general process flow of the discussion above for providing collision avoidance. The algorithm starts at box 122 and then determines if the vehicle 62 is in manual driving or autonomous driving at decision diamond 124. If the vehicle 62 is in autonomous driving, then the algorithm provides lane centering and path generation as described above at box 126, and if the vehicle 62 is being manually driven, then the algorithm calculates the predicted vehicle path 94 as discussed above at box 128. The algorithm then determines if an object is detected in front of the vehicle at box 130, and if so, performs a collision check to determine if a collision with the object will occur at the current vehicle speed and path at decision diamond 132. If no collision will occur, the algorithm returns to the start box 122. If a collision will occur at the decision diamond 132, the algorithm calculates the braking distance to avoid the collision at box 134, and then determines if the collision is avoidable by braking at decision diamond 136, as discussed above. If the collision can be avoided by braking alone at the decision diamond 136, then the algorithm performs the braking maneuver at box 138. If the algorithm determines that the collision cannot be avoided by braking and steering is required, the collision avoidance path 82 is generated at box 140, the cruise path 104 is generated at box 142 and the return path is generated at box 144.
As will be well understood by those skilled in the art, the several and various steps and processes discussed herein to describe the invention may be referring to operations performed by a computer, a processor or other electronic calculating device that manipulate and/or transform data using electrical phenomenon. Those computers and electronic devices may employ various volatile and/or non-volatile memories including non-transitory computer-readable medium with an executable program stored thereon including various code or executable instructions able to be performed by the computer or processor, where the memory and/or computer-readable medium may include all forms and types of memory and other computer-readable media.
The foregoing discussion disclosed 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.

## Claims

1. A method for providing an automatic steering path for a vehicle, said method comprising:
determining that the vehicle is being manually driven by a vehicle driver;
determining a predicted path of the vehicle based on vehicle motion sensing data and vehicle parameters, where determining a predicted path includes determining a set of waypoints on the predicted path via a time series solution of a differential equation including vehicle heading angle, vehicle longitudinal speed, vehicle lateral speed, vehicle yaw rate, vehicle steering angle, vehicle mass, vehicle inertia, vehicle front and rear cornering stiffnesses and distances between vehicle axles and vehicle center of gravity;
detecting a moving object in front of the vehicle;
determining if a collision between the vehicle and the object will occur if the vehicle travels along the predicted path at a current vehicle speed;
determining whether braking alone will prevent the collision with the object if it is determined that the collision will occur;
determining a steering path around the object if it is determined that vehicle braking will not prevent a collision with the object;
automatically steering the vehicle along the steering path; and
yielding the steering control back to the driver from the automatic steering.

2. The method according to claim 1 wherein determining the predicted path in time series includes solving the differential equation:




  
    [
    
      
        
          
            
              y
              .
            
            pred
          
        
      
      
        
          
            
              φ
              .
            
            pred
          
        
      
      
        
          
            
              v
              .
            
            y
          
        
      
      
        
          
            r
            .
          
        
      
    
    ]
  
  =
  
    
      [
      
        
      
      ⁢
      
        
          
            0
          
          
            
              v
              x
            
          
          
            1
          
          
            0
          
        
        
          
            0
          
          
            0
          
          
            0
          
          
            1
          
        
        
          
            0
          
          
            0
          
          
            
              -
              
                
                  
                    C
                    f
                  
                  +
                  
                    C
                    r
                  
                
                
                  m
                  ⁢
                  
                    
                  
                  ⁢
                  
                    v
                    x
                  
                
              
            
          
          
            
              
                
                  
                    b
                    ⁢
                    
                      
                    
                    ⁢
                    
                      C
                      r
                    
                  
                  -
                  
                    a
                    ⁢
                    
                      
                    
                    ⁢
                    
                      C
                      f
                    
                  
                
                
                  m
                  ⁢
                  
                    
                  
                  ⁢
                  
                    v
                    x
                  
                
              
              -
              
                v
                x
              
            
          
        
        
          
            0
          
          
            0
          
          
            
              
                
                  b
                  ⁢
                  
                    
                  
                  ⁢
                  
                    C
                    r
                  
                
                -
                
                  a
                  ⁢
                  
                    
                  
                  ⁢
                  
                    C
                    f
                  
                
              
              
                I
                ⁢
                
                  
                
                ⁢
                
                  v
                  x
                
              
            
          
          
            
              
                
                  
                    a
                    2
                  
                  ⁢
                  
                    C
                    f
                  
                
                +
                
                  
                    b
                    2
                  
                  ⁢
                  
                    C
                    r
                  
                
              
              
                I
                ⁢
                
                  
                
                ⁢
                
                  v
                  x
                
              
            
          
        
      
      ]
    
    ·
    
       
      
        
          
            [
            
              
                
                  
                    y
                    pred
                  
                
              
              
                
                  
                    φ
                    pred
                  
                
              
              
                
                  
                    v
                    y
                  
                
              
              
                
                  r
                
              
            
            ]
          
          +
          
            
              [
              
                
                  
                    0
                  
                
                
                  
                    0
                  
                
                
                  
                    
                      
                        C
                        f
                      
                      m
                    
                  
                
                
                  
                    
                      
                        a
                        ⁢
                        
                          
                        
                        ⁢
                        
                          C
                          f
                        
                      
                      I
                    
                  
                
              
              ]
            
            ·
            δ
          
        
        ,
      
    
  




where ypred is the lateral position of the vehicle, φpred is the vehicle heading angle, vx is the vehicle longitudinal speed, vy is the vehicle lateral speed, r is the vehicle yaw rate, δ is the steering angle, m is the vehicle mass, I is the vehicle inertia, Cf and Cr are the vehicle front and rear cornering stiffnesses, respectively, and a and b are the distances to the vehicle front and rear axle, respectively, from the center of gravity.

3. The method according to claim 2 wherein determining the predicted path includes defining the time series predicted path as a parametric third-order polynomial equation.

4. The method according to claim 3 wherein determining the parametric predicted path includes solving unknown parameters in the polynomial equation by minimizing a cost function.

5. The method according to claim 1 wherein determining whether vehicle braking alone will prevent the collision includes calculating a required deceleration to avoid the collision and comparing the required deceleration with a maximum capable deceleration of the vehicle.

6. The method according to claim 1 wherein determining if a collision between the vehicle and the object will occur includes defining a collision boundary around the moving object that is based on a speed of the moving object, moving direction of the object, a size of the moving object and a time-to-collision value, and determining if the lane centering path crosses the collision boundary.

7. The method according to claim 6 wherein determining a steering path around the object includes determining a collision avoidance path from the current vehicle position to a waypoint on the collision boundary, said method further comprising steering the vehicle to the waypoint on the collision avoidance path.

8. The method according to claim 7 wherein determining the collision avoidance path includes selecting one of a plurality of possible collision avoidance paths to multiple waypoints on the collision boundary where the closest waypoint to the current vehicle position that is within roadway boundaries is selected as the algorithm avoidance path.

9. The method according to claim 7 wherein determining the collision avoidance path includes solving a fifth-order polynomial equation based on initial vehicle conditions and roadway boundary conditions.

10. The method according to claim 9 wherein the fifth-order polynomial equation is:


yAP(x)=a5,APx5+a4,APx4+a3,APx3+a2,APx2+a1,APx+a0,AP,


for time 0<t<tTTC, wherein the initial conditions are defined as:


yAP(0)=0,



y′AP(0)=0,



y′′AP(0)=2c2,


and the boundary conditions are defined as:


yAP(vxtTTC)=ylane(vxtTTC)+DLC,



y′AP(vxtTTC)=y′lane(vxtTTC),



y′′AP(vxtTTC)=y′′lane(vxtTTC),


where yAP is vehicle lateral position on the collision avoidance path, ylane is vehicle lateral position on the lane centering path, a0,AP, a1,AP, a2,AP, a3,AP, a4,AP and a5,AP are unknown coefficients and to be determined using the initial conditions and the boundry conditions, tTTC is the time-to-collision value, vx is vehicle longitudinal speed, and DLC is a lateral deviation from the lane center.

11. The method according to claim 7 wherein detecting a moving object in front of the vehicle includes determining whether the moving object is moving in a transverse direction or a lateral direction relative to the lane centering path.

12. The method according to claim 11 wherein determining a steering path around the object includes determining a return path from the waypoint to the lane center if the object is moving in a transverse direction.

13. The method according to claim 12 wherein determining a return path includes determining the return path by solving a fifth-order polynomial equation based on initial conditions and roadway boundary conditions.

14. The method according to claim 13 wherein the fifth-order polynomial equation is:


yRP(x)=a5,RPx5+a4,RPx4+a3,RPx3+a2,RPx2+a1,RPx+a0,RP,


for time tTTC<t<tTTR, wherein the initial conditions are defined as:


yRP(vxtTTC)=yAP(vxtTTC),



y′RP(vxtTTC)=y′AP(vxtTTC),



y′′RP(vxtTTC)=y′′AP(vxtTTC),


and the boundary conditions are defined as:


yRP(vxtTTR)=ylane(vxtTTR),



y′RP(vxtTTR)=y′lane(vxtTTR),



y′′RP(vxtTTR)=y′′lane(vxtTTR),


where yAP is vehicle lateral position on the collision avoidance path, yRP is vehicle lateral position on the return path, ylane is vehicle lateral position on the lane centering path, a0,RP, a1,RP, a2,RP, a3,RP, a4,RP and a5,RP are unknown coefficients and to be determined using the initial conditions and the boundry conditions, tTTC is the time-to-collision value, tTTR is a time-to-return value, and vx is vehicle longitudinal speed.

15. The method according to claim 12 wherein determining a vehicle steering path includes determining a cruise path between the collision avoidance path and the return path if the object is moving in a longitudinal direction relative to the vehicle or the object is too long to be avoided only by the collision avoidance path and the return path.

16. The method according to claim 15 wherein determining the cruise path includes solving a fifth-order polynomial equation based on initial conditions and roadway boundary conditions.

17. The method according to claim 16 wherein the fifth-order polynomial equation is:


yCP(x)=a5,CPx5+a4,CPx4+a3,CPx3+a2,CPx2+a1,CPx+a0,CP,


for time tTTC<t<tTTS, wherein the initial conditions are defined as:


yCP(vxtTTC)=yAP(vxtTTC),



y′CP(vxtTTC)=y′AP(vxtTTC),



y′′CP(vxtTTC)=y′′AP(vxtTTC),


and the boundary conditions are defined as:


yCP(vxtTTS)=ylane(vxtTTS)+DLC,



y′CP(vxtTTS)=y′lane(vxtTTS),



y′′CP(vxtTTS)=y′′lane(vxtTTS),


where yAP is vehicle lateral position on the collision avoidance path, yCP is vehicle lateral position on the cruise path, ylane is vehicle lateral position on the lane centering path, a0,CP, a1,CP, a2,CP, a3,CP, a4,CP and a5,CP are unknown coefficients and to be determined using the initial conditions and the boundry conditions, tTTC is the time-to-collision value, tTTS is a time-to-cruise value, vx is vehicle longitudinal speed, and DLC is a deviation from the lane center.

18. The method according to claim 17 wherein a length of the cruise path is defined by the time-to-cruise value that is determined from the speed of the object and its direction as:




  
    
      t
      TTS
    
    =
    
      
        t
        TTC
      
      +
      
        
          
            v
            x
          
          -
          
            v
            
              x
              ,
              obs
            
          
        
        l
      
      +
      
        t
        margin
      
    
  
  ,




where vx is vehicle speed, vx,obs is the speed of the object, l is the length of the object, and tmargin is a safety margin in the cruise time.

19. A method for providing an automatic steering path for a vehicle, said method comprising:
determining that the vehicle is being manually driven by a vehicle driver;
determining a predicted path of the vehicle based on vehicle motion sensing data and vehicle parameters, where determining a predicted path includes determining a set of waypoints on the predicted path via a time series solution of a differential equation including vehicle heading angle, vehicle longitudinal speed, vehicle lateral speed, vehicle yaw rate, vehicle steering angle, vehicle mass, vehicle inertia, vehicle front and rear cornering stiffnesses and distances between vehicle axles and vehicle center of gravity;
detecting a moving object in front of the vehicle;
determining if a collision between the vehicle and the object will occur if the vehicle travels along the predicted path at a current vehicle speed;
determining a collision avoidance path from the current vehicle position to a safe waypoint adjacent to the moving object, wherein determining the collision avoidance path includes solving a fifth-order polynomial equation;
steering the vehicle from the current vehicle position to the waypoint on the collision avoidance path;
determining a return path from the waypoint to the lane center, wherein determining a return path includes solving a fifth-order polynomial equation;
steering the vehicle from the waypoint on the return path; and
yielding steering control back to the driver from automatic steering.

20. A method for providing an automatic steering path for a vehicle, said method comprising:
determining that the vehicle is being manually driven by a vehicle driver;
determining a predicted path of the vehicle based on vehicle motion sensing data and vehicle parameters, where determining a predicted path includes determining a set of waypoints on the predicted path via a time series solution of a differential equation including vehicle heading angle, vehicle longitudinal speed, vehicle lateral speed, vehicle yaw rate, vehicle steering angle, vehicle mass, vehicle inertia, vehicle front and rear cornering stiffnesses and distances between vehicle axles and vehicle center of gravity;
detecting a moving object in front of the vehicle;
determining if a collision between the vehicle and the object will occur if the vehicle travels along the predicted path at a current vehicle speed;
determining a collision avoidance path from the current vehicle position to a safe waypoint adjacent to the moving object, wherein determining the collision avoidance path includes solving a fifth-order polynomial equation;
steering the vehicle from the current vehicle position to the waypoint on the collision avoidance path;
determining a cruise path from the waypoint to an avoidance location beyond the object, wherein determining the cruise path includes solving a fifth-order polynomial equation;
steering the vehicle from the waypoint to the avoidance location on the cruise path;
determining a return path from the avoidance location to the lane center, wherein determining a return path includes solving a fifth-order polynomial equation;
steering the vehicle from the avoidance location on the return path; and
yielding steering control back to the driver from automatic steering.