Route planning algorithm for autonomous underwater vehicles based on the hybrid of particle swarm optimization algorithm and radial basis function

Abstract

The mission route plays an essential role for the mission security and reliability of an unmanned system. This paper gives a route planning method for autonomous underwater vehicles (AUVs) based on the hybrid of particle swarm optimization (PSO) algorithm and radial basis function (RBF). In the improved PSO algorithm, metropolis criterion is used to prevent the improved PSO algorithm from falling into local optimum and RBF is used to smooth the path planned by PSO algorithm. Compared with classic PSO algorithm, the hybrid algorithm of PSO and RBF can avoid falling into the local optimum effectively and plan an anti-collision route. Moreover, based on the simulation results, it can be seen that the approach presented here is more efficient in convergence performance, and the planned route requires lower performance of AUVs.

Keywords

Autonomous underwater vehicle route planning particle swarm optimization radial basis function metropolis criterion

Introduction

With the increasing demand for marine research and development, autonomous underwater vehicles (AUVs), as a new underwater transport platform with the capability of autonomous planning and navigation, have become an important unmanned carrier for the exploration and exploitation of marine resources (Blidberg, 2001). Owing to the complexity and variety of the marine environment, the abilities of route planning and obstacle avoidance are the foundation of autonomous navigation and operation of AUVs. Therefore, research on AUVs’ route planning method helps to raise the autonomy of AUVs and improve the efficiency of marine exploration (Das et al., 2015; Sahu and Subudhi, 2016).

Since the 1970s, the research of the AUVs route planning methods have been paid more attention by researchers, and a variety of AUVs route planning methods have been proposed. At present, the AUVs route planning methods are generally divided into two categories: the graph search method and the route search method.

When the AUVs are in a known environment without unknown obstacles, the route can be planned with the geometry based on the known environmental model. The geometric AUVs route planning methods including Free Space Method, Visibility Graph, Voronoi Graph Method, Grid Method, Cell Tree Representation, and so forth. For these methods, the mission space needs to be known, and the planned routes are based on the static environment model without considering the changes (Mahmoudzadeh et al., 2016; Petres et al., 2007).

As a result of the complex marine environment, such as incomplete seabed topographic map in AUVs working space, and the influence of marine biological swimming on the route and other conditions, the route search algorithms are usually adopted to plan the route for AUVs. At first, a rough global route is planned, and then gradually corrected the route during the movement. Such route planning algorithms are represented by heuristic search algorithms and artificial intelligence search algorithms. The common heuristic search algorithms include artificial potential field, A* algorithm and D* algorithm (Carrol et al., 2002; Cui et al., 2016). These heuristic search algorithms can find a feasible and optimal route without any collision with the environment model and have a simple and intuitive calculation process.

However, when the environment is complex and enormous, the calculation process is more complex and less efficient, and the search procedure can easily result in failure. Artificial intelligence (AI) algorithms include genetic algorithm, ant colony algorithm, simulated annealing algorithm, neural network algorithm, particle swarm optimization (PSO) algorithm, and so forth. But these artificial intelligence algorithms are prone to falling into the local optimal problem (Ding et al., 2005; Li et al., 2013; Liu et al., 2012; Zhang, 2006). Comparing these AI algorithms, PSO algorithm is simpler in computation and faster in convergence rate, which makes route planning more efficient. So, the PSO algorithm is always used as the basic algorithm for AUVs’ route planning (Clerc and Kennedy, 2002).

Because of the characteristics of the PSO optimization algorithm, the planned routes are mostly composed of discrete points. If these discrete points are not effectively smoothed, the route tracking control will be extremely difficult. Therefore, the planned route needs to be smoothed and the discrete control points need to be connected with continuous curves. At present, the most used curve fitting method is the B-Splines interpolation algorithm, but the B-spline interpolation can only be forward-smoothed, and only considers the influence of several points around the smooth point (Foo et al., 2009). Because the smooth is forward, which means the process is from the start point to the end, the smoothness for the route is not excellent. There are the same forward-smoothed problems in particle filter, Kalman filter, and so forth (Gadsden et al., 2009). In order to solve this problem, we introduce radial basis function (RBF) to interpolate the function. The RBF can approximate any continuous function with incredible precision (Er et al., 2002). Therefore, the smoothing effect is better than the B-splines. And RBF turns discrete solutions into continuous ones while preserving the original planning effect, eliminating random errors of discrete solutions, reducing the physical performance requirements, and forming the route of AUVs.

Aiming at the problem of route planning for AUVs, we propose the fusion algorithm of RBF and PSO to realize the route planning in the complicated marine environment, and plan the route for AUVs under the combination of mission constraints, unexpected threats and ocean current influence. In this paper, the second section expounds the mission environment model for AUVs, and designs the constraints model and the fitness function. Furthermore, Section III displays the fusion algorithm based on the basic PSO algorithm, metropolis criterion and RBF algorithm. In the fourth section, the simulation and analysis of the designed algorithm is carried out, and the correctness, feasibility and environmental adaptability of the algorithm are verified by simulation.

