Model-Driven Cooperative Path Planning for Dynamic Target Searching of Unmanned Unterwater Vehicle Formation

Abstract

With the increasing complexity of ocean missions, using multiple unmanned underwater vehicles to collaborate in executing tasks has become an effective way to improve the overall efficiency of ocean operations. Current research on path planning for multiple unmanned underwater vehicles mainly focuses on the basis of particle models or fully known environmental information, while research directions mainly focus on single indicators such as completion time and energy consumption. This paper first constructs a UUV model and a task scenario with detection success rate as the objective function. Then, a parameterization method based on a spiral search path was proposed for designing variables. A hierarchical control strategy is designed to ensure handle formation constraints. A general optimization framework for task scenarios has been constructed and combined with algorithms to solve optimization problems. Finally, this study compared and analyzed the performance of different optimization algorithms under the optimization framework, evaluated the optimization results of different search strategies, and explored the impact of dynamic objectives on the detection success rate. The results showed that the optimized path had a search success rate that increased by more than 50% compared to the direct path and the cover search path, which verified the effectiveness of the proposed method and strategy.

1. Introduction

The diversity of marine environmental resources has rendered marine exploration a pivotal field in academia [1]. Unmanned Underwater Vehicles (UUVs) have become indispensable for ocean exploration research due to their adaptability, durability, safety, and autonomy [2]. A single UUV is constrained by its detection range, endurance, reliability, and other factors, limiting its efficacy in complex missions due to finite detection, endurance limitations, and operational depth. Fault tolerance and robustness insufficiencies hinder high-complexity tasks, while adaptability to environmental or task changes is also limited. The capability of a single UUV is no longer sufficient to meet the growing demand for ocean exploration missions [3]. As a result, the utilization of multi-UUV systems, which significantly enhances task efficiency, extends coverage, and improves system flexibility and robustness, has emerged as a new trend in ocean exploration [4]. The collaborative technology of multiple UUVs has attracted widespread attention from countries around the world. Since 1998, the US Navy has been actively involved in the research and development of multiple cutting-edge projects, including Seaweb, DADS, CADRE, and PLUSNet [5,6,7]. These projects have significantly improved the efficiency of underwater combat and surveillance through the collaborative mode of heterogeneous clusters and successfully verified the core technology of underwater cluster networking. In addition, Aquabotix has launched the SwarmDiver cluster system, which consists of over 40 nodes and has been widely used in various practical fields such as ocean monitoring, plume tracking, and target detection, demonstrating its strong application potential and value [8]. At the same time, the Grex project of the European Union also conducted in-depth research on key technologies such as underwater heterogeneous cluster networking and heterogeneous platform task planning. In 2009, it successfully demonstrated the trajectory tracking and capture capabilities of the cluster, providing important technical support and demonstration for the collaborative operation of underwater unmanned systems [9]. The practical application of multi-UUV formation has further enhanced the importance of research on multi-UUV technology.

The widespread application of multi-UUV collaboration scenarios makes the research on multi-UUV collaboration technology crucial. As a crucial technology that enhances the efficiency of collaborative task execution among multiple unmanned underwater vehicles, multi-UUV path planning has garnered significant attention from various scholars. Lu et al. proposed a solution for global static path planning utilizing an improved Deep Double Q-Network (DDQN) algorithm to tackle the local dynamic collision avoidance problem [10]. The experimental results demonstrate that the proposed method successfully resolves the issues of both collision avoidance and path finding for multiple UUVs in complex environments, and it is capable of effectively navigating around obstacles to prevent collisions. Li et al. proposed a obstacle-avoidance path planning algorithm that combines the artificial potential field (APF) method and A ⁎ algorithm, which can realize multi-UUV coordinated path planning with collision avoidance (CPP/CA) [11]. Kiran Murthy utilized prior terrain information and parameterized the B-spline curve to obtain an optimized UUV trajectory [12]. Sun proposed a GK-OPM method that uses directed graphs and K-means methods to generate optimized searching paths for UUV mission efficiency [13]. McKeever and Scott Douglas designed parameterized paths for different task scenarios and created different path planners to adapt to different conditions, enabling UUVs to effectively track moving targets [14].These studies are based on A* and B-spline paths and are designed to parameterize and optimize the UUV search path for different task scenarios.

In addition, there are different evaluation methods for the quality of UUV task execution. Cheng et al. comprehensively evaluated the solution in terms of energy consumption, travel completion time, and communication time to solve the problem of multi-UUV task area allocation and path planning methods, thereby maximizing the efficiency of joint surface and underwater search [15]. Li proposed an adaptive search method for heterogeneous UUV clusters, which utilizes online state information and is aimed at reducing search time and enhancing search efficiency in unknown environments [16]. Fransman introduced a framework method for distributed constraint optimization problems, which segments the mine-threatened areas and explicitly reasones about their behaviors based on high-performance indicators, enabling the accomplishment of the mine target search mission within the prescribed time [17]. The evaluation methods for UUV efficiency mainly focus on energy consumption, completion time, and communication time. This article proposes an indicator for evaluating the success rate of UUV formation tasks, which is the success rate of UUV detection targets.

