GISdevelopment.net ---> AARS ---> ACRS 1998 ---> Mapping From Space Map-Matching Algorithm of GPS Vehicle Navigation System Pen -Shan Hung , Tsui -Chuan Su Geographic Information System Research Center, Reng Chia University 100 Wenhwa Rd . Taichung, Taiwan Tel : (886)-4-4516669, Fax : (886)-4-4519278 E-mail : tcu@gis.fcu.edu.tw Abstract : In general , Global Positioning System (GPS) has been widely used in Vehicle Navigation Systems. It helps the users to determine the vehicle position or provides users with proper maneuver instruction .Because of some biases, such as SA effect, buildings canyon around cities , thus those affect and block GPS signals .In addition , the road network of the digital Map is not accurate enough. These cause vehicle position not to locate precisely on the road network of the digital map. Therefore a map-matching algorithm is necessary. An optimal algorithm is developed through the analysis of some driving conditions (such as turning. U- turn or drive to parking lots).The algorithm is presented. Instroduction In vehicle Navigation System , Map- Matching approach plays an important role (Cring and Drane , 1994; Zhao,1997). It is a method of using digital map data and GPS satellite signal to locate the vehicle on proper poison relative to digital map. In general ,the vehicle location is not necessarily on the road of digital map. We try to filter the unreasonable GPS signals and remove the biases of GPS signals by using map- matching system .We expect to find the stability of GPS signals from many tests for different receivers. Sometimes the vehicle location is compatible with the road network and it is not sometimes. Therefore ,it is possible to display vehicle location on the wrong road. First, this paper describes the factor of noise that happens in the GPS positioning process. Then, we develop a map-matching mode by programming and testing. Finally ,we hope to find out a proper algorithm to establish a trust and correct position system and hope to find out a proper algorithm can be used on the car navigation system easily. Map-Matching Algorithm Because of inaccuracy of GPS posting, we need to find the stability of GPS positioning for the receiver we used. DV is the difference between the perpendicular distance point (Vn) at epoch n to road line and the distance of the point (Vn-1)at former epoch. Different GPS recever has different RMS values. Figure 1 demonstrates vehicle tracks with furno's GPS chip, and Figure 2 indicates the RMS valu for the receiver. The RMS value can Represent as the Stability of GPS receiver . Fig. 1 Vechicle tracks with Furuno receiver Fig.2 RMS value of the Furuno receiver. Because of the SA effect and some other, positioning error estimated to be 30-100 meters. Although the positioning error is over 30 meters, the error difference between two sequent epochs is much smaller than 30 m. For the first epoch, the position bias can be determined by comparing the road central line with the vehicle location. The derived position bias can be first used to correct GPS position for the following epochs. The above derived RMS value is used to decide whether the vehicle is on the road or away from the candidate road (or heading for parking lots). If the vehicle is away from the road, then the vehicle location does not necessarily to match on the road of digital map. In general, the vehicle location is not necessarily on the road of digital map. According to the coordinates determined by GPS, the GPS derived coordinates has to be used to decide which road is candidate with high probability. For GIS-based digital map, a curve road is represented by many vertexes. It can't simply calculate perpendicular distance from GPS point to central line. Assuming that GPS point is GI with coordinate (XG1, YG1), from-node of road is S1 with coordinate (XS1, YS1), to-node of road is E1 with coordinate (EE1, YE1). The value of K can be determined. Where is the angle between vector The (Xn, Yn) are the coordinates of the projected point of the road: XN=K*(XE1-XS1)+ X S1 ........................(4) YN=K*(YE1-YS1)+ YS1........................(5) 2) If K < 0, then the vehicle location is not on the candidate road, and the location is away from the from-node S1 3). If K > 1, then the vehicle location is not on the candidate road, and the location is away from the to-note E1 Selecting an accurate candidate road is important, and it affects prediction of nest vehicle location. Fig .3 a Muddy vehicle location In Fig3, the candidate road of G1 is either line or line2. The possibility of making wrong decision is very high. To solve this problem we consider the vehicle traveling direction. In digital road map database the true azimuth of road is recorded, and NMEA data also includes the vehicle direction. Therefore, we can compare these two any try to select the candidate road. After selection of the candidate road, Shown in Fig. 4, We assume current vehicle location is in G1, next vehicle location is G2, if the distance between G1, and E1, (end-node of road segment) are close to a pre-set value, the next turning candidate road will be Line1, Line2 and Line3. G1E, is the azimuth of traveling direction from G1, to E1, point, G2E, is the azimuth from E1, to G2, point. These values of azimuth will be used for judging which road is the candidate. If driver has a U-turn, the from-node and to-node of road segment must be switched. In Fig. 5, assuming current vehicle location is at G1, point, the location of former epoch is G0, endnode of road segment is E1, DHEADING = G1a - G0a If DDISTANCE is negative and larger then a tolerant value and DHEADING > Tolerance, we presume, we presume vehicle has a U-Turn. Fig. 4 Off-Road Segment Case. Fig .5 U- turn Case Analysis Results A few typical road networks and different driving behavior have been tested for the map-matching method. They include simple road network, complicated road network, off-road driving, and U-turn driving etc. Figures 6 to 9 shows that the map-matching has not been tested for some other sophisticated 3-dimensional road networks, since this kind of digital map for 3-D road network is not available yet. The further test is required. Fig.6 Simple Road Case Fig .7 Complicated Road Case Fig.8 Off-Road Driving Case Fig.9 U-turn Driving Case Conclusion A simple map-matching algorithm is successfully used project the vehicle location on the digital map 2-dimensional road network. Within the algorithm, the stability is determined and used to judge whether the vehicle is still on the candidate road or off the candidate road to parking lots. In additions, the traveling direction and the change of vehicle heading are also taken advantage of. We can also use DGPS technology to reduce the GPS positioning error. DGPS should make the map-matching easier. However, vehicle has to be equipped with radio-modem. This will increase the cost to set up the data-link system References Craig A. Scott and C.R. Drane(1994), Increased Accuracy of Motor Vehicle Position Estimation By Utilizin Map Data, Vehicle Dynamics, and other Information Sources, proceeding of Vehicle Navigation and Information Systems. Craig Scott (1994), Impoved GPS Positioning for Motor Vehicles Through Map Matching, Proceeding of Ion GPS-94, Salt Lake City, Utah, pp. 1391-1400 Yilin Zhao (1997), Vehicle Location and Navigation System, Artech House, pp. 83-103.