Le Hong,Changhui Song,Ping Yang and Weicheng Cui

Received:06 July 2021/Accepted:02 December 2021

?Harbin Engineering University and Springer-Verlag GmbH Germany,part of Springer Nature 2022

Abstract As autonomous underwater vehicles(AUVs)merely adopt the inductive obstacle avoidance mechanism to avoid collisions with underwater obstacles, path planners for underwater robots should consider the poor search efficiency and inadequate collision-avoidance ability. To overcome these problems, a specific two-player path planner based on an improved algorithm is designed. First, by combing the artificial attractive field (AAF) of artificial potential field (APF) approach with the random rapidly exploring tree (RRT) algorithm, an improved AAF-RRT algorithm with a changing attractive force proportional to the Euler distance between the point to be extended and the goal point is proposed. Second, a twolayer path planner is designed with path smoothing, which combines global planning and local planning. Finally, as verified by the simulations, the improved AAF-RRT algorithm has the strongest searching ability and the ability to cross the narrow passage among the studied three algorithms, which are the basic RRT algorithm, the common AAF-RRT algorithm, and the improved AAF-RRT algorithm. Moreover, the two-layer path planner can plan a global and optimal path for AUVs if a sudden obstacle is added to the simulation environment.

Keywords Autonomous underwater vehicles (AUVs); Path planner; Random rapidly exploring tree (RRT); Artificial attractive field(AAF);Path smoothing

1 Introduction

Path planning is one of the core technologies in autono‐mous underwater vehicles (AUVs), and it is also a key link in realizing autonomous navigation and operation(Sun et al. 2020). Path planning in underwater robots re‐fers to finding a collision-free path from the initial state to the target state according to certain evaluation criteria in the water environment containing obstacles.In addition,to a certain extent, path planning technology marks the intel‐ligence level of underwater robots (Gasparetto et al. 2015;Sariff and Buniyamin 2006).However,compared with oth‐er types of mobile robots, the working environment of un‐derwater robots is a large-scale three-dimensional (3D)space. The complexity of the underwater environment increases the difficulty of path planning.At the same time,the robot's position, energy consumption, self-attitude, and motion constraints should be considered (Gu et al. 2005).Therefore, it is very important to choose a reasonable and suitable path planning method for underwater robots.

Path planning methods for underwater robots can be divided into two categories: traditional approaches and intelligent approaches. Traditional approaches include path planning methods based on the road map construc‐tion method (Lozano-Pérez 1990), element decomposition method (Li 2012; Tanakitkorn et al. 2014), A* algorithm,D* algorithm, and artificial potential field (APF) method.The A* algorithm, D* algorithm, and APF method are the most widely used path planning approaches at present.The A* algorithm is suitable for static path planning (Hart et al. 1972). D* algorithm is a dynamic A* algorithm,which is suitable for solving the dynamic path planning problem by detecting the change in the previous node or nearby nodes of the shortest path (Carsten et al. 2006).The APF method is a virtual method proposed by Khatib etc.(Khatib 2003;Volpe and Khosla 1990).The intelligent path planning approaches include swarm intelligencebased methods and the method based on machine learning(Sun et al. 2020). Path planning methods for underwater robots based on swarm intelligence mainly include genetic algorithm (Xu and Li 2010; Xu and Yao 2008), ant colony algorithm (Liu et al. 2016; Wang et al. 2008), and firefly algorithm (Dong 2013; Liu et al. 2015).Algorithms based on swarm intelligence are relatively mature in global path planning, but they do not have a high real-time perfor‐mance. Concerning the application of machine learning to the path planning for underwater robots,Zhu et al.focused on the situation of sudden obstacles, using environmental changes to cause changes in neuron excitation and activity output values, and thereby outputting collision-free path points(Zhu et al.2015).To sum it up,traditional path plan‐ning methods are simple to describe and easy to imple‐ment.However,they generally lack flexibility and the abil‐ity to be applied in 3D complex underwater environments.Intelligent methods make up for many shortcomings of tra‐ditional methods. They can solve global and local path planning problems. However, based on the basic environ‐ment model,they can obtain high real-time planning.

