Adaptive and personalized navigation system

• US 7,512,487 B1
• Filed: 11/02/2006
• Issued: 03/31/2009
• 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): Tran; Khoi
• Assistant Examiner(s): AMIN, BHAVESH V
• Application Number:
  US11/556,120
• Time in Patent Office: 880 Days
• Field of Search: 701/200, 701/201, 701/208, 701/209, 701/207, 701/210, 701/202, 706/16, 706/20, 706/28, 706/54, 707/6, 703/2, 340/995.22, 340/995.23
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers

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 storage medium encoded with instructions, that when executed by one or more processors, cause the processor to carry out a process for generating directions for use in navigation during a current driving session, the process comprising:

storing a plurality of target attributes;

for at least a selection of the stored target attributes, storing a plurality of conditional variant models associated with the selected target attributes;

receiving a route request from a user, including a target destination;

generating a set of candidate routes;

computing a score for each candidate route based on one or more attribute models learned from previous user driving sessions, wherein computing comprises;

probabilistically determining for a target attribute that is one of the selected target attributes which of the plurality of conditional variant models associated with the target attribute currently corresponds to a condition of the target attribute; and

applying the determined conditional variant model to the target attribute; and

providing at least one scored route to the user.

2. 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 one or more driving sessions.

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

receiving current time and user location data for use in time-sensitive route generation.

4. The machine-readable medium of claim 1 wherein probabilistically determining which of the plurality of conditional variant models associated with the target attribute currently corresponds to a condition of the target attribute comprises:

determining if a conditional variant corresponds to an explicit or implicit condition.

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

in response to the conditional variant corresponding to an explicit condition, assigning a probability of 1 to a conditional variant model that corresponds to the explicit condition, and assigning a probability of 0 to other conditional variant models associated with the target attribute.

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

in response to the conditional variant corresponding to an implicit condition, assigning a probability to each conditional variant model associated with the target attribute, using Bayesian reasoning and observed data of the current driving session.

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

recomputing probabilities periodically during the current driving session, using subsequently observed data of the current driving session.

8. The machine-readable medium of claim 1 wherein computing a score for each candidate route further comprises:

computing a value of the target attribute based on a conditional variant model having a highest probability of being applicable to the current driving session.

9. The machine-readable medium of claim 1 wherein computing a score for each candidate route further comprises:

predicting a value for the target attribute using a combination of the conditional variant models for the attribute.

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

assigning an attribute weight to each target attribute of each candidate route, based on attribute preferences of the user;

wherein computing a score for each candidate route includes computing the score using target attribute values computed using the one or more attribute models, and the attribute weights.

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

adjusting the attribute weights based on subsequent user input.

12. The machine-readable medium of claim 10, the process further comprising:

sorting the candidate routes based on their scores;

wherein providing at least one scored route to the user includes providing a plurality of high scoring routes for user selection.

13. The machine-readable medium of claim 12, the process further comprising:

receiving a selected route from the user; and

determining if the attribute weights need to be adjusted based on that user selection.

14. The machine-readable medium of claim 13, the process further comprising:

in response to the attribute weights needing to be adjusted based on that user selection, adjusting the attribute weights based on the user selection.

15. The machine-readable medium of claim 1 wherein the one or more attribute models model at least one of different road attributes and a common road attribute under different conditions, and the road attributes include at least one of road speeds, road safety, user-favored roads, and user-disfavored roads.

16. The machine-readable medium of claim 15 wherein the different conditions include at least two of inclement weather, favorable weather, time of day, and time of week.

17. A method for generating directions for use in navigation during a current driving session, comprising:

storing a plurality of target attributes;

for at least a selection of the stored target attributes, storing a plurality of conditional variant models associated with the selected target attributes;

receiving a route request from a user, including a target destination;

generating a set of candidate routes;

computing a score for each candidate route based on one or more attribute models learned from previous user driving sessions, wherein computing comprises;

probabilistically determining for a target attribute that is one of the selected target attributes which of the plurality of conditional variant models associated with the target attribute currently corresponds to a condition of the target attribute; and

applying the determined conditional variant model to the target attribute; and

providing at least one scored route to the user.

18. The method of claim 17 wherein probabilistically determining which of the plurality of conditional variant models associated with the target attribute currently corresponds to a condition of the target attribute comprises:

determining if a conditional variant corresponds to an explicit or implicit condition;

in response to the conditional variant corresponding to an explicit condition, assigning a probability of 1 to a conditional variant model that corresponds to the explicit condition, and assigning a probability of 0 to other conditional variant models associated with the target attribute; and

in response to the conditional variant corresponding to an implicit condition, assigning a probability to each conditional variant model associated with the target attribute, using Bayesian reasoning and observed data of the current driving session.

19. The method of claim 18 further comprising:

recomputing probabilities periodically during the current driving session, using subsequently observed data of the current driving session.

20. The method of claim 17 wherein computing a score for each candidate route further comprises:

computing a value of the target attribute based on a conditional variant model having a highest probability of being applicable to the current driving session.

21. The method of claim 17 wherein computing a score for each candidate route further comprises:

predicting a value for the target attribute using a combination of the conditional variant models for the attribute.

22. The method of claim 17 further comprising:

assigning an attribute weight to each target attribute of each candidate route, based on attribute preferences of the user;

wherein computing a score for each candidate route includes computing the score using route attribute values computed using the one or more attribute models, and the attribute weights.

23. The method of claim 22 further comprising:

adjusting the attribute weights based on subsequent user input.

24. A method for generating directions for use in navigation during a current driving session, comprising:

storing a plurality of target attributes;

for at least a selection of the stored target attributes, storing a plurality of conditional variant models associated with the selected target attributes;

receiving a route request from a user, including a target destination;

generating a set of candidate routes;

assigning an attribute weight to each target attribute of each candidate route, based on attribute preferences of the user;

computing a score for each candidate route based on the attribute weights and one or more attribute models learned from previous user driving sessions, wherein at least one of the one or more attribute models provides a summary statistic of attribute values that have been observed during previous driving sessions, and wherein the computing comprises;

probabilistically determining for a target attribute that is one of the selected target attributes which of the plurality of conditional variant models associated with the target attribute currently corresponds to a condition of the target attribute; and

applying the determined conditional variant model to the target attribute; and

providing at least one scored route to the user.

25. The method of claim 24 wherein probabilistically determining which of the plurality of conditional variant models associated with the target attribute currently corresponds to a condition of the target attribute comprises:

determining if a conditional variant corresponds to an explicit or implicit condition;

in response to the conditional variant corresponding to an explicit condition, assigning a probability of 1 to a conditional variant model that corresponds to the explicit condition, and assigning a probability of 0 to other conditional variant models associated with the target attribute;

in response to the conditional variant corresponding to an implicit condition, assigning a probability to each conditional variant model associated with the target attribute, using Bayesian reasoning and observed data of the current driving session; and

recomputing probabilities periodically during the current driving session, using subsequently observed data of the current driving session.

26. The method of claim 24 wherein computing a score for each candidate route further comprises at least one of:

computing a value of the target attribute based on a conditional variant model having a highest probability of being applicable to the current driving session; and

predicting a value for the target attribute using a combination of the conditional variant models for the attribute.

27. The method of claim 24 further comprising:

adjusting the attribute weights based on subsequent user input.