Underactuated unmanned surface vehicles formation of obstacle avoidance and assembly: A disturbed fluid-based solution

Abstract

Unmanned surface vehicles (USVs) are highly manoeuvrable and autonomous, and hold significant potential for both military and civilian applications, particularly in formation operations. However, because of their underactuated nature, USVs struggle to navigate in complex maritime conditions during formation. At present, most of the technology is devoted to Unmanned Areial Vehicles and ground robots; these methods cannot be well applied to underactuated USVs. Moreover, the rationality of local path planning decision-making for underactuated USVs formation is still lacking. This study proposes an interfered fluid dynamic system (IFDS)-based local path planning method, called USV-IFDS, specifically designed for the formation of underactuated USVs. This method incorporates the IFDS obstacle avoidance approach, while adapting it through modifications and the inclusion of the kinematic constraints of USVs, thereby enhancing its applicability to the maritime environment. By decomposing the flow field velocity vector and implementing a formation control strategy, we effectively address the challenges in forming underactuated USVs and enhance the efficiency of USV formation local path planning. The proposed formation technique is predicated on the highly robust virtual structure method. Simulations of formation local path planning indicate that our method produces smooth paths, therefore validating its practical applicability to underactuated USV formations.

Keywords

Unmanned surface vehicle virtual structure method interfered fluid dynamical system formation flocking formation obstacle avoidance local path planning

Introduction

In recent years, the advancement of unmanned and intelligent operations has spurred the rapid development of unmanned surface vehicles (USVs). As a crucial element of unmanned maritime systems, USVs stand out because of their speed, intelligence, size, light weight, high manoeuvrability and agility, cost efficiency and elimination of potential human casualties, compared to traditional surface vehicles.¹ USVs play a vital role in military activities such as intelligence gathering, reconnaissance, precision attacks and special operations, and therefore, have attracted significant research attention.² Their diversified functions, higher manoeuvrability and cost efficiency enable them to perform an extensive array of military and civilian tasks, including hydrographic exploration, weather forecasting, maritime search and rescue, and policing and patrol. This versatility suggests a broad scope for their application in the effective utilisation, development and conservation of marine resources.³

However, the capability of individual USVs to perform diverse maritime operations is inherently limited. As a result, the formation of USVs to enhance their operational efficiency and range has emerged as a mainstream research direction. When compared to individual USVs, the formations of these vehicles offer several advantages^4–6:

(1) Enhanced operational efficiency: The coordinated control of a group of USVs, optimised decision making and task allocation based on mission requirements, and interactive information communication among multiple USVs enable tasks to be distributed and coordinated effectively. This approach markedly improves the efficiency of task resolution and execution.

(2) Increased reliability of mission execution: Interactive information communication within a USV formation mitigates the limitations of individual USVs in achieving autonomous, comprehensive perception. This enhancement improves the range and precision of perception and detection, thereby increasing the efficiency of the formation in acquiring and processing target information.

(3) Improved operational fault tolerance: In the case of individual USVs, a failure of critical equipment can significantly reduce the efficiency or even lead to mission failure. However, with USV formations, the coordinated control and interactive information communication among the multiple USVs enable optimised decision making, timely response and flexible adjustment of the operational plan, providing a better safeguard for successful operation execution.

Therefore, USV formations exhibit superior perception, task execution and fault-tolerance capabilities compared to individual USVs, marking a compelling direction for future technological development.

Underactuated USV formation local path planning is a critical aspect of formation operations and intelligent control, encompassing two main challenges: formation flocking (FF) and obstacle avoidance (OA). Given that USVs lack lateral propulsion, their underactuated nature results in less agility on water surfaces and makes their movement trajectories challenging to track.⁷ Therefore, a path-planning strategy that enables smooth navigation with high computational efficiency is needed. The virtual structure method, which is simple and highly robust, is employed to maintain a moving flock of USVs in an organised pattern. This method considers the formation shape as a rigid structure, providing clear feedback on the formation shape and enabling better determination and maintenance of the formation behaviour. However, this approach struggles to adapt flexibly and autonomously to complex sea conditions. Moreover, the underactuated nature of USVs (lack of lateral propulsion) limits the flexibility of a USV formation in responding to obstacles for collision avoidance.

State of the art approaches

To address these limitations, we have conducted extensive research and identified the following mainstream solutions: (Table 1)

(1) geometry-based methods, such as the velocity obstacle method^8–11;

(2) model predictive control (MPC) methods, for instance, the distributed MPC and neural-dynamic-based nonlinear MPC methods^12,13;

(3) stochastic planning methods such as the rapidly exploring random tree algorithm and its modified versions^14,15;

(4) the artificial potential field (APF) method^16–18;

(5) intelligent optimisation algorithms, for instance, neural networks and reinforcement learning.¹⁹

Table 1.

Current mainstream solutions.

Solutions	Instance	Disadvantage
Geometry-based methods	Velocity obstacle method	Underactuated USV cannot respond well
Model predictive control (MPC) methods	Distributed MPC method	Lack of rapid response and inefficient computation
Stochastic planning methods	Rapidly exploring random tree algorithm	Calculation efficiency is low in complex environments
The artificial potential field (APF) method	The artificial potential field	More local minimum problems
Intelligent optimisation algorithm	Neural networks and reinforcement learning	Sample inefficiency and lack of flexibility and generalisability