Considering the above-listed drawbacks of the two com‐mon approaches,in this paper,the RRT algorithm is adopt‐ed as the basic algorithm to study for the path planning of underwater robots. The RRT algorithm is chosen for three main reasons. First, the RRT algorithm is based on a tree structure and random sampling. Therefore, rather than an arbitrary geometric curve between two points, the route from the point to be extended and the new point could be generated by the kinematics and dynamics simulations of robots.Thus,it is suitable for solving dynamic path planning problems. Second, based on random sampling, the RRT algorithm does not need to search all points in the space and model the obstacle space accurately.Lastly,RRT algo‐rithms have advantages in multidimensional spaces. The higher the dimensionality is, the more the node states are.For traditional path planning methods, these algorithms can easily cause dimensionality disasters. However, RRT algorithms are based on random sampling. In a high-di‐mensional space, they just need more dimensions for sam‐pling,rather than sampling every state in the space.

The search randomness of RRT algorithms makes them have a strong exploration ability. However, it will lead to blindness while planning a certain path. At present, to solve this problem, scholars have proposed some strate‐gies.In the early stage,a single RRT-tree was mainly used for searching. To improve the search speed, scholars pro‐posed biased RRT(Lavalle and Kuffner 2000)and bidirec‐tional RRT(Jr and Lavalle 2000)search algorithms.There‐fore,improved RRT algorithms generally include two cate‐gories, namely, heuristic algorithms and bidirectional search approaches, which improve the convergence speed to a certain extent. To consider kinematic constraints of the intelligent vehicles, Liu, et al. proposed a target-bias‐ing strategy, which reduces the nodes of trees and im‐proves the search efficiency and running time of an algo‐rithm (Liu et al. 2017). Wang proposed a smooth splicing algorithm(Wang 2014).By optimizing the connection line between random points, the path is generated under the constraint of the motion system.However,the above-men‐tioned improved RRT algorithms can only plan a relatively optimal path at the cost of search efficiency, which would increase the complexity and searching time of path plan‐ning.Therefore,how to plan an optimized path without in‐fluencing the running efficiency of RRT algorithms is the problem. Recently, combined algorithms have per‐formed well in solving this problem. By combining mem‐brane computing, genetic algorithm, and the APF method,hybrid approaches successfully reduce time complexity(Orozco-Rosas et al.2019b)and speed up the computation(Orozco-Rosas et al.2019a).Inspired by the advantages of hybrid approaches, APF, a goal-oriented algorithm, may be a good choice for improving the performance of RRT algorithms.

Inspired by the two problems, the contributions of this study lie in the following aspects.First,the RRT algorithm is combined with the concepts of AAF in the APF method to guide random trees to grow in the direction of the target point. Based on the common AAF-RRT algorithm with a constant attractive force,an improved AAF-RRT algorithm with a proportional attractive force is proposed to enhance the goal orientation of the algorithm and reduce the compu‐tation resource. Second, other researchers mainly focus on studying obstacle avoidance on the global path, which has been planned for AUVs(Cai et al.2020).To simultaneous‐ly plan an optimal and global path,in this study,a two-lay‐er path planner with path smoothing is designed, which combines the global planning based on the proposed AAFRRT algorithm and the approaches of the local planning.Third, based on the simulation results, the proposed im‐proved AAF-RRT algorithm is verified to perform better than the common AAF-RRT algorithm in the three aspects,namely, search ability, collision-avoidance ability, and the ability to pass through narrow passages. Accordingly,based on the proposed AAF-RRT, the two-layer path plan‐ner can successfully plan the global and optimal path for AUVs when adding sudden obstacles to a simulated map.

2 Preliminaries for the RRT and APF

In this section, the concepts, characteristics, and plan‐ning process of the RRT algorithm and APF approach will be illustrated in detail.

2.1 RRT algorithm

Uninterruptedly searching the state space of robots via random sampling is the basic principle of RRT algorithms.It can be generally divided into two steps. First, a random tree is rapidly established.Then,an effective path from the initial point to the goal point is queried based on the ran‐dom tree.The corresponding pseudocode of RRT is shown in Algorithm 1.

Algorithm 1 RRT algorithm Input:the initial point xinit;the number of samples K;the step size t between the two points Output:the RRT-Tree T 1 Initialization;23456789 2 while k ≤K do 3 xrand=Random_State();4 xnear=Nearest_Neighbor(xrand,xnear);5 u=New_State(xrand,xnear);6 xnew=New_State(xrand,xnear);7 T.add_vertex(xnew);8 T.add_vertex(xnear,xnew,u);9 return T;

