Point of interest search along a route with return

• US 8,401,786 B2
• Filed: 09/27/2011
• Issued: 03/19/2013
• Est. Priority Date: 04/01/2009
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Decarta (Uber Technologies, Inc.)
• Inventors: Poppen, Richard F., Tang, Weidong
• Primary Examiner(s): Dager, Jonathan M
• Application Number:
  US13/246,201
• Publication Number:
  US 20120123678A1
• Time in Patent Office: 539 Days
• Field of Search: None
• US Class Current: 701/468
• 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 method for providing routing to a point of interest, the method comprising:

identifying, by a computer, a first set of points of interest, each point of interest in the first set reachable from a planned navigation route with a cost less than a first threshold cost;

identifying, by the computer, a second set of points of interest, the planned navigation route reachable from each point of interest in the second set with a cost less than a second threshold cost;

determining, by the computer, a third set of points of interest, the third set including only the points of interest in both the first and second set;

determining a fourth set of points of interest, the fourth set including only the points of interest in the third set wherein a cost to reach the point of interest from the route plus a cost to return to the route from the point of interest is less than a third threshold cost; and

displaying the fourth set of points of interest in a user interface of a navigation device.

2. The method of claim 1 wherein the third threshold cost is a driving distance.

3. The method of claim 1 wherein the third threshold cost is an estimated driving time.

7. The method of claim 1 wherein displaying the fourth set of points further comprises displaying one or more indicia of a distance to each of the points of interest.

8. The method of claim 1 wherein displaying the fourth set of points further comprises displaying one or more indicia of a driving time to each of the points of interest.

9. The method of claim 1 wherein displaying the fourth set of points further comprises displaying one or more indicia of extra driving time incurred by deviating to each of the points of interest.

10. The method of claim 1 wherein displaying the fourth set of points further comprises displaying one or more indicia of extra driving distance incurred by deviating to each of the points of interest.

11. The method of claim 1 wherein the planned navigation route is an automobile route.

12. The method of claim 1 wherein the planned navigation route is a marine route.

13. The method of claim 1 wherein the planned navigation route is an aviation route.

14. The method of claim 1 wherein the third threshold cost is a radial distance.

15. The method of claim 1 wherein the third threshold cost is received as user input.

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

a database storing point of interest data;

a global navigation satellite system radio, adapted to determine a current location of a user;

a routing engine, coupled to the global navigation satellite system radio and the database, adapted to;

identify a first set of points of interest, each point of interest in the first set reachable from a planned navigation route with a cost less than a first threshold cost;

identify a second set of points of interest, the planned navigation route reachable from each point of interest in the second set with a cost less than a second threshold cost;

determine a third set of points of interest, the third set including only the points of interest in both the first and second set;

determine a fourth set of points of interest, the fourth set including only the points of interest in the third set wherein a cost to reach the point of interest from the route plus a cost to return to the route from the point of interest is less than a third threshold cost; and

a user interface module, coupled to the routing engine, adapted to display one or more indicia of the distance to the point of interest.

5. The method of claim 4 wherein the global navigation satellite system radio is a GPS radio.

6. A computer program product for providing routing to a point of interest, the computer program product stored on a non-transitory computer-readable medium and including instructions adapted to cause a computer to execute steps comprising:

identifying a first set of points of interest, each point of interest in the first set reachable from a planned navigation route with a cost less than a first threshold cost;

identifying a second set of points of interest, the planned navigation route reachable from each point of interest in the second set with a cost less than a second threshold cost;

determining a third set of points of interest, the third set including only the points of interest in both the first and second set;

determining a fourth set of points of interest, the fourth set including only the points of interest in the third set wherein a cost to reach the point of interest from the route plus a cost to return to the route from the point of interest is less than a third threshold cost; and

displaying the fourth set of points of interest in a user interface of a navigation device.