Multiple Task Assignment and Path Planning of a Multiple Unmanned Surface Vehicles System Based on Improved Self-Organizing Mapping and Improved Genetic Algorithm

Abstract

This paper addresses multiple task assignment and path-planning problems for a multiple unmanned surface vehicle (USVs) system. Since it is difficult to solve multi-task allocation and path planning together, we divide them into two sub-problems, multiple task allocation and path planning, and study them separately. First, to resolve the multi-task assignment problem, an improved self-organizing mapping (ISOM) is proposed. The method can allocate all tasks in the mission area, and obtain the set of task nodes that each USV needs to access. Second, aiming at the path planning of the USV accessing the task nodes, an improved genetic algorithm (IGA) with the shortest path is proposed. To avoid USV collision during navigation, an artificial potential field function (APFF) is proposed. A multiple USV system with multi-task allocation and path planning is simulated. Simulation results verify the effectiveness of the proposed algorithms.

1. Introduction

Compared to manned surface ships, unmanned surface vehicles (USVs) have significant advantages when carrying out dangerous and boring tasks. However, there are some limitations when a single USV performs tasks, such as the limitation of maximum range, lack of scalability, etc. These problems can be effectively overcome using multiple USVs. A USV swarm is a typical multi-agent system. A multiple USV system, which is one of the most actively studied topics within multi-agent systems, generally aims to drive multiple agents to meet prescribed constraints on their states [1]. To research the multi-USV system more conveniently, it is divided into two sub-problems: multiple task assignment and path planning.

Recently, there has been progress regarding multiple task assignment in multi-agent systems. For example, a new intelligent multi-task allocation is proposed based upon the self-organizing map (SOM) [2]. The SOM adopts ring topology, with k SOMs for k USVs. In [3], an improved SOM is proposed for intelligent hybrid multi-task allocation of a single USV. However, for a single USV with multi-task allocation, this is equivalent to the path-planning problem, or the traveling salesman problem. In [4], an intelligent self-organized algorithm is proposed to solve a cooperative search–attack mission-planning problem for multiple unmanned aerial vehicles (UAVs). In [5], an integrated multiple autonomous underwater vehicle (AUV) dynamic task assignment and path-planning algorithm is proposed by combing the improved self-organizing map neural network with a novel velocity synthesis approach. In [6], a SOM-based neural network approach is proposed for multiple task assignment of a multi-robot system. In [7], a SOM with the shortest load-balancing constraints is proposed for AUVs. In contrast to our methods, which used distributed methods to deal with multi-task assignment and path planning, a centralized treatment approach is adopted in [2,3,4,5,6,7]. Each SOM corresponds to an object and outputs an ordered task array. Such a solution is theoretically feasible, but not practically applicable.

Path planning is another sub-problem of a multiple USV system. The method has two parts: an exact algorithm and a heuristic algorithm. A deterministic method can provide accurate results, but it takes a long time. A heuristic algorithm improves running speed by sacrificing the calculation accuracy to obtain an approximate optimal solution. In this case, a heuristic algorithm, such as the improved quantum ant colony algorithm [8], order-first split-second approach [9], fast marching method [10], interpolation algorithm [11], virtual spring method [12], improved genetic algorithm [13], artificial intelligence [14], A${}^{★}$ algorithm [15], self-organizing map [16], virtual target approach [17], etc., is mostly used in path planning. GA takes all individuals in a population as the object, and uses randomization technology to search an encoded parameter space efficiently.

Obstacle avoidance is a very important part of path planning. Researchers have paid extensive attention to obstacle avoidance. In [7], a hybrid path-planning approach is proposed to guide AUVs to reach their targets safely. In [15], an artificial potential field-based path-following approach with dynamic collision avoidance is proposed. In [18], a method based on a finite-control set model-predictive control is proposed. In [19], a distributed coordination mechanism is proposed for collision avoidance of multiple ships. In [20], an approach to normalize pseudo-distances is proposed. By ensuring the pseudo-distance was always larger than the safety threshold value, collisions with obstacles were avoided. In [21], a collision-avoidance potential function based on position estimation is proposed. The effectiveness of the collision-avoidance potential function assumes that the estimator has converged to stability. In actual engineering, the stability of the estimator cannot be guaranteed.

