Like every city, Boston has its springtime traditions: the beginning of baseball season, the Boston Marathon . . . and potholes. In 2010, the city filled more than 7000 potholes and responded to more than 4000 complaints.
Next spring, though, there may be fewer complaints, because the smartphones of ordinary citizens will report some potholes automatically. The new pothole-detecting app, a beta version of which can be seen here, will include a wavelet-based algorithm devised by two undergraduate students and their adviser, Edward Aboufadel of Grand Valley State University in Allendale, Michigan. In February 2012, the team was one of three winners in an open “crowdsourcing” competition, organized by InnoCentive, Inc.
Urban blight. Potholes—thanks to a smartphone app that uses a wavelet-based algorithm devised by REU students at Grand Valley State University—could soon be less of an annoyance to city drivers (and mayors).
The pothole saga began in 2010, when the city partnered with Worcester Polytechnic professor Fabio Carrera to develop a smartphone app, called Street Bump, which collects GPS and accelerometer data from phones riding in automobiles. Unfortunately, lots of things can make a smartphone sense a bump in the road. There are speed bumps, manhole covers, and railroad tracks, and temporary obstacles like abandoned groceries; the smartphone’s owner could always just drop it on the floor of the car by accident. In order to be useful, Street Bump needed an algorithm that could weed out the real potholes from the spurious incidents.
“It was clear that we needed some serious data analysis,” says Nigel Jacob of the Mayor’s Office of New Urban Mechanics. “It didn’t make any sense for us to have two people in a room thinking about it. We decided it was better to task a broad audience of people.”
The mayor’s office turned to InnoCentive, a company based in Waltham, Massachusetts, that organizes crowdsourcing challenges. Liberty Mutual Insurance (which could presumably benefit from fewer claims on its auto insurance policies) agreed to put up $25,000 to fund the Street Bump Challenge, which began on April 28, 2011, and ran for four months.
Aboufadel had been watching the InnoCentive website for problems that his students could work on. “When I saw this, I saw something that involves detecting spikes or jumps in data,” Aboufadel says. “That is something that wavelets are good for. I’m like the proverbial man with a hammer, to whom everything looks like a nail. Wavelets are my hammer.”
Aboufadel posed the pothole problem to his summer research advisees, Sara Jane Parsons of Indiana University of Pennsylvania and Nathan Marculis of Grand Valley State. The two students worked on it for eight weeks as part of a Research Experiences for Undergraduates program at Grand Valley.
To begin, Parsons and Marculis used the phone’s bearing and orientation information to define \(x\)-, \(y\)-, and \(z\)-coordinates for each incident. They weeded out incidents in which the acceleration or the velocity was too low. Then they applied a Cohen–Daubechies–Feauveau 9/7 filter (also used in JPG image compression) to enhance the detection of spikes in the acceleration data. “We used that one for a couple reasons,” Aboufadel says. “It has a certain symmetry that other wavelets don’t have. Also, because it averages nine data points at a time, we thought that it would be just long enough to capture the slowing down and speeding up, the typical behaviors for a pothole.” The smartphone app records the acceleration three times a second, so nine data points would represent three seconds of real time.
Unfortunately, the accelerometers in a cell phone are relatively primitive, and they will often miss the moment a car hits a pothole. Other researchers—a group at MIT led by Jakob Eriksson and a group at Microsoft Research in Bangalore—equipped vehicles with accelerometers in earlier studies, but they used sophisticated instruments that could record more than 300 data points per second. Thus, a significant part of the Street Bump Challenge was to deal with low-resolution data. The teams had to collate multiple recordings by multiple vehicles along the same street, some of which recorded a bump while others didn’t. Even when two cars hit the same pothole, they would not necessarily report it in exactly the same location, because of the cars’ motion and because of inaccuracies in the GPS readings.
In order to detect correlated incidents, Parsons and Marculis set up a connected graph of all the reported incidents based on a road map and computed a minimal spanning tree, using Kruskal’s algorithm. They then deleted the longest edges of the tree. “What’s left is a forest of mini-trees,” Aboufadel explains. “We assumed each cluster was an anomaly, and we computed its centroid.” That gave them an estimate for the location of the pothole. “This method captured what we wanted, and it was not hard to implement. It also was easy to explain how the algorithm worked. I’ve done clustering with eigenvalues and eigenvectors before, and people think you’re speaking Greek,” Aboufadel says.
This relatively low-tech approach worked well on the training data, identifying 9 of 11 potholes. It also worked well enough on the test data to be named one of the three prizewinners. The other two winning entrants were Elizabeth Yip, a software engineer from the state of Washington, and Sprout & Co., a community science cooperative from Somerville, Massachusetts. Each of the winning groups received a $9000 share of the prize money.
“The students are so excited,” Abou-fadel said. “I don’t think that at the end of the summer they believed something like this could happen.”
According to InnoCentive, the Boston mayor’s office has already received hundreds of requests for information about the pothole-detecting algorithms. They are now combining the strong points of all three winning algorithms into one package and developing a user-friendly interface.
“There is a lot of interest out there in creating competitions to address urban challenges,” says Jacob. “Our critique in general is that such challenges are incredibly broad. This was an experiment for us to see if we could take a well-articulated technical problem and get more depth in analysis. What we’ve seen is the development of an app that will improve the city of Boston.” And maybe your city next?