The detailed steps of algorithm 1 can be illustrated in the following steps:

Step 1Initialize the whole statespace. Define the initial pointxinit,the number of samplesK,and the step sizetbe‐tween the two points.

Step 2Use the function Random_State() to randomly generate a pointxrand.

Step 3Use the function Nearest_Neighbor() to find the pointxnearclosest to the pointxrand.

Step 4Get the extension vector using the function Selet_Input() and get the new pointxnewwith the step sizetand extension vectoru.

Step 5Determine whether there is an obstacle fromxneartoxnew. If it does not exist, then add the pointxnewto the tree vertex and connectxnewwithxnear.

Figure 1 vividly shows the growth of a random tree in a simulated environment. The blue triangle and red triangle represent the start point and goal point,respectively.Green circles denote points in the tree,and the blank circle denotes the sampling point. Located in the center of the figure, the two white irregular frustums of a pyramid represent the two obstacles in the environment. The expanding process of RRT can be illustrated as follows.After sampling point 5 in the map, the RRT algorithm would figure out the nearest point 3 in the tree.Then,the new point 4 would be added in the tree connected with point 3 at a prescribed step size.

Figure 1 Growth process of random trees in RRT

2.2 APF approach

TheAPF method is a classical path planning algorithm for robots.The APF regards the target position and obstacles as objects that have attractive and repulsive forces on robots,respectively. Therefore, the APF contains two kinds of force fields:AAF formed by the target position and artifi‐cial repulsive field (ARF) formed by various obstacles.The robot would move along the synthetic force of the at‐tractive force and repulsive forces. This synthetic force is given as follows:

wherexdenotes the coordinate position of the intelligent ve‐hicle in the environment,Fatt(x)is the attractive force that guides the vehicle to move to the goal position,andFrep(x)is the repulsive force that makes the vehicle avoid obstacles.F(x)is the synthetic force ofFatt(x)andFrep(x).

Figure 2 shows the force analysis of an intelligent vehi‐cle in the APF algorithm.The blue oval denotes an intelli‐gent vehicle in a simulated environment. The red triangle and white frustum of a pyramid still represent the goal point and obstacle in the environment, respectively. Ac‐cording to the previous illustration of the APF,F1andF2are the repulsive forces that two obstacles give to the intel‐ligent vehicle.F0is the attractive force given from the goal position to the position of the intelligent vehicle.After the synthesis of the three forces,F3is the final force that the vehicle receives. The vehicle would move under the guidance ofF3.

3 Improved AAF-RRT algorithm

Figure 2 Force analysis of an intelligent vehicle in the APF

As the randomness of RRT causes its search blindness,to improve the search efficiency, we add the concepts of the AAF in APF to the extension of random trees in the RRT algorithms. Then, the goal point in the search envi‐ronment would have an attractive field for robots. Consid‐ering that there exist the judging criteria for the collisions among points and obstacles in RRT,the concept of ARF in the APF approach is not necessary to be added to RRT al‐gorithms. After this combination, RRT becomes goal-ori‐ented, and this improved RRT algorithm is named AAFRRT algorithm in this paper, which is a kind of RRT algo‐rithm integrated with AAF.

In the concept of AAF, the potential function carries the information of targets, which should be delayed to RRT.Then,the random tree can move in the direction of the po‐tential field from the targets when exploring the space. In addition,the excellent exploration ability of RRT can make up for the shortcoming that the potential field method easily falls into a local minimum.After all,we combine RRT and AAF by adding the idea of target attraction into the exten‐sion of the RRT random tree.The detailed illustration of the extension in AAF-RRT is as follows: First, after randomly generating thenthsample pointprand(n), the correspondingnthnearest point,pnear(n),is obtained.Then,for thenthnear‐est pointpnear(n),R(n) represents the extension vector that the random pointprand(n) gives topnear(n).The attrac‐tive vectorA(n) is given from the goal point topnear(n).R(n) andA(n) simultaneously affect the extension of the random tree. Therefore, the random tree can grow toward the target point with a certain and rational trend.

Referring to Eq. (2), the artificial attractive vectorA(n)of the AAF-RRT algorithm constructed in this work can be elaborated by Eq.(3).

Then, the calculation equation for the new extended pointpnew(n)can be obtained by Eq.(5).

