Dynamic time series prediction of future traffic conditions

• US 8,065,073 B2
• Filed: 10/04/2010
• Issued: 11/22/2011
• Est. Priority Date: 03/03/2006
• Status: Expired due to Fees

• Current Assignee: Inrix Incorporated
• Original Assignee: Inrix Incorporated
• Inventors: Downs, Oliver B., Barker, Alec, Chapman, Craig H.
• Primary Examiner(s): Tran; Dalena
• Assistant Examiner(s): Figueroa; Jamie
• Application Number:
  US12/897,621
• Publication Number:
  US 20110082636A1
• Time in Patent Office: 414 Days
• Field of Search: 701/117, 701/119, 340/995.13
• US Class Current: 701/117
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions
• CPC Class Codes: G08G 1/0968 Systems involving transmission of navigation instructions to the vehicle

Abstract

Techniques are described for generating predictions of future traffic conditions at multiple future times, such as by using probabilistic techniques to assess various input data while repeatedly producing future time series predictions for each of numerous road segments (e.g., in a real-time manner based on changing current conditions for a network of roads in a given geographic area). In some situations, one or more predictive Bayesian models and corresponding decision trees are automatically created for use in generating the future traffic condition predictions for each geographic area of interest, such as based on observed historical traffic conditions for those geographic areas. Predicted future traffic condition information may then be used in a variety of ways to assist in travel and for other purposes, such as to plan optimal routes through a network of roads based on predictions about traffic conditions for the roads at multiple future times.

Claims

1. A computer-implemented method comprising:

receiving information describing a network of roads in a geographic area;

for each of the roads in the network, identifying multiple segments of the road for which traffic congestion will be distinctly tracked; and

automatically facilitating navigation of vehicles over the network of roads based on predicted traffic congestion of the roads, the automatic facilitating of the navigation of the vehicles being performed by one or more configured computing systems and including, for each of multiple users,

receiving a request from the user for information indicating predicted traffic conditions of roads of the network for travel to an indicated destination;

receiving information indicating current conditions that affect future traffic on the roads in the network, the current conditions including current levels of traffic on the roads, current weather for the geographic area, current events that are scheduled to occur in the geographic area, and current school sessions that are scheduled to occur in the geographic area;

identifying segments of roads of the network along one or more routes to the indicated destination from at least one possible starting position, each of the one or more routes including multiple identified road segments;

for each of multiple distinct future times, predicting an expected level of traffic congestion for each of the identified road segments at that future time, the predicting being based at least in part on the indicated current conditions;

for each of the one or more routes, determining a predicted travel time for the route based on the predicted expected traffic congestion levels for the multiple road segments of the route, the determining such that at least one predicted expected level of traffic congestion at a first future time is used for a first group of one or more of the road segments of the route and such that at least one predicted expected level of traffic congestion at a second future time is used for a second group of one or more other of the road segments of the route, the second future time being later than the first future time and the road segments of the second group being after the road segments of the first group along the route; and

providing information to the user that indicates the determined predicted travel time for at least one of the routes to the indicated destination,

so that users can navigate vehicles over the network of roads based on predicted traffic congestion of the roads at multiple future times.

2. The method of claim 1 wherein, for each of at least some of the multiple users, the providing of the information to the user includes displaying to the user a map on which multiple route options are indicated in such a manner that an optimal one of the route options is identified.

3. The method of claim 1 further comprising, for each of at least some of the multiple users, after the providing of the information to the user, receiving information indicating updated current conditions, predicting an updated expected level of traffic congestion for each of at least one of the identified road segments at one or more future times based at least in part on the updated current conditions, and providing updated information to the user that indicates an updated predicted travel time for at least one route to the indicated destination based at least in part on the predicted updated expected levels of traffic congestion.

4. The method of claim 1 wherein the predicting of the expected levels of traffic congestion for identified road segments at multiple future times is based on at least one predictive model for the network of roads in the geographic area, and wherein the method further comprises automatically generating the at least one predictive models based at least in part on prior observed levels of traffic congestions for the identified road segments and on prior conditions that affected the prior observed traffic congestion levels.

