Distributed Optimization-Based Path Planning for Multiple Unmanned Surface Vehicles to Pass through Narrow Waters

Abstract

Safety and efficiency are important when Unmanned Surface Vehicles (USVs) pass through narrow waters in complex marine environments. This paper considers the issue of path planning for USVs passing through narrow waterways. We propose a distributed optimization algorithm based on a polymorphic network architecture, which maintains connectivity and avoids collisions between USVs while planning optimal paths. Firstly, the initial path through the narrow waterway is planned for each USV using the narrow water standard route method, and then the interpolating spline method is used to determine its corresponding functional form and rewrite the function as a local cost function for the USV. Secondly, a polymorphic network architecture and a distributed optimization algorithm were designed for multi-USVs to maintain connectivity and avoid collisions between USVs, and to optimize the initial paths of the multi-USV system. The effectiveness of the algorithm is demonstrated by Lyapunov stability analysis. Finally, Lingshui Harbor of Dalian Maritime University and a curved narrow waterway were selected for the simulation experiments, and the results demonstrate that the paths planned by multiple USVs were optimal and collision-free, with velocities achieving consistency within a finite time.

1. Introduction

With the development of intelligent technology, the use of USVs is growing. USVs have become indispensable tools in oceanographic research, military operations, marine resource exploration, and maritime search and rescue. These USVs perform tasks in marine environments where it is difficult for humans to reach or stay for extended periods, thus improving operational efficiency and safety. Many USVs are urgently required to support the future development of the oceans [1,2,3,4]. USVs, as small-scale waterborne platforms with autonomous planning and navigation capabilities, are used in extreme conditions or places where personnel find it difficult to operate, placing higher demands on their flexibility and the prediction of their motion trends in complex marine environments. Passing through narrow waters is critical for the autonomous execution of USV missions. Therefore, simulation studies on the path planning of multiple USVs passing through narrow waters are necessary for the smooth execution of tasks involving multiple USVs [5,6,7].

The existing research primarily focuses on planning the path of a single vessel. To address the issue of fine motion control of USVs in small-scale regions, Du et al. [8] introduced a trajectory unit-based motion planning method. In response to the challenge of path planning for USVs navigating in marine environments over extended periods, Gao et al. [9] proposed a novel approach to environment modeling and path planning using an improved genetic algorithm. Liu et al. [10] proposed a motion planning method based on a mathematical model of USV maneuverability (the MA* algorithm) to resolve the issue of traditional path planning methods not aligning with the maneuverability of USVs. To overcome the constraints imposed by the map resolution on routes generated by the traditional A* algorithm and their potential incompatibility with the non-complete constraints of USVs, an improved smoothing A* algorithm was proposed by [11]. To tackle the challenges posed by complex marine environments, Lee et al. [12] proposed an algorithm that allows path planning in a short period. Aiming at the issues of the long search times and low safety performance of existing path planning in a variable marine environment, Bai et al. [13] proposed a plant growth-based path planning algorithm. To ensure the safe navigation of USVs, He et al. [14] proposed a VK-RRT* algorithm based on electronic nautical charts. For the path planning problem of ships navigating in harbor waters, Shu et al. [15] proposed a solution based on optimal control.

Despite the above, certain real-world tasks, such as patrolling, rescuing shipwrecks, apprehending smugglers, and removing water pollution, are too complex for a single USV to accomplish. Accordingly, it is crucial to study the synergy of multiple USVs, as they can work together effectively to complete these tasks. For the optimal inverse consensus control problem of a nonlinear multi-agent system, Su et al. [16] proposed a solution for optimal consensus control based on fuzzy approximation. A trajectory planning method based on consistent offset velocity direction (COVD) was suggested by [17] to address the issue of collision-free trajectory planning for USVs in the case of multi-USV collision. To tackle the problem of a single USV’s limited cooperative capability, a USV multilateral cooperative control system with topological scalability was proposed to be established within a polymorphic network by [18]. Additionally, a practical distributed flexible formation protocol for multiple USV systems, designed for navigating through narrow and irregular passages, was proposed by [19]. For the optimal consensus control problem of a nonlinear multi-agent system, Su et al. [20] proposed a reinforcement learning solution based on a new performance index function.

The research mentioned above effectively addresses the path planning challenges for multiple USVs. However, during ocean missions, ensuring the safe navigation of multiple USVs is crucial, and this requires the consideration of potential collisions between them. For the safety problem of inland navigation, Gan et al. [21] proposed a path planning scheme based on the safety potential field theory. Aiming at the problem of the safe navigation of a USV cluster in complex water environments, Ma et al. [22] proposed a USV cluster collision avoidance method based on negotiation protocol. Additionally, Ma et al. [23] introduced a collision avoidance method for USVs using a deep reinforcement learning (DRL) algorithm in complex encounter situations. Liu et al. [24] proposed a new trajectory planning method for collision-free trajectory planning of USVs under multi-ship collision scenarios, which simplifies the analysis of encounter situations through holistic thinking. Qian et al. [25] designed a new event-triggered collision avoidance control algorithm to expedite the formation shape convergence for the formation collision avoidance problem of multiple USVs.

Even though distributed-based path planning for multiple USVs can work well and solve the problem of collisions between USVs, it needs to optimize the paths to allow the USVs to complete their tasks efficiently. We learned from reading the distributed optimization literature that, using this method, the cost function can be processed to minimize it, thus completing the optimization of the system. Therefore, we decided to incorporate distributed optimization methods in the multi-USV system and progress has been made by scholars. Teng, F et al. [26] proposed a method to solve the economic dispatch of port microgrids with distributed optimization algorithms. A distributed optimization anti-avoidance algorithm based on the signum function was proposed by [27] to address the problem of the time-varying distributional convex optimization of continuous-time multi-intelligence systems with single and double integrators. Rahili and Ren [28] introduced a distributed algorithm with the signum function, an adaptive distributed algorithm, and a combined distributed tracking algorithm with a distributed estimation algorithm to solve the distributed optimization problem of continuous multi-intelligent body systems with single integrator dynamics. Additionally, Lin et al. [29] proposed a distributed nonsmooth algorithm for the time-varying distributed convex optimization problem for continuous-time multi-intelligent body systems with double integrator dynamics. While these distributed optimization algorithms offer reasonable solutions to the distributed optimization problem for multi-intelligent body systems, their integration with real-world scenarios still needs to be explored. Therefore, developing a safe and efficient method for a multi-USV system to navigate through narrow harbors and addressing the challenges posed by irregular environments is crucial for practical marine applications.

The research above offers a viable solution for multiple USVs to navigate through narrow waters. However, when operating in complex water environments, establishing safe and reliable communication between USVs is crucial for mission success. Building a polymorphic smart network presents new solution ideas for this challenge. In response to existing issues with the current Internet, such as its rigid structure, simple IP-based bearer structure, and inability to suppress unknown threats, Hu et al. [30] proposed a network architecture where network functions are represented polymorphically at each layer, known as a polymorphic smart network. Addressing the increasing complexity of tasks for multi-intelligent body systems, Lu et al. [31] proposed a method for maintaining connectivity in a multi-intelligent body system based on a polymorphic network. In order to fulfill the various needs of online equipment monitoring and process control in the process industry, Li et al. [32] designed a polymorphic network architecture based on integrated gateways. In response to the problem of high energy consumption and high cost when ships enter and leave harbor, Shan et al. [33] proposed a distributed energy management method based on a polymorphic network structure.

