Point of interest search along a route

• US 9,304,008 B2
• Filed: 04/01/2009
• Issued: 04/05/2016
• Est. Priority Date: 04/01/2008
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Poppen, Richard F., Tang, Weidong, Brownstone, Daniel R.
• Primary Examiner(s): Jabr, Fadey
• Assistant Examiner(s): Soofi, Yazan A
• Application Number:
  US12/936,128
• Publication Number:
  US 20110106429A1
• Time in Patent Office: 2,561 Days
• Field of Search: 701/201
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• 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/3626 Details of the output of route guidance instructions traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• 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 system includes a GPS module, user interface module, database and routing engine. To find nearby POIs in one embodiment the routing engine identifies POIs in the database located within a threshold distance from the planned route in Euclidean distance. The routing engine filters the results by exploring the road network to determine whether each of the POIs is within the threshold distance of the route in driving distance. The filtering may include exploring outward from the POI, until all roads within the threshold distance are explored or the route is reached; alternatively, distance to the POIs is checked by exploring outward from the route until all roads within the threshold distance of the route have been exposed. For those POIs reached in the exploration, the nearest point on the route and the distance to that point are known. Similar searches are performed based on driving time rather than distance.

Claims

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

determining, by a computer, a planned navigation route for a vehicle, the planned navigation route having an origin and a destination;

receiving, by the computer, a point of interest search request, the request received subsequent to a departure of the vehicle from the origin along the planned navigation route;

identifying, by a computer, at least one point of interest located within a first threshold distance of the planned navigation route;

identifying, by the computer, a route departure point, the route departure point located along the planned navigation route;

determining, by the computer, an along-route distance from a current location of the vehicle to the route departure point;

determining, by the computer, an off-route distance along at least one road from the route departure point to the point of interest; and

displaying in a user interface of a navigation device one or more indicia of the distance to the point of interest, the displayed indicia including the off-route distance.

2. The method of claim 1 wherein the identified points of interest are further located within a second threshold distance of the current location.

3. The method of claim 2 further comprising:

receiving user input indicating a preference for points of interest closer to the current location;

increasing the first threshold distance;

identifying at least one new point of interest located within the increased first threshold distance and the second threshold distance; and

displaying one or more indicia of the distance to the new point of interest.

4. The method of claim 3 wherein the user input is received via selection by the user of a single user interface element.

5. The method of claim 2 wherein the second threshold distance is specified as an estimated driving time.

6. The method of claim 2 wherein the second threshold distance is a radial distance.

7. The method of claim 2 wherein the second threshold distance is a driving distance.

8. The method of claim 2 wherein the second threshold distance is received as user input.

9. The method of claim 2 wherein the second threshold distance is associated with a category of the point of interest.

10. The method of claim 1 wherein the displayed indicia include the along-route distance.

11. The method of claim 1 wherein the displayed indicia include the total of the along-route distance and the off-route distance.

12. The method of claim 1 wherein the displayed indicia include the along-route distance and the total of the along-route distance and the off-route distance.

13. The method of claim 1 wherein the displayed indicia include the off-route distance and the total of the off-route distance and the along-route distance.

14. The method of claim 1 wherein the displayed indicia include the along-route distance and the off-route distance.

15. The method of claim 1 further comprising:

estimating a travel time from the current location to the point of interest, the travel time including an estimate of a travel time from the current location to the route departure point and an estimate of a travel time from the route departure point to the point of interest; and

displaying the estimated travel time from the current location to the point of interest in the user interface.

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

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

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

19. The method of claim 1 further comprising determining the current location using GPS.

20. The method of claim 1 wherein the point of interest is a restaurant.

21. The method of claim 1 wherein the point of interest is a hotel.

22. The method of claim 1 wherein the point of interest is a retail store.

23. The method of claim 1 wherein the point of interest is a gas station.

24. The method of claim 1 wherein the point of interest is an automobile repair facility.

25. The method of claim 1 wherein the point of interest is a medical facility.

26. The method of claim 1 further comprising:

receiving user input indicating a preference for points of interest farther from the current location;

decreasing the first threshold distance;

identifying a second point of interest, the second point of interest located within the original first distance and not located within the decreased first threshold distance; and

removing from the display indicia of the distance to the second point of interest.

27. The method of claim 26 wherein the user input is received via selection by the user of a single user interface element.

