Adaptive navigation system for estimating travel times

• US 8,452,529 B2
• Filed: 01/10/2008
• Issued: 05/28/2013
• Est. Priority Date: 01/10/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Alten, Brett Gregory
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): PECHE, JORGE O
• Application Number:
  US11/972,559
• Publication Number:
  US 20090182492A1
• Time in Patent Office: 1,965 Days
• Field of Search: 701/117, 701/118, 701/119, 701/200, 701/201, 701/202, 701/206, 701/209, 701/210, 701/400, 701/410, 701/411, 701/467, 701/527, 701/533
• US Class Current: 701/400
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles

Abstract

An estimated travel time for a route generated by a navigation system can be modified using a route-specific, custom travel factor computed from data collected by the navigation system while the user is traveling the route. In one aspect, the data can be stored in a local or remote database accessible by the navigation system. The data can be used to classify routes so that custom travel factors computed for a route in a given class can be used to estimate travel times for other routes in the same class. In another aspect, the classified custom travel factors can be shared with other users.

Claims

1. A method of estimating travel time, comprising:

obtaining an actual time taken by a vehicle for traveling a first route during a trip, wherein the actual time for traveling the first route during the trip is determined by a navigation system coupled to the vehicle during the trip;

updating a rolling average of travel time taken by the vehicle for traveling the first route based on the actual time taken during the trip;

determining at least one custom travel factor based on the rolling average of travel time taken by the vehicle for traveling the first route, the custom travel factor indicating a time adjustment for estimating travel times and is based on at least one of driving habits of a user associated with the vehicle, road conditions and traffic congestion; and

estimating a travel time for at least a second route using the custom travel factor.

2. The method of claim 1, wherein the first and second routes are classified as routes of a similar type, and wherein a route is classified into one of several types based on a feature set associated with the route.

3. The method of claim 2, wherein classifying a route into one of several types comprises applying a support vector machine classifier to the feature set, the method further comprising associating a similarity score to the route.

4. The method of claim 2, wherein the first and second routes are the same.

5. The method of claim 1, wherein the custom travel factor is used to modify a generic travel factor including at least one of an average speed and an average travel time for the second route.

6. The method of claim 1, wherein the custom travel factor is further based on one or more of time, location, driving patterns, season, route type, route features, traffic information, road conditions and location data.

7. The method of claim 1, wherein determining a custom travel factor, further comprises:

computing an average custom travel factor based on two or more custom travel factors.

8. The method of claim 1, wherein at least one of the determining and estimating is performed by a network resource.

9. The method of claim 1, wherein the first and second routes are classified as routes of a similar type by comparing route signatures provided by the first and second routes, the route signatures based on average speeds associated with the first and second routes.

10. The method of claim 9, wherein a route signature includes an n-dimensional vector having average speeds as vector components, and wherein comparing route signatures comprises comparing n-dimensional vectors corresponding to different routes to identify similar routes.

11. The method of claim 10, wherein identifying similar routes comprises using a similarity criterion that is based on one of Euclidean distance and least square error.

12. A navigation system, comprising:

a processor; and

a computer-readable medium coupled to the processor and having instructions stored thereon, which, when executed by the processor, causes the processor to perform operations comprising;

obtaining an actual time taken by a vehicle for traveling a first route during a trip, wherein the actual time for traveling the first route during the trip is determined by a navigation system coupled to the vehicle during the trip;

updating a rolling average of travel time taken by the vehicle for traveling the first route based on the actual time taken during the trip;

determining at least one custom travel factor based on the rolling average of travel time taken by the vehicle for traveling the first route, the custom travel factor indicating a time adjustment for estimating travel times and is based on at least one of driving habits of a user associated with the vehicle, road conditions and traffic congestion; and

estimating a travel time for at least a second route using the custom travel factor.

13. The system of claim 12, wherein the first and second routes are classified as routes of a similar type, and wherein a route is classified into one of several types based on a feature set associated with the route.

14. The system of claim 13, wherein the first and second routes are the same.

15. The system of claim 12, wherein the custom travel factor is used to modify a generic travel factor including at least one of an average speed and an average travel time for the second route.

16. The system of claim 12, wherein the custom travel factor is further based on one or more of time, location, driving patterns, season, route type, route features, traffic information, road conditions and location data.

17. The system of claim 12, where determining at least one custom travel factor further comprises:

determining if a custom travel factor is available; and

if a custom travel factor is available,

obtaining the custom travel factor.

18. The system of claim 17, where determining at least one custom travel factor further comprises:

identifying a class for the first or second route;

identifying a similar route in the class; and

obtaining a custom travel factor associated with the similar route.

19. The system of claim 12, wherein the actual time is obtained by a mobile phone.

20. The system of claim 19, wherein the actual time is obtained from one or more sensors of the mobile phone.