The objective of this paper was to solve the path planning problem for a multi-USV system to safely and efficiently pass through narrow waters, and to promote the marine industry’s vigorous development. The innovative contributions of this paper are summarized as follows:

(1)

For the single IP bearer and to address the difficulty in suppressing unknown threats, a communication architecture based on a polymorphic network was constructed to cope with the complex marine environment and ensure safe and reliable communication between USVs;

(2)

For the problem of safe and efficient cooperative passage of a multi-USV system passing through narrow waters, an algorithm based on distributed optimization was constructed to optimize the initial path and prevent collisions between USVs.

The paper is structured as follows: Section 2 presents the notations used in this paper and their descriptions. Section 3 describes the cost function, the kinematic model used for the path planning of multi-USV systems, the polymorphic network architecture, the distributed optimization algorithm, and the stability analysis. Section 4 presents path planning tests of USVs in different environments and discusses the robustness of the algorithms. Finally, Section 5 concludes the paper.

2. Preliminaries and Modeling

This section explains the notation used throughout the paper. The number of USVs is denoted by n. The symbol ℜ represents the set of real numbers, while the symbol ${\Re }^{+}$ denotes the set of positive real numbers. The symbol ${\Re }^n$ represents an $n\times 1$ dimensional column vector. The symbol ${(·)}^T$ denotes the transpose of a vector or matrix. The symbol $I_n$ denotes the $n\times n$ unit matrix, while the symbols ${\mathbf{1}}_n$ and ${\mathbf{0}}_n$ denote the n-dimensional column vector with element 1 and the n-dimensional column vector with element 0, respectively. The gradient and the Hessian matrix of the twice continuously differentiable function f are denoted by $\nabla f$ and H, respectively. $\left|\right|·{\left|\right|}_2$ denotes the 2-parameter, which is a measure of the magnitude of a vector in a vector space. The Kronecker Product, denoted by $C\otimes D$, is a matrix operation between two matrices C and D. It is used in this paper to expand the dimensionality of a matrix.

The communication relationship and communication topology between the USVs are described by the undirected graph $\mathcal{G}=({\mathcal{V}}_{\mathcal{G}},{\mathcal{E}}_{\mathcal{G}},{\mathcal{A}}_{\mathcal{G}})$, where ${\mathcal{V}}_{\mathcal{G}}=\{{\mathcal{V}}_1,{\mathcal{V}}_2,\cdots ,{\mathcal{V}}_n\}$ denotes the set of nodes of the USVs, ${\mathcal{E}}_{\mathcal{G}}=\{({\mathcal{V}}_i,{\mathcal{V}}_j)\in {\mathcal{V}}_{\mathcal{G}}\times {\mathcal{V}}_{\mathcal{G}}\}$ denotes the set of edges of the USVs, $({\mathcal{V}}_i,{\mathcal{V}}_j)$ denotes the information that node i accesses from node j. The adjacency matrix is defined as $\mathcal{A}=\left[a_{ij}\right]\in {\Re }^{n\times n}$, where $a_{ij}=1$ when $({\mathcal{V}}_i,{\mathcal{V}}_j)\in {\mathcal{E}}_{\mathcal{G}}$ and $a_{ij}=0$ otherwise. ${\mathcal{N}}_i=\{j\in {\mathcal{V}}_{\mathcal{G}}:({\mathcal{V}}_j,{\mathcal{V}}_i)\in {\mathcal{E}}_{\mathcal{G}}\}$ denotes all neighboring USVs of node i. The degree matrix of the undirected graph $\mathcal{G}$ is defined as $\mathcal{D}=diag\{d_1,d_2,\cdots ,d_n\}$, where $d_i={\sum }_{\mathrm{j}\in {\mathcal{N}}_i}{a}_{ij}$. The Laplacian matrix of the undirected graph $\mathcal{G}$ is defined as $\mathcal{L}=\mathcal{D}-\mathcal{A}$, or $\mathcal{L}=\mathcal{D}{\mathcal{D}}^T$. It is assumed that the Laplace matrix of an undirected graph $\mathcal{G}$ can be written as $\mathcal{L}=\left[{\ell }_{ij}\right]\in {\mathcal{R}}^{n\times n}$, where ${\ell }_{ii}={\sum }_{j=1}^n{a}_{ij}$ and ${\ell }_{ij}=-a_{ij}$ for $i\ne j$. The Laplacian matrix is semi-positive definite. The number of occurrences of the eigenvalue 0 represents the region of the graph where it is connected. The smallest non-zero eigenvalue, on the other hand, is indicative of the algebraic accessibility of the graph. The Laplacian matrix, denoted by $\mathcal{L}$, has zero row sums, which implies that the eigenvalue 0 of $\mathcal{L}$ is associated with the eigenvector ${\mathbf{1}}_n$.

To complete the subsequent proofs in this paper, Lemmas 1 and 2 are needed.

Lemma 1

([34]). We consider the function $f\left(x\right):{\Re }^N\to \Re$, which is continuously differentiable and convex. The minimum value of $f\left(x\right)$ is attained when $\nabla f=0$.

Lemma 2

([34]). The function f is assumed to be twice differentiable, meaning its Hessian H exists at each point in the domain of f, which is open. In this case, f is convex if and only if the domain of f is convex and its Hessian H is positive semidefinite: $H\ge 0$, $\forall x\in domf$.

Next, a multi-USV system consisting of n USVs is considered, whose interaction topology is described by an undirected graph $\mathcal{G}$. Since we are planning the path of a USV through narrow water, the bow rocking angle and angular velocity of the USVs are not taken into consideration. Then, ${\eta }_i\left(t\right)={[x_i\left(t\right),y_i\left(t\right)]}^T\in {\Re }^2$, ${\nu }_i\left(t\right)={[u_i\left(t\right),v_i\left(t\right)]}^T\in {\Re }^2$ represent the position and velocity of the ith USV, where $i\in \{1,2,\dots ,n\}$.

When a USV passes through a narrow water area, each USV will have a suitable trajectory according to narrow water standard route. We use the spline interpolation method in mathematics to fit the trajectory of each USV separately and use the derived function as the local cost function $f_i({\eta }_i\left(t\right),t):{\Re }^2\times {\Re }^{+}\to \Re$ of the ith USV, which takes the form of

$$f_i({\eta }_i\left(t\right),t)=\left|\right|{\eta }_i\left(t\right)-s_i\left(t\right){\left|\right|}_2^2,$$

(1)

where $s_i\left(t\right)\in {\Re }^2$ stands for the time-varying function for USV i. The cost function represents the quantization of the actual position versus the desired position.

