Point of interest search along a route with return

• US 10,444,026 B2
• Filed: 09/14/2017
• Issued: 10/15/2019
• Est. Priority Date: 04/01/2009
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Poppen, Richard F., Tang, Weidong
• Primary Examiner(s): Dager, Jonathan M
• Application Number:
  US15/704,913
• Publication Number:
  US 20180023969A1
• Time in Patent Office: 761 Days
• Field of Search: None
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• 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/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G01C 21/3605 Destination input or retrieval
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence
• CPC Class Codes: G01S 19/42 Determining position

Abstract

A routing module identifies POIs that can be reached from a route with a cost less than distance m. A routing engine performs a reverse exploration on nodes in the planned route to locate POIs from which the route can be reached with a cost of less than a second cost n. POIs identified as being reachable from the route with a cost of less than m, and from which the route is reachable with a cost less than n are then further filtered to identify a subset of the POIs for which the sum of the time or distance from the route to the POI and the time or distance from the POI back to the route is less than a threshold time or distance, t.

Claims

1. A computer-implemented method for providing routing to a point of interest, the method comprising:

determining, by one or more processors, a first cost to reach a destination along a first navigation route from a current location of a computing device, the first cost less than a second cost to reach the destination along a second navigation route from the current location;

determining, by the one or more processors, a third cost to detour to the point of interest from the first navigation route and to reach the destination from the point of interest along the first navigation route;

determining, by the one or more processors, a fourth cost to detour to the point of interest from the second navigation route and to reach the destination from the point of interest along the second navigation route; and

in response to determining that the fourth cost is less than the third cost, providing the second navigation route for presentation on the computing device.

2. The computer-implemented method of claim 1, wherein the first cost and the second cost are determined based on a first distance of the first navigation route and a second distance of the second navigation route, respectively, the first distance shorter than the second distance.

3. The computer-implemented method of claim 2, further comprising:

determining, by the one or more processors, that the point of interest is a first detour distance from the first navigation route and a second detour distance from the second navigation route, the first detour distance greater than the second detour distance.

4. The computer-implemented method of claim 2, further comprising:

determining, by the one or more processors, that the point of interest is less than a threshold distance from the second navigation route, the threshold distance greater than a difference between the first distance and the second distance.

5. The computer-implemented method of claim 1, wherein the first cost and the second cost are determined based on a first time of the first navigation route and a second time of the second navigation route, respectively, the first time shorter than the second time.

6. The computer-implemented method of claim 1, further comprising:

determining, by the one or more processors, that a detour time from the second navigation route to the point of interest is different than a return time from the point of interest to the second navigation route.

7. The computer-implemented method of claim 6, wherein the detour time is from a freeway exit of the second navigation route and the return time is to a freeway on-ramp of the second navigation route, the freeway on-ramp and the freeway exit located at different portions of the second navigation route.

8. The computer-implemented method of claim 6, wherein an average of the detour time and the return time is less than a threshold time.

9. The computer-implemented method of claim 8, wherein at least one of the detour time and the return time is greater than the threshold time.

10. A non-transitory computer-readable storage medium storing instructions for providing routing to a point of interest, the instructions when executed by one or more processors cause the one or more processors to perform steps including:

determining, by one or more processors, a first cost to reach a destination along a first navigation route from a current location of a computing device, the first cost less than a second cost to reach the destination along a second navigation route from the current location;

determining, by the one or more processors, a third cost to detour to the point of interest from the first navigation route and to reach the destination from the point of interest along the first navigation route;

determining, by the one or more processors, a fourth cost to detour to the point of interest from the second navigation route and to reach the destination from the point of interest along the second navigation route; and

in response to determining that the fourth cost is less than the third cost, providing the second navigation route for presentation on the computing device.

11. The non-transitory computer-readable storage medium of claim 10, wherein the first cost and the second cost are determined based on a first distance of the first navigation route and a second distance of the second navigation route, respectively, the first distance shorter than the second distance.

12. The non-transitory computer-readable storage medium of claim 11, having further instructions that when executed by the one or more processors cause the one or more processors to perform further steps including:

determining, by the one or more processors, that the point of interest is a first detour distance from the first navigation route and a second detour distance from the second navigation route, the first detour distance greater than the second detour distance.

13. The non-transitory computer-readable storage medium of claim 11, having further instructions that when executed by the one or more processors cause the one or more processors to perform further steps including:

determining, by the one or more processors, that the point of interest is less than a threshold distance from the second navigation route, the threshold distance greater than a difference between the first distance and the second distance.

14. The non-transitory computer-readable storage medium of claim 10, wherein the first cost and the second cost are determined based on a first time of the first navigation route and a second time of the second navigation route, respectively, the first time shorter than the second time.

15. The non-transitory computer-readable storage medium of claim 10, having further instructions that when executed by the one or more processors cause the one or more processors to perform further steps including:

determining, by the one or more processors, that a detour time from the second navigation route to the point of interest is different than a return time from the point of interest to the second navigation route.

16. The non-transitory computer-readable storage medium of claim 15, wherein the detour time is from a freeway exit of the second navigation route and the return time is to a freeway on-ramp of the second navigation route, the freeway on-ramp and the freeway exit located at different portions of the second navigation route.

17. The non-transitory computer-readable storage medium of claim 15, wherein an average of the detour time and the return time is less than a threshold time.

18. The non-transitory computer-readable storage medium of claim 17, wherein at least one of the detour time and the return time is greater than the threshold time.

19. A system for providing routing to a point of interest, comprising:

a global navigation satellite system radio configured to determine a current location of the system;

a routing engine coupled to the global navigation satellite system radio and configured to;

determine, by one or more processors, a first cost to reach a destination along a first navigation route from the current location, the first cost less than a second cost to reach the destination along a second navigation route from the current location;

determine, by the one or more processors, a third cost to detour to the point of interest from the first navigation route and to reach the destination from the point of interest along the first navigation route;

determine, by the one or more processors, a fourth cost to detour to the point of interest from the second navigation route and to reach the destination from the point of interest along the second navigation route; and

a user interface coupled to the routing engine and configured to provide the second navigation route for presentation on the system in response to determining that the fourth cost is less than the third cost.

20. The system of claim 19, wherein the first cost and the second cost are determined based on a first distance of the first navigation route and a second distance of the second navigation route, respectively, the first distance shorter than the second distance, and wherein the routing engine is further configured to:

determine, by the one or more processors, that the point of interest is less than a threshold distance from the second navigation route, the threshold distance less than a difference between the first distance and the second distance.