How long does it really take to drive from point A to point B? Though mapping applications have long given a guess along with directions, a group at Microsoft Research has built a system that gives a much more accurate estimate based on real-time road conditions and the user’s driving habits. The system also predicts which route will be fastest for each user, and will adjust its suggestions if a person’s driving habits change over time. The researchers presented their work last week at the 17th Association for Computing Machinery conference on Knowledge Discovery and Data Mining in San Diego.
The research is based on data from GPS sensors installed in more than 33,000 taxicabs in Beijing, China. Yu Zheng led the study at Microsoft Research Asia. His team previously analyzed that data simply to find quick routes around the city, since cab drivers are intimately familiar with changing driving conditions. Their newest application, however, integrates several additional factors.
The new algorithms use data from the taxis not only to find routes but also to gather information about both real-time and past traffic conditions. They also glean the weather from publicly available websites. The algorithms use this data to predict what traffic conditions a driver is likely to encounter upon arriving at various points on a path and to adjust the directions accordingly.
The system also uses the GPS data on users’ cell phones to track their driving behavior and provide personalized directions. “Different drivers have different fastest paths even at the same time of day,” says Zheng. For example, he says, an aggressive driver might do well driving on highways, passing cars and pushing the speed limit. A more conservative driver might get to a destination faster by traveling on back roads with less traffic. Zheng notes that the user’s privacy is protected by storing and analyzing the personalized data entirely on the phone.
Taking into account how these behaviors change over time is also important. Not only do people drive routes in different ways, Zheng says, they also adapt as they gain experience. “After I go through a route multiple times, I know how to drive it,” he says. As a result, the system sometimes changes its prediction of the fastest route based on a driver’s familiarity with certain streets.
Testing the system is difficult, the researchers note, because an individual can only drive one route at a time, and conditions are always different. The researchers evaluated their scheme by comparing actual GPS trip data with their travel time predictions. The team previously found that the routes they gleaned from taxis were faster than routes provided by major mapping services. In this study, the team showed that, over time, the system’s drive-time predictions became more accurate and that the personalized routes were faster than even the basic taxi-derived routes.
The ubiquity of cheap, always-connected GPS sensors has changed the kinds of predictions that are possible, says Sam Madden, an associate professor at the MIT Computer Science and Artificial Intelligence Laboratory who studies wireless sensor networks, including GPS units. “I think this is the first time it’s possible to do work like this at the scale of every road in a city or country,” Madden says. Zheng’s team, he adds, is “operating with a scale of data that is way beyond what was possible even three years ago.” Madden believes this has given the Microsoft researchers enough data to make significant progress at understanding traffic in real-time. He also considers their effort to customize routes innovative.
Zheng says his team’s app could be easily adapted for general or commercial use in any city that has a large number of taxicabs. Beijing ranks fourth in the world for number of cabs, but he notes that the top 10 includes Mexico City, Bangkok, Tokyo, New York, Buenos Aires, and Moscow. Zheng says, “We are doing something that can be deployed in the real world and can make a real impact.”