Mathematical description of the problem

Basic assumptions

Center of Mass (Centroid), Geometric Center, and Buoyancy Center are at the same point;

In the route planning process, only the movements of centroid in the horizontal orientation (yaw) and vertical orientation (pitch) are considered, the rest of the attitude movement is neglected ( $p = q = 0$ );

In the route planning process of AUVs, set the movement for uniform movement, and the speed is $v_{a}$ , and its direction is the tangent direction of the route (Zhuang et al., 2016).

Figure 1 shows the AUV motion diagram, where $E - ξ η ς$ means the fixed coordinate system, and the $O - xyz$ presents the moving coordinated system.

Figure 1.

The AUV motion diagram.

The fixed coordinate system: the original point is optional for the earth, $E ξ$ is in horizontal plane, and the main heading of AUV is positive. $E η$ is located on the horizontal plane and $E ξ$ is rotated $90 \circ$ clockwise according to the right hand rule; $E ς$ is perpendicular to $ξ E η$ plane, and the direction to the earth center is positive.

The moving coordinated system: the gravity center of the AUV is generally selected as the origin O; axes ox, oy, oz respectively are the intersection of the horizontal, transverse and longitudinal sections through the O point of the AUV, and the heading of the ox pointing to the heading of AUV is positive, and others are according to the right hand rules.

Environment (constraint) modeling

Constraint modeling in the marine environment is to describe the mission environment using a functional simulation method prior to route planning. Because of the complicated marine environment, AUVs need to consider a variety of natural environment constraints (currents, storms, seafloor topography and moving fish) and mission environment constraints (such as ships, mines and other threats). In view of the above environmental constraints, the complex marine environment is expressed as the following categories of constrained regions, which are simulated respectively by using function models (Li, 2014; Qian, 2009).

(1) Restricted regions

Restricted regions means a physical space where the AUVs cannot enter or pass through, such as islands, reefs, no-navigate region and underwater mountains. As shown in Figure 2, the restricted regions are represented by the convexities of the envelope according to equation (1), and the parameters are shown in Table 2. When the AUV is planning a route, the route cannot enter these bumps, so the route needs to pass around the restricted regions or pass through the bugle.

Figure 2.

Digital map simulated by mathematical functions.

In this paper, the restricted regions are enveloped into mountain ridge, and a mathematical model is used to describe the digital terrain

z_{i} (x, y) = \sum_{i = 1}^{n} h (i) \times \exp [- (x - x_{0} (i)) / x_{i} (i) - (y - y_{0} (i)) / y_{i} (i)]

(1)

Where $x_{0} (i), y_{0} (i)$ denote the central coordinates, $x_{i} (i), y_{i} (i)$ respectively mean tilt rate of the $X, Y$ axis, $h (i)$ presents the relative height. All of the parameters are used to describe the $i th$ convexity. And n means the number of convexities.

(2) Ocean current region

In the route planning of AUV, the existence of ocean current will have an impact on the direction and speed of AUV’s navigation, making the difference between its actual route and planned route, thus affecting the navigation of AUV. Therefore, it is necessary to take full consideration of the influence of the ocean current in the AUV route planning method. As shown in Figure 3, the horizontal flow of the currents is merely considered, without considering the vertical flow of current (Mao, 2006).

Figure 3.

Horizontal ocean current model (the speed is $v_{s}$ , counter-clockwise orientation).

In this paper, the discrete function is used to represent the ocean current, and the working space of AUV is set as a two-dimensional discrete space in the Descartes coordinate system. In the plane space, any point Q can be defined as $Q = Q (i, j), 0 < i < m, 0 < j < n$ , where $i, j$ mean the position coordinates in the AUV working plane, $m, n$ respectively represent the maximum coordinates of $X, Y$ axis. The velocity of each discrete point is $v_{c} = 2$ , then the angle between the direction of the ocean current and the x axis at any point is:

θ = \frac{π}{2} + \tan (\frac{y}{x})

(2)

Therefore, the velocities at $x, y$ axes respectively are $v_{sx} = v_{s} \sin θ, v_{sy} = v_{s} \cos θ$ .

When the AUV passes through the ocean current area, the heading of the vehicle needs to adjust to complete the route assignment in the direction of the composite with the ocean current. When the AUV passes through the current area, the velocity is shown in Figure 4. AUV has uniform motion, with a velocity of $v_{a}$ , and the angle between the direction of AUV’s velocity and the x axis is $θ_{2} = \arctan (\frac{y_{i + 1} - y_{i}}{x_{i + 1} - x_{i}})$ . The speed of the AUV on the $x, y$ axis is $v_{a} \sin θ_{2}$ , $v_{a} \cos θ_{2}$ , respectively. Based on the known velocity of AUV and ocean current respectively, the real velocity and the direction of the AUV in the ocean current can be calculated. Then the energy consumption can be considered as an evaluation index for route planning.

