Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The problem of matching measured latitude/longitude points to roads is becoming increasingly important. This paper describes a novel, principled map matching algorithm that uses a Hidden Markov Model (HMM) to find the most likely road route represented by a time-stamped sequence of latitude/longitude pairs. The HMM elegantly accounts for measurement noise and the layout of the road network. We test our algorithm on ground truth data collected from a GPS receiver in a vehicle. Our test shows how the algorithm breaks down as the sampling rate of the GPS is reduced. We also test the effect of increasing amounts of additional measurement noise in order to assess how well our algorithm could deal with the inaccuracies of other location measurement systems, such as those based on WiFi and cell tower multilateration. We provide our GPS data and road network representation as a standard test set for other researchers to use in their map matching work.

REFERENCES

• 1: E. Agapie , G. Chen , D. Houston , E. Howard , J. Kim , M. Y. Mun , A. Mondschein , S. Reddy , R. Rosario , J. Ryder , A. Steiner , J. Burke , E. Estrin , M. Hansen , M. Rahimi, Seeing our signals: combining location traces and web-based models for personal discovery, Proceedings of the 9th workshop on Mobile computing systems and applications, February 25-26, 2008, Napa Valley, California [doi>10.1145/1411759.1411762]
• 2: Helmut Alt , Alon Efrat , Günter Rote , Carola Wenk, Matching planar maps, Journal of Algorithms, v.49 n.2, p.262-283, November 2003 [doi>10.1016/S0196-6774(03)00085-3]
• 3: Sotiris Brakatsoulas , Dieter Pfoser , Randall Salas , Carola Wenk, On map-matching vehicle tracking data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 4: Gather, U. and V. Schultze, Robust Estimation of Scale of an Exponential Distribution. Statistica Neerlandica, 2001. 53(3): p. 327--341.
• 5: Greenfeld, J. S., Matching GPS Observations to Locations on a Digital Map, in 81th Annual Meeting of the Transportation Research Board. 2002: Washington, DC, USA.
• 6: http://www.bing.com/maps/. {cited 2009}.
• 7: http://www.dash.net/. {cited 2009}.
• 8: http://www.inrix.com/. {cited 2009}.
• 9: Hummel, B., Map Matching for Vehicle Guidance, in Dynamic and Mobile GIS: Investigating Space and Time, J. Drummond and R. Billen, Editors. 2006, CRC Press: Florida.
• 10: Kim, S. and J.-H. Kim, Adaptive Fuzzy-Network-Based C-Measure Map-Matching Algorithm for Car Navigation System. IEEE Transactions on Industrial Electronics, 2001. 48(2): p. 432--441.
• 11: Krumm, J., A Markov Model for Driver Turn Prediction, in Society of Automotive Engineers (SAE) 2008 World Congress. 2008: Detroit, Michigan, USA.
• 12: Krumm, J., J. Letchner, and E. Horvitz, Map Matching with Travel Time Constraints, in Society of Automotive Engineers (SAE) 2007 World Congress. 2007: Detroit, Michigan, USA.
• 13: Lamb, P. and S. Thiebaux, Avoiding Explicit Map-Matching in Vehicle Location, in 6th World Conference on Intelligent Transportation Systems (ITS-99). 1999: Toronto, Canada.
• 14: Patterson, D. J., et al., Inferring High-Level Behavior from Low-Level Sensors, in Fifth Internation Conference on Ubiquitous Computing (UbiComp 2003). 2003, Springer. p. 73--89.
• 15: VanDiggelen, F., GNSS Accuracy: Lies, Damn Lies, and Statistics, in GPS World. 2007. p. 26--32.
• 16: White, C. E., D. Bernstein, and A. L. Kornhauser, Some map matching algorithms for personal navigation assitants. Transportation Reserach Part C: Emerging Technologies, 2000. 8(1--6): p. 91--108.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Measurement

Keywords:
driving routes, location, map matching, road map