Then, the global cost function $f(\eta \left(t\right),t):{\Re }^2\times {\Re }^{+}\to \Re$ can be expressed as

$$f(\eta \left(t\right),t)=\sum _{i=1}^n\left|\right|{\eta }_i\left(t\right)-s_i\left(t\right){\left|\right|}_2^2.$$

(2)

Based on the above relations, we can obtain $H_i({\eta }_i\left(t\right),t)=\left[\begin{array}{cc}2& 0\\ 0& 2\end{array}\right]>0$,$\forall {\eta }_i\in domf$ and that $domf$ is convex. According to Lemma 2, we can obtain that the local cost function $f_i({\eta }_i\left(t\right),t)$ is convex, so the global cost function $f\left(\eta \right(t),t)$ is also convex. Therefore, there exists an optimal state ${\eta }^{*}\left(t\right)$ where ${\eta }^{*}\left(t\right)$ is the minimum of the time-varying convex optimization problem.

$${\eta }^{*}\left(t\right)=\arg \min f(\eta \left(t\right),t).$$

(3)

Next, we model the kinematics of the USV. The USV motion is modeled using a double integrator model as follows:

$$\left\{\begin{array}{c}{\dot{\eta }}_i\left(t\right)={\nu }_i\left(t\right)\hfill \\ {\dot{\nu }}_i\left(t\right)={\tau }_i\left(t\right).\hfill \end{array}\right.$$

(4)

where ${\tau }_i\left(t\right)$ represents the control input of the ith USV. For convenience, the writing of $\left(t\right)$ will be omitted below.

In a multi-USV system, each USV is considered a self-subject, given the absence of a central control node and the lack of a requirement to transmit data to the central node. Our goal is to design ${\tau }_i\left(t\right)$ for (4), which interacts with neighboring USVs through information to obtain local information to form the optimal state position ${\eta }^{*}\left(t\right)$. The problem of Equation (3) above can be rewritten as

$$\underset{{\eta }_i\left(t\right)}{min}\sum _{i=1}^n{f}_i({\eta }_i,t)\mathrm{subject}\mathrm{to}{\eta }_i={\eta }_j.$$

(5)

Intuitively, our goal is to solve the consensus and minimization problems on the global cost function ${\sum }_{i=1}^n{f}_i({\eta }_i,t)$ such that the state position ${\eta }_i\left(t\right)$ of the ith USV converges to the optimal path ${\eta }^{*}\left(t\right)$ to safely and efficiently pass through the narrow water.

3. Design and Analysis

3.1. Polymorphic Networks Architecture

Communication between USVs and base stations is critical to mission accomplishment in complex marine environments. To solve the challenge of secure and reliable communication, we designed a USV communication architecture based on a polymorphic network, which is graphically shown below.

According to Figure 1, the polymorphic network consists of data, control, and service layers [30] in a full-dimensional definable functional plane. The functions of each of these layers are as follows:

• Date Layer: USVs and ground stations access the network through a mixture of heterogeneous network multimodal terminal identifiers, for which the data layer provides fully dimensionally definable forwarding services;
• Control Layer: IP identification, identity identification, content identification, and location identification are incorporated into multimodal addressing and routing. Then, service layer applications are adapted to network routing based on mechanisms such as match selection and on-demand switching. Finally, control of the underlying data level forwarding is realized;
• Service Layer: The control layer network is used to implement path optimization and collision avoidance services for the multi-USV system.

In this polymorphic network architecture, the control layer is functionally matched with four network modes: Internet Protocol version 6 (IPv6) Networking [35] is based on the original communication function to ensure that the USV status information is received and forwarded in real time; Geostationary Earth Orbit (GEO) Networking [36] is used to transmit the geographic location information of the USV; Mobility First (MF) Networking [37] is used to send the communication request of the USV and receive the return result to assist the communication of the USV; and Named Data Networking (NDN) [38] is used to transmit the video data captured by the USV to the ground station in real time.

3.2. Design of the Distributed Optimization Algorithm

Next, to design the ${\tau }_i$ in the USV system and generate optimal paths for each USV while ensuring connectivity and collision avoidance, according to [39], a distributed optimization algorithm was designed. The algorithm only permits each USV to access local information and information from its neighbors. Specifically, each USV can only access its position information and relative position and velocity information from its neighboring USVs. This distributed optimization algorithm aims to achieve the goal of safe and efficient access to the narrow water. The algorithm is shown below:

$$\begin{array}{cc}\hfill {\tau }_i\left(t\right)=& -c_1\sum _{j\in {\mathcal{N}}_i}({\nu }_i-{\nu }_j)-c_2\sum _{j\in {\mathcal{N}}_i}sgn({\nu }_i-{\nu }_j)\\ & -\sum _{j\in {\mathcal{N}}_i}{\displaystyle \frac{\partial {\mho }_{ij}}{\partial \left({\eta }_i\right)}}-{\nu }_i-4{\eta }_i+{\ddot{s}}_i+{\dot{s}}_i+4s_i,\end{array}$$

(6)

where $c_1$ and $c_2$ denote positive constants, $sgn$ represents the sign function, and ${\mho }_{ij}$ denotes the potential function between the ith and jth USVs.

We assume that each USV has a communication radius of $\mathsf{{\rm Y}}$. USVs i and j are considered to be neighbors if ${∥{\eta }_i-{\eta }_j∥}_2<\mathsf{{\rm Y}}$, denoted as ${\mathcal{N}}_i$. In the algorithm, the role of $-{\sum }_{j\in {\mathcal{N}}_i}{\displaystyle \frac{\partial {\mho }_{ij}}{\partial \left({\eta }_i\right)}}$ is to maintain connectivity between the USVs, i.e., if two USVs are neighbors at moment $t=0$, the two USVs are also neighbors for any $t>0$ moment. However, if two USVs are not neighbors at moment $t=0$, they are not guaranteed to be neighbors at moment $t>0$. The role of ${\sum }_{j\in {\mathcal{N}}_i}({\nu }_i-{\nu }_j)$ is to ensure that the speeds of the USVs can be consistent with each other. ${\sum }_{j\in {\mathcal{N}}_i}sgn({\nu }_i-{\nu }_j)$ is to ensure that the speeds of the USVs can be consistent with each other for a finite amount of time. The terms $(-{\nu }_i-4{\eta }_i+{\ddot{s}}_i+{\dot{s}}_i+4s_i)$ are to ensure that the USVs can follow the upper optimum ${\eta }^{*}\left(t\right)$, thus achieving the optimization goal.

In order to maintain the connectivity between the USVs and prevent collision avoidance, we designed the following [40] potential function

$$\begin{array}{cc}\hfill {\mho }_{ij}^1=& \left\{\begin{array}{cc}{b}_1,\hfill & {∥{\eta }_i-{\eta }_j∥}_2>\mathsf{{\rm Y}}\hfill \\ -cos\left[2\pi \left({∥{\eta }_i-{\eta }_j∥}_2-d_{ij}\right)\right]+b_2,\hfill & d_{ij}<{∥{\eta }_i-{\eta }_j∥}_2\le \mathsf{{\rm Y}}\hfill \\ 20({∥{\eta }_i-{\eta }_j∥}_2-d_{ij}ln{∥{\eta }_i-{\eta }_j∥}_2)+b_3,\hfill & {∥{\eta }_i-{\eta }_j∥}_2\le d_{ij}\hfill \end{array}\right.\hfill \end{array}$$

(7)

and

$$\begin{array}{cc}\hfill {\mho }_{ij}^2=& \left\{\begin{array}{cc}ln(\mathsf{{\rm Y}}-||{\eta }_i-{\eta }_j{\left|\right|}_2)+{\displaystyle \frac{d_{ij}-\mathsf{{\rm Y}}}{\left|\right|{\eta }_i-{\eta }_j{\left|\right|}_2-\mathsf{{\rm Y}}}}+b_4,\hfill & d_{ij}<\left|\right|{\eta }_i-{\eta }_j{\left|\right|}_2<\mathsf{{\rm Y}}\hfill \\ 20\left(\right||{\eta }_i-{\eta }_j{\left|\right|}_2-d_{ij}ln\left|\right|{\eta }_i-{\eta }_j{\left|\right|}_2)+b_5,\hfill & \left|\right|{\eta }_i-{\eta }_j{\left|\right|}_2\le d_{ij},\hfill \end{array}\right.\hfill \end{array}$$

(8)

where $d_{ij}$ represents the desired distance between neighboring USVs. The potential function ${\mho }_{ij}$ makes a non-negative differentiable function of ${∥{\eta }_i-{\eta }_j∥}_2$. $b_1,b_2,b_3,b_4$ and $b_5$ are constants which can guarantee that the potential function ${\mho }_{ij}$ is continuous and minimized when $\left|\right|{\eta }_i-{\eta }_j{\left|\right|}_2=d_{ij}$. It is worth noting that ${\mho }_{ii}=0$, and $d_{ij}<\mathsf{{\rm Y}}$.

Therefore, $-{\sum }_{j\in {\mathcal{N}}_i}{\displaystyle \frac{\partial {\mho }_{ij}}{\partial {\eta }_i}}$ is of the following form:

$$\begin{array}{c}\hfill {\displaystyle \frac{\partial {\mho }_{ij}^1}{\partial {\eta }_i}}=\left\{\begin{array}{cc}0,\hfill & {∥{\eta }_i-{\eta }_j∥}_2>\mathsf{{\rm Y}}\hfill \\ {\displaystyle \frac{2\pi \left({\eta }_i-{\eta }_j\right)sin\left[2\pi \left({∥{\eta }_i-{\eta }_j∥}_2-d_{ij}\right)\right]}{{∥{\eta }_i-{\eta }_j∥}_2}},\hfill & d_{ij}<{∥{\eta }_i-{\eta }_j∥}_2\le \mathsf{{\rm Y}}\hfill \\ {\displaystyle \frac{20\left({\eta }_i-{\eta }_j\right)}{{∥{\eta }_i-{\eta }_j∥}_2}}{\displaystyle \frac{{∥{\eta }_i-{\eta }_j∥}_2-d_{ij}}{{∥{\eta }_i-{\eta }_j∥}_2}},\hfill & {∥{\eta }_i-{\eta }_j∥}_2\le d_{ij}\hfill \end{array}\right.\end{array}$$

(9)

and

$${\displaystyle \frac{\partial {\mho }_{ij}^2}{\partial {\eta }_i}}=\left\{\begin{array}{cc}{\displaystyle \frac{{\eta }_i-{\eta }_j}{{∥{\eta }_i-{\eta }_j∥}_2}}{\displaystyle \frac{{∥{\eta }_i-{\eta }_j∥}_2-d_{ij}}{{\left({∥{\eta }_i-{\eta }_j∥}_2-\mathsf{{\rm Y}}\right)}^2}},\hfill & d_{ij}<{∥{\eta }_i-{\eta }_j∥}_2<\mathsf{{\rm Y}}\hfill \\ 20{\displaystyle \frac{{\eta }_i-{\eta }_j}{{∥{\eta }_i-{\eta }_j∥}_2}}{\displaystyle \frac{{∥{\eta }_i-{\eta }_j∥}_2-d_{ij}}{{∥{\eta }_i-{\eta }_j∥}_2}},\hfill & {∥{\eta }_i-{\eta }_j∥}_2\le d_{ij}.\hfill \end{array}\right.$$

(10)

To maintain connectivity between USVs, we choose ${\mho }_{ij}^2$ as the potential function when ${∥{\eta }_i\left(0\right)-{\eta }_j\left(0\right)∥}_2<\mathsf{{\rm Y}}$ and ${\mho }_{ij}^1$ otherwise. When the initial position of USV j is within the communication radius of USV i, the potential function ${\mho }_{ij}^2$ used in this paper increases infinitely. When USV j is far away from the communication radius, the repulsion is increased to ensure that USV j is within the communication radius of i, which ensures connectivity between them. On the contrary, if the initial position of USV i and j is not within the communication radius of i, there is no need to ensure it.

Next, the multi-USV system (4), according to algorithm (6), first proves that the speeds can reach a consensus and that there are no collisions between USVs while ensuring connectivity. It is, therefore, shown that the mean of the USV positions tracks to the optimal trajectory ${\eta }^{*}$ and the velocity tracks to ${\nu }^{*}$.

To complete the proof that follows, we introduce the following lemma:

Lemma 3

([41]). For the Laplacian matrix $\mathcal{L}$ corresponding to the undirected graph $\mathcal{G}$, its smallest eigenvalue ${\lambda }_2\left(\mathcal{L}\right)$ other than 0 satisfies the following relation:

$${\lambda }_2\left[\mathcal{L}\right]=\underset{x^T{\mathbf{1}}_N=0,x\ne {\mathbf{0}}_N}{min}{\displaystyle \frac{x^T\mathcal{L}x}{x^{T}x}}.$$

(11)

Next, we define Theorem 1, which states the relationship between the velocity $\nu$, the potential function ℧, and $c_2$.

Theorem 1.

For a multi-USV system (4), assume that the undirected graph $\mathcal{G}\left(0\right)$ is strongly connected. When $c_2\ge {\displaystyle \frac{\left|\right|(\mathsf{\Lambda }\otimes I_2)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S){\left|\right|}_2}{\sqrt{{\lambda }_2\left(\mathcal{L}\right)}}}$, algorithm (6) allows for a consensus on the speed between the USVs, i.e., ${\nu }_i={\nu }_j$, as $t\to \infty$. Moreover, there is no collision between the USVs while ensuring connectivity.

Proof of Theorem 1.

Let $\mathsf{\Gamma }={[{\eta }_1^T,\dots ,{\eta }_n^T]}^T$, $V={[{\nu }_1^T,\dots ,{\nu }_n^T]}^T$, $S={[s_1^T,\dots ,s_n^T]}^T$, $\mathsf{\Lambda }=I_n-{\displaystyle \frac{{\mathbf{1}}_n{\mathbf{1}}_n^T}{n}}$. We rewrite the multi-USV system (4) in the following compact form:

$$\left\{\begin{array}{cc}\hfill \dot{\mathsf{\Gamma }}=& V\hfill \\ \hfill \dot{V}=& -c_1\left(\mathcal{L}\otimes I_2\right)V-c_2\left(\mathcal{D}\otimes I_2\right)sgn\left(\left({\mathcal{D}}^T\otimes I_2\right)V\right)\hfill \\ \hfill & -{\left[\sum _{j\in {\mathcal{N}}_1}{\displaystyle \frac{\partial {\mho }_{1j}}{\partial {\eta }_1}},\dots ,\sum _{j\in {\mathcal{N}}_n}{\displaystyle \frac{\partial {\mho }_{nj}}{\partial {\eta }_n}}\right]}^T-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S.\hfill \end{array}\right.$$

(12)

In order to prove that the velocity can reach consistency, we define the position error $e_{{\mathsf{\Gamma }}_i}={\eta }_i-{\displaystyle \frac{1}{n}}{\sum }_{j=1}^n{\eta }_j$ and velocity error $e_{V_i}={\nu }_i-{\displaystyle \frac{1}{n}}{\sum }_{j=1}^n{\nu }_j$ for the ith USV, written in compact form as $e_{\mathsf{\Gamma }}=(\mathsf{\Lambda }\otimes I_2)\mathsf{\Gamma }$, $\mathrm{and}{e}_V=(\mathsf{\Lambda }\otimes I_2)V$, respectively. Thus, it is clear that the velocity between the USVs reaches consistency when $e_V$ tends to zero. Next, we multiply $(\mathsf{\Lambda }\otimes I_2)$ on both sides simultaneously to obtain the following equation based on (12):

$$\left\{\begin{array}{cc}\hfill {\dot{e}}_{\mathsf{\Gamma }}=& e_V\hfill \\ \hfill {\dot{e}}_V=& -c_1\left(\mathcal{L}\otimes I_2\right)e_V-c_2\left(\mathcal{D}\otimes I_2\right)sgn\left(\left({\mathcal{D}}^T\otimes I_2\right)e_V\right)\hfill \\ \hfill & +\left(\mathsf{\Lambda }\otimes I_2\right)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S)-{\left[\sum _{j\in {\mathcal{N}}_1}{\displaystyle \frac{\partial {\mho }_{1j}}{\partial e_{{\mathsf{\Gamma }}_1}}},\dots ,\sum _{j\in {\mathcal{N}}_n}{\displaystyle \frac{\partial {\mho }_{nj}}{\partial e_{{\mathsf{\Gamma }}_n}}}\right]}^T.\hfill \end{array}\right.$$

(13)

Based on (13), we design the following Lyapunov function

$$w_1={\displaystyle \frac{1}{2}}{e}_V^T{e}_V+{\displaystyle \frac{1}{2}}\sum _{i=1}^n\sum _{j=1}^n{\mho }_{ij}.$$

(14)

According to Lemma 3.1 in [40], the potential function has the following concatenation relation: ${\displaystyle \frac{1}{2}}{\sum }_{i=1}^n{\sum }_{j=1}^n\left({\displaystyle \frac{\partial {\mho }_{ij}}{\partial {\eta }_i}}{\dot{\eta }}_i+{\displaystyle \frac{\partial {\mho }_{ij}}{\partial {\eta }_j}}{\dot{\eta }}_j\right)={\sum }_{i=1}^n{\sum }_{j=1}^n{\displaystyle \frac{\partial {\mho }_{ij}}{\partial {\eta }_i}}{\dot{\eta }}_i$. Also, using Lemma 3, the Liapunov function $w_1$ is derived for time t in the following form:

$$\begin{array}{cc}\hfill \dot{w_1}& =e_V^T{\dot{e}}_V+{\displaystyle \frac{1}{2}}\sum _{i=1}^n\sum _{j=1}^n\left({{\displaystyle \frac{\partial {\mho }_{ij}}{\partial e_{{\mathsf{\Gamma }}_i}}}}^T{e}_{V_i}+{{\displaystyle \frac{\partial {\mho }_{ij}}{\partial e_{{\mathsf{\Gamma }}_j}}}}^T{e}_{V_j}\right)\hfill \\ \hfill & =e_V^T{\dot{e}}_V+\sum _{i=1}^n\sum _{j=1}^n{{\displaystyle \frac{\partial {\mho }_{ij}}{\partial e_{{\mathsf{\Gamma }}_i}}}}^T{e}_{V_i}\hfill \\ \hfill & =-c_1{e}_V^T\left(\mathcal{L}\otimes I_2\right)e_V+e_V^T\left(\mathsf{\Lambda }\otimes I_2\right)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S)\hfill \\ \hfill & -c_2{e}_V^T\left(\mathcal{D}\otimes I_2\right)sgn\left(\left({\mathcal{D}}^T\otimes I_2\right)e_V\right)\hfill \\ & \le -c_1{e}_V^T\left(\mathcal{L}\otimes I_2\right)e_V-c_2\left|\right|({\mathcal{D}}^T\otimes I_2)e_V{\left|\right|}_1\hfill \\ \hfill & +{∥e_V∥}_2{∥\left(\mathsf{\Lambda }\otimes I_2\right)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S)∥}_2\hfill \\ & \le -c_1{e}_V^T\left(\mathcal{L}\otimes I_2\right)e_V-c_2\sqrt{e_V^T(\mathcal{D}{\mathcal{D}}^T\otimes I_2)e_V}\hfill \\ \hfill & +{∥e_V∥}_2{∥\left(\mathsf{\Lambda }\otimes I_2\right)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S)∥}_2\hfill \\ & \le -c_1{e}_V^T\left(\mathcal{L}\otimes I_2\right)e_V-c_2\sqrt{{\lambda }_2\left(\mathcal{L}\right)}{∥e_V∥}_2\hfill \\ \hfill & +{∥e_V∥}_2{∥\left(\mathsf{\Lambda }\otimes I_2\right)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S)∥}_2\hfill \\ & \le -c_1{e}_V^T\left(\mathcal{L}\otimes I_2\right)e_V-{∥e_V∥}_2\hfill \\ & (c_2\sqrt{{\lambda }_2\left(\mathcal{L}\right)}-{∥\left(\mathsf{\Lambda }\otimes I_2\right)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S)∥}_2).\hfill \end{array}$$

