Reactive path planning for autonomous driving

Patent metadata

Field	Value
Publication number	US-9868443-B2
Application number	US-201514696877-A
Country	US
Kind code	B2
Filing date	Apr 27, 2015
Priority date	Apr 27, 2015
Publication date	Jan 16, 2018
Grant date	Jan 16, 2018

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.

First claim

What is claimed is:

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:

D
i

=

∑
j

⁢

(

α
L

⁢

D

i
⁢

⁢
j

L

D
max
L

+

α
s

⁢

D

i
⁢

⁢
j

s

D
max
s

+

α
d

⁢

D

i
⁢

⁢
j

d

D
max
d

+

α
c

⁢

D

i
⁢

⁢
j

c

D
max
c

+

α
p

⁢

D

i
⁢

⁢
j

p

D
max
p

Assignees

• Gm Global Tech Operations Llc

Inventors

• Zeng Shuqing
• Jafari Rouhollah
• Moshchuk Nikolai K
• Litkouhi Bakhtiar B

Classifications

• B60W60/001

  Planning or execution of driving tasks · CPC title

• B60W60/00272

  relying on extrapolation of current movement · CPC title

• B60W2554/80

  Spatial relation or speed relative to objects · CPC title

• B60W30/16

  Control of distance between vehicles, e.g. keeping a distance to preceding vehicle · CPC title

• G05D1/021 Primary

  specially adapted to land vehicles · CPC title