5. The method of claim 1 wherein, for at least one of the multiple users, the indicated current conditions for use in predicting expected levels of traffic congestion further include current expectations for future weather for the geographic area, current traffic accidents on the roads, current construction activities on the roads, a current time of day, and a current day of week, and the current scheduled events are each associated with at least one event time and with a location in the geographic area such that traffic will be affected at one or more of the event times on segments of roads used for at least one of travel to the location and travel from the location.

6. The method of claim 1 wherein the network of roads includes roads for which traffic sensors are available to provide information about current levels of traffic, the identified segments of the roads each including at least one traffic sensor such that provided information about a current level of traffic for a road segment includes average traffic speed and/or traffic volume for that road segment.

7. A computer-implemented method comprising:

receiving indications of multiple road segments of multiple related roads;

receiving information indicating current traffic conditions at a first time for each of the road segments;

receiving information indicating other current conditions at the first time that affect traffic on the road segments, the other current conditions including multiple of current weather conditions, current events that are scheduled to occur, and current schedules for school sessions;

using the indicated current traffic conditions for the first time and the indicated other current conditions for the first time to automatically predict multiple distinct levels of traffic congestion at multiple distinct future times after the first time for each of one or more of the multiple road segments, the automatic predicting being performed by one or more configured computing systems, the predicted traffic congestion levels for the multiple future times being distinct from historical average traffic congestion levels corresponding to the multiple future times; and

using at least some of the predicted traffic congestion levels to facilitate travel on the roads.

8. The method of claim 7 wherein the automatic predicting of the levels of traffic congestion is based on use of at least one predictive model that uses the indicated current traffic conditions and the indicated other current conditions as input.

9. The method of claim 8 wherein the at least one predictive model includes a Bayesian network.

10. The method of claim 8 wherein the at least one predictive model includes a probabilistic model.

11. The method of claim 8 further comprising automatically generating the predictive model based at least in part on observed past traffic congestion levels on the road segments and on past traffic conditions and past other conditions that affected the past traffic congestion levels on the road segments.

12. The method of claim 7 further comprising, after the automatic predicting of the levels of traffic congestion for one of the road segments at the multiple distinct future times, receiving updated current conditions information that is distinct from the indicated current traffic conditions and the indicated other current conditions, automatically predicting new levels of traffic congestion for the one road segment at each of at least some of the multiple distinct future times, and using one or more of the predicted new traffic congestion levels to facilitate travel on the roads.

13. The method of claim 12 wherein the using of the at least some predicted traffic congestion levels to facilitate travel on the roads includes providing information about the at least some predicted traffic congestion levels to one or more recipients for use, and wherein the using of the predicted new traffic congestion levels to facilitate travel on the roads includes providing updated information about the predicted new traffic congestion levels to at least one of the recipients.

14. The method of claim 7 wherein the indicated current traffic conditions of each of the road segments include at least one of a measured average speed on the road segment and a measured traffic volume on the multiple road segment.

15. The method of claim 14 wherein the indicated other current conditions include the current weather conditions, the current events that are scheduled to occur, the current schedules for school sessions, current expectations for future weather, current traffic accidents on the road segments, current construction activities on the road segments, a current time of day, and a current day of week.

16. The method of claim 15 wherein the automatic predicting of the multiple distinct levels of traffic congestion at the multiple distinct future times is further based on information about prior traffic conditions before the first time for the one or more road segments.

17. The method of claim 7 wherein the received information indicating the current traffic conditions is obtained at least in part from a network of multiple traffic sensors such that each of at least some of the road segments each correspond to one or more of the multiple traffic sensors.

18. The method of claim 7 wherein the received information indicating the current traffic conditions is obtained at least in part from multiple vehicles traveling the multiple related roads, each vehicle able to repeatedly determine vehicle travel data that includes at least one of location of the vehicle, speed of the vehicle, and travel direction of the vehicle, and to provide the determined vehicle travel data.

