Research Abstracts - 2007

Motivation

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.

Approach

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.

Technical challenges

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[1]. 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[2]. 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.

Progress

We have developed a stochastic shortest path algorithm with an objective of maximizing the probability of arriving at the destination given deadline. It was assumed that the delays of each road segment follow Normal distribution and that they are independent each other. We implemented this algorithm with synthetic data by Python. Tiger map database and Google map open API was used for visualization. We have also visualized average speed of each road in Massachusetts and other stochastic properties on the map.

Figure 1: Implementation of a stochastic shortest path algorithm with synthetic travel time data (left) and visualization of average speed of each road in Massachusetts based on GPS localization data (right).

Future works

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.

References:

[1] 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.

[2] 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.