Anyone who’s driven in a crowded downtown knows that parking can mean almost endless circling in the hunt for a space close to your destination. Now engineers at Rutgers University in New Jersey have combined simple ultrasonic sensors, GPS receivers, and cellular data networks to create a low-cost, highly effective way to find the nearest available parking space.

The Rutgers researchers say that making detailed parking data widely available via Web-based maps or navigation systems could alleviate traffic congestion by allowing travelers to decide whether to park in a central garage, hunt for street parking, or choose another mode of transportation in advance. If drivers choose street parking, it could help by suggesting parking spaces to users through a navigation device or cell phone.

The team, led by assistant professors Marco Gruteser and Wade Trappe, mounted ultrasonic distance sensors on the passenger-side doors of three cars. Using data collected over two months as the drivers commuted through Highland Park, NJ, the researchers developed an algorithm that translated the ultrasound distance readings into a count of available parking spaces that was 95 percent accurate. By combining this with GPS data, they also generated maps of which spaces were occupied and which were open that were over 90 percent accurate.

Traffic congestion is a huge problem nationwide, particularly in downtown areas. A study by Transportation Alternatives, a New York City transportation advocacy group, found that up to 45 percent of the traffic in Manhattan is generated by cars circling the block looking for parking. In 2006, Donald Shoup, a professor in the department of urban planning at the University of California, Los Angeles, calculated that, over the course of a year, vehicles looking for parking in one small business district of Los Angeles burned 47,000 gallons of gasoline and produced 730 tons of carbon dioxide. The problem is so serious that some cities, such as San Francisco, have invested millions of dollars in “smart parking infrastructure”–systems that detect the presence of vehicles in parking spots using fixed sensors installed into the asphalt or in parking meters.

But such systems work only for metered or slotted parking spaces. They also have large installation and operating costs. The SFpark project in San Francisco covers 6,000 spaces–only about 25 percent of available street parking spots. At an estimated cost of $500 to install and maintain each sensor for a year, that adds up to $3 million. The Rutgers team set out to create a lower-cost alternative that can work for both metered and unslotted parking spaces.

The engineers devised a prototype of a sensing platform using a $20 ultrasonic sensor that reports the distance to the nearest obstacle and a $100 GPS receiver that notes the corresponding location. They connected both to a lightweight PC with a Wi-Fi card to transmit the data to a central server.

The algorithm that the researchers devised bases the detection of parked vehicles on dips in the ultrasonic sensor readings. To distinguish parked cars from other, smaller obstacles in the sensor’s path–for instance, trees, recycling bins, or people–they compared the width and depth of each dip with thresholds determined from a round of training data in which the engineers marked each sensor dip as a car or another object. They then developed filters that remove all dips that have a depth of less than the threshold that the algorithm “learned” from the training data. For slotted parking spaces, the algorithm had a detection accuracy of about 95 percent. For unslotted parking, they achieved about 96 percent accuracy.

The team also integrated its detection data with reference maps to create a spot-accurate map of parking availability. They faced a major challenge accomplishing this because the location coordinates provided by a GPS receiver are only typically accurate to three meters. With an approximate parking spot length of about seven meters, a vehicle could easily be matched to an incorrect adjacent spot. So they developed another algorithm that uses the ultrasonic sensor readings to detect certain fixed objects, such as trees and street signs. This allowed them to decrease their error rate by more than half.

After proving that the concept worked, Gruteser and his colleagues wanted to see whether such a system could effectively be deployed in a large city by putting sensor systems in vehicles that regularly drive around, such as taxis, police cars, and other government vehicles. The team used a public data set of 536 taxicabs in San Francisco to study the cars’ mobility patterns. While the cabs visited some parts of the city too rarely to make any data they collected useful for a real-time parking map, the sampling provided by these same cabs in the downtown area of San Francisco was more than adequate to cover the smaller area.

The engineers estimate that they could cover the downtown San Francisco area using only 300 cabs for roughly $200,000, a cost-saving factor of about 15 over a fixed-sensor system. “We know that this savings is related to the fact that we’re getting a nonguaranteed, random sampling of parking spaces, versus the continual monitoring offered by fixed sensor systems,” Gruteser says.

Developing a system for real-world deployment shouldn’t be that difficult, Gruteser says. The team chose to use ultrasonic range finders because of their relatively low cost compared to laser range finders and automotive radars, better nighttime operation compared to cameras, and their increasing availability in parking-assistance and automated parking systems in cars. This means that engineers could potentially use ultrasonic sensors already present in vehicles in a future parking-monitoring system.

While the researchers relied on opportunistic Wi-Fi connections to transmit their data from the cars to the central server, vehicles could report their data over widely available cellular modems, they say. Finally, Gruteser says, it would be fairly simple to distribute parking availability information over the Internet, similar to the way Google overlays traffic congestion data on its maps. Or, working with navigation device companies, it could be sent to commercial GPS receivers.

The Rutgers team has submitted its project report to the Annual International Conference on Mobile Systems, Applications, and Services (Mobisys), to be held in June in San Francisco.