Eq.(5)shows that the calculation forpnew(n)includes two parts,i.e.,the extension vector from the sample pointprand(n)and the attractive vector from the goal pointpgoal.Then,based on Algorithm 1 of the basic RRT algorithms,the pseudocode oftheAAF-RRTalgorithmsisshowninAlgorithm2.

?

Compared with Algorithm 1,vand the function Attractive_Input() are added to the algorithm. v denotes the attractive vector given from the target point.After get‐ting the coordinate positions of the goal point and the near‐est point, the function Attractive_Input() could calculate the attractive vector. Then, during the formation of the new point, the nearest point would synthesize two vectors,i.e., extension vectoruand attractive vectorv, to get the new point. In terms of connecting the nearest pointxnearand new pointxnew, the direction of this connection line is determined by the synthetic vectors ofuandv. Moreover,the corresponding formation and extension of the random tree are shown in Figure 3.

Figure 3 Extension of the random tree in AAF-RRT algorithms

Patterns in Figure 3 are generally the same as those in Figure 1. The difference between the two figures only lies in the formation of the new point. Figure 3 takes the tree extension in point 3 as an example.R(3) is the extension vector given by the sampling point 5.A(3) is the attrac‐tive vector from the goal point.F(3)is the final guided ex‐tension vector synthesized byR(3)andA(3).Then,under the influence ofF(3), the new point 4 is successfully formed and added into the random tree. In the previously designed AAF-RRT algorithm, the expression ofρ(n) in Eq. (3) is not determined yet.ρ(n) is described as the at‐tractive factor that thenthpoint to be extended receives from the AAF of the goal point. For the current common AAF-RRT algorithm, the attractive factor is set to be con‐stant. However, if all the points in the random tree receive the same attractive factor, then the point closer to the target point will receive the same gravitational force as the rest of the points.This condition may cause the point to jit‐ter near the target point when the tree is extended near the target point, which would affect the convergence of the planning algorithm. Therefore, an improved AAF-RRT algorithm is proposed. In this algorithm,ρ(n) is propor‐tional to the Euler distance between the goal point and thenthpoint to be extended. As for the first assumption that the attractive factor for the points to be extended is un‐changed and constant, Eq. (6) is chosen to describe the at‐tractive factor in the common AAF-RRT algorithm.

whereρ(n)denotes the attractive factor for thenthpoint to be extended andk1denotes the unchanged and constant value of attractive factors in this kind of situation. Unlike the common AAF-RRT algorithm presented above, for the improved AAF-RRT algorithm, the attractive factor is set to be proportional to the Euler distance between thenthpoint to be extended and the goal point.

The corresponding attractive factorρ(n)can be expressed as follows:

wherek2denotes the coefficient given to the attractive fac‐torρ(n).pgoalandpnear(n) represent the coordinate posi‐tions of the goal point andnthpoint to be extended,respec‐tively.||pgoal?pnear(n)||denotes the Euler distance between the mentioned two points. Here, when the point to be ex‐tended is closer to the goal point, the attractive force it re‐ceives would become smaller.This phenomenon would be helpful for the convergence of paths to be planned.

Based on the work done in Liu et al.(2017);Song et al.(2010);Wang et al. (2020), compared to the basic RRT al‐gorithm,the common AAF-RRT algorithm with a constant attractive force could accelerate the convergence of the path and shorten the path length. Therefore, to make the comparison of the simulation results comprehensive and convincing, in Section 6, we present the simulations con‐ducted among three algorithms, namely, basic RRT algo‐rithm, common AAF-RRT algorithm with constant at‐tractive forces, and improved AAF-RRT algorithm with a proportional attractive force.

4 Two-layer path planner

The proposed two-layer path planner is divided into two parts: First, the global path would be planned by the cho‐sen path planning algorithm.Then,the position of the sud‐den obstacle in the environmental model would decide whether the path should be replanned.

4.1 Two steps for the path planner

Figure 4 Diagram of the two-layer path planner

The diagram of the proposed path planner is shown in Figure 4,which describes the specific steps of how to con‐duct the planning process combining global planning and local planning. The first step is global planning, which gets the global path by the specific path planning algo‐rithm. The other steps in the diagram all belong to the lo‐cal planning.The detailed illustration of the local planning is as follows:After a sudden obstacle is added to the envi‐ronmental model, the planner would identify its position and determine whether it conflicts with the previous path.Then, according to the determination, the planner would replan the path or not.

