An on-board computer monitored driver behavior by recording Global Positioning System (GPS) position signals during trips. GPS receivers pinpoint geographic position by triangulating on radio signals from GPS satellites. These receivers generate a position estimate using latitude, longitude, and altitude. They also provide other information, such as a time stamp for each position detection.
![\includegraphics[width=5in]{GPS-map.eps}](img1.gif) |
We used real-world, differential GPS data collected from two different drivers and vehicles during the course of normal daily driving. Differential GPS provides more accurate estimates of position than basic GPS. Differential GPS uses fixed location receivers on earth to determine the current error in the GPS signal. A radio station transmits a correction for this error to be used by receivers to improve the accuracy of basic GPS. We used a Garmin integrated satellite antenna/receiver, a DCI differential corrections unit, and a LG Phenom hand-held PC to detect and record position. Estimated position accuracy is 5-10 meters.
We employed a map matching procedure to reconstruct the path taken during a trip. This procedure assigns each recorded position to exactly one of the road segments stored in the digital road map. Since the segment sequence describes the path taken during a trip, each segment in the sequence must be connected the next. Noise in the position estimates and the segment locations stored in the digital map introduce uncertainty into map matching. We implemented a backtracking best-first-search algorithm to find the most likely path. This algorithm finds the path nearest to entire sequence of positions for a trip. The algorithm reduces overall uncertainty and eliminates discontinuous paths by summing distance over many segments rather than over just one segment.
To begin, the algorithm adds those segments in the digital road map that are closest to the first point in the position sequence to a path list. It iteratively expands paths on the list starting with the path with lowest average distance between the positions so far and the segments to which they are assigned. It expands a path by 1) adding all neighboring segments to the path list and 2) computing a new average distance. The list is pruned at each iteration so that at most 100 nearest paths remain. At the end, the output of the algorithm is a list of segment identifiers, the direction traveled on the segment, and a time stamp indicating when the driver entered that road segment.