Underwater map-matching aided inertial navigation system based on multi-geophysical information

Abstract

In order to achieve long-term covert precise navigation for an underwater vehicle, the shortcomings of various underwater navigation methods used are analyzed. Given the low navigation precision of underwater map-matching aided inertial navigation based on single-geophysical information, a model of an underwater map-matching aided inertial navigation system based on multi-geophysical information (gravity, topography and geomagnetism) is put forward, and the key technologies of map-matching based on multi-geophysical information are analyzed. Iterative closest contour point (ICCP) map-matching algorithm and data fusion based on Dempster-Shafer (D-S) evidence theory are applied to navigation simulation. Simulation results show that accumulation of errors with increasing of time and distance are restrained and fusion of multi-map-matching is superior to any single-map-matching, which can effectively determine the best match of underwater vehicle position and improve the accuracy of underwater vehicle navigation.

Keywords

geophysical information / underwater navigation / iterative closest contour point (ICCP) algorithm / Dempster-Shafer (D-S) evidence theory / map-matching

Introduction

Because of the special environment of the underwater vehicle, the adoption of underwater navigation is restricted in many ways. Even with the high positioning accuracy of the global position system (GPS) satellite, signals are still unable to be received underwater. This can be done only towards the shore or over the water, but still easily interfered. The result of dead reckoning is greatly influenced by the speed of ocean currents (the top speed can be up to 2 nmile/h, while the speed of unmanned underwater vehicles (UUVs) under restrictions of power is about 3-6 nmile/h). Vehicle ground speed can be measured by the use of Doppler velocity sonar on condition that vehicles run close to the seabed, but the shortest distance is restricted. There is too much interference of echo signal as to acoustic navigation (long baseline and ultra-short baseline) in areas such as long and narrow waters or the Arctic. Two outcomes result from inertia navigation velocity: accumulative errors by integrating twice and a costly high accuracy inertial navigation sensor [1].

Map-aided navigation is for realizing aided navigation by using the information of static spatial distribution. It is also known as the geophysical characteristics aided navigation technology. Geophysical parameters of geophysical information navigation based on maps include topography, gravity, and geomagnetism. The premise of using geophysical navigation is to equip a high resolution ground map and sensitive sensors. Currently, the map precision of geophysical information and sensors accuracy are not high enough, the ultra high accuracy sensors is of high price, and any single navigation mode cannot meet the requirement of underwater vehicles. In view of the above, the paper puts forward an underwater map-matching aided inertial navigation system based on geophysical information (topography, gravity, and geomagnetism). This system, through map-matching, can supply accurate and reliable positioning information to an underwater vehicle under the conditions of different environments and survey and mapping, with various interferences. It also limits the divergence of inertial navigation errors varying with time and distance, in order to satisfy the requirement of long-term hidden accurate navigation for underwater vehicles [2,3].

System model

The main idea of the navigation method is to realize the real-time acquisition of such geophysical characteristics parameters in the vehicle such as the seabed elevation, gravity values, gravity anomaly values, gravity anomaly gradient values, magnetic values, and magnetic anomaly values. A certain matching algorithm is applied to locate the vehicle in the geophysical characteristic map of the waters, and to estimate the related navigation information. The final accurate navigation information is achieved by the combination of the inertial navigation system and navigation information from matching. The technology comprises access technology of geophysical characteristics parameters, map-matching location technology, data fusion technology, and two-dimensional (2D) map data processing technology.

The basic structure model of the multi-map-matching aided inertial navigation system is shown in Fig. 1. It can be divided, according to the function, into five parts: map-matching module, inertial navigation module, navigation information data fusion module, maps of virtual and display module, and module of manipulation and track planning. The navigation module provides such information as position, velocity, and posture for the vehicle. Maps of the virtual and display module provide the vehicle track and environmental real-time display for manipulating platform. The manipulation and track planning module gives out tracking planning and control parameters of the vehicle according to the navigation information.

The core of the navigation system is the multi-map-matching module in the navigation module, which is shown in Fig. 2. The vehicle’s position and velocity information come from the inertial navigation module and integrated navigation information, and matching results join the navigation information data fusion module. Its composition includes digital map storage, map search, map feature analysis, navigation probability analysis, map generation, geophysical parameter acquisition and matching algorithm modules. According to the input of the vehicle position and velocity information, the map search module searches in digital map database to get the corresponding reference map basic data in vehicle navigable areas. The analysis results of the map features serve as the basis of both determining the reference map for the system and choosing the map track planning of the vehicle and interpolation method. The pretreatment module deals with the on-site data set in real-time processing, and the information corresponding to the reference map is obtained. Meanwhile, the distributed parallel method is applied to the earth’s physical parameters adjustment and filtering.

