1. Introduction

With the increasing demands of marine monitoring and exploration, the unmanned surface vessel (USV) becomes widely used in water area environmental inspection. The main research direction in the application of the USV is flight path planning. The purpose of path planning is to obtain a scientific, safe, and concise path in a specific environment. As the USV navigation environment deteriorates, the problems needed to be solved in USV path planning are becoming harsher, and the amount of calculation is also increasing, so the path planning problem gets trickier. In recent years, many studies has have been done for USV flight path planning and swarm intelligence algorithm has been popularly used, including particle swarm optimization (PSO) (Xin et al., 2019; Krell et al., 2022), artificial fish swarm algorithm (Zhao et al., 2022), ant colony algorithm (Wang et al., 2022), genetic algorithm (GA) (Park et al., 2021), and etc. Among these intelligent algorithms, particle swarm optimization is the most widely used in the field of automatic control because of its simple principle, fewer parameters, fast optimization speed, small amount of calculation and other advantages (Khayati et al., 2019). At present, the application of particle swarm optimization algorithm in robot path planning is very active (Chen and Sun, 2021; Wu et al., 2022; Xiao et al., 2022), but the research on USV flight path planning is still a frontier field. In practical application, due to the irregular, complex and uncertain USV navigation environment, the algorithm is easy to fall into local extreme values, resulting in poor quality of generated paths, waste of time and resources. Therefore, improving the global search ability and robustness of the algorithm becomes a key content in USV flight path planning. The most popular use of PSO for global path planning is genetic particle swarm optimization (GaPSO), which combines the advantages of the genetic algorithm (GA) and the particle swarm optimization algorithm. In Pehlivanoglu (2012), an improved PSO for robot path planning is presented. In Zhang and Xing (2019), GA is combined with the voronoi diagram to generate the optimal path for autonomous unmanned aerial vehicles (UAVs). The applying of GaPSO can reduce the probability of falling into local optimal solutions, however, the global search capability needs to be enhanced. Differential evolution algorithm (DE) has been used in many fields such as intelligent machines, robots, equipments and so on Yang et al. (2011) and Yildiz (2013). Because of its strong global searching ability and high robustness, DE can be used to solve multiobjective, constrained and complex optimization problems.

Compared with genetic algorithms, the global exploration ability of DE is more obvious. However, the accuracy of the optimal solution and convergence speed are affected by the parameter settings and the mutation operations. To get a compromise between the optimal solution accuracy and optimization speed, many studies have been done on the values of the control parameters, including the population size NP, the crossover probability CR, and the scaling factor F. It is well known that the size of the population increases, the probability of finding the optimal solution is higher, however the amount of calculation and computation time may also increase. The value of F has a great influence on the speed of optimization. For a larger F value, the population is more abundant, but the amount of calculation is larger and the computation time is longer. With a smaller F, the optimal solution can be found faster, but the diversity of the population can't be guaranteed, so the algorithm will easily fall into a local optimum value. To obtain appropriate parameters, a lot of studies have been done. In Yildiz (2013), the authors pointed out that F should be set to 0.5. In Li et al. (2019), the authors suggested that F should between [0.4, 0.95]. The values of these parameters are difficult to select to obtain a better performance.

In order to get a better flight path with fast optimization speed and less computation, this paper proposed a discrete particle swarm optimization algorithm with differential evolution algorithm (DeDSO) for USV flight path planning. This algorithm combines the advantages of the conventional particle swarm optimization algorithm and the differential evolution algorithm, so as to enhance the global search ability and improve the path planning efficiency and stability. In order to ensure both high search speed and high precision solution, the scaling factor F in DE is self-adaptive with the iteration.

The remainder of this paper is organized as follows. Section 2 gives the mathematical model of USV automatic inspection problem. Section 3 introduces the working principle of conventional PSO, DE, and the improved DePSO. Section 4 gives the framework and implementation procedure of the DePSO. Section 5 describes the numerical simulation results and comparison. Finally, section 6 gives a short conclusion.

2. Mathematical model of USV automatic inspection problem

Flight path planning is a global optimization problem aims to search the optimal flight path for USVs. When USV is applied in water environment inspection, it is necessary to generate a sailing path. The path planning process of the USV is shown in Figure 1. Firstly, a feasible global path is drawn according to the regional map information by identifying the surrounding environment and the status information of the USVs. Then the ship navigates according to the specified path. During the navigation, the sensors monitor the surrounding environment, and the local path planning is used to avoid obstacles, and then the ship continues to travel according to the original path.