When executing tasks within a UUV formation, it is imperative to track trajectory points. Thus, there is an urgent need to propose a UUV formation method that is specifically designed for tracking path points [17,18,19]. Chen et al. proposed a control strategy that utilizes virtual structures, leader–follower formation features, and redistribution mechanisms, which enables multiple UUV formations to reduce the possibility of collisions and interference with teammates and obstacles in various complex combat environments, enhancing the collaborative ability of multi-UAV formation control and cluster search operations [20]. Liu proposed a dual layer method for generating collaborative detection tasks for multiple unmanned underwater vehicles, effectively improving the collaborative detection capability of multiple UUVs for wide areas and moving targets [21]. At the same time, based on multi-UUV paths, the article proposes a UUV formation layered control model to solve the problems that may be encountered in UUV formation.

The current research is predominantly centered around the pivotal technologies within UUV swarm search and on individual metrics such as energy consumption, completion time, and coverage area. In addition, most task planning studies are limited to point planning and fail to conduct in-depth research based on the actual task scenarios and mathematical models of UUVs. In this paper, we aim to optimize the search path of the UUV formation by considering the actual physical model of the UUV for enhancing the search success rate. To achieve this goal, firstly, we establish the UUV kinematic model, the UUV functional model, the UUV formation hierarchical control model, and the task scenario model. Secondly, we parameterize the modeling of search paths. Finally, we extract the optimization problem and design an optimization method to optimize and solve it. In summary, this work makes the following contributions:

• Proposing a model-driven cooperative path planning method with detection success rate as the objective for dynamic target search in the absence of prior information.
• Designing a UUV formation layered control model based on time consistency to to handle the formation constraints of UUV formations in collaborative search paths.
• Developing a UUV formation path parameterization method based on a dynamic target threat range to design optimized UUV formation paths and optimization variables. An optimization method is proposed that uses the Kriging-assisted discrete global optimization method (KDGO) algorithm framework to optimize the search path.

The remaining sections of this paper are as follows. Section 2 presents the current state of research on UUV formations and their limitations, highlightling the improvements proposed in this study. Section 3 introduces the UUV model and the UUV formation task scenario. Section 4 introduces the optimization framework and the data-driven optimization algorithm. In Section 5, we analyze and discuss the optimization results.

2. Previous Works

2.1. Related Works

Generally, the strategy applied to task allocation in multi-UUV systems is mainly based on known task information. These strategies aim to optimize the task allocation process, ensuring that each UUV can efficiently complete its assigned tasks while considering the overall task completion efficiency, resource utilization, and collaborative cooperation among UUVs, thereby improving the overall performance and efficiency of multi-UUV systems. Matarik proposed a task allocation algorithm that mimics animal grouping behavior, clustering and distributes tasks to multiple UUV systems in a distributed manner to improve task allocation efficiency [22]. Parker built a distributed system that uses UUV behavior analysis to refine complex tasks into multiple small computing units for more efficient task processing. These studies plan task allocation for UUV formations based on the assumption that prior information about the target is fully known. However, in real-world scenarios, it is often impossible to have complete knowledge of the target information.

Path planning mainly includes artificial potential fields and various intelligent path planning algorithms. The artificial potential field method plans a path by constructing a virtual artificial potential field, where the destination is set as the center point that is attractive to the UUV, and obstacles are set as areas or objects that generate repulsive forces to the UUV [23]. Swarm intelligence algorithms have demonstrated excellent performance in path planning for unmanned underwater vehicles. However, the potential local minimum problem they may face can sometimes cause the vehicle to stall prematurely before reaching its destination. In contrast, fuzzy logic intelligent algorithms do not require complex mathematical models, rely on human experience for flexible navigation, and overcome local minimum problems [24]. Fuzzy logic performs particularly well in path planning and obstacle avoidance tasks for unmanned underwater vehicles, mainly due to its ability to handle information uncertainty, which is often accompanied by high levels of uncertainty and incompleteness in underwater environments [25]. Kim used a fuzzy logic-based algorithm to accurately infer the turning direction and angle of unmanned underwater vehicles, aiming to effectively avoid potential collisions and efficiently complete complex path planning tasks. This algorithm can fully utilize the advantages of fuzzy logic in handling uncertain information, dynamically adjust the motion trajectory of UUVs based on current environmental conditions and preset obstacle avoidance strategies, and ensure their safe and stable progress in complex and changing underwater environments [26]. Ali developed a method based on fuzzy ontology modeling for path planning of unmanned underwater vehicles [27]. Yang proposed a biomimetic neural network for vehicle path planning, including optimal planning paths and efficient collision avoidance [28]. The application of reinforcement learning in path planning for UUVs is developing rapidly. This method optimizes the behavior of AUVs by continuously updating their status and setting reward mechanisms based on the environment. A low-cost and efficient AUV solution has been developed by combining reinforcement learning (RL)-based path planning with artificial potential field (APF) methods [29]. Wang and his colleagues proposed a multi-behavior critical reinforcement learning (RL) algorithm for AUV path planning, aimed at solving the problem of low learning efficiency caused by oscillation amplitude in the early stages of training. This algorithm effectively shortens the time required for the RL algorithm to reach a convergence state and significantly improves the performance of AUVs in avoiding obstacles [30]. Most studies on multi-UUV path planning focus primarily on point mass models, where only the path points are planned without adequately considering whether the actual UUVs can effectively track path points.

