Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-01-22T12:52:58.304Z Has data issue: false hasContentIssue false
  • English
  • Français

A Hidden Markov Model-Based Map-Matching Algorithm for Wheelchair Navigation

Published online by Cambridge University Press:  15 June 2009

Ming Ren  and
Hassan A. Karimi
Ming Ren*
Affiliation:
(University of Pittsburgh)
Hassan A. Karimi
Affiliation:
(University of Pittsburgh)
*
(Email: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Application of map-matching techniques to GPS positions can provide accurate vehicle location information in challenging situations. The Hidden Markov Model (HMM) is a statistical model that is well known for providing solutions to temporal recognition applications such as text and speech recognition. This paper introduces a novel map-matching algorithm based on HMM for GPS-based wheelchair navigation. Given GPS positions, a hidden Markov chain model is established by using both geometric data and the topology of sidewalk segments. The map-matching algorithm employs the Viterbi algorithm to estimate correct sidewalk segments as hidden states in a HMM in order to match GPS trajectory on the corresponding segment sequence. The HMM-based map-matching algorithm was validated on a campus sidewalk network for wheelchair navigation. The results show an improvement in tracking a wheelchair in dense urban conditions both in accuracy and in computational time.

Keywords

Hidden Markov ModelMap-matchingWheelchair navigation
Type
Research Article
Information
The Journal of Navigation , Volume 62 , Issue 3 , July 2009 , pp. 383 - 395
Copyright
Copyright © The Royal Institute of Navigation 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Cappé, O., Moulines, E., Rydén, T. (2005). Inference in Hidden Markov Models, Published by Springer.Google Scholar
Ephraim, Y. and Merhav, N. (2002). Hidden Markov processes, IEEE Trans. Inform. Theory, vol. 48, pp. 1518–1569.CrossRefGoogle Scholar
Forney, G. D. (1973). The Viterbi algorithm. Proceedings of the IEEE 61(3): 268–278.CrossRefGoogle Scholar
Geotools (2008). The java GIS toolkit, http://sourceforge.net/projects/geotools/Google Scholar
Hidden Markov model. Wikipedia, the free encyclopedia, http://en.wikipedia.org/wiki/Hidden_Markov_modelGoogle Scholar
Jagadeesh, G. R., Srikanthan, T. and Zhang, X. D. (2004). A Map Matching Method for GPS Based Real-Time Vehicle Location, Journal Of Navigation, 57, 429–440.Google Scholar
Karimi, H A, Conahan, T. and Roongpiboonsopit, D. (2006). A Methodology for Predicting Performances of Map-Matching Algorithms, W2GIS 202–213.CrossRefGoogle Scholar
Kasemsuppakorn, P. and Karimi, H. A. (2008). Data requirements and spatial database for personalized wheelchair navigation, 2nd International Convention on Rehabilitation Engineering & Assistive Technology.Google Scholar
Krumm, J., Letchner, J. and Horvitz, E. (2007). Map Matching with Travel Time Constraints, SAE 2007 World Congress, April 16–19.CrossRefGoogle Scholar
Meng, Y. (2006). Improved Positioning of Land Vehicle in ITS Using Digital Map and Other Accessory Information, PhD Thesis, Department of Land Surveying and Geoinformatics, Hong Kong Polytechnic University.Google Scholar
Ochieng, W. Y., Quddus, M. A. and Noland, R. B. (2004). Map-matching in complex urban road networks, Brazilian Journal of Cartography (Revista Brasileira de Cartografia) 55 (2), 1–18.Google Scholar
Quddus, M. A., Ochieng, W. Y., Zhao, L., Noland, R B 2003 A general map-matching algorithm for transport telematics applications, GPS Solutions 7 (3), 157–167.CrossRefGoogle Scholar
Quddus, M. A., Noland, R. B., Ochieng, W. Y. (2004). Validation of map-matching algorithm using high precision positioning with GPS, Journal of Navigation 58, 257–271.Google Scholar
Quddus, M. A. (2006). High Integrity Map Matching Algorithms for Advanced Transport Telematics Applications A thesis of the University of London.Google Scholar
Quddus, M. A., Ochieng, W. Y. and Noland, R. B. (2007). Current map-matching algorithms for transport applications: State-of-the art and future research directions, Transportation Research Part C 15, pp. 312–328.Google Scholar
Rabiner, L. R. (1989). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257–286.CrossRefGoogle Scholar
Ren, M., Karimi, H. A. (under review, 2008). A Chain-Code-Based Map Matching Algorithm for Wheelchair Navigation. Transactions in GIS.Google Scholar
Taylor, G., Blewitt, G., Steup, D., Corbett, S., Car, A. (2001). Road reduction filtering for GPS-GIS navigation, Transactions in GIS, ISSN 1361–1682, 5(3), 193–207.CrossRefGoogle Scholar
Taylor, G., Brunsdon, C., Li, J., Olden, A., Steup, D., Winter, M. (2006). GPS accuracy estimation using map-matching techniques: Applied to vehicle positioning and odometer calibration, Computers, Environments, and Urban Systems 30, 757–772.Google Scholar