Sage Journals: Discover world-class research

Abstract

This article presents a comparison of different path-planning algorithms for autonomous underwater vehicles using terrain-aided navigation. Four different path-planning methods are discussed: the genetic algorithm, the A* algorithm, the rapidly exploring random tree* algorithm, and the ant colony algorithm. The goal of this article is to compare the four methods to determine how to obtain better positioning accuracy when using terrain-aided navigation as a means of navigation. Each algorithm combines terrain complexity to comprehensively consider the motion characteristics of the autonomous underwater vehicles, giving reachable path between the start and end points. Terrain-aided navigation overcomes the challenges of underwater domain, such as visual distortion and radio frequency signal attenuation, which make landmark-based localization infeasible. The path-planning algorithms improve the terrain-aided navigation positioning accuracy by considering terrain complexity. To evaluate the four algorithms, we designed simulation experiments that use real-word seabed bathymetry data. The results of autonomous underwater vehicle navigation by terrain-aided navigation in these four cases are obtained and analyzed.

Keywords

Autonomous underwater vehicle terrain-aided navigation (TAN)path-planning genetic algorithm (GA)

Introduction

In recent decades, autonomous underwater vehicle (AUV) and its related technologies have developed rapidly, and AUV has become an important tool for human exploration of the deep sea.^1,2 However, accurate underwater positioning and navigation methods still restrict the long-range underwater operations for AUVs. Global positioning system, inertial navigation system (INS),^3,4 ultrashort baseline (USBL),⁵ long baseline (LBL)⁶ acoustic positioning systems, and geophysical navigation, such as terrain-aided navigation (TAN)⁷ and geomagnetic matching navigation, all provide options for improving navigational accuracy, with various levels of attainable precision. INS has high navigation accuracy with expensive auxiliary equipment such as attitude heading reference systems and Doppler velocity logs (DVL), nevertheless, INS navigation error is related to the total distance traveled, which means it could not suit for long-time underwater navigation without other precise auxiliary positioning means. Although USBL and LBL could provide bounded navigation error, offshore service vessels or acoustic array which would limit AUV operating radius is necessary. As a result, geophysical navigation, especially TAN, has been one feasible method for AUV underwater navigation due to its bounded error and no requirement of auxiliary equipment.

TAN basically provides a positional fix by correlating terrain surface obtained by multi-beam sonar with a stored topographical map, taking the location of the best match to be the position of the navigator.⁸

Path planning is one of the core technical issues in the field of AUV research. The goal is to find an optimal path from the start point to the end point according to a preset evaluation function under different environmental conditions. For TAN, its location is accurately related to terrain complexity,⁹ the path-planning algorithm needs to consider both terrain complexity and motion characteristics of the AUVs.

The main contributions of this article are the following:

provide path-planning algorithms to give a feasible path between the start and end points which is suitable for TAN,

propose using ant colony algorithm for AUV’s TAN path planning, and

evaluate the performance of four path-planning algorithms by simulation experiments.

Problem formulation

TAN problem

The terrain matching positioning module establishes the association between two sets of topographical measurement data by calculating the similarity between the real-time measured terrain (RTM) and the digital elevation map (DEM). The measure of the degree of similarity is usually expressed by a distance function, which is also called the belief function which is represented via terrain standard deviation.

belief = \frac{1}{T S D}

T S D = \sqrt{\frac{1}{M N} \sum_{i = 1}^{M} \sum_{i = 1}^{N} (h (i, j) - h_{s} (i, j))}

where M, N is the size of a matching unit, $H (i, j)$ is the depth in a priori map, $H_{s} (i, j)$ is the depth by real-time measurement of AUV.

As is shown in Figure 1, the TAN can be divided into two phases, the tracking phase and the matching phase, and the two phases switch to each other. To reduce the use of AUV energy, multi-beam sonar only works during the tracking phase, and RTM can be provided for the TAN algorithm.

Figure 1.

AUV operation process with TAN. AUV: autonomous underwater vehicle; TAN: terrain-aided navigation.

TAN filtering is mainly to continuously update the position through iterative estimation, which is completed in the tracking phase of TAN. Whenever a new match result is obtained, we use a particle filter (PF) to fuse the navigation information to get the real-time position of the AUV. The PF design and parameter selection are referred from Teng et al.¹⁰

Path-Planning methods for AUV based on TAN

Traditional path-planning issues need to consider energy consumption, AUV motion constraints, avoiding obstacles, and so on. Since the accuracy of TAN positioning is related to the complexity of the terrain, the terrain information around the path becomes the biggest factor to consider at this time.⁹

We introduce the amount of Fisher information to measure complexity of the terrain. Define the amount of terrain Fisher information in a local area as follows¹¹

T F I C = \sqrt{\frac{1}{M N} \sum_{i = 1}^{M} \sum_{j = 1}^{N} ‖ \frac{\partial h (x_{i, j})}{\partial x_{i, j}} \frac{\partial h (x_{i, j})}{\partial x_{i, j}^{T}} ‖}

where M, N is the size of the area, h is the depth of seabed.

A good path-planning result should have the following characteristics:

Start at the specified starting point and end at the specified end point.

Consider AUV motion characteristics.

Consider terrain information.

Methodology

The genetic algorithm

The path planning based on genetic algorithm can be simply summarized into three steps: coding, genetic manipulation and decoding,¹² which is outlined in Figure 2.

Figure 2.

GA path-planning flow chart. GA: genetic algorithm.

The genetic operation is divided into steps of selection, crossover, and variation.¹³ The selection operator used in this study is roulette method. The idea of roulette method is the probability of being selected according to the value of the fitness. Figure 3 is the flow chart of roulette method, which makes sure that gene with a higher value of the fitness has a higher probability to be selected.¹⁴

Figure 3.

Roulette method flow chart.

The key of GA solving path-planning problem is the design of fitness function. In this research, fitness is defended by equation (4)

\begin{matrix} f i t n e s s = U_{a} \cdot F (l e n g t h) + U_{b} \cdot F (s m o o t h n e s s) \\ + U_{c} \cdot sec u r i t y + U_{d} \cdot F (T F I C) \end{matrix}

where $U_{a}$ , $U_{b}$ , $U_{c}$ , $U_{d}$ is the proportion of each item, length is the total length of the path, and smoothness is the smoothness of the path, defined by equation (5)

s m o o t h n e s s = \sum_{i = 1}^{n - 1} θ_{i}

where $θ_{i}$ is the heading variety of sub-path number i and

security is defined by equations (6) and (7)

s e c u r i t y = \sum_{i = 1}^{n} b_{i}

b_{i} = {\begin{array}{l} punish & r_{i} < r_{AUV} \\ 0 & r_{i} \geq r_{AUV} \end{array}

where r_i is the minimum bead of curvature radius of sub-path number i, r _AUV is the radius of gyration of AUV, punish is the punish value, take −30 in this article.

TFIC is the Fisher information value of the terrain.

The A* algorithm

The A* algorithm is a one-way heuristic searching algorithm, which in essence brings the related knowledge involved in the problem to be solved directly into the algorithm to improve the computational efficiency.¹⁵ The A* algorithm uses a step-by-step searching method, which means in each step the estimate function will be used for the new state to generate an estimate. And every next action is determined based on the value of the estimate.¹⁶ The A* algorithm has the following features:

Adoptability: If there is a feasible path from the start S to the end point T, the algorithm has the ability to always find the relative optimal path from S to T. A* has the adoptability because of its heuristic function $h (n) < h^{*} (n)$ , where h(n) is the estimate of minimum cost from S to T, and $h^{*} (n)$ is the cost of the optimal path from S to T.

Optimality: In the operation of the A* algorithm, all nodes meet the demand of the monotonic principle, and all paths to the next point selected by the A* algorithm are the optimal paths.

The algorithm used in this article is as follows:

Construct the environment field field, set up start point S and goal point T, compute $f^{*} (n)$ . ( $f (n)$ is the estimation of $f^{*} (n)$ , $f^{*} (n) = h^{*} (n) + g^{*} (n)$ , $g^{*} (n)$ is the minimum cost from S to point n, $h^{*} (n)$ is the minimum cost from piont n to T.)

Put the start point S into Open Table, set open cost to 0, set open heuristics function to infinity, empty the Close Table.

Choose the node with minimum value of f in the Open Table, move it into Close Table. If the node is the end point T, end the algorithm, otherwise continue to 4.

Calculate each node’s cost function and heuristics function. If this node is in Open Table, put it into step 3. Take the node with the minimum cost function in the Open Table as the next point and move it to the Close Table.

Push back from the end point to the starting point, put the corresponding coordinates into the matrix, and draw the path line.

The RRT* algorithm

Rapidly exploring random tree (RRT) was proposed in the study by LaValle.¹⁷ It obtains the optimal path by building an incremental tree, and the new node was generated by moving at a certain velocity toward a random sampling point. Rapidly exploring random tree* (RRT*) was developed based on the RRT algorithm.¹⁸ For a new node in RRT*, its parent is the node which could minimize its cost, instead of its nearest node. This helps RRT* realize the approximation of the optimal path. The advantage of RRT* is its ability to search for the approximate optimal path in high-dimensional space.¹⁹

RRT* mainly includes the following functions

z_{r a n d} = S a m p l e ()

Make random sampling in (space), and $z_{r a n d}$ is the coordinate of the random sampling point.

z_{n e a r e s t} = N e a r e s t (T, z_{r a n d})

in which $z_{n e a r e s t}$ is the coordinate of the node nearest to $z_{r a n d}$ on the tree T according to the Euclidean distance.

O b s t a c l e (z_{n e a r e s t}, z_{n e w})

which is for making sure if there is any obstacle on the link between $z_{n e a r e s t}$ and $z_{n e w}$ . TRUE will be output if there is any, otherwise output FALSE.

z_{p a r e n t} = C h o o s e p a r e n t (T, z_{n e w}, r)

is the coordinate of the parent node which could minimize the cost of $z_{n e w}$ , and on the link between $z_{n e w}$ and $z_{p a r e n t}$ where there is no obstacle.

The algorithm procedure of RRT* is given in Algorithm 1.

Algorithm 1: RRT*
1	Initialize Tree T
2	Do
3	$z_{r a n d} = S a m p l e ()$
4	$z_{n e a r e s t} = N e a r e s t (T, z_{r a n d})$
5	$z_{n e w} = S t e e r (z_{n e a r e s t}, z_{r a n d}, u)$
6	If $O b s t a c l e (z_{n e a r e s t}, z_{n e w})$
7	$z_{p a r e n t} = C h o o s e p a r e n t (T, z_{n e w}, r)$
8	Until $z_{n e w} = z_{g o a l}$

In contrast with the traditional path planning for obstacle avoidance, path planning for TAN considers terrain information. Besides, the distance between nodes should be decided by the confidence of the current matching result instead of setting them as a fixed value. Ma Teng¹⁰ made improvements on Steer function and choose parent function in RRT* algorithm. Area of interest (AOI) is proposed for the process searching for the new node. The roulette method is used in the AOI for calculating the resultant force to decide the heading direction of the node. In this way, the resulting path takes into account the terrain information and the TAN algorithm.

The ant colony algorithm

The TAN path-planning algorithm based on ant colony algorithm flow chart is shown in Figure 4. The ant colony algorithm simulates the social form of ants, finds food, task assignment, and construction of cemetery similar to ants, and solves the problem of optimization.²⁰ Compared with the traditional ant colony algorithm, the algorithm performs path planning by changing Food and Information.

Figure 4.

Ant colony algorithm flow chart.

Food

Most path-planning methods for TAN realize the TAN effect on the path by importing the terrain information into the optimization function. But in fact, just more accumulated terrain information on the path does not always bring better effect. In other words, what we are looking for is the shortest path with higher navigation accuracy on the path, other than the path which gives optimization function the largest value with the terrain information imported. In the ant colony algorithm, we implemented this by setting the “Food”. Food does not participate in the optimization function, which means that the ant does not need as much food as possible during the process of optimizing, as long as the existing food is enough for it to reach the next matching point.

Information

In fact, when using food to select the shortest path, the algorithm tends to choose the straight line connecting the start point and the end point. That is because there is no limit on the number of matching points on the AUV path. Because it is not feasible in actual operation that set a maximum number of matching points due to the difference within maps and within the setting of start points and end points. The update formula of the pheromones is modified. The Information for each point along the path is not distributed according to the distance, but according to the number of matching points. After the (t + 1)th iteration, the improved formula of the pheromones is

τ_{i j} (t + n) = ρ τ_{i j} (t) + Δ τ_{i j} (t, t + n)

Δ τ_{i j} (t, t + n) = \sum_{k = 1}^{m} Δ τ_{i j}^{k} (t, t + n)

Δ τ_{i j}^{k} (t, t + n) = {\begin{matrix} Q / N_{k} (i, j) \in path k \\ 0 otherwise \end{matrix}

where $τ_{i j} (t + n)$ is the pheromones of $(i, j)$ in $t + 1$ , ρ is the attenuation coefficient, and Q is the strength of pheromones.

Experimental setup and results

The DEMs used in the simulation experiment are obtained from www.ibcao.org. Because the size is too large, we use scale maps of five hundredths which are shown in Figure 5(a) and (b). Figure 5(c) and (d) shows the terrain information of each scale map.

Figure 5.

Scale map and terrain information.

The two maps are used because different situations are analyzed in the experiment. The area where the map A (Figure 5(a)) is located has a high terrain information value, and the area corresponding to map B (Figure 5(b)) has a large number of flat terrain areas.

In the experiment, we simulated the operation using MAUV-II, a mini-micro AUV designed by Harbin Engineering University.²¹ The main characteristics of MAUV-II are the radius of gyration is 63 m, and the positioning error of the estimated navigation is 1.5% of the distance traveled.

To verify the quality of these paths, we proposed to carry out AUV TAN simulation experiments. In the test, we simulated an AUV equipped with multi-beam sonar to track the path. The acoustic parameters in the test are also referenced MAUV-II, sounding swath of the multi-beam sonar carried by MAUV-II was composed of 192 beams that generated a fan width of approximately 1.5 times water depth. It works at a frequency of 2 Hz in the experiment. AUV in the experiment is 1 m/s.

To be relatively fair to each algorithm, the optimization function in the experiment uses the same function as in GA (equation (4)), and the TAN algorithm uses the algorithm introduced in the previous section.

Since GA, RRT* algorithm, and ant colony algorithm are stochastic algorithms, Monte Carlo experiments were performed, and each algorithm was repeated 100 times in each map. Since the A* algorithm is not stochastic, only one experiment is performed on each of the two maps.

Figures 6, 7, and 8 show the path length, dead reckoning (DR) drift, and TAN navigation error, respectively, obtained under map A in the experiment.

Figure 6.

Experimental results—path length (map A).

Figure 7.

Experimental results— DR drift (map A).

Figure 8.

Experimental results—TAN error (map A). TAN: terrain-aided navigation.

Figures 9, 10, and 11 show the path length, DR drift, and TAN navigation error, respectively, obtained under map B in the experiment.

Figure 9.

Experimental results—path length (map B).

Figure 10.

Experimental results—DR drift (map B).

Figure 11.

Experimental results—TAN error (map B). TAN: terrain-aided navigation.

Figures 12 and 13 show the path comparisons given by the four algorithms in both cases. Since the Monte Carlo experiment was performed by three algorithms (RRT*, GA, ant colony), typical cases occurring in 100 repeated experiments were selected and presented in the figure.

Figure 12.

Experimental results—typical paths given by each algorithm (map A).

Figure 13.

Experimental results—typical paths given by each algorithm (map B).

The path given by all the algorithms in the experiment allows the AUV to obtain better positioning accuracy through the TAN, but it also benefits from the abundant seabed terrain.

In the experiment done by map A, the A* algorithm obtained relatively good experimental results, which gave the shortest path and better navigation and positioning results. The other three algorithms are comparable, and there is no big difference.

In the experiment done on map B, the A* algorithm also obtained relatively good experimental results, which gave the shortest path and better navigation and positioning results. Among the other three algorithms, GA has better performance than the other two, indicating that GA can better find a more suitable path on this map.

The reason why A* can obtain better experimental results may be that A* can obtain the optimal solution found, given the optimization function. At the same time, the other algorithms are likely to fall into the local optimal solution, thus missing the opportunity to meet the optimal solution.

In the experiment of map B, the reason why GA is better than RRT* and ant colony may be that the genetic mutation process of GA can better inspire the algorithm to find a more suitable path when the figure of terrain information is not so large.

Conclusions

With the DEM of target area, we present four path-planning algorithms (GA, A*, RRT*, and ant colony) for AUVs TAN. We evaluated four algorithms to compare the performance of TAN tracking path obtained from each algorithm by simulation experiment. The following conclusions are drawn:

All the four algorithms have the ability to present a reliable path for TAN.

A* gives a relatively good path under both maps (short distance and high navigation accuracy)

TAN is a method that can be relied upon to solve the AUV long-term underwater operation problem.

However, since the given optimization function does not necessarily have a linear relationship with the accuracy of TAN, the accuracy of navigation has great uncertainty, which is worthy of further study.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Key R&D Program of China [Grant No. 2017YFC0305700], National Natural Science Foundation of China [Nos. 51879057, 51779052], Qingdao National Laboratory for Marine Science and Technology [Grant No. QNLM2016ORP0406], and Fundamental Research Funds for the Central Universities [Grant No. HEUCFG201810], the Open Fund of Key Laboratory of High Performance Ship Technology (Wuhan University of Technology), Ministry of Education (No. gxnc19051802).

ORCID iD

Zheng Cong

Ye Li

Yanqing Jiang

References

Fong

Jones

. Evaluation of AUV-based ADCP measurements. Limnol Oceanogr-Meth 2006; 4(3): 58–67.

Forrest

Bohm

Laval

. Investigation of under-ice thermal structure: small AUV deployment in Pavilion Lake, BC, Canada. In: OCEANS 2007, Vancouver, BC, Canada, 29 September–4 October 2007. Piscataway: IEEE, 2007.

Karimi

Bozorg

Khayatian

. A comparison of DVL/INS fusion by UKF and EKF to localize an autonomous underwater vehicle. In: 2013 First RSI/ISM international conference on robotics and mechatronics (ICRoM), Tehran, Iran, 13–15 February 2013.

Melo

Matos

. Survey on advances on terrain based navigation for autonomous underwater vehicles. Ocean Eng 2017; 139: 250–264.

Morgado

Oliveira

Silvestre

. Experimental evaluation of a USBL underwater positioning system. In: ELMAR, 2010 proceedings, Zadar, Croatia, 15–17 September 2010. IEEE.

Scherbatyuk

AP.

The AUV positioning using ranges from one transponder LBL. In: Challenges of Our Changing Global Environment. Conference Proceedings. OCEANS’95. MTS/IEEE. San Diego, CA, USA, 9–12, 1995, October Vol. 3, 1995. IEEE.

Chen

. Review of AUV underwater terrain matching navigation. J Navigation 2015; 68(6): 1155–1172.

Nygren

. Terrain navigation for underwater vehicles. Diss. Stockholm: KTH, 2005.

Rupeng

Teng

. Underwater digital elevation map gridding method based on optimal partition of suitable matching area. Int J Adv Robot Syst 2019; 16(2).

10.

Teng

Yanqing

. A dynamic path planning method for terrain-aided navigation of autonomous underwater vehicles. Meas Sci Technol 2018; 29(9): 095105.

11.

Efron

Hinkley

. Assessing the accuracy of the maximum likelihood estimator: observed versus expected Fisher information. Biometrika 1978; 65(3): 457–483.

12.

Peng

Jin

Wang

. Multimodal optimization enhanced cooperative coevolution for large-scale optimization. IEEE Trans Cybern 2018; 99: 1–14.

13.

Xingguang

. Large-scale cooperative co-evolution using niching based multi-modal optimization and adaptive fast clustering. Swarm Evol Comput 2017; 35: 65–77.

14.

Roberge

Tarbouchi

Labonté

. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Trans Ind Inf 2013; 9(1): 132–141.

15.

Bodhale

Afzulpurkar

Thanh

. Path planning for a mobile robot in a dynamic environment. In: 2008 IEEE international conference on robotics and biomimetics, Bangkok, Thailand, 22–25 February 2009. IEEE.

16.

Chen

. Autonomous underwater vehicle optimal path planning method for seabed terrain matching navigation. Ocean Eng 2017; 133: 107–115.

17.

LaValle

. Rapidly-exploring random trees: a new tool for path planning. 1998.

18.

Islam

Nasir

Malik

. RRT*-smart: rapid convergence implementation of RRT* towards optimal solution. In: International conference on mechatronics and automation, Chengdu, China, 5–8 August 2012. IEEE.

19.

Melchior

Simmons

. Particle RRT for path planning with uncertainty. In: 2007 IEEE international conference on robotics and automation, 2007. IEEE.

20.

Dorigo

Birattari

Blum

(eds). Ant colony optimization and swarm intelligence. In: Proceedings sixth international conference, ANTS 2008, Vol. 5217, Brussels, Belgium, 22–24 September 2008. Springer.

21.

Fei

Shuo

. Comparison of two six-degree of freedom simulation models for mini autonomous underwater vehicle. In: ASME 2012 31st international conference on ocean, offshore and arctic engineering, 2012. American Society of Mechanical Engineers.

An evaluation of path-planning methods for autonomous underwater vehicle based on terrain-aided navigation