In addition, when exploring path planning for multiple UUVs, the current focus is mainly on two core optimization objectives. 1. Task execution time and efficiency. Wenjie Li proposed a USV/UUV heterogeneous collaborative search method based on real-time state information. This method rasterizes the task environment, adaptively plans the search path based on the motion state of the USV/UUV, and updates the grid state information in real time. Simulation shows that this method can efficiently collaborate searches in unknown environments and shorten the task time [16]. In the face of maritime security challenges, Pan et al. developed the T-MOEA/D algorithm, which cleverly integrates task scenarios and optimization processes. By balancing time and energy consumption, the algorithm enhances the effectiveness of unmanned underwater vehicles in mine detection tasks. The research results provide a strategic blueprint for the planning of large-scale multi-UUV mine countermeasure missions, effectively improving operational efficiency and safety in complex underwater environments [31]. 2. Coverage area. Yongzhou Lu innovatively proposed a task allocation method based on the principle of biological balance to address the difficulty of underwater shipwreck coverage detection and combined it with the Voronoi diagram principle to delineate the core detection area. At the same time, a path planning strategy for underwater target unmanned submersible area coverage detection was designed for near seabed environments. This strategy balances the workload of UUV tasks through the principle of biological balance and integrates the reliability q function of intelligent units based on the actual underwater detection environment to optimize the search path of multiple UUV formations, thereby significantly improving the search area and efficiency [32]. Yan Bo proposed an optimized “Z-shaped” search path planning method that ensures comprehensive coverage of the area while possessing high task adaptability. It can automatically adjust the search strategy according to task requirements and select the optimal formation mode in real time based on the shape of the area, effectively shortening the overall search path length of the unmanned underwater vehicle formation. This innovation not only increases the search area of UUV formations but also significantly enhances search efficiency [33]. The optimization objectives of the current research are primarily achieved by evaluating the UUV’s detection area, completion time, and execution efficiency, not comprehensively considering the mission success rate of the UUV formation.

2.2. Research Gap and Improvements

Research gap: 1. Based on the above analysis, most studies on cooperative search of multiple UUV formations are based on the assumption of known mission scenarios and prior information about the targets. However, these studies often overlook the fact that in actual missions, prior information about the targets is usually incomplete. 2. Most studies on path planning for multiple UUV formations are based solely on mass point models, without fully considering the kinematic and dynamic constraints of the UUVs themselves. 3. Most research on path planning aims to achieve optimization goals by evaluating the detection area, task completion time, and task execution efficiency of UUV formations without comprehensively assessing the success rate of UUV formation task completion.

This paper proposes an innovative multi-UUV collaborative path planning method that closely relies on a mathematical model of the UUVs, especially their kinematic and dynamic characteristics, and deeply studies the strategy of multi-UUV collaborative search path planning. The following are several aspects of this method used to solve corresponding problems:

• In the task scenarios of this study, to better align with the practical application requirements of UUV formations, this study only possess prior information about the dynamic target’s position, while its movement trajectory remains unclear.
• The path planning in this study is not limited to a point-mass model but is based on the kinematic and dynamic constraints of real UUVs. Additionally, a hierarchical control strategy for multi-UUV formations is proposed to meet the formation constraints.
• The evaluation of the objective function is no longer limited to single task metrics such as detection area, completion time, or detection efficiency. Instead, it takes multiple factors into account, using detection success rate as the comprehensive evaluation criterion.

3. UUV Model and UUV Formation Task Scenario

3.1. UUV Model

Unlike most studies that primarily rely on path planning and only consider particle models, this study fully considers the kinematic and dynamic models of unmanned underwater vehicles. As shown in Figure 1, the head of the UUV is the detection module of the UUV. The orange fan-shaped area represents the UUV detection model, which is arranged at the bow of the UUV, with a detection range of a fan-shaped area, a detection angle of ${\theta }_d$, and a detection distance of $R_d$. When the target position appears within the fan-shaped range, it is considered that the UUV has successfully detected the target. The detection angle and detection range are set to 120° and 2000 m, respectively, based on the actual operational requirements. The upper part of the UUV is the communication unit with the antenna of the UUV. The communication angle is ${\theta }_c$, and the communication range is $R_c$. When UUV formation members have appeared in each other’s communication areas, the communication link is successfully established, forming UUV clusters. The communication angle and detection range are set to 100° and 2000 m, respectively, based on the actual operational requirements. The internal part is the energy package of the UUV unit in which the energy carried by the UUV is sufficient to navigate for 300 km at a speed of 25 knots.

The kinematic equation governing the motion of the i-th UUV is expressed as follows:

