Dynamic rerouting during navigation

• US 9,360,335 B1
• Filed: 09/20/2013
• Issued: 06/07/2016
• Est. Priority Date: 07/09/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Powelson, Lawrence Howard, Stoltzman, Will
• Primary Examiner(s): Jabr, Fadey
• Assistant Examiner(s): Jos, Basil T
• Application Number:
  US14/033,032
• Time in Patent Office: 991 Days
• Field of Search: 701/414
• US Class Current: 1/1
• 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

Abstract

Initial navigation directions are generated to guide a vehicle along an initial route between an origin and a destination. When the vehicle is a certain location disposed along the initial route, an alternate route to the destination is determined, such that the alternate route and the initial route diverge at a point of divergence between the current location of the vehicle and the destination. Boundaries of an announcement window within which the alternate route can be suggested are determined in view of a current speed of the vehicle. When the point of divergence is within the announcement window, generating, by the one or more processors, an interactive prompt to suggest that the alternate route be selected, such that the interactive prompt is not generated when the point of divergence is outside the announcement window.

Claims

1. A method for providing dynamic rerouting notifications, the method comprising:

generating, by one or more processors, initial navigation directions to guide a vehicle along an initial route between an origin and a destination;

when the vehicle is at a current location on the initial route, determining, by the one or more processors, an alternate route to the destination, including determining a point of divergence between the initial route and the alternate route;

determining, by the one or more processors, boundaries of a dynamic rerouting window in response to having determined the point of divergence, including determining the boundaries based on (i) a current speed of the vehicle and (ii) the current location of the vehicle with respect to the point of divergence; and

when the point of divergence is within the dynamic rerouting window, generating, by the one or more processors, an interactive prompt to suggest that the alternate route be selected, wherein the interactive prompt is not generated when the point of divergence is outside the dynamic rerouting window.

2. The method of claim 1, wherein generating the interactive prompt further includes:

determining, by the one or more processors, a projected amount of time saved by selecting the alternate route,

wherein generating the interactive prompt is in response to determining that the projected amount of time is above a threshold value.

3. The method of claim 2, wherein generating the interactive prompt further includes:

determining, by the one or more processors, a difference in distances to the destination along the initial route and the alternate route,

wherein the threshold value is a first threshold value, and

wherein generating the interactive prompt is in response to determining that the difference in distances is below a second threshold value.

4. The method of claim 1, wherein determining the alternate route to the destination includes periodically checking, by the one or more processors, adverse conditions along the initial route, wherein the adverse conditions include one or more heavy traffic, lane closures, reported accidents, and adverse weather.

5. The method of claim 1, wherein determining the boundaries of the dynamic rerouting window includes:

determining, by the one or more processors, a leading edge of the dynamic rerouting window corresponding to a projected position of the vehicle after a first predetermined period of time, at a current speed of the vehicle, and

determining, by the one or more processors, a trailing edge of the dynamic rerouting window corresponding to a projected position of the vehicle after a second predetermined period of time, at the current speed of the vehicle.

6. The method of claim 5, further comprising:

transmitting, by the one or more processors, the leading edge and the trailing edge of the dynamic rerouting window to a server, and

receiving, by the one or more processors, an indication of whether the point of divergence is within the dynamic rerouting window, in response to the transmission of the leading edge and the trailing edge.

7. The method of claim 1, further comprising:

generating, by the one or more processors, a first polyline made up of a first sequence of points to represent the original route;

generating, by the one or more processors, a second polyline made up of a second sequence of points to represent the alternate route; and

comparing, by the one or more processors, the first sequence to the second sequence to determine the point of divergence.

8. The method of claim 1, further comprising:

receiving a confirmation via the interactive prompt that the alternate route has been selected; and

providing navigation directions to guide the vehicle along the alternate route to the destination.

9. The method of claim 1, wherein the initial navigation directions include a sequence of instructions provided as the vehicle follows the initial route, the method further comprising:

determining, by the one or more processors, an amount of time remaining until a next one in the sequence of instructions is to be provided;

wherein generating the interactive prompt is further in response to determining that the amount of time is above a threshold value.

10. A non-transitory computer-readable medium storing thereon instructions for providing dynamic rerouting notifications, wherein the instructions, when executed on one or more processors, cause the one or more processors to:

generate initial navigation directions to guide a vehicle along an initial route between an origin and a destination;

when the vehicle is at a current location on the initial route, determine an alternate route to the destination, including determining a point of divergence between the initial route and the alternate route;

determine boundaries of a dynamic rerouting window in response to having determined the point of divergence, including determining the boundaries based on (i) a current speed of the vehicle and (ii) the current location of the vehicle with respect to the point of divergence; and

when the point of divergence is within the dynamic rerouting window, generate an interactive prompt to suggest that the alternate route be selected, wherein the interactive prompt is not generated when the point of divergence is outside the dynamic rerouting window.

11. The computer-readable medium of claim 10, wherein to generate the interactive prompt, the instructions further cause the one or more processors to:

determine a projected amount of time saved by selecting the alternate route,

wherein generating the interactive prompt is in response to determining that the projected amount of time is above a threshold value.

12. The computer-readable medium of claim 11, wherein to generate the interactive prompt, the instructions further cause the one or more processors to:

determine a difference in distances to the destination along the initial route and the alternate route,

wherein the threshold value is a first threshold value, and

wherein generating the interactive prompt is in response to determining that the difference in distances is below a second threshold value.

13. The computer-readable medium of claim 10, wherein to determine the alternate route to the destination, the instructions cause the one or more processors to periodically check adverse conditions along the initial route, wherein the adverse conditions include one or more heavy traffic, lane closures, reported accidents, and adverse weather.

14. The computer-readable medium of claim 10, wherein to determine the boundaries of the dynamic rerouting window, the instructions further cause the one or more processors to:

determine a leading edge of the dynamic rerouting window corresponding to a projected position of the vehicle after a first predetermined period of time, at a current speed of the vehicle, and

determine a trailing edge of the dynamic rerouting window corresponding to a projected position of the vehicle after a second predetermined period of time, at the current speed of the vehicle.

15. The computer-readable medium of claim 10, wherein the instructions further cause the one or more processors to:

generate a first polyline made up of a first sequence of points to represent the original route;

generate second polyline up of a second sequence of points to represent the alternate route; and

compare the first sequence to the second sequence to determine the point of divergence.

16. The computer-readable medium of claim 10, wherein the instructions further cause the one or more processors to:

receive a confirmation via the interactive prompt that the alternate route has been selected; and

provide navigation directions to guide the vehicle along the alternate route to the destination.

17. The computer-readable medium of claim 10, wherein the initial navigation directions include a sequence of instructions provided as the vehicle follows the initial route, and wherein the instructions further cause the one or more processors to:

determine an amount of time remaining until a next one in the sequence of instructions is to be provided;

wherein generating the interactive prompt is further in response to determining that the amount of time is above a threshold value.

18. A computing device comprising:

a user interface configured to receive user input and provide output;

one or more processors; and

a non-transitory computer-readable medium storing thereon instructions for providing dynamic rerouting notifications, wherein the instructions, when executed on one or more processors, cause the computing device to;

generate initial navigation directions to guide a vehicle along an initial route between an origin and a destination;

when the vehicle is at a current location on the initial route, determine an alternate route to the destination, including determining a point of divergence between the initial route and the alternate route;

determine boundaries of a dynamic rerouting window in response to having determined the point of divergence, including determining the boundaries based on (i) a current speed of the vehicle and (ii) the current location of the vehicle with respect to the point of divergence; and

when the point of divergence is within the dynamic rerouting window, generate an interactive prompt to suggest that the alternate route be selected, wherein the interactive prompt is not generated when the point of divergence is outside the dynamic rerouting window.

19. The computing device of claim 18, wherein the user interface includes an audio speaker to provide voice announcements to a user.

20. The computing device of claim 18, wherein to generate the interactive prompt, the instructions further cause the computing device to:

determine a projected amount of time saved by selecting the alternate route,

wherein generating the interactive prompt is in response to determining that the projected amount of time is above a threshold value.

21. The computing device of claim 20, wherein to generate the interactive prompt, the instructions further cause the computing device to:

determine a difference in distances to the destination along the initial route and the alternate route,

wherein the threshold value is a first threshold value, and

wherein generating the interactive prompt is in response to determining that the difference in distances is below a second threshold value.