Reactive path planning for autonomous driving

• US 9,868,443 B2
• Filed: 04/27/2015
• Issued: 01/16/2018
• Est. Priority Date: 04/27/2015
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations LLC (General Motors Company)
• Inventors: Zeng, Shuqing, Jafari, Rouhollah, Moshchuk, Nikolai K., Litkouhi, Bakhtiar B.
• Primary Examiner(s): LIN, ABBY YEE
• Application Number:
  US14/696,877
• Publication Number:
  US 20160313133A1
• Time in Patent Office: 995 Days
• CPC Class Codes: B60W 2554/80 Spatial relation or speed relative to objects
• CPC Class Codes: B60W 30/0956 the prediction being responsive to traffic or environmental parameters
• CPC Class Codes: B60W 30/12 Lane keeping
• CPC Class Codes: B60W 30/16 Control of distance between vehicles, e.g. keeping a distance to preceding vehicle
• CPC Class Codes: B60W 30/18163 Lane change; Overtaking manoeuvres
• CPC Class Codes: B60W 60/001 Planning or execution of driving tasks
• CPC Class Codes: B60W 60/0011 involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles
• CPC Class Codes: B60W 60/00272 relying on extrapolation of current movement
• CPC Class Codes: B62D 15/0255 Automatic changing of lane, e.g. for passing another vehicle
• CPC Class Codes: B62D 15/0265 Automatic obstacle avoidance by steering
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G08G 1/163 involving continuous checking
• CPC Class Codes: G08G 1/167 Driving aids for lane monitoring, lane changing, e.g. blind spot detection

Abstract

A method of adaptively re-generating a planned path for an autonomous driving maneuver. An object map is generated based on the sensed objects in a road of travel. A timer re-set and actuated. A planned path is generated for autonomously maneuvering the vehicle around the sensed objects. The vehicle is autonomously maneuvered along the planned path. The object map is updated based on sensed data from the vehicle-based devices. A safety check is performed for determining whether the planned path is feasible based on the updated object map. The planned path is re-generated in response to a determination that the existing path is infeasible, otherwise a determination is made as to whether the timer has expired. If the timer has not expired, then a safety check is re-performed; otherwise, a return is made to re-plan the path.

Claims

1. A method of adaptively re-generating a planned path for an autonomous driving maneuver comprising the steps of:

(a) obtaining, by vehicle-based devices, object data associated with sensed objects in a road of travel;

(b) constructing, by a processor, an object map based on the sensed objects in the road of travel;

(c) re-setting and actuating a timer;

(d) generating, by the processor, a planned path for autonomously maneuvering a vehicle around the sensed objects, the planned path being generated based on a cost-distance function;

(e) autonomously maneuvering the vehicle along the planned path;

(f) updating the object map based on updated sensed data from the vehicle-based devices;

(g) determining whether the planned path is feasible based on the updated object map;

(h) returning to step (a) in response to a determination that the planned path is infeasible;

otherwise continuing to step (i);

(i) determining whether the timer has expired; and

(j) returning to step (a) in response to the timer expiring;

otherwise, returning to step (f);

wherein generating the planned path further includes the steps of identifying virtual nodes based on the sensed objects in the road of travel and applying Delaunay triangulation for generating triangles among selected virtual nodes;

wherein the virtual nodes include lane virtual nodes, host vehicle virtual nodes, ending virtual nodes, and shifted scan nodes, the lane virtual nodes represent lane boundaries of the road, the host vehicle virtual nodes represent a position of a host vehicle and a start of a search space, wherein the ending virtual nodes represent an end of the search space, and the shifted scan nodes represent displacements of detected dynamic objects based on velocities of the detected dynamic objects relative to the host vehicle;

wherein generating the planned path further includes identifying vertex points along edges of the triangles, the vertex points evenly spaced along each triangle edge, and forming linear segments between every pair of vertex points within each triangle;

wherein a respective linear segment connecting a respective pair of vertex points is only formed if the respective pair of vertex points belongs to a respective triangle and if the vertex points do not belong to a same edge of the respective triangle;

wherein the planned path is generated from an identified host virtual node to an identified ending virtual node by selecting a respective linear segment from each triangle, each linear segment selected from each triangle forms a continuous planned path from the identified host virtual node to the identified ending virtual node;

wherein each of the selected linear segments are identified based on a cost-distance function, the cost-distance function being generated as distance functional components relating to a length of the planned path, as a relative slope of each segment, as an offset of the planned path to a previous determined path, as an offset from a center of a current driven lane, and as an offset distance from surrounding obstacles.

2. The method of claim 1, wherein no vertex points are formed on a lane boundary of the road.

3. The method of claim 1, wherein each of the respective distance functional components are weighted for identifying a degree of use in the cost-distance function.

4. The method of claim 3, wherein the cost-distance function is represented by the following formula:

5. The method of claim 4, wherein the distance function component D_ij^L corresponds to an actual length of the j-th segment of the i-th path, and wherein D_ij^L is represented by the following equation:

D_ij^L=√

{square root over ((x_ij^vs−

x_ij^vt)²+(y_ij^vs−

y_ij^vt)²)}

where (x_ij^vs,y_ij^vs) and (x_ij^vt,y_ij^vt) denote the source and target vertices of a corresponding segment, respectively.

6. The method of claim 5, wherein the distance function component D_ij^s corresponds to the relative slope of the j-th segment of the i-th path to a heading of the host vehicle or the lane, wherein term D_ij^s is represented as follows:

7. The method of claim 4, wherein the distance function component D_ij^s corresponds to the relative slope of the j-th segment of the i-th path to a heading of the host vehicle or the lane, wherein term D_ij^s is represented as follows:

8. The method of claim 4, wherein the distance function component D_ij^d corresponds to a distance of a segment in a search graph to a host vehicle path found at a previous planning time for preventing significant deviation from the previous planned path, wherein the distance function component D_ij^d is represented as follows:

D_ij^d=D_ij^ds+D_ij^dt

where D_ij^ds and D_ij^dt are weighted offsets from a previous host vehicle path for the source and target vertices of the segments with weighting directed on vertices closer to the host vehicle.

9. The method of claim 4, wherein the distance function component D_ij^ic corresponds to a distance of a segment in a search graph to a centerline of a current lane, wherein the distance function component D_ij^c is represented as follows:

D_ij^c=min(d_ij^c1,d_ij^c2,d_ij^c3)

where d_ij^c1, d_ij^c2 and d_ij^c3 are offset values of each linear segment from the centers of a current lane, an adjacent left lane, and an adjacent right lane, respectively.

10. The method of claim 9, wherein the distance component function D_ij^p ensures that the shortest planned path is at least at a safe distance threshold from the surrounding obstacles while factoring dynamics of moving targets, and wherein a virtual potential field value D_ij^p is represented as follows:

11. The method of claim 1, further comprising the step of refining the planned path by identifying a corridor surrounding the planned path, the corridor having a left corridor boundary and a right corridor boundary offset from the planned path.

12. The method of claim 11, wherein the left corridor boundary and the right corridor boundary are formed based on left corridor points and right corridor points wherein the left corridor points and right corridor points are determined using the following conditions:

13. The method of claim 11, further comprising the step of re-generating a planned path within the corridor as a function of an estimated curvature and curvature rate at various path points.

14. The method of claim 13, further comprising the step of determining feasibility of the re-generated planned path as a function of lateral accelerations of the vehicle and a distance from surrounding objects.