Dynamic routing for self-driving vehicles

• US 10,254,121 B2
• Filed: 01/23/2017
• Issued: 04/09/2019
• Est. Priority Date: 01/23/2017
• Status: Active Grant

• Current Assignee: Uatc, LLC (Uber Technologies, Inc.)
• Original Assignee: Uber Technologies, Inc.
• Inventors: Stentz, Anthony, Nagy, Bryan
• Primary Examiner(s): Ismail, Mahmoud S
• Application Number:
  US15/412,303
• Publication Number:
  US 20180209801A1
• Time in Patent Office: 806 Days
• Field of Search: 701 25, 701 26
• CPC Class Codes: B60W 2556/45 External transmission of data to or from the vehicle
• 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: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G05D 1/0214 in accordance with safety or protection criteria, e.g. avoiding hazardous areas monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0297 by controlling means in a control room
• CPC Class Codes: Y02T 10/84 Data processing systems or methods, management, administration

Abstract

A self-driving vehicle (SDV) can dynamically analyze a sensor view of a surrounding area of the SDV, and a current localization map in order to autonomously operate acceleration, braking, and steering systems of the SDV along a current route to a destination. Upon approaching a decision point along the current route, the SDV can perform a cost optimization to determine whether to diverge from the current route.

Claims

1. A self-driving vehicle (SDV) comprising:

acceleration, braking, and steering systems;

a set of sensors generating a sensor view of a surrounding area of the SDV; and

a control system comprising one or more processors executing an instruction set that causes the control system to;

dynamically analyze (i) the sensor view of the surrounding area, and (ii) a current localization map in order to autonomously operate the acceleration, braking, and steering systems along a current route to a destination;

upon approaching a decision point along the current route, perform a cost optimization by;

determining one or more alternative route options that diverge from the current route at the decision point;

determining, from the sensor view, a risk factor for continuing along the current route;

determining, from the sensor view, an additional risk factor for each of the one or more alternative route options; and

determining whether to diverge from the current route based, at least in part, on the risk factor for continuing along the current route and the additional risk factor for each of the one or more alternative route options.

2. The SDV of claim 1, wherein the executed instruction set further causes the control system to determine the one or more alternative route options that diverge from the current route by:

transmitting a route option inquiry to a backend transport routing system; and

based on the route option inquiry, receiving, from the backend transport routing system the one or more alternative route options that diverge from the current route at the decision point.

3. The SDV of claim 2, wherein the executed instruction set causes the control system to further perform the cost optimization by (i) determining, from the sensor view, an immediate traffic situation on the current route, and (ii) comparing the immediate traffic situation on the current route with one or more traffic situations corresponding to the one or more alternative route options.

4. The SDV of claim 3, wherein the backend transport routing system manages routing for a fleet of self-driving vehicles, including the SDV, throughout a given region.

5. The SDV of claim 3, wherein the executed instruction set further causes the control system to:

transmit a localized traffic context update to the backend transport routing system, the localized traffic context update indicating the immediate traffic situation.

6. The SDV of claim 4, wherein the executed instruction set further causes the control system to:

receive a route update for the current route from the backend transport routing system based on traffic context data submitted by individual vehicles in the fleet of self-driving vehicles.

7. The SDV of claim 4, wherein performance of the cost optimization upon approaching the decision point corresponds to routing by the control system based on the dynamic analysis of the sensor view.

8. The SDV of claim 1, wherein each of the one or more alternative route options is associated with a time delta, and wherein the executed instruction set causes the control system to determine whether to diverge from the current route by (i) determining, from the sensor view, a time delta for continuing along the current route, and (ii) comparing the time delta for continuing along the current route to the time delta for each of the one or more alternative route options.

9. A non-transitory computer readable medium storing instructions that, when executed by one or more processors of a control system for a self-driving vehicle (SDV), cause the control system to:

dynamically analyze (i) a sensor view of a surrounding area of the SDV, and (ii) a current localization map in order to autonomously operate acceleration, braking, and steering systems of the SDV along a current route to a destination; and

upon approaching a decision point along the current route, perform a cost optimization by;

determining one or more alternative route options that diverge from the current route at the decision point;

determining, from the sensor view, a risk factor for continuing along the current route;

determining, from the sensor view, an additional risk factor for each of the one or more alternative route options; and

determining whether to diverge from the current route based, at least in part, on the risk factor for continuing along the current route and the additional risk factor for each of the one or more alternative route options.

10. The non-transitory computer readable medium of claim 9, wherein the executed instructions cause the control system to determine the one or more alternative route options by:

transmitting a route option inquiry to a backend transport routing system; and

based on the route option inquiry, receiving, from the backend transport routing system, the one or more alternative route options that diverge from the current route at the decision point.

11. The non-transitory computer readable medium of claim 10, wherein the executed instructions cause the control system to further perform the cost optimization by (i) determining, from the sensor view, an immediate traffic situation on the current route, and (ii) comparing the immediate traffic situation on the current route with one or more traffic situations corresponding to the one or more alternative route options.

12. The non-transitory computer readable medium of claim 11, wherein the backend transport routing system manages routing for a fleet of self-driving vehicles, including the SDV, throughout a given region.

13. The non-transitory computer readable medium of claim 12, wherein the executed instructions further cause the control system to:

transmit a localized traffic context update to the backend transport routing system, the localized traffic context update indicating the immediate traffic situation.

14. The non-transitory computer readable medium of claim 12, wherein the executed instructions further cause the control system to:

receive a route update for the current route from the backend transport routing system based on traffic context data submitted by individual vehicles in the fleet of self-driving vehicles.

15. The non-transitory computer readable medium of claim 12, wherein performance of the cost optimization upon approaching the decision point corresponds to routing by the control system based on the dynamic analysis of the sensor view.

16. A computer-implemented method of operating a self-driving vehicle (SDV), the method being performed by one or more processors of the SDV and comprising:

dynamically analyzing (i) a sensor view of a surrounding area of the SDV, and (ii) a current localization map in order to autonomously operate acceleration, braking, and steering systems of the SDV along a current route to a destination;

upon approaching a decision point along the current route, performing a cost optimization by;

determining one or more alternative route options that diverge from the current route at the decision point;

determining, from the sensor view, a risk factor for continuing along the current route; and

determining, from the sensor view, an additional risk factor for each of the one or more alternative route options; and

determining whether to diverge from the current route based, at least in part, on the risk factor for continuing along the current route and the additional risk factor for each of the one or more alternative route options.

17. The method of claim 16, wherein determining the one or more alternative route options that diverge from the current route comprises:

transmitting a route option inquiry to a backend transport routing system; and

based on the route option inquiry, receiving, from the backend transport routing system, the one or more alternative route options that diverge from the current route at the decision point.

18. The method of claim 17, wherein performing the cost optimization further comprises (i) determining, from the sensor view, an immediate traffic situation on the current route, and (ii) comparing the immediate traffic situation on the current route with one or more traffic situations corresponding to the one or more alternative route options.

19. The method of claim 18, wherein the backend transport routing system manages routing for a fleet of self-driving vehicles, including the SDV, throughout a given region.