Dynamic routing for autonomous vehicles

Patent metadata

Field	Value
Publication number	US-10042362-B2
Application number	US-201615355658-A
Country	US
Kind code	B2
Filing date	Nov 18, 2016
Priority date	Nov 18, 2016
Publication date	Aug 7, 2018
Grant date	Aug 7, 2018

Abstract

A route for a trip to a destination is generated using map information. A set of no-go roadway segments, where the vehicle is not able to drive in an autonomous mode, relevant to the route from the plurality of no-go roadway segments is identified from the map information. A local region around a current location of the vehicle is determined. A local map region including roadway segments of the map information that correspond to locations within the local region is determined. The set of the plurality of no-go roadway segments is filtered from the roadway segments of the local map region. A cost value is assigned to each roadway segment of the filtered roadway segments of the local map region. Any assigned cost values are used to determining a plan for maneuvering the vehicle for a predetermined period into the future. The vehicle is maneuvered according to the plan.

First claim

The invention claimed is:

1. A method for maneuvering a vehicle, the method comprising:
generating, by one or more processors, a route for a trip from a first location to a destination using map information, the map information including roadway segments defining the shape and location of roadways, the map information also identifying at least one no-go roadway segment defining roadway segments where the vehicle is not able to drive in an autonomous mode;
identifying, by the one or more processors, from the map information, a set of no-go roadway segments relevant to the route from the plurality of no-go roadway segments;
determining, by the one or more processors, a local region around a current location of the vehicle, the local region corresponding to a geographic area including both locations that the vehicle is able to reach from the current location within a pre-determined period of time as well as a region behind the vehicle at the current location;
identifying, by the one or more processors, a local map region by performing a graph cut on the map information, the local map region including roadway segments of the map information;
filtering, by the one or more processors, the set of the plurality of no-go roadway segments from the roadway segments of the local map region;
assigning, by the one or more processors, a cost value to each roadway segment of the filtered roadway segments of the local map region;
using, by the one or more processors, any assigned cost values to determining a plan for maneuvering the vehicle for a predetermined period of time into the future; and
maneuvering, by the one or more processors, the vehicle according to the plan.

2. The method of claim 1 , further comprising identifying at least one additional no-go roadway segment which would not allow the vehicle to reach the destination using a graph walk starting from the destination, and the set of no-go roadway segments includes the at least one no-go roadway segment as well as at least one additional roadway segment.

3. The method of claim 1 , wherein the local region is determined periodically and the set of no-go roadway segments are identified only once for the trip.

4. The method of claim 1 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on a construction area corresponding to the roadway segment.

5. The method of claim 1 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on an unprotected left turn corresponding to the roadway segment.

6. The method of claim 1 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on a time to reach the destination from the roadway segment.

7. The method of claim 1 , further comprising:
storing at least one assigned cost value in a local cache;
determining a second local region at least partially overlapping with the local region;
identify a second local map region including roadway segments of the map information that correspond to locations within the second local region;
filter the set of the plurality of no-go roadway segments from the roadway segments of the second local map region;
assigning a cost value to each roadway segment of the filtered roadway segments of the second local map region by retrieving the at least one assigned cost value from the local cache;
using any assigned cost values for each roadway segment of the filtered roadway segments of the second local map region to determining a second plan for maneuvering the vehicle for a second predetermined period into the future; and
maneuvering the vehicle according to the second plan.

8. The method of claim 1 , wherein the plan includes a set of connected roadway segments of the filtered roadway segments of the local map region that lead out of the local region and have a lowest accumulation of cost values.

9. The method of claim 1 , wherein determining the plan includes determining whether a lane change for the vehicle should be forced.

10. The method of claim 1 , wherein determining the plan includes determining whether a turn should be executed to move the vehicle between two lane roadway segments.

11. The method of claim 1 , wherein determining the plan includes identifying a secondary path when a primary path corresponding to the roadway segments of the route is not available.

12. The method of claim 1 , further comprising identifying a second set of no-go roadway segments using a graph walk on the map information starting from the destination and moving towards the staring location; and wherein filtering the set of no-go roadway segments includes removing any segments of the second set of no-go roadway segments.

13. The method of claim 1 , wherein identifying the second set of no-go roadway segments includes identifying segments of the map information that will not get the vehicle to the destination.

14. A system for maneuvering a vehicle, the system comprising one or more processors configured to:
generate a route for a trip from a first location to a destination using map information, the map information including roadway segments defining the shape and location of roadways, the map information also identifying a plurality of no-go roadway segments defining roadway segments where the vehicle is not able to drive in an autonomous mode;
identify a set of no-go roadway segments relevant to the route from the plurality of no-go roadway segments;
determine a local region around a current location of the vehicle, the local region corresponding to a geographic area including both locations that the vehicle is able to reach from the current location within a pre-determined period of time as well as a region behind the vehicle at the current location;
identify a local map region by performing a graph cut on the map information, the local map region including roadway segments of the map information;
filter the set of the plurality of no-go roadway segments from the roadway segments of the local map region;
assign a cost value to each roadway segment of the filtered roadway segments of the local map region;
use any assigned cost values to determining a plan for maneuvering the vehicle for a predetermined period into the future; and
maneuver the vehicle according to the plan.

15. The method of claim 14 , wherein the one or more processors are further configured to identify at least one additional no-go roadway segment which would not allow the vehicle to reach the destination using a graph walk starting from the, and the set of no-go roadway segments includes the at least one no-go roadway segment as well as the at least one additional roadway segment.

16. The method of claim 14 , wherein the local region is determined periodically and the set of no-go roadway segments are identified only once for the trip.

17. The method of claim 14 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on a construction area corresponding to the roadway segment.

18. The method of claim 14 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on an unprotected left turn corresponding to the roadway segment.

19. The method of claim 14 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on a time to reach the destination from the roadway segment.

Assignees

• Waymo Llc

Inventors

• Fairfield Nathaniel
• Herbach Joshua Seth

Classifications

• G01C21/3667

  Display of a road map (G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635) · CPC title

• G01C21/3461

  Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries · CPC title

• G01C21/20

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G08G1/096833

  where different aspects are considered when computing the route · CPC title

• G01C21/3407 Primary

  specially adapted for specific applications · CPC title