Machine learning and intelligence for sensing, inferring, and forecasting traffic flows
Machine learning and intelligence are being applied in multiple ways to addressing difficult challenges in multiple fields, including transportation, energy, and healthcare. Research scientists at Microsoft Research have been engaged in efforts in all of these areas. We focus on multiyear efforts at Microsoft Research to infer and forecast the flows of traffic. The work leverages machine learning to build services that make use of both live streams of sensed information and large amounts of heterogeneous historical data. This has led to multiple prototypes and real-world services such as traffic-sensitive directions in Bing Maps. Focused work in this realm also stimulated new efforts in related areas, such as privacy and routing.
Fielded Smartphlow traffic application.
Traffic has been growing in major cities around the world given the increase in densities of cars on roads and the slow development of road infrastructure. With research starting in 2002, research scientist and developer teams at Microsoft Research pioneered the use of machine learning methods to build predictive models for traffic. The work led early on to prototypes that can infer and predict the flow of traffic at different times into the future based on the analysis of large amounts of data on traffic over months and years. The work was leveraged in revolutionary services, such as traffic maps that show users how traffic is evolving over time, as well as in services that provide traffic-sensitive directions by considering the inferred speeds on roads that are not sensed directly.
Research on machine learning for traffic spanned several projects and has focused on both on principles and applications. Multiple technical and empirical studies were performed as part of this work. On the fielding of applications, the research efforts sit behind the traffic-sensitive directions in Bing Directions within Bing Maps and the mobile directions service on the Windows Mango phones. A portion of Microsoft Research’s methods, tools, and software on predictive analytics for traffic were licensed externally in 2004 to traffic startup Inrix shortly after the company was formed, helping to slingshot that company into the world as a leading international provider of traffic analyses and predictions.
As part of efforts on learning about traffic flows from data, researchers at Microsoft Research explored methods that enhance the safety and privacy of people who wish to help with the “crowdsourcing” of real-time flows of road data from their mobile GPS data. Principles of community sensing have been developed. These principles center on working with people under a “privacy budget” based on the use of the computations of the value of information for understanding flows over time on the road network.
Predicting Traffic Jams and Flows: JamBayes
Machine learning methods have been applied to create methods that provide estimates of flows inferences about current and future traffic flows. Research on the JamBayes project, started in 2002, was framed by the frustrations encountered with navigating through Seattle traffic, a region that has seen great growth amidst slower changes to the highway infrastructure. JamBayes focused on learning to forecast flows from multiple streams of information.
The challenge was to predict the future of traffic flow: How long would it be until a current traffic jam on the highway system of Seattle would melt? How long until open flows on different segments of the highway system of Seattle would become clogged? The idea was to combine heterogeneous streams and histories of information to make these predictions. These streams included multiple years of different types of data, including sensed highway data, reports of accidents throughout the highway system, weather, and major regional events such as Mariners and Supersonics games.
Data was analyzed and processed into a predictive model that is used in real time to generate predictions about the duration of jams on different regions of the highway system.
The work led to the Smartphlow prototype which has been used by thousands of Microsoft employees for years. Smartphlow explored both the fielding of a predictive traffic service as well as navigation techniques for small devices.
Display of JamBayes on smartphone, showing with graphical icons predictions of time until traffic jams would likely melt (red clock icon on display at top left) and times until a freeflowing portion of the freeway would likely clog (green clock at top right). The clock icons included display of the system’s context-sensitive confidence in the inference, by showing standard deviations around the expected time (bottom).
Startup company Inrix licensed Microsoft Research technology in 2005 via an innovative Microsoft technology licensing program. Picture above: Eric Horvitz of Microsoft Research (left) with Craig Chapman, Chief Technology Officer at Inrix.
Predicting Traffic Surprises
Work on traffic forecasting led to work on human expectations and surprises and on a surprise modeling service that was fielded in Smartphlow. With surprise modeling, machine learning is used to forecast future events that will surprise people. Surprise modeling and forecasting in Smartphlow considers when traffic will be jammed unexpectedly or will flow more than expected (e.g.,, during rush hour) on routes of interest. Smartphlow users can set up alerting so that their devices alert them when a surprise lurks within a half hour on their commute home, as commute time approaches.
Surprise modeling controls in Smartphlow, allowing users to set up alerts when future relevant surprises are predicted.
Work on surprise modeling received the Technology Review’s TR10 honor in 2008.
Scaling up to All Roads: Clearflow Project
In a Microsoft Research project named Clearfow, following on to the JamBayes effort, efforts focused on applying machine learning to learn how to predict the flows on all street segments of a greater city area. The work has leveraged large amounts of GPS data collected from volunteers, buses, and paratransit vehicles for over five years. The data is used to learn about dependencies among flows based on multiple aspects of road networks, including road attributes and topology. The Clearflow project addressed the challenge with generating traffic-sensitive directions. Simpler traffic-sensitive routing consider known flows, such as sensed flows on highways, and consider traffic jams as only existing on those roads, often re-routing drivers onto even more crowded surface roads, assuming that the side streets are not influenced by traffic. Clearflow considers all flows on all roads via predictive models in addition to real-time sensing. Directions are provided based on best guesses about flows over all roads.
Large amounts of GPS data were collected on highway systems from volunteers and participating buses and paratransit vehicles. This figure highlights some of the data collected as displayed as colored trails.
A Clearflow prototype constructed at Microsoft Research was made available as a service to the whole Microsoft community for providing directions within Seattle. The prototype helped with refining the methods and in better understanding user needs and satisfaction.
Input fields for Clearflow prototype fielded internally at Microsoft as part of the R&D process.
From Microsoft Research to Bing Maps
Given the successes of the Clearflow prototype, collaborations were initiated with the Bing directions team. The intensive work led to the fielding of a version of Clearflow for 72 major cities in North America, where Clearflow is used for inferences on over 60 million road segments in North America.
Clearflow availability for North American cities announced in Spring 2008.
Clearflow traffic-sensitive routing is available in Bing Directions for 72 North American cities.
Users can gain access to the directions provided by the Clearflow traffic service for 72 North American cities. Simply go to Bing Directions. When asking for directions, Bing will provide default directions and provide a link that allows users to see traffic-sensitive directions.
Traffic sensitive directions in Bing. Top: default directions. Bottom: Directions and travel time estimates revised using Clearflow.
- Paper on predicting traffic flows: E. Horvitz, J. Apacible, R. Sarin, and L. Liao (2005). Prediction, Expectation, and Surprise: Methods, Designs, and Study of a Deployed Traffic Forecasting Service, Twenty-First Conference on Uncertainty in Artificial Intelligence, UAI-2005, Edinburgh, Scotland, July 2005.
- Paper on principles of community sensing: A. Kause, E. Horvitz, A. Kansal, F. Zhao. Toward Community Sensing, Proceedings of IPSN 2008, International Conference on Information Processing in Sensor Networks, St. Louis, Missouri, April 2008.
- Paper on promise of predictive modeling: E. Horvitz and T. Mitchell, From Data to Knowledge to Action: A Global Enabler for the 21st Century, Data Analytic Series, Computing Community Consortium, Computing Research Association (CRA), June 2010.
- New York Times on Clearflow
- Technology Review article on TR 10 award for surprise forecasting
- Inrix Corporation