Figure 4.

Schematic diagram of the velocity of AUV.

(3) Threat regions

In complex ocean environments, a large number of enemy forces (such as warships, submarines, etc.) deployed in the ocean often pose a threat to the safe navigation of AUV. Therefore, it is necessary to model the threat regions prior to the route planning, and to avoid the threats during the planning process. Some threats are shown in Figure 5. There are three main types of danger that may exist in the working ocean area of AUV according its working depth. The first type of threat comes from ships floating on the sea surface, such as ships with sonar, floating sonar, and so forth. The second type of threat is in the water, such as submarines, moving fishes, and so forth. The last type of threat is natural threats existing on the seabed. Therefore, there are three main threat models:

Lower half ellipsoid model

S_{th} = {P (x, y, z) | (x, y, z) \in S, (z \in [z_{0} - r, z_{o}] \cap [{(x - x_{0})}^{2} + {(y - y_{0})}^{2} + {(z - z_{0})}^{2}] \leq r^{2})}

(3)

Ellipsoid model

S_{th} = {P (x, y, z) | (x, y, z) \in S, (z \in [z_{0} - r, z_{o} + r] \cap [{(x - x_{0})}^{2} + {(y - y_{0})}^{2} + {(z - z_{0})}^{2}] \leq r^{2})}

(4)

Upper half ellipsoid model

S_{th} = {P (x, y, z) | (x, y, z) \in S, (z \in [z_{0}, z_{o} + r] \cap [{(x - x_{0})}^{2} + {(y - y_{0})}^{2} + {(z - z_{0})}^{2}] \leq r^{2})}

(5)

Where, $S_{th}$ is the scope of the threat region; $(x_{0}, y_{0}, z_{0})$ is the center of the ellipsoid; and r is the radius of the ellipsoid.

Figure 5.

The threat model in the marine environment.

Other constraints

In the process of AUV route planning, except considering the environment, threats, terrain and other factors, it is necessary to consider the physical performance, the safety of navigation, concealment and so on. Therefore, the planned route needs to satisfy many factors as shown in Table 1.

Table 1.

The constraints of the vehicle.

Num.	Category	Constraints	Equations
i	Physical capability	Pitch angle	$α - \arccos \frac{a_{i}^{T} a_{i + 1}}{\| a_{i} \| * \| a_{i + 1} \|} > 0, (i = 2, \dots, n - 1)$
ii	Physical capability	Yaw angle	$\tan θ - \frac{\| b_{i} \|}{\| a_{i} \|} > 0, (i = 2, \dots, n)$
iii	Physical capability	Minimum track length	$l_{i} - l_{min} > 0, (i = 1, 2, \dots, n)$
iv	Conceal constraint	Height	$H_{max} - H_{i} > 0 and H_{i} - H_{min} > 0, (i = 1, 2, \dots, n)$
vi	Mission requirement	voyage	$L_{max} - \sum_{i} ‖ l_{i} ‖ \geq 0, (i = 2, 3, \dots, n)$

Table 2.

Convexities parameter settings.

No.	Position		Height	Tilt
No.	$x_{0}$	$y_{0}$	Height	$x_{i}$	$y_{i}$
0	30	100	8.0	25	20
1	120	160	6.0	20	25
2	165	100	9.2	25	20
3	40	160	8.0	25	20
4	120	40	5.2	25	25
5	60	40	7.6	20	25
6	100	100	6.0	25	20

where $α$ , $θ$ respectively denote the yaw angle and pitch angle, and $H_{max}$ , $H_{min}$ denote the max and min height, $L_{max}$ means the farthest working distance.

Fitness function

The aim of route planning is to find a optimal route from the starting point to the destination with shortest navigation time and maximum survival probability. It takes a lot of factors into consideration, such as real time, comprehensive effects of threats, topographies, AUV’s performance, mission requirements for example. Therefore, the fitness function must consider the sailing time, route safety, and so forth.

Therefore, the fitness function f is designed as

f = α \sum_{i = 1}^{n - 1} ρ_{i} l_{i} + β \sum_{i = 1}^{n} ϕ_{i} z_{i}

(6)

Where n denotes the number of nodes in the planned route, $α, β$ represent the coefficient of fitness factors, $l_{i}$ presents the length between the $i th$ and $(i + 1) th$ points, $z_{i}$ is the height of the $i th$ point, $ρ_{i}$ is the time when the AUV pass through the route, $ϕ_{i}$ is the impact of being founded from the AUV’s height. Because of the uniform movement of AUV, for convenience, $ρ_{i}$ is equal to 1, and $ϕ_{i}$ is set as 1, too.

PSO algorithm and RBF

PSO has the advantages of less parameter setting, simple structure and inherent parallelism. Therefore, it is especially suitable to solve complex optimization problems with a lot of nonlinear, non-differentiable and multi-peaks. However, the PSO easily falls into the local optimal solution and the solutions are generally discrete (Rajabi et al., 2014).