(15)

It can be seen that $\dot{w_1}$ is negative semidefinite when $c_2\ge {\displaystyle \frac{\left|\right|(\mathsf{\Lambda }\otimes I_2)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S){\left|\right|}_2}{\sqrt{{\lambda }_2\left(\mathcal{L}\right)}}}$. Thus, according to both $w_1\ge 0$ and $\dot{w_1}\le 0$, we can obtain ${\mho }_{ij}$, $e_V\in L_{\infty }$. By integrating both sides of (15), it can be demonstrated that $e_V\in L_2$. According to Barbalat’s Lemma [42], we can conclude that $e_V\to 0$ when $t\to \infty$, which implies that velocity $\nu$ eventually reach consensus. Moreover, since ${\mho }_{ij}\in L_{\infty }$, we can conclude that USVs avoid collisions while maintaining connectivity. This completes the proof. □

Next, we define Theorem 2, which states the relationship between position $\eta$, velocity $\nu$, and ${\eta }^{*}$ and ${\nu }^{*}$.

Theorem 2.

For a multi-USV system, assume that the undirected graph $\mathcal{G}\left(0\right)$ is strongly connected. The distributed optimization algorithm enables the USV system to track to the optimal state ${\eta }^{*}$, and the velocity tracks to ${\nu }^{*}$ when $c_2\ge {\displaystyle \frac{\left|\right|(\mathsf{\Lambda }\otimes I_2)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S){\left|\right|}_2}{\sqrt{{\lambda }_2\left(\mathcal{L}\right)}}}$.

