# Research Progress of Path Planning Methods for Autonomous Underwater Vehicle

Authors: Yinjing Guo; Hui Liu; Xiaojing Fan; Wenhong Lyu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Path planning is a key technology for autonomous underwater vehicle (AUV) navigation. With the emphasis and research on AUV, AUV path planning technology is continuously developing. Path planning techniques generally include environment modelling methods and path planning algorithms. Based on a brief description of the environment modelling methods, this paper focuses on the path planning algorithms commonly used by AUV. According to the basic principles of the algorithm, the AUV path planning algorithms are divided into four categories: artificial potential field methods, geometric model search methods, random sampling methods, and intelligent bionic methods. In this review, we summarize in detail the development and application of various path planning algorithms in recent years. Meanwhile, we analyse the advantages and disadvantages of various algorithms and their improvement methods. Obstacles, ocean currents, and undersea terrain have an impact on AUV path planning. Therefore, how to deal with the complex underwater environment adds some limits to AUV path planning algorithms. In addition to the external environment, path planning algorithms also need to consider AUV’s physical constraints, such as energy constraints and motion constraints. Then, we analyse the motion constraints in AUV path planning. Finally, we discuss the development direction of AUV path planning algorithm. Time-varying ocean currents, special obstacles, multiobjective constraints, and practicability will be the problems that AUV path planning algorithms need to solve.


---

## Body

## 1. Introduction

In the 21st century, human attention has shifted from land to ocean. There are abundant ocean resources, and many countries have adopted ocean development as their national development strategy. As an important tool for exploring the ocean, an autonomous underwater vehicle (AUV) can perform specific underwater tasks such as monitoring, operation, search, and rescue [1–3], and it plays an important role in the civilian and military fields [4]. Compared with land robot and aerial robot, AUV works underwater at different depths and faces more complicated underwater environments. Path planning exists in the entire navigation process of AUV and is the key to AUV’s underwater operation. The safe and efficient navigation of AUV cannot be separated from path planning. The influence of the underwater environment must be considered in AUV path planning, such as obstacles, ocean currents, and terrain. Moreover, the planned path also needs to meet the motion constraints of AUV [5]. Many experts and scholars have done much research and achieved fruitful results on AUV path planning.AUV path planning refers to planning a safe and feasible path from the initial state (position, attitude) to the target state (position, attitude) under certain evaluation criteria (such as optimal path length, shortest sailing time, and minimum energy consumption). According to the scope of path planning, AUV path planning can be divided into global path planning and local path planning. It is the most commonly used classification of path planning. Global path planning obtains all environmental information of the AUV during the entire navigation process in advance to find the globally optimal path. Local path planning relies on a variety of sensors carried by the AUV to collect real-time environmental information (such as the distribution of obstacles) to plan a locally optimal path for obstacle-free navigation.The general path planning steps include environment modelling, underwater positioning, and path planning, as shown in Figure1. It is usually necessary to establish an environmental model of the planned area for AUV when solving practical problems. Environment modelling can map the AUV’s physical environment (underwater working space) into an environmental model that can be processed by a computer. Underwater positioning can obtain the position of AUV, which is the premise of AUV path planning. Different from the traditional GPS positioning, underwater positioning is more difficult. The radio waves decay quickly in water, so acoustic equipment can be used to obtain the AUV’s position. Path planning refers to using a path planning algorithm to generate a feasible path of AUV based on the environment model, and it is the core of path planning. The environment modelling method should be selected flexibly according to the environment and actual requirements to improve the efficiency of the path planning.Figure 1
General steps and methods of AUV path planning.In AUV path planning, the commonly used underwater environment modelling methods are grid method [6, 7], cell tree method [8, 9], Voronoi diagram method [10, 11], visibility graph method [1, 12], etc. The grid method and the cell tree method use regular graphics (such as squares) to describe the underwater environment information. The modelling is simple, and the calculation amount is small. However, the surrounding environment information cannot be accurately reflected. They are suitable for simple, low-precision underwater environment modelling. Each cell is the same, so the size of the cell will directly affect the performance of the planning algorithm [13]. The Voronoi diagram method and the visibility graph method use irregular graphics (such as polygons) to describe the underwater environment information, and they are more complicated in the calculation. They can better reflect the surrounding environment information and are suitable for the modelling of the complex and high-precision underwater environment. Suitable environment modelling methods can reduce storage and improve the efficiency of path planning. However, due to the complexity and particularity of the underwater environment and the limitations of sensors, it is challenging to establish an accurate underwater model. The dynamically changing underwater environment also increases the difficulty of modelling. Therefore, many previous studies ignored the depth of the underwater environment and established two-dimensional (2D) models. The 2D underwater model is simple, but it cannot entirely reflect the actual underwater environment. Although it increases the modelling difficulty and computational complexity, three-dimensional (3D) underwater modelling will gradually replace 2D modelling as the mainstream with the improvement of computing power and the need for a complete underwater environment. In practical applications, appropriate 2D/3D models should be established according to the specific underwater environments and the requirements of path planning algorithms [14].There are many methods for the AUV path planning. According to the basic principles of the algorithm, the path planning algorithms are divided into four categories, including artificial potential field methods, geometric model search methods, random sampling methods, and intelligent bionic methods. Different path planning algorithms have differences in real-time performance, planning speed, or the path’s length and smoothness. As the kinematic and dynamic constraints of AUV in 3D space become very complicated, some 2D path planning algorithms are difficult to extend to 3D space [15]. Path planning methods have their advantages, disadvantages, and application scope. The path planning algorithm should be reasonably selected according to the actual requirements (such as planning accuracy and working environment) and the advantages and disadvantages of the algorithm to achieve better effects for AUV path planning.The rest of the paper is organized as follows. In Section2, we introduce the path planning algorithms for AUV in detail. In Section 3, we analyse the motion constraints in AUV path planning. The development directions of AUV path planning algorithms are given in Section 4. Finally, the conclusion is made in Section 5.


## 2. Path Planning Algorithms for AUV

AUV path planning algorithm originated from the path planning algorithm of wheeled mobile robots (WMRs). The two have some similarities, but they are also quite different. From the aspect of the application environment of the algorithm, the AUV path planning algorithm is applied to the underwater environment, while the WRM path planning algorithm is applied to the terrestrial environment. There are great differences between the underwater environment and the terrestrial environment, and the underwater environment has uncertain and dynamic characteristics. Random and complex obstacles, ocean currents, and terrain will have a certain impact on AUV path planning. From the aspect of the application object of the algorithm, AUV and WRM are different in motion control, environment perception, navigation, positioning, communication, etc., such as AUV’s six degrees of freedom (DOF) motion, complex kinematic and dynamic constraints, and low underwater visibility. Moreover, the AUV path planning includes 2D plane planning and 3D space planning, while the WRM path planning is generally two-dimensional. In addition, AUV has a high underwater experiment cost. Once lost, it is difficult to recover. Therefore, it is difficult to apply the commonly used path planning algorithms of WRM to AUV, and many new path planning algorithms suitable for AUV are proposed.


### 2.1. Artificial Potential Field Methods

The artificial potential field (APF) algorithm was initially applied to the collision avoidance of the manipulator and is now widely used in the AUV path planning. Obstacles in the environment need to be considered when planning the AUV paths, and the APF algorithm can have a good obstacle avoidance effect. The basic idea of APF is to assume that the AUV is affected by a virtual artificial force field when it moves in an obstacle environment. The target point and the obstacle generate gravitational and repulsive forces on the AUV, respectively. The combined force of the two controls the movement of the AUV, as shown in Figure2.Figure 2
Force analysis of AUV in traditional APF.The APF algorithm is safe, efficient, and easy to implement. For static obstacles in an unknown environment, Solari Franco et al. proposed a potential field algorithm for obstacle avoidance using a mechanical scanning sonar. The algorithm assumes that the angular direction of each beam of the sonar is the possible direction for the AUV to select the path, then calculates the evaluation point potential at a certain distance from the AUV in each beam direction, and finally selects the lowest potential as the direction of AUV motion. The effectiveness of the algorithm was verified by simulation [16]. The APF algorithm performs well in path planning under a static environment. However, it does not consider the influence of ocean currents and dynamic obstacles, which will cause large deviations in practical applications. The underwater environment in which AUV works is different from the ground, and ocean currents will have a greater impact on AUV’s movement. Therefore, ocean currents and dynamic obstacles must be considered in AUV path planning. Cheng et al. proposed a new path planning algorithm combining artificial potential field and velocity synthesis, which better solves the path planning problem of AUV in ocean current environment with dynamic obstacles. This algorithm synthesizes the velocity of the ocean current and the AUV, and the direction of the synthetic velocity is accurately determined by the artificial potential field. Considering the influence of the relative velocity between AUV and dynamic obstacles on AUV motion, the velocity repulsive potential field determined by the relative velocity is introduced. Compared with the traditional APF, the time and path length are reduced by 15%, respectively [17].The APF algorithm also has a good obstacle avoidance effect on irregular obstacles. It is widely used in real-time obstacle avoidance and smooth path planning [18, 19], but the algorithm itself has some inherent shortcomings, such as the local minimum and goal nonreachable with obstacles nearby (GNRON). Setting a virtual obstacle near the local minimum can effectively solve the local minimum problem. The virtual obstacle will change the potential field around the AUV, thereby getting rid of the existing local minimum [16]. Fan et al. made three improvements to the traditional APF. The first is to add a distance correction factor into the repulsive potential field function to solve the GNRON problem; the second is to propose the regular hexagon-guided method to solve the local minima problem; the third is to introduce the relative velocity method to avoid the dynamic obstacles in time. The improved APF can find a collision-free optimal path in both static and dynamic environments [20].The APF algorithm can also be used for multi-AUV path planning. Based on the 3DOF kinematic and dynamic modelling of AUV under wave disturbances, Das et al. combined the APF, ant colony optimization, and clonal selection to solve the obstacle avoidance control of multi-AUV in an obstacle-rich environment. The combined algorithm overcomes the shortcomings that traditional APF is easy to fall into the local minimum and cannot find the path if there are many similar obstacles. The effectiveness of the algorithm for path planning under wave disturbances is verified in [21]. To improve the obstacle avoidance ability of AUV in the 2D environment, Liang et al. established 3DOF kinematic and dynamic models of AUV by ignoring the pitch, roll, and heave motion and then improved the repulsive force field based on the traditional APF. The modified repulsive force field is annular so that AUV can smoothly bypass obstacles at a safe distance. It also ensures the safety of multi-AUV path planning [22]. Some APF algorithms introduce the motion characteristics of AUV in the design, which will greatly increase the practicability of the algorithm.


### 2.2. Geometric Model Search Methods

The geometric model search methods are traditional and classical path planning methods. This method has been widely used in path planning because of its mature technology and simple implementation process. In this type of method, the establishment of the model is very strict, which directly affects the final planned path. Common geometric model search methods are Dijkstra,A∗, D∗, D∗ Lite, level set method (LSM), etc. The relationship between them is summarized in Figure 3, and Table 1 shows a simple comparison between them.Figure 3
The relationship between geometric model search methods.Table 1
Geometric model search methods.
MethodAdvantageDisadvantageApplicationDijkstra(1) Easy to implement(1) Low search efficiency(1) 2D environment(2) High success rate(2) Large storage space(2) Simple environment(3) Good stability and robustness(3) Global shortest path planning(4) Gets the optimal solution for the shortest pathA∗(1) Low calculation cost(1) Generated path is not smooth(1) 2D/3D environment(2) Short search time(2) High complexity in the multidimensional environment(2) Static/dynamic environment(3) High search efficiency(3) Global shortest path planningD∗Lite(1) Simple and stable(1) Less application(1) 2D/3D environment(2) High efficiency(2) Slow search speed in large environment(2) Simple/unknown environment(3) Effective obstacle avoidance(3) Local path planning(4) Dynamic searchLSM(1) Effectively simulates the dynamic process(1) Slow processing speed(1) 2D environment(2) Suitable for combining with ocean current(2) Long computation time(2) Dynamic ocean current environment(3) Global path planning


#### 2.2.1. Dijkstra Algorithm

Dijkstra algorithm is a typical global shortest path planning algorithm [23, 24]. It starts from the starting point and uses the strategy of the greedy algorithm to traverse the adjacent nodes which are closest to the starting point and not visited. When it reaches the endpoint, it can find the shortest path from the starting point to the endpoint. Dijkstra algorithm is mainly used to solve the single-source shortest path problem in weighted directed or undirected graphs.Eichhorn applied the Dijkstra algorithm to a time-varying environment by adding time information in the weighted directed graph as an additional dimension. The algorithm searched for the path with the minimum sailing time as the optimization goal and achieved good results in both fixed and time-varying ocean currents [25]. In addition to ocean currents, obstacle avoidance is also a factor to be considered when searching for a path. Kirsanov et al. added an addition part (AP) to the traditional Dijkstra algorithm, which is mainly responsible for static and dynamic obstacle avoidance. AP uses the critical radius of collision between AUV and the dynamic obstacles to avoid dynamic obstacles. The modified algorithm also takes the dynamic characteristics of the ocean current into account to optimize the path. The numerical results show that the algorithm is effective in 2D path optimization [26]. Grefstad and Schjolberg used the Dijkstra algorithm for path planning on the basis of using sonar to detect obstacles and IKMs Merlin UCV and Statoils Snorre B oil field are used in reference [27]. The test results show that the algorithm can generate a new obstacle-free path, and the method is also applicable to AUV [27]. Dijkstra algorithm is easy to implement and has good stability and robustness. It can obtain the optimal solution of the shortest path by traversing all nodes and is suitable for path planning in simple environments. Although the path planning has a high success rate, the algorithm will occupy a large amount of storage space, and the search efficiency will become low when applied to large-scale and complex environments. The relaxed Dijkstra algorithm proposed by Ammar et al. solved the problem of global path planning in a large-scale grid environment, and the time to find the optimal solution is three times faster than the traditional Dijkstra algorithm [24].


#### 2.2.2.A∗ and D∗ Lite Algorithms

A∗ algorithm is the most effective direct search algorithm for solving the shortest path in static road networks and is widely used to solve low-dimensional path planning problems. Compared with the Dijkstra algorithm, this algorithm uses heuristic information to guide the optimal path generation, which can reduce the calculation cost and improve the efficiency of path planning. The core idea of the A∗ algorithm is still an iterative process. A∗ algorithm evaluates the path cost through the function fn=gn+hn, where n is the position of AUV; fn is the path cost from the starting point to the target point; gn is the actual path cost from the starting point to the current position of the AUV; and hn is the estimated cost of the best path from the current position to the target point. Moreover, hn is the heuristic embodiment of the A∗ algorithm [28].The traditionalA∗ algorithm generates the optimal path by minimizing the path cost. However, it does not consider path length, obstacle collision risk, manoeuvrability restriction, and ocean currents in path planning [29]. Lefebvre et al. used path length and collision risk as optimization criteria to find the minimum risk path of AUV and proposed a hierarchical A∗ (HA∗) algorithm based on the hierarchical technique. HA∗ associates the collision risk represented by probability with path planning and solves the path planning problem in stages through an abstract graph. Dijkstra, A∗, hierarchical Dijkstra (HD), and HA∗ are used to plan the minimum length path and the minimum collision risk path of AUV, as shown in Figure 4. Compared with the traditional A∗ algorithm, HA∗ greatly improves the efficiency of path planning, although the path obtained by HA∗ is not optimal in length. The calculation time of the minimum length path and the minimum collision risk path is reduced by 71% and 86%, respectively [30].Figure 4
(a) Minimal length paths. (b) Minimal collision risk paths [30].
(a)(b)A∗ algorithm has a short planning time and a small amount of calculation. It is a global search algorithm commonly used in the AUV path planning. However, the A∗ algorithm will generate some unnecessary inflection points in the search process [31]. Moreover, the resulting final path is a multisegment path composed of many continuous straight lines, which is difficult to meet the requirements of AUV dynamic and kinematic constraints. Wang et al. combined the A∗ algorithm with a uniform cubic B-spline curve to generate a smooth path satisfying AUV motion constraints. The B-spline curve has independent control points that are easy to adjust, and it is more convenient and flexible to use the B-spline curve to fit the waypoints of a path generated by the A∗ algorithm. The simulation results show that this method can effectively smooth the path and shorten the path length and calculation time [32]. To minimize the energy consumption of AUV in an unknown ocean current environment, Li et al. improved the A∗ algorithm by using travel time as a heuristic cost function. In the simulation, the 6DOF nonlinear dynamic model of REMUS AUV was used, and the rudder turn angle of AUV was limited to less than 30 degrees considering the turn radius constraint. The algorithm’s effectiveness was verified under the condition that both the current velocity and AUV velocity are constant [1].TheD∗ algorithm, also known as dynamic A∗, is a dynamic shortest path algorithm. The D∗ algorithm can search the path in an unknown environment, but its efficiency is low. D∗ Lite algorithm is an improved version of the D∗ algorithm, which combines the advantages of the D∗ algorithm and the LPA∗ algorithm. Unlike the forward search used by LPA∗, D∗ Lite uses the reverse search (the target point is fixed and the starting point changes with time) [33], which makes the path planning easier and faster. Due to the dynamic characteristics of the underwater environment and the uncertainty and incompleteness of environmental information, it is necessary to replan the path in time when the AUV encounters unknown static or dynamic obstacles. D∗ Lite algorithm can effectively solve this problem. Sun et al. applied the D∗ Lite algorithm to the Maritime I AUV for 3D path planning in a partly unknown environment. Based on the description of the AUV structure, they used a grid map to rasterize the 3D underwater space. The simulation results under different obstacle environments prove that the algorithm is effective for both 2D and 3D underwater environments. In Figure 5, AUV can quickly replan the path when encountering unexpected obstacles (red cube) [34]. D∗ Lite algorithm is suitable for the AUV path planning in an unknown environment. However, few people have applied it to AUV path planning in recent years. Large environments will increase the time complexity of the algorithm search. Besides, the algorithm cannot cope with the fine planning of the local environment.Figure 5
An example of usingD∗ Lite to generate the final path [34]. (a) No unexpected obstacles. (b) Unexpected obstacles.
(a)(b)


#### 2.2.3. Level Set Method

LSM was proposed by Osher and Sethian. LSM can naturally integrate the ocean model into the level set equations and effectively simulate dynamic processes, so it has attracted widespread attention in the AUV path planning considering the influence of ocean currents [35]. In 2017, Subramani et al. used the level set equation to plan a time-optimal path for the REMUS 600 AUV in a strong and dynamic ocean current environment and considered operational constraints (such as minimum depth). The test results in Buzzards Bay and Vineyard Sound regions showed that AUV reaches the target point along the time-optimal path 6–15% faster than the shortest path, although the local currents and geometric constraints are complex [36]. Since then, Subramani et al. have conducted further research on the application of the LSM method to path planning in the ocean current environment. Due to the uncertainty in the path planning, the stochastic dynamically orthogonal level set equation is applied to control the AUV to travel in an uncertain, strong, and dynamic ocean current environment, and the stochastic time-optimal path planning is carried out in [37]. Based on [37], Subramani and Lermusiaux combined the risk optimality criterion based on decision theory with the stochastic dynamically orthogonal level set equations to search for the risk-optimal path in a random dynamic environment, and it minimizes the suboptimal risk of the stochastic time-optimal path predictions [38]. The LSM method achieved good results in path planning under different ocean current environments, such as stochastic front, double-gyre QG flow, flow past an island, and flow exiting a strait [37, 38]. The LSM can solve more complicated problems, but it takes longer calculation time [39].


### 2.3. Random Sampling Methods

Random sampling methods, such as the rapidly exploring random tree (RRT) method and the probabilistic roadmap (PRM) method, perform well in the AUV path planning. This type of method uses random sampling to make probabilistic detection of the AUV underwater working environment to search the path [40], but this probability or randomness brings some challenges to the AUV path planning.


#### 2.3.1. Rapidly Exploring Random Tree

RRT takes the initial point as the root node and generates a random extended tree by adding leaf nodes through random sampling (Figure6). When the leaf nodes in the random tree include the target point, a path from the initial point to the target point can be found in the random tree. RRT has a powerful spatial search capability and can effectively solve path planning in high-dimensional space and complex constraints. However, there are some problems such as the path is not optimal and the algorithm is easy to fall into a minimum.Figure 6
Basic RRT build process [41]. Xinit is an initial point, Xrand is a random sampling point, Xnearest is the nearest point to Xrand, and Xnew is a new point.With the development of the RRT algorithm, many variant algorithms have appeared. TheRRT∗ algorithm can converge to the optimal solution. Unlike RRT, which searches for the nearest neighbouring nodes in the roadmap, RRT∗ checks the connections with all neighbouring nodes within a specific radius. It can search for a path in the 2D or 3D environment. Hernández et al. improved the RRT∗ algorithm by using the concepts of anytime algorithm and lazy collision evaluation. The improved algorithm enables AUV to replan the path according to nearby obstacles perceived during navigation. The underwater experiments of the SPARUS-II AUV verified the effectiveness of the algorithm in planning obstacle-free paths in unknown underwater environments [8]. Aiming at the path planning problem of multi-AUV systems, Cui et al. proposed a multidimensional RRT∗ algorithm (MDMI-RRT∗) based on mutual information. Unlike traditional measures such as path length or elapsed time as the cost function, this algorithm uses uncertainty measure as the cost function. It uses mutual information between observation and estimation to describe the path quality and generates the best path of the multi-AUV system based on mutual information [42]. RRT∗ solves the problem that RRT is easy to fall into the minimum value, but the calculation speed of this algorithm is much slower than RRT, especially when it is applied to path planning in a wide range of environments. RRT-Smart made two modifications to RRT to make it converge faster than RRT∗. One modification is path optimization, which checks to shorten the path at each expansion step. Another modification is intelligent sampling, which selectively samples nodes with a high probability of success [43].Yu proposed a Smooth RRT path optimization algorithm considering the limitation of the AUV motion angle. The algorithm ignores the pitching motion and only considers the translation and rotation motion of AUV. By adding the convergence and angle factors, the growth point and exploration point of the expansion tree are improved, thereby improving the speed and practicability of the algorithm. The greedy algorithm is used to smooth the path to meet the special requirements of the shortest path and manoeuvrability of AUV [41]. Considering the kinematic constraints such as obstacle avoidance and dynamic constraints such as hard bounds and nonholonomic characteristics of AUV, Taheri et al. proposed a closed-loop RRT algorithm (CL-RRT), which is a randomized kinodynamic path planning algorithm based on incremental sampling. The term closed loop refers to the application of a 6DOF nonlinear AUV model and three fuzzy proportional derivative controllers (FPDC). In CL-RRT, the RRT algorithm generates the random offspring vertices and related branches for FPDC to design the appropriated control signals, feasible branches, and accessible vertices by considering the kinodynamic constraints of AUV. Compared with traditional RRT, CL-RRT can quickly plan the feasible path for AUV in the seabed environment or 3D space with cluttered obstacles, as shown in Figure 7 [44].Figure 7
An example of using CL-RRT to generate the final path [44]. (a) 3D cluttered space with nine static obstacles. (b) 3D seabed environment.
(a)(b)


#### 2.3.2. Probabilistic Roadmap Method

PRM is divided into two stages: learning and query. In the learning stage, the nodes in the motion space are randomly sampled, and adjacent nodes are searched at each node and connected to build a collision-free roadmap. In the query stage, a heuristic search algorithm is used to search for feasible paths from the roadmap based on the starting point, target point, and roadmap information [45]. This method can effectively avoid obstacles and is suitable for solving the motion planning problem in high-dimensional space [46]. McMahon and Plaku applied PRM to AUV mission and path planning and constructed a navigation roadmap through probabilistic sampling. The roadmap takes into account the effects of vehicle dynamics and ocean currents and enables AUV to avoid known obstacles, dangerous areas, or other forbidden regions. Simulation and underwater experiments show that the method can plan an obstacle-free, low-cost, and dynamically feasible path for AUV in the time-varying ocean current environment, such as riverine or estuary environment [47]. Huang et al. used the side-scan sonar of AUV to obtain environmental information such as obstacles to classify the seafloor and constructed a probabilistic roadmap based on the seafloor classification map to search for the shortest route for cable laying between the two islands. The roadmap effectively improves the construction efficiency of submarine cables and saves costs [48]. The path planned by PRM is not necessarily the optimal path because the random sampling of the roadmap nodes increases the randomness of the path planning. Besides, when AUV moves in a narrow channel, the efficiency of the probabilistic roadmap method will be reduced [49] because random sampling is difficult to achieve in a narrow space.


### 2.4. Intelligent Bionic Methods

Compared with the traditional path planning methods introduced above, the intelligent bionic method is a new type of path planning method. The main idea is to abstract the behaviours or thoughts of some animals in the nature as algorithms to solve the path planning problem. According to the characteristics of intelligent bionic algorithms, they are divided into three types: swarm intelligence algorithms, evolutionary algorithms, and human-inspired algorithms. The commonly used intelligent bionic algorithms are shown in Figure8, and Table 2 shows a simple comparison between them. Intelligent bionic algorithms may have some problems such as slow processing speed, poor stability and real-time performance, and easy to fall into local optimum. However, they have strong adaptability to the environment and are very suitable for the AUV path planning in complex dynamic environments. With the improvement of computing power and the emphasis on intelligent bionic algorithm research, intelligent bionic algorithms will be widely used in AUV path planning.Figure 8
Common intelligent bionic methods.Table 2
The comparison of different intelligent bionic methods.
MethodAdvantageDisadvantageApplicationPSO(1) Simple and easy to implement(1) Slow convergence speed in the late stage of search(1) 2D/3D environment(2) Few adjustable parameters(2) Possible to fall into a local optimal solution(2) Global/local path planning(3) High convergence accuracy(3) Unfeasible path(4) Fast search speed(5) Strong global search capabilityACO(1) Distributed computation(1) Slow convergence speed in the initial stage of search(1) 2D/3D environment(2) Positive feedback of information(2) Easy to fall into local optimum(2) Global path planning(3) Heuristic search(4) Easy to implementGA(1) High efficiency(1) Premature convergence(1) 2D/3D environment(2) Rarely falls into local optimum(2) Poor stability(2) Global/local path planning(3) Good robustness and adaptability(3) Slow search speed in the late stage of search(3) Complex environment(4) Strong global search capability5. Easy to combine with other algorithmsDE(1) Simpler than GAConverges prematurely to a local minimum as the evolutionary algebra increases(1) 2D/3D environment(2) Strong global convergence ability and robustness(2) Global path planningANN(1) Distributed parallel processing of information(1) Long learning time(1) 2D/3D environment(2) High intelligence(2) Poor generalization ability(2) Global path planning(3) Strong learning and adaptive ability(3) Slow processing speed(4) Strong robustness and high parallelism(4) Poor real-time performanceFL(1) No need to build accurate environment model(1) Heavy reliance on expert experience(1) 2D/3D environment(2) No complicated mathematical calculation required(2) Poor adaptability to the environment(2) Local path planning(3) Meets real-time requirements(3) Fuzzy rules are not easy to summarize in complex environmentsRL(1) Makes AUV have learning ability(1) Convergence speed(1) 2D/3D environment(2) Interacts with the environment(2) Exploration and development balance(2) Global/local path planning(3) No prior knowledge required(3) Complex, unknown, and dynamic environment(4) Real-time, efficient, and fastDRL(1) Captures the original sensor input directly(1) Time-consuming search(1) 2D/3D environment(2) Interacts with the environment(2) Overfitting(2) Global/local path planning(3) Strong environmental adaptability(3) Complex, unknown, and dynamic environment


#### 2.4.1. Swarm Intelligence Algorithms

The basic idea of the swarm intelligence algorithm is to simulate the activities of groups such as birds and ants in the nature. Through the individual cooperation mechanism in the group, information is transmitted to each other, and the optimal solution in the entire group is continuously updated until it converges to the global optimal.(1) Particle Swarm Optimization. The particle swarm optimization (PSO) algorithm is a random search algorithm that simulates the foraging behaviour of birds. The algorithm first initializes a group of random particles with only two properties of speed and position and then calculates each particle’s fitness value through the fitness function. The optimal solution that each particle searches individually is called individual extremum pBest, and the optimal individual extremum in the particle swarm is the current global optimal solution gBest. In each iteration, pBest and gBest are updated according to the fitness value of the particles, and then all particles update their speed and position according to pBest and gBest. PSO algorithm has a memory function, and all particles save their best historical position within themselves and the population. After several iterations, gBest is updated to find the optimal global solution that meets the termination conditions.The concept of the PSO algorithm is similar to the evolutionary algorithm, but the PSO algorithm is affected by individual and social behaviours [50]. PSO algorithm is simple and easy to implement, and it has the advantages of fewer adjustable parameters, high convergence accuracy, and strong global search ability [51]. It is one of the fastest optimization methods to solve the path planning problem and has been widely used in AUV path planning [52–54]. PSO converges faster in the initial search stage and slower in the later search stage and may fall into a locally optimal solution. Therefore, many improvements have been made to this method. Zhuang et al. proposed a hybrid algorithm that integrates PSO with Legendre pseudospectral method (LPM). The PSO-LPM uses PSO to initialize the robustness of random initial values and then switches the search algorithm to LPM to speed up the subsequent search process. The nonlinear 4DOF motion equation of AUV is established by neglecting AUV’s roll and pitch motion. The hybrid PSO-LPM algorithm can converge to the global optimum faster and better [55]. Lin et al. obtained depth information through stereovision detection technology to reconstruct obstacles and established a nonlinear 6DOF mathematical model of AUV. The self-tuning fuzzy control system is used to control the heading and depth of the AUV, and a single objective PSO (SOPSO) dynamic routing algorithm is used to plan the minimum time and energy consumption path. To overcome the local optimization of PSO, SOPSO uses random inertia weights to deal with the dynamic changing environment. In the presence of obstacles and currents, the algorithm can successfully plan a collision-free path for AUV [50].Due to the lack of constraints in the traditional PSO algorithm, an infeasible path may be generated during the update process. Yan et al. combined predictive control with the PSO algorithm (PSO-PC) and introduced two-step prediction into the particle update process. It can detect newer particles and avoid generating infeasible particles. Considering that the ocean current will affect the AUV motion, the algorithm establishes a typical uniform flow model with constant velocity to simulate the nearshore shallow sea environment. The PSO-PC algorithm solves multi-AUV patrol path planning in complex environments [56]. For unknown oceanic environment and irregular obstacles, Yan et al. proposed a real-time path planning algorithm that combines PSO and waypoint guidance (PSO-WG). The algorithm simplifies 6DOF kinematic model to 3DOF model according to the uncontrollable roll motion and the bilateral symmetric structure of AUV. PSO was used to search for suitable temporary waypoints as the current target point to guide the AUV. Besides, the algorithm also considers the turning restraints (including turning radius and angular velocity) of AUV to smooth the path. The comparison with APF and genetic algorithm shows that the algorithm can generate the optimal path [57]. PSO algorithm is an online path planning method, and it can also be applied to the coordinated path planning for unmanned aerial aquatic vehicle (UAAV) and AUV [58].The quantum-behaved particle swarm optimization algorithm (QPSO) is an improved version of PSO. QPSO assumes that each particle in the swarm has a quantum behaviour, instead of using the traditional position and velocity update rules in PSO [39]. Moreover, its overall performance is better than the PSO algorithm. In [39], Zeng et al. proposed a QPSO algorithm based on B-spline curves for path planning in a large environment ranging from tens to hundreds of kilometres. The ocean environment is modelled as a static current field composed of slowly changing eddies and static obstacles. The algorithm is compared with classic A∗, RRT, RRT∗, GA, and PSO algorithms (Figure 9). The simulation results show that QPSO can plan a better path in a short time. Twelve variants of particle swarm intelligence-based path planning algorithms are compared in [51]. They are applied to search for optimal paths in 2D and 3D ocean environments with obstacles and nonuniform currents. The physical motion limitations of AUV, including yaw and pitch motions, are also considered in the search process.Figure 9
A comparison of path planning algorithms in [39]. (a)A∗. (b) RRT. (c)RRT∗. (d) QPSO, PSO, and GA.
(a)(b)(c)(d)To overcome the local optimal limit, Li et al. introduced the adaptive law into QPSO and proposed an adaptive6 quantum-behaved particle swarm optimization algorithm (AQPSO). The Lamb–Oseen vortex was used to simulate the ocean current, and the obstacle avoidance model was established. In AQPSO, the quantum bit amplitude is used to encode the position, and the quantum rotation gate is used to update the particles. The mutation possibility and inertial factor are adaptively changed. The adaptive law and quantum behaviour significantly improve the search efficiency of the PSO algorithm. The algorithm takes the travel time as the fitness function and considers the dynamic constraints to meet the manoeuvrability of AUV. Compared with GA, PSO, and QPSO, AQPSO has better performance in time consumption and path smoothness [59]. Wu et al. proposed a distance evolution nonlinear particle swarm optimization (DENPSO) algorithm to save the energy consumption of AUV path planning. The algorithm has three major improvements. The first is to transform the inertia weight factor and learning factor from linear to nonlinear to ensure that the particles can fully explore the 3D underwater environment in the evolution process; the second is that the distance evolution factor will randomly disturb the particles with poor search range to prevent particles from falling into the local optimal area; the third is to use a penalty function to describe the target of energy optimization under obstacles and the ocean. Besides, DENPSO models the underwater environment, including eddy current field and obstacles. Considering that AUV’s rolling probability in the 3D underwater environment is very small, the 6DOF kinematic model of AUV is simplified. Compared with linear PSO (LPSO), DENPSO has reduced energy consumption by 2.1514e + 03 J in the 3D simulated underwater environment and 1.049e + 07 J in the real underwater environment, respectively [60].(2) Ant Colony Optimization. The ant colony optimization (ACO) algorithm was inspired by the behaviour that ants can find the shortest path to the food source in the foraging. The basic principle is that the positive feedback mechanism will increase the pheromone concentration on the shorter path. The pheromone can attract more ants. Finally, the optimal path will be found between the food source and the nest. ACO algorithm is an excellent probabilistic global optimization algorithm. It has the advantages of distributed computing, positive feedback of information, heuristic search, and easy implementation. Moreover, ACO has good applicability to 2D or 3D path planning. Luan et al. combined ACO with cuckoo search (CS) for AUV path planning. The hybrid optimization does not need manual adjustment, and the parameters are relatively small. The method can effectively shorten the length of the path [61]. Zhang et al. proposed an angle-optimized path planning algorithm based on the ACO algorithm. The algorithm takes angle and path length as optimization targets. The simulation results in dense obstacles environment show that the improved algorithm can reduce the rotation angle of the AUV and the path length, thus saving energy [62].However, the traditional ACO algorithm has some shortcomings, such as slow convergence speed and easy to fall into the local optimal solution. Therefore, the ACO algorithm is often combined with other algorithms (such asA∗ [63] and PSO [64]) to solve the AUV path planning problem better. Che et al. proposed an improved ACO algorithm based on PSO. The algorithm used the improved pheromone update rules and the heuristic function based on the PSO algorithm to find the optimal path for AUV. For complex undersea terrain, the uniform mesh method was used to construct a 3D undersea environment, and the movements of AUV were simplified into forward, transverse, and longitudinal movements. The 3D simulation results (Figure 10) show that the optimal path length is reduced by 17% compared to the traditional ACO algorithm [64]. Yao et al. proposed the bilevel optimization (BIO) scheme. The upper optimization uses ACO to find a collision-free channel composed of connected grids from the starting point to the endpoint. The lower optimization uses QPSO to find the optimal energy path in the channel generated by the upper algorithm. Moreover, the ocean environment was modelled as a strong current field with fixed and moving obstacles. The BIO scheme has high computational efficiency and can generate the time-optimal path of AUV in the obstacle environment [65]. Lin et al. proposed a hybrid quantum ant colony algorithm (hybrid QACO) for AUV’s real-time path planning. The algorithm proposed an adaptive quantum gate and an improved rule of pheromone update based on the motion characteristics of AUV in the process of obstacle avoidance. Besides, it combined the local search method with QACO. A nonlinear fitness function is defined to limit the yaw angle. The simulation results show that the algorithm can improve the path planning quality and obtain a smoother path [66]. Besides, efficient path planning and reasonable task allocation are the basic requirements to ensure improvement in work efficiency of AUV under limited energy.Figure 10
A comparison of path planning algorithms in [64]. (a) Traditional ACO. (b) Improved ACO.
(a)(b)


#### 2.4.2. Evolutionary Algorithms

Inspired by the biological evolution in the nature, the evolutionary algorithm is a global optimization algorithm with high robustness and wide adaptability. Genetic algorithm (GA), differential evolution (DE) algorithm, firefly algorithm (FA), and biogeography-based optimization (BBO) algorithm are common evolutionary algorithms that can effectively solve the path planning problem of AUV.(1) Genetic Algorithm. GA is a global optimization algorithm that simulates the natural selection of Darwin’s theory and the biological evolution of genetic mechanisms [35, 67]. GA first generates the initial population by coding and then calculates the fitness of individuals in the population. Then, the selection, crossover, and mutation operations are applied to the population to produce and preserve superior individuals and eliminate inferior individuals. After the genetic operation, the next generation population is obtained. After the continuous evolution of the population from generation to generation, the individual with the maximum fitness finally obtained can be used as the approximate optimal solution of the problem after decoding. This algorithm can search efficiently in a complex ocean environment [68] and rarely falls into the local optimal solution. Similar to the PSO algorithm, GA searches for the optimal solution through random iteration.The genetic algorithm has good robustness and adaptability and strong global search ability. It has a good effect on AUV path planning. Cao et al. used the genetic algorithm to search the globally optimal path of AUV. The algorithm improved the initial population generation method by detecting whether the connection between two adjacent points passed through obstacles and introduced a chamfer operator based on the traditional genetic operator to smooth the angle. The simulation results show that the algorithm accelerates the convergence speed while converging to the optimal solution [69]. However, the improved genetic algorithm uses a 2D plane figure to represent AUV’s working space and does not consider the motion characteristics of AUV and the 3D underwater environment. Ataei and Yousefi-Koma evaluated the optimal path of AUV based on the criteria of total length of path, margin of safety, smoothness of the planar motion, and gradient of diving and then used the nondominated sorting genetic algorithm (NSGA-II) to perform multiobjective optimization of the above four objectives. The 4DOF kinematic and dynamic models of AUV were established by neglecting roll and pitch motions. NSGA-II found the multicriteria optimal path for AUV in the 3D environment with static obstacles [70].The energy problem must be considered in AUV path planning, which is related to whether the AUV can reach the destination. Tanakitkorn et al. improved the cost function of GA to minimize the energy consumption of AUV during navigation. The improved cost function consists of energy consumption terms estimated from the dynamics of Delphin 2 AUV. Since the AUV is assumed to travel at a constant depth, only the surge, sway, and yaw motions of the AUV are considered. The improved GA algorithm effectively reduces AUV’s energy consumption in a 2D static environment, such as Heronry South Lake, labyrinth with many concave-shaped obstacles, and split ellipse [6]. Tsiogkas et al. applied the genetic algorithm to the AUV path planning under energy constraints and compared it with the optimal mixed-integer quadratic programming (MIQP). The genetic algorithm’s time efficiency is at least three times that of the optimal MIQP algorithm [71]. The ocean current has a great influence on the energy consumption of AUV in the complex and changeable ocean environment. Pan et al. proposed a genetic-ant hybrid algorithm to solve the path planning problem in the current environment. The hybrid algorithm establishes an ocean current model with grids based on B-spline function and redefines a new fusion strategy to improve the integration efficiency. The hybrid algorithm has a fast search speed, which effectively reduces the energy consumption of AUV [68]. To obtain the energy-optimal path, Yao et al. proposed an improved genetic algorithm (IGA). The grey wolf optimizer was used to modify the mutation operator so that the mutation always changed towards the optimal solution, which effectively improved the effectiveness of the mutation and enriched the diversity of the population. Compared with the path planned by GA, the path planned by IGA is not the shortest path (Figure 11), but this path saves energy by using ocean current [72].Figure 11
Comparison of the optimal paths between IGA and GA [72].The genetic algorithm has some shortcomings, such as early maturity, poor stability, and slow convergence speed. However, it is easy to combine with other algorithms and can give full play to its advantages in the iterative process. The genetic algorithm starts searching from a cluster rather than a single solution, which is conducive to global optimization. Moreover, the algorithm simultaneously processes multiple individuals in the population, that is, it evaluates multiple solutions in the search space. Therefore, the risk of falling into a locally optimal solution is reduced.(2) Differential Evolution. The principle of DE is similar to the genetic algorithm, and it also includes crossover, mutation, and selection operations. However, in the DE algorithm, the mutation operation uses differential mutation, and the selection operation uses a one-to-one elimination mechanism to update the population. In this way, the complexity of the genetic operation is reduced. DE is an effective technique for solving complex optimization problems, and it is also suitable for solving the path planning problem of AUV [73–75]. Zadeh et al. designed a path planner based on the DE algorithm. The planner considers AUV kinematics and ocean dynamics for path planning and models the operating terrain to simulate real underwater environments. The terrain includes offline map, static/dynamic time-varying ocean currents, and different moving and static uncertain obstacles. The simulation results show that the method has strong robustness and can effectively deal with ocean currents and obstacles [73]. DE algorithm can be combined with other algorithms to solve the AUV task assignment and path planning problems. Zadeh et al. used a specific combination of differential evolution and firefly optimization (DEFO) algorithms to simulate the synchronous process of task assignment and path planning. The simulation results in a large environment indicated that the algorithm could effectively reduce the energy consumed by path planning while completing the maximum number of assigned tasks [74]. Yu et al. combined DE with ACO for path planning of multiple AUV systems, and the hybrid algorithm achieved good results [75]. DE has strong global convergence ability and robustness, and its unique memory ability enables it to dynamically track the current search situation to adjust its search strategy.(3) Firefly Algorithm and Biogeography-Based Optimization. FA is a heuristic algorithm inspired by the flickering behaviour of fireflies. One firefly will be attracted by a brighter one to adjust its position. The position of fireflies represents the solution of the optimization problem. The traditional FA algorithm has some shortcomings in convergence speed and stability. Gu et al. proposed an improved FA algorithm that adjusts the length of random steps and parameters of the algorithm based on the distance between two fireflies and the iteration time. The excluding operator and contracting operator were used to improve the effect of obstacle avoidance, convergence speed, and path smoothness. The simulation results show that the algorithm can generate a feasible path with fast convergence speed in the 3D environment [76]. BBO is an evolutionary algorithm that simulates the equilibrium theory of island biogeography concept and is also suitable for AUV path planning [52]. MahmoudZadeh et al. developed a motion planner based on the BBO algorithm to deal with path planning in a real environment. Firstly, a real undersea environment model is built based on an offline map, which includes static and uncertain obstacles, current, and floating and moving objects. Then, the 6DOF kinematic model of AUV is established. Finally, the motion planner can quickly regenerate the optimal path of AUV by controlling the motion of AUV according to the underwater environment’s unexpected changes [77]. MahmoudZadeh et al. used PSO, DE, BBO, and FA to perform online path planning for AUV rendezvous and analysed the performance of the four. The comparison results (Figure 12) in different scenarios show that FA can effectively use the current to avoid obstacles and generate the optimal path in the spatiotemporal ocean flows, while DE has better performance in time optimality [78].Figure 12
Comparison of PSO, DE, FA, and BBO [78].


#### 2.4.3. Human-Inspired Algorithms

Human-inspired algorithms are inspired by human thought or social behaviour, including artificial neural network (ANN) algorithms, fuzzy logic (FL) algorithms, and learning algorithms (LAs).(1) Artificial Neural Network. ANN is a mathematical model that simulates the behaviour of animal or human neural networks and processes information in a distributed and parallel way. It has high intelligence; however, most ANNs have the disadvantages of long learning time, poor generalization ability, and slow processing speed. Moreover, it is difficult to ensure the real-time performance of path planning. Complex and changeable environments or obstacles are difficult to describe with mathematical formulas. However, neural network algorithms are still widely used in the AUV path planning due to their strong learning ability, adaptive ability, strong robustness, and high parallelism.In most cases, the working environment of AUV is unknown. To deal with AUV path planning in an unknown environment, Zhu et al. proposed a multi-AUV hunting algorithm based on a bioinspired neural network (BNN). On the basis of using the discrete grid map to represent the underwater environment, each neuron in the neural network corresponds to a grid cell in the grid map (Figure13), and then the moving path of the AUV is generated according to the activities of the neural network. BNN can quickly and efficiently plan a feasible path in the unknown environment with static obstacles of different shapes, including U shape, polygon shape, square shape, and rectangle shape [79]. Wu et al. added the lateral inhibition of obstacles to the neural network to solve the problem of AUV moving along the edges of obstacles and improve the safety and rationality of path planning [81]. However, the BNN algorithm does not consider ocean currents and 3D dynamic environments. There are some difficulties when BNN is applied to 3D path planning, such as complex calculation in a large environment and repeated path when the obstacle size is larger than the detection range of the sensor.Figure 13
(a) 2D BNN model [79]. (b) 3D BNN model [80].
(a)(b)Cao et al. extended BNN to the 3D underwater environment for multi-AUV target search and constructed a topologically organized bioinspired neurodynamic model based on the grid map to represent the dynamic environment. Each AUV searches the path according to the steepest gradient descent rule. The algorithm performs well in 3D underwater environments with static obstacles of different sizes and shapes [82]. Ni et al. improved the BNN by improving the shunting equation of the neural network model [83] and adding virtual target and target attractor [80] to adapt to the dynamic environment and improve the efficiency and real-time path planning. In [80], an improved dynamic BNN model that regards AUV as the core is proposed. The model will be reconstructed with the movement of AUV, and its radius depends on the detection range of the sensor. The simulation results show that the improved model can effectively solve the real-time path planning problems in different 3D unknown environments, including underwater environments with static and dynamic obstacles and special seabed environments such as underwater mountains, deep underwater valleys, and underwater caves. However, it does not take into account the effects of ocean currents on AUV path planning. To solve this problem, Cao and Zhu combined the BNN and velocity synthesis algorithm to optimize the path of AUV in a dynamic environment with ocean current [84]. BNN can also be combined with the self-organizing map (SOM) neural network to solve the task assignment and path planning of the multi-AUV system [85].The BNN algorithm does not correctly establish the cooperation mechanism between AUVs, which sometimes causes collisions between AUVs. Moreover, it has high computational complexity, low work efficiency, and long path planning time. In response to these shortcomings, Zhu et al. proposed the Glasius bioinspired neural network (GBNN) algorithm and applied it to multi-AUV complete coverage path planning [2, 7, 86]. The algorithm updates each AUV’s neural network activity according to the state of the grid map and the location of other AUVs. GBNN algorithm can improve planning efficiency and effectively reduce path planning time [86]. In the GBNN algorithm, all AUVs share working environment information, and each AUV treats other AUVs as moving obstacles, thus avoiding collisions and repeated search paths between multiple AUVs [87].(2) Fuzzy Logic. Fuzzy logic imitates the uncertainty judgment and reasoning thinking mode of the human brain and makes inference judgments for unknown systems based on environmental information and fuzzy rules to solve the problem of path planning [88, 89]. The algorithm takes the sensors' real-time measurement information as the input and generates the control information based on the experts' experience and knowledge as the output for AUV real-time path planning.Fuzzy logic does not need an accurate environment model and too complicated mathematical calculation and has achieved good results in AUV’s collision avoidance control and path planning [90]. Due to the complexity of the 3D fuzzy design, the fuzzy logic algorithm is generally used for 2D path planning. This problem can be solved by mapping the 3D environment into horizontal plane and vertical plane [91]. Based on the forward-looking sonar model, Sun et al. obtained the virtual acceleration and velocity of AUV in the horizontal and vertical plane through the fuzzy system and then used the velocity synthesis method to generate the real control variables. They developed a fuzzy inference system with an accelerate/break (A/B) module for real-time navigation and simplified the AUV’s motion into 4DOF (including surge, heave, pitch, and yaw) according to the thruster arrangement of AUV. The simulation results verify the effectiveness and feasibility of the method for path planning and obstacle avoidance in static or dynamic environments [92]. On this basis, using PSO or QPSO to optimize the membership function value in fuzzy logic rules can generate the optimal 3D path in complex underwater environments, as shown in Figure 14. In Figure 14(d), the QPSO fuzzy method converges faster and performs better [91, 92]. Zhou et al. used the fuzzy comprehensive evaluation (FCE) method based on the fuzzy logic decision to select the best route from the solution produced by the multiobjective particle swarm optimization (MOPSO) algorithm. The FCE method increased the sampling efficiency, reduced power consumption, and better completed the path planning mission in the spatiotemporal ocean environment [93]. Peng et al. proposed a fuzzy logic LOS guidance/control method to solve the uncertainties in the operating environment, which can adjust adaptively the navigation coefficient and improve the accuracy of path planning [94].Figure 14
A comparison of path planning algorithms in [91]. (a) 3D dynamic fuzzy path planning without optimization. (b) 3D dynamic PSO-fuzzy path planning. (c) 3D dynamic QPSO-fuzzy path planning. (d) Performance comparison of path planning.
(a)(b)(c)(d)The traditional 2-input fuzzy controller takes the distance and direction angle of the obstacle relative to the AUV as input. To reduce the computational complexity of the 2-input fuzzy controller, Yu et al. simplified it to a single-input fuzzy controller based on the signed distance method and introduced the asymmetry factor and slope to make the output surface of the single-input fuzzy controller nonlinear. The 5DOF kinematic and dynamic equations of the underactuated AUV were established by neglecting the rolling motion. The simplified nonlinear single-input fuzzy controller has good robustness and solves the problems of complex nonlinear AUV dynamics and unknown environmental disturbances [95]. For dynamic obstacles, Li et al. designed a 3-input fuzzy controller to reduce the influence of obstacle movement speed on the control effect. Compared with the traditional 2-input fuzzy controller, the 3-input fuzzy controller adds the change of the distance between the AUV and the obstacle as an input. The simulation results show that the 3-input controller can better avoid moving obstacles during the AUV navigation, and it is more effective than the commonly used 2-input controller when the obstacle moves fast [96].The fuzzy logic algorithm is often used to solve the local path planning problems of AUV. However, it relies heavily on expert experience and has poor adaptability to the environment. Fuzzy rules are difficult to summarize in complex underwater environments. Once determined, it is difficult to adjust online.(3) Learning Algorithm. Learning algorithm imitates the human learning process and is a new and popular path planning algorithm in recent years. It mainly includes reinforcement learning (RL), deep learning (DL), and deep reinforcement learning (DRL). The learning algorithm enables the AUV to autonomously plan the path according to the environment, which significantly improves the intelligence of path planning.Reinforcement learning is suitable for AUV path planning in a complex and unknown dynamic environment and has a good development prospect. Unlike supervised learning, which learns from training samples, reinforcement learning learns control strategies in the interaction between the system and the environment [97]. In Figure 15(a), AUV selects an action to act on the environment. The state will change after the environment accepts the action, and a reward signal is generated to feed back to AUV. Then, AUV selects the next action according to the reward signal and the current state of the environment. Reinforcement learning enables AUV to have strong self-learning ability and to effectively perform obstacle avoidance and path planning according to the environment. Vibhute proposed an adaptive dynamic programming (ADP) technique based on reinforcement learning and designed an obstacle-free path finder based on ADP to achieve the optimal motion control for AUV. Considering the motion characteristics of AUV, 6DOF kinematic and dynamic models are established. ADP effectively avoided the collision between AUV and static obstacles and realized the optimal path planning of AUV [98].Figure 15
(a) RL framework. (b) DRL framework.
(a)(b)Q-learning algorithm, similar to the dynamic programming algorithm, is one of the commonly used reinforcement learning algorithms in AUV path planning. Gautam and Ramanathan applied the Q-learning algorithm to path planning in the near-bottom ocean environment and established a cost function to describe the dynamics of AUV in near-bottom ocean currents. Q-learning, GA, ACO, and PSO were used to optimize the cost function and search the optimal path. The test results on SLOCUM Glider show that Q-learning has low computational complexity [99]. Considering that the ocean current in littoral regions will have a significant impact on the motion of AUV, Yoo and Kim used the Q-learning algorithm based on temporal difference learning for 2D path planning in complex ocean current disturbances. The 3DOF kinematic model was used to incorporate the nonholonomic motion characteristics of AUV. Constrained by the limited turning speed of the AUV, the action space of AUV was discretized, and the heading angle change was limited. Q-learning was used to determine the action sequence to generate the shortest time path. The simulation results (Figure 16) show that the algorithm can generate a feasible path in flood tidal current or ebb tidal current [100]. On the basis of using the Voronoi diagram to divide the spatial region, Han et al. used the Q-learning algorithm to plan the path of AUV in the subregion and set different reward functions to meet the requirements of the system. The algorithm effectively reduces the energy consumption of AUV [101]. Sarsa (λ) is also a commonly used reinforcement learning algorithm. To reduce the cost of removing sea urchins by AUV, Noguchi and Maki first used APF to make AUV track the seafloor and then used Sarsa (λ) with good convergence to plan a safe path without collision to approach and catch the sea urchins. In the simulation, the AUV successfully found a safe path to capture sea urchins in a complex situation [19].Figure 16
(a) Path planning in flood tide. (b) Path planning in ebb tide [100].
(a)(b)Reinforcement learning does not require prior knowledge, and it is real-time, efficient, and fast when solving AUV path planning problems. However, there are still many problems to be solved, such as convergence speed and equilibrium between exploration and exploitation [102].The search method based on deep learning can directly capture the original sensor input. DRL combines the perception ability of deep learning with the decision-making ability of reinforcement learning, as shown in Figure15(b). It can directly control AUV’s motion based on the input image to solve the path planning problem of AUV [103]. Cao et al. first used sonar imaging to obtain environmental information to establish a grid map of the AUV search area and then adopted the asynchronous advantage actor-critic (A3C) network structure to enable the AUV to learn from its own experience and generate search strategies for various unknown environments. At the same time, DRL and dual-stream Q-learning are applied to AUV obstacle avoidance and navigation to further optimize the search path. The simulation results show that the method can effectively control AUV to explore unknown environments [104]. However, deep reinforcement learning may have disadvantages such as long training time and overfitting to the environment.


## 2.1. Artificial Potential Field Methods

The artificial potential field (APF) algorithm was initially applied to the collision avoidance of the manipulator and is now widely used in the AUV path planning. Obstacles in the environment need to be considered when planning the AUV paths, and the APF algorithm can have a good obstacle avoidance effect. The basic idea of APF is to assume that the AUV is affected by a virtual artificial force field when it moves in an obstacle environment. The target point and the obstacle generate gravitational and repulsive forces on the AUV, respectively. The combined force of the two controls the movement of the AUV, as shown in Figure2.Figure 2
Force analysis of AUV in traditional APF.The APF algorithm is safe, efficient, and easy to implement. For static obstacles in an unknown environment, Solari Franco et al. proposed a potential field algorithm for obstacle avoidance using a mechanical scanning sonar. The algorithm assumes that the angular direction of each beam of the sonar is the possible direction for the AUV to select the path, then calculates the evaluation point potential at a certain distance from the AUV in each beam direction, and finally selects the lowest potential as the direction of AUV motion. The effectiveness of the algorithm was verified by simulation [16]. The APF algorithm performs well in path planning under a static environment. However, it does not consider the influence of ocean currents and dynamic obstacles, which will cause large deviations in practical applications. The underwater environment in which AUV works is different from the ground, and ocean currents will have a greater impact on AUV’s movement. Therefore, ocean currents and dynamic obstacles must be considered in AUV path planning. Cheng et al. proposed a new path planning algorithm combining artificial potential field and velocity synthesis, which better solves the path planning problem of AUV in ocean current environment with dynamic obstacles. This algorithm synthesizes the velocity of the ocean current and the AUV, and the direction of the synthetic velocity is accurately determined by the artificial potential field. Considering the influence of the relative velocity between AUV and dynamic obstacles on AUV motion, the velocity repulsive potential field determined by the relative velocity is introduced. Compared with the traditional APF, the time and path length are reduced by 15%, respectively [17].The APF algorithm also has a good obstacle avoidance effect on irregular obstacles. It is widely used in real-time obstacle avoidance and smooth path planning [18, 19], but the algorithm itself has some inherent shortcomings, such as the local minimum and goal nonreachable with obstacles nearby (GNRON). Setting a virtual obstacle near the local minimum can effectively solve the local minimum problem. The virtual obstacle will change the potential field around the AUV, thereby getting rid of the existing local minimum [16]. Fan et al. made three improvements to the traditional APF. The first is to add a distance correction factor into the repulsive potential field function to solve the GNRON problem; the second is to propose the regular hexagon-guided method to solve the local minima problem; the third is to introduce the relative velocity method to avoid the dynamic obstacles in time. The improved APF can find a collision-free optimal path in both static and dynamic environments [20].The APF algorithm can also be used for multi-AUV path planning. Based on the 3DOF kinematic and dynamic modelling of AUV under wave disturbances, Das et al. combined the APF, ant colony optimization, and clonal selection to solve the obstacle avoidance control of multi-AUV in an obstacle-rich environment. The combined algorithm overcomes the shortcomings that traditional APF is easy to fall into the local minimum and cannot find the path if there are many similar obstacles. The effectiveness of the algorithm for path planning under wave disturbances is verified in [21]. To improve the obstacle avoidance ability of AUV in the 2D environment, Liang et al. established 3DOF kinematic and dynamic models of AUV by ignoring the pitch, roll, and heave motion and then improved the repulsive force field based on the traditional APF. The modified repulsive force field is annular so that AUV can smoothly bypass obstacles at a safe distance. It also ensures the safety of multi-AUV path planning [22]. Some APF algorithms introduce the motion characteristics of AUV in the design, which will greatly increase the practicability of the algorithm.


## 2.2. Geometric Model Search Methods

The geometric model search methods are traditional and classical path planning methods. This method has been widely used in path planning because of its mature technology and simple implementation process. In this type of method, the establishment of the model is very strict, which directly affects the final planned path. Common geometric model search methods are Dijkstra,A∗, D∗, D∗ Lite, level set method (LSM), etc. The relationship between them is summarized in Figure 3, and Table 1 shows a simple comparison between them.Figure 3
The relationship between geometric model search methods.Table 1
Geometric model search methods.
MethodAdvantageDisadvantageApplicationDijkstra(1) Easy to implement(1) Low search efficiency(1) 2D environment(2) High success rate(2) Large storage space(2) Simple environment(3) Good stability and robustness(3) Global shortest path planning(4) Gets the optimal solution for the shortest pathA∗(1) Low calculation cost(1) Generated path is not smooth(1) 2D/3D environment(2) Short search time(2) High complexity in the multidimensional environment(2) Static/dynamic environment(3) High search efficiency(3) Global shortest path planningD∗Lite(1) Simple and stable(1) Less application(1) 2D/3D environment(2) High efficiency(2) Slow search speed in large environment(2) Simple/unknown environment(3) Effective obstacle avoidance(3) Local path planning(4) Dynamic searchLSM(1) Effectively simulates the dynamic process(1) Slow processing speed(1) 2D environment(2) Suitable for combining with ocean current(2) Long computation time(2) Dynamic ocean current environment(3) Global path planning


### 2.2.1. Dijkstra Algorithm

Dijkstra algorithm is a typical global shortest path planning algorithm [23, 24]. It starts from the starting point and uses the strategy of the greedy algorithm to traverse the adjacent nodes which are closest to the starting point and not visited. When it reaches the endpoint, it can find the shortest path from the starting point to the endpoint. Dijkstra algorithm is mainly used to solve the single-source shortest path problem in weighted directed or undirected graphs.Eichhorn applied the Dijkstra algorithm to a time-varying environment by adding time information in the weighted directed graph as an additional dimension. The algorithm searched for the path with the minimum sailing time as the optimization goal and achieved good results in both fixed and time-varying ocean currents [25]. In addition to ocean currents, obstacle avoidance is also a factor to be considered when searching for a path. Kirsanov et al. added an addition part (AP) to the traditional Dijkstra algorithm, which is mainly responsible for static and dynamic obstacle avoidance. AP uses the critical radius of collision between AUV and the dynamic obstacles to avoid dynamic obstacles. The modified algorithm also takes the dynamic characteristics of the ocean current into account to optimize the path. The numerical results show that the algorithm is effective in 2D path optimization [26]. Grefstad and Schjolberg used the Dijkstra algorithm for path planning on the basis of using sonar to detect obstacles and IKMs Merlin UCV and Statoils Snorre B oil field are used in reference [27]. The test results show that the algorithm can generate a new obstacle-free path, and the method is also applicable to AUV [27]. Dijkstra algorithm is easy to implement and has good stability and robustness. It can obtain the optimal solution of the shortest path by traversing all nodes and is suitable for path planning in simple environments. Although the path planning has a high success rate, the algorithm will occupy a large amount of storage space, and the search efficiency will become low when applied to large-scale and complex environments. The relaxed Dijkstra algorithm proposed by Ammar et al. solved the problem of global path planning in a large-scale grid environment, and the time to find the optimal solution is three times faster than the traditional Dijkstra algorithm [24].


### 2.2.2.A∗ and D∗ Lite Algorithms

A∗ algorithm is the most effective direct search algorithm for solving the shortest path in static road networks and is widely used to solve low-dimensional path planning problems. Compared with the Dijkstra algorithm, this algorithm uses heuristic information to guide the optimal path generation, which can reduce the calculation cost and improve the efficiency of path planning. The core idea of the A∗ algorithm is still an iterative process. A∗ algorithm evaluates the path cost through the function fn=gn+hn, where n is the position of AUV; fn is the path cost from the starting point to the target point; gn is the actual path cost from the starting point to the current position of the AUV; and hn is the estimated cost of the best path from the current position to the target point. Moreover, hn is the heuristic embodiment of the A∗ algorithm [28].The traditionalA∗ algorithm generates the optimal path by minimizing the path cost. However, it does not consider path length, obstacle collision risk, manoeuvrability restriction, and ocean currents in path planning [29]. Lefebvre et al. used path length and collision risk as optimization criteria to find the minimum risk path of AUV and proposed a hierarchical A∗ (HA∗) algorithm based on the hierarchical technique. HA∗ associates the collision risk represented by probability with path planning and solves the path planning problem in stages through an abstract graph. Dijkstra, A∗, hierarchical Dijkstra (HD), and HA∗ are used to plan the minimum length path and the minimum collision risk path of AUV, as shown in Figure 4. Compared with the traditional A∗ algorithm, HA∗ greatly improves the efficiency of path planning, although the path obtained by HA∗ is not optimal in length. The calculation time of the minimum length path and the minimum collision risk path is reduced by 71% and 86%, respectively [30].Figure 4
(a) Minimal length paths. (b) Minimal collision risk paths [30].
(a)(b)A∗ algorithm has a short planning time and a small amount of calculation. It is a global search algorithm commonly used in the AUV path planning. However, the A∗ algorithm will generate some unnecessary inflection points in the search process [31]. Moreover, the resulting final path is a multisegment path composed of many continuous straight lines, which is difficult to meet the requirements of AUV dynamic and kinematic constraints. Wang et al. combined the A∗ algorithm with a uniform cubic B-spline curve to generate a smooth path satisfying AUV motion constraints. The B-spline curve has independent control points that are easy to adjust, and it is more convenient and flexible to use the B-spline curve to fit the waypoints of a path generated by the A∗ algorithm. The simulation results show that this method can effectively smooth the path and shorten the path length and calculation time [32]. To minimize the energy consumption of AUV in an unknown ocean current environment, Li et al. improved the A∗ algorithm by using travel time as a heuristic cost function. In the simulation, the 6DOF nonlinear dynamic model of REMUS AUV was used, and the rudder turn angle of AUV was limited to less than 30 degrees considering the turn radius constraint. The algorithm’s effectiveness was verified under the condition that both the current velocity and AUV velocity are constant [1].TheD∗ algorithm, also known as dynamic A∗, is a dynamic shortest path algorithm. The D∗ algorithm can search the path in an unknown environment, but its efficiency is low. D∗ Lite algorithm is an improved version of the D∗ algorithm, which combines the advantages of the D∗ algorithm and the LPA∗ algorithm. Unlike the forward search used by LPA∗, D∗ Lite uses the reverse search (the target point is fixed and the starting point changes with time) [33], which makes the path planning easier and faster. Due to the dynamic characteristics of the underwater environment and the uncertainty and incompleteness of environmental information, it is necessary to replan the path in time when the AUV encounters unknown static or dynamic obstacles. D∗ Lite algorithm can effectively solve this problem. Sun et al. applied the D∗ Lite algorithm to the Maritime I AUV for 3D path planning in a partly unknown environment. Based on the description of the AUV structure, they used a grid map to rasterize the 3D underwater space. The simulation results under different obstacle environments prove that the algorithm is effective for both 2D and 3D underwater environments. In Figure 5, AUV can quickly replan the path when encountering unexpected obstacles (red cube) [34]. D∗ Lite algorithm is suitable for the AUV path planning in an unknown environment. However, few people have applied it to AUV path planning in recent years. Large environments will increase the time complexity of the algorithm search. Besides, the algorithm cannot cope with the fine planning of the local environment.Figure 5
An example of usingD∗ Lite to generate the final path [34]. (a) No unexpected obstacles. (b) Unexpected obstacles.
(a)(b)


### 2.2.3. Level Set Method

LSM was proposed by Osher and Sethian. LSM can naturally integrate the ocean model into the level set equations and effectively simulate dynamic processes, so it has attracted widespread attention in the AUV path planning considering the influence of ocean currents [35]. In 2017, Subramani et al. used the level set equation to plan a time-optimal path for the REMUS 600 AUV in a strong and dynamic ocean current environment and considered operational constraints (such as minimum depth). The test results in Buzzards Bay and Vineyard Sound regions showed that AUV reaches the target point along the time-optimal path 6–15% faster than the shortest path, although the local currents and geometric constraints are complex [36]. Since then, Subramani et al. have conducted further research on the application of the LSM method to path planning in the ocean current environment. Due to the uncertainty in the path planning, the stochastic dynamically orthogonal level set equation is applied to control the AUV to travel in an uncertain, strong, and dynamic ocean current environment, and the stochastic time-optimal path planning is carried out in [37]. Based on [37], Subramani and Lermusiaux combined the risk optimality criterion based on decision theory with the stochastic dynamically orthogonal level set equations to search for the risk-optimal path in a random dynamic environment, and it minimizes the suboptimal risk of the stochastic time-optimal path predictions [38]. The LSM method achieved good results in path planning under different ocean current environments, such as stochastic front, double-gyre QG flow, flow past an island, and flow exiting a strait [37, 38]. The LSM can solve more complicated problems, but it takes longer calculation time [39].


## 2.2.1. Dijkstra Algorithm

Dijkstra algorithm is a typical global shortest path planning algorithm [23, 24]. It starts from the starting point and uses the strategy of the greedy algorithm to traverse the adjacent nodes which are closest to the starting point and not visited. When it reaches the endpoint, it can find the shortest path from the starting point to the endpoint. Dijkstra algorithm is mainly used to solve the single-source shortest path problem in weighted directed or undirected graphs.Eichhorn applied the Dijkstra algorithm to a time-varying environment by adding time information in the weighted directed graph as an additional dimension. The algorithm searched for the path with the minimum sailing time as the optimization goal and achieved good results in both fixed and time-varying ocean currents [25]. In addition to ocean currents, obstacle avoidance is also a factor to be considered when searching for a path. Kirsanov et al. added an addition part (AP) to the traditional Dijkstra algorithm, which is mainly responsible for static and dynamic obstacle avoidance. AP uses the critical radius of collision between AUV and the dynamic obstacles to avoid dynamic obstacles. The modified algorithm also takes the dynamic characteristics of the ocean current into account to optimize the path. The numerical results show that the algorithm is effective in 2D path optimization [26]. Grefstad and Schjolberg used the Dijkstra algorithm for path planning on the basis of using sonar to detect obstacles and IKMs Merlin UCV and Statoils Snorre B oil field are used in reference [27]. The test results show that the algorithm can generate a new obstacle-free path, and the method is also applicable to AUV [27]. Dijkstra algorithm is easy to implement and has good stability and robustness. It can obtain the optimal solution of the shortest path by traversing all nodes and is suitable for path planning in simple environments. Although the path planning has a high success rate, the algorithm will occupy a large amount of storage space, and the search efficiency will become low when applied to large-scale and complex environments. The relaxed Dijkstra algorithm proposed by Ammar et al. solved the problem of global path planning in a large-scale grid environment, and the time to find the optimal solution is three times faster than the traditional Dijkstra algorithm [24].


## 2.2.2.A∗ and D∗ Lite Algorithms

A∗ algorithm is the most effective direct search algorithm for solving the shortest path in static road networks and is widely used to solve low-dimensional path planning problems. Compared with the Dijkstra algorithm, this algorithm uses heuristic information to guide the optimal path generation, which can reduce the calculation cost and improve the efficiency of path planning. The core idea of the A∗ algorithm is still an iterative process. A∗ algorithm evaluates the path cost through the function fn=gn+hn, where n is the position of AUV; fn is the path cost from the starting point to the target point; gn is the actual path cost from the starting point to the current position of the AUV; and hn is the estimated cost of the best path from the current position to the target point. Moreover, hn is the heuristic embodiment of the A∗ algorithm [28].The traditionalA∗ algorithm generates the optimal path by minimizing the path cost. However, it does not consider path length, obstacle collision risk, manoeuvrability restriction, and ocean currents in path planning [29]. Lefebvre et al. used path length and collision risk as optimization criteria to find the minimum risk path of AUV and proposed a hierarchical A∗ (HA∗) algorithm based on the hierarchical technique. HA∗ associates the collision risk represented by probability with path planning and solves the path planning problem in stages through an abstract graph. Dijkstra, A∗, hierarchical Dijkstra (HD), and HA∗ are used to plan the minimum length path and the minimum collision risk path of AUV, as shown in Figure 4. Compared with the traditional A∗ algorithm, HA∗ greatly improves the efficiency of path planning, although the path obtained by HA∗ is not optimal in length. The calculation time of the minimum length path and the minimum collision risk path is reduced by 71% and 86%, respectively [30].Figure 4
(a) Minimal length paths. (b) Minimal collision risk paths [30].
(a)(b)A∗ algorithm has a short planning time and a small amount of calculation. It is a global search algorithm commonly used in the AUV path planning. However, the A∗ algorithm will generate some unnecessary inflection points in the search process [31]. Moreover, the resulting final path is a multisegment path composed of many continuous straight lines, which is difficult to meet the requirements of AUV dynamic and kinematic constraints. Wang et al. combined the A∗ algorithm with a uniform cubic B-spline curve to generate a smooth path satisfying AUV motion constraints. The B-spline curve has independent control points that are easy to adjust, and it is more convenient and flexible to use the B-spline curve to fit the waypoints of a path generated by the A∗ algorithm. The simulation results show that this method can effectively smooth the path and shorten the path length and calculation time [32]. To minimize the energy consumption of AUV in an unknown ocean current environment, Li et al. improved the A∗ algorithm by using travel time as a heuristic cost function. In the simulation, the 6DOF nonlinear dynamic model of REMUS AUV was used, and the rudder turn angle of AUV was limited to less than 30 degrees considering the turn radius constraint. The algorithm’s effectiveness was verified under the condition that both the current velocity and AUV velocity are constant [1].TheD∗ algorithm, also known as dynamic A∗, is a dynamic shortest path algorithm. The D∗ algorithm can search the path in an unknown environment, but its efficiency is low. D∗ Lite algorithm is an improved version of the D∗ algorithm, which combines the advantages of the D∗ algorithm and the LPA∗ algorithm. Unlike the forward search used by LPA∗, D∗ Lite uses the reverse search (the target point is fixed and the starting point changes with time) [33], which makes the path planning easier and faster. Due to the dynamic characteristics of the underwater environment and the uncertainty and incompleteness of environmental information, it is necessary to replan the path in time when the AUV encounters unknown static or dynamic obstacles. D∗ Lite algorithm can effectively solve this problem. Sun et al. applied the D∗ Lite algorithm to the Maritime I AUV for 3D path planning in a partly unknown environment. Based on the description of the AUV structure, they used a grid map to rasterize the 3D underwater space. The simulation results under different obstacle environments prove that the algorithm is effective for both 2D and 3D underwater environments. In Figure 5, AUV can quickly replan the path when encountering unexpected obstacles (red cube) [34]. D∗ Lite algorithm is suitable for the AUV path planning in an unknown environment. However, few people have applied it to AUV path planning in recent years. Large environments will increase the time complexity of the algorithm search. Besides, the algorithm cannot cope with the fine planning of the local environment.Figure 5
An example of usingD∗ Lite to generate the final path [34]. (a) No unexpected obstacles. (b) Unexpected obstacles.
(a)(b)


## 2.2.3. Level Set Method

LSM was proposed by Osher and Sethian. LSM can naturally integrate the ocean model into the level set equations and effectively simulate dynamic processes, so it has attracted widespread attention in the AUV path planning considering the influence of ocean currents [35]. In 2017, Subramani et al. used the level set equation to plan a time-optimal path for the REMUS 600 AUV in a strong and dynamic ocean current environment and considered operational constraints (such as minimum depth). The test results in Buzzards Bay and Vineyard Sound regions showed that AUV reaches the target point along the time-optimal path 6–15% faster than the shortest path, although the local currents and geometric constraints are complex [36]. Since then, Subramani et al. have conducted further research on the application of the LSM method to path planning in the ocean current environment. Due to the uncertainty in the path planning, the stochastic dynamically orthogonal level set equation is applied to control the AUV to travel in an uncertain, strong, and dynamic ocean current environment, and the stochastic time-optimal path planning is carried out in [37]. Based on [37], Subramani and Lermusiaux combined the risk optimality criterion based on decision theory with the stochastic dynamically orthogonal level set equations to search for the risk-optimal path in a random dynamic environment, and it minimizes the suboptimal risk of the stochastic time-optimal path predictions [38]. The LSM method achieved good results in path planning under different ocean current environments, such as stochastic front, double-gyre QG flow, flow past an island, and flow exiting a strait [37, 38]. The LSM can solve more complicated problems, but it takes longer calculation time [39].


## 2.3. Random Sampling Methods

Random sampling methods, such as the rapidly exploring random tree (RRT) method and the probabilistic roadmap (PRM) method, perform well in the AUV path planning. This type of method uses random sampling to make probabilistic detection of the AUV underwater working environment to search the path [40], but this probability or randomness brings some challenges to the AUV path planning.


### 2.3.1. Rapidly Exploring Random Tree

RRT takes the initial point as the root node and generates a random extended tree by adding leaf nodes through random sampling (Figure6). When the leaf nodes in the random tree include the target point, a path from the initial point to the target point can be found in the random tree. RRT has a powerful spatial search capability and can effectively solve path planning in high-dimensional space and complex constraints. However, there are some problems such as the path is not optimal and the algorithm is easy to fall into a minimum.Figure 6
Basic RRT build process [41]. Xinit is an initial point, Xrand is a random sampling point, Xnearest is the nearest point to Xrand, and Xnew is a new point.With the development of the RRT algorithm, many variant algorithms have appeared. TheRRT∗ algorithm can converge to the optimal solution. Unlike RRT, which searches for the nearest neighbouring nodes in the roadmap, RRT∗ checks the connections with all neighbouring nodes within a specific radius. It can search for a path in the 2D or 3D environment. Hernández et al. improved the RRT∗ algorithm by using the concepts of anytime algorithm and lazy collision evaluation. The improved algorithm enables AUV to replan the path according to nearby obstacles perceived during navigation. The underwater experiments of the SPARUS-II AUV verified the effectiveness of the algorithm in planning obstacle-free paths in unknown underwater environments [8]. Aiming at the path planning problem of multi-AUV systems, Cui et al. proposed a multidimensional RRT∗ algorithm (MDMI-RRT∗) based on mutual information. Unlike traditional measures such as path length or elapsed time as the cost function, this algorithm uses uncertainty measure as the cost function. It uses mutual information between observation and estimation to describe the path quality and generates the best path of the multi-AUV system based on mutual information [42]. RRT∗ solves the problem that RRT is easy to fall into the minimum value, but the calculation speed of this algorithm is much slower than RRT, especially when it is applied to path planning in a wide range of environments. RRT-Smart made two modifications to RRT to make it converge faster than RRT∗. One modification is path optimization, which checks to shorten the path at each expansion step. Another modification is intelligent sampling, which selectively samples nodes with a high probability of success [43].Yu proposed a Smooth RRT path optimization algorithm considering the limitation of the AUV motion angle. The algorithm ignores the pitching motion and only considers the translation and rotation motion of AUV. By adding the convergence and angle factors, the growth point and exploration point of the expansion tree are improved, thereby improving the speed and practicability of the algorithm. The greedy algorithm is used to smooth the path to meet the special requirements of the shortest path and manoeuvrability of AUV [41]. Considering the kinematic constraints such as obstacle avoidance and dynamic constraints such as hard bounds and nonholonomic characteristics of AUV, Taheri et al. proposed a closed-loop RRT algorithm (CL-RRT), which is a randomized kinodynamic path planning algorithm based on incremental sampling. The term closed loop refers to the application of a 6DOF nonlinear AUV model and three fuzzy proportional derivative controllers (FPDC). In CL-RRT, the RRT algorithm generates the random offspring vertices and related branches for FPDC to design the appropriated control signals, feasible branches, and accessible vertices by considering the kinodynamic constraints of AUV. Compared with traditional RRT, CL-RRT can quickly plan the feasible path for AUV in the seabed environment or 3D space with cluttered obstacles, as shown in Figure 7 [44].Figure 7
An example of using CL-RRT to generate the final path [44]. (a) 3D cluttered space with nine static obstacles. (b) 3D seabed environment.
(a)(b)


### 2.3.2. Probabilistic Roadmap Method

PRM is divided into two stages: learning and query. In the learning stage, the nodes in the motion space are randomly sampled, and adjacent nodes are searched at each node and connected to build a collision-free roadmap. In the query stage, a heuristic search algorithm is used to search for feasible paths from the roadmap based on the starting point, target point, and roadmap information [45]. This method can effectively avoid obstacles and is suitable for solving the motion planning problem in high-dimensional space [46]. McMahon and Plaku applied PRM to AUV mission and path planning and constructed a navigation roadmap through probabilistic sampling. The roadmap takes into account the effects of vehicle dynamics and ocean currents and enables AUV to avoid known obstacles, dangerous areas, or other forbidden regions. Simulation and underwater experiments show that the method can plan an obstacle-free, low-cost, and dynamically feasible path for AUV in the time-varying ocean current environment, such as riverine or estuary environment [47]. Huang et al. used the side-scan sonar of AUV to obtain environmental information such as obstacles to classify the seafloor and constructed a probabilistic roadmap based on the seafloor classification map to search for the shortest route for cable laying between the two islands. The roadmap effectively improves the construction efficiency of submarine cables and saves costs [48]. The path planned by PRM is not necessarily the optimal path because the random sampling of the roadmap nodes increases the randomness of the path planning. Besides, when AUV moves in a narrow channel, the efficiency of the probabilistic roadmap method will be reduced [49] because random sampling is difficult to achieve in a narrow space.


## 2.3.1. Rapidly Exploring Random Tree

RRT takes the initial point as the root node and generates a random extended tree by adding leaf nodes through random sampling (Figure6). When the leaf nodes in the random tree include the target point, a path from the initial point to the target point can be found in the random tree. RRT has a powerful spatial search capability and can effectively solve path planning in high-dimensional space and complex constraints. However, there are some problems such as the path is not optimal and the algorithm is easy to fall into a minimum.Figure 6
Basic RRT build process [41]. Xinit is an initial point, Xrand is a random sampling point, Xnearest is the nearest point to Xrand, and Xnew is a new point.With the development of the RRT algorithm, many variant algorithms have appeared. TheRRT∗ algorithm can converge to the optimal solution. Unlike RRT, which searches for the nearest neighbouring nodes in the roadmap, RRT∗ checks the connections with all neighbouring nodes within a specific radius. It can search for a path in the 2D or 3D environment. Hernández et al. improved the RRT∗ algorithm by using the concepts of anytime algorithm and lazy collision evaluation. The improved algorithm enables AUV to replan the path according to nearby obstacles perceived during navigation. The underwater experiments of the SPARUS-II AUV verified the effectiveness of the algorithm in planning obstacle-free paths in unknown underwater environments [8]. Aiming at the path planning problem of multi-AUV systems, Cui et al. proposed a multidimensional RRT∗ algorithm (MDMI-RRT∗) based on mutual information. Unlike traditional measures such as path length or elapsed time as the cost function, this algorithm uses uncertainty measure as the cost function. It uses mutual information between observation and estimation to describe the path quality and generates the best path of the multi-AUV system based on mutual information [42]. RRT∗ solves the problem that RRT is easy to fall into the minimum value, but the calculation speed of this algorithm is much slower than RRT, especially when it is applied to path planning in a wide range of environments. RRT-Smart made two modifications to RRT to make it converge faster than RRT∗. One modification is path optimization, which checks to shorten the path at each expansion step. Another modification is intelligent sampling, which selectively samples nodes with a high probability of success [43].Yu proposed a Smooth RRT path optimization algorithm considering the limitation of the AUV motion angle. The algorithm ignores the pitching motion and only considers the translation and rotation motion of AUV. By adding the convergence and angle factors, the growth point and exploration point of the expansion tree are improved, thereby improving the speed and practicability of the algorithm. The greedy algorithm is used to smooth the path to meet the special requirements of the shortest path and manoeuvrability of AUV [41]. Considering the kinematic constraints such as obstacle avoidance and dynamic constraints such as hard bounds and nonholonomic characteristics of AUV, Taheri et al. proposed a closed-loop RRT algorithm (CL-RRT), which is a randomized kinodynamic path planning algorithm based on incremental sampling. The term closed loop refers to the application of a 6DOF nonlinear AUV model and three fuzzy proportional derivative controllers (FPDC). In CL-RRT, the RRT algorithm generates the random offspring vertices and related branches for FPDC to design the appropriated control signals, feasible branches, and accessible vertices by considering the kinodynamic constraints of AUV. Compared with traditional RRT, CL-RRT can quickly plan the feasible path for AUV in the seabed environment or 3D space with cluttered obstacles, as shown in Figure 7 [44].Figure 7
An example of using CL-RRT to generate the final path [44]. (a) 3D cluttered space with nine static obstacles. (b) 3D seabed environment.
(a)(b)


## 2.3.2. Probabilistic Roadmap Method

PRM is divided into two stages: learning and query. In the learning stage, the nodes in the motion space are randomly sampled, and adjacent nodes are searched at each node and connected to build a collision-free roadmap. In the query stage, a heuristic search algorithm is used to search for feasible paths from the roadmap based on the starting point, target point, and roadmap information [45]. This method can effectively avoid obstacles and is suitable for solving the motion planning problem in high-dimensional space [46]. McMahon and Plaku applied PRM to AUV mission and path planning and constructed a navigation roadmap through probabilistic sampling. The roadmap takes into account the effects of vehicle dynamics and ocean currents and enables AUV to avoid known obstacles, dangerous areas, or other forbidden regions. Simulation and underwater experiments show that the method can plan an obstacle-free, low-cost, and dynamically feasible path for AUV in the time-varying ocean current environment, such as riverine or estuary environment [47]. Huang et al. used the side-scan sonar of AUV to obtain environmental information such as obstacles to classify the seafloor and constructed a probabilistic roadmap based on the seafloor classification map to search for the shortest route for cable laying between the two islands. The roadmap effectively improves the construction efficiency of submarine cables and saves costs [48]. The path planned by PRM is not necessarily the optimal path because the random sampling of the roadmap nodes increases the randomness of the path planning. Besides, when AUV moves in a narrow channel, the efficiency of the probabilistic roadmap method will be reduced [49] because random sampling is difficult to achieve in a narrow space.


## 2.4. Intelligent Bionic Methods

Compared with the traditional path planning methods introduced above, the intelligent bionic method is a new type of path planning method. The main idea is to abstract the behaviours or thoughts of some animals in the nature as algorithms to solve the path planning problem. According to the characteristics of intelligent bionic algorithms, they are divided into three types: swarm intelligence algorithms, evolutionary algorithms, and human-inspired algorithms. The commonly used intelligent bionic algorithms are shown in Figure8, and Table 2 shows a simple comparison between them. Intelligent bionic algorithms may have some problems such as slow processing speed, poor stability and real-time performance, and easy to fall into local optimum. However, they have strong adaptability to the environment and are very suitable for the AUV path planning in complex dynamic environments. With the improvement of computing power and the emphasis on intelligent bionic algorithm research, intelligent bionic algorithms will be widely used in AUV path planning.Figure 8
Common intelligent bionic methods.Table 2
The comparison of different intelligent bionic methods.
MethodAdvantageDisadvantageApplicationPSO(1) Simple and easy to implement(1) Slow convergence speed in the late stage of search(1) 2D/3D environment(2) Few adjustable parameters(2) Possible to fall into a local optimal solution(2) Global/local path planning(3) High convergence accuracy(3) Unfeasible path(4) Fast search speed(5) Strong global search capabilityACO(1) Distributed computation(1) Slow convergence speed in the initial stage of search(1) 2D/3D environment(2) Positive feedback of information(2) Easy to fall into local optimum(2) Global path planning(3) Heuristic search(4) Easy to implementGA(1) High efficiency(1) Premature convergence(1) 2D/3D environment(2) Rarely falls into local optimum(2) Poor stability(2) Global/local path planning(3) Good robustness and adaptability(3) Slow search speed in the late stage of search(3) Complex environment(4) Strong global search capability5. Easy to combine with other algorithmsDE(1) Simpler than GAConverges prematurely to a local minimum as the evolutionary algebra increases(1) 2D/3D environment(2) Strong global convergence ability and robustness(2) Global path planningANN(1) Distributed parallel processing of information(1) Long learning time(1) 2D/3D environment(2) High intelligence(2) Poor generalization ability(2) Global path planning(3) Strong learning and adaptive ability(3) Slow processing speed(4) Strong robustness and high parallelism(4) Poor real-time performanceFL(1) No need to build accurate environment model(1) Heavy reliance on expert experience(1) 2D/3D environment(2) No complicated mathematical calculation required(2) Poor adaptability to the environment(2) Local path planning(3) Meets real-time requirements(3) Fuzzy rules are not easy to summarize in complex environmentsRL(1) Makes AUV have learning ability(1) Convergence speed(1) 2D/3D environment(2) Interacts with the environment(2) Exploration and development balance(2) Global/local path planning(3) No prior knowledge required(3) Complex, unknown, and dynamic environment(4) Real-time, efficient, and fastDRL(1) Captures the original sensor input directly(1) Time-consuming search(1) 2D/3D environment(2) Interacts with the environment(2) Overfitting(2) Global/local path planning(3) Strong environmental adaptability(3) Complex, unknown, and dynamic environment


### 2.4.1. Swarm Intelligence Algorithms

The basic idea of the swarm intelligence algorithm is to simulate the activities of groups such as birds and ants in the nature. Through the individual cooperation mechanism in the group, information is transmitted to each other, and the optimal solution in the entire group is continuously updated until it converges to the global optimal.(1) Particle Swarm Optimization. The particle swarm optimization (PSO) algorithm is a random search algorithm that simulates the foraging behaviour of birds. The algorithm first initializes a group of random particles with only two properties of speed and position and then calculates each particle’s fitness value through the fitness function. The optimal solution that each particle searches individually is called individual extremum pBest, and the optimal individual extremum in the particle swarm is the current global optimal solution gBest. In each iteration, pBest and gBest are updated according to the fitness value of the particles, and then all particles update their speed and position according to pBest and gBest. PSO algorithm has a memory function, and all particles save their best historical position within themselves and the population. After several iterations, gBest is updated to find the optimal global solution that meets the termination conditions.The concept of the PSO algorithm is similar to the evolutionary algorithm, but the PSO algorithm is affected by individual and social behaviours [50]. PSO algorithm is simple and easy to implement, and it has the advantages of fewer adjustable parameters, high convergence accuracy, and strong global search ability [51]. It is one of the fastest optimization methods to solve the path planning problem and has been widely used in AUV path planning [52–54]. PSO converges faster in the initial search stage and slower in the later search stage and may fall into a locally optimal solution. Therefore, many improvements have been made to this method. Zhuang et al. proposed a hybrid algorithm that integrates PSO with Legendre pseudospectral method (LPM). The PSO-LPM uses PSO to initialize the robustness of random initial values and then switches the search algorithm to LPM to speed up the subsequent search process. The nonlinear 4DOF motion equation of AUV is established by neglecting AUV’s roll and pitch motion. The hybrid PSO-LPM algorithm can converge to the global optimum faster and better [55]. Lin et al. obtained depth information through stereovision detection technology to reconstruct obstacles and established a nonlinear 6DOF mathematical model of AUV. The self-tuning fuzzy control system is used to control the heading and depth of the AUV, and a single objective PSO (SOPSO) dynamic routing algorithm is used to plan the minimum time and energy consumption path. To overcome the local optimization of PSO, SOPSO uses random inertia weights to deal with the dynamic changing environment. In the presence of obstacles and currents, the algorithm can successfully plan a collision-free path for AUV [50].Due to the lack of constraints in the traditional PSO algorithm, an infeasible path may be generated during the update process. Yan et al. combined predictive control with the PSO algorithm (PSO-PC) and introduced two-step prediction into the particle update process. It can detect newer particles and avoid generating infeasible particles. Considering that the ocean current will affect the AUV motion, the algorithm establishes a typical uniform flow model with constant velocity to simulate the nearshore shallow sea environment. The PSO-PC algorithm solves multi-AUV patrol path planning in complex environments [56]. For unknown oceanic environment and irregular obstacles, Yan et al. proposed a real-time path planning algorithm that combines PSO and waypoint guidance (PSO-WG). The algorithm simplifies 6DOF kinematic model to 3DOF model according to the uncontrollable roll motion and the bilateral symmetric structure of AUV. PSO was used to search for suitable temporary waypoints as the current target point to guide the AUV. Besides, the algorithm also considers the turning restraints (including turning radius and angular velocity) of AUV to smooth the path. The comparison with APF and genetic algorithm shows that the algorithm can generate the optimal path [57]. PSO algorithm is an online path planning method, and it can also be applied to the coordinated path planning for unmanned aerial aquatic vehicle (UAAV) and AUV [58].The quantum-behaved particle swarm optimization algorithm (QPSO) is an improved version of PSO. QPSO assumes that each particle in the swarm has a quantum behaviour, instead of using the traditional position and velocity update rules in PSO [39]. Moreover, its overall performance is better than the PSO algorithm. In [39], Zeng et al. proposed a QPSO algorithm based on B-spline curves for path planning in a large environment ranging from tens to hundreds of kilometres. The ocean environment is modelled as a static current field composed of slowly changing eddies and static obstacles. The algorithm is compared with classic A∗, RRT, RRT∗, GA, and PSO algorithms (Figure 9). The simulation results show that QPSO can plan a better path in a short time. Twelve variants of particle swarm intelligence-based path planning algorithms are compared in [51]. They are applied to search for optimal paths in 2D and 3D ocean environments with obstacles and nonuniform currents. The physical motion limitations of AUV, including yaw and pitch motions, are also considered in the search process.Figure 9
A comparison of path planning algorithms in [39]. (a)A∗. (b) RRT. (c)RRT∗. (d) QPSO, PSO, and GA.
(a)(b)(c)(d)To overcome the local optimal limit, Li et al. introduced the adaptive law into QPSO and proposed an adaptive6 quantum-behaved particle swarm optimization algorithm (AQPSO). The Lamb–Oseen vortex was used to simulate the ocean current, and the obstacle avoidance model was established. In AQPSO, the quantum bit amplitude is used to encode the position, and the quantum rotation gate is used to update the particles. The mutation possibility and inertial factor are adaptively changed. The adaptive law and quantum behaviour significantly improve the search efficiency of the PSO algorithm. The algorithm takes the travel time as the fitness function and considers the dynamic constraints to meet the manoeuvrability of AUV. Compared with GA, PSO, and QPSO, AQPSO has better performance in time consumption and path smoothness [59]. Wu et al. proposed a distance evolution nonlinear particle swarm optimization (DENPSO) algorithm to save the energy consumption of AUV path planning. The algorithm has three major improvements. The first is to transform the inertia weight factor and learning factor from linear to nonlinear to ensure that the particles can fully explore the 3D underwater environment in the evolution process; the second is that the distance evolution factor will randomly disturb the particles with poor search range to prevent particles from falling into the local optimal area; the third is to use a penalty function to describe the target of energy optimization under obstacles and the ocean. Besides, DENPSO models the underwater environment, including eddy current field and obstacles. Considering that AUV’s rolling probability in the 3D underwater environment is very small, the 6DOF kinematic model of AUV is simplified. Compared with linear PSO (LPSO), DENPSO has reduced energy consumption by 2.1514e + 03 J in the 3D simulated underwater environment and 1.049e + 07 J in the real underwater environment, respectively [60].(2) Ant Colony Optimization. The ant colony optimization (ACO) algorithm was inspired by the behaviour that ants can find the shortest path to the food source in the foraging. The basic principle is that the positive feedback mechanism will increase the pheromone concentration on the shorter path. The pheromone can attract more ants. Finally, the optimal path will be found between the food source and the nest. ACO algorithm is an excellent probabilistic global optimization algorithm. It has the advantages of distributed computing, positive feedback of information, heuristic search, and easy implementation. Moreover, ACO has good applicability to 2D or 3D path planning. Luan et al. combined ACO with cuckoo search (CS) for AUV path planning. The hybrid optimization does not need manual adjustment, and the parameters are relatively small. The method can effectively shorten the length of the path [61]. Zhang et al. proposed an angle-optimized path planning algorithm based on the ACO algorithm. The algorithm takes angle and path length as optimization targets. The simulation results in dense obstacles environment show that the improved algorithm can reduce the rotation angle of the AUV and the path length, thus saving energy [62].However, the traditional ACO algorithm has some shortcomings, such as slow convergence speed and easy to fall into the local optimal solution. Therefore, the ACO algorithm is often combined with other algorithms (such asA∗ [63] and PSO [64]) to solve the AUV path planning problem better. Che et al. proposed an improved ACO algorithm based on PSO. The algorithm used the improved pheromone update rules and the heuristic function based on the PSO algorithm to find the optimal path for AUV. For complex undersea terrain, the uniform mesh method was used to construct a 3D undersea environment, and the movements of AUV were simplified into forward, transverse, and longitudinal movements. The 3D simulation results (Figure 10) show that the optimal path length is reduced by 17% compared to the traditional ACO algorithm [64]. Yao et al. proposed the bilevel optimization (BIO) scheme. The upper optimization uses ACO to find a collision-free channel composed of connected grids from the starting point to the endpoint. The lower optimization uses QPSO to find the optimal energy path in the channel generated by the upper algorithm. Moreover, the ocean environment was modelled as a strong current field with fixed and moving obstacles. The BIO scheme has high computational efficiency and can generate the time-optimal path of AUV in the obstacle environment [65]. Lin et al. proposed a hybrid quantum ant colony algorithm (hybrid QACO) for AUV’s real-time path planning. The algorithm proposed an adaptive quantum gate and an improved rule of pheromone update based on the motion characteristics of AUV in the process of obstacle avoidance. Besides, it combined the local search method with QACO. A nonlinear fitness function is defined to limit the yaw angle. The simulation results show that the algorithm can improve the path planning quality and obtain a smoother path [66]. Besides, efficient path planning and reasonable task allocation are the basic requirements to ensure improvement in work efficiency of AUV under limited energy.Figure 10
A comparison of path planning algorithms in [64]. (a) Traditional ACO. (b) Improved ACO.
(a)(b)


### 2.4.2. Evolutionary Algorithms

Inspired by the biological evolution in the nature, the evolutionary algorithm is a global optimization algorithm with high robustness and wide adaptability. Genetic algorithm (GA), differential evolution (DE) algorithm, firefly algorithm (FA), and biogeography-based optimization (BBO) algorithm are common evolutionary algorithms that can effectively solve the path planning problem of AUV.(1) Genetic Algorithm. GA is a global optimization algorithm that simulates the natural selection of Darwin’s theory and the biological evolution of genetic mechanisms [35, 67]. GA first generates the initial population by coding and then calculates the fitness of individuals in the population. Then, the selection, crossover, and mutation operations are applied to the population to produce and preserve superior individuals and eliminate inferior individuals. After the genetic operation, the next generation population is obtained. After the continuous evolution of the population from generation to generation, the individual with the maximum fitness finally obtained can be used as the approximate optimal solution of the problem after decoding. This algorithm can search efficiently in a complex ocean environment [68] and rarely falls into the local optimal solution. Similar to the PSO algorithm, GA searches for the optimal solution through random iteration.The genetic algorithm has good robustness and adaptability and strong global search ability. It has a good effect on AUV path planning. Cao et al. used the genetic algorithm to search the globally optimal path of AUV. The algorithm improved the initial population generation method by detecting whether the connection between two adjacent points passed through obstacles and introduced a chamfer operator based on the traditional genetic operator to smooth the angle. The simulation results show that the algorithm accelerates the convergence speed while converging to the optimal solution [69]. However, the improved genetic algorithm uses a 2D plane figure to represent AUV’s working space and does not consider the motion characteristics of AUV and the 3D underwater environment. Ataei and Yousefi-Koma evaluated the optimal path of AUV based on the criteria of total length of path, margin of safety, smoothness of the planar motion, and gradient of diving and then used the nondominated sorting genetic algorithm (NSGA-II) to perform multiobjective optimization of the above four objectives. The 4DOF kinematic and dynamic models of AUV were established by neglecting roll and pitch motions. NSGA-II found the multicriteria optimal path for AUV in the 3D environment with static obstacles [70].The energy problem must be considered in AUV path planning, which is related to whether the AUV can reach the destination. Tanakitkorn et al. improved the cost function of GA to minimize the energy consumption of AUV during navigation. The improved cost function consists of energy consumption terms estimated from the dynamics of Delphin 2 AUV. Since the AUV is assumed to travel at a constant depth, only the surge, sway, and yaw motions of the AUV are considered. The improved GA algorithm effectively reduces AUV’s energy consumption in a 2D static environment, such as Heronry South Lake, labyrinth with many concave-shaped obstacles, and split ellipse [6]. Tsiogkas et al. applied the genetic algorithm to the AUV path planning under energy constraints and compared it with the optimal mixed-integer quadratic programming (MIQP). The genetic algorithm’s time efficiency is at least three times that of the optimal MIQP algorithm [71]. The ocean current has a great influence on the energy consumption of AUV in the complex and changeable ocean environment. Pan et al. proposed a genetic-ant hybrid algorithm to solve the path planning problem in the current environment. The hybrid algorithm establishes an ocean current model with grids based on B-spline function and redefines a new fusion strategy to improve the integration efficiency. The hybrid algorithm has a fast search speed, which effectively reduces the energy consumption of AUV [68]. To obtain the energy-optimal path, Yao et al. proposed an improved genetic algorithm (IGA). The grey wolf optimizer was used to modify the mutation operator so that the mutation always changed towards the optimal solution, which effectively improved the effectiveness of the mutation and enriched the diversity of the population. Compared with the path planned by GA, the path planned by IGA is not the shortest path (Figure 11), but this path saves energy by using ocean current [72].Figure 11
Comparison of the optimal paths between IGA and GA [72].The genetic algorithm has some shortcomings, such as early maturity, poor stability, and slow convergence speed. However, it is easy to combine with other algorithms and can give full play to its advantages in the iterative process. The genetic algorithm starts searching from a cluster rather than a single solution, which is conducive to global optimization. Moreover, the algorithm simultaneously processes multiple individuals in the population, that is, it evaluates multiple solutions in the search space. Therefore, the risk of falling into a locally optimal solution is reduced.(2) Differential Evolution. The principle of DE is similar to the genetic algorithm, and it also includes crossover, mutation, and selection operations. However, in the DE algorithm, the mutation operation uses differential mutation, and the selection operation uses a one-to-one elimination mechanism to update the population. In this way, the complexity of the genetic operation is reduced. DE is an effective technique for solving complex optimization problems, and it is also suitable for solving the path planning problem of AUV [73–75]. Zadeh et al. designed a path planner based on the DE algorithm. The planner considers AUV kinematics and ocean dynamics for path planning and models the operating terrain to simulate real underwater environments. The terrain includes offline map, static/dynamic time-varying ocean currents, and different moving and static uncertain obstacles. The simulation results show that the method has strong robustness and can effectively deal with ocean currents and obstacles [73]. DE algorithm can be combined with other algorithms to solve the AUV task assignment and path planning problems. Zadeh et al. used a specific combination of differential evolution and firefly optimization (DEFO) algorithms to simulate the synchronous process of task assignment and path planning. The simulation results in a large environment indicated that the algorithm could effectively reduce the energy consumed by path planning while completing the maximum number of assigned tasks [74]. Yu et al. combined DE with ACO for path planning of multiple AUV systems, and the hybrid algorithm achieved good results [75]. DE has strong global convergence ability and robustness, and its unique memory ability enables it to dynamically track the current search situation to adjust its search strategy.(3) Firefly Algorithm and Biogeography-Based Optimization. FA is a heuristic algorithm inspired by the flickering behaviour of fireflies. One firefly will be attracted by a brighter one to adjust its position. The position of fireflies represents the solution of the optimization problem. The traditional FA algorithm has some shortcomings in convergence speed and stability. Gu et al. proposed an improved FA algorithm that adjusts the length of random steps and parameters of the algorithm based on the distance between two fireflies and the iteration time. The excluding operator and contracting operator were used to improve the effect of obstacle avoidance, convergence speed, and path smoothness. The simulation results show that the algorithm can generate a feasible path with fast convergence speed in the 3D environment [76]. BBO is an evolutionary algorithm that simulates the equilibrium theory of island biogeography concept and is also suitable for AUV path planning [52]. MahmoudZadeh et al. developed a motion planner based on the BBO algorithm to deal with path planning in a real environment. Firstly, a real undersea environment model is built based on an offline map, which includes static and uncertain obstacles, current, and floating and moving objects. Then, the 6DOF kinematic model of AUV is established. Finally, the motion planner can quickly regenerate the optimal path of AUV by controlling the motion of AUV according to the underwater environment’s unexpected changes [77]. MahmoudZadeh et al. used PSO, DE, BBO, and FA to perform online path planning for AUV rendezvous and analysed the performance of the four. The comparison results (Figure 12) in different scenarios show that FA can effectively use the current to avoid obstacles and generate the optimal path in the spatiotemporal ocean flows, while DE has better performance in time optimality [78].Figure 12
Comparison of PSO, DE, FA, and BBO [78].


### 2.4.3. Human-Inspired Algorithms

Human-inspired algorithms are inspired by human thought or social behaviour, including artificial neural network (ANN) algorithms, fuzzy logic (FL) algorithms, and learning algorithms (LAs).(1) Artificial Neural Network. ANN is a mathematical model that simulates the behaviour of animal or human neural networks and processes information in a distributed and parallel way. It has high intelligence; however, most ANNs have the disadvantages of long learning time, poor generalization ability, and slow processing speed. Moreover, it is difficult to ensure the real-time performance of path planning. Complex and changeable environments or obstacles are difficult to describe with mathematical formulas. However, neural network algorithms are still widely used in the AUV path planning due to their strong learning ability, adaptive ability, strong robustness, and high parallelism.In most cases, the working environment of AUV is unknown. To deal with AUV path planning in an unknown environment, Zhu et al. proposed a multi-AUV hunting algorithm based on a bioinspired neural network (BNN). On the basis of using the discrete grid map to represent the underwater environment, each neuron in the neural network corresponds to a grid cell in the grid map (Figure13), and then the moving path of the AUV is generated according to the activities of the neural network. BNN can quickly and efficiently plan a feasible path in the unknown environment with static obstacles of different shapes, including U shape, polygon shape, square shape, and rectangle shape [79]. Wu et al. added the lateral inhibition of obstacles to the neural network to solve the problem of AUV moving along the edges of obstacles and improve the safety and rationality of path planning [81]. However, the BNN algorithm does not consider ocean currents and 3D dynamic environments. There are some difficulties when BNN is applied to 3D path planning, such as complex calculation in a large environment and repeated path when the obstacle size is larger than the detection range of the sensor.Figure 13
(a) 2D BNN model [79]. (b) 3D BNN model [80].
(a)(b)Cao et al. extended BNN to the 3D underwater environment for multi-AUV target search and constructed a topologically organized bioinspired neurodynamic model based on the grid map to represent the dynamic environment. Each AUV searches the path according to the steepest gradient descent rule. The algorithm performs well in 3D underwater environments with static obstacles of different sizes and shapes [82]. Ni et al. improved the BNN by improving the shunting equation of the neural network model [83] and adding virtual target and target attractor [80] to adapt to the dynamic environment and improve the efficiency and real-time path planning. In [80], an improved dynamic BNN model that regards AUV as the core is proposed. The model will be reconstructed with the movement of AUV, and its radius depends on the detection range of the sensor. The simulation results show that the improved model can effectively solve the real-time path planning problems in different 3D unknown environments, including underwater environments with static and dynamic obstacles and special seabed environments such as underwater mountains, deep underwater valleys, and underwater caves. However, it does not take into account the effects of ocean currents on AUV path planning. To solve this problem, Cao and Zhu combined the BNN and velocity synthesis algorithm to optimize the path of AUV in a dynamic environment with ocean current [84]. BNN can also be combined with the self-organizing map (SOM) neural network to solve the task assignment and path planning of the multi-AUV system [85].The BNN algorithm does not correctly establish the cooperation mechanism between AUVs, which sometimes causes collisions between AUVs. Moreover, it has high computational complexity, low work efficiency, and long path planning time. In response to these shortcomings, Zhu et al. proposed the Glasius bioinspired neural network (GBNN) algorithm and applied it to multi-AUV complete coverage path planning [2, 7, 86]. The algorithm updates each AUV’s neural network activity according to the state of the grid map and the location of other AUVs. GBNN algorithm can improve planning efficiency and effectively reduce path planning time [86]. In the GBNN algorithm, all AUVs share working environment information, and each AUV treats other AUVs as moving obstacles, thus avoiding collisions and repeated search paths between multiple AUVs [87].(2) Fuzzy Logic. Fuzzy logic imitates the uncertainty judgment and reasoning thinking mode of the human brain and makes inference judgments for unknown systems based on environmental information and fuzzy rules to solve the problem of path planning [88, 89]. The algorithm takes the sensors' real-time measurement information as the input and generates the control information based on the experts' experience and knowledge as the output for AUV real-time path planning.Fuzzy logic does not need an accurate environment model and too complicated mathematical calculation and has achieved good results in AUV’s collision avoidance control and path planning [90]. Due to the complexity of the 3D fuzzy design, the fuzzy logic algorithm is generally used for 2D path planning. This problem can be solved by mapping the 3D environment into horizontal plane and vertical plane [91]. Based on the forward-looking sonar model, Sun et al. obtained the virtual acceleration and velocity of AUV in the horizontal and vertical plane through the fuzzy system and then used the velocity synthesis method to generate the real control variables. They developed a fuzzy inference system with an accelerate/break (A/B) module for real-time navigation and simplified the AUV’s motion into 4DOF (including surge, heave, pitch, and yaw) according to the thruster arrangement of AUV. The simulation results verify the effectiveness and feasibility of the method for path planning and obstacle avoidance in static or dynamic environments [92]. On this basis, using PSO or QPSO to optimize the membership function value in fuzzy logic rules can generate the optimal 3D path in complex underwater environments, as shown in Figure 14. In Figure 14(d), the QPSO fuzzy method converges faster and performs better [91, 92]. Zhou et al. used the fuzzy comprehensive evaluation (FCE) method based on the fuzzy logic decision to select the best route from the solution produced by the multiobjective particle swarm optimization (MOPSO) algorithm. The FCE method increased the sampling efficiency, reduced power consumption, and better completed the path planning mission in the spatiotemporal ocean environment [93]. Peng et al. proposed a fuzzy logic LOS guidance/control method to solve the uncertainties in the operating environment, which can adjust adaptively the navigation coefficient and improve the accuracy of path planning [94].Figure 14
A comparison of path planning algorithms in [91]. (a) 3D dynamic fuzzy path planning without optimization. (b) 3D dynamic PSO-fuzzy path planning. (c) 3D dynamic QPSO-fuzzy path planning. (d) Performance comparison of path planning.
(a)(b)(c)(d)The traditional 2-input fuzzy controller takes the distance and direction angle of the obstacle relative to the AUV as input. To reduce the computational complexity of the 2-input fuzzy controller, Yu et al. simplified it to a single-input fuzzy controller based on the signed distance method and introduced the asymmetry factor and slope to make the output surface of the single-input fuzzy controller nonlinear. The 5DOF kinematic and dynamic equations of the underactuated AUV were established by neglecting the rolling motion. The simplified nonlinear single-input fuzzy controller has good robustness and solves the problems of complex nonlinear AUV dynamics and unknown environmental disturbances [95]. For dynamic obstacles, Li et al. designed a 3-input fuzzy controller to reduce the influence of obstacle movement speed on the control effect. Compared with the traditional 2-input fuzzy controller, the 3-input fuzzy controller adds the change of the distance between the AUV and the obstacle as an input. The simulation results show that the 3-input controller can better avoid moving obstacles during the AUV navigation, and it is more effective than the commonly used 2-input controller when the obstacle moves fast [96].The fuzzy logic algorithm is often used to solve the local path planning problems of AUV. However, it relies heavily on expert experience and has poor adaptability to the environment. Fuzzy rules are difficult to summarize in complex underwater environments. Once determined, it is difficult to adjust online.(3) Learning Algorithm. Learning algorithm imitates the human learning process and is a new and popular path planning algorithm in recent years. It mainly includes reinforcement learning (RL), deep learning (DL), and deep reinforcement learning (DRL). The learning algorithm enables the AUV to autonomously plan the path according to the environment, which significantly improves the intelligence of path planning.Reinforcement learning is suitable for AUV path planning in a complex and unknown dynamic environment and has a good development prospect. Unlike supervised learning, which learns from training samples, reinforcement learning learns control strategies in the interaction between the system and the environment [97]. In Figure 15(a), AUV selects an action to act on the environment. The state will change after the environment accepts the action, and a reward signal is generated to feed back to AUV. Then, AUV selects the next action according to the reward signal and the current state of the environment. Reinforcement learning enables AUV to have strong self-learning ability and to effectively perform obstacle avoidance and path planning according to the environment. Vibhute proposed an adaptive dynamic programming (ADP) technique based on reinforcement learning and designed an obstacle-free path finder based on ADP to achieve the optimal motion control for AUV. Considering the motion characteristics of AUV, 6DOF kinematic and dynamic models are established. ADP effectively avoided the collision between AUV and static obstacles and realized the optimal path planning of AUV [98].Figure 15
(a) RL framework. (b) DRL framework.
(a)(b)Q-learning algorithm, similar to the dynamic programming algorithm, is one of the commonly used reinforcement learning algorithms in AUV path planning. Gautam and Ramanathan applied the Q-learning algorithm to path planning in the near-bottom ocean environment and established a cost function to describe the dynamics of AUV in near-bottom ocean currents. Q-learning, GA, ACO, and PSO were used to optimize the cost function and search the optimal path. The test results on SLOCUM Glider show that Q-learning has low computational complexity [99]. Considering that the ocean current in littoral regions will have a significant impact on the motion of AUV, Yoo and Kim used the Q-learning algorithm based on temporal difference learning for 2D path planning in complex ocean current disturbances. The 3DOF kinematic model was used to incorporate the nonholonomic motion characteristics of AUV. Constrained by the limited turning speed of the AUV, the action space of AUV was discretized, and the heading angle change was limited. Q-learning was used to determine the action sequence to generate the shortest time path. The simulation results (Figure 16) show that the algorithm can generate a feasible path in flood tidal current or ebb tidal current [100]. On the basis of using the Voronoi diagram to divide the spatial region, Han et al. used the Q-learning algorithm to plan the path of AUV in the subregion and set different reward functions to meet the requirements of the system. The algorithm effectively reduces the energy consumption of AUV [101]. Sarsa (λ) is also a commonly used reinforcement learning algorithm. To reduce the cost of removing sea urchins by AUV, Noguchi and Maki first used APF to make AUV track the seafloor and then used Sarsa (λ) with good convergence to plan a safe path without collision to approach and catch the sea urchins. In the simulation, the AUV successfully found a safe path to capture sea urchins in a complex situation [19].Figure 16
(a) Path planning in flood tide. (b) Path planning in ebb tide [100].
(a)(b)Reinforcement learning does not require prior knowledge, and it is real-time, efficient, and fast when solving AUV path planning problems. However, there are still many problems to be solved, such as convergence speed and equilibrium between exploration and exploitation [102].The search method based on deep learning can directly capture the original sensor input. DRL combines the perception ability of deep learning with the decision-making ability of reinforcement learning, as shown in Figure15(b). It can directly control AUV’s motion based on the input image to solve the path planning problem of AUV [103]. Cao et al. first used sonar imaging to obtain environmental information to establish a grid map of the AUV search area and then adopted the asynchronous advantage actor-critic (A3C) network structure to enable the AUV to learn from its own experience and generate search strategies for various unknown environments. At the same time, DRL and dual-stream Q-learning are applied to AUV obstacle avoidance and navigation to further optimize the search path. The simulation results show that the method can effectively control AUV to explore unknown environments [104]. However, deep reinforcement learning may have disadvantages such as long training time and overfitting to the environment.


## 2.4.1. Swarm Intelligence Algorithms

The basic idea of the swarm intelligence algorithm is to simulate the activities of groups such as birds and ants in the nature. Through the individual cooperation mechanism in the group, information is transmitted to each other, and the optimal solution in the entire group is continuously updated until it converges to the global optimal.(1) Particle Swarm Optimization. The particle swarm optimization (PSO) algorithm is a random search algorithm that simulates the foraging behaviour of birds. The algorithm first initializes a group of random particles with only two properties of speed and position and then calculates each particle’s fitness value through the fitness function. The optimal solution that each particle searches individually is called individual extremum pBest, and the optimal individual extremum in the particle swarm is the current global optimal solution gBest. In each iteration, pBest and gBest are updated according to the fitness value of the particles, and then all particles update their speed and position according to pBest and gBest. PSO algorithm has a memory function, and all particles save their best historical position within themselves and the population. After several iterations, gBest is updated to find the optimal global solution that meets the termination conditions.The concept of the PSO algorithm is similar to the evolutionary algorithm, but the PSO algorithm is affected by individual and social behaviours [50]. PSO algorithm is simple and easy to implement, and it has the advantages of fewer adjustable parameters, high convergence accuracy, and strong global search ability [51]. It is one of the fastest optimization methods to solve the path planning problem and has been widely used in AUV path planning [52–54]. PSO converges faster in the initial search stage and slower in the later search stage and may fall into a locally optimal solution. Therefore, many improvements have been made to this method. Zhuang et al. proposed a hybrid algorithm that integrates PSO with Legendre pseudospectral method (LPM). The PSO-LPM uses PSO to initialize the robustness of random initial values and then switches the search algorithm to LPM to speed up the subsequent search process. The nonlinear 4DOF motion equation of AUV is established by neglecting AUV’s roll and pitch motion. The hybrid PSO-LPM algorithm can converge to the global optimum faster and better [55]. Lin et al. obtained depth information through stereovision detection technology to reconstruct obstacles and established a nonlinear 6DOF mathematical model of AUV. The self-tuning fuzzy control system is used to control the heading and depth of the AUV, and a single objective PSO (SOPSO) dynamic routing algorithm is used to plan the minimum time and energy consumption path. To overcome the local optimization of PSO, SOPSO uses random inertia weights to deal with the dynamic changing environment. In the presence of obstacles and currents, the algorithm can successfully plan a collision-free path for AUV [50].Due to the lack of constraints in the traditional PSO algorithm, an infeasible path may be generated during the update process. Yan et al. combined predictive control with the PSO algorithm (PSO-PC) and introduced two-step prediction into the particle update process. It can detect newer particles and avoid generating infeasible particles. Considering that the ocean current will affect the AUV motion, the algorithm establishes a typical uniform flow model with constant velocity to simulate the nearshore shallow sea environment. The PSO-PC algorithm solves multi-AUV patrol path planning in complex environments [56]. For unknown oceanic environment and irregular obstacles, Yan et al. proposed a real-time path planning algorithm that combines PSO and waypoint guidance (PSO-WG). The algorithm simplifies 6DOF kinematic model to 3DOF model according to the uncontrollable roll motion and the bilateral symmetric structure of AUV. PSO was used to search for suitable temporary waypoints as the current target point to guide the AUV. Besides, the algorithm also considers the turning restraints (including turning radius and angular velocity) of AUV to smooth the path. The comparison with APF and genetic algorithm shows that the algorithm can generate the optimal path [57]. PSO algorithm is an online path planning method, and it can also be applied to the coordinated path planning for unmanned aerial aquatic vehicle (UAAV) and AUV [58].The quantum-behaved particle swarm optimization algorithm (QPSO) is an improved version of PSO. QPSO assumes that each particle in the swarm has a quantum behaviour, instead of using the traditional position and velocity update rules in PSO [39]. Moreover, its overall performance is better than the PSO algorithm. In [39], Zeng et al. proposed a QPSO algorithm based on B-spline curves for path planning in a large environment ranging from tens to hundreds of kilometres. The ocean environment is modelled as a static current field composed of slowly changing eddies and static obstacles. The algorithm is compared with classic A∗, RRT, RRT∗, GA, and PSO algorithms (Figure 9). The simulation results show that QPSO can plan a better path in a short time. Twelve variants of particle swarm intelligence-based path planning algorithms are compared in [51]. They are applied to search for optimal paths in 2D and 3D ocean environments with obstacles and nonuniform currents. The physical motion limitations of AUV, including yaw and pitch motions, are also considered in the search process.Figure 9
A comparison of path planning algorithms in [39]. (a)A∗. (b) RRT. (c)RRT∗. (d) QPSO, PSO, and GA.
(a)(b)(c)(d)To overcome the local optimal limit, Li et al. introduced the adaptive law into QPSO and proposed an adaptive6 quantum-behaved particle swarm optimization algorithm (AQPSO). The Lamb–Oseen vortex was used to simulate the ocean current, and the obstacle avoidance model was established. In AQPSO, the quantum bit amplitude is used to encode the position, and the quantum rotation gate is used to update the particles. The mutation possibility and inertial factor are adaptively changed. The adaptive law and quantum behaviour significantly improve the search efficiency of the PSO algorithm. The algorithm takes the travel time as the fitness function and considers the dynamic constraints to meet the manoeuvrability of AUV. Compared with GA, PSO, and QPSO, AQPSO has better performance in time consumption and path smoothness [59]. Wu et al. proposed a distance evolution nonlinear particle swarm optimization (DENPSO) algorithm to save the energy consumption of AUV path planning. The algorithm has three major improvements. The first is to transform the inertia weight factor and learning factor from linear to nonlinear to ensure that the particles can fully explore the 3D underwater environment in the evolution process; the second is that the distance evolution factor will randomly disturb the particles with poor search range to prevent particles from falling into the local optimal area; the third is to use a penalty function to describe the target of energy optimization under obstacles and the ocean. Besides, DENPSO models the underwater environment, including eddy current field and obstacles. Considering that AUV’s rolling probability in the 3D underwater environment is very small, the 6DOF kinematic model of AUV is simplified. Compared with linear PSO (LPSO), DENPSO has reduced energy consumption by 2.1514e + 03 J in the 3D simulated underwater environment and 1.049e + 07 J in the real underwater environment, respectively [60].(2) Ant Colony Optimization. The ant colony optimization (ACO) algorithm was inspired by the behaviour that ants can find the shortest path to the food source in the foraging. The basic principle is that the positive feedback mechanism will increase the pheromone concentration on the shorter path. The pheromone can attract more ants. Finally, the optimal path will be found between the food source and the nest. ACO algorithm is an excellent probabilistic global optimization algorithm. It has the advantages of distributed computing, positive feedback of information, heuristic search, and easy implementation. Moreover, ACO has good applicability to 2D or 3D path planning. Luan et al. combined ACO with cuckoo search (CS) for AUV path planning. The hybrid optimization does not need manual adjustment, and the parameters are relatively small. The method can effectively shorten the length of the path [61]. Zhang et al. proposed an angle-optimized path planning algorithm based on the ACO algorithm. The algorithm takes angle and path length as optimization targets. The simulation results in dense obstacles environment show that the improved algorithm can reduce the rotation angle of the AUV and the path length, thus saving energy [62].However, the traditional ACO algorithm has some shortcomings, such as slow convergence speed and easy to fall into the local optimal solution. Therefore, the ACO algorithm is often combined with other algorithms (such asA∗ [63] and PSO [64]) to solve the AUV path planning problem better. Che et al. proposed an improved ACO algorithm based on PSO. The algorithm used the improved pheromone update rules and the heuristic function based on the PSO algorithm to find the optimal path for AUV. For complex undersea terrain, the uniform mesh method was used to construct a 3D undersea environment, and the movements of AUV were simplified into forward, transverse, and longitudinal movements. The 3D simulation results (Figure 10) show that the optimal path length is reduced by 17% compared to the traditional ACO algorithm [64]. Yao et al. proposed the bilevel optimization (BIO) scheme. The upper optimization uses ACO to find a collision-free channel composed of connected grids from the starting point to the endpoint. The lower optimization uses QPSO to find the optimal energy path in the channel generated by the upper algorithm. Moreover, the ocean environment was modelled as a strong current field with fixed and moving obstacles. The BIO scheme has high computational efficiency and can generate the time-optimal path of AUV in the obstacle environment [65]. Lin et al. proposed a hybrid quantum ant colony algorithm (hybrid QACO) for AUV’s real-time path planning. The algorithm proposed an adaptive quantum gate and an improved rule of pheromone update based on the motion characteristics of AUV in the process of obstacle avoidance. Besides, it combined the local search method with QACO. A nonlinear fitness function is defined to limit the yaw angle. The simulation results show that the algorithm can improve the path planning quality and obtain a smoother path [66]. Besides, efficient path planning and reasonable task allocation are the basic requirements to ensure improvement in work efficiency of AUV under limited energy.Figure 10
A comparison of path planning algorithms in [64]. (a) Traditional ACO. (b) Improved ACO.
(a)(b)


## 2.4.2. Evolutionary Algorithms

Inspired by the biological evolution in the nature, the evolutionary algorithm is a global optimization algorithm with high robustness and wide adaptability. Genetic algorithm (GA), differential evolution (DE) algorithm, firefly algorithm (FA), and biogeography-based optimization (BBO) algorithm are common evolutionary algorithms that can effectively solve the path planning problem of AUV.(1) Genetic Algorithm. GA is a global optimization algorithm that simulates the natural selection of Darwin’s theory and the biological evolution of genetic mechanisms [35, 67]. GA first generates the initial population by coding and then calculates the fitness of individuals in the population. Then, the selection, crossover, and mutation operations are applied to the population to produce and preserve superior individuals and eliminate inferior individuals. After the genetic operation, the next generation population is obtained. After the continuous evolution of the population from generation to generation, the individual with the maximum fitness finally obtained can be used as the approximate optimal solution of the problem after decoding. This algorithm can search efficiently in a complex ocean environment [68] and rarely falls into the local optimal solution. Similar to the PSO algorithm, GA searches for the optimal solution through random iteration.The genetic algorithm has good robustness and adaptability and strong global search ability. It has a good effect on AUV path planning. Cao et al. used the genetic algorithm to search the globally optimal path of AUV. The algorithm improved the initial population generation method by detecting whether the connection between two adjacent points passed through obstacles and introduced a chamfer operator based on the traditional genetic operator to smooth the angle. The simulation results show that the algorithm accelerates the convergence speed while converging to the optimal solution [69]. However, the improved genetic algorithm uses a 2D plane figure to represent AUV’s working space and does not consider the motion characteristics of AUV and the 3D underwater environment. Ataei and Yousefi-Koma evaluated the optimal path of AUV based on the criteria of total length of path, margin of safety, smoothness of the planar motion, and gradient of diving and then used the nondominated sorting genetic algorithm (NSGA-II) to perform multiobjective optimization of the above four objectives. The 4DOF kinematic and dynamic models of AUV were established by neglecting roll and pitch motions. NSGA-II found the multicriteria optimal path for AUV in the 3D environment with static obstacles [70].The energy problem must be considered in AUV path planning, which is related to whether the AUV can reach the destination. Tanakitkorn et al. improved the cost function of GA to minimize the energy consumption of AUV during navigation. The improved cost function consists of energy consumption terms estimated from the dynamics of Delphin 2 AUV. Since the AUV is assumed to travel at a constant depth, only the surge, sway, and yaw motions of the AUV are considered. The improved GA algorithm effectively reduces AUV’s energy consumption in a 2D static environment, such as Heronry South Lake, labyrinth with many concave-shaped obstacles, and split ellipse [6]. Tsiogkas et al. applied the genetic algorithm to the AUV path planning under energy constraints and compared it with the optimal mixed-integer quadratic programming (MIQP). The genetic algorithm’s time efficiency is at least three times that of the optimal MIQP algorithm [71]. The ocean current has a great influence on the energy consumption of AUV in the complex and changeable ocean environment. Pan et al. proposed a genetic-ant hybrid algorithm to solve the path planning problem in the current environment. The hybrid algorithm establishes an ocean current model with grids based on B-spline function and redefines a new fusion strategy to improve the integration efficiency. The hybrid algorithm has a fast search speed, which effectively reduces the energy consumption of AUV [68]. To obtain the energy-optimal path, Yao et al. proposed an improved genetic algorithm (IGA). The grey wolf optimizer was used to modify the mutation operator so that the mutation always changed towards the optimal solution, which effectively improved the effectiveness of the mutation and enriched the diversity of the population. Compared with the path planned by GA, the path planned by IGA is not the shortest path (Figure 11), but this path saves energy by using ocean current [72].Figure 11
Comparison of the optimal paths between IGA and GA [72].The genetic algorithm has some shortcomings, such as early maturity, poor stability, and slow convergence speed. However, it is easy to combine with other algorithms and can give full play to its advantages in the iterative process. The genetic algorithm starts searching from a cluster rather than a single solution, which is conducive to global optimization. Moreover, the algorithm simultaneously processes multiple individuals in the population, that is, it evaluates multiple solutions in the search space. Therefore, the risk of falling into a locally optimal solution is reduced.(2) Differential Evolution. The principle of DE is similar to the genetic algorithm, and it also includes crossover, mutation, and selection operations. However, in the DE algorithm, the mutation operation uses differential mutation, and the selection operation uses a one-to-one elimination mechanism to update the population. In this way, the complexity of the genetic operation is reduced. DE is an effective technique for solving complex optimization problems, and it is also suitable for solving the path planning problem of AUV [73–75]. Zadeh et al. designed a path planner based on the DE algorithm. The planner considers AUV kinematics and ocean dynamics for path planning and models the operating terrain to simulate real underwater environments. The terrain includes offline map, static/dynamic time-varying ocean currents, and different moving and static uncertain obstacles. The simulation results show that the method has strong robustness and can effectively deal with ocean currents and obstacles [73]. DE algorithm can be combined with other algorithms to solve the AUV task assignment and path planning problems. Zadeh et al. used a specific combination of differential evolution and firefly optimization (DEFO) algorithms to simulate the synchronous process of task assignment and path planning. The simulation results in a large environment indicated that the algorithm could effectively reduce the energy consumed by path planning while completing the maximum number of assigned tasks [74]. Yu et al. combined DE with ACO for path planning of multiple AUV systems, and the hybrid algorithm achieved good results [75]. DE has strong global convergence ability and robustness, and its unique memory ability enables it to dynamically track the current search situation to adjust its search strategy.(3) Firefly Algorithm and Biogeography-Based Optimization. FA is a heuristic algorithm inspired by the flickering behaviour of fireflies. One firefly will be attracted by a brighter one to adjust its position. The position of fireflies represents the solution of the optimization problem. The traditional FA algorithm has some shortcomings in convergence speed and stability. Gu et al. proposed an improved FA algorithm that adjusts the length of random steps and parameters of the algorithm based on the distance between two fireflies and the iteration time. The excluding operator and contracting operator were used to improve the effect of obstacle avoidance, convergence speed, and path smoothness. The simulation results show that the algorithm can generate a feasible path with fast convergence speed in the 3D environment [76]. BBO is an evolutionary algorithm that simulates the equilibrium theory of island biogeography concept and is also suitable for AUV path planning [52]. MahmoudZadeh et al. developed a motion planner based on the BBO algorithm to deal with path planning in a real environment. Firstly, a real undersea environment model is built based on an offline map, which includes static and uncertain obstacles, current, and floating and moving objects. Then, the 6DOF kinematic model of AUV is established. Finally, the motion planner can quickly regenerate the optimal path of AUV by controlling the motion of AUV according to the underwater environment’s unexpected changes [77]. MahmoudZadeh et al. used PSO, DE, BBO, and FA to perform online path planning for AUV rendezvous and analysed the performance of the four. The comparison results (Figure 12) in different scenarios show that FA can effectively use the current to avoid obstacles and generate the optimal path in the spatiotemporal ocean flows, while DE has better performance in time optimality [78].Figure 12
Comparison of PSO, DE, FA, and BBO [78].


## 2.4.3. Human-Inspired Algorithms

Human-inspired algorithms are inspired by human thought or social behaviour, including artificial neural network (ANN) algorithms, fuzzy logic (FL) algorithms, and learning algorithms (LAs).(1) Artificial Neural Network. ANN is a mathematical model that simulates the behaviour of animal or human neural networks and processes information in a distributed and parallel way. It has high intelligence; however, most ANNs have the disadvantages of long learning time, poor generalization ability, and slow processing speed. Moreover, it is difficult to ensure the real-time performance of path planning. Complex and changeable environments or obstacles are difficult to describe with mathematical formulas. However, neural network algorithms are still widely used in the AUV path planning due to their strong learning ability, adaptive ability, strong robustness, and high parallelism.In most cases, the working environment of AUV is unknown. To deal with AUV path planning in an unknown environment, Zhu et al. proposed a multi-AUV hunting algorithm based on a bioinspired neural network (BNN). On the basis of using the discrete grid map to represent the underwater environment, each neuron in the neural network corresponds to a grid cell in the grid map (Figure13), and then the moving path of the AUV is generated according to the activities of the neural network. BNN can quickly and efficiently plan a feasible path in the unknown environment with static obstacles of different shapes, including U shape, polygon shape, square shape, and rectangle shape [79]. Wu et al. added the lateral inhibition of obstacles to the neural network to solve the problem of AUV moving along the edges of obstacles and improve the safety and rationality of path planning [81]. However, the BNN algorithm does not consider ocean currents and 3D dynamic environments. There are some difficulties when BNN is applied to 3D path planning, such as complex calculation in a large environment and repeated path when the obstacle size is larger than the detection range of the sensor.Figure 13
(a) 2D BNN model [79]. (b) 3D BNN model [80].
(a)(b)Cao et al. extended BNN to the 3D underwater environment for multi-AUV target search and constructed a topologically organized bioinspired neurodynamic model based on the grid map to represent the dynamic environment. Each AUV searches the path according to the steepest gradient descent rule. The algorithm performs well in 3D underwater environments with static obstacles of different sizes and shapes [82]. Ni et al. improved the BNN by improving the shunting equation of the neural network model [83] and adding virtual target and target attractor [80] to adapt to the dynamic environment and improve the efficiency and real-time path planning. In [80], an improved dynamic BNN model that regards AUV as the core is proposed. The model will be reconstructed with the movement of AUV, and its radius depends on the detection range of the sensor. The simulation results show that the improved model can effectively solve the real-time path planning problems in different 3D unknown environments, including underwater environments with static and dynamic obstacles and special seabed environments such as underwater mountains, deep underwater valleys, and underwater caves. However, it does not take into account the effects of ocean currents on AUV path planning. To solve this problem, Cao and Zhu combined the BNN and velocity synthesis algorithm to optimize the path of AUV in a dynamic environment with ocean current [84]. BNN can also be combined with the self-organizing map (SOM) neural network to solve the task assignment and path planning of the multi-AUV system [85].The BNN algorithm does not correctly establish the cooperation mechanism between AUVs, which sometimes causes collisions between AUVs. Moreover, it has high computational complexity, low work efficiency, and long path planning time. In response to these shortcomings, Zhu et al. proposed the Glasius bioinspired neural network (GBNN) algorithm and applied it to multi-AUV complete coverage path planning [2, 7, 86]. The algorithm updates each AUV’s neural network activity according to the state of the grid map and the location of other AUVs. GBNN algorithm can improve planning efficiency and effectively reduce path planning time [86]. In the GBNN algorithm, all AUVs share working environment information, and each AUV treats other AUVs as moving obstacles, thus avoiding collisions and repeated search paths between multiple AUVs [87].(2) Fuzzy Logic. Fuzzy logic imitates the uncertainty judgment and reasoning thinking mode of the human brain and makes inference judgments for unknown systems based on environmental information and fuzzy rules to solve the problem of path planning [88, 89]. The algorithm takes the sensors' real-time measurement information as the input and generates the control information based on the experts' experience and knowledge as the output for AUV real-time path planning.Fuzzy logic does not need an accurate environment model and too complicated mathematical calculation and has achieved good results in AUV’s collision avoidance control and path planning [90]. Due to the complexity of the 3D fuzzy design, the fuzzy logic algorithm is generally used for 2D path planning. This problem can be solved by mapping the 3D environment into horizontal plane and vertical plane [91]. Based on the forward-looking sonar model, Sun et al. obtained the virtual acceleration and velocity of AUV in the horizontal and vertical plane through the fuzzy system and then used the velocity synthesis method to generate the real control variables. They developed a fuzzy inference system with an accelerate/break (A/B) module for real-time navigation and simplified the AUV’s motion into 4DOF (including surge, heave, pitch, and yaw) according to the thruster arrangement of AUV. The simulation results verify the effectiveness and feasibility of the method for path planning and obstacle avoidance in static or dynamic environments [92]. On this basis, using PSO or QPSO to optimize the membership function value in fuzzy logic rules can generate the optimal 3D path in complex underwater environments, as shown in Figure 14. In Figure 14(d), the QPSO fuzzy method converges faster and performs better [91, 92]. Zhou et al. used the fuzzy comprehensive evaluation (FCE) method based on the fuzzy logic decision to select the best route from the solution produced by the multiobjective particle swarm optimization (MOPSO) algorithm. The FCE method increased the sampling efficiency, reduced power consumption, and better completed the path planning mission in the spatiotemporal ocean environment [93]. Peng et al. proposed a fuzzy logic LOS guidance/control method to solve the uncertainties in the operating environment, which can adjust adaptively the navigation coefficient and improve the accuracy of path planning [94].Figure 14
A comparison of path planning algorithms in [91]. (a) 3D dynamic fuzzy path planning without optimization. (b) 3D dynamic PSO-fuzzy path planning. (c) 3D dynamic QPSO-fuzzy path planning. (d) Performance comparison of path planning.
(a)(b)(c)(d)The traditional 2-input fuzzy controller takes the distance and direction angle of the obstacle relative to the AUV as input. To reduce the computational complexity of the 2-input fuzzy controller, Yu et al. simplified it to a single-input fuzzy controller based on the signed distance method and introduced the asymmetry factor and slope to make the output surface of the single-input fuzzy controller nonlinear. The 5DOF kinematic and dynamic equations of the underactuated AUV were established by neglecting the rolling motion. The simplified nonlinear single-input fuzzy controller has good robustness and solves the problems of complex nonlinear AUV dynamics and unknown environmental disturbances [95]. For dynamic obstacles, Li et al. designed a 3-input fuzzy controller to reduce the influence of obstacle movement speed on the control effect. Compared with the traditional 2-input fuzzy controller, the 3-input fuzzy controller adds the change of the distance between the AUV and the obstacle as an input. The simulation results show that the 3-input controller can better avoid moving obstacles during the AUV navigation, and it is more effective than the commonly used 2-input controller when the obstacle moves fast [96].The fuzzy logic algorithm is often used to solve the local path planning problems of AUV. However, it relies heavily on expert experience and has poor adaptability to the environment. Fuzzy rules are difficult to summarize in complex underwater environments. Once determined, it is difficult to adjust online.(3) Learning Algorithm. Learning algorithm imitates the human learning process and is a new and popular path planning algorithm in recent years. It mainly includes reinforcement learning (RL), deep learning (DL), and deep reinforcement learning (DRL). The learning algorithm enables the AUV to autonomously plan the path according to the environment, which significantly improves the intelligence of path planning.Reinforcement learning is suitable for AUV path planning in a complex and unknown dynamic environment and has a good development prospect. Unlike supervised learning, which learns from training samples, reinforcement learning learns control strategies in the interaction between the system and the environment [97]. In Figure 15(a), AUV selects an action to act on the environment. The state will change after the environment accepts the action, and a reward signal is generated to feed back to AUV. Then, AUV selects the next action according to the reward signal and the current state of the environment. Reinforcement learning enables AUV to have strong self-learning ability and to effectively perform obstacle avoidance and path planning according to the environment. Vibhute proposed an adaptive dynamic programming (ADP) technique based on reinforcement learning and designed an obstacle-free path finder based on ADP to achieve the optimal motion control for AUV. Considering the motion characteristics of AUV, 6DOF kinematic and dynamic models are established. ADP effectively avoided the collision between AUV and static obstacles and realized the optimal path planning of AUV [98].Figure 15
(a) RL framework. (b) DRL framework.
(a)(b)Q-learning algorithm, similar to the dynamic programming algorithm, is one of the commonly used reinforcement learning algorithms in AUV path planning. Gautam and Ramanathan applied the Q-learning algorithm to path planning in the near-bottom ocean environment and established a cost function to describe the dynamics of AUV in near-bottom ocean currents. Q-learning, GA, ACO, and PSO were used to optimize the cost function and search the optimal path. The test results on SLOCUM Glider show that Q-learning has low computational complexity [99]. Considering that the ocean current in littoral regions will have a significant impact on the motion of AUV, Yoo and Kim used the Q-learning algorithm based on temporal difference learning for 2D path planning in complex ocean current disturbances. The 3DOF kinematic model was used to incorporate the nonholonomic motion characteristics of AUV. Constrained by the limited turning speed of the AUV, the action space of AUV was discretized, and the heading angle change was limited. Q-learning was used to determine the action sequence to generate the shortest time path. The simulation results (Figure 16) show that the algorithm can generate a feasible path in flood tidal current or ebb tidal current [100]. On the basis of using the Voronoi diagram to divide the spatial region, Han et al. used the Q-learning algorithm to plan the path of AUV in the subregion and set different reward functions to meet the requirements of the system. The algorithm effectively reduces the energy consumption of AUV [101]. Sarsa (λ) is also a commonly used reinforcement learning algorithm. To reduce the cost of removing sea urchins by AUV, Noguchi and Maki first used APF to make AUV track the seafloor and then used Sarsa (λ) with good convergence to plan a safe path without collision to approach and catch the sea urchins. In the simulation, the AUV successfully found a safe path to capture sea urchins in a complex situation [19].Figure 16
(a) Path planning in flood tide. (b) Path planning in ebb tide [100].
(a)(b)Reinforcement learning does not require prior knowledge, and it is real-time, efficient, and fast when solving AUV path planning problems. However, there are still many problems to be solved, such as convergence speed and equilibrium between exploration and exploitation [102].The search method based on deep learning can directly capture the original sensor input. DRL combines the perception ability of deep learning with the decision-making ability of reinforcement learning, as shown in Figure15(b). It can directly control AUV’s motion based on the input image to solve the path planning problem of AUV [103]. Cao et al. first used sonar imaging to obtain environmental information to establish a grid map of the AUV search area and then adopted the asynchronous advantage actor-critic (A3C) network structure to enable the AUV to learn from its own experience and generate search strategies for various unknown environments. At the same time, DRL and dual-stream Q-learning are applied to AUV obstacle avoidance and navigation to further optimize the search path. The simulation results show that the method can effectively control AUV to explore unknown environments [104]. However, deep reinforcement learning may have disadvantages such as long training time and overfitting to the environment.


## 3. Motion Constraints in AUV Path Planning

Underwater vehicles mainly include remotely operated vehicles (ROVs), underwater gliders, and AUVs. ROV is restricted by the cable, and its movement is completed by human teleoperation. An underwater glider can sometimes be used as AUV, but it depends on the external environment and has poor manoeuvrability. AUV has strong manoeuvrability and can autonomously perform the corresponding movement according to the task or environment, effectively reducing the dependence on humans and the environment.The ultimate goal of the path planning algorithm is to generate a feasible path for AUV. If the path does not meet the motion constraints of AUV, the AUV may not be able to travel along this path, resulting in deviation and even damage to the AUV. In principle, the path planned by the path planning algorithm must meet the motion constraints of AUV. However, it is very difficult. To improve the computational efficiency, most existing path planning algorithms often ignore the motion constraints of AUV. Although it will increase the computational complexity of path planning algorithms, the motion characteristics should be considered in AUV path planning. It can make the generated path meet the motion constraints of AUV and increase the practicability of the path. In this section, we give a brief introduction to the motion constraints of AUV.


### 3.1. Kinematic and Dynamic Constraints

AUV is a rigid body. Generally speaking, the motion of AUV in 3D space is six degrees of freedom: surge, roll, sway, pitch, heave, and yaw. That is to say, AUV has rotation and translation velocity components in each dimension [90]. The earth-fixed coordinate system and the body-fixed coordinate system are used to describe the motion of AUV in the underwater environment, as shown in Figure 17. Table 3 shows the parameters of AUV with six degrees of freedom.Figure 17
Earth-fixed coordinate system and body-fixed coordinate system.Table 3
The parameters of AUV with 6DOF.
DOFDescriptionPosition and Euler anglesForces and momentsLinear and angular velocities1SurgexXu2SwayyYv3HeavezZw4RollϕKp5PitchθMq6YawψNrThe kinematic model deals with the geometric aspects of motion and does not consider the influence of force and mass factors. The general form of AUV’s 6DOF kinematic model is as follows:(1)η˙=Jηv,where η=x,y,z,ϕ,θ,ψΤ is the position and orientation vector of AUV with respect to the earth-fixed coordinate system; v=u,v,w,p,q,rΤ is the linear and angular velocities vector in the body-fixed coordinate system; and Jη is the Jacobian transformation matrix.The dynamic model describes the relationship between the force acting on the AUV and motion and relates the force and moment to AUV’s position and speed. The general form of AUV’s 6DOF dynamic model is as follows:(2)Mv˙+Cvv+Dvv+gη=τ,where M is the inertia matrix (including added mass); Cv is the Coriolis-centripetal matrix (including added mass); Dv is the hydrodynamic damping and lift matrix; gη represents the gravitational forces and moments (hydrostatic); and τ=X,Y,Z,K,M,NΤ is the vector of external forces and moments. The body structure of AUV will affect the dynamics because AUV will interact with the surrounding water in the process of motion to produce drag and lift forces [105].In practical application, the motion of AUV will be simplified according to the dimension or requirement of path planning. In addition to the 6DOF motion model, three other common simplified models are introduced below.


#### 3.1.1. Model 1: 5DOF

Remark 1.
The roll motion of AUV is ignored. In general, the probability of AUV rolling in a 3D underwater environment is small, so the roll motion of AUV can be ignored, that is,ϕ=p=0. At this time, η=x,y,z,θ,ψΤ and v=u,v,w,q,rΤ. The 5DOF model is usually used in 3D path planning.


#### 3.1.2. Model 2: 4DOF

Remark 2.
The roll and pitch motions of AUV are ignored, that is,ϕ=p=0 and θ=q=0. At this time, η=x,y,z,ψΤ and v=u,v,w,rΤ. The 4DOF model is usually used in 3D path planning. References [91, 92] are another case, which ignores the sway and roll motion of the AUV.


#### 3.1.3. Model 3: 3DOF

Remark 3.
The roll, pitch, and heave motions of AUV are ignored, that is,ϕ=p=0, θ=q=0, and z=w=0. At this time, η=x,y,ψΤ and v=u,v,rΤ. The 3DOF model is usually used in 2D path planning.
The kinematics and dynamics of AUV are described above. As we all know, the increase of state dimension will significantly increase the calculation of path planning. The computational efficiency of the path planning algorithm can be improved by using the motion model with a low state dimension. Since the change in the water depth of AUV is relatively small, people mainly focus on the movement of AUV in the horizontal plane and use the plane motion model for 2D path planning. However, when it comes to the precise path planning in local or small-scale environments, it is necessary to use the motion model with a high degree of freedom for 3D path planning.
Accurate kinematic and dynamic models are essential for AUV path planning, which also affects navigation and control. However, it is really difficult to obtain these models, especially the dynamic model. How to conduct successful and effective path planning with inaccurate kinematic and dynamic models will be a future research point.


### 3.2. Turning Constraints

The movement of AUV is restricted by the vehicle’s inherent turning constraints, such as turning rate and turning radius [44, 100, 106]. They are closely related and represent the turning ability of AUV. Theoretically, the turning constraints of AUV should be considered in path planning. If not, AUV may not follow the planned path and may even collide [29]. References [41, 51, 57] considered the turning angle of AUV to plan a smooth path.


### 3.3. Other Constraints

Sometimes, the depth limitation is also considered in AUV path planning [36, 107]. It can avoid the AUV getting stranded when sailing in shallow water or along the coastline.It is vital to generate a feasible path that considers the motion characteristics of AUV. In this way, AUV can track this path to the target point smoothly. Therefore, motion constraints should be reasonably introduced in AUV path planning according to AUV's body structure, underwater environment, and task requirements.


## 3.1. Kinematic and Dynamic Constraints

AUV is a rigid body. Generally speaking, the motion of AUV in 3D space is six degrees of freedom: surge, roll, sway, pitch, heave, and yaw. That is to say, AUV has rotation and translation velocity components in each dimension [90]. The earth-fixed coordinate system and the body-fixed coordinate system are used to describe the motion of AUV in the underwater environment, as shown in Figure 17. Table 3 shows the parameters of AUV with six degrees of freedom.Figure 17
Earth-fixed coordinate system and body-fixed coordinate system.Table 3
The parameters of AUV with 6DOF.
DOFDescriptionPosition and Euler anglesForces and momentsLinear and angular velocities1SurgexXu2SwayyYv3HeavezZw4RollϕKp5PitchθMq6YawψNrThe kinematic model deals with the geometric aspects of motion and does not consider the influence of force and mass factors. The general form of AUV’s 6DOF kinematic model is as follows:(1)η˙=Jηv,where η=x,y,z,ϕ,θ,ψΤ is the position and orientation vector of AUV with respect to the earth-fixed coordinate system; v=u,v,w,p,q,rΤ is the linear and angular velocities vector in the body-fixed coordinate system; and Jη is the Jacobian transformation matrix.The dynamic model describes the relationship between the force acting on the AUV and motion and relates the force and moment to AUV’s position and speed. The general form of AUV’s 6DOF dynamic model is as follows:(2)Mv˙+Cvv+Dvv+gη=τ,where M is the inertia matrix (including added mass); Cv is the Coriolis-centripetal matrix (including added mass); Dv is the hydrodynamic damping and lift matrix; gη represents the gravitational forces and moments (hydrostatic); and τ=X,Y,Z,K,M,NΤ is the vector of external forces and moments. The body structure of AUV will affect the dynamics because AUV will interact with the surrounding water in the process of motion to produce drag and lift forces [105].In practical application, the motion of AUV will be simplified according to the dimension or requirement of path planning. In addition to the 6DOF motion model, three other common simplified models are introduced below.


### 3.1.1. Model 1: 5DOF

Remark 1.
The roll motion of AUV is ignored. In general, the probability of AUV rolling in a 3D underwater environment is small, so the roll motion of AUV can be ignored, that is,ϕ=p=0. At this time, η=x,y,z,θ,ψΤ and v=u,v,w,q,rΤ. The 5DOF model is usually used in 3D path planning.


### 3.1.2. Model 2: 4DOF

Remark 2.
The roll and pitch motions of AUV are ignored, that is,ϕ=p=0 and θ=q=0. At this time, η=x,y,z,ψΤ and v=u,v,w,rΤ. The 4DOF model is usually used in 3D path planning. References [91, 92] are another case, which ignores the sway and roll motion of the AUV.


### 3.1.3. Model 3: 3DOF

Remark 3.
The roll, pitch, and heave motions of AUV are ignored, that is,ϕ=p=0, θ=q=0, and z=w=0. At this time, η=x,y,ψΤ and v=u,v,rΤ. The 3DOF model is usually used in 2D path planning.
The kinematics and dynamics of AUV are described above. As we all know, the increase of state dimension will significantly increase the calculation of path planning. The computational efficiency of the path planning algorithm can be improved by using the motion model with a low state dimension. Since the change in the water depth of AUV is relatively small, people mainly focus on the movement of AUV in the horizontal plane and use the plane motion model for 2D path planning. However, when it comes to the precise path planning in local or small-scale environments, it is necessary to use the motion model with a high degree of freedom for 3D path planning.
Accurate kinematic and dynamic models are essential for AUV path planning, which also affects navigation and control. However, it is really difficult to obtain these models, especially the dynamic model. How to conduct successful and effective path planning with inaccurate kinematic and dynamic models will be a future research point.


## 3.1.1. Model 1: 5DOF

Remark 1.
The roll motion of AUV is ignored. In general, the probability of AUV rolling in a 3D underwater environment is small, so the roll motion of AUV can be ignored, that is,ϕ=p=0. At this time, η=x,y,z,θ,ψΤ and v=u,v,w,q,rΤ. The 5DOF model is usually used in 3D path planning.


## 3.1.2. Model 2: 4DOF

Remark 2.
The roll and pitch motions of AUV are ignored, that is,ϕ=p=0 and θ=q=0. At this time, η=x,y,z,ψΤ and v=u,v,w,rΤ. The 4DOF model is usually used in 3D path planning. References [91, 92] are another case, which ignores the sway and roll motion of the AUV.


## 3.1.3. Model 3: 3DOF

Remark 3.
The roll, pitch, and heave motions of AUV are ignored, that is,ϕ=p=0, θ=q=0, and z=w=0. At this time, η=x,y,ψΤ and v=u,v,rΤ. The 3DOF model is usually used in 2D path planning.
The kinematics and dynamics of AUV are described above. As we all know, the increase of state dimension will significantly increase the calculation of path planning. The computational efficiency of the path planning algorithm can be improved by using the motion model with a low state dimension. Since the change in the water depth of AUV is relatively small, people mainly focus on the movement of AUV in the horizontal plane and use the plane motion model for 2D path planning. However, when it comes to the precise path planning in local or small-scale environments, it is necessary to use the motion model with a high degree of freedom for 3D path planning.
Accurate kinematic and dynamic models are essential for AUV path planning, which also affects navigation and control. However, it is really difficult to obtain these models, especially the dynamic model. How to conduct successful and effective path planning with inaccurate kinematic and dynamic models will be a future research point.


## 3.2. Turning Constraints

The movement of AUV is restricted by the vehicle’s inherent turning constraints, such as turning rate and turning radius [44, 100, 106]. They are closely related and represent the turning ability of AUV. Theoretically, the turning constraints of AUV should be considered in path planning. If not, AUV may not follow the planned path and may even collide [29]. References [41, 51, 57] considered the turning angle of AUV to plan a smooth path.


## 3.3. Other Constraints

Sometimes, the depth limitation is also considered in AUV path planning [36, 107]. It can avoid the AUV getting stranded when sailing in shallow water or along the coastline.It is vital to generate a feasible path that considers the motion characteristics of AUV. In this way, AUV can track this path to the target point smoothly. Therefore, motion constraints should be reasonably introduced in AUV path planning according to AUV's body structure, underwater environment, and task requirements.


## 4. The Development Direction of AUV Path Planning Algorithm

AUV will develop in the direction of intelligence, remoteness, and collectivization. Moreover, the external environment faced by AUV will be more complex and changeable. The requirements for AUV path planning technology will be higher and higher. The development of the path planning algorithm has been relatively mature, and it is difficult to study a new algorithm. There are some problems in the development of AUV path planning algorithms:(1)
Some algorithms have inherent drawbacks.(2)
Some algorithms have low planning efficiency or intelligence.(3)
There are few path planning algorithms suitable for the multi-AUV system.(4)
How to apply the algorithm to the 3D underwater environment.(5)
Some algorithms do not consider complex environments (such as special obstacles and time-varying ocean currents).(6)
Some algorithms do not consider multiobjective constraints and practicality.To solve the above problems, the AUV path planning algorithm will continue to develop in the following directions. Figure18 summarizes the general development of AUV path planning algorithms from 2015 to 2020.Figure 18
Development of AUV path planning algorithm.


### 4.1. Direction A: Improvement of Existing Path Planning Algorithms

Any algorithm has its limitations in practical applications. By improving the existing path planning algorithm, we can overcome some shortcomings of the algorithm itself and improve the performance of the algorithm. In 2017, Zhang et al. improved the three intelligent behaviours of scouting, summoning, and besieging of the wolf pack algorithm, effectively improving the convergence speed and local search ability of the algorithm [106]. In 2019, Ma et al. proposed an ant colony algorithm combining alarm pheromone. Ants trapped in the infeasible area will release the alarm pheromone to avoid other ants entering the area, thus reducing the invalid search and improving the search efficiency [108]. In 2020, Zeng et al. proposed a QPSO path planner combined with the current prediction. This planner can maximize the use of favourable currents to generate an optimal path in a spatiotemporal changing marine environment [109]. The improvement of the existing algorithm will be a significant development direction of the AUV path planning algorithm.


### 4.2. Direction B: Fusion of Multiple Path Planning Algorithms

A single path planning algorithm cannot solve all the problems encountered by AUV in practical applications. The fusion of multiple algorithms can improve AUV path planning efficiency and point out a new direction for path planning. Various algorithms should learn from each other to jointly complete the path planning task of AUV. Considering the influence of ocean current on AUV path planning, the velocity synthesis algorithm can be combined with some path planning algorithms, such as APF [17, 110] and BNN [84]. In 2018, Yao and Zhao used the grey wolf optimization algorithm to modify the mutation operator in the genetic algorithm to make the mutation change to the optimal solution direction [72]; given the fact that traditional ACO algorithm is easy to fall into local optimal, Che et al. designed a heuristic function based on the PSO algorithm to improve the global search efficiency [64]. In 2019, Lim et al. used selectively differential evolution-hybridized quantum PSO (SDEQPSO) for constrained path planning. The algorithm can generate a smooth and feasible path under hard constraints of boundary conditions and soft constraints of obstacle avoidance [111]. In 2020, Wang et al. combined PSO with cubic spline interpolation to achieve obstacle avoidance and path optimization. The planned path curvature is continuous and can meet the constraint of the minimum rotation radius of AUV [112].


### 4.3. Direction C: Intelligent Path Planning Algorithms

With the rapid development of computer intelligence technology, especially machine learning, using machine learning to solve AUV’s path planning is one of the current trends. Through learning and training, the AUV has self-learning ability. It can improve the AUV’s intelligence level and realize the path planning of the AUV in complex and unknown environments. In recent years, RL methods (such as Q-learning [99, 100] and Sarsa [19]) or deep reinforcement learning methods [104] have achieved excellent results in AUV path planning. In 2018, Cao et al. used reinforcement learning and Gaussian process regression to solve the path planning with bathymetric aids and modelled the value function as a Gaussian process to minimize the location uncertainty when the AUV reaches the target point [113]. In 2020, Sun et al. used the hierarchical deep Q network in 3D path planning. The algorithm divided the task of path planning into three layers to solve the problem of dimension disaster and modified the reward function according to the different requirements of the task [114]. However, there is relatively little research in this area. Therefore, intelligent path planning algorithms still need to be developed.


### 4.4. Direction D: Multi-AUV Cooperative Path Planning Algorithms

As the tasks undertaken by AUV become increasingly complex and single AUV has some problems such as limited energy resources, multi-AUV parallel collaborations have become an important way to solve such problems. In multi-AUV path planning, safety is essential for each AUV. In the GBNN algorithm [7, 86], each AUV regards other AUVs as moving obstacles, thus avoiding collision between multiple AUVs. In 2019, Liang et al. proposed an improved APF method with a ring-shaped repulsion field, which can ensure that multiple AUVs can smoothly bypass obstacles at a safe distance [22]; based on assigning tasks to multi-AUV systems, Chen et al. combined the restricted velocity synthesis method and the belief function method to guide each AUV to reach the target safely. The restricted velocity synthesis method is used to overcome the influence of ocean currents, and the belief function method is used to avoid obstacles [115]. In 2020, Panda et al. applied the grey wolf optimization (GWO) algorithm to the path planning of the multi-AUV system and compared it with the genetic algorithm. GWO algorithm can make AUV reach the goal in a shorter time, thus reducing the path cost [116]; Xiong et al. proposed an elite group-based evolutionary algorithm (EGEA) for multi-AUV path planning [117]. It will be the most important research in the future to design an algorithm to realize the collision-free cooperative path planning of multi-AUV.


### 4.5. Direction E: 3D Path Planning Algorithms

The 3D path planning algorithm has some problems, such as difficult environment modelling and complicated calculation. However, it is very suitable for real underwater environments and can meet AUV’s actual work requirements. Now, an increasing number of algorithms are applied to the 3D path planning of AUV. In 2015, Yu et al. proposed a hybrid search fast marching (HSFM) method to generate a three-dimensional smooth path from the discrete representation of the underwater environment [118]. In 2018, Sun et al. established a three-dimensional Glasius bionic neural network model to represent the three-dimensional underwater working environment, which independently planned the path according to the activity of neurons [119]. In 2019, Liu et al. proposed a learning fixed-height histogram (LFHH) method based on the estimation of distribution algorithm to solve the path planning in the 3D environment with current and moving obstacles [120]. Sometimes, the 3D underwater environment can be mapped to the horizontal plane and vertical plane to solve 3D path planning. In the future, the 3D path planning algorithm will become the mainstream method.In addition, we think that the future research directions of AUV path planning algorithms should focus on the following aspects:(1)
Time-Varying Ocean Current. Most of the existing path planning algorithms in ocean current environments are for steady currents with constant size and direction and do not consider the influence of time-varying ocean currents. When AUV is in the time-varying current environment, the path planning algorithm should be able to deal with the time-varying current effectively.(2)
Special Obstacles. Most of the existing path planning algorithms treat obstacles as regular graphics and are suitable for simple environments. AUV path planning algorithms for special obstacle environments (such as irregular obstacles, flexible obstacles, and dense obstacles) are very few and should be focused on.(3)
Multiobjective Constraint. As the tasks undertaken by AUV become more complex, the path planning algorithms cannot simply take the path length or navigation time as a single optimization goal, and the evaluation of path quality should start from many aspects, such as energy consumption, smoothness, safety, feasibility, and so on. The path planning algorithm under multiobjective constraints can effectively improve the path quality.(4)
Practicability. Most of the existing path planning algorithms are verified by simulation, but the practicability of the algorithm has not been verified by experiments. If the algorithm cannot be applied to the actual underwater environment, the significance or value of the algorithm will be greatly reduced. Therefore, the practicability of the algorithm should be improved in the design and verified by the actual underwater experiment.


## 4.1. Direction A: Improvement of Existing Path Planning Algorithms

Any algorithm has its limitations in practical applications. By improving the existing path planning algorithm, we can overcome some shortcomings of the algorithm itself and improve the performance of the algorithm. In 2017, Zhang et al. improved the three intelligent behaviours of scouting, summoning, and besieging of the wolf pack algorithm, effectively improving the convergence speed and local search ability of the algorithm [106]. In 2019, Ma et al. proposed an ant colony algorithm combining alarm pheromone. Ants trapped in the infeasible area will release the alarm pheromone to avoid other ants entering the area, thus reducing the invalid search and improving the search efficiency [108]. In 2020, Zeng et al. proposed a QPSO path planner combined with the current prediction. This planner can maximize the use of favourable currents to generate an optimal path in a spatiotemporal changing marine environment [109]. The improvement of the existing algorithm will be a significant development direction of the AUV path planning algorithm.


## 4.2. Direction B: Fusion of Multiple Path Planning Algorithms

A single path planning algorithm cannot solve all the problems encountered by AUV in practical applications. The fusion of multiple algorithms can improve AUV path planning efficiency and point out a new direction for path planning. Various algorithms should learn from each other to jointly complete the path planning task of AUV. Considering the influence of ocean current on AUV path planning, the velocity synthesis algorithm can be combined with some path planning algorithms, such as APF [17, 110] and BNN [84]. In 2018, Yao and Zhao used the grey wolf optimization algorithm to modify the mutation operator in the genetic algorithm to make the mutation change to the optimal solution direction [72]; given the fact that traditional ACO algorithm is easy to fall into local optimal, Che et al. designed a heuristic function based on the PSO algorithm to improve the global search efficiency [64]. In 2019, Lim et al. used selectively differential evolution-hybridized quantum PSO (SDEQPSO) for constrained path planning. The algorithm can generate a smooth and feasible path under hard constraints of boundary conditions and soft constraints of obstacle avoidance [111]. In 2020, Wang et al. combined PSO with cubic spline interpolation to achieve obstacle avoidance and path optimization. The planned path curvature is continuous and can meet the constraint of the minimum rotation radius of AUV [112].


## 4.3. Direction C: Intelligent Path Planning Algorithms

With the rapid development of computer intelligence technology, especially machine learning, using machine learning to solve AUV’s path planning is one of the current trends. Through learning and training, the AUV has self-learning ability. It can improve the AUV’s intelligence level and realize the path planning of the AUV in complex and unknown environments. In recent years, RL methods (such as Q-learning [99, 100] and Sarsa [19]) or deep reinforcement learning methods [104] have achieved excellent results in AUV path planning. In 2018, Cao et al. used reinforcement learning and Gaussian process regression to solve the path planning with bathymetric aids and modelled the value function as a Gaussian process to minimize the location uncertainty when the AUV reaches the target point [113]. In 2020, Sun et al. used the hierarchical deep Q network in 3D path planning. The algorithm divided the task of path planning into three layers to solve the problem of dimension disaster and modified the reward function according to the different requirements of the task [114]. However, there is relatively little research in this area. Therefore, intelligent path planning algorithms still need to be developed.


## 4.4. Direction D: Multi-AUV Cooperative Path Planning Algorithms

As the tasks undertaken by AUV become increasingly complex and single AUV has some problems such as limited energy resources, multi-AUV parallel collaborations have become an important way to solve such problems. In multi-AUV path planning, safety is essential for each AUV. In the GBNN algorithm [7, 86], each AUV regards other AUVs as moving obstacles, thus avoiding collision between multiple AUVs. In 2019, Liang et al. proposed an improved APF method with a ring-shaped repulsion field, which can ensure that multiple AUVs can smoothly bypass obstacles at a safe distance [22]; based on assigning tasks to multi-AUV systems, Chen et al. combined the restricted velocity synthesis method and the belief function method to guide each AUV to reach the target safely. The restricted velocity synthesis method is used to overcome the influence of ocean currents, and the belief function method is used to avoid obstacles [115]. In 2020, Panda et al. applied the grey wolf optimization (GWO) algorithm to the path planning of the multi-AUV system and compared it with the genetic algorithm. GWO algorithm can make AUV reach the goal in a shorter time, thus reducing the path cost [116]; Xiong et al. proposed an elite group-based evolutionary algorithm (EGEA) for multi-AUV path planning [117]. It will be the most important research in the future to design an algorithm to realize the collision-free cooperative path planning of multi-AUV.


## 4.5. Direction E: 3D Path Planning Algorithms

The 3D path planning algorithm has some problems, such as difficult environment modelling and complicated calculation. However, it is very suitable for real underwater environments and can meet AUV’s actual work requirements. Now, an increasing number of algorithms are applied to the 3D path planning of AUV. In 2015, Yu et al. proposed a hybrid search fast marching (HSFM) method to generate a three-dimensional smooth path from the discrete representation of the underwater environment [118]. In 2018, Sun et al. established a three-dimensional Glasius bionic neural network model to represent the three-dimensional underwater working environment, which independently planned the path according to the activity of neurons [119]. In 2019, Liu et al. proposed a learning fixed-height histogram (LFHH) method based on the estimation of distribution algorithm to solve the path planning in the 3D environment with current and moving obstacles [120]. Sometimes, the 3D underwater environment can be mapped to the horizontal plane and vertical plane to solve 3D path planning. In the future, the 3D path planning algorithm will become the mainstream method.In addition, we think that the future research directions of AUV path planning algorithms should focus on the following aspects:(1)
Time-Varying Ocean Current. Most of the existing path planning algorithms in ocean current environments are for steady currents with constant size and direction and do not consider the influence of time-varying ocean currents. When AUV is in the time-varying current environment, the path planning algorithm should be able to deal with the time-varying current effectively.(2)
Special Obstacles. Most of the existing path planning algorithms treat obstacles as regular graphics and are suitable for simple environments. AUV path planning algorithms for special obstacle environments (such as irregular obstacles, flexible obstacles, and dense obstacles) are very few and should be focused on.(3)
Multiobjective Constraint. As the tasks undertaken by AUV become more complex, the path planning algorithms cannot simply take the path length or navigation time as a single optimization goal, and the evaluation of path quality should start from many aspects, such as energy consumption, smoothness, safety, feasibility, and so on. The path planning algorithm under multiobjective constraints can effectively improve the path quality.(4)
Practicability. Most of the existing path planning algorithms are verified by simulation, but the practicability of the algorithm has not been verified by experiments. If the algorithm cannot be applied to the actual underwater environment, the significance or value of the algorithm will be greatly reduced. Therefore, the practicability of the algorithm should be improved in the design and verified by the actual underwater experiment.


## 5. Conclusions

Path planning technology has been widely used in AUV underwater navigation and work. This paper reviews the path planning techniques of AUV. Based on the introduction of typical environment modelling methods, the development of path planning technology is introduced in detail, and the advantages and disadvantages of various path planning algorithms are summarized. Many environment modelling methods and path planning algorithms perform well in the 2D or 3D environment. Besides, the AUV path planning needs to consider the uncertainties and dynamic characteristics of the environment, real-time performance, effectiveness, and optimality of the planning algorithm. Moreover, it needs to meet the AUV’s motion constraints. AUV path planning cannot be solved simply by using a certain algorithm, and it must be handled flexibly according to the actual situation and the advantages and disadvantages of various algorithms. This paper aims to summarize the development and advantages and disadvantages of current path planning technologies for AUV to provide some reference for researchers. However, due to the limitation of experimental conditions, most of the studies in the existing literature only stay in the simulation stage. Although some research has been carried out in the actual underwater environment, it has not reached the practical application requirements. Some path planning algorithms are not well adapted to complex underwater environments, and they also have problems such as poor robustness and slow running speed. In the future, it is hoped that more AUV path planning algorithms can be applied to the actual underwater environment and achieve excellent results.



---

*Source: 8847863-2021-02-13.xml*