Due to the complexity of the multiple USV system, this paper divides it into two sub-problems, namely multi-task assignment and path planning. In the first stage, an improved self-organizing mapping (ISOM) for multiple task assignment of all USVs is proposed for multiple task allocation. An ISOM can be used to achieve the multiple task assignment of all USVs, with the resulting task set corresponding to USV being an unordered array. In the second stage, which aims at the path-planning problem of the USV accessing tasks, an improved genetic algorithm (IGA) is proposed. To solve the problem of USVs colliding during navigation, an artificial potential field function (APFF) based on position information measured by the sensor system is proposed. The accuracy of the information measured by the sensor system can be guaranteed in engineering. Finally, collision-free trajectories are generated for each USV.

In summary, the main contributions of this paper are summarized as follows.

• For multiple task assignment, an improved self-organizing mapping algorithm is proposed. In this case, all tasks are distributed uniformly using the ISOM, and a set of tasks corresponds to each USV.
• For path planning, an improved genetic algorithm with the shortest path as the cost function is proposed. By improving the genetic algorithm, we calculate the unordered array from multi-task assignment to obtain a set of ordered arrays with the shortest track.
• Obstacle avoidance is a very important part of path planning. To avoid obstacles in USV path planning, an APFF based on position information measured by the sensor system is proposed.

This paper is organized as follows: Section 2 describes the problem of multi-USV systems, the model of USV and some necessary preliminaries. Section 3 proposes an ISOM for multiple task allocation. Section 4 designs an IGA and APFF for path planning. Section 5 gives simulation and comparison results to verify the effectiveness of the proposed method. Section 6 concludes the paper.

2. Problem Description and Notation

2.1. Problem Description

A multiple USV system is a complex system. In much of the literature, path planning is combined into SOM to provide multi-task allocation and path planning at the same time. This method is feasible in theory, but not in practice, because path planning is a very time-consuming algorithm. In this case, multiple task assignment and path planning are executed in the same program, which will run slowly. The distributed processing of a multiple USV system mainly focuses on two areas: multiple task assignment and path planning. The multiple USV system framework based on multi-task assignment and path planning is shown in Figure 1.

The first challenge is the multi-task allocation problem of the multiple USV system. Aiming to solve the problem of multiple task assignment, an ISOM is proposed. An ISOM can allocate all tasks for all USVs. Through ISOM, the task set accessed by each USV is obtained, and each task belongs to only one task set. Moreover, the ISOM has good extensibility and scalability. For example, the number of USVs needs to be added or reduced, and some tasks are added or modified, etc.

The second challenge is to give all USVs access to their task node sets along an optimum path. Multiple tasks can be regarded as multiple task points, and access to the set of tasks can be considered to be the traveling salesman problem (TSP). Based on traditional path planning, an IGA with the shortest path is proposed. At the same time, to avoid USV collisions during navigation, an APFF is proposed.

A real USV is in a three-dimensional space, which makes path planning problems of multiple USVs complex. The USV motion can be decoupled into two motions in a two-dimensional plane and a vertical direction, respectively. As shown in the Figure 2, the mission area is two-dimensional [4].

Assumption 1.

All the tasks are in the mission area, and the priority of each task is the same.

Assumption 2.

The USVs are homogeneous USVs with basic capabilities for navigation, obstacle avoidance, and location recognition [4].

2.2. Modeling of the USV

The 3 degrees of freedom (DOFs) kinematic equations of the USV can be expressed in vector form as [22]

$$\begin{array}{cc}\hfill & \dot{\eta }=R\left(\psi \right)\upsilon \hfill \end{array}$$

(1)

$$\begin{array}{cc}\hfill & M\dot{\upsilon }+D\left(\upsilon \right)\upsilon =\tau +{\tau }^{*}\hfill \end{array}$$

(2)

where $R\left(\psi \right)$ is the rotation matrix, it is given as:

$$\begin{array}{c}\hfill R\left(\psi \right)=\left[\begin{array}{ccc}cos\left(\psi \right)& -sin\left(\psi \right)& 0\\ sin\left(\psi \right)& cos\left(\psi \right)& 0\\ 0& 0& 1\end{array}\right]\end{array}$$

(3)

