Volume 1, Issue 2
The Mathematics of High-Tech Highways
John Rice is also involved in the Taiwanese American Occultation Survey (TAOS), an effort to detect comets in the Kuiper Belt beyond Neptune.
How long 'til we get there? That question is at the tip of every child's tongue during long road trips. The answer is squarely in the realm of probability and statistics. Just ask John Rice, a UC Berkeley professor of statistics searching for meaning in masses of traffic data.
Rice and his colleagues across campus in the College of Engineering are developing a system that taps California's pre-existing freeway sensor network for data to intelligently deal with congestion. The Freeway Performance Measurement System (PeMS) is a repository for real-time traffic data that streams into the California Department of Transportation from thousands of loop detectors, hexagon-shaped wire sensors in the pavement that count cars and measure average speed. Rice devised the statistical algorithms that convert the raw loop data into "news you can use."
Loop detectors on California freeways provide data for Rice's statistical analysis. (Bill Stone/PATH photo)
Already, travelers who log on to the PeMS Web site can be informed of expected travel times at that moment along many common routes. Eventually, the system will be optimized for mobile phone use. PeMS was also designed to help traffic managers make informed decisions about ramp-metering lights and message boards and aid city planners in the study of long-term traffic trends when considering capital improvements.
Creating an accurate picture of a chaotic system like California's freeways is no easy task though. A model is only as good as the data that's fed into it, and, according to Rice, "a lot of the loop detector data is bad."
"There is a great deal of intermittent malfunction and noise in the system," he says.
Basically, the loop detectors are prone to occasional failure. As a result, the two gigabytes of data streaming into PeMS each day is of wildly varying quality. Cleaning that data--identifying bad data and inferring what may be missing--is a matter of statistics.
It's difficult to identify a broken detector based on a single abnormal measurement, Rice explains. However, by comparing a day's worth of measurements from a single detector with the measurements from many other detectors, the software can "easily distinguish bad behavior from good." Once the bad data is removed, those holes must be filled through "imputation," statistical guesses based on historical data or measurements from neighboring loop detectors.
Of course, what a driver really wants to know is how long it will take to get from one place to another at some time in the future. For example, say you have a meeting across town in two hours. Ideally, you would visit the PeMS Web site right away and enter your origin, destination, and desired time of arrival. The system would then suggest a departure time and the fastest route. To that end, Rice and his colleagues have developed novel prediction algorithms.
One of their predictive techniques is based on a statistical model called "linear regression," a term borrowed from the phrase "regressing towards the average." Essentially, the algorithm works on the assumption that if current congestion is especially bad compared to historical data, it's likely to improve and vice versa. Based on the current state of the freeway, an equation then forecasts the total travel time between two points.
The Berkeley Highway Laboratory is a 2.7 mile section of Interstate 80 that's observable with a bank of video cameras. (courtesy ITS)
To improve the quality of the predictions, Rice and his collaborators are now exploring the use of video cameras to complement existing loop detectors. A few miles south of the Berkeley campus, adjacent to the San Francisco-Oakland Bay Bridge, more than a dozen video cameras mounted high above the freeway keep a constant vigil on surrounding traffic conditions. The surveillance cameras are part of the Berkeley Highway Laboratory, an Institute of Transportation Studies test-bed for traffic monitoring systems.
"Cameras provide better spatial coverage than loop detectors and are easy to replace if they break," Rice says. "The problem with video though is that it's very difficult for computers to spot cars and track them to accurately measure speed and congestion."
Indeed, machine vision is one of computer science's toughest challenges. The difficulty is compounded by the fact that the cameras are mounted relatively far away atop a building, resulting in low-resolution video. So instead of honing in on particular vehicles, the technique devised by Rice and graduate student Young Cho represents each lane in a video frame as a multi-colored "intensity profile." When the profiles are stacked, an "intensity flow" across time and space becomes visible. These stripes, known as moving peaks, contain information about the aggregate behavior of the vehicles and are easily analyzed by a computer.
"By looking at how the images evolve, we can use our algorithm to abstract useful information like local speed estimates," Rice says.
Indeed, while Rice's formulas, graphs, and algorithms may resemble hieroglyphics to the uninitiated, his research is actually a bridge between a somewhat esoteric science and everyday life.
"I've always been attracted to statistics because it sits between math and the physical world," Rice says.