28. The method of claim 1 wherein the first threshold distance is specified as an estimated driving time.

29. The method of claim 1 wherein displaying one or more indicia of the distance to the point of interest further comprises displaying an estimated driving time to the point of interest.

30. The method of claim 29 wherein the indicia further comprises an estimated off-route driving time to the point of interest.

31. The method of claim 1 wherein the first threshold distance is a radial distance.

32. The method of claim 1 wherein the first threshold distance is a driving distance.

33. The method of claim 1 wherein a plurality of points of interest are identified and the indicia of the distance to the points of interest are displayed in order of increasing along-route distance.

34. The method of claim 1 wherein a plurality of points of interest are identified and the indicia of the distance to the points of interest are displayed in order of increasing total distance.

35. The method of claim 1 wherein a plurality of points of interest are identified and the indicia of the distance to the points of interest are displayed in order of increasing off-route distance.

36. The method of claim 1 wherein the first threshold distance is received as user input.

37. The method of claim 1 wherein the first threshold distance is associated with a category of the point of interest.

38. The method of claim 1 wherein the route departure point is the point on the route nearest to the point of interest measured in Euclidean distance.

39. The method of claim 1 wherein the off-route distance is the Euclidean distance from the route departure point to the point of interest.

40. The method of claim 1 wherein the route departure point is the point on the route from which the driving distance to the point of interest is minimized.

41. The method of claim 40 wherein the off-route distance is the driving distance along roads from the route departure point to the point of interest, and the along-route distance is the driving distance along the route from the current location to route departure point.

42. The method of claim 1 wherein the route departure point is a point on the route from which an estimated driving time to the point of interest is minimized.

43. The method of claim 42 wherein the off-route distance is an estimated driving time from the route departure point to the point of interest and the along-route distance is an estimated driving time from the current position to the route departure point.

44. The method of claim 1 wherein the route departure point is a point on the route such that the distance along the route to the point plus the distance from the point to the point of interest is minimized.

45. The method of claim 44 wherein distance is a driving distance.

46. The method of claim 44 wherein distance is an estimated driving time.

47. A method for providing routing to a point of interest, the method comprising:

inferring, by a routing engine, a user'"'"'s current route, the route not preprogrammed by the user;

identifying at least one point of interest located within a first threshold distance of the inferred route and a second threshold distance of a current location;

identifying a route departure point, the route departure point located along the inferred route;

determining an along-route distance from the current location to the route departure point;

determining an off-route distance from the route departure point to the point of interest; and

displaying in a user interface one or more indicia of the distance to the point of interest.

48. The method of claim 47 wherein inferring the user'"'"'s current route further comprises:

identifying a street name associated with the current location;

identifying a direction of travel associated with current movement of the user;

creating a route along the identified street name in the current direction of travel; and

inferring that the user'"'"'s current route is the created route.

50. The method of claim 47 wherein inferring the user'"'"'s current route further comprises:

retrieving a set of previously traveled routes;

identifying a previously traveled route including the current location and having a same direction of travel as a direction of travel associated with current movement of the user; and

inferring that the user'"'"'s current route is the identified previously traveled route.

51. The method of claim 47 wherein inferring the user'"'"'s current route further comprises:

retrieving a set of previous destinations;

identifying one or more of the retrieved destinations located in the user'"'"'s direction of travel;

selecting the identified destination being approached most rapidly by the user; and

inferring as the user'"'"'s route a route from the user'"'"'s current location to the selected identified definition.

49. The method of 48 wherein the created route continues past the termination of the identified street name along a second street, the second street having a direction approximating the direction of travel.

52. 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 at least one point of interest stored in the database and located within a first threshold distance of a planned navigation route;

identify a route departure point, the route departure point located along the planned navigation route;

determine an along-route distance from a current location to the route departure point;

determine an off-route distance along at least one road from the route departure point to the point of interest; 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, the indicia including the off-route distance.

53. The system of claim 52 wherein the global navigation satellite system radio is a GPS radio.

54. 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:

inferring a user'"'"'s current route;

identifying at least one point of interest located within a first threshold distance of the inferred route and a second threshold distance of a current location;

identifying a route departure point, the route departure point located along the inferred route;

determining an along-route distance from the current location to the route departure point;

determining an off-route distance from the route departure point to the point of interest; and

displaying in a user interface one or more indicia of the distance to the point of interest, the indicia including the off-route distance.