In this paper, aiming to solve the problems of PSO algorithm during the route optimization, the PSO algorithm is improved to adapt to complex marine environment and emergencies. The proposed route planning method which is based on PSO algorithm, Metropolis criterion and RBF is shown in Figure 6, which divides the improved PSO (IPSO) algorithm into GPSO (Global PSO algorithm) and LPSO (Local PSO algorithm) according to the route optimization scope. These two PSO algorithm processes are the same and the difference is granularity while dealing with the problem. In this paper, the Metropolis criterion is proposed as the new acceptance criterion of PSO to improve the PSO problem of easily falling into the local optimal problem. Then we use the RBF to interpolate the planned route and reduce the physical performance requirements to AUV. The same for the complex and volatile marine environment characteristics, a local PSO algorithm is designed. In the event of a sudden threat, the route planning algorithm turns into the LPSO processing flow, the re-planning route without entering the threat region will be planned.

Figure 6.

Route planning algorithms diagram.

Particle swarm optimization algorithm

The PSO algorithm can be described as: there are m particles in the D dimension space to search, and the velocity and position of $j^{th}$ particles in the $i^{th}$ iteration are $v_{i, j}$ and $x_{i, j}$ , respectively. Its optimal position in D dimension is $p_{p, j}$ , and the global optimal position of the entire population in the D dimension is $p_{i, g}$ . And the update of the position and velocity are as follows

\begin{matrix} v_{i + 1, j} = w \times v_{i, j} + c_{1} \times r_{1} \times (p_{p, j} - x_{i, j}) \\ + c_{2} \times r_{2} \times (p_{i, g} - x_{i, j}) \end{matrix}

(7)

x_{i + 1, j} = x_{i, j} + v_{i + 1, j}

(8)

Where $i \in [1, m]$ , $j = 1, 2, \dots, m$ ; $c_{1}$ , $c_{2}$ are learning factor; $r_{1}$ , $r_{2}$ are the random number in $(0, 1)$ , $v_{i, j}$ denotes the velocity of $j^{th}$ particle in the $i^{th}$ iteration, $v_{i} \in [- v_{max}, v_{max}]$ , $v_{max}$ is constant.

Figure 7 shows the particle’s position update process according to the updated equations (7)–(8). $x_{i}$ , $v_{i}$ are the position and velocity of the $i th$ particle, and $x_{i + 1}$ , $v_{i + 1}$ are the updated position and velocity. Update and search the better results until the search for a satisfactory solution or to a certain number of iterations.

Figure 7.

Particle position update in PSO algorithm.

There are three parts on the right side of equation (7) according to Figure 7. The first part is the velocity part $w \times v_{i, j}$ , which represents the inheritance of the previous velocity, and prevents the algorithm from falling into the local optimum. The second part is the cognitive part $c_{1} \times r_{1} \times (p_{p, j} - x_{i, j})$ , which represents the learning process of the particles based on their own experience, reflecting the cognitive ability of the particles, making the particles have a global search ability. The third part is social part $c_{2} \times r_{2} \times (p_{gd} - x_{id})$ , which presents the information sharing between particles, reflects the social ability of particles, and indicates that the particles share the best location of the whole group, and it can accelerate the convergence.

Because of the inherent characteristics of PSO algorithm, such as easily falling into local optimum, and incomplete of the local search, scholars proposed various improvements, mainly to adjust the inertia weight and learning factor so that the algorithm can balance between global search and local search.

The inertia weight, which determines the particle’s convergence rate, is represented by w. When w decreases with the increase of the iterations number, the changing w is conducive to improving the performance of the algorithm, and the equation is as follows (Vafashoar and Meybodi et al., 2016)

w = w_{max} - iter \times \frac{(w_{max} - w_{min})}{Iter}

(9)

Where $w_{min}$ is the minimum inertia weight, and $w_{max}$ is the maximum inertia weight, Iter is the maximum iterations number, iter is the current iterations number.

The improvements of learning factors are introduced in the same way, and the equations are as follows

c_{1} = {c_{1}}_{max} - iter \times \frac{{c_{1}}_{max} - {c_{1}}_{end}}{Iter}

(10)

c_{2} = {c_{2}}_{max} - iter \times \frac{{c_{2}}_{max} - {c_{2}}_{end}}{Iter}

(11)

Where, ${c_{1}}_{max}, {c_{2}}_{max}$ are the maximum learning factors, and $c_{1 min}, c_{2 min}$ are the minimum learning factors.

The improved strategy of the PSO algorithm in this paper can effectively improve the situation of local convergence, and it has significantly improved in the optimization accuracy and stability.

Metropolis criterion

Metropolis criterion is a strategy for receiving new states. And the process is described in a thermos physical method. The physical system tends to be in a lower energy state, but the heat movement prevents it from falling into the lowest state. Therefore, we need to focus on those important contributions to achieve better results.

