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

Printer Friendly Format

Page 2 of 3
| Previous | Next |

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

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, m_Ai1 (q) and m_Ai2 (d) are the membership values of q and d in the membership functions sets A_i1 and A_i2, 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 A₁, A₂, A₃, and A₄ .

Fig.4. The proposed map matching algorithm for 4 points A₁, A₂, A₃, and A₄
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.