Adaptive and personalized navigation system

• US 9,810,545 B2
• Filed: 11/21/2016
• Issued: 11/07/2017
• Est. Priority Date: 11/02/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Golding, Andrew R., Rasmussen, Jens Eilstrup
• Primary Examiner(s): Amin, Bhavesh V
• Application Number:
  US15/356,866
• Publication Number:
  US 20170067749A1
• Time in Patent Office: 351 Days
• Field of Search: None
• 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 computer-implemented method for travel time prediction, the method comprising:

receiving, by one or more computing devices, a route request associated with a user;

determining, by the one or more computing devices, one or more candidate routes responsive to the route request, wherein each of the one or more candidate routes comprises one or more road segments;

accessing, by the one or more computing devices, a plurality of different road speed models, wherein each road speed model comprises a model of vehicle speeds on one or more of the one or more road segments during different conditions, each road speed model having been created by a road speed modeler configured to;

collect observations of road speed data during a plurality of driving sessions, the road speed data including a set of sensor measurements relevant to road speed; and

create the plurality of different road speed models corresponding to different conditions that impact the road speed;

selecting, by the one or more computing devices, at least one of the plurality of different road speed models based at least in part on one or more conditions associated with the route request; and

employing, by the one or more computing devices, the selected at least one road speed model to predict one or more travel times respectively for the one or more candidate routes.

2. The computer-implemented method of claim 1, wherein the different conditions comprise one or more of weather information, construction information, day-of-week information or time-of-day information.

3. The computer-implemented method of claim 1, further comprising:

determining a driver ID for the user, and

restricting the plurality of different road speed models to include only road speed models associated with the driver ID indicating that the user has traversed one or more of the one or more road segments during a set of driving sessions.

4. The computer-implemented method of claim 3, wherein a default value is assigned for one or more unseen road segments that were not traversed by the user during the set of driving sessions.

5. The computer-implemented method of claim 3, wherein the plurality of different road speed models are created at least in part from driving data aggregated from a number of users.

6. The computer-implemented method of claim 1, wherein receiving, by one or more computing devices, a route request associated with a user comprises receiving a target destination, current time data and a current location of the user.

7. The computer-implemented method of claim 6, wherein receiving a target destination, current time data and a current location of a user comprises receiving sensor data from one or more of a GPS receiver and a dead-reckoning sensor.

8. The computer-implemented method of claim 1, wherein the plurality of different road speed models are created at least in part from road segment data that includes transition time from one stretch of road to another.

9. The computer-implemented method of claim 1, wherein the plurality of different road speed models are created at least in part from input used to adjust road speeds learned during anomaly conditions that do not reflect typical speeds for a given road segment at a given time.

10. The computer-implemented method of claim 1, wherein selecting, by the one or more computing devices, at least one of the plurality of different road speed models based at least in part on one or more conditions associated with the route request comprises at least one selected from a group consisting of:

determining, by the one or more computing devices, a level of user hurriedness based on one or more detected driving behaviors;

determining, by the one or more computing devices, a current environmental condition;

determining, by the one or more computing devices, a current level of traffic; and

determining, by the one or more computing devices, a type of a road segment included in each candidate route.

11. The computer-implemented method of claim 1, wherein selecting, by the one or more computing devices, at least one of the plurality of different road speed models based at least in part on one or more conditions associated with the route request comprises:

constructing, by the one or more computing devices, one or more mini-models of road speed;

determining, by the one or more computing devices, a similarity metric for pairs of the one or more mini-models, wherein the similarity metric measures the degree of similarity between pairs of mini-models; and

clustering, by the one or more computing devices, the one or more mini-models based at least in part from the similarity metrics.

12. The computer-implemented method of claim 11, wherein determining, by the one or more computing devices, a similarity metric for pairs of the one or more mini-models, comprises determining a smoothed distribution of road speeds on each road segment that is common between two mini-models.

13. A non-transitory machine-readable storage medium encoded with instructions that, when executed by one or more processors, cause the processor to carry out a process comprising:

receiving a route request associated with a user;

determining one or more candidate routes responsive to the route request, wherein each of the one or more candidate routes comprises one or more road segments;

accessing a plurality of different road speed models, wherein each road speed model comprises a model of vehicle speeds on one or more of the one or more road segments during different conditions, each road speed model having been created by a road speed modeler configured to;

collect observations of road speed data during a plurality of driving sessions, the road speed data including a set of sensor measurements relevant to road speed; and

create the plurality of different road speed models corresponding to different conditions that impact the road speed;

selecting at least one of the plurality of different road speed models based at least in part on one or more conditions associated with the route request; and

employing the selected at least one road speed model to predict one or more travel times respectively for the one or more candidate routes.

14. The non-transitory machine-readable storage medium of claim 13, wherein the different conditions comprise one or more of weather information, driver information, day-of-week information or time-of-day information.

15. The non-transitory machine-readable storage medium of claim 13, wherein the plurality of different road speed models are created at least in part from driving data aggregated from a number of users.

16. The non-transitory machine-readable storage medium of claim 13, wherein receiving a route request associated with a user comprises receiving a target destination, current time data and a current location of the user identified by one or more sensors.

17. The non-transitory machine-readable storage medium of claim 13, wherein selecting at least one of the plurality of different road speed models based at least in part on one or more conditions associated with the route request comprises:

constructing one or more mini-models of road speed;

determining a similarity metric for pairs of the one or more mini-models, wherein the similarity metric measures the degree of similarity between pairs of mini-models; and

clustering the one or more mini-models based at least in part from the similarity metrics.

18. The non-transitory machine-readable storage medium of claim 13, wherein the plurality of different road speed models are created at least in part from road segment data that includes transition time from one stretch of road to another.

19. The non-transitory machine-readable storage medium of claim 13, wherein the plurality of different road speed models are created at least in part from input used to adjust road speeds learned during anomaly conditions that do not reflect typical speeds for a given road segment at a given time.

20. The non-transitory machine-readable storage medium of claim 13, wherein selecting at least one of the plurality of different road speed models based at least in part on one or more conditions associated with the route request comprises at least one selected from a group consisting of:

determining a level of user hurriedness based on one or more detected driving behaviors;

determining a current environmental condition;

determining a current level of traffic; and

determining a type of a road segment included in each candidate route.