with the properties: $\parallel R\left(\psi \right)\parallel =1$ and $R^{\mathrm{T}}\left(\psi \right)R\left(\psi \right)=I_{3\times 3}$. $\eta :={[x,y,\psi ]}^{\mathrm{T}}$ is the position and yaw angle in the earth-fixed frame $X_E{O}_E{Y}_E$ (see Figure 3). $\upsilon :={[u,v,r]}^{\mathrm{T}}$ is the velocity vector in the body-fixed frame $X_B{O}_B{Y}_B$, where u, v, and r represent the surge, sway, and yaw angular velocities, respectively. The system inertia matrix M is positive, definite, and constant, where $M=M^{\mathrm{T}}\in {\mathbf{R}}^{3\times 3}$ and $\dot{M}=0$. The damping matrix D is also symmetric and positive definite, i.e., $D\in {\mathbf{R}}^{3\times 3}$. $\tau :={[{\tau }_1,{\tau }_2,{\tau }_3]}^{\mathrm{T}}$ is the control input, which is produced by propellers. ${\tau }^{*}:={\tau }_{wind}+{\tau }_{wave}+{\tau }_{ocean}$ is the total environment disturbance by wind, waves, and ocean currents, respectively.

Assumption 3.

The position-yaw and velocity information for each vessel are available.

Remark 1.

The environmental disturbances consist of a low-frequency part and high-frequency part. In this paper, only the low-frequency part is considered during the control process.

2.3. Notation

For the multi-USV system of multiple task assignment and path planning, the following notations will be used in this paper. T = $\{T_1,T_2,\dots ,T_i,\dots ,T_M\}$ represents the M tasks randomly distributed in the mission area. Throughout the paper, $T_i$ represents the ith task, i.e., $i=1,2\dots ,M$. $T_i=(t_{i1},t_{i2},\dots ,t_{ik},\dots ,t_{iK})$ represents the ith target node is K-dimensional, i.e., $k=1,2,\dots ,K$. U = $\{US{V}_1,US{V}_2,\dots ,US{V}_j,\dots ,US{V}_N\}$ represents the set of N USVs in the multiple USV system. Throughout the paper, $US{V}_j$ represents the task set of the jth USV needs to access, i.e., $j=1,2,\dots ,N$. At the same time, M is the number of neurons in the input layer, which is the same size as the number of task nodes in multiple USVs system. N is the number of cluster centers in the ISOM network, and the size is consistent with the number of USVs in multi-USV system. O = $\{O_1,O_2,\dots ,O_q,\dots ,O_Q\}$ represents the set of Q obstacles in the mission area, i.e., $q=1,2,\dots ,Q$. $max(•)$ means to take the maximum value of the •. ${(·)}^{\mathrm{T}}$ represents the transpose of a matrix.

3. Improved Self-Organizing Mapping

The self-organizing mapping network and multiple USV system multi-task allocation module have many similar characteristics and phenomena. First, the number of input objects in a SOM network can be changed arbitrarily. It is not affected by the design principle of the SOM network. Second, SOM adopts a mechanism of competitive learning, which gives adjacent neurons similar characteristics. In the multiple USV system, each USV can be understood as the “cluster center” in SOM. Because of these similar characteristics and phenomena, it is feasible to apply SOM in the multiple task assignment module of the multi-USV system.

3.1. The Principle of Self-Organizing Mapping

Self-organizing mapping, also known as the Kohonen network, was first proposed by Kohonen, and can realize unsupervised learning and clustering of data [23,24]. The Kohonen network is a neural network with only an input layer and a computational layer, as shown in Figure 4. SOM assumes that there are some topological structures or orders in the input objects, which can realize mapping from the input layer to the computational layer. The mapping can preserve topological features.

