Dynamic routing for autonomous vehicles

• US 10,691,131 B2
• Filed: 07/09/2018
• Issued: 06/23/2020
• Est. Priority Date: 11/18/2016
• Status: Active Grant

• Current Assignee: Waymo LLC (Alphabet Inc.)
• Original Assignee: Waymo LLC (Alphabet Inc.)
• Inventors: Fairfield, Nathaniel, Herbach, Joshua Seth
• Primary Examiner(s): Paige, Tyler D
• Application Number:
  US16/029,922
• Publication Number:
  US 20190004527A1
• Time in Patent Office: 715 Days
• Field of Search: 701411
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G08G 1/096833 where different aspects are considered when computing the route

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.

Claims

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 including a plurality of lane segments;

determining, by the one or more processors, a set of lane segments for a local map region of the map information based on a current location of the vehicle, wherein the local map region corresponds to all areas that the vehicle could possibly reach within a predetermined period of time;

assigning, by the one or more processors, a cost value to each lane segment of the set of lane segments of the local map region based on the destination;

using, by the one or more processors, any assigned cost values to determine whether to pass an object; and

maneuvering, by the one or more processors, the vehicle based on the determination of whether to pass the object.

2. The method of claim 1, wherein the object is another vehicle in a same lane as the vehicle.

3. The method of claim 1, wherein the object is a stopped vehicle in a same lane as the vehicle.

4. The method of claim 1, wherein determining whether to pass the vehicle is further based on assigned cost values for lane segments for a second lane adjacent to a first lane in which the vehicle is traveling.

5. The method of claim 1, wherein determining whether to pass the object is further based on assigned cost values for lane segments corresponding to the vehicle proceeding through an intersection without a turn if the vehicle passes the object.

6. The method of claim 1, wherein determining whether to pass the object is further based on assigned cost values for lane segments corresponding to the vehicle making a right turn through an intersection if the vehicle does not pass the object.

7. The method of claim 1, wherein at least some of the lane segments of the set of lane segments correspond to lane segments of a lane adjacent to a lane segment in which the vehicle is traveling when the cost values are assigned.

8. The method of claim 1, wherein the cost values are assigned further based on the destination location.

9. The method of claim 1, wherein assigning at least one of the any assigned cost values for a given lane segment of the set of lane segments includes retrieving a previously assigned cost value from local cache.

10. The method of claim 1, wherein assigning at least a second one of the any assigned cost values for a second given lane segment of the set of lane segments includes generating a new value based on the destination.

11. 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 including a plurality of lane segments;

determine a set of lane segments for a local map region of the map information based on a current location of the vehicle, wherein the local map region corresponds to all areas that the vehicle could possibly reach within a predetermined period of time;

assign a cost value to each lane segment of the set of lane segments of the local map region based on the destination;

use any assigned cost values to determine whether to pass an object; and

maneuver the vehicle based on the determination of whether to pass the object.

12. The system of claim 11, wherein the object is another vehicle in a same lane as the vehicle.

13. The system of claim 11, wherein the object is a stopped vehicle in a same lane as the vehicle.

14. The system of claim 11, wherein the one or more processors are further configured to determine whether to pass the vehicle is further based on assigned cost values for lane segments for a second lane adjacent to a first lane in which the vehicle is traveling.

15. The system of claim 11, wherein the one or more processors are further configured to determine whether to pass the object is further based on assigned cost values for lane segments corresponding to the vehicle proceeding through an intersection without a turn if the vehicle passes the object.

16. The system of claim 11, wherein the one or more processors are further configured to determine whether to pass the object is further based on assigned cost values for lane segments corresponding to the vehicle making a right turn through an intersection if the vehicle does not pass the object.

17. The system of claim 11, wherein at least some of the lane segments of the set of lane segments correspond to lane segments of a lane adjacent to a lane segment in which the vehicle is traveling when the cost values are assigned.

18. The system of claim 11, wherein the one or more processors are further configured to assign at least one of the any assigned cost values for a given lane segment of the set of lane segments includes retrieving a previously assigned cost value from local cache.

19. The system of claim 11, wherein the one or more processors are further configured to assign at least a second one of the any assigned cost values for a second given lane segment of the set of lane segments includes generating a new value based on the destination.

20. The system of claim 11, further comprising the vehicle.