4.2 Path smoothing

Owing to the randomness of the RRT algorithm, the al‐gorithm has a strong exploration ability.However,the ran‐domness will lead to the blindness of path planning. Ac‐cordingly, the planned path would have more redundant points, which increases the corners and the length of the path. Therefore, many optimization methods have been used to determine sub-optimal and optimal paths. The most common and simplest optimization method is prun‐ing,which aims to cut out unnecessary nodes.As shown in Figure 5, if there is no collision between point 1 and point 3, then the line from point 1 to point 2 and the line from point 2 to point 3 can be directly replaced with the line from point 1 to point 3.

After path smoothing is conducted by pruning, redun‐dant points could be correspondingly cut, and the planned path would be shorter according to the triangle inequality.

5 Simulation results

Figure 5 Diagram of the two-layer path planner

Simulations are conducted in two parts:The first part is the simulations for comparing the improved AAF-RRT al‐gorithm with the common AAF-RRT algorithm and basic RRT algorithm. The simulation includes the selection of the environmental mazes, outputting the figures on the views of the random trees,processing time and path length obtained by the algorithms, and conducting the rank-sum tests on the data samples.The second simulations are exe‐cuted for the two-player path planner.A new environmen‐tal maze is chosen for the simulation.Then, the figures on the planned path after the path smoothing and path replan‐ning after the emergence of the sudden obstacles are outputted.

5.1 Simulations for the algorithms

Several mazes are used for studying RRT algorithms.From a comprehensive view,three different mazes with dif‐ferent layouts of obstacles are chosen as the simulation en‐vironments,as shown in Figure 6.Based on the simulation results under the three simulation environments,the search‐ing ability of the three algorithms, i.e., basic RRT algo‐rithm, common AAF-RRT algorithm, and improved AAFRRT algorithm,can be deeply compared and analyzed.

Figure 6 Three different mazes with three different layouts

In the figure, the black pattern represents the obstacle that intelligent agents cannot pass,whereas the white areas are where the agents can pass. The coordinate system of the maze is established as follows: The upper long side of the maze is thex-axis. The right side is the positive direc‐tion of thex-axis. The left side of the maze is they-axis,the positive direction of which is the downward direction.The green hollow circles in the mazes are the initial points, and the red hollow circles are the goal points. The corresponding coordinate positions of the two types of points are unified to be(10,10)and(290,290),respective‐ly. Figure 6(a) shows a simple maze with three square ob‐stacles. There is no obvious obstacle blocking the agents from the start point to the goal point. This simple maze is used for the preliminary exploration of the search speed,search performance, and collision-avoidance ability of the three algorithms. For further exploration of the collisionavoidanceability,anothersimplemaze,showninFigure6(b),contains the non-negligible obstacles on the line from the start point to the goal point. Considering the poor ability of the basic RRT algorithm to pass through the narrow passage in the environment, a complex maze with the nar‐row passage is selected. Whether AAF-RRT algorithms can improve this kind of ability would be answered and confirmed.

Before the simulation of the three algorithms under the three different mazes, we unified several standards for the subsequent simulations. First, the coordinate positions of the start point and goal point are set as (10, 10) and (290, 290),respectively. The maximum iterations of the simulations are 10 000.Two indexes are chosen to reflect the searching abili‐ty and collision-avoidance ability of the three planning al‐gorithms, which are the processing time (s) reflecting the search speed and the path length reflecting the search per‐formance. The overview of the random tree and final planned path would be outputted under the three algo‐rithms, which could directly reflect the search randomness of the sampling-based planning algorithms.Lastly,accord‐ing to Eqs.(5)and(6),we assume thatk1andk2in the sub‐sequent simulations are equal to 0.02 and 0.0001,respectively.

5.1.1 Simple maze

For the preliminary exploration, simulations are con‐ducted in the simple maze. Again, the black areas repre‐sent the obstacles in the maze, and white areas represent the passable areas in the maze. The simulation results are shown in Figure 7.

Figure 7 Whole view of the generated random trees and final planned paths in the simple maze under the three algorithms

