REACTIVE PATH PLANNING FOR AUTONOMOUS DRIVING

• US 20160313133A1
• Filed: 04/27/2015
• Published: 10/27/2016
• 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: JAFARI, ROUHOLLAH, ZENG, SHUQING, MOSHCHUK, NIKOLAI K., LITKOUHI, BAKHTIAR B.
• Granted Patent: US 9,868,443 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 a road of travel;

(c) re-setting and actuating a timer;

(d) generating, by the processor, a planned path for autonomously maneuvering the 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).

2. The method of claim 1 wherein generating the planned path further includes comprises the steps of:

identifying virtual nodes based on the sensed objects in the road of travel; and

applying Delauney triangulation for generating triangles among selected virtual nodes.

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

4. The method of claim 3 further comprising the steps of:

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.

5. The method of claim 4 wherein a respective linear segment connecting a respective pair of vertex points of a respective triangle is only formed if the respective pair of vertex points belongs to the same respective triangle and if the vertex points do not belong to a same edge of the respective triangle.

6. The method of claim 4 wherein no vertex points are formed on a lane boundary of the road.

7. The method of claim 5 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, wherein each linear segment selected from each triangle forms a continuous planned path from the identified host virtual node to the identified ending virtual node.

8. The method of claim 7 wherein each of the selected linear segments are identified based on a cost-distance function, the cost-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.

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

10. The method of claim 9 wherein the cost-distance function is represent by the following formula:

11. The method of claim 10 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)²)} 

 

(16)

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

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

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

14. The method of claim 10 wherein the distance function component D_ij^d corresponds to a distance of a segment in the search graph to the 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 the weighted offsets from the previous host vehicle path for the source and target vertices of the segments with weighting directed on vertices closer to the host vehicle

15. The method of claim 10 wherein the distance function component D_ij^c corresponds to a distance of a segment in the search graph to the 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) 

 

(21)

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

16. The method of claim 15 wherein 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 the moving targets, and wherein the virtual potential field value D_ij^p is represented as follows:

17. The method of claim 8 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.

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

19. The method of claim 17 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.

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