Method and apparatus for predicting a destination using a route search algorithm

• US 9,869,563 B2
• Filed: 04/17/2014
• Issued: 01/16/2018
• Est. Priority Date: 04/17/2013
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom International BV (TomTom NV)
• Inventors: Broadbent, Samuel Mark, Geelen, Pieter Andreas, Hareau, Stphane, Santiago Nunez, Jose F.
• Primary Examiner(s): LANG, MICHAEL DEAN
• Application Number:
  US14/785,406
• Publication Number:
  US 20160097649A1
• Time in Patent Office: 1,370 Days
• 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/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• 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/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G01C 21/3691 Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions arrangements for giving variable traffic instructions G08G1/09
• CPC Class Codes: G01C 21/3694 Output thereof on a road map
• CPC Class Codes: G01C 21/3697 Output of additional, non-guidance related information, e.g. low fuel level G01C21/3679 takes precedence
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality

Abstract

A method of predicting a destination of a user of a mobile device is described, together with a device for performing the same. The method comprises determining a location of the mobile device, and executing a route search algorithm with respect to a trip data-base. The trip database stores information indicative of a personal road network of a user of the mobile device, one or more road segments in the personal road network being associated with a respective destination location, and cost information associated with road segments in the personal network, the cost information being based, at least in part, on traversal information in the trip database.

Claims

1. A mobile device, comprising a processor communicably coupled to a trip database storing information indicative of a personal road network of roads previously traveled by a user of the mobile device, one or more road segments in the personal road network being associated with a respective destination location,

wherein the processor performs operations for a prediction module that:

selects a given road segment from the personal network based on a current location of the mobile device;

executes a route search algorithm to generate a route based on costs associated with road segments, the route search starting from the given road segment from the personal network, wherein the cost for each road segment is computed based on attributes associated with traversing the road segment, and wherein the cost for each road segment is reduced when the road segment is included in the personal road network;

determines a destination of a user of a mobile device based on the route; and

provides the destination to the user for selection as a destination of a current journey.

2. The mobile device of claim 1, wherein the traversal information is indicative of a number of times each road segment in the personal network has been traversed by the user.

3. The mobile device of claim 1, wherein the road segment selected as the start location has a location corresponding to, or within a predetermined distance of, the current location.

4. The mobile device of claim 1, wherein the prediction module determines the destination based on a current time and time information stored in the trip database indicative of a time of traversal of associated road segments in the personal network.

5. The mobile device of claim 4, wherein the prediction module selects a road segment from the personal network based on the current location of the mobile device and performs the route search using the road segment as a start location when the current time corresponds to the time information.

6. The mobile device of claim 5, wherein the time information indicates one of a plurality of periods of time during which the road segment was traversed, and the current time corresponds to the time information when matching, or within a predetermined number of time periods of, the current time.

7. The mobile device of claim 1, wherein the processor is communicably coupled to a favourites database storing information indicative of one or more points of interest (POIs) selected by the user.

8. The mobile device of claim 7, wherein the one or more road segments in the personal network associated with a destination location are associated with POIs in the favourites database.

9. The mobile device of claim 1, wherein the personal network of the user comprises a plurality of road segments previously traversed by the user of the mobile device in one or more journeys.

10. The mobile device of claim 1, comprising a display device, wherein the prediction module provides a suggested destination interface comprising the determined destination.

11. The mobile device of claim 1, wherein the prediction module provides one or more further, less likely, destinations.

12. A method of determining a destination of a user of a mobile device, the mobile device being coupled to a trip database storing information indicative of a personal road network of roads previously traveled by a user of the mobile device, one or more road segments in the personal road network being associated with a respective destination location, the method comprising:

selecting a given road segment from the personal network based on a current location of the mobile device;

executing a route search algorithm to generate a route based on costs associated with road segments, the route search starting from the given road segment from the personal network, wherein the cost for each road segment is computed based on attributes associated with traversing the road segment, and wherein the cost for each road segment is reduced when the road segment is included in the personal road network;

determining the destination based on the route; and

providing the destination to the user for selection as a destination of a current journey.

13. The method of claim 12, wherein the destination is a destination location associated with a road segment found by the route search algorithm.

14. The method of claim 12, wherein the determining of the destination based on a current time and time information stored in the trip database indicative of a time of traversal of associated road segments in the personal network.

15. The method of claim 12, wherein the one or more road segments in the personal network associated with a destination location are associated with user-selected points of interest (POIs) stored in a favourites database.

16. The method of claim 12, comprising providing the determined destination to the user for selection as a destination of a current journey.

17. A non-transitory computer readable medium comprising computer software operable, when executed, to cause one or more processors coupled to a trip database storing information indicative of a personal road network of roads previously traveled by a user of a mobile device, one or more road segments in the personal road network being associated with a respective destination location, to perform a method of determining a destination of a user of the mobile device, the method comprising:

selecting a given road segment from the personal network based on a current location of the mobile device;

executing a route search algorithm to generate a route based on costs associated with road segments, the route search starting from the given road segment from the personal network, wherein the cost for each road segment is computed based on attributes associated with traversing the road segment, and wherein the cost for each road segment is reduced when the road segment is included in the personal road network;

determining the destination based on the route; and

providing the destination to the user for selection as a destination of a current journey.