Generating attribute models for use in adaptive navigation systems

• US 7,680,749 B1
• Filed: 11/02/2006
• Issued: 03/16/2010
• Est. Priority Date: 11/02/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rasmussen, Jens Eilstrup, Golding, Andrew R.
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US11/556,128
• Time in Patent Office: 1,230 Days
• Field of Search: 706/14, 706/45, 701/207, 382/153
• US Class Current: 706/14
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

Abstract

Adaptive navigation techniques are disclosed that allow navigation systems to learn from a user'"'"'s personal driving history. As a user drives, models are developed and maintained to learn or otherwise capture the driver'"'"'s personal driving habits and preferences. Example models include road speed, hazard, favored route, and disfavored route models. Other attributes can be used as well, whether based on the user'"'"'s personal driving data or driving data aggregated from a number of users. The models can be learned under explicit conditions (e.g., time of day/week, driver ID) and/or under implicit conditions (e.g., weather, drivers urgency, as inferred from sensor data). Thus, models for a plurality of attributes can be learned, as well as one or more models for each attribute under a plurality of conditions. Attributes can be weighted according to user preference. The attribute weights and/or models can be used in selecting a best route for user.

Claims

1. A machine-readable medium encoded with instructions, that when executed by one or more processors, cause the processor to carry out a process for generating attribute models for use in a navigation system, the process comprising:

computing a value for each desired attribute along one or more road segments covered by each driving session for a user;

computing a default value for unseen road segments not yet traveled; and

forming one or more attribute models for each attribute based on the corresponding attribute values.

2. The machine-readable medium of claim 1, the process further comprising:

learning conditional variants for at least one of the one or more attribute models.

3. The machine-readable medium of claim 2 wherein learning conditional variants comprises determining if at least one of an explicit and implicit condition applies to a particular conditional variant of a model.

4. The machine-readable medium of claim 3 wherein for explicit conditions, learning conditional variants further comprises:

defining a data bucket for an explicit condition of a target attribute;

storing attribute data computed for one or more road segments from a plurality of driving sessions into the appropriate buckets; and

forming a conditional variant model for each bucket based on the attribute data in that bucket.

5. The machine-readable medium of claim 4, the process further comprising:

repeating the defining, storing, and forming a conditional variant model for each of a plurality of attributes.

6. The machine-readable medium of claim 3 wherein for implicit conditions, learning conditional variants further comprises:

for each driving session, forming a mini-model for a target attribute by statistically merging attribute data computed for that driving session;

identifying pairs of like mini-models using a similarity metric; and

forming a conditional variant model based on attribute data from pairs of like mini-models.

7. The machine-readable medium of claim 6, the process further comprising:

in response to a stopping criterion not being met, repeating the identifying and forming a conditional variant model until the stopping criterion is met.

8. The machine-readable medium of claim 7, the process further comprising:

repeating the forming a mini-model, identifying, forming a conditional variant model, and repeating for each of a plurality of attributes.

9. The machine-readable medium of claim 3 wherein for both explicit and implicit conditions applying to a particular conditional variant of a model, learning conditional variants further comprises:

partitioning attribute data computed for one or more road segments from a plurality of driving sessions into appropriate data buckets by explicit conditions; and

clustering attribute data within a data bucket based on a similarity metric to form implicit conditional variants within each explicit condition.

10. The machine-readable medium of claim 3 wherein for both explicit and implicit conditions applying to a particular conditional variant of a model, learning conditional variants further comprises:

forming a mini-model for a target attribute by statistically merging attribute data computed for a corresponding driving session;

identifying pairs of like mini-models using a similarity metric;

forming an implicit conditional variant model based on attribute data from pairs of like mini-models; and

partitioning attribute data within each implicit conditional variant model into appropriate data buckets by explicit conditions.

11. The machine-readable medium of claim 1, the process further comprising:

storing the one or more attribute models and any conditional variants, so that they can subsequently be accessed by a route generator.

12. The machine-readable medium of claim 1 wherein at least one of the one or more attribute models provides a summary statistic of attribute values that have been observed during driving sessions on a particular segment.

13. The machine-readable medium of claim 1 wherein computing a value for each desired attribute comprises:

applying attribute estimation rules to sensor data to compute the value for each desired attribute.

14. The machine-readable medium of claim 1 wherein computing a default value for unseen road segments comprises:

computing a summary statistic based on attribute values that have been observed.

15. A method for generating attribute models for use in a navigation system, the process comprising:

computing a value for each desired attribute along one or more road segments covered by each driving session for a user;

computing a default value for unseen road segments not yet traveled; and

forming one or more attribute models for each attribute based on the corresponding attribute values.

16. The method of claim 15 further comprising:

learning conditional variants for at least one of the one or more attribute models.

17. The method of claim 16 wherein learning conditional variants comprises determining if at least one of an explicit and implicit condition applies to a particular conditional variant of a model.

18. The method of claim 17 wherein for explicit conditions, learning conditional variants further comprises:

defining a data bucket for an explicit condition of a target attribute;

storing attribute data computed for one or more road segments from a plurality of driving sessions into the appropriate buckets; and

forming a conditional variant model for each bucket based on the attribute data in that bucket.

19. The method of claim 18 further comprising:

repeating the defining, storing, and forming a conditional variant model for each of a plurality of attributes.

20. The method of claim 17 wherein for implicit conditions, learning conditional variants further comprises:

for each driving session, forming a mini-model for a target attribute by statistically merging attribute data computed for that driving session;

identifying pairs of like mini-models using a similarity metric; and

forming a conditional variant model based on attribute data from pairs of like mini-models.

21. The method of claim 20 further comprising:

in response to a stopping criterion not being met, repeating the identifying and forming a conditional variant model until the stopping criterion is met.

22. The method of claim 21 further comprising:

repeating the forming a mini-model, identifying, forming a conditional variant model, and repeating for each of a plurality of attributes.

23. The method of claim 17 wherein for both explicit and implicit conditions applying to a particular conditional variant of a model, learning conditional variants further comprises:

partitioning attribute data computed for one or more road segments from a plurality of driving sessions into appropriate data buckets by explicit conditions; and

clustering attribute data within a data bucket based on a similarity metric to form implicit conditional variants within each explicit condition.

24. The method of claim 17 wherein for both explicit and implicit conditions applying to a particular conditional variant of a model, learning conditional variants further comprises:

forming a mini-model for a target attribute by statistically merging attribute data computed for a corresponding driving session;

identifying pairs of like mini-models using a similarity metric;

forming an implicit conditional variant model based on attribute data from pairs of like mini-models; and

partitioning attribute data within each implicit conditional variant model into appropriate data buckets by explicit conditions.

25. The method of claim 15 further comprising:

storing the one or more attribute models and any conditional variants, so that they can subsequently be accessed by a route generator.

26. The method of claim 15 wherein at least one of the one or more attribute models provides a summary statistic of attribute values that have been observed during driving sessions on a particular segment.

27. The method of claim 15 wherein computing a value for each desired attribute comprises:

applying attribute estimation rules to sensor data to compute the value for each desired attribute.

28. The method of claim 15 wherein computing a default value for unseen road segments comprises:

computing a summary statistic based on attribute values that have been observed.

29. A system for generating attribute models for use in a navigation system, the process comprising:

means for computing a value for each desired attribute along one or more road segments covered by each driving session for a user;

means for computing a default value for unseen road segments not yet traveled; and

means for forming one or more attribute models for each attribute based on the corresponding attribute values.

30. The system of claim 29 further comprising:

means for learning conditional variants for at least one of the one or more attribute models.