Proof of Theorem 2.

In this section, we study the relationship between the optimal trajectory ${\eta }^{*}$ of the global cost function and the USV. We design the following Lyapunov function:

$$w_2=w_{21}+w_{22},$$

(16)

where

$$w_{21}=2{\left[\sum _{i=1}^n({\eta }_i-s_i)\right]}^T\left[\sum _{i=1}^n({\eta }_i-s_i)\right],$$

(17)

$$w_{22}={\displaystyle \frac{1}{2}}{\left[\sum _{i=1}^n({\nu }_i+{\eta }_i-{\dot{s}}_i-s_i)\right]}^T\left[\sum _{i=1}^n({\nu }_i+{\eta }_i-{\dot{s}}_i-s_i)\right].$$

(18)

We can obtain that

$${\dot{w}}_{21}=4{\left[\sum _{i=1}^n({\eta }_i-s_i)\right]}^T\left[\sum _{i=1}^n({\nu }_i-{\dot{s}}_i)\right],$$

(19)

$${\dot{w}}_{22}={\left[\sum _{i=1}^n({\nu }_i+{\eta }_i-{\dot{s}}_i-s_i)\right]}^T\left[\sum _{i=1}^n({\dot{\nu }}_i+{\nu }_i-{\ddot{s}}_i-{\dot{s}}_i)\right].$$

