Generating and using pattern keys in navigation systems to predict user destinations

• US 8,229,666 B2
• Filed: 01/19/2009
• Issued: 07/24/2012
• Est. Priority Date: 03/31/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bell, David, Bygrave, Chris, Dineen, Oliver, Norton, Philip
• Primary Examiner(s): Tran, Dalena
• Application Number:
  US12/355,901
• Publication Number:
  US 20090248288A1
• Time in Patent Office: 1,282 Days
• Field of Search: 701 23- 27, 701208-210, 701213-214, 701200-202, 701/400, 701408-411, 701/426, 701/438, 701/461, 701/462, 701/467, 701/468, 701/540, 342/357.01, 342/357.1, 342/357.08, 340988-990, 340/995, 370/351
• US Class Current: 701/400
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement

Abstract

Systems and methods for automatically generating pattern keys based on models of user travel patterns and behavior, wherein the pattern keys may be used in automated navigation systems for fast and efficient prediction of user destinations.

Claims

1. A system for automatically generating pattern keys for use by an automated navigation system to provide navigational assistance, comprising:

a predictive model constructed using obtained route information wherein the route information includes routes traveled by a user, and route information for a given route comprises a starting location, a destination location, and one or more decision point locations along the route from the starting location to the destination location, the routes traveled by the user represented in the predictive model with corresponding starting and destination locations and one or more decision point locations between the starting and destination locations, wherein the predictive model learns weights associated with the decision point locations using the obtained route information to represent user travel patterns, the predictive model being used in the automated navigation system to identify one or more predictable routes of the user, wherein a predictable route is identified as a route by the predictive model in which beginning from a starting location of the route, a destination location can be predicted with a probability that exceeds a threshold value, based on weights associated with a subset of one or more decision point locations in a beginning portion of the route following the starting location;

a pattern key generator configured to generate a pattern key for each identified predictable route, which comprises the destination location and the subset of one or more decision point locations sufficient to determine that the probability exceeds the threshold value with the remaining decision points in the sequence being omitted from the pattern key; and

a non-transitory computer readable medium for storing the pattern keys.

2. The system of claim 1, wherein the identified predictable route has the highest probability of the routes of predicting the destination location.

3. The system of claim 1, wherein the starting location, destination location, and decision point locations comprise GPS coordinates.

4. The system of claim 1, wherein the predictive model is further configured for determining a plurality of actual decision point locations along an actual user travel path, matching the plurality of actual decision point locations to a subset of the decision point locations associated with the stored plurality of pattern keys, and predicting a travel destination location for the actual user travel path as the destination location associated with the stored pattern key with a matching subset of the plurality of decision point locations, wherein the matching subset is sufficient to determine that a probability that this destination location is the travel destination location for the actual user travel path exceeds a threshold value based on weights associated with the subset of decision point locations.

5. A method for automatically generating pattern keys for use by an automated navigation system to provide navigational assistance, the method comprising:

using a computer to execute steps comprising;

obtaining route information regarding routes traveled by a user, wherein route information for a given route comprises a starting location, a destination location and one or more decision point locations along the route from the starting location to the destination location;

using the obtained route information to build a predictive model, in which the routes traveled by the user are represented with starting and destination locations and one or more decision point locations between the starting and destination locations, wherein the predictive model learns weights associated with the decision point locations using the obtained route information to represent user travel patterns;

identifying one or more predictable routes of the user, wherein a predictable route is identified as a route having a starting location and a destination location that has a probability that exceeds a threshold value, based on the weights associated with one or more decision point locations of the route following the starting location;

generating a pattern key for each identified predictable route, which comprises the destination location and the subset of one or more decision point locations sufficient to determine that the probability exceeds the threshold value with the remaining decision points in the sequence being omitted from the pattern key; and

storing the pattern keys in a non-transitory memory.

6. The method of claim 5, wherein the identified predictable route has the highest probability of the routes of predicting the destination location.

7. The method of claim 5, further comprising:

determining a plurality of actual decision point locations along an actual user travel path;

matching the plurality of actual decision point locations to a subset of the decision point locations associated with the stored pattern keys; and

predicting a travel destination location for the actual user travel path as the destination location associated with the stored pattern key with a matching subset of the plurality of decision point locations.

8. A non-transitory computer-readable storage medium for automatically generating pattern keys for use by an automated navigation system to provide navigational assistance, the non-transitory computer-readable storage medium comprising computer program code, coded on the medium, providing instructions for:

obtaining route information regarding routes traveled by a user, wherein route information for a given route comprises a starting location, a destination location and one or more decision point locations along the route from the starting location to the destination location;

using the obtained route information to build a predictive model, in which the routes traveled by the user are represented with starting and destination locations and one or more decision point locations between the starting and destination locations, wherein the predictive model learns weights associated with the decision point locations using the obtained route information to represent user travel patterns;

identifying one or more predictable routes of the user, wherein a predictable route is identified as a route having a starting location and a destination location that has a probability that exceeds a threshold value, based on the weights associated with one or more decision point locations of the route following the starting location;

