PATENT DOCUMENT

Publication Number: US-8452529-B2
Application Number: US-97255908-A
Country: US
Kind Code: B2

Title: Adaptive navigation system for estimating travel times

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:
What is claimed is: 
     
       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.

Description:
TECHNICAL FIELD 
     This subject matter is generally related to navigation systems. 
     BACKGROUND 
     Many conventional navigation systems estimate travel time for routes to assist the user in time management. For example, a simplistic travel time estimate can be derived by dividing the length of the route by the posted speed limit of the route. Such a time estimate often includes error due to a variety of variables that are not accounted for in the computation, such as road conditions, traffic congestion, driving patterns, accuracy of navigation system, etc. 
     Some navigation systems use traffic time providers to provide more accurate travel times. These providers often use cell phone probes and wireless cell phone networks to estimate travel times for highways and roadways. One system, for example, traces specific, anonymous vehicles, and uses a sequence of cellular messages to correlate the cell phones to the route traveled. Once a cell phone is correlated to a route, the system can measure the position of the cell phone and travel time samples can be generated for various segments of the route. If the travel time samples are averaged over long periods of time then the travel time samples can lead to large errors in travel times estimates. Moreover, publicly available studies have shown that travel time estimation using cell phones as data probes may not be accurate in heavy traffic conditions due to the inability to accurately track position. 
     Some navigation systems allow users to enter parameters related to the user&#39;s specific driving habits. These parameters, however, do not take into account local traffic patterns and changes in the user&#39;s driving habits based on time of day, season or other factors that could alter the user&#39;s driving habits. 
     SUMMARY 
     An estimated travel time for a route generated by a navigation system can be modified using a custom travel factor determined from personal travel data collected by the navigation system while the user is traveling the route. In one aspect, the personal travel data can be stored in a local or remote database accessible by the navigation system. The personal travel data can be used to classify routes so that custom travel factors 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. 
     These features provide customized travel time estimates that take into account a user&#39;s driving habits, the characteristics of the vehicle being navigated, road conditions, seasonal conditions, traffic congestion and other factors, which cannot be accounted for by conventional statistical calculations based on data samples obtained from a test vehicle or device traveling the route. 
    
    
     
       DESCRIPTION OF DRAWINGS 
         FIG. 1  is a block diagram of an example navigation system for estimating travel time. 
         FIGS. 2A-2B  are flow diagrams of example processes for estimating travel time. 
         FIG. 3  illustrates an example route which can include route segments. 
         FIG. 4  is a block diagram of an example navigation system. 
         FIG. 5  illustrates an example network for estimating travel time. 
         FIG. 6  illustrates an example data structure for retrieving time adjustments from a database for use in estimating travel time. 
         FIG. 7  illustrates an example data structure for classifying routes. 
     
    
    
     DETAILED DESCRIPTION 
     System Overview 
       FIG. 1  is a block diagram of example navigation system  100  for estimating travel time. System  100  can include one or more of vehicle computing system  102 , navigation system  104  and mobile device  106 . In some implementations, vehicle computing system  102  can be coupled to navigation system  104  and provides navigation system  104  with information related to the operation of the vehicle (e.g., speed, fuel consumption, braking information). In other implementations, vehicle computing system  102  can include navigation system  104 . 
     In some implementations, navigation system  104  can be coupled to mobile device  106  for receiving estimated travel time  110  and other information from mobile device  106 . Mobile device  106  can be any portable device capable of performing navigation functions, including but not limited to: a portable navigation system, a mobile phone, a USB drive, a media player, an email device, etc. 
     In some implementations, navigation system  104  can be installed in the vehicle or can be a portable device. Mobile device  106  can include navigation system  104  or can be coupled (e.g., physically using a tether or dock or wirelessly) to navigation system  104 . Navigation system  104  and/or mobile device  106  can be operable to provide estimated travel time  110  for a route being traveled by navigation system  104  and/or mobile device  106 . Navigation system  104  and/or mobile device  106  can include display  108  for displaying navigation data, such as a map highlighting the route to be navigated. Navigation system  104  and/or mobile device  106  can include means (e.g., a keypad, rotary knob, buttons) for receiving input from a user or data from a network, as described in reference to  FIG. 5 . 
     Example Travel Time Estimation Process 
       FIG. 2A  is a flow diagram of example process  200  for estimating travel time. In some implementations, process  200  begins by obtaining personal travel data associated with a first route collected while traveling the first route ( 202 ). Examples of personal travel data can include but are not limited to: time, location, speed, accelerations, de-accelerations, braking patterns, etc. At least one custom travel factor (e.g., a time adjustment) can be determined based on the personal travel data ( 204 ). Using the custom travel factor, travel time can be estimated for at least a second route ( 206 ). The second route can be similar to, or the same as, the first route, or a different route in the same class as the first route, as described further in reference to  FIG. 7 . The custom travel factor can be used to modify a generic travel factor, such as an average speed or average travel time for the route. 
       FIG. 2B  is a flow diagram of example process  208  for estimating travel time. In some implementations, process  208  can begin by obtaining a route request ( 210 ). The route request can be specified by user input. For example, a user can submit a route request by entering a destination address into a navigation system. The navigation system determines a route and estimated travel time based on the request ( 212 ). The estimated travel time can be determined using a time estimation algorithm that is native to the navigation system. For example, the native algorithm may assume a constant or average speed (e.g., a posted speed limit) for the route. However, since driving speeds are seldom constant, the time travel estimates will often contain error which can be adjusted by custom travel factors. If a custom travel factor is available ( 214 ) because it was determined using personal travel data collected during one or more previous trips along the same route, then the custom travel factor for the route or a similar route can be obtained ( 216 ) from a local or remote database, and applied to the estimated travel time ( 222 ). A “similar” route can be a route that falls into the same route class as the requested route, as described in reference to  FIG. 7 . 
     In some implementations, a route can be divided into route segments and each segment can be associated with one or more custom travel factors. The factors can be represented in any suitable units or dimensions (e.g., speed, time). For example, the factors can be represented in minutes which can be added or subtracted to the estimated travel time obtained in step  210 . 
     If custom travel factors are not available (e.g., a new route is requested), then new customer travel factors can be computed based on personal travel data collected while the user (or the navigation system) travels the route ( 218 ). Examples of data include but are not limited to: time, location, speed, accelerations, de-accelerations, braking patterns, etc. The new factors can be determined based on the collected data ( 220 ) and applied to the estimated travel time for the route ( 222 ). In some implementations, the new factors can be determined based on the collected data in combination with other data provided by other sources or service providers (e.g., traffic information providers, navigation service providers, location based service providers). 
     To compute a custom travel factor, a route can be broken into one or more route segments and the average speed of the vehicle can be measured at one or more geographical locations in each segment. The speed measurements can be acquired from a vehicle computing system, by an integrated or portable navigation system or by any other device (e.g., a mobile phone) located in the vehicle which has appropriate sensors for detecting speed (e.g., accelerometer). In some implementations, the speed measurements can be computed from positional data of a mobile device (e.g., a cell phone, Wi-Fi) provided by a wireless network carrier using various known technologies (e.g., triangulation using cell towers). If a route is traveled repeatedly by the user, a rolling average of travel speeds for one or more locations of each route segment can be computed. The speed data can be stored locally or remotely where it can be accessed by the user&#39;s navigation system (or shared with other navigation systems) to generate custom travel factors using known distances associated with the route segments and/or other data. 
     In some implementations, rather than collecting speed data the elapsed time to travel a given route segment can be determined using a timer operating in the navigation system, for example. The latter method would take into account local obstacles that could effect travel time (e.g., stoplights, toll booths, bridges, railroad crossings). Each time a user travels a route, the actual time to travel the route can be computed and added to a rolling travel time average which can be stored in a local or remote database. For example, a user may travel the same route to work Monday through Friday. For each trip, the navigation system determines actual travel time which can be added to the rolling travel time average. The custom travel factors can be set equal to the rolling travel time averages. 
     In some implementations, the average speeds and/or average travel times for a particular route segment can be collected over a period of time to provide a historical view of how the average speeds and/or travel times change for different seasons, days of the week, times of day, etc. And, since this data can be collected by the user&#39;s personal navigation system (rather than from a probe), the historical view can be personalized to the user&#39;s driving habits, the peculiarities of the vehicle (e.g., a motorcycle, truck, SUV, sports car), the type of navigation system (e.g., GPS, cell phone tower triangulation, Wi-Fi), etc. In some implementations, average speeds and average times can be measured and each measurement can be used to confirm the accuracy of the other, and to select which measurement to use for a custom travel factor. For example, an average speed measurement can be converted into an average time measurement and compared with data provided by a travel time estimation service to confirm its accuracy compared to a directly computed average time measurement. An example travel time estimation service provider is AirSage® of Atlanta, Ga., U.S.A. 
     Example Estimated Travel Time Calculation 
       FIG. 3  illustrates an example route including route segments for computing custom travel factors. In the example shown, a route (shown in bold) is presented on map  302  presented on map display  300  of a navigation system. The route includes route segments  2 ,  1 ,  5  and  6 . For simplicity of calculations, we can assume that the total distance is 40 miles, where each segment is 10 miles. The posted speed limits for the route segments  2 ,  1 ,  5  and  5  are 65 mph, 55 mph, 35 mph and 25 mph, respectively. In this example, the navigation system may compute an estimated total travel time for the route to be [10/65+10/55+10/35+10/25]*60˜60 minutes. 
     Each time the user travels the route an actual average speed measurement can be made for each route segment. Segment  2  is a highway and has an actual average speed of 55 mph. Segment  1  is a highway and has an actual average speed of 40 mph. Segment  5  is a residential street and has an actual average speed of 35 mph. Segment  6  is a residential street and has an actual average speed of 20 mph. Thus the actual average time to travel the route is [10/55+10/40+10/35+10/20]˜72 minutes. When compared with the estimated travel time of about 60 minutes, the estimated travel time error is about +12 minutes. Thus in this example, the custom travel factor for this route can be +12 minutes. 
     This custom travel factor can capture the driving habits or patterns of the user and other factors effecting time such as road conditions and traffic congestion. The factor can be time stamped or otherwise indexed for easy retrieval from a local and/or remote database. A given factor may only be valid for certain times of the year, certain days of the week and certain times of the day, as described in reference to  FIG. 6 . The average speed can be calculated from the stored factors and other historical data using an iterative method to find a least-square fit. As new actual travel time data are collected, the average speed can be updated with an exponential smoothing procedure. Some examples of such techniques are described in Camp, R. and D. DeHayes (1974), “A Computer-based Method for Predicting Transit Time Parameters Using Grid Systems,” Decision Sciences, Vol. 5, pp. 339-346, which publication is incorporated by reference herein in its entirety. 
     Example Navigation System Architecture 
       FIG. 4  is a block diagram of example navigation system  400  for implementing the features and operations described in reference to  FIGS. 1-3 . In this example, navigation system  400  can include wireless communication capabilities, for example, to communicate with one or more network-based providers, such as a navigation service provider or a traffic information provider. 
     Navigation system  400  can include memory interface  402 , one or more data processors  404  (e.g., image processors and/or central processing units) and peripherals interface  406 . Memory interface  402 , one or more processors  404  and/or peripherals interface  406  can be separate components or can be integrated in one or more integrated circuits. The various components in navigation system  400  can be coupled by one or more communication buses or signal lines. For example, other sensors  410  can be connected to peripherals interface  406 , such as a positioning system (e.g., a GPS receiver), an accelerometer, a temperature sensor, or other sensing device, to facilitate related functionalities. Peripherals interface  406  can be used to interface with vehicle computer interface  414  of a vehicle computing system, e.g., vehicle computing system  102  shown in  FIG. 1 . 
     Communication functions can be facilitated through one or more wireless communication subsystems  412 , which can include radio frequency receivers and transmitters and/or optical (e.g., infrared) receivers and transmitters. The specific design and implementation of wireless communication subsystem  412  can depend on the communication network(s) over which navigation system  400  is intended to operate. For example, navigation system  400  can include a communication subsystem designed to operate over a GSM network, a GPRS network, an EDGE network, a Wi-Fi or WiMax network, and a Bluetooth™ network. 
     In this example, I/O subsystem  416  can include optional touch screen controller  418  and/or other input controller(s)  420 . Touch-screen controller  418  can be coupled to optional touch screen  422 . Touch screen  422  and touch screen controller  418  can, for example, detect contact and movement (e.g., gestures) or break thereof using any of multiple touch sensitivity technologies, including but not limited to capacitive, resistive, infrared, and surface acoustic wave technologies, as well as other proximity sensor arrays or other elements for determining one or more points of contact with touch screen  422 . 
     Other input controller(s)  420  can be coupled to other input/control devices  424 , such as one or more buttons, rocker switches, thumb-wheel, infrared port, USB port, and/or a pointer device such as a stylus. The one or more buttons (not shown) can include an up/down button for volume control of a speaker and/or a microphone. Touch screen  422  can, for example, also be used to implement virtual or soft buttons and/or a keyboard. Other input/output and control devices can also be used. 
     Memory interface  402  can be coupled to memory  408 . Memory  408  can include high-speed random access memory and/or non-volatile memory, such as one or more magnetic disk storage devices, one or more optical storage devices, and/or flash memory (e.g., NAND, NOR). Memory  408  can store operating system  426 , such as Darwin, RTXC, LINUX, UNIX, OS X, WINDOWS, or an embedded operating system such as VxWorks. Operating system  426  may include instructions for handling basic system services and for performing hardware dependent tasks. In some implementations, operating system  426  can be a kernel (e.g., UNIX kernel). 
     Memory  408  may also store communication instructions  428  to facilitate communicating with one or more additional devices, one or more computers and/or one or more servers. Memory  408  can include estimated travel time instructions  430  to implement features and operations described in reference to  FIGS. 1-3 . Memory  408  can include GPS/Navigation instructions  436  to facilitate GPS and navigation-related processes and instructions. Memory  408  can include graphical user interface instructions  432  to facilitate graphic user interface processing and sensor processing instructions  434  to facilitate sensor-related processing and functions (if any). For example, if navigation system  400  includes an accelerometer, instructions  434  can receive output from the accelerometers and can use the output to generate speed data. 
     Each of the above identified instructions and applications can correspond to a set of instructions for performing one or more functions described above. These instructions need not be implemented as separate software programs, procedures or modules. Memory  408  can include additional instructions or fewer instructions. Furthermore, various functions of navigation system  400  can be implemented in hardware and/or in software, including in one or more signal processing and/or application specific integrated circuits. Memory  408  can include other software instructions  438  for one or more applications. 
     Example Network for Estimating Travel Time 
       FIG. 5  illustrates example network  500  for estimating travel time. In some implementations, the navigation system can communicate over one or more wired and/or wireless networks  512  (e.g., the Internet, WLAN). For example, access point  508 , such as an 802.11g wireless access point, can provide communication access to network  512 . In some implementations, the navigation system can be physically connected to access point  508  using one or more cables and access point  508  can be a vehicle computer system. 
     The navigation system can communicate with one or more services over one or more wired and/or wireless networks  512 . For example, navigation service  504  can provide navigation information, e.g., map information, location information, route information, and other information, to the navigation system. Such information can be stored in remote database  512 . In other implementations, the navigation system obtains map, location and route information from local database  510 . In other implementations, the navigation system uses a combination of local database  510  and remote database  512  to store data for use in estimating travel times. Traffic information service  506  can provide traffic information (including travel time estimates) to the navigation system which can be used to improve or confirm the accuracy of time travel estimates computed by the navigation system, as described in reference to  FIG. 3 . 
     Example Schema for Retrieving Time Adjustment Data 
       FIG. 6  illustrates an example schema  600  for retrieving a custom travel factor from a data structure for use in estimating travel time. In the example shown, the navigation system retrieves from a local or remote database a custom travel factor of 20 minutes for the user&#39;s “Winter Work Route.” This particular custom travel factor is associated with Winter, the month of January, Monday and Morning. If the user requests the Winter Work Route from their navigation system, then the navigation system can use the current season, month, day and time to generate a query for retrieving the custom travel factor of +20 minutes. The factor can be added to the estimated travel time provided by the native travel time algorithm of the navigation system to generate a more accurate estimated travel time for the Winter Work Route. 
     Example Data Structure for Classifying Routes 
       FIG. 7  illustrates example data structure  700  for classifying routes. In some implementations, it may be possible to classify routes based on route features which can include custom travel factors. While a user travels a route, in some implementations the route can be transmitted to a navigation service through a network connection (e.g., navigation service  504 ). The service accesses various route data resources to extract a feature set for the route. Features can include but are not limited to: the number of segments, the average speeds for the segments, posted speed limits for the segments, route type (e.g., local, arterial, collector, rural, city, residential), the number of streetlights and their associated timings, the number of stop signs, the number of school zones or other speed-restricted zones, etc. A classifier (e.g., a support vector machine) can be applied to the features to generate labels or categories for the routes. Each new route can be processed by the classifier and labeled appropriately. In some implementations, each route can be given a similarity score that can be used to determine routes that are similar (based on similarity criteria) to the requested route. 
     In some implementations, the average speeds for a route can provide a route signature that can be compared against other route signatures. For example, an n-dimensional vector having average speeds as vector components can be compared with other n-dimensional vectors in an n-dimensional vector space to identify similar routes. The similarity criteria can be Euclidean distance, least-square error, or any other suitable criteria. 
     In some implementations, data structure  700  can be a table containing a row for each route associated with a user. The columns can include data collected to facilitate classification by a classifier. In the example shown, the columns include: Route Name, Route Type and Route Features. Other data an also be stored as desired. The Route Type and Route Features can be used by the classifier to find routes of the same type and having similar features to the requested route. Thus if a user requests a new route, a time adjustment factor for a route in the same class can be used to improve the estimated travel time calculated by the navigation system. In some implementations, factors can be shared with other users through a service bureau, social network, forum, online community, etc. 
     A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made. For example, elements of one or more implementations may be combined, deleted, modified, or supplemented to form further implementations. As yet another example, the logic flows depicted in the figures do not require the particular order shown, or sequential order, to achieve desirable results. In addition, other steps may be provided, or steps may be eliminated, from the described flows, and other components may be added to, or removed from, the described systems. Accordingly, other implementations are within the scope of the following claims.

Metadata:
Filing Date: 20080110
Publication Date: 20130528
Grant Date: 20130528
Priority Date: 20080110
Inventors: ALTEN BRETT GREGORY
Assignee: APPLE INC
CPC Classifications: [{"code": "G01C21/3484", "inventive": true, "first": true, "tree": "[]"}, {"code": "G01C21/3484", "inventive": true, "first": true, "tree": "[]"}]
Family ID: 40851390