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

Patent metadata

Field	Value
Publication number	US-9869563-B2
Application number	US-201414785406-A
Country	US
Kind code	B2
Filing date	Apr 17, 2014
Priority date	Apr 17, 2013
Publication date	Jan 16, 2018
Grant date	Jan 16, 2018

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.

First claim

The invention claimed is:

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.

Assignees

• Tomtom Navigation Bv
• Tomtom Int Bv

Inventors

• Broadbent Samuel Mark
• Geelen Pieter Andreas
• Hareau Stéphane
• Santiago Nunez Jose F

Classifications

• G01C21/3697

  Output of additional, non-guidance related information, e.g. low fuel level (G01C21/3679 takes precedence) · CPC title

• G01C21/3453 Primary

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• G01C21/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 title

• G08G1/096827

  where the route is computed onboard · CPC title

• G01C21/3691 Primary

  Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions (arrangements for giving variable traffic instructions G08G1/09) · CPC title