generating a pattern key for each identified predictable route, which comprises the destination location and the subset of one or more decision point locations sufficient to determine that the probability exceeds the threshold value with the remaining decision points in the sequence being omitted from the pattern key; and

storing the pattern keys in a non-transitory memory.

9. The non-transitory computer-readable storage medium of claim 8, wherein the identified predictable route has the highest probability of the routes of predicting the destination location.

10. The non-transitory computer-readable storage medium of claim 8, further comprising computer program code, coded on the medium, providing instructions for:

determining a plurality of actual decision point locations along an actual user travel path;

matching the plurality of actual decision point locations to a subset of the decision point locations associated with the stored pattern keys; and

predicting a travel destination location for the actual user travel path as the destination location associated with the stored pattern key with a matching subset of the plurality of decision point locations.

11. A method for predicting a destination in a navigational system using a stored pattern key, the method comprising:

using a computer to execute steps comprising;

storing a plurality of pattern keys, a pattern key identifying a predictable route, the pattern key including a a starting point, a destination location and a subset of a set of identified decision point locations of the route leading to the destination location, each identified decision point location having a weight;

determining a plurality of actual decision point locations along an actual user travel path;

matching the plurality of actual decision point locations to a subset of the decision point locations associated with at least one of the stored plurality of pattern keys;

responsive to the probability of matching the plurality of actual decision point locations to the subset of the decision point locations associated with a selected pattern key exceeding a threshold value, modifying the selected pattern key for the actual user travel path, the modified pattern key containing a reduced subset of decision point locations; and

predicting a travel destination location for the actual user travel path as the destination location using the modified pattern key.

12. The method of claim 11, wherein the predictable route further comprises a starting location and the matching further comprises matching one of the plurality of actual decision point locations to the starting location.

13. The method of claim 11, wherein determining the plurality of actual decision point locations along the actual user travel path further comprises:

determining a point along a current path of the actual user; and

adding the point along the current path of the actual user as one of the plurality of actual decision point locations.

14. The method of claim 11, further comprising predicting the travel destination location earlier in the actual user travel path by lowering the threshold value for the probability that the destination location associated with the pattern key is the travel destination location for the actual user travel path.

15. A non-transitory computer-readable storage medium for predicting a destination in a navigational system using a stored pattern key, the non-transitory computer-readable storage medium comprising computer program code, coded on the medium, providing instructions for:

storing a plurality of pattern keys, a pattern key identifying a predictable route, the pattern key including a a starting point, a destination location, and a subset of a set of identified decision point locations of the route leading to the destination location, each identified decision point location having a weight;

determining a plurality of actual decision point locations along an actual user travel path;

matching the plurality of actual decision point locations to a subset of the decision point locations associated with at least one of the stored plurality of pattern keys;

responsive to the probability of matching the plurality of actual decision point locations to the subset of the decision point locations associated with a selected pattern key exceeding a threshold value, modifying the selected pattern key for the actual user travel path, the modified pattern key containing a reduced subset of decision point locations; and

predicting a travel destination location for the actual user travel path as the destination location using the modified pattern key.

16. The non-transitory computer-readable storage medium of claim 15, wherein determining the plurality of actual decision point locations along the actual user travel path further comprises:

determining a point along a current path of the actual user; and

adding the point along the current path of the actual user as one of the plurality of actual decision point locations.

17. The non-transitory computer-readable storage medium of claim 15, further comprising computer program code, coded on the medium, providing instructions for predicting the travel destination location earlier in the actual user travel path by lowering the threshold value for the probability that the destination location associated with the pattern key is the travel destination location for the actual user travel path.

18. A system for predicting a destination in a navigational system using a stored pattern key, the system comprising:

a plurality of pattern keys, a pattern key identifying a predictable route, the pattern key including a a starting point, a destination location and a subset of a set of identified decision point locations of the route leading to the destination location, each identified decision point location having a weight;

a non-transitory computer-readable storage medium for storing the plurality of pattern keys; and

a predictive model for determining a plurality of actual decision point locations along an actual user travel path, matching the plurality of actual decision point locations to a subset of the decision point locations associated with at least one of the stored plurality of pattern keys;

a pattern key generator for, responsive to the probability of matching the plurality of actual decision point locations to the subset of the decision point locations associated with a selected pattern key exceeding a threshold value, modifying the selected pattern key for the actual user travel path, the modified pattern key containing a reduced subset of decision point locations; and

the predictive model for predicting a travel destination location for the actual user travel path as the destination location using the modified pattern key.

19. The system of claim 18, wherein the predictive model further is configured for determining a point along a current path of the actual user and adding the point along the current path of the actual user as one of the plurality of actual decision point locations.

20. The system of claim 18, wherein the predictive model is further configured for predicting the travel destination location earlier in the actual user travel pathby lowering the threshold value for the probability that the destination location associated with the pattern key is the travel destination location for the actual user travel path.