19. The method of claim 7 wherein the received information indicating the current traffic conditions is obtained at least in part from multiple users traveling the multiple related roads, each user having a mobile device operative to provide geo-location data including location of the device.

20. The method of claim 7 wherein the indicated other current conditions include one or more current weather conditions and one or more current scheduled events and one or more current school session schedules, the received information for the current weather conditions including at least one of an air temperature, a wind speed, a wind direction, an amount of precipitation measured over a period of time, and a level of sky cover, the received information for each event including at least one associated time and one or more indications of one or more locations associated with the event, and the received information for each current school session schedule including at least one associated time and one or more indications of one or more locations associated with one or more schools.

21. The method of claim 7 wherein the using of the at least some predicted traffic congestion levels to facilitate travel on the roads includes at least one of initiating presentation of the at least some predicted traffic congestion levels to a user and of providing indications of the at least some predicted traffic congestion levels to a third party that uses the provided indications to facilitate travel on the roads.

22. The method of claim 7 wherein the using of the at least some predicted traffic congestion levels for road segments to facilitate travel on the roads includes generating comparative information regarding the at least some predicted traffic congestion levels and other traffic congestion levels for those road segments, and providing one or more indications of the generated comparative information.

23. The method of claim 7 wherein the using of the at least some predicted traffic congestion levels to facilitate travel on the roads includes:

identifying multiple route options between a starting location and a destination location over the multiple roads, each of the route options including at least one of the one or more road segments;

selecting at least one of the multiple route options as being preferred based at least in part on the predicted traffic congestion levels; and

providing one or more indications of the selected route options.

24. The method of claim 23 wherein the automatic predicting of the multiple distinct levels of traffic congestion at the multiple distinct future times is performed for each of the multiple road segments, and wherein each of the identified multiple route options includes a plurality of the multiple road segments.

25. The method of claim 23 wherein the one or more road segments include a plurality of the multiple road segments, wherein one or more of the identified multiple route options each includes two or more of the plurality of road segments, and wherein the method further comprises automatically determining for each of the one or more route options a predicted travel time for the route option based on the predicted traffic congestion levels at the multiple distinct future times for the two or more road segments included in the route option, the determining of the predicted travel time for each of the one or more route options including using at least one predicted expected level of traffic congestion at one of the multiple future times for a first group of one or more of the road segments included in the route option and including using at least one predicted expected level of traffic congestion at another of the multiple future times for a second group of one or more other of the road segments included in the route option, the another future time being later than the one future time and the road segments of the second group being after the road segments of the first group along the route option.

26. The method of claim 25 wherein the selected preferred at least one route options are each one of the one or more route options, and wherein the selecting of the at least one route options as being preferred is based on the automatically determined predicted travel times for the selected preferred at least one route options.

27. The method of claim 23 wherein the using of the at least some predicted traffic congestion levels to facilitate travel on the roads includes initiating display to a user of a map on which the multiple route options are indicated.

28. The method of claim 23 wherein the using of the at least some predicted traffic congestion levels to facilitate travel on the roads includes initiating providing of the at least some predicted traffic congestion levels to a user, and wherein the method further comprises, after the providing of the at least some predicted traffic congestion levels to the user, receiving information indicating updated current conditions, predicting an updated expected level of traffic congestion for each of at least one of the one or more road segments at one or more of the multiple future times based at least in part on the updated current conditions, and providing updated information to the user that indicates an updated predicted travel time for at least one of the multiple route options based at least in part on the predicted updated expected levels of traffic congestion.

29. The method of claim 7 wherein the predicted levels of traffic congestion each have at least one associated vehicle speed, and wherein the multiple roads are part of an interconnected network of roads in a single geographic area.

30. A non-transitory computer-readable medium whose stored contents configure a computing system to perform a method, the method comprising:

receiving information indicating current traffic conditions at a first time for each of multiple road segments of one or more roads;

receiving information indicating other current conditions at the first time that affect traffic on the multiple road segments, the other current conditions including at least one of current weather conditions, current events that are scheduled to occur, and current schedules for school sessions;

using the indicated current traffic conditions for the first time and the indicated other current conditions for the first time to automatically predict multiple distinct future traffic conditions for the one or more roads, the automatic predicting being performed by the configured computing system, each of the predicted future traffic conditions being for one of the multiple road segments at one of multiple future times after the first time; and

providing one or more indications of at least some of the predicted future traffic conditions for use in facilitating travel on the one or more roads.

31. The non-transitory computer-readable medium of claim 30 wherein the predicting of the future traffic conditions for the one or more roads includes use of a predictive Bayesian network model for the one or more roads in order to predict a traffic congestion level at each of the multiple future times for each of at least one of the multiple roads.

32. The non-transitory computer-readable medium of claim 30 wherein the method further comprises identifying a route between a starting location and an ending location based at least in part on the predicted future traffic conditions, and wherein the providing of the one or more indications of the at least some predicted future traffic conditions includes indicating the identified route to a user.

33. The non-transitory computer-readable medium of claim 32 wherein the one or more roads include multiple road segments, wherein the automatic predicting of the multiple distinct future traffic conditions for the one or more roads further includes distinctly predicting future traffic conditions for each of one or more of the road segments for each of the multiple future times, and wherein the method further comprises determining multiple route options between the starting location and the destination location, each of the route options including at least one of the one or more road segments, and selecting the identified route from the multiple route options as a preferred route based at least in part on the predicted future traffic conditions.

34. The non-transitory computer-readable medium of claim 33 wherein the automatic predicting of the multiple distinct future traffic conditions for the one or more roads is further performed for each of the multiple road segments, and wherein each of the determined multiple route options includes a plurality of the multiple road segments.

35. The non-transitory computer-readable medium of claim 34 wherein the method further comprises automatically determining for each of the multiple route options a predicted travel time for the route option based on the predicted future traffic conditions at the multiple distinct future times for the plurality of road segments included in the route option, the determining of the predicted travel time for each of the route options including using at least one predicted future traffic condition at one of the multiple future times for a first group of one or more of the road segments included in the route option and including using at least one predicted future traffic condition at another of the multiple future times for a second group of one or more other of the road segments included in the route option, the another future time being later than the one future time and the road segments of the second group being after the road segments of the first group along the route option.

36. The non-transitory computer-readable medium of claim 35 wherein the selecting of the identified route as being preferred is based on the automatically determined predicted travel times for the selected identified route.

37. The non-transitory computer-readable medium of claim 32 wherein the indicating of the identified route to a user includes initiating display to the user of a map on which the identified route is indicated.

38. The non-transitory computer-readable medium of claim 32 wherein the indicating of the identified route to the user includes indicating a predicted travel time for the identified route to the user, and wherein the method further comprises, after the indicating of the identified route to the user, receiving information indicating updated current conditions, predicting updated future traffic conditions for the one or more roads at one or more of the multiple future times based at least in part on the updated current conditions, and providing updated information to the user that indicates an updated predicted travel time for the identified route based at least in part on the predicted updated future traffic conditions.

39. The non-transitory computer-readable medium of claim 30 wherein the predicted future traffic conditions for the one or more roads at the multiple future times are distinct from historical average traffic conditions corresponding to the multiple future times.

40. The non-transitory computer-readable medium of claim 30 wherein the computer-readable medium is a memory of the configured computing system, and wherein the contents are instructions that when executed program the configured computing system to perform the method.

41. The non-transitory computer-readable medium of claim 30 wherein the contents include one or more data structures for use in predicting future traffic information for roads, the one or more data structures representing a predictive Bayesian network model for the one or more roads and including multiple entries, some of the entries each corresponding to one of multiple road segments of the one or more roads and one of multiple future times so as to store a predicted future traffic condition for that road segment at that future time, and other of the entries each corresponding to one of multiple current conditions that include current traffic conditions of each of the multiple road segments and one or more other current conditions so as to store input information for the predicting.

