Home Articles A Real-Time Precise Fuzzy Algorithm for Map Matching via GPS

A Real-Time Precise Fuzzy Algorithm for Map Matching via GPS


M.R.Mosavi
Assistant Professor, Department of Electrical Engineering
Behshahr University of Science and Technology, Behshahr 48518-78413, Iran
Email: [email protected]

Abstract
In this paper, a fuzzy map matching method is proposed, which uses a digital road map to correct the GPS position error. The proposed algorithm is easy to calculate. It requires little computation time without need to extra sensors and can find the mobile exact position which moves on the road. The effectiveness of this algorithm is verified by the real road experiments. For the experiments, a car navigation system is implemented with a low cost GPS receiver and a microcontroller chip. The real road experiments demonstrate the effectiveness and applicability of the proposed algorithm for accurate navigation with low cost GPS receivers. The results show that real-time positioning error reduces from 25m to less than 1.5m using proposed fuzzy map matching algorithm. Moreover, the system is cheaper and more efficient than conventional systems.

I. Introduction
Global Positioning System (GPS) is widely used in the real-time precise positioning. The mobile determined positions using GPS receivers could be displayed in electronic map. However, because of errors exist in GPS and also in digital maps, it is not possible to ensure that mobile positions register properly on a digital map. The result this is that a mobile may be seen to be moving over a building or into the sea. To avoid this problem, map matching method can be used to improve mobile position display precision over an electronic map [1].

A map matching method using a digital road map is a useful approach to correct these errors. In other words, map matching is a scheme for finding the mobile accurate position on the road. As the mobile is running on the road, the positioning error can be reduced by map matching algorithm if we know the road on which the mobile is [2].

There are a lot of map matching methods based on the geometric approaches. These methods find the road which is close to the mobile trajectory. In these algorithms, it is difficult to calculate the nearest road and it requires hard calculations, which leads to a time consuming. Another map matching algorithm is to use conditional probability. This algorithm is more robust than geometric method and it can cover from false positioning quickly. However, it requires more computation time and more memory to store the mobile trajectory [3].

In this paper, a new fuzzy map matching algorithm is proposed for reducing of GPS position error. It is easy to implementation and requires little computation. Also, this method can find the mobile exact position on the road. A car navigation system is developed for the real road experiments. The effectiveness and applicability of the proposed algorithm is verified by the real road experiments.

This paper is organized as follow. Section II explains proposed map matching algorithm. The hardware implementation of navigation system is described in section III. Section IV shows some experimental results with real developed car navigation system. Conclusions are explained in section V.

Abstract
In this paper, a fuzzy map matching method is proposed, which uses a digital road map to correct the GPS position error. The proposed algorithm is easy to calculate. It requires little computation time without need to extra sensors and can find the mobile exact position which moves on the road. The effectiveness of this algorithm is verified by the real road experiments. For the experiments, a car navigation system is implemented with a low cost GPS receiver and a microcontroller chip. The real road experiments demonstrate the effectiveness and applicability of the proposed algorithm for accurate navigation with low cost GPS receivers. The results show that real-time positioning error reduces from 25m to less than 1.5m using proposed fuzzy map matching algorithm. Moreover, the system is cheaper and more efficient than conventional systems.

I. Introduction
Global Positioning System (GPS) is widely used in the real-time precise positioning. The mobile determined positions using GPS receivers could be displayed in electronic map. However, because of errors exist in GPS and also in digital maps, it is not possible to ensure that mobile positions register properly on a digital map. The result this is that a mobile may be seen to be moving over a building or into the sea. To avoid this problem, map matching method can be used to improve mobile position display precision over an electronic map [1].

A map matching method using a digital road map is a useful approach to correct these errors. In other words, map matching is a scheme for finding the mobile accurate position on the road. As the mobile is running on the road, the positioning error can be reduced by map matching algorithm if we know the road on which the mobile is [2].

There are a lot of map matching methods based on the geometric approaches. These methods find the road which is close to the mobile trajectory. In these algorithms, it is difficult to calculate the nearest road and it requires hard calculations, which leads to a time consuming. Another map matching algorithm is to use conditional probability. This algorithm is more robust than geometric method and it can cover from false positioning quickly. However, it requires more computation time and more memory to store the mobile trajectory [3].

In this paper, a new fuzzy map matching algorithm is proposed for reducing of GPS position error. It is easy to implementation and requires little computation. Also, this method can find the mobile exact position on the road. A car navigation system is developed for the real road experiments. The effectiveness and applicability of the proposed algorithm is verified by the real road experiments.

This paper is organized as follow. Section II explains proposed map matching algorithm. The hardware implementation of navigation system is described in section III. Section IV shows some experimental results with real developed car navigation system. Conclusions are explained in section V.

II. Proposed Map Matching Algorithm Design
q is error between the mobile measured position and the desired route. Also, d is the mobile measured position distance to the desired route. The relationships between the obtained trajectory vector (®a) and the reference vector (®r) are shown in Fig.1.


Fig.1. q and d parameters definition
The calculations for q and d are explained below. We compute q by finding the inner of the trajectory vector and the reference vector, wherein:

Note that and are positive values. As evidenced by Fig.2, is obtained as follow:

q and d are fed into fuzzy system of Fig.2. q’ is the fuzzy system output and defined as rotation angle of trajectory vector for mapping. After fuzzification, rule inference, and defuzzification, q’ is generated for rotation angle of trajectory vector.


Fig.2. Proposed fuzzy system
The design procedures for the fuzzy system are as follows:
Step1: Fuzzification. A membership function is utilized to convert the input data into a fuzzy value. The triangular shaped membership functions are defined into the five sets of Large Negative (LN), Small Negative (SN), Zero (ZE), Small Positive (SP), and Large Positive (LP), as shown in Fig.3.

Fig.3. Triangular shaped membership functions
Step2: Fuzzy Inference. After considering the various mapping situations affecting, we are able to define the rules base as shown in table1 [4].
Table1. Rules Base of the fuzzy system of Fig.2

Step3: Defuzzification. The system herein utilizes the height method of defuzzification to reduce microprocessor calculation time. Since the fuzzy system rules are known to have 17 inference rule antecedent propositions, it is first necessary to computer the grade of membership for each inference rule proposition. If q and d are the fuzzy system inputs, then the grade of the i-th inference rule is:

Where, mAi1 (q) and mAi2 (d) are the membership values of q and d in the membership functions sets Ai1 and Ai2, respectively. Min operation represents the intersection of the fuzzy set to obtain minimum value. To solve for the overall inference result of q’ from each inference rule, it is derived by adding the average value, so [5]:

Where, q’-i is the i-th inference rule center. The q’ is used as the fuzzy controller’s output signal. Fig.4 shows proposed map matching algorithm for 4 points A1, A2, A3, and A4 .

Fig.4. The proposed map matching algorithm for 4 points A1, A2, A3, and A4
III. Hardware Implementation
A car navigation system consists of several subsystems, such as a positioning system, a route guidance system, and a user interface system. The main role of a car navigation system is to find the car position as precisely as possible. In this research, a low cost GPS engine manufactured by Rockwell Company was used. The Rockwell “Microtraker Low Power (MLP)” is a single board, five parallel-channels, L1-only Coarse Acquisition (C/A) code capability. To read the GPS receiver data as well as to calculate the car position simultaneously at every sampling time, the developed navigation system consists of two serial ports, a sensor handling serial port for the GPS receiver and a serial port for communication to computer. A 16-bit microcontroller 80C196KB is used for the map matching algorithm. All the programs for microcontroller and computer are coded in C-language and visual basic 6, respectively. As mentioned above, the developed car navigation system is a subsystem that has the positioning ability only. The mapped position from the developed car navigation system is sent to the notebook computer through RS232 serial communication. The map matched position is displayed on the notebook monitor.

 

IV. Experimental Results
Measurements reading were actually observed in a graphics format displayed on the computer monitor. Fig.5 show a sample map matching using the proposed algorithm.


Fig.5. A sample map matching using the proposed algorithm
Performance of the proposed algorithm map matching was evaluated by data sets that were collected on the building of Computer Control and Fuzzy Logic Research Lab in the Iran University of Science and Technology. Many experiments were performed on urban streets, which have different features such as small roads, wide roads, and etc. The developed navigation system discussed in section III was used. No additional sensors were used. The mapped position of the car was sent to 80586 notebook computer, where the map matching was performed. Fig.6, Fig.7, and Fig.8 show the desired, measured, and mapped routes, respectively.

Fig.6. The desired route for the mobile unit


Fig.7. The Measured route for the mobile unit


Fig.8. The Mapped route for the mobile unit

V. Conclusions
In this paper, a new map matching algorithm and its rules have been proposed. For experiments, a car navigation system was developed with a small number of sensors, such as a low cost GPS receiver and a microcontroller chip. The effectiveness of the proposed map matching algorithm was verified with several experiments. In the experiments, mapped car position was precise, so that real-time positioning error reduces from 25m to less than 1.5m. Moreover, the proposed algorithm needs little computation time. This feature makes it suitable for using in a car navigation system with a low power microcontroller.

References:

  1. Fenglin Guo, Yuesheng Ji, and Guorong Hu, “Methods for Improving the Accuracy and Reliability of Vehicle-borne GPS Intelligence Navigation”, GIS Development Magazine, November 2002.
  2. Sinn Kim and Jong-Hwan Kim, “Q-factor Map Matching Method using Adaptive Fuzzy Network”, IEEE Conference on Fuzzy Systems, Vol.2, August 1999, pp.628-633.
  3. Sinn Kim and Jong-Hwan Kim, “Adaptive Fuzzy-Network-Based C-Measure Map-Matching Algorithm for Car Navigation System”, IEEE Transactions on Industrial Electronics, Vol.48, No.2, April 2001, pp.432-441.
  4. K.-Y. Tu, F.-R. Chang, L.-S. Wang, and G.-S. Song, “Navigation and Control of Unmanned Boat via GPS”, ION Technical Meeting, January 1997, pp.617-621.
  5. M.R.Mosavi, “Fuzzy Point Averaging of the GPS Position Components”, Map Asia Conference 2004, 26-29 August, 2004, Beijing, China.