Suppose M tasks and N USVs are randomly distributed in the mission area. The SOM network model with an input layer and computational layer is shown in Figure 4. The first layer is the input layer. It contains M neurons, and the dimension of each neuron is K-dimensional. Therefore, the expression pattern of the ith neuron is $T_i=(t_{i1},t_{i2},\dots ,t_{ik},\dots ,t_{iK})$, $i=1,2,\dots ,M$, $k=1,2,\dots ,K$. The second layer is the output layer. It contains $N{M}_1$ neurons $(R_{11},\dots ,R_{1M_1},R_{21},\dots ,R_{2M_1},\dots ,R_{N1},\dots ,R_{N{M}_1})$. It represents the coordinates of the N USVs and the corresponding set of $M_1$ task nodes ($M_1\le M$). $R_{nm}=(w_{nmx},w_{nmy})$ represents the connection weight of the output neurons to the input neurons, $n=1,2,\dots ,N$, $m=1,2,\dots ,M_1$, $M_1\le M$. At the beginning, the SOM is initialized with the connection weights $(w_{nmx},w_{nmy})$, $n=1,2,\dots ,N$, which are the initial locations of the N USVs.

3.2. Initialization Parameters

These initialization parameters mainly include a training set ($dat{a}_{training}$), test set ($dat{a}_{test}$), maximum value of iterations ($iter$), learning rate (${\eta }_0$), learning rate parameter ($lear{n}_{para}$), neighborhood radius ($neig{h}_{redius}$), neighborhood parameter ($neig{h}_{para}$), weight of connecting all neurons (w), etc. In addition, we focus on one of the parameters w, which meets the following condition

$$\begin{array}{c}\hfill w=rand(N,M).\end{array}$$

(4)

where $w\in {\mathbf{R}}^{N\times M}$ represents the $N\times M$-dimensional Euclidean Space, in which the elements are randomly distributed in (0,1). N and M represent the numbers of USVs and tasks, respectively.

3.3. Winner Selection Rules

For a given task as an input object, the output neurons compete to be the winner according to a specified criterion described as [6] references

$$\begin{array}{c}\hfill W_i=\underset{i}{min}{D}_{inm},\end{array}$$

(5)

where $i=1,2,\dots ,M$, $n=1,2,\dots ,N$, $m=1,2,\dots ,M_1$. $W_i$ denotes that the ith neuron from the nth group of the computational layer is the winner of the mth input layer object. $D_{inm}$ is the Euclidean distance between $T_i$ and $R_{nm}$, which is calculated by

$$\begin{array}{c}\hfill D_{inm}=∥T_i-R_{nm}∥\times (1+P),\end{array}$$

(6)

where

$$\begin{array}{c}\hfill ∥T_i-R_{nm}∥=\sqrt{\sum _{k=1}^K{(t_{ik}-w_{nm})}^2},\end{array}$$

(7)

where $T_i=(t_{i1},t_{i2},\dots ,t_{ik},\dots ,t_{iK})$, $i=1,2,\dots ,M$, $k=1,2,\dots ,K$,$T_i$ is the target coordinate of the ith input node. $R_{nm}=w_{nm}$, $n=1,2,\dots ,N,m=1,2,\dots ,M_1,i\ne m$, $R_{nm}$ is the coordinate of the mth neuron from the nth group of the computational layer.

Parameter P in (6) represents the equitable distribution of workload for jth USV [7], and it is defined as

$$\begin{array}{c}\hfill P_j=\frac{L_j-\overline{L_j}}{1+\overline{L_j}},\end{array}$$

(8)

where $j=1,2,\dots ,N$. $L_j$ and $\overline{L_j}$ are the actual cruise path length and the average cruise path length of the jth USV, respectively.

Without losing generality, we need to consider the workload and energy consumption of each USV to ensure that all USVs can return to the supply point for fuel consumption. Considering different types of USV, their equipment is different, which will lead to different basic technical parameters. For example, the basic technical parameters of the US Navy “ship-class” unmanned combat surface craft are as follows: the maximum speed is between 32 knots and 35 knots, the cruise speed of towing and other mine-sweeping tasks can reach 20 to 25 knots, and the sea self-sustaining capacity can reach 48 h. The cruise speed of the remote-control multi-mission surface craft designed by the US Navy is 16 knots, and its self-sustaining power can reach 24 h during the operation. Here, we choose the cruising speed of USV at 20 knots and cruise duration of 24 h. The track length ($L_{path}$) of USV is calculated as follows:

$$\begin{array}{c}\hfill L_{path}=v\times t=20\left(\mathrm{knots}\right)\times 1.852\left(\mathrm{km}/\mathrm{h}\right)\times 24\left(\mathrm{h}\right)=888.96\left(\mathrm{km}\right).\end{array}$$