$$\left\{\begin{array}{c}{M}_i=-C\left(v_i\right)v_i-D\left(v_i\right)v_i+{\tau }_i\hfill \\ \dot{\eta }=J\left({\eta }_i\right)v_i\hfill \end{array}\right.$$

(1)

where $v_i=[u_i,v_i,r_i]$ refers to the longitudinal velocity, lateral velocity, and yaw angular velocity of the UUV in the motion coordinate system. ${\eta }_i={[x_i,z_i,{\psi }_i]}^T$ refers to the northward position, eastward position, and yaw angle of the UUV in the inertial coordinate system. ${\tau }_i=[{\tau }_{iu},0,{\tau }_{ir}]$ denotes the thrust of the UUV propulsion system and the yawing moment generated by the rudder. $M=\left[\begin{array}{ccc}{m}_{11}& 0& 0\\ 0& m_{22}& 0\\ 0& 0& m_{33}\end{array}\right]$ represents the simplified inertia matrix of the UUV. $C=\left[\begin{array}{ccc}0& 0& m_{22}v\\ 0& 0& m_{11}u\\ m_{22}v& -m_{11}u& 0\end{array}\right]$ represents the centripetal force matrix of the UUV. $J\left({\eta }_i\right)=\left[\begin{array}{ccc}\cos {\psi }_i& -sin{\psi }_i& 0\\ sin{\psi }_i& \cos {\psi }_i& 0\\ 0& 0& 1\end{array}\right]$ denotes the transformation matrix between the UUV’s inertial coordinate system and its motion coordinate system, where m represents the mass of the UUV (in kilograms). $X_{\dot{u}}$, $Y_{\dot{v}}$, $N_{\dot{r}}$ represents the acceleration coefficient; $I_z$ denotes the moment of inertia around the Z-axis in the motion coordinate system; $m_{11}=m-X_{\dot{u}}$, $m_{22}=m-Z_{\dot{v}}$, $m_{33}=I_z-N_{\dot{r}}$, $D_{11}=-X_u-X_{u\left|u\right|}\left|u\right|$, $D_{22}=-Z_u-Z_{v\left|v\right|}\left|v\right|$, $D_{33}=-N_r-N_{r\left|r\right|}\left|r\right|$ represents the damping coefficient of the UUV. The kinematic equation governing the motion of the i-th UUV is expressed as follows.

$$\left\{\begin{array}{c}{x}_i=u_{i}cos{\psi }_i-v_{i}sin{\psi }_i\hfill \\ z_i=u_{i}sin{\psi }_i+v_{i}cos{\psi }_i\hfill \\ {\psi }_i=r_i\hfill \end{array}\right.$$

(2)

3.2. UUV Formation Task Scenario

During the UUV formation execution of tasks, it is typically impossible to fully acquire all information about the target. Unlike path planning based on fully known prior information, the motion characteristics of the dynamic targets studied in this paper are not entirely known. In the task scenario of this study, the motion characteristics of the target can only be estimated based on its potential speed, assuming it follows a normal distribution with a mean of 5 knots. This serves as the basis for task allocation and path planning for the unmanned underwater vehicle (UUV) formation. The motion characteristics of the target in different simulation scenarios are presented in the figure below. As is shown in Figure 2, the target’s speed and direction vary in each simulation.

Based on the prior information of the target, the task scenario assumes the target is located 50 km from our position. In order to achieve collaborative search for the target, we deployed a horizontal formation consisting of three UUVs which search for the target at a speed of 20 knots based on different search path strategies. By adjusting different search paths ${\xi }_1$, ${\xi }_2$, ${\xi }_3$, the objective is to find an optimal path that satisfies the UUVs’ dynamic constraints while maximizing the detection probability Y. As shown in Figure 3, the red lines represent the different search paths of the UUV formation, the black pentagram indicates the prior information about the target’s location, and the blue trajectory lines represent the possible escape directions of the target.   

$$\begin{array}{cc}\mathrm{Max}\hfill & Y(\xi )\hfill \\ \mathrm{W}.\mathrm{r}.\mathrm{t}\hfill & \xi \hfill \\ \mathrm{S}.\mathrm{t}.\hfill & UUVkinetics,UUVformation,Searchpath\hfill \end{array}$$

(3)

where Y represents the detection success rate, and $\xi$ represents different paths. The constraints include UUV dynamic constraints, UUV formation constraints, and search path constraints.

4. Optimization Framework and Optimization Algorithm

4.1. Design Variables

After conducting research [34,35], the spiral search method performs better than traditional direct flight and coverage search methods. Therefore, we propose a path parameterization method based on the spiral search. The purpose of this spiral path planning method is to design a search strategy for the UUV formation that constructs multi-level threat loops around target points and parameterizes and optimizes these loops to generate a search path that conforms to the maneuverability of the UUV formations. The specific steps are as follows:

• Threat loop construction and discretization. Based on the prior position information of the target, establish multiple threat loops with different radii (such as R1 to R5), and discretize each threat loop by uniformly selecting multiple sampling points on each loop, which together form the path point database on that loop.
• Sampling point selection and path generation. Select sampling points from the dataset of each threat loop and combine them according to certain rules (such as minimum angle, maximum distance, etc.) to preliminarily form a segmented path.
• Path verification and filtering. Verify each generated candidate path to determine if it meets the maneuvering constraints of the UUV formation (such as the maximum turning angle of the formation configuration). Filter out paths that do not meet the conditions and retain paths that meet the requirements as the final candidate.
• Path fitting and smoothing processing. Fit the selected paths to make their curvature changes smoother and adapt to the actual maneuverability of UUV formations. Ultimately generate one or more optimal search paths for UUV formations to use during mission execution.

As shown in Figure 4, we use the parameterization method to design variables for sampling points on five threat loops. Threat rings with different radii are selected, centered on the target’s prior location, and each threat ring is uniformly discretized, with a discrete point chosen from each ring. In this study, five threat rings with different radii were selected, and each ring was discretized into 50 sample points, with each sample point numbered from 1 to 50. Therefore, this study includes a total of 10 variables: the radius $x_1$, $x_2$, $x_3$, $x_4$, $x_5$ of each of the five threat rings and the location information $x_6$, $x_7$, $x_8$, $x_9$, $x_{10}$ of the sample points on the rings. As shown in

Table 1. Design variables.

	${\mathit{x}}_1$	${\mathit{x}}_2$	${\mathit{x}}_3$	${\mathit{x}}_4$	${\mathit{x}}_5$	${\mathit{x}}_6$	${\mathit{x}}_7$	${\mathit{x}}_8$	${\mathit{x}}_9$	${\mathit{x}}_{10}$
Range	0–5 × 103	5 × 103–10 × 103	10 × 103–15 × 103	15 × 103–20 × 103	20 × 103–25 × 103	1–50	1–50	1–50	1–50	1–50

, the range of radii for the rings is 0–5 km, 5–10 km, 10–15 km, 15–20 km, and 20–25 km, with the variable values for points on the threat rings ranging from 1 to 50. Consequently, by varying the size of the threat loops and the sequence of the sampling points within them, the search path for the UUV formation is established. In short, 10 design variables, $x_1$, $x_2$, $x_3$, $x_4$, $x_5$, $x_6$, $x_7$, $x_8$, $x_9$, $x_{10}$, are defined.

4.2. Constraints

4.2.1. UUV Constraints and Path Constraints

Though we aim to increase rate of success via the searching path, the path should first satisfy the UUV dynamic constraints and the requirements for the UUV formation. Therefore, we have two types of constraints. As shown below, constraints $g\left(x\right)$ mainly include $E_i\left(x\right),C_i\left(x\right),P\left(x\right)$. The first type of constraint is the energy consumption constraint of the UUVs and the UUV formation communication constraint, which is essential for maintaining the UUV formation.

$$\begin{array}{cc}{E}_i\left(x\right)-E\ge 0,\hfill & i=1,2,3\hfill \\ {C_v}_i\left(x\right)-C_v\le 0,\hfill & i=1,2,3\hfill \\ {C_d}_i\left(x\right)-C_d\le 0,\hfill & i=1,2,3\hfill \\ {C_a}_i\left(x\right)-C_a\le 0,\hfill & i=1,2,3\hfill \end{array}$$

(4)

where $E_i\left(x\right)$ represents the energy consumption of the i-th UUV, E represents the reserve energy of the UUV, ${C_v}_i$ represents the current speed of the i-th UUV, $C_v$ represents the communication speed allowed by the UUV, ${C_d}_i$ represents the current distance between the i-th UUV and the other two members, $C_d$ represents the communication distance of the i-th UUV, ${C_a}_i$ represents the current angle of the i-th UUV compared to the other two members, and $C_a$ represents the current communication angle between the i-th UUV and the other two members.

The second constraint is the constraint of path selection. Specially, we limit the angle of each segmented search path to no more than 60 degrees for meeting the UUV dynamic model requirements and improving the efficiency of UUV formations in performing search tasks.

$$P_{a(i,i+1)}\left(x\right)\le P_{a\mathrm{threshold}}$$

(5)

Here, $P_{a(i,i+1)}$ represents the angle between the i-th path and the i+1th path, and $P_{a\mathrm{threshold}}$ represents the allowed path angle, which is 60 degrees.

4.2.2. UUV Formation Layered Control Model

Due to the extreme complexity of underwater environments, the UUVs are unable to freely adopt task allocation control strategies with higher degrees of freedom in actual task execution, like drones, unmanned boats, and unmanned vehicles. As shown in Figure 5, in the practical application of UUV formation, especially during large maneuvering turns, a series of challenges will be encountered, including the risk of communication loss, rigid formation structure, and limited turning radius of the UUV configuration.

In order to meet the constraints of the UUV formation and maintain a certain formation for searching according to the optimized path, this section proposes a control strategy that integrates the UUV dynamics model with the requirements for maintaining the formation. As shown in Figure 6, the red trajectory lines signify the driving path of the leader. By discretizing these lines, we acquire the path points of the leader. Following this, in accordance with the time consistency principle of the UUV formation, the trajectory points for the followers are computed to generate black follower trajectory lines. This methodology ensures that the UUV formation reaches their respective trajectory points simultaneously. The control strategy aims to precisely regulate the speed and orientation of the formation members, ensuring that the UUV formation can efficiently perform search tasks in a compact and coordinated cluster form to meet the communication constraints.

As shown in Algorithm 1, the control strategy adopts a hierarchical control architecture, which is designed to optimize the collaborative control process of UUV formations. The control algorithm is divided into two layers, each layer undertaking a specific control task. The upper-level control is responsible for receiving given path points and calculating the expected velocity and attitude angle of each sub-UUV based on the predetermined formation configuration. The lower-level control receives the velocity and attitude angle calculated by the upper and uses a PID controller to precisely adjust these two control objectives, outputting necessary control inputs including rudder angle and thrust to drive each sub-UUV to approach the target. This calculation process ensures that the formation can move forward according to the established path while taking into account the relative position and dynamic balance within the formation.

$${\psi }_i=\mathrm{atan}{\displaystyle \frac{(z_i-z_r)}{(x_i-x_r)}}$$

(6)

$${\delta }_i=k_{\psi }({\psi }_r-{\psi }_i)+k_y{w}_y$$

(7)

Here, ${\psi }_i$ represents the current heading angle of the i-th UUV, $[x_i,z_i]$ indicates the position information of the UUV, $[x_r,z_r]$ indicates the position information of the guidance point, $k_{\psi }$ and $k_y$ are parameters for the heading angle and heading angular velocity, and ${\delta }_i$ represents the UUV’s rudder angle.

Algorithm 1 UUV formation layered speed allocation control strategy

/*Initialization*/   (01) Initialization the position of path point $path$, the configuration of UUV formation $formationConfig$, the flag for task completion $fla{g}_c$, If the task is completed, it is 1, otherwise it is 0, the desired velocity of the i-th UUV $v_{di}$, the desired rudder angle of the i-th UUV ${\delta }_{di}$, the thrust and rudder angle of the i-th UUV $T_i$, ${\delta }_i$, the state of the i-th UUV $S_i$; /*Main Loop*/   (02) function mainControlLoop($path$, $formationConfig$):   (03) while $fla{g}_c$:   (04)  $v_{di}$, ${\delta }_{di}$ = upperLevelControl($path$, $formationConfig$)   (05)  $T_i$, ${\delta }_i$ = lowerLevelControl($v_{di}$, ${\delta }_i$)   (06)  Update formation status /* Upper-level Control*/   (07) function upperLevelControl($path$, $formationConfig$):   (08) for ith UUV in formation:   (09)   $v_{di}$, ${\delta }_{di}$ = calculateDesiredSpeedAndPose($path$, $formationConfig$)   (10) return /* Lower-level Control*/   (11) function lowerLevelControl($v_{di}$, ${\delta }_{di}$):   (12) for i-th UUV in formation:   (13)   $T_i$, ${\delta }_i$ = PIDController($v_{di}$, ${\delta }_{di}$)   (14) return

The thrust control of the UUV is controlled according to the speed calculated by the speed distribution strategy, as shown in Formula (4).

$$T_i=0.5C_x\rho {v_{ri}}^{2}S$$

(8)

where $T_i$ represents the thrust of the i-th UUV, $C_x$ represents the drag characteristic coefficient, $\rho$ represent the density of seawater, $v_{ri}$ represents the expected speed of the i-th UUV, and S represents the characteristic area of the UUV.

As shown in Figure 7, based on the mathematical model of the UUV, the layered control strategy is successfully applied to various paths. The blue trajectory and its points represent the navigation path and position of the main UUV, while the red and black trajectories and points correspond to the navigation paths and positions of different sub-UUVs, respectively. Based on the simulation trajectory points of the UUV, the control strategy can ensure that the UUV formation navigates in a closely coordinated cluster form according to the predetermined path, effectively verifying its feasibility in practical applications.

4.3. Objective Function

For the effectiveness of UUV formations, the commonly concerned factors include searching time, coverage area, etc. However, the actual task application process involves evaluating the performance of the UUV formation in executing tasks; that is, evaluating the success rate of the UUV formation in executing tasks. Specifically, during the execution of the task, the motion trajectory of dynamic targets, including both speed and direction, is unknown, and the UUV formation can only roughly estimate the target’s direction. Due to the uncertainty of the target, this study uses the Monte Carlo method to evaluate the quality of the search paths. In each Monte Carlo experiment, the speed and direction of the dynamic target are random variables following a normal distribution. For each path, we conduct 100 Monte Carlo simulations to determine the search success rate for that path. The path with the highest success probability is considered the optimal one.

In short, the optimization purpose aims to increase the success rate for searching targets and finds an optimized path that satisfies the UUV dynamics and maintains the stability of the UUV formation when the prior information of the target is unknown. Therefore, Monte Carlo simulation is used to evaluate the success rate of the UUV formation in executing tasks. The objective function is given as follows:

$$min{\mathrm{Y}}_{\mathrm{s}}=-{\displaystyle \frac{D_{sn}}{D_n}}$$

(9)

where $D_n$ represents the number of UUV formation detections, and $D_{sn}$ represents the number of successful detections.

In summary, a mathematical formulation of an engineering optimization problem within the task scenario should be extracted, as shown in Figure 8. The optimization objective is obtained through Monte Carlo simulation evaluation, using design variables as path points. The constraints include communication constraints, energy consumption constraints, and path selection constraints.

4.4. Optimization Algorithm

Upon formulating the optimization problem, the selection of an appropriate optimization algorithm becomes crucial. The configuration of optimization problems inherently permits the delineation of variables tailored to specific research requirements, particularly within the realm of discrete parameterization. As such, this constitutes a discrete optimization problem, distinct from its continuous counterpart, as it involves discrete variables. Furthermore, the evaluation process associated with this problem is inherently resource-intensive and time-consuming, underscoring its categorization as an expensive and computationally demanding optimization challenge.

This study uses Kriging-assisted Discrete Global Optimization (KDGO) [36] to solve the optimization problem extracted in this paper. KDGO primarily comprises two parts: one is the initialization, and the other is the proposed multi-start knowledge mining. In this paper, the Latin Hypercube Sampling (LHS) strategy is used to obtain the Design of Experiments (DoE) samples. Subsequently, these initial samples are projected onto the matrix to acquire discrete samples. The knowledge mining process is reiterated, and the Kriging model is updated accordingly. Finally, the optimization will terminate if the number of function evaluations (NFE) reaches the maximum allowable NFE (maxNFE). The comprehensive optimization procedure is outlined in Figure 9. Firstly, the process performs initialization design to construct the Kriging model. Subsequently, the KDGO method is used to optimize and solve the constructed proxy model, forming new path sample points. Next, based on these optimized sample points, the process forms a search path. Finally, simulation calculations are conducted based on this path to evaluate the success rate of the UUV formation simulation, and this process is continued until the iteration requirements are met.

5. Optimization Results Analysis

5.1. Initialization

After defining the optimization problem and algorithm, the LHS method is used to initialize the solution of the optimization framework. As shown in

Table 2. Sampling.

Number	R1	R2	R3	R4	R5	P1	P2	P3	P4	P5	obj
1	5867	19,338	22,294	30,439	44,256	9	2	5	3	4	0.21
2	6249	17,312	21,542	33,872	40,152	9	5	4	4	6	0.22
3	7850	18,182	22,998	30,655	40,625	8	4	7	3	5	0.22
4	6129	16,658	24,325	33,379	43,785	4	1	2	8	8	0.23
5	7990	16,752	23,511	33,181	44,505	2	6	7	6	7	0.32
6	8584	17,475	24,413	34,785	41,476	5	5	5	2	4	0.33
7	8618	19,736	20,866	30,162	43,051	9	8	3	3	5	0.33
8	8817	16,106	23,245	35,027	40,220	10	5	5	3	5	0.34

, the size of the solved values is mainly concentrated between 0.2 and 0.35. As depicted in Figure 10, the path of the UUV formation initially intersects the target and then reverses to search. The disadvantage of this search path is evident based on the figure, as the UUV formation repeatedly scans the target area. When the UUV formation searches along this path, it wastes considerable time, allowing the dynamic targets to escape the area that our formation could search. Consequently, the search probability for the targets was concentrated within the range of 0.20 to 0.25. As shown in Figure 11, the shape of the path planned by the UUV formation appears to have undergone modifications based on a straight line. The UUV formation continuously searches back and forth along the direction of the straight line, indicating that searching along this type of path can increase the search probability to between 0.3 and 0.35. It is necessary to further apply optimization algorithms to iteratively solve it in order to improve the accuracy of the solution.

5.2. Optimization Results

The following is a comparative analysis of three algorithms utilized in collaborative search path optimization, accompanied by their respective path planning diagrams, convergence plots, and operational outcomes. The path planning diagrams visually depict the trajectory planning undertaken by these three algorithms across various scenarios. By juxtaposing the search paths formulated by the different algorithms to evaluate the efficiency of the execution task path of UUV formation.

Table 3. Optimization of the optimal result samples for each algorithm.

Algorithm	R1	R2	R3	R4	R5	P1	P2	P3	P4	P5	obj
KDGO	9001	17,614	20,179	34,632	40,931	9	2	5	3	4	0.65
PSO	5967	17,312	21,542	33,872	40,100	9	5	4	4	6	0.61
DE	6127	16,616	23,373	33,379	43,785	10	5	5	3	5	0.62

shows the optimal solutions obtained by three algorithms for optimization problems, and the optimization results of these three algorithms all demonstrate consistency. The convergence plots are shown in Figure 12. The first plot depicts the iteration process, while the second, third, and fourth plots represent the optimal search paths obtained using KDGO, DE, and PSO, respectively. The three algorithms display a general congruence in terms of convergence outcomes. The three optimal path searches first cover the region of prior information about the target, then they select a direction for exploration. They quickly adjust their direction to search in another potential escape route of the target, aiming to detect the target’s possible escape positions and enhance the success rate of the search under conditions of incomplete prior information about dynamic targets. Meanwhile, compared to DE and PSO, KDGO demonstrates a superior convergence rate. The path optimization converges within 50 iterations, during which the objective function value of the iteration process undergoes a decrease from −0.20 to −0.65, representing a 65% improvement.

5.3. Comparative Analysis of Optimized Paths

In the UUV search strategy for targets, distributed searches and centralized searches are the two main methods [37]. However, in actual underwater work environments, due to the complex and ever-changing underwater environment, communication limitations, and energy considerations, UUV formations often cannot implement distributed searches. Therefore, collaborative searches in the form of clusters can better meet the requirements. In this situation, the selection of search strategies becomes particularly crucial, mainly covering three methods: direct search, lawn mower search [38], and spiral search.

To verify the advantages of the optimal optimized search over direct search and lawn mower search, 100 Monte Carlo simulations were conducted based on a normal distribution of target velocity magnitude and a random distribution of velocity direction. The direct navigation search is configured with three UUVs spaced 2000 m apart, conducting a dynamic target search based on the prior information about the target’s location. The coverage search process is as follows: three UUVs travel 40 km to the location of the target’s prior information, maintaining a distance of 2000 m between each other. They first navigate 35 km to the right, then search by moving downward for 10 km, after which they continue searching by traveling in the opposite direction to complete the coverage search.

As shown in Figure 13, the coverage search has the largest coverage area, the straight-line search has the smallest, and the spiral search falls in between. In the coverage search, when the search path passes through the region with prior information about the target and continues to the right, the target is likely to escape from the left side of the prior information area, resulting in a detection success rate of only 0.42. The straight-line search, with the smallest coverage area, makes it easy for dynamic targets to escape from both sides, leading to the lowest detection success rate of 0.34. In contrast, the optimized path strikes a good balance between spatial and temporal constraints. By rapidly covering all directions of the mission area, the optimized path achieves the highest detection success rate, reaching 0.65. Based on the above simulation analysis, we found that the optimized search can significantly improve the success rate of target detection to 0.65, which is much higher than the 0.34 success rate of the direct search and the 0.42 success rate of the coverage search. These results indicate that the optimized search path has significant advantages when performing search tasks in the form of clusters.

As shown in Figure 14, the simulation set the speed of the dynamic target to 3 knots, 5 knots, and 7 knots, respectively, and it used multiple UUV formations for collaborative search of the target, recording the highest search success rate achievable at different speed settings. Subsequently, we conducted in-depth analyses and comparisons of these results. We found that as the target speed increases, the probability of multiple UUVs collaborating to search for the target is significantly affected. As shown in the figure, when the speed of the dynamic target is 3 knots, the search success rate is 0.72. When the speed is increased to 5 knots, the success rate decreases to 0.65. When the speed further increases to 7 knots, the search success rate is 0.52. Based on the above data, it can be concluded that, in the absence of complete prior information, when UUV formations search according to our optimized paths, the faster the speed of dynamic targets, the lower the success rate of the search.

5.4. Analysis of Dynamic Characteristics of UUVs

The optimal path is presented on the left side of Figure 15. Within this illustration, the black stars signify the position of the target’s prior information, while the blue circles represent threat loops centered on the target. The red circles indicate sampling points positioned on each threat loop. The planned paths are distinguished based on color: the red trajectory lines represent the leader’s route, and the black trajectory lines depict the follower’s path. On the right side of the graph (assuming the original “left side” was a typo, as the UUV’s actual trajectory is typically compared to the planned path), the actual trajectory of the UUV formation is shown. Here, the orange trajectory corresponds to the leader’s path, and the black trajectory represents the follower’s path. Upon departure, the UUV formation initially travels in a straight line, traversing the target’s prior information position. It then proceeds to detect to the right rear, crosses a point, and continues forward for navigation and detection, ultimately detecting to the right front. The trajectory diagram clearly illustrates that throughout the entire search process, the UUV formation maintains a cohesive formation for efficient task execution. This path effectively balances search efficiency with area coverage. By navigating along this optimized route, the UUV formation achieves a success rate of 0.65—a significant improvement over the success rate prior to optimization—while maintaining the formation’s configuration. The optimized search path thus enhances the intersection probability with the search area, ensuring a more effective and efficient mission outcome.

In Figure 16, Figure 17 and Figure 18, the black line represents the expected trajectory position, while the red line depicts the actual trajectory of UUV 1, UUV 2, UUV 3. Through the implementation of control algorithms, members of the UUV formation consistently maneuver towards the expected position information, demonstrating a high degree of accuracy in approximating the real location. Notably, the thrust of the members of the UUV formation remains relatively constant, since the entire formation’s speed is synchronized with that of the members of the UUV formation to ensure seamless communication within the UUV formation. On the right-hand side of the figure, the rudder angle information of the members of the UUV formation is presented. During the initial phase, the members of the UUV formation undergoe a rudder angle adjustment. As the UUV formation progresses with its task, although minor fluctuations are observed, the overall rudder angle manages to maintain a stable orientation, indicating effective control and stability in maneuvering. This stability is crucial for maintaining the formation’s integrity and ensuring efficient mission execution.

6. Conclusions

This paper first constructs a realistic UUV model and its formation task scenarios in practical applications. Subsequently, based on these task scenarios, a parameterized method for spiral search is proposed to design the optimization variables. A hierarchical control strategy is then introduced to ensure that the formation can search forward while maintaining a specific configuration, grounded on the constraints of the UUV formation. Next, the optimization problem is extracted from the task scenarios, and three algorithms, primarily based on the KDGO algorithm, are employed to solve this problem. Finally, the optimization results are analyzed and compared with commonly used coverage search and direct path search in practical tasks, along with an in-depth examination of different dynamic targets. The results of the optimization experiment show that, under the condition of maintaining a constant dynamic target velocity, compared to the traditional DE and PSO algorithms, the proposed optimization framework combined with the KDGO algorithm not only converges faster but also achieves more significant optimization effects. Under this optimized path, the UUV swarm significantly enhanced the search efficiency for dynamic targets. In the designated task scenario, optimizing the path increased the search success rate of the UUV swarm from 0.42 to 0.65 compared to the coverage search, achieving a 54% improvement. In comparison to the direct search, the success rate rose from 0.34 to 0.65, representing a 101% enhancement. For different dynamic targets, the faster the target’s speed, the harder it is for the UUV to detect the target.

This paper provides a valuable reference and theoretical basis for practical multi-UUV formation collaborative search tasks by exploring key technologies for target search, including path parameterization methods, optimization framework design, and algorithm applications. These research results not only contribute to improving the search efficiency and success rate of UUV formations in complex dynamic environments but also lay a solid foundation for further expanding the application of UUVs in fields such as ocean exploration, environmental monitoring, and target tracking.

However, there are still some limitations to this research. Firstly, we did not consider the impact of ocean currents on UUVs in the actual ocean. Secondly, our research did not consider underwater obstacles at all. Furthermore, this exploration is limited to the two-dimensional marine environments. In future research, we will continuously optimize and refine the real marine environments in which micro unmanned underwater vehicles operate, aiming to provide empirical data of reference values for the practical application of UUV formations.