Contents for This Page
Traffic congestion is a nationwide problem, which results in tremendous personal and social cost. One reason is that most drivers stick to one or two familiar routes everyday not knowing that other possibilities might have been faster. Although several Internet services show us driving directions, they often turn out not to be the fastest path because varying traffic conditions are not considered. Live radio traffic broadcast is sometimes helpful for avoiding congestion, but it is limited to a small set of arterials. Moreover, it is often in the middle of the congested road that we hear congestion reports tell us how to avoid that road; Too late to escape! Our research intends to help the public reduce the amount of time wasted on the roads by providing appropriate traffic information, such as optimal driving directions and travel time estimates, through the Internet and cell phones.
See also MIT CarTel.
Our research objective is to provide an effective navigation system for cars that uses historical and real time traffic data to determine optimal driving directions and traffic estimates. In particular, we:
- develop novel algorithms for predicting traffic conditions from both historical data and current information, including GPS sensor data and toll booth pass time records.
- develop efficient algorithms for finding the optimal paths with stochastic conditions.
- implement and evaluate a traffic information system using the proposed algorithms.
To achieve our goal, live traffic data are essential. There have been various approaches for getting real-time road speed or flow, from using sensors buried under the asphalt to using cameras. However, methods utilizing these kinds of equipment are expensive to establish. Thus, it may be impossible to get live traffic information for all the roads. In contrast, our approach involves getting traffic data from various sources that are already established and wide-ranging, such as GPS (Global Positioning System) navigation, cell phone localization, and toll plaza pass time. As a result, we are able to estimate the speed of entire road ways without any deployment of additional hardware systems on roads.
Our research uses live traffic data from taxis equipped with CarTel Network nodes (including GPS and wireless communication); other sources (e.g. mobile phone data and road sensors) can be used to augment CarTel data. GPS location data have been gathered by the probe-vehicles equipped with the GPS sensor units developed in the CarTel project (cartel.csail.mit.edu).
Technical challenges and Approach
One challenge is how to assign measurement data to a road map. Since the measurement data are noisy and a road map database is not exactly lined up with them, a good map-matching algorithm is needed. Even if we knew the current road velocity of all the roads, several challenges remain. The problem is that the best path based on the current information might not be optimal since the road condition could change while we travel. What we really need to know is the velocity of each road at the time we actually drive through it. In fact, we don't know what the future velocity will be, but we envision that we can predict the future condition of roads by examining how the past and current traffic conditions affect the future condition. Thus, we examine the observed data from various sources and suggest a probabilistic model that characterizes the road speed statistically. The average (mean) and the deviation from it (variance) are the two most important parameters that indicate the characteristics of roads. Another challenge is developing a good algorithm for finding the optimal path. From the stochastic nature of road speed, optimality depends on drivers' goals. One reasonable goal would be maximizing the probability of arriving on time. Another would be minimizing the expected travel time. So, we define the problem that captures the objectives and develop algorithms that find optimal paths.
A robust map-matching algorithm was developed to correctly assign GPS trajectories to the road segments where the GPS samples might have originated.
Building a road traffic information map
A road network delay model has been built based on the observed travels by GPS probe-vehicles. GPS sensor data have been used to build the travel time distributions for each road section.
Optimal path finding
Optimal path finding algorithms with stochastic conditions have been developed and implemented using the travel time distributions of road networks. The following figure shows different optimal paths according to the three different criteria: minimum distance, minimum expected time, and maximum probability of arriving by the deadline.
We plan to build a road speed distribution according to various conditions that affect road traffic, such as weather, time of day, day of week, accident. Data sources include the GPS positioning data obtained from taxies operating in greater Boston area and the Massachusetts Turnpike toll plaza pass event log. We will suggest probabilistic models that fit to the gathered data and we will come up with a optimal path finding algorithm based on the models. In addition, stochastic shortest path algorithms for other kinds of objectives need to be devised. Finally, it is required to develop faster algorithms to provide real time traffic information.
Publications and Talks
Sejoon Lim, Hari Balakrishnan, David Gifford, Samuel Madden, Daniela Rus - Stochastic motion planning and applications to traffic
- The International Journal of Robotics Research , December 2010
BibtexAuthor : Sejoon Lim, Hari Balakrishnan, David Gifford, Samuel Madden, Daniela Rus
Title : Stochastic motion planning and applications to traffic
In : The International Journal of Robotics Research -
Date : December 2010
Sejoon Lim, Hari Balakrishnan, David Gifford, Samuel Madden, Daniela Rus - Stochastic Motion Planning and Applications to Traffic
- Proceedings of the Eighth International Workshop on the Algorithmic Foundations of Robotics (WAFR) , Guanajuato, Mexico, December 2008
- Pdf BibtexAuthor : Sejoon Lim, Hari Balakrishnan, David Gifford, Samuel Madden, Daniela Rus
Title : Stochastic Motion Planning and Applications to Traffic
In : Proceedings of the Eighth International Workshop on the Algorithmic Foundations of Robotics (WAFR) -
Address : Guanajuato, Mexico
Date : December 2008
- Proceedings of the 6th ACM Conference on Embedded Networked Sensor Systems (SenSys), Accepted , Raleigh, NC, November 2008
- Pdf http://groups.csail.mit.edu/drl/wiki/images/4/47/SenSys08_DemoPoster_Lim.pdf
BibtexAuthor : Hari Balakrishnan, Nikolaus Correll, Jakob Erikkson, Sejoon Lim, Samuel Madden, Daniela Rus
Title : Demo Abstract: PCP: The Personal Commute Portal
In : Proceedings of the 6th ACM Conference on Embedded Networked Sensor Systems (SenSys), Accepted -
Address : Raleigh, NC
Date : November 2008
- 2nd International Workshop on Mobile Vehicular Networks (MoVeNet) , Atlanta, GA, September 2008
- BibtexAuthor : Sejoon Lim, Hari Balakrishnan, Samuel Madden, Daniela Rus
Title : Stochastic Route Planning with Networked Cars (Invited Talk)
In : 2nd International Workshop on Mobile Vehicular Networks (MoVeNet) -
Address : Atlanta, GA
Date : September 2008
Sejoon Lim, Hari Balakrishnan, Jakob Eriksson, David Gifford, Samuel Madden, Daniela Rus - Intelligent Transportation with Networked Cars (Demo Abstract)
- Proceedings of the International Conference on Mobile Systems, Applications, and Services (MobiSys) , Breckenridge, CO, June 2008
- Pdf BibtexAuthor : Sejoon Lim, Hari Balakrishnan, Jakob Eriksson, David Gifford, Samuel Madden, Daniela Rus
Title : Intelligent Transportation with Networked Cars (Demo Abstract)
In : Proceedings of the International Conference on Mobile Systems, Applications, and Services (MobiSys) -
Address : Breckenridge, CO
Date : June 2008
 Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On Map-Matching Vehicle Tracking Data. In Proceedings of the 31st VLDB Conference, pp. 853--864, Trondheim, Norway, 2005.
 Evdokia Nikolova, Matthew Brand, and David Karger. Optimal Route Planning under Uncertainty. In Proceedings of 2006 International Conference on Automated Planning & Scheduling , Lake District, England, June 2006.