SYSTEMS AND METHODS FOR GENERATING PATTERN KEYS FOR USE IN NAVIGATION SYSTEMS TO PREDICT USER DESTINATIONS

• US 20090248288A1
• Filed: 01/19/2009
• Published: 10/01/2009
• Est. Priority Date: 03/31/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bell, David, Norton, Philip, Bygrave, Chris, Dineen, Oliver
• Granted Patent: US 8,229,666 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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:

an adaptive neural network 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 being represented in the adaptive neural network with corresponding starting and destination locations and one or more decision point locations between the starting and destination locations, wherein the decision point locations have associated weights that are adaptively learned using the obtained route information to represent user travel patterns,

the adaptive neural network being traversed in the automated navigation system to identify one or more predictable routes, wherein a predictable route is identified as a route through the adaptive neural network 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

memory media for storing the pattern keys.