Analyses of key technologies

Underwater map-matching algorithms

Underwater map-matching position is a characteristic of the vehicle’s sailing in low speed in low resolution map. The map-matching method from the point of principle can be divided into two relevant methods: recursion algorithm and batch processing algorithm. The batch processing algorithm represented with terrain contour matching (TERCOM) limits the vehicle course, leading to location results with a certain time delay. The recursion algorithm represented with Sandia inertial terrain aided navigation (SITAN) is sensitive to initial error, and is liable to lead to mismatch in the large area of gradient parameter (filter divergence). However, the algorithm has the merits of real-time position estimation and providing positioning error estimation, etc. According to the characteristics of underwater navigation, the recursion algorithm is a fairly effective and reasonable matching method [4].

Map feature analysis and judgment of navigation technology

Assessing the result of map-matching is the key step to prevent false positioning. Map feather analysis includes correlation measure analysis, roughness measure analysis, gradient feather analysis, fractal dimension analysis, feature entropy analysis, etc., all of which are based on space information features extracted from 2D spatial data. However, in the navigation, the feature and the time correlation cannot be reflected. More than that, the influence of real-time data acquisition accuracy on matching performance lacks reasonable evaluation. Quantitative evaluation for navigation performance of map matching is the basis of enhancing the navigation reliability and reducing navigation matching computation measure [5].

Multi-resolution-map-matching cooperation technologies

Multi-resolution-map-matching cooperation matching position is the key and one of the difficulties. Table 1 makes a comparison among three kinds of map matching aided inertial navigation systems. In different regions, different geophysical parameters show different reference map resolutions and result in inconsistent location observing update frequency. Therefore, cooperation location needs to solve the synchronization problems of each matching subsystem. Making full use of isoline intersection information of the reference map to get multi-map-matching position output, the matching position accuracy can be enhanced.

Experiment and simulation

In order to verify the feasibility of the system, we simulate an underwater vehicle uniform voyage in a straight line in north latitude 16°-18°, east longitude 123°-125°, regardless of ocean currents, temperature, salinity and other similar factors, and assume the velocity of voyage at 12 nmile/h [6]. Resolution of gravity map with earth gravitational model 96 (EGM 96) is 0.2′×0.2′; resolution of terrain map is 0.3′×0.3′, resolution of magnetic map is 0.2′×0.2′. Gravity, topography, and geomagnetism all adopt the iterative closest contour point (ICCP) algorithm, which is widely used in map-matching iteration.

The basic steps of the algorithm are as follows:

1) Using the sensor gathering data in each measuring point in the corresponding map, extract corresponding isoline set C={c_i, i=1, 2,…,N}.

2) Consider each measuring point as the initial iteration value, denote each measuring point as p_i, and the set of measuring points as P=[p₁, p₂,…, p_N].

3) Search its closest point y_i (Y=[y₁, y₂,…,y_N]) in the corresponding isoline, then calculate transform T which makes the relevant extremum function minimum.

Consider objective function as

(1)d={\displaystyle \frac{\mathrm{1}}{N}}{\displaystyle \sum _{i=\mathrm{1}}^N{\omega }_i}\Vert y_i-T{p}_i\Vert ,

where ω_i is weight factor.

4) Transform set P_k with T, i.e., P_{k+\mathrm{1}}=T{P}_k.

5) Judge termination conditions, if it is satisfied, end iteration, if not, go to 3) [7,8].

Dempster-Shafer (D-S) evidence theory is applied to achieve data fusion of time and space of navigation data.

For given basic probability function m and any A∈2^Ω, where Ω is the universal set, the trust function is as follows:

(2)\mathrm{B}\mathrm{e}\mathrm{l}(A)={\displaystyle \sum _{B\subseteq A}m(B)},

and plausibility function is

(3)\mathrm{P}\mathrm{l}(A)=\mathrm{1}-\mathrm{B}\mathrm{e}\mathrm{l}(\overline{A})={\displaystyle \sum _{B\cap A\ne \varnothing }m(B)},

where Bel is called the threshold function, which is the total trust degree for proposition A; Pl is called the ceiling function, which signifies the trust degree that does not negative A. Pl is the sum of basic probability assignment function (BPAF) that collects all intersects with A. When there is evidence, reject A, Pl(A)=0; and when there is no evidence, reject A, Pl(A)=1. Trust degree and plausibility degree sum up the relationship that is evident to specific proposition A, and the relationship is shown in Fig. 3.