The left sides of Figure 7 show the simulation results of the basic RRT.The middle and right sides show the results of the AAF-RRT algorithms with constant attractive and proportional attractive forces, respectively. Figure 7(a)shows the whole view of the three generated random trees,where the nodes in the tree become less from left to right.This result indicates that AAF-RRT algorithms can reduce the search randomness of the basic RRT and improve the running efficiency of the algorithms. Conversely, the im‐proved AAF-RRT algorithm with proportional attractive forces behaves better in this kind of utility compared with the common AAF-RRT algorithm. In terms of the final planned paths shown in Figure 7(b), there exists no obvi‐ous difference among the three planned paths. However,due to the improvement in the randomness of the RRT algorithms, the planned paths are smooth in the AAF-RRT algorithms.

After conducting the same simulation ten times,the data samples of the processing time and path length under the three algorithms are outputted,which are shown in Figures 8 and 9, respectively. Based on the data shown in the fig‐ures, the samples are all non-normal. Therefore, the ranksum test should be used to preliminarily determine wheth‐er the gap between two data samples is evident. With the significance level set to 0.05, the rank-sum test results on the processing time and path length among the three sam‐ples are also shown in Figures 8 and 9, where “*” indi‐cates that the overall difference between the two data sam‐ples is significant.

Figure 8 Processing time and rank-sum test results of the three algorithms on the simple maze

Two conclusions can be derived from the simulation results. First, in terms of the processing time, the gap between the common AAF-RRT and basic RRT is not sig‐nificant,whereas the gap between the improved AAF-RRT and basic RRT and the gap between the improved AAFRRT and common AAF-RRT are all significant. For the path length,only the gap between the improved AAF-RRT and basic RRT is significant. Then, a further conclusion can be obtained.The improved AAF-RRT behaves the best among the three algorithms in terms of processing time.Common AAF-RRT cannot behave better than the basic RRT in the processing time. Moreover,AAF-RRT behaves better than the basic RRT in the path length,whereas com‐mon AAF-RRT still does not have a significant difference with the basic RRT.

Figure 9 Path length and rank-sum test results of the three algorithms on the simple maze

To sum it up,through the preliminary exploration of the simple maze, the simulation results confirm that the two AAF-RRT algorithms can improve the search randomness of the RRT algorithm. They can also improve the running efficiency and search performance of the basic RRT algo‐rithm. Furthermore, the improved AAF-RRT behaves the best in terms of the running efficiency and search perfor‐mance among the three algorithms.

5.1.2 Simple maze with obstacles on the line

Based on the former simulations, the simulation envi‐ronment is upgraded from a simple maze to a simple maze with obvious obstacles on the line. This line refers to the virtual line from the initial point to the goal point in the environment. The aim of this simulation is mainly to determine whether AAF-RRT algorithms could improve the collision-avoidance ability of basic RRT algorithms.Similar to the former simulations, figures on the whole view of the random trees and the final planned paths are successfully outputted,as shown in Figure 10.

Compared with those in Figure 7, the meanings of the patterns stay unchanged in Figure 10. The numbers of nodes in the random trees still turn less from top to bottom in Figure 10. Moreover, the trees tend to be smooth under the AAF-RRT algorithms. Therefore, with the upgrading of the maze, the AAF-RRT algorithms still behave better than the basic RRT algorithm. In terms of the emergence of the obvious obstacles on the line from the initial point to the goal point, the simulation results also show that the AAF-RRT algorithms have a better collision-avoidance ability without the loss of running efficiency.Running effi‐ciency is reflected by the nodes in the random tree.

Figure 10 Whole view of the generated random trees and final planned paths in the simple maze with obstacles on the line under the three algorithms

The corresponding simulation data of the three algo‐rithms are shown in Figures 11 and 12, where the ranksum test results are also shown.The differences among the three algorithms are all significant. Therefore, based on the overlook of the data samples,the order of the planning performance from good to bad is as follows: improved AAF-RRT algorithm→common AAF-RRT algorithm→ba‐sic RRT algorithm.

Based on the simulation results in the second maze, the AAF-RRT algorithms can improve the collision-avoidance ability of the RRT algorithms without the loss of the run‐ning efficiency and searching ability. At the same time,based on the common AAF-RRT algorithm, the improved AAF-RRT algorithm can further improve the search speed and reduce the path length.

5.1.3 Complex maze with narrow passages

Figure 11 Processing time and rank-sum test results of the three algorithms on the simple maze with obstacles on the line

Figure 12 Path length and rank-sum test results of the three algorithms on the simple maze with obstacles on the line