42. A computing system, comprising:

one or more processors;

a first component configured to, when executed by at least one of the one or more processors, and for each of multiple distinct future times, predict traffic conditions at that future time for each of one or more of multiple road segments of one or more roads based at least in part on obtained information indicating current conditions related to the road segments, the indicated current conditions including multiple of current traffic conditions for the road segments, current weather conditions, current scheduled events, and current school schedules; and

a second component configured to, when executed by at least one of the one or more processors, provide one or more indications of at least one of the predicted traffic conditions for use in facilitating travel on the one or more roads.

43. The computing system of claim 42 further comprising a memory on which is stored a predictive probabilistic model for use in the predicting of the traffic conditions, the predicted traffic conditions including a predicted future traffic congestion level at each of the multiple future times for each of the multiple road segments.

44. The computing system of claim 43 wherein the second component is further configured to use the predicted traffic conditions to generate information indicating preferred travel over the one or more roads such that the provided indications include one or more indications of the generated information.

45. The computing system of claim 43 further comprising a third module configured to automatically generate the predictive model based at least in part on past traffic conditions and past conditions that affected the past traffic conditions on the road segments.

46. The computing system of claim 42 wherein the predicted future traffic conditions at the multiple future times are distinct from historical average traffic conditions corresponding to the multiple future times.

47. The computing system of claim 42 comprising a third component configured to identify a route between a starting location and an ending location based at least in part on the predicted traffic conditions for the multiple future times, and wherein the providing of the one or more indications of the at least one predicted traffic conditions includes indicating the identified route to a user.

48. The computing system of claim 45 wherein the third component is further configured to determine multiple route options between the starting location and the destination location, each of the route options including at least one of the one or more road segments, and to select the identified route from the multiple route options as a preferred route based at least in part on the predicted traffic conditions.

49. The computing system of claim 48 wherein the automatic predicting of the traffic conditions is further performed for each of the multiple road segments, and wherein each of the determined multiple route options includes a plurality of the multiple road segments.

50. The computing system of claim 49 wherein the third component is further configured to automatically determine for each of the multiple route options a predicted travel time for the route option based on the predicted traffic conditions at the multiple distinct future times for the plurality of road segments included in the route option, the determining of the predicted travel time for each of the route options including using at least one predicted future traffic condition at one of the multiple future times for a first group of one or more of the road segments included in the route option and including using at least one predicted future traffic condition at another of the multiple future times for a second group of one or more other of the road segments included in the route option, the another future time being later than the one future time and the road segments of the second group being after the road segments of the first group along the route option.

51. The computing system of claim 50 wherein the selecting of the identified route as being preferred is based on the automatically determined predicted travel times for the selected identified route.

52. The computing system of claim 47 wherein the indicating of the identified route to a user includes initiating display to the user of a map on which the identified route is indicated.

53. The computing system of claim 47 wherein the indicating of the identified route to the user includes indicating a predicted travel time for the identified route to the user, wherein the first component is further configured to, after the indicating of the identified route to the user, receive information indicating updated current conditions and predict updated future traffic conditions for the one or more road segments at one or more of the multiple future times based at least in part on the updated current conditions, and wherein the second component is further configured to provide updated information to the user that indicates an updated predicted travel time for the identified route based at least in part on the predicted updated future traffic conditions.

54. The computing system of claim 42 wherein the first component is a dynamic traffic predictor component, and wherein the first and second components each include software instructions for execution by the one or more processors.

55. The computing system of claim 42 wherein the first component consists of means for, for each of multiple distinct future times, predicting traffic conditions at that future time for each of one or more of multiple road segments of one or more roads based at least in part on obtained information indicating current conditions related to the road segments, the indicated current conditions including multiple of current traffic conditions for the road segments, current weather conditions, current scheduled events, and current school schedules, and wherein the second component consists of means for providing one or more indications of at least one of the predicted traffic conditions for use in facilitating travel on the one or more roads.