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! 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.
The 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 these goals, 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.
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.
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.
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.