(20)

Since the topology of a multi-USV system is described by the undirected graph $\mathcal{G}$, by accumulating the controllers ${\tau }_i$, we obtain ${\sum }_{i=1}^n{\dot{\nu }}_i={\sum }_{i=1}^n(-{\nu }_i-4{\eta }_i+{\ddot{s}}_i+{\dot{s}}_i+4s_i)$. Thus,

$${\dot{w}}_{22}=4{\left[\sum _{i=1}^n({\nu }_i+{\eta }_i-{\dot{s}}_i-s_i)\right]}^T\left[\sum _{i=1}^n({\dot{s}}_i-{\eta }_i)\right].$$

(21)

Further, we can obtain

$$\begin{array}{cc}\hfill {\dot{w}}_2& ={\dot{w}}_{21}+{\dot{w}}_{22}\hfill \\ & =4{\left[\sum _{i=1}^n({\eta }_i-s_i)\right]}^T\left[\sum _{i=1}^n({\nu }_i-{\dot{s}}_i)\right]+4{\left[\sum _{i=1}^n({\nu }_i+{\eta }_i-{\dot{s}}_i-s_i)\right]}^T\left[\sum _{i=1}^n({\dot{s}}_i-{\eta }_i)\right]\hfill \\ \hfill & =-4{\left[\sum _{i=1}^n({\eta }_i-s_i)\right]}^T\left[\sum _{i=1}^n({\eta }_i-s_i)\right].\hfill \end{array}$$

(22)

Since $f_i({\eta }_i,t)=\left|\right|{\eta }_i\left(t\right)-s_i\left(t\right){\left|\right|}_2^2$, $▿f_i({\eta }_i,t)=2({\eta }_i-s_i)$, we can deduce that

$$\begin{array}{c}\hfill w_2={\displaystyle \frac{1}{2}}{(\sum _{i=1}^n▿f_i({\eta }_i,t))}^T(\sum _{i=1}^n▿f_i({\eta }_i,t))+{\displaystyle \frac{1}{2}}{\left[\sum _{i=1}^n({\nu }_i+{\eta }_i-{\dot{s}}_i-s_i)\right]}^T\left[\sum _{i=1}^n({\nu }_i+{\eta }_i-{\dot{s}}_i-s_i)\right],\end{array}$$

(23)

$${\dot{w}}_2=-{(\sum _{i=1}^n▿f_i({\eta }_i,t))}^T(\sum _{i=1}^n▿f_i({\eta }_i,t)).$$

(24)

We can obtain that ${\dot{w}}_2<0$ if ${\sum }_{i=1}^n▿f_i({\eta }_i,t)\ne 0$. Then, we can conclude that ${\sum }_{i=1}^n▿f_i({\eta }_i,t)$, ${\nu }_i+{\eta }_i-{\dot{s}}_i-s_i\in L_{\infty }$. Next, we simultaneously integrate both sides of (24) to obtain ${\sum }_{i=1}^n▿f_i({\eta }_i,t)\in L_2$. By application of Barbalat’s Lemma [42], ${\sum }_{i=1}^n▿f_i({\eta }_i,t)\to 0$ when $t\to \infty$, and then we obtain ${\sum }_{i=1}^n({\eta }_i\left(t\right)-s_i\left(t\right))=0$, ${\sum }_{i=1}^n({\nu }_i\left(t\right)-{\dot{s}}_i\left(t\right))=0$. According to Lemma 1, ${\eta }^{*}$ satisfies ${\sum }_{i=1}^n({\eta }^{*}\left(t\right)-s_i\left(t\right))=0$, ${\sum }_{i=1}^n({\nu }^{*}\left(t\right)-{\dot{s}}_i\left(t\right))=0$. We can obtain that ${\displaystyle \frac{1}{n}}{\sum }_{i=1}^n{\eta }_i\to {\eta }^{*}$, ${\displaystyle \frac{1}{n}}{\sum }_{i=1}^n{\nu }_i\to {\nu }^{*}$.

From the above analysis, we can conclude that the actual position ${\eta }_i$ and velocity ${\nu }_i$ of the USV can be tracked to the optimal position ${\eta }^{*}$ with velocity ${\nu }^{*}$. This completes the proof. □

Remark 1.

Since $\sqrt{{\lambda }_2\left(\mathcal{L}\right)}$ has a lower bound above 0, for $c_2\ge {\displaystyle \frac{\left|\right|(\mathsf{\Lambda }\otimes I_2)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S){\left|\right|}_2}{\sqrt{{\lambda }_2\left(\mathcal{L}\right)}}}$, the condition for it to hold is now that $\left|\right|(\mathsf{\Lambda }\otimes I_2)(-V-4\mathsf{\Gamma }+\ddot{S}+\dot{S}+4S){\left|\right|}_2$ has an upper bound, i.e., $\left|\right|s_i\left(t\right)-s_j\left(t\right){\left|\right|}_2$, $\left|\right|{\dot{s}}_i\left(t\right)-{\dot{s}}_j\left(t\right){\left|\right|}_2$ and $\left|\right|{\ddot{s}}_i\left(t\right)-{\ddot{s}}_j\left(t\right){\left|\right|}_2$ are bounded and need to be satisfied [28] such that $c_2$ exists to ensure the effectiveness of the algorithm.

