Traffic forecasting employing modeling and analysis of probabilistic interdependencies and contextual data

• US 7,698,055 B2
• Filed: 06/30/2005
• Issued: 04/13/2010
• Est. Priority Date: 11/16/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J., Apacible, Johnson T., Sarin, Raman K.
• Primary Examiner(s): Tran; Dalena
• Application Number:
  US11/171,791
• Publication Number:
  US 20060106530A1
• Time in Patent Office: 1,748 Days
• Field of Search: 701117-119, 701/201, 701/202, 701207-209, 701/211, 342/357.13, 342/357.07, 340988-990, 340/995.1, 340/995.13, 340/995.18, 340/539.13
• US Class Current: 701/117
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions

Abstract

Systems and methods are described for constructing predictive models, based on statistical machine learning, that can make forecasts about traffic flows and congestions, based on an abstraction of a traffic system into a set of random variables, including variables that represent the amount of time until there will be congestion at key troublespots and the time until congestions will resolve. Observational data includes traffic flows and dynamics, and other contextual data such as the time of day and day of week, holidays, school status, the timing and nature of major gatherings such as sporting events, weather reports, traffic incident reports, and construction and closure reports. The forecasting methods are used in alerting, the display graphical information about predictions about congestion on desktop on mobile devices, and in offline and real-time automated route recommendations and planning.

Claims

1. A system that facilitates communicating, visualizing, or alerting about traffic patterns, comprising:

at least one processor;

computer-executable components for execution in the at least one processor, the components comprising;

a predictive model component that generates predictions relating to traffic parameters at a future time at a location, the predictions being generated based in part on current values of context parameters other than traffic parameters, the predictions further based in part on historical data relating the context parameters to the traffic parameters at the location; and

an interface component that graphically outputs traffic parameters based at least in part upon the generated predictions, the interface component;

determining a time and a location, and

the traffic parameters being selectively output to the user for the determined time and for the determined location.

2. The system of claim 1, wherein the contextual parameters comprise contextual data received by way of one or more of a camera, the Internet, a television broadcast, and a radio broadcast, and the contextual data comprises at least one of time of day, day of week, holiday status, season, school status, weather properties, data relating to sporting events, data relating to parades, data relating to movies, and data relating to political events.

3. The system of claim 1, the predictive model component employs one or more of marginal or mean traffic flow expectations based on one or more of time of day, day of week, and current traffic information;

and probabilistic forecasts about future traffic flows in different regions to guide creation of route plans in an attempt to minimize total driving time.

4. The system of claim 3, GPS data is utilized to locate a user and to provide information on traffic at the location.

5. The system of claim 1, the interface component existent upon one or more of a laptop, a personal digital assistant, a cellular phone, a smart phone, an automobile, and a desktop computer.

6. The system of claim 1, the predictions relating to traffic parameters at the future time are associated with one or more of time until congestions appear and time until congestions will clear at each of a set of at least one of identified trouble spots and bottleneck regions of a road system identified based on the historical data.

7. The system of claim 1, the predictive model component is built by way of a statistical method, the statistical method is one of a Bayesian network, a dynamic Bayesian network, a continuous time Bayesian network, a Hidden Markov Model, a Markov process, particle filtering, a Gibbs-sampling based approach, a neural network, a support vector machine, one or more differential equations, a logic-based reasoning system, and a fuzzy logic-centric method.

8. The system of claim 1, further comprising a model analyzer component that compares outputs predicted by the predictive model component with actual events, builds a case library of predicted situations and their accuracy, and uses the library to tune and/or annotate base level inferences so as to relay a reliability of the base level inference.

9. The system of claim 1, a case library of accuracies of predictions is used to build via statistical machine learning procedures a separate predictive model that can predict in real-time reliability of the predictive model component based at least in part on available contextual information.

10. The system of claim 1, further comprising a bottleneck identification tool that identifies regions within a traffic system associated with at least one of cyclic congestions, frequent congestions, and largest duration congestions within a traffic system via exploring statistics of congestion based on the historical data.

11. The system of claim 1, the interface component provides an input mechanism for the user to specify a congestion level and selectively outputs the traffic parameters when the predictions indicate congestion above the specified congestion level when the predicted traffic parameters indicate congestion above the threshold.

12. The system of claim 1, contextual data received and analyzed by the predictive model component utilized to improve the predictive model component.

13. A computer-readable medium comprising the computer-executable components of claim 1.

14. The system of claim 1, wherein:

the interface component comprises a control adapted to receive user input indicate of a threshold level of congestion;

at least one of the traffic parameters is a congestion parameter; and

the interface component selectively outputs traffic parameters by generating an alert to the user when the congestion parameter exceeds the threshold level.

15. A computerized method for predicting traffic patterns, comprising:

generating a representation of a plurality of roadways;

determining a future time of interest to a user and a traffic pattern of interest to the user at a location of interest to the user at the future time;

with at least one processor;

predicting events with respect to traffic patterns upon the plurality of roadways at the future time at the location based at least in part on bottlenecks identified from historical data indicating a region with at least one of cyclic congestions, frequent congestions, and largest duration congestions; and

selectively graphically displaying the predicted events, the selectively displaying comprising graphically displaying an indication of the traffic pattern when the predicted traffic pattern matches the traffic pattern of interest.

16. The method of claim 15, further comprising:

receiving contextual data relating to the plurality of roadways; and

generating the predictions as a function of the received contextual data.

17. The method of claim 16, further comprising graphically displaying an icon that indicates at least one of a time until a region is clear and a time until an open region will jam;

and graphically displaying a graphical feature to indicate occurrence of a surprising event.

18. The method of claim 15, further comprising reasoning about and among random variables that represent time until congestion and time until clear for sets of at least one of troublesome traffic hotspots and bottleneck regions in a traffic system.

19. The method of claim 15, further comprising:

comparing output of the predictive model with actual events; and

automatically tuning the predictive model as a function of the comparison.

20. A traffic pattern prediction system, comprising:

at least one processor;

computer-executable means executable on the at least one processor, the computer-executable means comprising;

means for predicting traffic parameters based at least on current context data;

means for determining whether the predicted traffic parameters are of interest to a user based on the predicted traffic parameters being outside a range of expected traffic parameters, the expected traffic parameters being computed based on historical data; and

means for selectively alerting the user of the traffic parameters that are of interest to the user.