Method and system for operating autonomous driving vehicles using graph-based lane change guide

Patent metadata

Field	Value
Publication number	US-10137896-B2
Application number	US-201615396211-A
Country	US
Kind code	B2
Filing date	Dec 30, 2016
Priority date	Dec 30, 2016
Publication date	Nov 27, 2018
Grant date	Nov 27, 2018

Abstract

In one embodiment, autonomous driving control is provided for an autonomous vehicle changing from a source lane to a target lane. Using a topological map, a reference node is selected in the source lane. With respect to the reference node, an earliest node is determined in the source lane at which it is first possible for the vehicle to change lanes and a last node is determined in the source lane after which it is no longer possible to change lanes. A range of the source lane is determined for which the vehicle can change lanes.

First claim

What is claimed is:

1. A computer-implemented method of operating an autonomous vehicle to change lanes from a source lane to a target lane, the method comprising:
selecting a first reference node of a topological graph associated with the source lane, the first reference node being a node in the source lane at which the autonomous vehicle can change lanes to a second reference node in the target lane;
determining, with respect to the first reference node of the topological graph, an earliest node in the source lane at which it is first possible for the autonomous vehicle to change lanes from the source lane to the target lane;
determining, with respect to the first reference node of the topological graph, a last node in the source lane after which it is no longer possible for the autonomous vehicle to change lanes from the source lane to the target lane;
determining a range of the source lane for which the autonomous vehicle can change lanes from the source lane to the target lane, wherein the range is from the earliest node in the source lane to the last node in the source lane; and
generating a trajectory to autonomously control the autonomous vehicle to change lanes from the source lane the target lane within the range, including determining time, a speed, and a distance to change lanes.

2. The method of claim 1 wherein the first reference node is selected using a minimum cost algorithm, an initial start location of the autonomous vehicle and a final destination location of the autonomous vehicle.

3. The method of claim 1 wherein the first reference node, the earliest node and the last node are all located on a central axis of the source lane being represented on the topological graph and wherein the second reference node is located on a central axis of the target lane being represented on the topological graph.

4. The method of claim 3 wherein the central axes of the source and target lanes include nodes at a predetermined interval along the central axes.

5. The method of claim 1 wherein determining the last node comprises:
performing a conditional breadth-first search for nodes in the source lane after the first reference node until a node in the source lane is found that does not have a corresponding node in the target lane, the corresponding node in the target lane being a node at which the autonomous vehicle can change lanes from the node in the source lane to the node in the target lane,
wherein segments of the source lane are merged between the first reference node in the source lane and the last node.

6. The method of claim 5 wherein determining the earliest node comprises:
performing a conditional breadth-first search for nodes in the target lane before the second reference node for a length corresponding to a length of the merged segments of the source lane, wherein each node in the target lane that is searched before the second reference node for the length is stored in a look up table.

7. The method of claim 6 wherein determining the earliest node further comprises:
traversing nodes of the source lane in a reverse direction beginning at the first reference node until a node in the source lane is found that does not have a corresponding node in the target lane stored in the look up table, the corresponding node in the target lane being a node at which the autonomous vehicle can change lanes from the node in the source lane to the node in the target lane.

8. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations of operating an autonomous vehicle to change lanes from a source lane to a target lane, the operations comprising:
selecting a first reference node of a topological graph associated with the source lane, the first reference node being a node in the source lane at which the autonomous vehicle can change lanes to a second reference node in the target lane;
determining, with respect to the first reference node of the topological graph, an earliest node in the source lane at which it is first possible for the autonomous vehicle to change lanes from the source lane to the target lane;
determining, with respect to the first reference node of the topological graph, a last node in the source lane after which it is no longer possible for the autonomous vehicle to change lanes from the source lane to the target lane;
determining a range of the source lane for which the autonomous vehicle can change lanes from the source lane to the target lane, wherein the range is from the earliest node in the source lane to the last node in the source lane; and
generating a trajectory to autonomously control the autonomous vehicle to change lanes from the source lane to the target lane within the range, including determining time, a speed, and a distance to change lanes.

9. The non-transitory machine-readable medium of claim 8 wherein the first reference node is selected using a minimum cost algorithm, an initial start location of the autonomous vehicle and a final destination location of the autonomous vehicle.

10. The non-transitory machine-readable medium of claim 8 wherein the first reference node, the earliest node and the last node are all located on a central axis of the source lane being represented on the topological graph and wherein the second reference node is located on a central axis of the target lane being represented on the topological graph.

11. The non-transitory machine-readable medium of claim 10 wherein the central axes of the source and target lanes include nodes at a predetermined interval along the central axes.

12. The non-transitory machine-readable medium of claim 8 wherein determining the last node comprises:
performing a conditional breadth-first search for nodes in the source lane after the first reference node until a node in the source lane is found that does not have a corresponding node in the target lane, the corresponding node in the target lane being a node at which the autonomous vehicle can change lanes from the node in the source lane to the node in the target lane,
wherein segments of the source lane are merged between the reference node in the source lane and the last node.

13. The non-transitory machine-readable medium of claim 12 wherein determining the earliest node comprises:
performing a conditional breadth-first search for nodes in the target lane before the second reference node for a length corresponding to a length of the merged segments of the source lane, wherein each node in the target lane that is searched before the second reference node for the length is stored in a look up table.

14. The non-transitory machine-readable medium of claim 13 wherein determining the earliest node further comprises:
traversing nodes of the source lane in a reverse direction beginning at the first reference node until a node in the source lane is found that does not have a corresponding node in the target lane stored in the look up table, the corresponding node in the target lane being a node at which the autonomous vehicle can change lanes from the node in the source lane to the node in the target lane.

15. A data processing system, comprising:
a processor; and
a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations of operating an autonomous vehicle to change lanes from a source lane to a target lane, the operations including:
selecting a first reference node of a topological graph associated with the source lane, the first reference node being a node in the source lane at which

Assignees

• Baidu Usa Llc

Inventors

• Zhuang Li
• Yang Guang
• Wang Jingao

Classifications

• G01C21/3453

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• B60W30/095

  Predicting travel path or likelihood of collision · CPC title

• B60W30/18163 Primary

  Lane change; Overtaking manoeuvres · CPC title

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/3658

  Lane guidance · CPC title