4. Simulation and Analysis

4.1. Simulation Discussion

We chose actual narrow waters for the analysis and experiments to complete the design of the cost function and simulation experiments.

A narrow harbor with a longitude of 121.5388° E and latitude of 38.8665° N was selected, and its satellite map and aerial map are shown in Figure 2.

The narrowest width of this narrow harbor is 10 m. Simulation verification was conducted in this harbor in which $n=5$ USVs were selected to form a USV system. It was assumed that an urgent mission was received to sail out of the narrow harbor for an operation, and the five USVs were located in different positions. Based on the narrow water standard route, we designed an initial optimal navigation trajectory for the five USVs, as shown in Figure 3.

If the algorithm was not used and multiple USVs followed the above path normally, there was a possibility that safety accidents could occur, causing unnecessary losses. Therefore, we used a distributed optimization algorithm to optimize the paths of multiple USVs so that they could safely and efficiently pass through the narrow harbor. We used the function to fit the paths in the graph, to rewrite the function, and we used it as a cost function for each USV. In addition, we used the algorithm above to calculate the paths of the USVs for the purpose of optimization, to ensure the connectivity between the USVs, and for collision avoidance.

The expression of the function was solved using spline interpolation as follows:

$$\begin{array}{cc}\hfill & f_1\left({\eta }_1\left(t\right),t\right)=\hfill \\ & {\left(x_1\left(t\right)-\left(-0.001t^5+0.0316t^4-0.3557t^3+1.4837t^2\right)\right)}^2\hfill \\ \hfill & +{\left(y_1\left(t\right)-\left(0.0004t^5-0.0116t^4+0.0633t^3+0.581t^2\right)\right)}^2,\hfill \end{array}$$

(25)

$$\begin{array}{cc}\hfill & f_2\left({\eta }_2\left(t\right),t\right)=\hfill \\ & {\left(x_2\left(t\right)-\left(-0.0005t^5+0.0158t^4-0.1779t^3+0.7418t^2+5\right)\right)}^2\hfill \\ \hfill & +{\left(y_2\left(t\right)-\left(-0.00004t^5+0.004t^4-0.116t^3+1.32t^2-5\right)\right)}^2,\hfill \end{array}$$

(26)

$$\begin{array}{cc}\hfill & f_3\left({\eta }_3\left(t\right),t\right)=\hfill \\ & {\left(x_3\left(t\right)-10)\right)}^2\hfill \\ \hfill & +{\left(y_3\left(t\right)-\left(0.0004t^5-0.0115t^4+0.0632t^3++0.581t^2\right)\right)}^2,\hfill \end{array}$$

(27)

$$\begin{array}{cc}\hfill & f_4\left({\eta }_4\left(t\right),t\right)=\hfill \\ & {\left(x_4\left(t\right)-\left(0.0005t^5-0.0158t^4+0.1779t^3-0.7418t^2+15\right)\right)}^2\hfill \\ \hfill & +{\left(y_4\left(t\right)-\left(-0.00004t^5+0.004t^4-0.115t^3+1.32t^2-5\right)\right)}^2,\hfill \end{array}$$

(28)

$$\begin{array}{cc}\hfill & f_5\left({\eta }_5\left(t\right),t\right)=\hfill \\ & {\left(x_5\left(t\right)-\left(0.001t^5-0.0316t^4+0.3557t^3-1.4837t^2+20\right)\right)}^2\hfill \\ \hfill & +{\left(y_5\left(t\right)-\left(0.0004t^5-0.0116t^4+0.0633t^3+0.581t^2\right)\right)}^2.\hfill \end{array}$$

(29)

The cost functions were all convex and can be written as $f_i({\eta }_i\left(t\right),t)=\left|\right|{\eta }_i\left(t\right)-s_i\left(t\right){\left|\right|}_2^2$. In the finite time that the multi-USV system passed through the narrow harbor, it satisfied $\left|\right|s_i\left(t\right)-s_j\left(t\right){\left|\right|}_2$, $\left|\right|{\dot{s}}_i\left(t\right)-{\dot{s}}_j\left(t\right){\left|\right|}_2$ and $\left|\right|{\ddot{s}}_i\left(t\right)-{\ddot{s}}_j\left(t\right){\left|\right|}_2$ were bounded, which shows that the cost function satisfied Remark 1 and met the algorithm’s requirements. We took them as the cost functions of the multi-USV system and used algorithm (6) to optimize them to plan a safe and optimal path for the multi-USV system to pass through the narrow harbor.

Then, we experimented with five USVs, with initial positions of ${\eta }_1={[0,0]}^T$, ${\eta }_2={[5,-5]}^T$, ${\eta }_3={[10,0]}^T$, ${\eta }_4={[15,-5]}^T$, and ${\eta }_5={[20,0]}^T$, and initial speeds of $\nu ={[0,0]}^T$. We set the desired distance as $d=2$ m.

The communication radius between USVs was changed for different complex sea areas. In order to simulate the impact of the actual marine environment and verify the feasibility of the algorithm, we designed different communication radius scenarios, e.g., limited communication between USVs and arbitrary communication between USVs, and the communication radii were set to be $\mathsf{{\rm Y}}=5$ m, $\mathsf{{\rm Y}}=10$ m, and $\mathsf{{\rm Y}}=30$ m. According to the above parameters, the simulation experiments were performed and the following simulation graphs were obtained.

Figure 4a,b show the trajectory of USVs with $\mathsf{{\rm Y}}=5$ m. Compared with the initially planned path in Figure 3, in the limited time, by using algorithm (6) to optimize the initial path, the distance between two neighboring USVs was close to $d=2$ m; thus, the collision between USVs was avoided. The maximum distance between the two USVs was $d_{max}<10$ m, which ensured that USVs could pass through the Lingshui Harbor of Dalian Maritime University safely and efficiently. In Figure 4c,d, we can see that before $t=2$ s, $u_1,u_2,u_3$, and $u_4$ gradually increased; after $t=2$ s, $u_1,u_2,u_3$, and $u_4$ began to converge and finally oscillated in a minimal range. Due to the initial trajectory, $u_3=0$, and v in a finite period, gradually increased and finally converged. In agreement with $\mathsf{{\rm Y}}=5$ m, the algorithm remained valid when $\mathsf{{\rm Y}}=10$ m and $\mathsf{{\rm Y}}=30$ m were present. According to Figure 5a,b, we can see that the planned path could enable the USV to pass through Lingshui Harbor of Dalian Maritime University safely and efficiently. From Figure 5c,d, we can see that u and v finally reached consistency in the finite time, although the oscillations were more obvious. According to Figure 6a,b, it can be seen that the planned path was smooth, and the USV could pass through Lingshui Harbor of Dalian Maritime University safely and efficiently. From Figure 6c,d, it can be seen that the speed of the USV did not exhibit the phenomenon of oscillation, and u and v reached consistency in a limited time.