The first three methods generate formation strategies that accommodate the internal structure of a formation and its relationship with obstacle avoidance. However, these strategies are not suitable for USVs because of their underactuated nature and lack of agile response. Moreover, these methods involve computational loads that increase exponentially with the expansion of the operational task and range, leading to inefficient computation for obstacle-free paths and potential loss of tracking targets. The fifth method, reinforcement learning, has the fundamental defect of ‘sample inefficiency’ in obstacle avoidance and lacks flexibility and generalizability; therefore, it does not have good practicability in the obstacle avoidance of underactuated USVs.

A disturbed fluid-based solution

To address these limitations, we have proposed real-time path planning and OA methods inspired by the behaviour of fluids under complex conditions. The most notable among these is the interfered fluid dynamic system (IFDS) method proposed by Wang et al.^20–25 The IFDS method outperforms other fluid behaviour-inspired methods by generating smooth motion paths while maintaining low computational load and high controllability. It offers global optimisation, smooth motion paths and parallel computations, outperforming the APF method by overcoming its local minimum problem. These advantages of the IFDS method over the APF method have also been discussed in previous studies.^20–23 However, traditional IFDS methods do not account for the kinematic characteristics of USVs or the constraints on USV formation. Additionally, they are limited in OA under two-dimensional (2D) conditions and cannot generate a 2D local path planning strategy for the formation of underactuated USVs. To address these issues, this study proposes a USV-specific IFDS local path planning method, called USV-IFDS. This method incorporates the kinematic constraints of USVs, overcomes the limitations of traditional IFDS methods in 2D environments, and ultimately establishes an IFDS strategy suitable for USV formation local path planning.

Model of the problem

Model of obstacles

USV sensor detection of obstacles tends to be excessively precise for path-planning applications. To enhance the efficiency of local path planning, obstacles are abstracted into regular convex shapes. For instance, islands, reefs and shores are represented as triangles, rectangles, hexagons, ellipses, circles or combinations thereof. Moving boats and ships are approximated as circles and ellipses. Hence, obstacles can be expressed using the following equation²⁶:

Γ (ξ) = (\frac{x_{t} - x_{0}}{a})^{2 c} + (\frac{y_{t} - y_{0}}{b})^{2 d}

(1)

where ξ = (x_t, y_t) represents the USV position at a given moment t and ξ₀ = (x₀, y₀) denotes the centre of the obstacle. The terms a and b are the axial lengths of the obstacle; c and d are the obstacle shape parameters. For an obstacle with sharp boundaries, reasonably chosen axial lengths and shape parameters can moderate the sharpness of the obstacle boundaries to an acceptable extent. This adjustment aligns with USV manoeuvrability constraints and substantially enhances the feasibility of the obstacle avoidance path.

Kinematic model (constraints) of underactuated USVs

The first and most important step to develop the USVs mathematical model is to represent the movement on a 2D plane.²⁷ Because the focus of this study was path planning and the USV is underdriven and does not have transverse thrust, only its pitch and roll motion are considered. Meanwhile, owing to the minimal planning period and short motion distance of adjacent prediction points, it can be regarded as linear continuous motion. The model is as follows:

{\begin{matrix} x_{t + 1} = x_{t} + V_{t} Δ t \cos (θ_{t}) \\ y_{t + 1} = y_{t} + V_{t} Δ t \sin (θ_{t}) \\ θ_{t + 1} = θ_{t} + ω_{t} Δ t \end{matrix}

(2)

where x_t, y_t, θ_t, V_t and ω_t denote the x-coordinate, y-coordinate, course angle, velocity amplitude and steering angular velocity of the USV in the geodetic coordinate system at a given moment t, respectively.

Considering the limitations in USVs power and direction-changing ability as well as the constraints on their manoeuvrability, the USV velocity vector, ${\overset{⇀}{V}}_{\lim}$ , can be expressed as

{\overset{⇀}{V}}_{\lim} = {(V, ω) | v \in [V_{\min}, V_{\max}], ω \in [ω_{\min}, ω_{\max}]

(3)

The actual velocity at the next moment, V_t+₁, can be expressed as

{\overset{⇀}{V}}_{t + 1} = {(V_{t + 1}, ω_{t + 1}) | V_{t + 1} \in [V_{t} - a_{v -} Δ t, V_{t} + a_{v +} Δ t], ω_{t + 1} \in [ω_{t} - a_{ω} Δ t, ω_{t} + a_{ω} Δ t]

(4)

where (V_min, V_max) represents the velocity range; (ω_min, ω_max) represents the steering angular velocity range; and α_v-, α_v+ and α_ω refer to the deceleration, acceleration and steering performances of the velocity, respectively.

USV-IFDS local path planning method

Description of the IFDS method

The traditional IFDS method contemplates three-dimensional OA. However, given that ships can only move on the water surface and their manoeuvrability is limited, only the 2D aspect of the IFDS method is discussed here. Prior to path planning using the IFDS method, all obstacles are modelled using equation (1), with the destination set as ξ_d = (x_d, y_d) and the number of obstacles denoted as K.

When the USV is positioned on an obstacle-free water surface, the initial flow field is established considering the path from the USV current position at a given moment t to the destination as a straight line with a velocity amplitude of V. Hence, the initial flow field along the two axes of the geodetic coordinate system, u, can be expressed as

u_{t} = {[\begin{matrix} \frac{V (x_{d} - x_{t})}{d} \frac{V (y_{d} - y_{t})}{d} \end{matrix}]}^{T}

(5)

where $d = \sqrt{{(x_{t} - x_{d})}^{2} + {(y_{t} - y_{d})}^{2}}$ is the distance from the USV position at moment t to the destination.

When the USV is positioned on a water surface with K obstacles, the total disturbance of the obstacles to the initial flow field μ_t can be expressed in matrix form ( $\bar{M}$ ):

\bar{M} = \sum_{k = 1}^{K} W_{k} M_{k}

(6)

where W_k is the weight of the kth obstacle, which increases as the distance between the obstacle and USV decreases, and M_k is the disturbance matrix of the kth obstacle. W_k and M_k can be expressed as

W_{k} = {\begin{matrix} 1 \\ Π_{i = 1, i \neq k}^{K} \frac{(Γ_{i} - 1)}{(Γ_{i} - 1) + (Γ_{k} - 1)} \end{matrix} \begin{matrix} K = 1 \\ K \neq 1 \end{matrix}

(7)

M_{k} = I - \frac{n_{k} n_{k}^{T}}{{| Γ_{k} |}^{1 / ρ_{k}} n_{k}^{T} n_{k}}

(8)

where I is the attraction matrix (a second-order identity matrix illustrating the effects of the destination on the USV); $- \frac{n_{k} n_{k}^{T}}{{| Γ_{k} |}^{1 / ρ_{k}} n_{k}^{T} n_{k}}$ is the repulsion matrix (representing the effects of the obstacle on the initial flow field); ρ_k is the repulsion coefficient (adjusting the OA response of the USV to the obstacle, where a larger ρ_k value indicates a stronger OA response to the obstacle); and $n^{k} = {[\begin{matrix} \frac{\partial Γ_{k}}{\partial x} \frac{\partial Γ_{k}}{\partial y} \end{matrix}]}^{T}$ is the normal vector of the obstacle surface.

Subsequently, moving obstacles such as ships and platforms are taken into account to facilitate dynamic OA. Consequently, the original flow velocity u_t is adjusted. The resulting total interfered flow velocity can be expressed as

\bar{u_{t}} = \bar{M} (u_{t} - v_{Γ}) + v_{Γ}

(9)

where v_Г is the total velocity vector of the obstacles and can be expressed as

v_{Γ} = \sum_{k = 1}^{K} W_{k} e^{\frac{1 - Γ_{k}}{λ_{k}}} v_{Γ_{k}}

(10)

where λ_k is the constant of the kth obstacle and v_Гk is the velocity vector of the kth obstacle. Accordingly, ${\bar{u}}_{t} = {[\begin{matrix} \bar{u_{x_{t}}} \bar{u_{y_{t}}} \end{matrix}]}^{T}$ , and the USV position at the next moment is updated as $ξ_{t + 1} = (x_{t + 1}, y_{t + 1}) = (x_{t} + \bar{u_{x_{t}}} Δ t, y_{t} + \bar{u_{y_{t}}} Δ t)$ , where Δt represents the sampling time. Finally, a motion path can be obtained by integrating the USV position with respect to the sampling time.

The aforementioned method exhibits the following characteristics:

Theorem 1: When the USV is at a considerable distance from any obstacle, its motion path follows a straight line in the original direction.

Theorem 2: Obstacles cannot be penetrated.

Proof: (1) When the USV is far from any obstacle, because $Γ_{k} = \infty$ , ${\bar{u}}_{t} = u_{t}$ .

(2) If the USV is positioned at the surface of an obstacle, ensuring that the normal velocity remains at zero will prevent the obstacle from being penetrated. Hence, it is only necessary to demonstrate that $n_{k}^{T} \bar{u_{t}} = 0$ . Because Г_k = 1 when the USV is located at the obstacle’s surface and $n_{k}^{T} M_{k} = n_{k}^{T} - \frac{n_{k}^{T} n_{k} n_{k}^{T}}{n_{k}^{T} n_{k}} = n_{k}^{T} - n_{k}^{T} = 0$ , the condition that an obstacle cannot be penetrated is satisfied.

Description of the USV-IFDS

The previous derivation illustrates that the conventional IFDS method for 2D path planning does not account for the kinematic constraints of USVs. Therefore, this study introduces the USV-IFDS method, which takes the kinematic constraints of USVs into account using a kinematic model, ensuring the feasibility of motion paths.

Let us denote the current course angle of the USV at moment h as θ_h; the interfered flow velocity obtained using equation (9), ${\bar{u}}_{h} = {[\begin{matrix} \bar{u_{x_{h}}} \bar{u_{y_{h}}} \end{matrix}]}^{T}$ , represents the expected OA velocity at the next moment. From this relation, the expected course angle can be determined: $\tan θ_{h + 1} = \frac{\bar{u_{y_{h}}}}{\bar{u_{x_{h}}}}$ . Hence, the expected steering angular velocity becomes $ω_{h} = \frac{θ_{h + 1} - θ_{h}}{Δ t}$ .

Considering the constraint of angular velocity, the actual output course angle, θ_true, can be derived:

θ_{t rue} = {\begin{matrix} θ_{h + 1} & ω_{min} \leq ω_{h} \leq ω_{max} \\ θ_{h} + Δ t ω_{max} & ω_{max} \leq ω_{h} \\ θ_{h} + Δ t ω_{min} & ω_{h} \leq ω_{min} \end{matrix}

(11)

By replacing the expected course angle with the constrained course angle, θ_true, the actual course angle at the following moment can be derived. The output-constrained course angle can be substituted into equation (2) to derive the position of the USV at the next moment.

Method for solving local minima

The USV-IFDS path planning method outlined in the previous section can effectively simulate the path of natural water flow and overcomes the local minimum problem associated with the APF method. However, it is evident that the USV-IFDS method still encounters issues with stagnation points and trap areas. To better resolve these problems, we made modifications to ensure the feasibility of the motion paths.

Stagnation point analysis and improvement solution

Figure 1 illustrates the situation where the USV, goal and obstacle are in a straight line.

Figure 1.

Stagnation point example.

When the USV moves to the centre of an obstacle with the goal directly behind the obstacle, the initial flow field from the goal to the USV (u) and the repulsion flow field from the obstacle to the USV (n) are collinear but in opposite directions. This situation results in a decreasing total flow field velocity $\bar{u}$ , which exactly equals zero when the USV reaches the surface of the obstacle. Consequently, the USV stagnates at that point, creating a stagnation point under 2D conditions.

To overcome this problem, we introduced an escape matrix to improve the stagnation point issue of the USF-IFDS in 2D planes. We first obtain a tangent vector $τ_{k} = {[\begin{matrix} \frac{\partial Γ_{k}}{\partial y} - \frac{\partial Γ_{k}}{\partial x} \end{matrix}]}^{T}$ that is perpendicular to the normal vector n_k of the obstacle surface. This tangent vector is incorporated into a matrix added to equation (8):

M_{k} = I - \frac{n_{k} n_{k}^{T}}{{| Γ_{k} |}^{1 / ρ_{k}} n_{k}^{T} n_{k}} + \frac{i τ_{k} n_{k}^{T}}{{| Γ_{k} |}^{1 / σ_{k}} n_{k}^{T} n_{k} C_{k}}

(12)

Here, the newly added term, $\frac{i τ_{k} n_{k}^{T}}{{| Γ_{k} |}^{1 / σ_{k}} n_{k}^{T} n_{k} C_{k}}$ , represents the escape matrix, which operates on similar principles as the repulsion matrix. The tangent vector τ_k is projected onto the initial flow field to adjust the effects of the initial flow field. $i \in [- 1, 1]$ is used to adjust the escape direction, causing the USV to veer towards the right boundary if it is closer to the right boundary, and towards the left boundary if it is closer to the left boundary. The escape coefficient of the kth obstacle is represented by σ_k, with a larger escape coefficient indicating a faster speed to avoid the stagnation point. We introduce a constant, C_k, to mitigate its effect on OA performance. If C_k is assigned a reasonable value, the magnitude of the escape matrix is considerably smaller than that of the repulsion matrix, which minimises its effect on the original motion path and avoids the creation of sharp curves.

When the USV is heading towards the stagnation point, the tangent vector τ_k helps the USV to deviate slightly in the direction perpendicular to the course, thus escaping from the stagnation point.

The proof that the escape matrix does not affect the course is as follows: When the USV is at the surface of the obstacle, because $n_{k}^{T} i τ_{k} = 0$ , $n_{k}^{T} \bar{u} = 0$ ; that is, theorem 1 is satisfied. When the USV is far away from any obstacle, because Г_k increases monotonically as the USV moves away from the obstacle and C_k affects the escape matrix, the norm of the escape matrix is infinitesimal, that is, theorem 2 is satisfied. Hence, the flow field with the addition of the escape matrix still satisfies the requirements for path planning.

Trap area problem and improvement solution

The issue of ‘trap areas’ arises when multiple overlapping obstacles are present in the planning space, enclosed by the common tangent of the two circles and the boundaries of the obstacles as shown in Figure 2; this situation forms an enclosed space or ‘trap’ to the trap situation occurs because of a limitation in the algorithm. When the USV is located at the junction of two obstacles, both Г_k and Г_k+1 equal 1, causing the denominator of equation (7) used for weight calculation to become 0. As a result, navigation planning fails. This issue is particularly likely to occur when the two obstacles are large, parallel-moving ships. To mitigate navigation collision risks and take into account the limited manoeuvrability of underactuated USVs, a virtual goal strategy can be employed to navigate around these trap areas.

Figure 2.

Trap area example.

First, when a trap area is identified, a virtual goal is created on the basis of the following observations:

(1) The presence of multiple overlapping obstacles;

(2) The interfered flow velocity $\vec{u}$ moving towards the trap area;

(3) $min {d (ξ, ξ_{1}), d (ξ, ξ_{2}), d (ξ, ξ_{3}), . . . d (ξ, ξ_{k})} \leq d_{TA}$ .

Here, d_TA represents a threshold value, which is established considering factors such as the manoeuvrability of the USV, number of overlapping obstacles and area of the trap. D(ξ, ξ_k) measures the distance from the USV to the kth obstacle.

Figure 3 illustrates a scenario where all these conditions are fulfilled. A circular sector is defined with the centre of the USV model serving as the origin, a radius of d_TA and a central angle derived from the course angle of the USV and the maximum turning angle, which falls within the range (θ_t − φ_max, θ_t + φ_max).

Figure 3.

Creation of a virtual goal.

N discrete points, represented as v (virtual goals), are chosen on the arc. These N points form a set of optimal options v_1,2,3…N for the virtual goal. Lastly, the N virtual goals are assessed, with a lower cost function value indicating a superior choice for the virtual goal. The cost function, eval, is given as follows:

eval = λ_{1} α + λ_{2} β + λ_{3} ϑ

(13)

Here, (λ₁, λ₂, λ₃) are the weights, α represents the safety cost for determining whether the USV collides with an obstacle, β represents the distance cost for determining the extra distance of movement and $ϑ$ represents the escape cost for determining whether the USV has escaped from the trap area.

α = {\begin{matrix} Π_{k = 1}^{K} 1 / Γ_{k} (ξ_{v}) \\ + \infty \end{matrix} \begin{matrix} Γ_{k} (ξ_{v}) > 1 \\ Γ_{k} (ξ_{v}) \leq 1 \end{matrix}

β = \frac{d (ξ_{v}, ξ_{d}) - min d (ξ_{v}, ξ_{d})}{d_{max} (ξ_{v}, ξ_{d}) - min d (ξ_{v}, ξ_{d})}

ϑ = {\begin{matrix} 0 \\ + \infty \end{matrix} \begin{matrix} from USV to v without passing throug the trap area \\ Otherwise \end{matrix}

When the virtual goal satisfies the cost function and feasibility requirements, the USV advances to the virtual target point and after driving to the virtual target point, it sails to the target point again, thereby escaping the trap area.

Formation local path planning using the USV-IFDS method

The preceding explanation covers local path planning for a single USV using the USV-IFDS method, which makes the IFDS method more suitable for the specific operating environment of USVs. To further refine this method for formation coordination, we break down the formation problem into two aspects: local path planning for FF and local path planning for formation OA. To simplify the problem and make the method more practical, we consider these two aspects separately. For formation maintenance, given the stability and safety requirements of an underactuated USV formation, we employ a highly robust virtual structure method as our formation strategy. In other words, we treat the entire formation as a rigid body.

Formation flocking strategy

The local path planning for individual USVs during FF considers the constraints of a single USV described in Section ‘A disturbed fluid-based solution’ as well as the requirements for OA and FF. We assume that there are only a small number of obstacles in the path of flocking, as illustrated in Figure 4.

Figure 4.

Formation flocking example.

Here, we use the virtual structure points associated with individual USVs as the respective goals of their initial flow fields. Given the rock-avoidance characteristic of water flow, which is fundamental to the IFDS method, each USV can effectively avoid obstacles and reach the assembly point through the shortest possible path. Furthermore, to ensure the task execution by a USV formation is both efficient and feasible, we consider two things. First, we treat the virtual structure points (the goals of the initial flow fields) as dynamic goals during the configuration of the initial flow fields. This approach allows a task to be assigned to a USV formation before the individual USVs reach their designated positions, significantly reducing the time needed for FF and task execution. Second, it is possible that the path of a USV flocking to the assembly point intersects with that of another USV. To ensure safe and simultaneous flocking, we treat each USV as a dynamic obstacle for the others. Furthermore, we decouple the vectors and scalars of each USV initial flow field. As a result, equation (5) is broken down into velocity amplitude V and vector ${[\begin{matrix} \frac{x_{d} - x_{t}}{d} \frac{y_{d} - y_{t}}{d} \end{matrix}]}^{T}$ . The velocity amplitude is then adjusted according to the distance to the virtual structure point, as demonstrated in Figure 5.

Figure 5.

Distance to a virtual structure point.

The relationship between the velocity amplitude and distance is characterised as

V = {\begin{matrix} \begin{matrix} V_{max} \\ V_{vir} + (V_{max} - V_{vir}) e^{- λ_{vir 2} (d_{vir 2} - d)} \\ V_{vir} e^{- λ_{vir 1} (d_{vir 1} - d)} \end{matrix} \begin{matrix} d \geq d_{vir 2} \\ d_{vir 1} \leq d < d_{vir 2} \\ d < d_{vir 1} \end{matrix} \end{matrix}

(14)

where V_max represents the maximum velocity amplitude and V_vir is the presupposed velocity of the virtual structure point. The variables d_vir1 and d_vir2 are threshold values for the distance to the virtual structure point, and d is the actual distance from the USV to the virtual structure point. λ_vir1 and λ_vir2 are the constants to adjust the velocity magnitudes at the two distance thresholds. According to equation (14), when outside d_vir2, the USV moves closer to the virtual target point at the maximum speed, and when inside d_vir1, the USV slows and moves away from the virtual target point; thus, we can effectively manage the velocity magnitude of each USV so that it aligns with the presupposed velocity. Adjusting d_vir1 and d_vir2 enables us to control the distance from the USV to the virtual structure point, thereby enhancing the reliability of FF. Furthermore, once a USV moves into the interval between d_vir1 and d_vir2, other USVs are no longer considered obstacles. This approach ensures that individual USVs within a formation do not interfere with one another during formation navigation.

When every USV in the formation has moved into the interval between d_vir1 and d_vir2 relative to its corresponding virtual structure point, the formation has successfully completed the flocking phase and can begin the formation navigation phase.

Formation OA strategy

The interfered flow field-based OA strategy designed for a single USV is also utilised for formation OA. A USV retains its agility whether it is navigating individually or within a formation. Furthermore, because of the inherent properties of the flow fields, their streamlines do not intersect even when they share the same response coefficient for the same obstacle. This feature provides a certain degree of safety during formation OA. However, there are still challenges, as illustrated in Figure 6.

Figure 6.

Formation OA example.

When two or more USVs are on the same side of an obstacle, their streamlines do not intersect, but the space between the streamlines may become excessively small. Given that actual USVs are not mass points but objects with a certain volume, this situation could be unsafe for formation navigation. If each USV is considered an obstacle to the others as during FF (as described in Section ‘Formation flocking strategy’), the OA performance of the USVs will be significantly compromised. Therefore, a new solution is needed for this problem.

For a formation consisting of F_tot USVs to avoid the kth obstacle, the disturbance matrix M_k for each USV is computed using equation (12). Then, the formation matrix is added to account for the effects of the other F_tot − 1 USVs on the current USV. The formation matrix of the fth USV in the formation affecting the current USV is expressed as $\frac{χ_{f} n_{k}^{T} (1 - e^{1 - Γ_{k}})}{{| Γ_{k} |}^{1 / ρ_{kf}} ‖ χ_{f} ‖ ‖ n_{k}^{T} ‖} F_{f}$ . A matrix is added for each additional USV. This formation matrix can make the USV move away from the other USVs corresponding to each matrix through the repulsion vector. The final total disturbance matrix is expressed as

\begin{matrix} M_{k} = I - \frac{n_{k} n_{k}^{T}}{{| Γ_{k} |}^{1 / ρ_{k}} n_{k}^{T} n_{k}} + \frac{i τ_{k} n_{k}^{T}}{{| Γ_{k} |}^{1 / σ_{k}} n_{k}^{T} n_{k} C_{k}} + \frac{χ_{f} n_{k}^{T} (1 - e^{1 - Γ_{k}})}{{| Γ_{k} |}^{1 / ρ_{kf}} ‖ χ_{f} ‖ ‖ n_{k}^{T} ‖} F_{f} \\ + \frac{χ_{f + 1} n_{k}^{T} (1 - e^{1 - Γ_{k}})}{{| Γ_{k} |}^{1 / ρ_{kf + 1}} ‖ χ_{f + 1} ‖ ‖ n_{k}^{T} ‖} F_{f + 1} . . . . . + \frac{χ_{Ftot - 1} n_{k}^{T} (1 - e^{1 - Γ_{k}})}{{| Γ_{k} |}^{1 / ρ_{kFtot - 1}} ‖ χ_{Ftot - 1} ‖ ‖ n_{k}^{T} ‖} F_{Ftot - 1} \end{matrix}

(15)

where $χ_{f} = {[\begin{matrix} x_{f} - x_{t} y_{f} - y_{t} \end{matrix}]}^{T}$ is the repulsion vector of the fth USV to the current USV (where (x_f, y_f) is the predicted position of the fth USV at the next moment); $‖ • ‖$ is the 2-norm of the vector; ρ_kf is the modulation coefficient of the formation matrix of the effects of the fth USV on the current USV during OA, with a larger modulation coefficient indicating better performance; and F_f is the response coefficient, which changes with the distance from the fth USV to the current USV and is expressed as

F_{f} = {\begin{matrix} \begin{matrix} \frac{e^{d_{w} - d_{f}}}{2} d_{f} \geq d_{w} \end{matrix} \\ \begin{matrix} 1 - \frac{e^{d_{f} - d_{w}}}{2} d_{f} < d_{w} \end{matrix} \end{matrix}

(16)

where d_f is the distance from the fth USV to the current USV and d_w is the warning distance for the current USV. Equation (16) decreases monotonically, is continuous, and converges between 0 and 1. Thus, F_f decreases as the distance increases and converges at 0 as the distance increases to a certain value. F_f increases as the distance decreases and converges at 1 when the distance decreases to a certain value.

Similar to the proof of escape, the reasonableness of the formation matrix is demonstrated as follows: When the USV is far from any obstacle, $Γ_{k} = \infty$ and consequently, $1 - e^{1 - Γ_{k}}$ is approximately equal to 1, the formation matrix is infinitesimal, and theorem 1 is satisfied. When the USV is at the obstacle surface, because $Γ_{k} = 1$ , $1 - e^{1 - Γ_{k}} = 0$ , the formation matrix equals 0, and $n_{k}^{T} \bar{u} = 0$ ; that is, theorem 2 is satisfied.

Simulation

Case study using the USV-IFDS and IFDS methods

Comparison of imposed constraints

Unlike the IFDS method, the USV-IFDS method accounts for kinematic constraints. To demonstrate that the USV-IFDS method is more appropriate under 2D conditions, a path planning case was simulated using both methods separately. The conditions were as follows: starting point of (1, 1) m, goal of (200, 200) m, USV course angle θ = 45°, velocity V = 7.5 m/s (uniform), centre of obstacle at (100, 90) m, obstacle radius of 25 m and repulsion coefficient ρ_k = 3 (to ensure that the variables have unique values for both the USV-IFDS and IFDS methods). Figure 7 shows the angular velocities produced by the two methods.

Figure 7.

Angular velocities yielded by the USF-IFDS (constraint: maximum angular velocity 0.1 rad/s) and IFDS methods.

As illustrated in Figure 7, the USV-IFDS method more effectively adheres to the kinematic constraints compared to the IFDS method.

Comparison of local minima

Unlike the traditional IFDS method, the USV-IFDS method effectively resolves the issue of stagnation points. To compare these two methods in this regard, a stagnation point avoidance problem was separately solved using both methods under the following conditions: starting point of (1, 1) m, goal of (100, 100) m, course angle θ = 45°, velocity V = 7.5 m/s (uniform), centre of the obstacle at (50, 50) m, obstacle radius of 15 m and repulsion coefficient ρ_k = 3 for both methods. For the USV-IFDS method, the escape coefficient σ_k was set to 1, and the constant C_k was set to 10. The results are shown in Figure 8.

Figure 8.

Comparison of stagnation point avoidance performance: (a) IFDS method and (b) USV-IFDS method.

The USV-IFDS method demonstrated strong capabilities in navigating away from stagnation points and effectively resolving stagnation point issues. It produced a path that not only complied with OA requirements but was also smooth, thereby validating its exceptional effectiveness in local OA planning for underactuated USVs.

In addition, the USV-IFDS method successfully addressed the trap area issue. This was confirmed with the following test case: start point of (1, 1) m, goal of (100, 100) m, USV angle θ = 45°, velocity V = 7.5 m/s (uniform), centre of obstacle #1 at (50, 60) m, centre of obstacle #2 at (60, 50) m, radii of both obstacles of 15 m, repulsion coefficient ρ_k = 3, escape coefficient σ_k of 1 and constant C_k of 10. The results are presented in Figure 9.

Figure 9.

Configuration of virtual goal for escaping from a trap area using the USV-IFDS method. The method succeeded in generating a virtual goal and escaping from the trap area.

Formation local path planning (formation flocking)

The performance of the USV-IFDS method in local path planning for FF was verified by simulating the flocking of three USVs using the following parameter settings: The starting positions for USV #1, #2 and #3 were (10, 10) m, (40, 1) m and (1, 40) m, respectively; the maximum velocity was 23 m/s (approximately 45 knots); the course angle θ was 45°; the repulsion coefficient ρ_k was 3; the escape coefficient σ_k was set at 1; and the constant C_k was set at 10. The centres of the three obstacles were located at (80, 60) m, (30, 50) m and (100, 110) m, with radii of 9, 12 and 11 m, respectively. The initial positions of the virtual structure points for USV #1, #2 and #3 were (150, 120) m, (150, 150) m and (120, 150) m, respectively. The uniform velocity of the virtual structure formation was 7.5 m/s (approximately 15 knots), with a course angle θ of 45°. The distance thresholds were d_vir1 = 10 m and d_vir2 = 11 m. The velocity magnitude adjustment constants at the distance thresholds were λ_vir1 = 0.5 and λ_vir2 = 8. Figure 10 illustrates the movement trajectories of the flocking USVs.

Figure 10.

Formation flocking trajectories yielded by the USV-IFDS method.

As shown in Figure 11, equation (14) was effective in converging the velocity amplitude of individual USVs to match the velocity amplitude of the virtual formation. Figure 12 shows that the USVs did not collide with each other during FF, thereby validating the capability of the USV-IFDS method for dynamic FF.

Figure 11.

Velocity magnitude curves of flocking USVs yielded by the USF-IFDS method.

Figure 12.

Distances between pairs of flocking USVs yielded by the USF-IFDS method.

Formation local path planning (formation OA)

The local path planning capabilities of the USV-IFDS method were also validated by simulating a formation of three USVs with the following parameters: Starting points of USV #1, #2 and #3 were (10, 10) m, (0, 20) m and (20, 0) m, respectively; the maximum velocity was 23 m/s (approximately 45 knots); the course angle θ was 45°; the repulsion coefficient ρ_k was set to 3; the escape coefficient σ_k was set to 1; the constant C_k was set to 10; the obstacle centre was at (80, 50) m; the obstacle radius was 25 m; the initial positions of the virtual structure points for USV #1, #2 and #3 were (100, 100) m, (90, 110) m and (110, 90) m, respectively; the uniform velocity of virtual structure formation was 7.5 m/s (approximately 15 knots); the course angle θ was 45°; the distance thresholds d_vir1 and d_vir2 were 10 and 11 m, respectively; the velocity magnitude adjustment constants at distance thresholds λ_vir1 and λ_vir2 were 0.5 and 8, respectively; ρ_kf = 1; and the warning distance d_w was 13 m. Figures 13 to 15 showcase the OA performance as well as the distance between pairs of USVs.

Figure 13.

Distances between pairs of USVs during formation OA yielded by the traditional IFDS method.

Figure 14.

Distances between pairs of USVs during formation OA yielded by the USF-IFDS method.

Figure 15.

Formation OA performance of the USV-IFDS method.

Figure 13 shows that the distances between pairs of USVs calculated using the traditional IFDS method at the 4-s mark were approximately 10 m. This does not satisfy the requirements for safe navigation, because the vessels were too close to each other.

However, as shown in Figures 14 and 15, the USV-IFDS method significantly improved upon this result, effectively controlling the distances between pairs of USVs to be greater than the minimum safe distance of 13 m. This result complies with the requirements for both OA and safe navigation. Furthermore, following this phase, the individual USVs were able to successfully converge to form a coordinated formation.

Conclusion

In this study, a new path planning scheme based on disturbed flow fields is proposed for underdriven USV formation. This scheme includes solving the existing problems of IFDS in USV application and combining formation assembly and formation obstacle avoidance strategies based on the virtual structure method. The USV-IFDS scheme is an improvement of the traditional IFDS, wherein IFDS is joined the underactuated USV kinematics constraints, and through the modification of the matrix and join the constraints of the cost function, this scheme solves better the problem of local minimum. In addition, USV-IFDS uses vector and scalar decoupling in formation, which makes IFDS more suitable for formation based on the virtual structure method. It renders the formation more stable and flexible, and better overcomes the shortcomings of virtual structure formation compared with other obstacle avoidance methods. Simulation results show that the proposed formation strategy (USV-IFDS) successfully combines the advantages of IFDS and the virtual structure method, and considerably improves the formation assembly and obstacle avoidance performance of underactuated USV formation.

The simulations in this study assumed an ideal environment without considering the effects of wind and waves. Hence, in the future, we will combine the motion model of underactuated USVs in a real environment to constrain them, implement the formation architecture in a more complex real system, and further study the formation strategy.

Footnotes

Acknowledgements

The authors would like to thank the editors and the anonymous reviewers for their valuable comments on the content and presentation of this article.

Author contributions

Conceptualization, YL; methodology, YL; software, YL; validation, YL; formal analysis, YL; resources, YL; writing – original draft preparation, YL; writing – review and editing, JZ; supervision, JZ; project administration, JZ; funding acquisition, JZ and YZ. All authors have read and agreed to the published version of the manuscript.

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was funded by the Natural Science Foundation of Hubei Province [grant number 2018CFC865].

ORCID iDs

Yiping Liu

Bowen Sui

References

Xiaoming

. Introduction to maritime unmanned systems. Harbin: Harbin Engineering University Press, 2020.

Yong

Jiajun

Jia

. Research in unmanned surface vehicles: progress and direction. Ship Eng 2020; 42(2): 10010–10017.

. Research status and key technologies of small USV. Shipbuild China 2020; 61: 241–249.

Zhouhua

Wentao

Dan

, et al. Coordinated control of multiple unmanned surface vehicles: Recent advances and future trends. Chin J Ship Res 2021; 16(1): 51–64.

Cao

Chen

Zeng

. Consensus control of unmanned surface vehicle group based on advanced reinforcement learning. J Huazhong Univ Sci Technol 2019; 47(9): 42–47.

Shaorong

Jianjian

Dan

. Current development of control technology for unmanned surface vehicle clusters under complex sea conditions. J Unmanned Undesea Syst 2020; 28(6): 584–596.

Abro

GEM

Jabeen

Manan

. Stabilization of non-holonomic 03 DOF hovercraft using robust RST control design. Sukkur IBA J Emerg Technol 2019; 2(1): 45–50.

Yuan

Zhang

. A novel real-time collision risk awareness method based on velocity obstacle considering uncertainties in ship dynamics. Ocean Eng 2021; 220: 108436.

Huang

Gelder

. Non-linear velocity obstacles with applications to the maritime domain. In: Guedes Soares

Teixeira

(eds). Maritime transportation and harvesting of sea resources. Lisbon, Portugal: Taylor & Francis Group. 2017, pp. 999–1007.

10.

Chen

Huang

Papadimitriou

. An improved time discretized non-linear velocity obstacle method for multi-ship encounter detection. Ocean Eng 2020; 196: 106718.

11.

Huang

Gelder

Wen

. Velocity obstacle algorithms for collision prevention at sea. Ocean Eng 2018; 151: 308–321.

12.

Dai

Cao

Xia

, et al. Distributed MPC for formation of multiagent systems with collision avoidance and obstacle avoidance. J Franklin Inst 2017; 354(4): 2068–2085.

13.

Xiao

Chen

CLP

. Formation control of leader–follower mobile robots’ systems using model predictive control based on neural dynamic optimization. IEEE Trans Ind Electron 2016; 63(9): 5752–5762.

14.

Liu

Chen

Feng

, et al. An improved RRT* UAV formation path planning algorithm based on goal bias and node rejection strategy. Unmanned Syst 2023; 11(4): 317–326.

15.

Pedram

Stefarr

Funada

, et al. Rationally inattentive path-planning via RRT*. In: Proceedings of the American control conference (ACC), Denver, USA, 2021, pp. 3440–3446.

16.

Liu

Goh

, et al. Formation tracking control of multiagents in constrained space. IEEE Trans Control Syst Technol 2016; 24(3): 992–1003.

17.

Paul

Krogstad

Gravdahl

. Modelling of UAV formation flight using 3D potential field. Simul Model Pract Theory 2008; 16(9): 1453–1462.

18.

Chang

Xia

Huang

. Coordinated formation control design with obstacle avoidance in three-dimensional space. J Franklin Inst 2015; 352(12): 2068–2085.

19.

Xia

Zhu

Liu

, et al. Research on collision avoidance algorithm of unmanned surface vehicle based on deep reinforcement learning. IEEE Sens J 2022; 23(11): 11262–11273.

20.

Xiao

Hongwei

Dawei

, et al. Three-dimensional path planning for unmanned aerial vehicles based on principles of stream avoiding obstacles. Acta Aeronaut Astronaut Sin 2013; 34(7): 1670–1681.

21.

Wang

Lyu

Yao

, et al. Three-dimensional path planning for unmanned aerial vehicle based on interfered fluid dynamical system. Chin J Aeronaut 2015; 28(1): 229–239.

22.

Wang

Lei

Yao

, et al. Planning three-dimensional collision-avoidance path for UAV on the basis of disturbed fluid dynamical system algorithm. Control Theory App 2016; 33(3): 295–303.

23.

Wang

, et al. Formation obstacle avoidance: a fluid-based solution. IEEE Syst J 2019; 14(1): 1479–1490.

24.

Yanxiang

Honglun

Jianfa

, et al. Adaptive path planning for UAV based on interfered fluid algorithm and deep neural network. J Unmanned Syst Technol 2020; 3(6): 50–58.

25.

Jianfa

Honglun

Yanxiang

, et al. UAV reactive interfered fluid path planning. Acta Autom Sin 2023; 49(2): 272–287.

26.

Khaitib

. Real-time obstacle avoidance for manipulators and mobile robots. Int J Robot Res 1986; 5(1): 90–98.

27.

Abro

GEM

Zulkifli

Asirvadam

, et al. Modeling, controlling & stabilization of an underactuated air-cushion vehicle (ACV). In: 2021 IEEE international conference on signal and image processing applications (ICSIPA), Kuala Terengganu, Malaysia, 2021, pp. 197–202.