First, initializing particle state as the particle’s current state, and the energy is $E_{i}$ .After a random change in a randomly chosen particle, the energy of the new state j is $E_{j}$ . If $E_{j} < E_{i}$ , the new state $E_{j}$ will be accepted as an important state. If $E_{j} > E_{i}$ , the thermal motion will be considered to judge whether the new state is an import state, it depends on the probability. From the Gibbs canonical ensemble, we can know that the ratio of the probability of the state i and the state j is equal to the ratio of the corresponding Boltzmann factor, and the equation is as follows

r = \exp (\frac{E_{i} - E_{j}}{kT}) > ξ

(12)

where $κ$ is Boltzmann factor, T is the initial temperature, r is less than 1. $ξ = rand$ , if $r > ξ$ , then the state j is more important.

Compared with the state i, if the new state j is more important, the new state will be the real-time state instead of state i, otherwise, maintain the original state.

The above new accept criterion is called metropolis criterion, which can significantly improve the artificial intelligence algorithm to fall easily into the local optimum.

RBF

RBF can approximate any non-linear function and can handle difficult-to-interpret regularities in the system. And it has good generalization ability and fast learning convergence speed. Therefore, it has been successfully applied in nonlinear function approximation, time series analysis, data classification, pattern recognition, information processing, image processing, system modeling, control, fault, and so forth (Deng et al., 2013; Su et al., 2013).

The structure of an RBF neural network consists of three layers, as shown in Figure 8:

The input neuron layer;

The hidden neuron layer;

The output neuron layer.

Figure 8.

RBF neural network structure.

During the learning process, RBF neurons firstly calculate the distances between input nodes and center nodes and then non-linear transformations will be applied to this distance. Output layer and hidden layer perform different learning tasks. Output layer is to adjust the linear weights, using a linear optimization strategy, and thus learn faster. The hidden layer is to adjust the parameters of the transfer function, using a non-linear optimization strategy, which has a slow learning speed.

The Guass function is used as the transfer function of the RBF

R_{i} (x) = \exp (- {‖ x - c_{i} ‖}^{2} / 2 σ_{i}^{2}), i = 1, 2, \dots, m

(13)

where x denotes the input vector; $c_{i}$ represents the center of the base function, and has the same vector as x, $σ_{i}$ is a variable of the $i th$ perception, it determines the width of the base function around the center point; m is the number of the perceptive units (the number of the hidden layer neuron). $‖ x - c_{i} ‖$ is the norm of the vector $x - c_{i}$ , and it usually expresses the distance between x and $c_{i}$ . $R_{i} (x)$ has a unique maximum at $c_{i}$ . With the increase of $‖ x - c_{i} ‖$ , $R_{i} (x)$ will decrease to 0. Only a few neurons, which are close to the center, are activated.

RBF uses Guass function as the transfer function of hidden layer, and the hidden layer is used to achieve the non-linear mapping of $X \to R_{i} (x)$ , output layer to achieve linear mapping of $R_{i} (x) \to y_{k}$ . The inputs are $X = (x_{1}, x_{2}, \dots, x_{j}, \dots, x_{n})$ , and the actual outputs are $Y = (y_{1}, y_{2}, \dots, y_{k}, \dots, y_{p})$ , then the output layer of k neuron network output is

{\hat{y}}_{k} = \sum_{i = 1}^{m} ω_{ik} R_{i} (X) k = 1, 2, \dots, p

(14)

Where $ω_{ik}$ is the connection weight of the $k th$ neurons in output layer with the $i th$ unit in hidden layer, $R_{i} (x)$ is the transfer function of $i th$ neuron in hidden layer. Therefore, when the cluster center $c_{i}$ and weight $ω_{k}$ of RBF is determined, we can get the corresponding output value to the certain input.

To illustrate the advantages of RBF, several filter algorithms, such as Kalman filter, B-Spline interpolation and RBF interpolation are compared. It can be seen clearly that the RBF has the best performance in interpolation fitting both linear and non-linear functions in Figure 9. And the Kalman filter has a better performance than B-Spline interpolation in linear function, while the B-Spline performs better in the non-linear function.

Figure 9.

Compare among RBF, Kalman filter and B Splines on smoothness.

Route planning algorithm based on improved PSO

Global route planning algorithm

Although the PSO algorithm has many advantages, such as easy to understand, fast convergence and less parameter settings, there are still some problems such as easy to fall into the local optimum, the planned route is not smooth, and so forth. We proposed a fusion algorithm based on PSO algorithm, metropolis criterion and RBF. The metropolis criterion is used as new acceptance criterion to improve the problem of easily falling into local optimum. RBF is used to interpolate the planned route, which can not only change the discrete points into a continuous route, but also eliminate the random errors caused by the discreteness.

Based on the contents introduced above, we apply the fusion algorithm based on the PSO algorithm and RBF to AUVs’ route planning, and the algorithm has been summed up by the flow chart shown in Figure 10. Also, the proposed distributed algorithm for AUV is implemented in the following specific steps:

Step 1. Initialize parameters of the PSO algorithm.

Step 2. Initialize the particle swarm, including population size n, and particle’s m-dimension position $x_{i, j}$ and velocity $v_{i, j}$ , where the i means the iteration number, and j presents the number of particles.

Step 3. Introduce the fitness function, and initialize the local optimal value $p_{i, p}$ and global optimal value $g_{i, g}$ .

Step 4. Update the location $x_{i, j}$ and velocity $v_{i, j}$ with equations (7)–(8).

Step 5. Interpolate the position vector $x_{i, j}$ with RBF, and constraint the interpolated position.

Step 6. Evaluate the positions with fitness function.

Step 7. Update the local/global optimal value based on the Metropolis criterion.

Step 8. If satisfied with the terminating condition, output the optimal route. If not, return to step 4.

Figure 10.

Flow chart of global route planning algorithm based on the fusion algorithm.

Local route planning algorithm

Compared with the global route planning algorithm, the coordination of optimization of the route and route planning time is the key to the online local route planning. Based on improved PSO algorithm, the global route planning algorithm provides a global optimization reference route for online planning. In actual route planning, with the guidance of the global route, AUV can avoid various obstacles that threat the safety of the route as early as possible. However, in practice, AUVs do not strictly operate on the reference route. According to the current environment probed by the sensor and the feedback running state from the control system, the route planning system determine the front route whether there are emergent threats and obstacles. And then the probed data will be transmitted into the digital map as obstacles. Local route planning will work, re-planning a local route, completing the modification of waypoints and control instructions before the AUVs reach new threat areas. This can improve the response ability of AUV to the surrounding and changing situation and avoid new threats. As shown in Figure 11, the broken line in the picture is the predetermined route, and the solid line is the re-planning route.

Figure 11.

Re-planning scheme.

Where $Δ T$ is the re-planning allowable time range, $t_{M_{i}}$ is measure time of the $i th$ sensor, and $t_{P_{i}}$ is the cost time of $i th$ re-planning process. In the time of $t_{i}$ , the AUV will implement the $(i - 1) th$ planned route (the broken line). This process will continue to $t_{i} + Δ t_{i}$ . When $Δ t_{i} = t_{M_{i}} + t_{P_{i}}$ , the AUV will operate along the route (the solid line) re-planned according to the environmental information until reach $(i + 1) th$ route. It can be seen from Figure 11, if $Δ T > Δ t_{i}$ , then the route updates can be calculated by incorporating new information about the changing marine environment. And if $Δ T$ is short enough, environment information is fed back to the planner in real time, ensuring that planned routes are safe and efficient. However, the shorter the planning window, the faster algorithms are required.

To solve the problem, this paper designs a fast, local route planning algorithm for emergent environmental threats. Based on the global optimization route, the local route planning algorithm is to determine whether the route is safe under the emergent threat, and re-planning the threatened route segments. The re-planning method adopts the improved PSO route planning method with the RTS smoother. The specific algorithm flow chart is shown in Figure 12.

Figure 12.

Local route planning algorithm.

Simulation

In this paper, the function simulating method of digital elevation map is used to establish the threats models. And the AUV route planning is implemented with GPSO modified by RBF and LPSO modified by RTS smoother. In order to verify the accuracy of the designed algorithm, simulation parameters are designed based on the built virtual model, as shown in Table 3 (Zhang et al., 2015).

Table 3.

PSO parameters settings.

Parameter	Value	Parameter	Value
$w_{start}$	0.9	$w_{end}$	0.4
$c 1_{start}$	1.8	$c 1_{end}$	0.4
$c 2_{start}$	2.0	$c 2_{end}$	0.4
N	40	M	300
temp	1000	Iter	300

where w represents the inertia weight, $c_{1}, c_{2}$ respectively represent learning factor, which can be obtained by solving equations (9)–(11), N presents the swarm size, M means the particle’s dimension, temp represents the original temperature in Metropolis criterion, and Iter represents the number of iterations.

The specific parameters descriptions are shown in section 2.2. The size of the mission space is $2000 \times 2000 \times 200$ $(m^{3})$ , the starting point is $(2, 2, - 19)$ , the target point is $(198, 198, - 19)$ . At the same time, to ensure the concealment of the AUV during the transfer process, the complexity of the seabed environment needs to be fully utilized. In other words, the AUV should be as close as possible to the sea bed under the premise of preventing collisions with the sea bed and set its height constraint as $4 ~ 10 m$ .

RBF adopts MATLAB’s newrb function to design an approximate RBF. Its invocation format is

[net] = newrb (P, T, GOAL, SPREAD, MN)

where P is a matrix composed of input vectors, T presents the matrix consisting of target classification vector, Goal represents the mean square error goal, SPREAD means the spread speed of RBF, MN means the maximum number of neurons.

In this paper, the parameters are set as [net]=newrb(P,T,0,100,10) after testing many times.