The former two simulation results under the two simple mazes have verified that the AAF-RRT algorithms im‐prove the search randomness and searching ability of the basic RRT algorithms. Considering the poor ability of the RRT algorithms in passing through the narrow passage, a complex maze with a narrow passage is chosen as the sim‐ulation environment.This maze contains a narrow passage around the target point. It also includes obstacles on the line from the initial point to the target point. The simula‐tion results of the random trees and planned paths are shown in Figure 11.

Figure 13(a) shows that the random tree under the basic RRT algorithm is very complicated and almost covers the entire maze. During the conducted simulation process un‐der the basic RRT algorithm,the random tree extends in an extremely slow manner when passing the narrow passages.However, from the other two whole views of the random trees under the two AAF-RRT algorithms,the nodes of the random trees are significantly reduced, especially in the improved AAF-RRT algorithm with a proportional attrac‐tive force. Comparing the two random trees under the two AAF-RRT algorithms,the tendency of the random trees to‐ward the goal point is more obvious under the improved AAF-RRT algorithm. This comparison indicates that the improved AAF-RRT algorithm behaves better in terms of the ability to pass the narrow passage than the common AAF-RRT algorithm.

Figure 13 Whole view of the generated random trees and final path in the complex maze with the narrow passage under the three algorithms

The simulation results under the three algorithms are shown in Figures 14 and 15. Based on the positions of the“*,” in the searching speed, the order of the performance from good to bad is as follows: improved AAF-RRT algo‐rithm→common AAF-RRT algorithm→basic RRT algo‐rithm. However, in the path length tests, only the differ‐ence between the improved AAF-RRT algorithm and the basic RRT algorithm is significant.

Figure 14 Processing time and rank-sum test results of the three algorithms on the simple maze with obstacles on the line

Figure 15 Processing time and rank-sum test results of the three algorithmson the simple maze with obstacles on the line

Based on the above analysis of the simulation results,compared with the common AAF-RRT algorithm, the im‐proved AAF-RRT algorithm can effectively improve the ability to pass the narrow passage of the RRT algorithms better. This kind of improvement has not been found and verified by other researchers.

5.1.4 Local minima trap

One of the challenges in the APF approach is the local minima trap, which may happen when the two APFs, i.e.,AAF and ARF, cancel each other out. For example, when an obstacle is located between the robot and target posi‐tion, a local minima trap may happen.Although the gradi‐ent of these local minima points is zero, they are not the target point set in the environment. Moreover, this kind of local minima trap exists in other path planning methods,such as genetic algorithms(Gong and Peng 2002), cluster‐ing algorithms (Dash et al 2003; Xu and Franti 2004), and deep learning methods(Kawaguchi 2016).

In our proposed AAF-RRT algorithms, a local minima trap also exists in some situations. The existence of the local minima trap in APF approaches directly caused the emergence of that in the AAF-RRT algorithms. The emergence of the local minima trap also indicates that the combination of APF and RRT has advantages and disadvantages. Thus, we should highlight its strengths and avoid its weakness as much as possible. Many ways can be done to solve the local minima trap. One method is to introduce a high-level planner, which would make the robot not only use the detection information from the sensors at any time but also maintain the ability of global planning (Dong 2009). Some remedial solutions allow the robot to fall into the local optimum and then use other solutions to fix the problem. For example, a disturbance or backtracking could be added to the local minima trap to jump out of the local minima points(Morris 1993).

Considering that the objective of this study is to explore the search utilization of the improved AAF-RRT algo‐rithm, an easy and simple solution is chosen to escape the local minima trap for the AAF-RRT algorithms. The solu‐tion is to manually reduce the relevant attractive factors until the path can get into the goal point. In the two AAFRRT algorithms proposed in this paper,the relevant attrac‐tive factors arek1andk2in Eqs. (5) and (6). During the previous numerical simulations under the three RRT algo‐rithms, when adopting thek1andk2of the simulations in the former two simple mazes,the local minima trap emerg‐es in the complex maze under the two AAF-RRT algo‐rithms withk1= 0.2 andk2= 0.002,respectively.By using the proposed solution of reducing the two attractive fac‐tors,the local minima trap can be effectively escaped whenk1= 0.02 andk2= 0.000 1.The four overviews of the ran‐dom tree of the emergence and escape of the local minima trap in the mentioned situation are shown in Figures 16 and 17.Figure 16 shows the situation under the common AAFRRT algorithm, whereas Figure 17 shows the situation under the improved AAF-RRT algorithm. As shown in the two figures, although the attractive factors are manu‐ally adjusted and reduced, the proposed solution to es‐cape the local minima trap for the AAF-RRT algorithms is useful and feasible.

