Path planning and obstacle avoidance for auv: a review

𝐴

∗

search algorithm. To

overcome defects of the traditional

𝐴

∗

algorithm,

Li and Zhang

(

2020

)

designed a multi-directional

𝐴

∗

algorithm, which reduced the number

of search nodes to get the optimal path.

In summary,

𝐴

∗

algorithm is usually modified to improve the expan-

sion of heuristic function or sub node to better adapt to the application

of AUV path planning. When the

𝐴

∗

algorithm searches for the next

node, it has to calculate and select the node with the smallest

𝑓

value

each time. It is time-consuming to calculate the

𝑓

value of all nodes in

the map, especially for the search area with a large map. This might

make the speed of planning for a path very slow.

---

Ocean Engineering 235 (2021) 109355

5

C. Cheng et al.

Fig. 4.

An illustration of one iteration in the genetic algorithm.

3.2. Genetic algorithm

Inspired by the natural selection and evolution, the genetic algo-

rithm is proposed and has been widely used to solve various opti-

mization problems. The genetic algorithm works by initializing the

population randomly, selecting the suitable individuals with a fitness

function, carrying on the selection, crossover, mutation genetic oper-

ations, and constantly updating the population (

Haupt and Werner

,

2007

).

Fig. 4

shows one iterative process of the genetic algorithm.

Through operating on the object directly, the genetic algorithm can

obtain and guide the search space automatically without defining rules.

Restricted by genetic algorithm, researchers usually modify the

algorithm in terms of the genetic operator, evaluation factor or indi-

vidual selection of population to adapt to the characteristics of AUV.

For example,

Alvarez and Caiti

(

2001

) applied genetic algorithm to

path planning of underwater vehicle. In their method, a new ge-

netic operator is added to the algorithm to make it converge to the

global minimum when there are different minimum values in the

ocean flow field. To complete the obstacle avoidance task under strong

currents,

Alvarez et al.

(

2004

) proposed an improved genetic algorithm.

In their method, an iterative operator is added to change the initial

population, and a random migration operator is added to improve the

mutation rate. Their results show that AUV can obtain the path with

minimum energy consumption.

Zhang

(

2006

) designed a hierarchical

path planning method based on the genetic algorithm. Firstly, the

AUV workspace is decomposed into obstacle region and free region by

octree. Then the genetic algorithm is used to search the path of the free

region. According to the current information provided by electronic

charts, an adaptive function is established for genetic algorithm

Sun

and Zhang

(

2012

). In their method, the ocean current is used as an

evaluation factor of the adaptive function in the algorithm, which saves

the energy consumption of AUV.

Li et al.

(

2013

) show that adding

a node deletion operator and a smoothing operator into the genetic

algorithm can get a better path. In addition,

Cao et al.

(

2016

) improved

the initial population generation method of the genetic algorithm and

designed tangential operators to greatly improve the convergence speed

of AUV path planning.

Yan and Pan

(

2019

) proposed an improved

genetic algorithm to solve the premature problem in the traditional ge-

netic algorithm. In their method, the population entropy is used as the

diversity evaluation standard, and an adaptive method is used to adjust

the probability in crossover and mutation. In addition, considering the

kinematic characteristics of AUV as shown in Section

2

, the individuals

who are close to obstacles or do not conform to the actual attitude of

AUV are eliminated in the genetic algorithm.

The biggest advantage of genetic algorithm is that it does not need

to know how to find the optimal solution before planning. The genetic

algorithm has been successfully applied to AUV path planning in en-

vironments with known static obstacles. However, if the parameters

of the algorithm were not adjusted properly, some problems might

happen, e.g., individual peak value or the planning speed might be very

slow.