To discuss the superiority of the proposed algorithm (improved PSO with RBF interpolation, IPSO), this paper introduces three other comparing algorithms, including basic PSO algorithm, improved PSO algorithm with B-spline interpolation (BPSO), and improved PSO algorithm based on Kalman Filter (KPSO). These four algorithms are compared with each other to illustrate the superiority.

Route planning without considering the impact of ocean current

Considering the environment model constraints without the influence of ocean current, the results based on the fusion algorithm of RBF and PSO algorithm (IPSO) are shown in Figures 13 –16. Figure 13 is a three-dimensional schematic diagram of the route planned by the proposed global route planning algorithm. It can be clearly seen from the figure that the proposed algorithm can plan a collision-free route under the environment model and constraint conditions. And compared with other algorithms, the smoothest route is planned by IPSO algorithm. As can be seen from Figure 14, among the 100 iterations, the route planned by IPSO is significantly better than the other three algorithms, and the final solution is also the best among these four algorithms. Figure 15 shows the three-dimensional view of the route planned by IPSO and the projection in the three planes. It is more intuitive that the route planned by IPSO is smooth in the three planes, which means the route requires a lower performance for the AUVs. Also, in Figure 16, the variations of yaw and pitch angles with turning nodes are displays to evaluate the smoothness of the planned route by several algorithms. It is obvious that the angles of the route planned by IPSO, which is improved with RBF, are smaller than others. In other words, the route planned by IPSO is the smoothest, indicating that the IPSO algorithm is the best algorithm within these several algorithms for AUVs’ route planning.

Figure 13.

Three-dimension route planned by AUV.

Figure 14.

Fitness value of iterative.

Figure 15.

The projection of planned route.

Figure 16.

The variations of yaw and pitch angles with the nodes.

Consider the effects of currents

Under the existing environment models and constraints, the proposed algorithm can still complete the corresponding route planning mission considering the influence of ocean current. Figure 17 is a schematic plan of the proposed algorithm. The dotted curve in the figure is the result of the route planning of the AUV considering the influence of the ocean current and the solid curve is the result without considering the ocean current. It can be clearly seen that in the first half of the AUV routes are similar under the strong environmental model and constraints. But under the weak environment constraints, the route planning considering the influence of the current can make adaptive adjustments to the current, so that it can reduce the impact of ocean currents on AUV route planning. Figure 18 shows the projected contrast of the planned route in three planes in both cases, so as to better characterize its planning features. Figure 19 shows the extra energy (higher fitness value) consumed to overcome the effects of ocean currents to reach the destination.

Figure 17.

The planned route considering current influence.

Figure 18.

Projection comparison.

Figure 19.

Fitness value of iterative process.

Route planning method in case of sudden threat

When encountering an emergent threat, it is necessary to re-plan the route that was in the threat area. The local route planning algorithm has been introduced in section 3.4.2. And some simulation has been done to verify the accuracy of the algorithm.

The emergent threat setting is shown in Table 4.

Table 4.

The emergent threat setting.

No.	Category	Coordinate			Impact radius (r)
No.	Category	x	y	z	Impact radius (r)
0	Ellipsoid model	10	20	-6	3
1	Ellipsoid model	80	60	-13	3
2	Ellipsoid model	100	100	-15	3
3	Upper half Ellipsoid model	150	130	-18	9

As shown in Figure 20 (three-dimension graph), the route can be planned by the proposed local route planning algorithm in emergent threats. The dotted line in the figure shows the re-planning route when the planned route (the solid lines) encountered emergent threats. It can be seen in Figure 20 that the planned route does not intersect with the emergent threat, and the entire planned route is smooth and reliable, which means that the proposed algorithm is feasible and effective. As shown in Figure 21, the planned route is smoother and still within the AUV physical performance constraints at the point of attachment, which can satisfy the physical performance requirements of the AUVs. Figure 22 shows the variation of the fitness value with the increase of iteration number in re-planning process.

Figure 20.

The IPSO route planning result for emergent threats.

Figure 21.

Projection of local route planning algorithm for unexpected threat.

Figure 22.

Fitness value curve with iterations in re-planning.

Conclusions

In this paper, a modified PSO algorithm is proposed for AUVs to plan the mission route in a complex marine environment. The proposed algorithm based on the fusion of RBF and PSO algorithm can plan the path for AUVs. Compared with BPSO and KPSO, the planned route is relatively smooth, which can satisfy the requirements of tracking control for AUVs. Besides, the fusion of PSO algorithm with RBF can complete the AUVs global route planning, and the comprehensive performance of the planned route is better; the fusion of PSO algorithm with RTS smoother has higher computational efficiency and can quickly plan out near-optimal routes for AUVs to avoid emergent threats.

Footnotes

Declaration of conflicting interest

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the Fundamental Research Funds for the Central Universities (No. HEUCFP201770), the Natural Science Foundation of Heilongjiang Province (No. F2017005), the National Natural Science Funds (No.11772185), the Harbin Science and Technology Innovation Talent Youth Fund (No.2015RQQXJ003), Shanghai Talent Plan Project (No. 16QB1403500).