For D-S evidence theory data fusion, there are three reasoning systems in this paper. The basic probability assignment trust function respectively assumes m₁, m₂, m₃ and Bel₁, Bel₂, Bel₃. The subset is A. The D-S rule of the probability assignment system synthesis is shown as below:

(4)m_{\mathrm{12}}(A)={\displaystyle \frac{{\displaystyle \sum _{A_{\mathrm{1}}\cap A_{\mathrm{2}}=A}{m}_{\mathrm{1}}(A_{\mathrm{1}})m_{\mathrm{2}}(A_{\mathrm{2}})}}{{\displaystyle \sum _{A_{\mathrm{1}}\cap A_{\mathrm{2}}\ne \varnothing }{m}_{\mathrm{1}}(A_{\mathrm{1}})m_{\mathrm{2}}(A_{\mathrm{2}})}}}=m_{\mathrm{1}}(A_{\mathrm{1}})\oplus m_{\mathrm{2}}(A_{\mathrm{2}}),

where

(5){\displaystyle \sum _{A_{\mathrm{1}}\cap A_{\mathrm{2}}\ne \varnothing }{m}_{\mathrm{1}}(A_{\mathrm{1}})m_{\mathrm{2}}(A_{\mathrm{2}})}=\mathrm{1}-{\displaystyle \sum _{A_{\mathrm{1}}\cap A_{\mathrm{2}}=\varnothing }{m}_{\mathrm{1}}(A_{\mathrm{1}})m_{\mathrm{2}}(A_{\mathrm{2}})}=\mathrm{1}-q.

In order to avoid assigning non-zero probability to the normalization factor (correction factor) of the empty set when combining evidence, 1–q is used to assign the abandoned reliability allocation of empty set to non-empty set according to the proportion [9].

The D-S evidence theory provides a combination of two evidence rules. Use Eq. (4) to assemble m₁₂ and m₃.

For each fusion cycle, the time and space information fusion process with D-S evidence theory is shown in Fig. 4 [10].

Figure 5 shows the local enlarged drawing of the simulation track. Figures 6 and 7 show the latitude and longitude errors, respectively.

Conclusion

It can be seen from the simulation results that errors of inertial navigation increase with time increasing, the fusion of multi-map-matching is superior to that of single-map-matching. Furthermore, the fusion track is in close proximity to real track, which proves the feasibility of the system illustrated in this paper.

References

[1] Tong Z, Bian S F. Study on the algorithm of sea bottom terrain match. In: Proceedings of the 2009 Second International Conference on Information and Computing Science. 2009, 1: 179-182

[2] Hartman R, Hawkinson W, Sweeney K. Tactical underwater navigation system (TUNS). In: Proceedings of 2008 IEEE/ION Position, Location and Navigation Symposium. 2008, 898-911

[3] Hegrenaes O, Berglund E, Hallingstad O. Model-aided inertial navigation for underwater vehicles. In: Proceedings of IEEE International Conference on Robotics and Automation. 2008, 1069-1076

[4] Feng H, Deng Z L. The study on low speed vehicle localization on reference map. Journal of Beijing University of Posts and Telecommunications, 2005, 28(3): 52-54 (in Chinese)

[5] Feng H, Yan L, Zhang F Z, Liu G J, Deng Z L. Data map characteristic analysis based on aided inertial navigation. Journal of Beijing University of Posts and Telecommunications, 2004, 27(4): 23-27 (in Chinese)

[6] Cordón O, Damas S. Image registration with iterated local search. Journal of Heuristics, 2006, 12(1-2): 73-94

[7] Wang Z G, Bian S F. ICCP algorithm for gravity aided inertial navigation. Acta Geodaetica et Cartographica Sinica, 2008, 37(2): 147-151, 157 (in Chinese)

[8] Zhang J H, Yan L, Sun X F, Deng W. ICCP matching algorithm simulation experiment research in aided navigation. GNSS World of China, 2006, 31(2): 5-9 (in Chinese)

[9] Hu L M, Gao J, He K F, Xie Z. Image fusion using D-S evidence theory and ANOVA method. In: Proceedings of the 2005 IEEE International Conference on Information Acquisition. 2005, 427-431

[10] Li R, Li B C, Li D. The temporal-spatial fusion based on the improved Dempster-Shafter technique. Computer Engineering and Applications, 2005, 41(13): 174-176 (in Chinese)

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg