Path planning and obstacle avoidance for auv: a review

3.1. A

∗

algorithm

𝐴

∗

algorithm is the most effective direct search algorithm in the

static environment. It combines heuristic searching and searching based

on the shortest path (

Duchoň et al.

,

2014

). In the

𝐴

∗

algorithm, the

search area is generally divided into small squares, with each square

representing a node. The

𝐴

∗

algorithm uses an evaluation function:

𝑓

(

𝑛

) =

𝑔

(

𝑛

) +

ℎ

(

𝑛

)

, which provides guidances for the selection of nodes

in an open list. In the evaluation function,

𝑔

(

𝑛

)

is the actual cost of

node

𝑛

found so far from the initial node, and the cost estimate

ℎ

(

𝑛

)

is the Manhattan distance from node

𝑛

to the target node (

Yao et al.

,

2010

). As shown in

Fig. 3

, the

𝐴

∗

algorithm calculates the

𝑓

value of

the surrounding nodes and selects the node with the smallest

𝑓

value

as the next traversal node until the target node is found.

Due to the particularity of the marine environment,

Carroll et al.

(

1992

) considered the maximum operation depth of AUV and current

information in the heuristic function when they used the

𝐴

∗

algorithm

for path planning. To shorten the search time,

Szczerba et al.

(

2000

)

proposed a sparse

𝐴

∗

algorithm using the maximum turning angle and

the maximum path length as constraints for the basic

𝐴

∗

algorithm.

Yan et al.

(

2012a

) proposed an

𝐴

∗

algorithm based on circle search.

In their method, a virtual terrain is used to map the 3D space into

a 2D search area, which can meet the constraints of the change rate

of the AUV’s pitch angle and heading angle. In addition, the search

step size and search direction of the algorithm are flexible, so that

AUV can quickly get out of the threat and reach the destination. Based

on a sparse

𝐴

∗

algorithm,

Chen et al.

(

2012

) constructed the search

space of obstacles by randomly distributing points and combined with

a visibility inspection method under the constraint of maximum turning

radius to make AUV path smoother. According to the anisotropy of

the current flow,

Yan et al.

(

2012b

) expanded the sub nodes of

𝐴

∗

algorithm in a specific direction, which simplifies the spatial range

and greatly shortens the path planning time.

Wang and Pang

(

2019

)

applied the

𝐴

∗

search algorithm to a chemical plume tracking task with

AUV. Specifically, they get the source location according to the partially

observable Markov decision process (

Jiu et al.

,

2019

), and search the

shortest path of chemical source with the