In this experiment, from Figure 4a,b, Figure 5a,b and Figure 6a,b, it can be seen that, when $t=0$, if two USVs were neighbors of each other, then they were also neighbors of each other when $t>0$. On the contrary, when $t=0$, if two USVs were not neighbors of each other, then when $t>0$, there was no need to ensure that they were neighbors of each other, and there was no collision, which verified the feasibility of the potential function. Then, we discovered smoother planned paths and speeds occurred when any two USVs could communicate with each other. When the communication radius was too small, the speeds between USVs could be inconsistent, leading to oscillations within a small range. It is shown that the size of the communication radius affected the algorithm’s optimization of paths and speeds, so it was necessary to increase the communication radius, security, and reliability of the USVs by using the communication architecture of a polymorphic network. However, regardless of whether we chose $\mathsf{{\rm Y}}=5$ m, $\mathsf{{\rm Y}}=10$ m, or $\mathsf{{\rm Y}}=30$ m, the multi-USV system could navigate through Lingshui Harbor of Dalian Maritime University while avoiding collisions. This outcome confirms the effectiveness of the algorithm. It is worth noting that the initial speed v of the USV and the number of positive constants $c_1$ in the algorithm affected the convergence time. The convergence time was important in that it indicated the time needed to track the upper optimal speed $v^{*}$ between USVs with respect to reaching agreement. In the theoretical proof, the speeds reached consistency when the time tended to infinity, but in practice, the magnitude of $c_1$ affected the convergence time of the speeds.

To examine the effect of the initial positions on the algorithm, we re-tested Figure 6 by changing its initial positions to ${\eta }_1={[4,2]}^T$, ${\eta }_2={[9,-5]}^T$, ${\eta }_3={[15,0]}^T$, ${\eta }_4={[18,-5]}^T$, and ${\eta }_5={[22,-3]}^T$, and we suggested that the initial direction of the USV should be aligned with the destination direction as much as possible. From Figure 7, it can be seen that changing the initial position did not affect the speed of convergence, but it affected path planning. This shows that changing the initial position did not affect the effectiveness of the algorithm.

Next, in order to further verify the effectiveness of the algorithm, we simulated the curved narrow waterway. Again five USVs were selected for the experiment, and the initial positions were divided into ${\eta }_1={[0,4]}^T$, ${\eta }_2={[0,2]}^T$, ${\eta }_3={[0,0]}^T$, ${\eta }_4={[0,-2]}^T$, and ${\eta }_5={[0,-4]}^T$. The initial speeds were all $\nu ={[0,0]}^T$. The narrowest width of this narrow harbor is 8 m, the desired distance of $d=2$ m was selected. The cost function was designed as follows:

$$\begin{array}{cc}\hfill f_1\left({\eta }_1\left(t\right),t\right)=& {\left(x_1\left(t\right)-5t)\right)}^2\hfill \\ \hfill & +{\left(y_1\left(t\right)-\left(-0.009375t^5+0.1979t^4-1.187t^3+1.208t^2+2.9t+4\right)\right)}^2,\hfill \end{array}$$

(30)

$$\begin{array}{cc}\hfill f_2\left({\eta }_2\left(t\right),t\right)=& {\left(x_2\left(t\right)-5t)\right)}^2\hfill \\ \hfill & +{\left(y_2\left(t\right)-\left(-0.008854t^5+0.1823t^4-1.01t^3+0.2708t^2+5.183t+2\right)\right)}^2,\hfill \end{array}$$

(31)

$$\begin{array}{cc}\hfill f_3\left({\eta }_3\left(t\right),t\right)=& {\left(x_3\left(t\right)-5t)\right)}^2\hfill \\ \hfill & +{\left(y_3\left(t\right)-\left(-0.008333t^5+0.1667t^4-0.8333t^3-0.6667t^2+7.467t\right)\right)}^2,\hfill \end{array}$$

(32)

$$\begin{array}{cc}\hfill f_4\left({\eta }_4\left(t\right),t\right)=& {\left(x_4\left(t\right)-5t)\right)}^2\hfill \\ \hfill & +{\left(y_4\left(t\right)-\left(-0.007812t^5+0.151t^4-0.6562t^3-1.604t^2+9.75t-2\right)\right)}^2,\hfill \end{array}$$

(33)

$$\begin{array}{cc}\hfill f_5\left({\eta }_5\left(t\right),t\right)=& {\left(x_5\left(t\right)-5t)\right)}^2\hfill \\ \hfill & +{\left(y_5\left(t\right)-\left(-0.007292t^5+0.1354t^4-0.4792t^3-2.542t^2+12.03t-4\right)\right)}^2.\hfill \end{array}$$

(34)

We chose the communication radius $\mathsf{{\rm Y}}=10$ m and the parameters $c1=0.8$, $c2=1$, according to the initial conditions and the cost function to carry out the simulation experiments, and the experimental results are shown in Figure 8.

As we can see from Figure 8, the multi-USV system could pass through this curved narrow waterway smoothly, the speeds were consistent in a finite time, and no collision occurred between the USVs. This further illustrates the effectiveness and practicality of the algorithm.

4.2. Robustness Discussion

In a real environment, the USV will be disturbed by external factors such as wind, waves, and currents. To demonstrate the robustness of the proposed distributed optimization algorithm to different disturbances in complex environments, we tested the two experimental scenarios in the previous paper separately, where the initial values were kept the same as those in the previous paper. We considered an external disturbance ${\tau }_d={[2.5sin\left(t\right),2cos\left(1.7t\right)]}^T$. From Figure 9 and Figure 10, we see that the multi-USV system could safely and efficiently pass through the narrow waterway and the speeds converged in a finite time. This test verified that the algorithm in this paper is robust.

5. Conclusions

This paper investigates the problem of path planning for multiple USVs in the ocean when passing through narrow waters safely and efficiently. Firstly, multiple USVs were studied based on distributed control, where each USV was considered an autonomous entity without a central control node. Secondly, the method of narrow water standard route in navigation was utilized to plan an optimal path for multiple USVs to pass through narrow waters. Then, the spline interpolation method was used to design functions to fit the different paths, and the rewritten form of the function served as the corresponding cost function for USVs. Next, a polymorphic network was constructed to minimize the global cost function through the interaction of position and velocity information between neighboring USVs, while avoiding collisions between USVs. Finally, Lingshui Harbor of Dalian Maritime University and a curved narrow waterway were selected for the simulation experiments, and the robustness of the algorithm was assessed. The experimental results show that, under the distributed optimization algorithm, the planned paths of multiple USVs were all optimal paths, collision was avoided, and the consistency of the speed was achieved in a limited time, so that the USVs were able to pass through the narrow waterway safely and efficiently. This shows that the algorithm has a certain robustness.