Figure 1. USV path planning process diagram.

The problem to be solved in this paper is to plan a global path for USVs applied in water area automatic inspection. In a certain water area, several sampling points are spread, which will be automatically inspected and sampled by the USVs. The purpose of flight path planning is to generate a route between the starting point and the destination, which ensures that all sampling points are inspected only once except the starting point, and the path formed should meet specific optimization objectives, which is equivalent to the traveling salesman problem (TSP) (Laporte, 2010; Zheng et al., 2022). The TSP model has been mainly used for single vehicle operating situations as described in this paper, and the main idea is to search the optimal path to visit all sampling points.

minf=∑i=1n-1D(i,i+1)+D(1,n)    (1)

The objective function is the key point of an optimization problem. In our design, the optimization objective is demonstrated as function f, and the mathematical model corresponding to n sampling points is defined as Equation (1). Where D(i, i + 1) respects the distance between sampling point “i” and sampling point “i + 1.” In this paper, the USV sampling problem is corresponding to symmetry TSP problem, which satisfies D(i, j) = D(j, i), where i, j ∈ (1, 2, …, n).

3. Improved particle swarm optimization model 3.1. Particle swarm optimization algorithm

In particle swarm optimization, the updating of population tends to be closer to the optimal value. The optimization process of PSO is shown in Figure 2. Particles adjust their speed and direction of motion according to their own historical optimal value Pbest and global optimal value Gbest, and measure the merits of particles by optimizing the fitness value determined by the target, so as to drive the particles to the optimal value (Wu et al., 2017; Rauf et al., 2020).

Figure 2. The optimization process of PSO.

The next generation particle position Xid(t+1) and velocity Vid(t) are calculated through Equations (2) and (3) respectively. In which, Xid(t) is the tth generation particle position; ω is the inertia weight, which determines the optimization speed of the algorithm; c1 and c2 decide the speed for the particle approaching Pbest and Gpest respectively; R1 and R2 are random numbers, and their values range from 0 to 1; In this paper, the fitness represents the length of the USV navigation route, the calculation formula is (4), in which (xi, yi) are the coordinates of the i th and the i+1 th sampling point, respectively. The pseudo code of PSO is presented in Table 1.

Algorithm I: Conventional PSO.

Xid(t+1)=Xid(t)+Vid(t+1)    (2) vid(t+1)=ωvid(t)+c1R1(Pbest-Xid)  +c2R2(Gbest-Xid)    (3) f(x)=∑i=1n-1(yi+1-yi)2+(xi+1-xi)2    (4) 3.2. Differential evolution algorithm

Differential evolution algorithm is a bionic intelligent calculation method which simulates the natural evolutionary law to find the global optimal value. The optimization process of DE is shown in Figure 3. The main body of the algorithm generally includes three steps: mutation, crossover and selection (Yi et al., 2016; Bilal et al., 2020). The pseudo code of DE is presented in Table 2. Three different individual vectors are randomly selected to get a difference vector, denoted as Xr1, Xr2, and Xr3, and the mutation vector Vi was calculated according to Equation (5). The scaling factor F is set to control the influence of difference vector (Xr2-Xr3) on the evolution speed, and the value of F is generally between [0,1].

Figure 3. The optimization process of DE.

Algorithm II: Conventional DE.

Vi=Xr1+F(Xr2-Xr3)    (5)

The function of crossover operation is to hybridize the current individuals of the population with the mutation vector generated by the mutation, and generate new individuals randomly according to a certain probability, as shown in Equation (6). CR is the crossover probability, which determines the size of the hybridization probability, and its value is a real constant between [0,1].

uij(t+1)=,,,]},,,]},,,]},,,,,]}],"socialLinks":[,"type":"Link","color":"Grey","icon":"Facebook","size":"Medium","hiddenText":true},,"type":"Link","color":"Grey","icon":"Twitter","size":"Medium","hiddenText":true},,"type":"Link","color":"Grey","icon":"LinkedIn","size":"Medium","hiddenText":true},,"type":"Link","color":"Grey","icon":"Instagram","size":"Medium","hiddenText":true}],"copyright":"Frontiers Media S.A. All rights reserved","termsAndConditionsUrl":"https://www.frontiersin.org/legal/terms-and-conditions","privacyPolicyUrl":"https://www.frontiersin.org/legal/privacy-policy"}'>