Synthesis and Analysis of the Map-Matching Algorithm for Car Navigation Systems

S. P. Dmitriev, O. A. Stepanov, B. S. Rivkin, D. A. Koshaev, D. Chung

Abstract:	At present, car navigation systems using digital road maps (DRM), data from dead reckoning and/or satellite systems are widely applied [1-6]. It is not uncommon that DRM are used not only to display a car position but also to correct it [1-4]. The correction is performed by comparing a car route calculated from the data obtained from the satellites or dead reckoning with a set of possible routes formed from the map. Using the map data about the road along which a car is moving it is possible to determine the car position more exactly. The peculiarity of the information processing in the navigation systems using the map data is the nonlinear character of this problem the fact that considerably complicates the synthesis of the algorithms and analysis of their accuracy. By now no mathematical framework capable of accounting for the nonlinear character of the problem and all the available information entirely has been proposed for the problem of car navigation discussed here. In real systems without any justification the initial problem is substituted, as a rule, for a few separate subproblems: identification of the road, linear filtering of the data on a straight road, detection of the road turn, and so on. It is essential that only part of the available information is used in solving each of the separate subproblems. It should be noted that the navigation method based on comparison of measurements and data from a map (mapping or map-matching navigation) has been quite often used in airborne and marine navigation systems [7-11]. The algorithms of data processing for airborne and marine map-matching navigation are also nonlinear and the Markovian filtering theory is effectively used to develop the algorithms for these systems [7,10,11]. By analogy with it this paper suggests using the Markovian filtering theory as a mathematical framework in solving the car navigation problem under consideration. This approach allows taking account of the nonlinear character of the problem and all the available information entirely. It is essential that the problem of identification of the road on which the car is most probably located and the estimation of the car’s position on this road to the maximum accuracy are solved within a unified statement. In this paper the described approach was taken as a basis for the synthesis of the algorithm and analysis of the potential accuracy. The efficiency of the algorithm developed is tested by using real information about the coordinates, speed and course obtained from a satellite system.
Published in:	Proceedings of the 55th Annual Meeting of The Institute of Navigation (1999) June 27 - 30, 1999 Royal Sonesta Hotel Cambridge, MA
Pages:	505 - 514
Cite this article:	Dmitriev, S. P., Stepanov, O. A., Rivkin, B. S., Koshaev, D. A., Chung, D., "Synthesis and Analysis of the Map-Matching Algorithm for Car Navigation Systems," Proceedings of the 55th Annual Meeting of The Institute of Navigation (1999), Cambridge, MA, June 1999, pp. 505-514.
Full Paper:	ION Members/Non-Members: 1 Download Credit Sign In