5.2 Simulations for the two-layer path planner

A new simulation environment is configured for the two-layer path planner, which is shown in Figure 16. As shown in Figure 18, the blue and green squares denote the initial node and goal node, respectively. The coordinate position of the initial node is set to (2, 2), whereas that of the goal node is set to (49, 24). The black frame in the figure represents the boundary of the environment. The gray patterns denote the obstacles in the environment,which consist of four circular obstacles and four rectangular obstacles.

Figure 16 Whole view of the generated random trees where the local minima trap emerges be overcomed under the common AAFRRT algorithm

Figure 17 Whole view of the generated random trees where the local minima trap emerges and be overcomed under the improved AAF-RRT algorithm

5.2.1 Two-layer path planner combined with path smoothing

The improved AAF-RRT is chosen to be the planning algorithm in the two-layer path planner. The simulation process of the two-layer path planner consists of two parts according to the description in Section 4.1.First,the global path would be outputted by the planning algorithm.Second,considering the probability of the sudden obstacles in the environment,the path would be replanned according to the positions of the sudden obstacles.

For the first part, the improved AAF-RRT algorithm would be used to generate a global path.To further shorten the path length, pruning is conducted after generating a path.Then,the planned paths with no pruning and pruning are both outputted, which are shown in Figure 19.The red line denotes the path simulated with no pruning, whereas the blue line represents the path simulated with pruning.Then,the corresponding path length is reduced from 66.95 to 59.36 by adding pruning.

Figure 18 Environmental configuration of the simulations for the two-player path planner

Figure 19 Planned paths without pruning and with pruning

5.2.2 Two-layer planner added with sudden obstacles

Based on the planned path simulated in Figure 19, we add the sudden obstacles thrice one by one.The fish pattern represents the sudden obstacle. The geometric center of the first obstacle is located in (10, 7), which conflicts with the previously planned path. Therefore, a new path is planned after adding the obstacle, as shown in Figure 20(a).The meanings of the red and blue lines are unchanged.The second obstacle is added at (15, 22). The obstacle would not conflict with the previously planned path.Therefore, there is no need for the path to be replanned.The previously planned path with pruning would be retained in the red line, as shown in Figure 20(b). Lastly,the third sudden obstacle emerges at (23, 16), conflicting with the previously planned path. Then, the replanned paths are outputted based on the newly added three obstacles,which are also shown in Figure 20(c).

To sum it up, based on the simulation results, the twolayer path planned can not only search a global path with the help of the improved AAF-RRT algorithm and the pruning process but also effectively replan the path when the sudden obstacle emerges in the environment.

Figure 20 Planned paths after the sudden obstacles thrice one by one

6 Conclusions

In order to improve the search efficiency and collisionavoidance ability of AUVs, this study proposes a specific two-player path planner based on an improved algorithm.By integrating the AAF concept with the RRT algorithm,the proposed AAF-RRT algorithm is verified to perform better than the basic RRT algorithm and common AAFRRT algorithm. After adding several sudden obstacles to the simulation environment, it is confirmed that the twolayer path planner based on the proposed algorithm can quickly react and effectively avoid obstacles.The two veri‐fication results provide a basis for the subsequent practical application of the RRT algorithm in AUVs. They also make stable path planning in harsh underwater environ‐ments no longer a luxury.

Thus far, the improved AAF-RRT algorithm and twolayer path planner have only been applied to a two-dimen‐sional environment. In the future, to further explore the feasibility of the algorithm and path planner, a 3D simula‐tion will be conducted. Moreover, it would be interesting to explore whether the expansion direction branches in RRT can refer to the true growth direction of branches in nature.

Founding InformationSupported by Zhejiang Key R&D Program 558 No. 2021C03157, the “Construction of a Leading Innovation Team” project by the Hangzhou Munic-559 ipal government, the Startup funding of New-joined PI of Westlake University with Grant No. 560 (041030150118) and the funding support from the Westlake University and Bright Dream Joint In-561 stitute for Intelligent Robotics.