(9)

After the above calculation, the cruise path reaches 888.96 km, which can fully meet our design requirements. In this case, the influence of parameter P can be ignored, and Formula (6) can be rewritten as follows:

$$\begin{array}{c}\hfill D_{inm}=∥T_i-R_{nm}∥.\end{array}$$

(10)

3.4. Neighborhood Updating Rules

The next step is to calculate the distance between the other neurons and the winner neuron, which is the weight (w). The key is to determine the neighborhood function ($h_{ji}$). We choose the function as the neighborhood function of the winner neuron, and the specific expression is as follows:

$$\begin{array}{c}\hfill h_{ji}\left(t\right)=\left\{\begin{array}{cc}{e}^{-d_{ji}^2/2\sigma {\left(t\right)}^2},\hfill & d_{ji}\le neig{h}_{redius}\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.\end{array}$$

(11)

where $d_{ji}=∥T_i-T_{winner}∥$, $j=1,2,\dots ,N$, $i=1,2,\dots ,M$. $d_{ji}$ represents the distance between the ith neuron and the winner neuron in the jth output neuron. $\sigma \left(t\right)={\sigma }_0\times e^{-\frac{t}{2}}$ is a monotone decreasing function, and ${\sigma }_0>0$ is a small constant. The $h_{ji}$ provides a percentage-like measure of how close the neurons are.

The initial neighborhood radius ($neig{h}_{radius}$) should be half the length of the whole output plane at least. The neighborhood radius ($neig{h}_{radius}\left(t\right)$) is defined as follows

$$\begin{array}{c}\hfill neig{h}_{radius}\left(t\right)=neig{h}_{radius}\left(0\right)\times e^{-\frac{t}{neig{h}_{para}}},\end{array}$$

(12)

where $neig{h}_{radius}\left(t\right)$ is a monotone decreasing function. $neig{h}_{radius}\left(0\right)>0$ is a very large constant. $neig{h}_{para}$ represents neighborhood parameter. After iteration, the neighborhood radius will converge to a small normal value.

The update rule without considering the ocean current is defined as

$$\begin{array}{c}\hfill R_{nm}(t+1)=\left\{\begin{array}{cc}{T}_i,\hfill & D_{inm}\le D_{min}\hfill \\ R_{nm}\left(t\right)+\beta \times h_{ji}\times (T_i-R_{nm}),\hfill & \mathrm{otherwise}\hfill \end{array}\right.\end{array}$$

(13)

where $D_{min}$ represents the range of topological neighborhood structure. After calculation, $D_{min}=neig{h}_{redius}\times neig{h}_{redius}$ is a large enough number. After iteration, once $D_{inm}\le D_{min}$, $R_{nm}(t+1)$ is expressed as

$$\begin{array}{c}\hfill R_{nm}(t+1)=T_{winner}\left(t\right).\end{array}$$

(14)

3.5. Weight Updating Rules

The learning rate is represented by the character $\eta \left(t\right)$, which is defined as follows

$$\begin{array}{c}\hfill \eta \left(t\right)=\eta \left(0\right)\times e^{-\frac{t}{lear{n}_{para}}},\end{array}$$

(15)

where $\eta \left(t\right)$ is a monotone decreasing function denoting learning rate, $\eta \left(0\right)={\eta }_0$, ${\eta }_0\in (0,1]$ is a constant, $lear{n}_{para}$ represents learning rate parameter.

Through the above description, $w(t+1)$ is expressed as

$$\begin{array}{c}\hfill w(t+1)=w\left(t\right)+\eta \left(t\right)\times h_{ji}\left(t\right)\times (T_i-w\left(t\right)).\end{array}$$

(16)

3.6. Improved Self-Organizing Mapping

Next, the improved SOM is divided into the following two areas.

(1) The target set is divided into a training set and test set. In the training process of the ISOM algorithm, only the training set is used. When the training is completed and the classification effect is achieved, the test set is processed. This can ensure the accuracy of test-set classification.

(2) The verification of the test set is divided into two steps: storage and grouping. After testing, M neurons were stored. According to the serial number of the task node in the storage data, the grouping is completed. Finally, the set of tasks is the effect of the multi-USV system’s multiple task allocation.

3.7. Pseudocode and Flowchart of Improved Self-Organizing Mapping

After the above comprehensive analysis and overall design, we can configure the ISOM algorithm. The pseudocode is shown in Algorithm 1 and the flowchart of the ISOM, as shown in Figure 5.

Algorithm 1 ISOM algorithm-based multiple USVs system multi-task assignment module.

Input: Parameter Initialization. training set ($dat{a}_{training}$), test set ($dat{a}_{test}$), number of targets in the test set (N), number of neuron nodes (M), maximum number of iterations ($iter$), learning rate (${\eta }_0$), learning rate parameter ($lear{n}_{para}$), neighborhood radius ($neighbo{r}_{redius}$), neighborhood parameter ($neighbo{r}_{para}$), weight of connecting all neurons (w), etc. Output:$ISO{M}_{num}=cell(1,N)$; $Grouping$: $X_{group1}$, $X_{group2}$, …, $X_{groupN}$   //$training$ $set$   for t = 1: $ite{r}_{max}$ do       for j = 1: $M_{training}$ do           Through the calculation of Formulas (2)–(7), the winner neuron is found $W_i$;           Through Formulas (8)–(11), calculate the neighborhood function $h_{ji}$;           for i = 1: N do              Through the calculation of Formula (13), update the weight of connecting all neurons w;           end for       end for       Through the calculation of Formula (9), update the neighborhood radius $neighbo{r}_{radius}$;       Through the calculation of Formula (12), update the learning rate $\eta$;   end for   //$test$ $set$   $ISO{M}_{num}=cell(1,size(w,1))$;   for i = 1: $size(w,1)$ do       $Storage$: $ISO{M}_{num}=cell(1,N)$;   end for   for i = 1: $M_{test}$ do       $Grouping$: $X_{group1}$, $X_{group2}$, …, $X_{groupN}$;   end for

4. Improved Genetic Algorithm

4.1. Genetic Algorithm

A genetic algorithm is a computational model to simulate the Darwinian evolution process of natural selection and genetic stimulation. It finds the best solution by simulating the process of biological evolution.

The genetic algorithm (GA) is a relatively mature heuristic algorithm. The IGA is takes the shortest track as the fitness function. First, the IGA starts with a population of random solutions. Second, a fitness function is formed to evaluate the adaptability of the solution. Third, it determines whether the individuals in this generation are optimal solutions. If they are, the optimum solution is presented, and the IGA is ended. If not, then it interactively generates a new generation of individuals through genetic operations, including selection, crossover, and mutation to perform corresponding genetic operations. The IGA continues to judge whether the new generation of individuals is the optimal solution. The approximate optimum solution is found through continuous loops, and then gradually converges to the optimum solution.

Through the above comprehensive analysis, we can configure the IGA. The pseudocode is shown in Algorithm 2. The flowchart of the IGA is shown in Figure 6.

Algorithm 2 IGA-based multiple USVs system path-planning module.

Input: Parameters Initialization. initial population size ($M_{popu}$), maximum number of iterations ($M_{iter}$), crossover probability ($p_c$), mutation probability ($p_m$), etc. Output:$L_{path}$, The best individual of each generation.   for $k1$ = 1: $M_{popu}$do       The initial population is produced   end for   while $iter<M_{iter}+1$ do            for $k1$ = 1: $M_{popu}$ do           Genetic operation was carried out in turn           Call their respective functions to selection, crossover, and mutation       end for           The population is updated, and a new generation of individuals is generated           Calculate the fitness function           Record the contemporary optimal fitness and best individual           $iter\leftarrow iter$+1;       end while

4.2. Artificial Potential Field Function

The basic principle of artificial potential field (APF) is a virtual force field, assuming that USV as a point moves in a virtual force field. The repulsion field is composed of the repulsive force of all obstacles for the USV, and the gravitational field is generated by the attraction of the task node for the USV. The artificial potential field function (APFF) is equal to the sum of repulsion and gravitation. The design of the APFF is based on the information measured by the sensor system. This information includes the actual position of multiple missions, multiple USVs, and obstacles in the mission area. Moreover, the accuracy of this information can be guaranteed. Therefore, APFF is feasible.

In APFF, we defined the following concepts. Repulsion is defined as follows

$$\begin{array}{c}\hfill F_{o,j}={\omega }_1\times max(e^{-a\times {(X_j-O_q)}^{\top }\times (X_j-O_q)}),\end{array}$$

(17)

where $F_{o,j}$ represents the repulsive force of obstacles for the jth USV. ${\omega }_1$ represents the repulsion gain coefficient, which is a constant value. a represents the threat level coefficient, which is a constant value. $X_j(x_j,y_j)$ and $O_q(x_q,y_q)$ represents the coordinates of the jth USV and qth obstacle, respectively $j=1,2,\dots ,N$ and $q=1,2,\dots ,Q$.

The gravitation is defined as follows

$$\begin{array}{c}\hfill F_{t,j}={\omega }_2\times {(X_j-T_l)}^{\top }\times (X_j-T_l),\end{array}$$

(18)

where $F_{t,j}$ represents the gravitation force of the $ii$th task for the jth USV. ${\omega }_2$ represents the gravitation gain coefficient, which is a very small constant. $X_j(x_j,y_j)$ represents the coordinate of the jth USV, $j=1,2,\dots ,N$. $T_l=(x_l,y_l)$ represents the coordinates of the lth task corresponding to the jth USV, $l=1,2,\dots ,M_1$, $M_1\le M$.

The APFF is equal to the sum of repulsion and gravitation, which is as follows:

$$\begin{array}{c}\hfill F_j=F_{o,j}+F_{t,j}\end{array}$$

(19)

where $F_j$ represents the resultant force of the jth USV in the artificial potential field, $j=1,2,\dots ,N$.

Substituting (17) and (18) into (19), we obtain the force of the USV in the APFF. According to the gradient descent method, it can be deduced that the moving direction of the USV is the descent direction of the APFF.

5. Simulation and Results

Simulations were carried out with Matlab 2018a. The simulations were run on a PC with a dual-core 2.30 GHz Intel(R) Core(TM) i5-8300H CPU and 8 GB of RAM.

To verify the proposed algorithm, two different simulations were set up in this section, namely three experimental groups and one comparision group.

In simulations, the model of surface ship Cybership II was used [25]. The time-varying environmental disturbances were modeled as first-order Markov processes [26].

In the simulation results, the blue area represents high potential value, and the white area means a low potential value, which is approximately zero. When the mission area is a grid, the black area represents an obstacle, and the white area indicates an allowed area. The simulation results are shown in Figure 7, Figure 8, Figure 9 and Figure 10, where $USVi$$(i=1,2,\dots ,N)$ represents the ith USV. The ★ indicates the location of the tasks.

5.1. Experimental Group of Proposed Algorithms

In this subsection, the simulation results show the effectiveness of the proposed algorithm. As an experimental group, the algorithm proposed in this paper is used. The ISOM is used for multiple task allocation. The parameters are as follows: $neig{h}_{radius}\left(0\right)=3$, $neig{h}_{para}$ = 10,000, $\eta \left(0\right)=1$, $lear{n}_{para}$ = 10,000. The IGA is used for path planning. The APFF is used to realize USV obstacle avoidance. The parameters are as follows: $M_{popu}=100$, $M_{iter}=200$, $p_c=0.8$, $p_m=0.08$, ${\omega }_1=1$, ${\omega }_2=0.0001$.

The experimental group includes three groups of experiments, which are experimental group 1, experimental group 2, and experimental group 3. The purpose of experimental group 1 is to test the effectiveness of the proposed method. Experimental group 2 aims to verify the stability and scalability of the ISOM. The purpose of experimental group 3 is to validate the effective of the APFF.

5.1.1. Experimental Group 1

According to the proposed algorithms, the number of tasks and the number of USVs are selected to be $M=20$, $N=2$ and $M=20$, $N=4$, respectively.

The multiple USV system simulation results of experimental group 1 are shown in Figure 7. Figure 7a shows the simulation effect of 20 tasks and 2 USVs. Figure 7b shows the simulation of 20 missions and 4 USVs. Through Figure 7, it can be verified that the proposed algorithm is effective.

5.1.2. Experimental Group 2

Compared with experimental group 1, and with other parameters unchanged, only the number of tasks and the number of USVs are selected as $M=15$, $N=2$ and $M=15$, $N=4$, respectively.

The multi-USV system simulation results of experimental group 2 are shown in Figure 8. Figure 8a shows the simulation of 15 tasks and 2 USVs. Figure 8b shows the simulation effect of 15 missions and 4 USVs. From Figure 8, it also can be verified that the proposed algorithm can achieve multiple task allocation and path planning. By comparing Figure 7 and Figure 8, it can be validated that the ISOM has good scalability, increasing or reducing the number of USV, and adding or deleting tasks, etc.

5.1.3. Experimental Group 3

In this subsection, the effectiveness of the proposed APFF has been verified. Only one parameter in the APFF was changed: the threat level coefficient (a). Other simulation conditions are the same as those in experimental group 1. $a=0.8$ and $a=1.6$ are the parameters of experimental group 1 and experimental group 3, respectively.

Simulation results are shown in Figure 9. Figure 9a shows the simulation of 20 tasks and 2 USVs. Figure 9b shows the simulation of 20 missions and 4 USVs. Figure 7 and Figure 9 show the avoidance obstacle effect of USV when $a=0.8$ and $a=1.6$, respectively. When $M=20,N=2$, the track lengths of USV1 and USV2 are shown in

Table 1. The track length of each USV in $M=20,N=2$.

	USV1 (m)	USV2 (m)
experimental group 1 (a = 0.8)	39.6	81.7
experimental group 3 (a = 1.6)	37.5	78.7
comparison group 1	36.9	78.1

. When $M=20,N=4$, the track lengths of USV1, USV2, USV3, and USV4 are shown in

Table 2. The track length of each USV in $M=20,N=4$.

	USV1 (m)	USV2 (m)	USV3 (m)	USV4 (m)
experimental group 1 (a = 0.8)	34.7	38.8	37.9	44.3
experimental group 3 (a = 1.6)	31.8	36.0	37.2	42.8
comparison group 1	31.8	36.0	36.8	42.1

.

5.2. Comparison and Analysis

In this subsection, traditional path planning is used in the simulation process, but the obstacles in the task area were not considered in [6]. In this paper, the proposed method considers the improved genetic algorithm and the threat level coefficient (a) regarding obstacles in the path planning of a multiple USV system.

The multi-USV system simulation results of comparison group 1 are shown in Figure 10. Figure 10a,b show the multi-USV system simulation effect of each USV when $M=20,N=2$ and $M=20,N=4$, respectively. Traditional SOM can realize multi-task allocation of a multiple USV system. However, in the process of path planning, the existence of obstacles in the mission area was not considered. Comparing Figure 7 and Figure 10, the trajectories of multiple USVs will pass through the high-risk area, and some of them will even pass directly through obstacles.

The route lengths of each USV when $M=20,N=2$ and $M=20,N=4$ are shown in Table 1 and Table 2. Through a comprehensive comparison of the contents in Table 1 and Table 2, it can be found that when the threat level of the obstacle decreases, the length of the route is approximately equal to the straight route.

By comparing Figure 7 and Figure 10, when changing the threat level coefficient (a) in the APFF, the trajectory of the USV has already violated obstacles in the mission area. However, each USV has a different track length. As shown in Table 1, the trajectory length of USV1 for $a=0.8$ is 39.6, which is 5.6% above that of $a=1.6$. The trajectory length of USV2 for $a=0.8$ is 81.7, which is 3.8% above that of $a=1.6$. The same conclusion can be drawn from the comparison of USV sailing length in Table 2. It can be concluded that the trajectory is safe at the expense of the total length of the route. The smaller the value of a, the higher the threat degree of obstacles. At the same time, the route is far from obstacles, safety is improved, and the path length is increased.

6. Conclusions

In this paper, we studied a multiple USV system for multi-task assignment and path planning. Multi-USV systems are divided into two: multiple task allocation and path planning. Some algorithms have been proposed for multi-task assignment and path planning. To obtain the task set of each USV, the ISOM is used to deal with multiple task allocation in the mission area. To realize USV parallel path planning, an IGA is proposed to obtain the ordered task sequence. To avoid a collision of USV trajectories, an APFF is designed. Simulation results show the effectiveness of the proposed algorithms. However, this paper does not consider the problem of dynamic obstacles and USV communication. These problems will be the focus of the future research.