Search Results

Map matching determines which road a vehicle is on based on inaccurate measured locations, such as GPS points. Simple algorithms, such as nearest road matching, fail often. We introduce a new algorithm that finds a sequence of road segments which simultaneously match the measured locations and which are traversable in the time intervals associated with the measurements. The time constraint, implemented with a hidden Markov model, greatly reduces the errors made by nearest road matching. We trained and tested the new algorithm on data taken from a large pool of real drivers.

This paper develops and tests algorithms for predicting the end-to-end route of a vehicle based on GPS observations of the vehicle's past trips. We show that a large portion a typical driver's trips are repeated. Our algorithms exploit this fact for prediction by matching the first part of a driver's current trip with one of the set of previously observed trips. Rather than predicting upcoming road segments, our focus is on making long term predictions of the route. We evaluate our algorithms using a large corpus of real world GPS driving data acquired from observing over 250 drivers for an average of 15.1 days per subject. Our results show how often and how accurately we can predict a driver's route as a function of the distance already driven.