Path planning and obstacle avoidance for auv: a review

Ocean Engineering 235 (2021) 109355

7

C. Cheng et al.

Table 1

Comparison of main global path planning methods for known obstacle avoidance.

Algorithm

Advantages and disadvantages

Reference

Improvement

A* Algorithm

Direct search

Carroll et al.

(

1992

)

/

No preprocessing required

Szczerba et al.

(

2000

)

Sparse A* algorithm and optimization path

Large amount of calculation

Chen et al.

(

2012

)

/

Optimal solution not guaranteed

Yan et al.

(

2012a

)

The search process is more flexible

Yan et al.

(

2012b

)

Considering the anisotropy of current

Wang and Pang

(

2019

)

/

Li and Zhang

(

2020

)

Multi-direction A* algorithm is designed

Genetic Algorithm

Strong global searching ability

Alvarez and Caiti

(

2001

)

/

Slow convergence

Alvarez et al.

(

2004

)

Add iteration operator and random migration operator

Poor local optimization

Zhang

(

2006

)

/

Poor stability

Sun and Zhang

(

2012

)

Adjust the fitness function

Li et al.

(

2013

)

Add node deletion operator and smoothing operator

Cao et al.

(

2016

)

Change initial population and add tangential operator

Yan and Pan

(

2019

)

Improve diversity evaluation criteria and increase

mutation rate

Differential Evolution

Similar to genetic algorithm

Li et al.

(

2014a

)

/

Higher mutation probability

Zhang et al.

(

2014

)

Improved cost function

Mahmoud et al.

(

2018

)

Using current energy

Ant Colony

Strong global searching ability

Wang and Wei

(

2009

)

Add cutting operator and insertion point operator

Optimization

High efficiency

Zhang and Jia

(

2012

)

Add penalty factor

High convergence speed in later period

Yang et al.

(

2015

)

Pheromone elimination

Slow convergence speed in early stage

Dong and Xu

(

2017

)

Add the reinforcement idea

Yu et al.

(

2018

)

/

Ma et al.

(

2018

)

Use alarm pheromones to reduce invalid searches

Hu and Zhang

(

2019

)

Improved heuristic function

Che et al.

(

2020

)

Improved pheromone update rules

Ma et al.

(

2020

)

Improve the initial pheromone

Particle Swarm

Fast search time

Yang and Zhang

(

2009

)

Improved particle update strategy

Optimization

High convergence speed in early stage

Tang et al.

(

2010

)

Solving the critical point problem

Slow convergence speed in later period

Li et al.

(

2019c

)

Adaptive quantum particle swarm optimization

Easy to fall into local optimum

Wang et al.

(

2020

)

Improved quantum particle swarm optimization

Lim et al.

(

2020b

)

Combining with differential evolution algorithm

Lim et al.

(

2020b

)

learning

Sutton and Barto

(

1998

). Specifically, a positive reward will

be given to safe paths and a negative reward will be given to collision

paths during the training process.

Yu et al.

(

2018

) proposed

𝐴𝐶𝑂

-

𝐴

∗

by

combining the ant colony optimization (ACO) algorithm with

𝐴

∗

search

(

Phanthong

,

2015

). Based on fine-grained modeling,

𝐴𝐶𝑂

-

𝐴

∗

takes

the advantages of the

𝐴

∗

algorithm which uses admissible heuristic

functions for pairwise path planning and the ACO algorithm which

establishes the target’s marching order through coarse-grained model-

ing based on the representative estimation strategy. Their experimental

results show that AUV can successfully pass through the area with dense

obstacles. To reduce invalid search,

Ma et al.

(

2018

) introduced an

alarm pheromone in the ant colony optimization algorithm. When an

ant reaches the infeasible area, it releases alarm messages to alert the

ants behind. Compared with other methods, it can not only build a

collision-free path for AUV, but also can keep AUV away from obstacles

as far as possible.

To solve the limitation of single objective programming in the actual

marine environment,

Hu and Zhang

(

2019

) proposed an multi-objective

ant colony optimization strategy. In their method, the evaluation func-

tion for pheromone update is no longer determined by a single path

length, but also considers the impact of the current on energy con-

sumption and the safety of AUV. Their results in simulated experiments

show that the algorithm can make AUV reach the target point without

collision under the constraint of multi-target. With regard to energy

consumption which is an important factor for AUV path planning,

Ma

et al.

(

2020

) applied the firework-ant colony algorithm (

Zhang et al.

,

2018

) to the path planning of AUV. The initial pheromones of the ant

colony algorithm are derived from the initial reference path generated

by the improved fireworks algorithm, which can obtain the global

optimal solution in a shorter time. To allow AUV to find an optimal

path in complex seabeds,

Che et al.

(

2020

) proposed the ant colony

algorithm with particle swarm optimization. The particle swarm opti-

mization algorithm is introduced into the path length heuristic function

to improve the pheromone update rules. In addition, considering the

difficulty of AUV in three-dimensional space, the proposed method

limits the initialization range of individual population, greatly im-

proves the search efficiency and avoids a series of unnecessary pitching

and heave. Compared with the traditional ant colony algorithm, the

optimized path in the simulation is greatly shortened.

The ant colony optimization algorithm can easily find an optimal

path to the target point in environments with known static obstacles.

The searching efficiency can be greatly improved with distributed com-

puting and positive feedback mechanism, but the convergence might be

very slow. Therefore, the application of ant colony algorithm to AUV

path planning still needs further investigations.

3.6. Discussion

Table 1

shows advantages and disadvantages of global path plan-

ning methods with collision avoidance of known obstacles. Compared

with other algorithms, the

𝐴

∗

algorithm is the most direct heuristic

search algorithm without any preprocessing operation. However, if the

task is executed in a large-scale environment, a large number of nodes

need to be calculated, which results in a low searching efficiency.

According to the principle of survival of the fittest, the genetic algo-

rithm usually carries out a large number of evolutionary operations.

Therefore, it will occupy a large storage space and has more parameters

to be adjusted, resulting in a slow convergence speed. The advantage

of the genetic algorithm is that it has strong global search ability and

can overcome the sub-optimal solution problem of the

𝐴

∗

algorithm.

Similar to the genetic algorithm, a differential evolutionary algorithm

also has genetic operators such as selective cross mutation, which can

be defined with different methods. It is verified that the robustness

of the differential evolutionary algorithm is superior to the genetic

algorithm in a wide range of path planning applications.

The ant colony optimization algorithm and particle swarm opti-

mization algorithm are bionic methods inspired upon the behavior

mechanism of biological groups in nature. They can adapt to the

---

Ocean Engineering 235 (2021) 109355

8

C. Cheng et al.

Fig. 7.

The path planning mechanism of the basic RRT algorithm in the presence of

obstacles.

Source:

Modified from

Yu et al.

(

2017

).

environment in a shorter time with the cooperation between individual

organisms. The most significant feature of the ant colony optimization

algorithm is that it adopts a positive feedback mechanism, which can

promote the ants to move towards the direction with high pheromone

concentration. Because the distribution of the initial pheromones is

sparse, it takes more time to search at the beginning, which leads to

a slow convergence. In the later stage, with the increase of pheromone

concentration, the convergence rate increases obviously. Different from

the ant colony algorithm, the particle swarm algorithm makes use of

information shared among groups, and has faster convergence speed in

the initial stage. Meanwhile, the particle swarm optimization algorithm

has fewer parameters and certain memory functions, which can greatly

reduce the searching time. However, the lack of dynamic regulation of

particle velocity makes it prone to convergence at local optimum.