References

Blidberg

(2001) The development of autonomous underwater vehicles (AUV); a brief summary. IEEE Icra 17(5): 209–212.

Carroll

Mcclaran

Nelson

Barnett

(2002) AUV path planning: An A* approach to path planning with consideration of variable vehicle speeds and multiple, overlapping, time-dependent exclusion zones. In: Proceedings of the 1992 Symposium on Autonomous Underwater Vehicle Technology, Washington, USA, 2–3 June, pp. 79–84. IEEE.

Clerc

Kennedy

(2002) The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Press IEEE Transactions on Evolutionary Computation 6(1): 58–73.

Cui

Yan

(2016) Mutual information-based multi-AUV path planning for scalar field sampling using multidimensional RRT. IEEE Transactions on Systems Man and Cybernetics Systems 46(7): 993–1004.

Das

Subudhi

Pati

(2015) Co-operative control coordination of a team of underwater vehicles with communication constraints. Transactions of the Institute of Measurement and Control 38(4): 463–481.

Deng

Irwin

Fei

(2013) Two-stage RBF network construction based on particle swarm optimization. Transactions of the Institute of Measurement and Control 35(1): 25–33.

Ding

Jiao

Bian

Wang

(2005) AUV local path planning based on virtual potential field. In: IEEE International Conference Mechatronics and Automation, Niagara FAlls, Canada, 29 July–1 August 2005, Vol. 4, pp. 1711–1716

Toh

(2002) Face recognition with radial basis function (RBF) neural networks. IEEE Transactions on Neural Networks 13(3): 697–710.

Foo

Knutzon

Kalivarapu

et al . (2009) Path planning of unmanned aerial vehicles using b-splines and particle swarm optimization. Journal of Aerospace Computing Information and Communication 6(4): 271–290.

10.

Gadsden

Dunne

Kirubarajan

(2009) Comparison of extended and unscented kalman, particle, and smooth variable structure filters on a bearing-only target tracking problem. Proceedings of SPIE – The International Society for Optical Engineering 7445: 74450B1–74450B13.

11.

(2014) Three-dimensional path planning of robots in virtual situations based on an improved fruit fly optimization algorithm. Advances in Mechanical Engineering, (2014-11-11): 1–12.

12.

Zhao

Huang

et al . (2013) A wavelet-based grey particle filter for self-estimating the trajectory of manoeuvring autonomous underwater vehicle. Transactions of the Institute of Measurement and Control 36(3): 321–335.

13.

Liu

Wei

Gao

(2012) 3D path planning for AUV using fuzzy logic. In: International Conference on Computer Science and Information Processing, IEEE, Xi’an, China, 24–26 August 2012, pp. 599–603.

14.

Mahmoudzadeh

Powers

Sammut

et al . (2016) Optimal route planning with prioritized task scheduling for AUV missions. In: IEEE International Symposium on Robotics and Intelligent Sensors, Langkawi, Malaysia, 18–20 October 2016, pp. 7–14.

15.

Mao

(2006) The research of global path planning of autonomous underwater vehicle. Dissertation. Harbin Engineering University.

16.

Petres

Pailhas

Patron

et al . (2007) Path planning for autonomous underwater vehicles. IEEE Transactions on Robotics 23(2): 331–341.

17.

Qian

(2009) Research on local path planning with learning ability for AUV. Dissertation. Harbin Engineering University.

18.

Rajabi

Rezaie

Rahmani

(2014) A novel nonlinear model predictive control design based on a hybrid particle swarm optimization-sequential quadratic programming algorithm: Application to an evaporator system. Transactions of the Institute of Measurement and Control 38(1): 17–39.

19.

Sahu

Subudhi

(2016). Potential function-based path-following control of an autonomous underwater vehicle in an obstacle-rich environment. Transactions of the Institute of Measurement and Control 39(8): 1236–1252.

20.

Zhu

Liu

(2013) An online outlier detection method based on wavelet technique and robust RBF network. Transactions of the Institute of Measurement & Control 35(8): 1046–1057.

21.

Vafashoar

Meybodi

(2016) Multi swarm bare bones particle swarm optimization with distribution adaption. Applied Soft Computing 47(1): 534–552.

22.

Zhang

Tang

Hua

Guan

(2015) A new particle swarm optimization algorithm with adaptive inertia weight based on bayesian techniques. Applied Soft Computing 28(C): 138–149.

23.

Zhang

(2006) A hierarchical global path planning approach for AUV based on genetic algorithm. In: The 2006 IEEE International Conference Mechatronics and Automation, Luoyang, China, 25–28 June 2006, Vol. 2, pp. 1157–1160.

24.

Zhuang

Sharma

Subudhi

et al . (2016) Efficient collision-free path planning for autonomous underwater vehicles in dynamic environments with a hybrid optimization algorithm. Ocean Engineering 127(1): 190–199.