Collaborative Search and Target Capture of AUV Formations in Obstacle Environments

Featured Application

When multiple AUVs are combined in formation, they can improve operational efficiency while maintaining mutual communication. This article focuses on the obstacle avoidance problems en-countered by AUV formations during collaborative search and target capture, proposes an energy cost optimal formation obstacle avoidance strategy and an improved SOM path planning algorithm to achieve target capture by occupying adjacent positions of target in the underwater obstacle environment.

Abstract

When performing cooperative search operations underwater, multi-autonomous underwater vehicles formations may encounter array-type obstacles such as gullies and bumps. To safely traverse the obstacle domain, this paper balances convergence time, transformation distance and sensor network power consumption, and proposes a Formation Comprehensive Cost (FCC) model to achieve collision avoidance of the formations. The FCC model is used instead of the fitness function of the genetic algorithm to solve the assignment of capture positions and the improved neural self-organizing map (INSOM) algorithm is proposed to achieve efficient path-planning during the capture process. The simulation experiments in 3D space verify that the proposed scheme can improve the efficiency of robot deployment while ensuring safety.

1. Introduction

As a disruptive technology that changes the way society works and lives in the future, unmanned system technology has received a lot of attention and rapid development in academia and industry, among which the application of intelligent decision making robots in resource exploration, environmental monitoring, biological research, etc., has became a hotspot for research [1,2,3]. When operating in unknown waters, the operation efficiency and detection range of a single autonomous underwater vehicle (AUV) are limited by the size of the platform, while multiple AUVs operating in formation can not only improve the search efficiency, but also achieve cooperative positioning with a short communication time delay to ensure the accuracy of underwater navigation and operational safety, while the robots in the formation can occupy the coordinates around the target in a many-to-one manner to complete the capture task. Therefore, it is important to study the mission-planning of AUV formations in different environments.

In the unknown underwater environment, the AUV formation completes the capture of underwater targets in two stages: search and capture. Since the terrain obstacles can affect the safety of the formation, the array-shaped obstacles formed by submarine gullies and bulges make the AUV formation unable to maintain the original structure; therefore, whether the robots can complete the formation change independently according to the distribution of obstacles during operation has a great impact on the safety of cooperative operation.

Formation transformation [4,5] is mainly divided into static and dynamic: static formation transformation generally refers to fixed-formation transformations when obstacle distribution is not considered. Desai [6] applied nonlinear control theory and graph theory methods to study formation control strategies for mobile robots, using double rows or a columnar parade through obstacle areas, but such schemes cannot adaptively adjust the formation according to environmental information, have low flexibility and high time and energy costs, and have large limitations. Yan, Z et al. [7,8] virtually tracked linear formations using an improved artificial potential field method, but the linear structure has a high repetition rate in its detection range and low efficiency in cooperative detection. Ding, G et al. [9,10] proposed a controller based on a neural network model, which can better maintain the formation of AUVs, but did not discuss the case of traversing large obstacle domains. The dynamic formation transformation can select the optimal formation autonomously based on the environmental information. Jiang R X et al. [11] proposed an optimal efficiency model for evaluating multi-robot formation transformation for obstacle domains, choosing formation convergence time and path length as evaluation criteria, respectively, but the two models are difficult to balance in practical applications [12].

After searching for a target, whether the robots in the formation can quickly complete the assignment of capture positions and dynamically path-plan has a great impact on the efficiency of the capture operation. Cai, W [13] resolved the Multiple Traveling Sales Person (MTSP) problem using a genetic algorithm (GA), but Euclidean distance was the only cost function. Ma, X [14] and Zhu, D [15] both proposed a self-organizing neural-network-based task assignment method, but did not consider the robot’s own load energy consumption. The path-planning algorithms such as A* [16,17,18], neural network [19,20,21], ant colony [22,23,24] and reinforcement learning [25,26,27,28], etc., are more mature. Ma, X et al. [29,30] proposed a bionic neural wave network (BNWN) algorithm to complete the path-planning in a multi-AUVs collaborative target capture process; however, the computational effort is large and the real-time performance is difficult to guarantee. Hadi, B [31] proposed a path-planning and formation control strategy for the two key problems of AUV collision avoidance and obstacle avoidance but lacked experimental proof of simulation in 3D space.

This paper addresses the process of cooperative search and target capture in unknown waters by the formation of multiple AUVs, with the following main contributions:

• For the formation avoidance problem in the process of searching for targets in unknown waters, a Formation Comprehensive Cost (FCC) model that balances the convergence time, transformation distance and load energy consumption is proposed to realize the collision avoidance of array-shaped obstacles.
• The FCC model is introduced to the genetic algorithm to solve the assignment problem of capture position.
• An improved neural self-organizing map (INSOM) algorithm is proposed to realize path-planning during the capture process, and the feasibility of the proposed scheme in different types of obstacle environments is verified by simulation experiments.

The rest of the paper is organized as follows: Section 2 describes the general flow of the proposed formation capture scheme. Section 3 establishes the simulation environment model, describes the position change of each robot during the formation transformation using the formation parameter information matrix, and proposes an FCC model that balances the convergence time, transformation distance and load energy consumption to realize the formation change during the search process. Section 4 introduces the FCC model to GA to complete the allocation of capture positions within the formation and combines this with the INSOM algorithm to realize the rapid deployment of robots in collaborative capture. Section 5 shows and explains the simulation experimental results. Section 6 summarizes the proposed target capture scheme.

2. Target Capture Scheme for AUV Formation

When operating in waters where the target location is unknown, AUVs can sense the surrounding environment through various sensors that are carried by themselves (such as multibeam forward-looking sonar and underwater camera), and use multi-source data fusion and target identification technology to obtain information regarding the obstacles and targets in the environment, providing data support for collision avoidance and target capture in AUV formation.

The process of AUV formation when capturing targets in an unknown environment is shown in Figure 1, and the whole operation process is divided into two major parts, cooperative search and target capture, based on whether the robot formation finds the target. After the initialization of the formation, the robots keep the preset structure to detect the operating water in the forbidden search mode; if an obstacle is detected, they will judge whether they need to change the formation, and, if so, they will cross the obstacle domain with the optimal formation after the change, and then revert to the original formation to continue the search. When the formation senses the location of the target, the system enters the capture phase. After the task assignment, the system informs the corresponding robot of the capture location, and then combines with the path-planning algorithm to complete the containment of the target. Since the formation change strategy, task assignment and path-planning method directly affect the efficiency and safety of the operation, they are the focus of this paper.

3. Formation Cooperative Search and Transformation Strategy

3.1. Formation and Environment Initialization

The commonly used robot formation is shown in Figure 2a–e, and in order to achieve a cooperative exploration at different depths and reduce unnecessary energy consumption when moving in AUV formation [32,33], this paper chose a formation structure based on the geese type to complete the formation initialization (as shown in Figure 2f), in which the bottom robot extends the exploration range in two directions at 90°, and the interval between neighboring robots is the distance threshold D_S, which is used to ensure the communication quality. The system randomly selects a robot as the initial virtual leader during the collaborative search process, and when any robot in the formation detects an obstacle, it switches to the new virtual leader to guide the other robots in their travels, resulting in a high formation flexibility and fault tolerance.

When the formation encounters a complex obstacle environment in the form of submarine gullies and bulges due to crustal movements, robots must be able to change formation to traverse the obstacle domain, guarantee the communication quality between AUVs and take advantage of cooperative operations. To facilitate an explanation of the proposed scheme, an underwater virtual environment containing a large array of obstacles is created in this paper (Figure 3). The yellow cube represents the target, the cubes distributed around it represent the small obstacles, the four dark columns represent the large obstacle areas, and the six cyan nodes represent the formation of six AUVs.

3.2. Formation Control Scheme

When large obstacles are encountered during the search process, multiple AUVs traverse the obstacle domain in formation transformation, which can take advantage of cooperative search and ensure the communication quality between robots. The formation recovery can be completed in the shortest time after traversing the obstacles. To facilitate the analysis of a formation traversal mode in array-type obstacle domains, a formation control model is provided in this section to describe the position change of each robot during the formation transformation using the formation parameter information matrix as follows:

$$B{T}_{li}\left(t+t_{all}\right)=\left\{\begin{array}{l}B{T}_{lc-x}\left(t\right)+{\mu }_i\ast f_i+f_c \\ B{T}_{lc-y}\left(t\right)+{\mu }_i\ast f_i+f_c \\ B{T}_{lc-z}\left(t\right)+{\mu }_i\ast f_i+f_c \\ i=1,2,\cdots ,N\end{array}\right.$$

(1)

where t is the start time of the transformation, $t_{all}$ is the total time needed to complete the transformation, $B{T}_{l\mathrm{c}}\left(t\right)$ represents the coordinates of the virtual leader before the transformation, $B{T}_{li}\left(t+t_{all}\right)$ represents the coordinates of the robots in the formation after the transformation, ${\mu }_i$ and $f_i$ are the deformation control rate and the team control function of the i-th robot, respectively, and $f_c$ is the virtual structure point motion control function set in Section 3.1.

The N AUVs in the formation are denoted as $R_1,R_2\dots R_N$, and the state of the i-th robot $R_i$ is represented as $S_i$. If $R_i$ is set as the leader, then $S_i=1$; otherwise, $S_i=0$. To represent the state and formation of each robot, Equations (2) and (3) define the parameter information matrix of the leader and non-leader AUVs, respectively.

$$F_i=\left[\begin{array}{c}{R}_i\\ S_i\\ B{T}_{li}\left(t\right)\end{array}\right]$$

(2)

$$F_i=\left[\begin{array}{c}{R}_i\\ S_i\\ {\mu }_i\ast f_i\end{array}\right]$$

(3)

If $R_1$ is set as the virtual leader, the parameter information matrix F for the whole formation can be expressed as:

$$F=[F_1,F_2\dots F_i\dots ,F_N]=\left[\begin{array}{cc}{R}_1& R_2\\ S_1& S_2\\ B{T}_{li}\left(t\right)& {\mu }_2\ast f_2\left(x\right)\end{array}\dots \begin{array}{c}{R}_i\\ S_i\\ {\mu }_i\ast f_i\left(x\right)\end{array}\dots \begin{array}{c}{R}_N\\ S_N\\ {\mu }_N\ast f_N\left(x\right)\end{array}\right]$$

(4)

Meanwhile, the robots inside the formation need to satisfy the collision avoidance constraint, i.e., the distance between any two robots is greater than or equal to the safety distance $L_s$:

$$\left|R_i-R_j\right|=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2+{(z_i-z_j)}^2}\ge L_s$$

(5)

In this paper, the geese formation is set as the basic search formation, and the transformed formations can evolve from the basic formation. For the convenience of explanation, several formation transformation schemes when the geese formation encounters a large obstacle domain are projected onto the XOY plane to obtain Figure 4. If an array-type obstacle domain is detected during the formation cooperative search, the feasible spacing $D_o$ of the obstacle domain is compared with the maximum spacing $D_r\left(D_r=2\sqrt{2}{D}_S\right)$ of the robots in the formation to determine whether the current formation can traverse the obstacle domain. If it cannot, then whether Figure 4b,c obtained by modifying $\mu$ is feasible is determined, and if it is still not possible to traverse the obstacle domain, Figure 4d, obtained by changing $f$ as the traversal formation, is chosen. Most of the existing formation transformation strategies address the special state where the leader is on the central axis of the obstacle domain, so the analysis of the energy consumption during transformation is incomplete, and the transformation scheme shown in this paper complements the situation where the leader is on both sides of the central axis (Figure 4b), which is more adaptable.

The AUV formation achieves an adaptive search through the forbidden search mechanism and the adjustment of sensor detection distance, and performs formation transformation under the constraint of Equation (1) to adapt to the change in environment and operational requirements. When any single robot in the formation detects an obstacle, this robot is set as the leader and the rest of the robots switch to the follower state. The system switches from the formation cooperative search state to the distributed tracking state when the target is detected, and the cooperative capture of the target is realized through the path-planning algorithm.

The advantage of this formation control method is that each AUV can be considered a virtual pilot, and the other AUVs choose their own movement according to the virtual pilot. By replacing the virtual leader when the leader breaks down, the whole formation can continue to operate without going into a paralyzed state. When a robot fails, the robot can still navigate according to the path that was planned at the previous moment, and other robots can reach the designated target position according to the original plan, with a strong fault tolerance.

3.3. Formation Comprehensive Cost (FCC) Model

Various evaluation models have been proposed by researchers to address the energy consumption problem in dynamic formation transformation. The optimal formation convergence time (FCT) efficiency model [11] aims to find the robot that consumes the most time t_i in the formation transformation and minimizes its moving distance, and the shortest convergence time model that is obtained is:

$$T=\min \max \{t_1,t_2,t_3\dots t_n\}$$

(6)

The objective of the optimal formation energy consumption (FEC) efficiency model [11] is to calculate and minimize the sum of all robots moving in the formation transformation, and the resulting minimum energy consumption model is (with $s_k$ representing the sum of paths for each AUV in the k-th permutation):

$$D=\min \{s_1,s_2,s_3\dots s_k\}$$

(7)

Most of the existing formation transformation schemes are based on the above two models; however, the minimum time and the minimum energy consumption obtain different optimal results in some environments, and the power consumption of the sensors inside the platform during the operation (e.g., forward-looking sonar sensing the surrounding environment) is ignored. Therefore, this paper further considers the power consumption brought by hardware systems such as sensor networks inside the robot, combines the energy consumption caused by motion transformation with the inherent hardware energy consumption of the transformation process, and proposes a formation comprehensive cost (FCC) model that integrates the convergence time, transformation distance and load energy consumption, as shown in Equation (8):

$$\min E=\min {\displaystyle \sum _{i=1}^n(({\displaystyle \sum _{j=1}^{k_i-1}\lambda v_i{}^3\frac{\left|\overrightarrow{d_{i,j}{d}_{i,j+1}}\right|}{v_g}})+\frac{D_{\max }}{v_g}{p}_0)}$$

(8)

The first half of Equation (8) represents the energy consumption caused by the distance the AUV moves when changing formation, and the second half represents the energy consumption of the system load, which is determined by the formation convergence time. $\lambda$ represents the water resistance coefficient, which is related to the AUV shape and underwater environment, $v_i$ represents the propulsion speed of the AUV propeller, $v_g$ represents the motion speed of the AUV relative to the geodesic coordinate system, $p_0$ represents the inherent power consumption of the AUV, which is determined by the consumption of the internal components of the robot, $k_i$ represents the number of path points passed by the i-th AUV, and $d_i$ is the position of each path point during the transformation. $D_{\max }$ denotes the maximum distance the robot moves during the formation change and is given by Equation (9):

$$D_{\max }=\max \{{\displaystyle \sum _{j=1}^{k_1-1}\left|\overrightarrow{d_{1,j}{d}_{1,j+1}}\right|},{\displaystyle \sum _{j=1}^{k_2-1}\left|\overrightarrow{d_{2,j}{d}_{2,j+1}}\right|},\cdots {\displaystyle \sum _{j=1}^{k_i-1}\left|\overrightarrow{d_{i,j}{d}_{i,j+1}}\right|}\cdots ,{\displaystyle \sum _{j=1}^{k_n-1}\left|\overrightarrow{d_{n,j}{d}_{n,j+1}}\right|}\}$$

(9)

By bringing Equation (1) into Equation (8), the integrated energy consumption environment adaptation function for dynamic formation transformation can be obtained as follows:

$$\min E=\left\{\begin{array}{c}\min {\displaystyle \sum _{i=1}^n(({\displaystyle \sum _{\mathrm{t}=1}^{t_t-1}\lambda v_{\mathrm{i}}{}^3\frac{\left|\right|B{T}_{li-x}\left(t+1\right)-B{T}_{li-x}\left(t\right)\left(1\right)\left|\right|}{v_g}})+\frac{D_{\max }}{v_g}{p}_0)}\\ \min {\displaystyle \sum _{i=1}^n(({\displaystyle \sum _{\mathrm{t}=1}^{t_t-1}\lambda v_{\mathrm{i}}{}^3\frac{\left|\right|B{T}_{li-y}\left(t+1\right)\left(2\right)-B{T}_{li-y}\left(t\right)\left(2\right)\left|\right|}{v_g}})+\frac{D_{\max }}{v_g}{p}_0)}\\ \min {\displaystyle \sum _{i=1}^n(({\displaystyle \sum _{\mathrm{t}=1}^{t_t-1}\lambda v_{\mathrm{i}}{}^3\frac{\left|\right|B{T}_{li-z}\left(t+1\right)\left(3\right)-B{T}_{li-z}\left(t\right)\left(3\right)\left|\right|}{v_g}})+\frac{D_{\max }}{v_g}{p}_0)}\end{array}\right.$$

(10)

For energy consumption analysis of the formation transformation, this paper uses the position of each robot in the formation within the grid network as the basis for solving the position of the robot at the minimum fitness value (the formation transformation with the lowest integrated cost) using the FCC model.

3.4. Formation Cooperative Search Process

The flow of the AUV formation in the collaborative search process is shown in Figure 5: if any robot in the formation detects a target, then the search process ends and enters the subsequent capture process; otherwise, the formation senses the environment in the form of a forbidden search. If the formation detects an array-type obstacle field during the cooperative search, it compares the feasible spacing of the obstacle field with the maximum spacing of the robots in the formation to determine whether the current formation can pass the obstacle field. If the AUV formation must change its formation to pass the obstacle field, the system selects the optimal formation through the environmental adaptation function in the FCC model, controls the AUV formation to reach the position corresponding to the optimal formation, and keeps the original heading to cross the obstacle field; otherwise, the AUV formation does not need to change its formation, and crosses the obstacle field in a straight line to save energy. When the robot at the end of the formation is far from the obstacle domain, the formation changes back to the base formation of geese and continues to perform search operations until the target is detected.

4. Target Cooperative Capture

4.1. GA-Based Task Assignment

In a 3D underwater space, a formation is judged to have successfully captured a target when the robots in the formation occupy each of the six neighborhood positions around the target. Therefore, task assignment is required to determine the capture position of each robot after the formation enters the capture phase, and the assignment result affects the deployment speed and capture efficiency of the robots.

The traditional exhaustive enumeration method is widely used in task assignment. Although the exhaustive enumeration strategy can obtain the optimal solution, it contains randomness and uncertainty, and the complexity of the algorithm increases as the number of targets to be assigned increases (there are N! kinds of assignment schemes for N targets). If there are too many targets to be assigned, the strategy may not converge to obtain the optimal solution in finite time. In addition, when the target moves, the capture points around it are changing, and the task points assigned to each robot are also dynamically changing. If the grid density is large, the exhaustive method will seriously affect the real-time performance of the algorithm, while the small grid density cannot guarantee that the optimal assignment scheme will be obtained.

The genetic algorithm is based on pattern theorem and Markov chain model, so its search possesses a better directionality, fast computation, and smaller probability of falling into local optimum; however, the problem of under- or over-assignment may occur. In addition, individuals with higher fitness in the genetic process have a higher probability of being inherited by the next generation, but the fitness function based on Euclidean distance cannot achieve dual evolution in time and space.

The optimization goal of task assignment is the lowest total energy consumption required as the robot occupies the corresponding position. In this paper, we propose a GA-based task assignment method (Figure 6), where the formation obtains different position assignments that are actually equivalent to the robot team transformation again, so this paper introduces the FCC model to the GA process to replace the original fitness function and make the natural selection in the evolutionary process more realistic. This is integrated with the reassignment strategy to solve the possible over- and under-assignment problems.

The fitness function chosen by the genetic algorithm to solve the minimization problem is:

$$fit(x)=-{\displaystyle \sum _{i=1}^n{w}_i{x}_i}$$

(11)

A new objective function is constructed by bringing Equation (8) into the objective function of the genetic algorithm:

$$f(x)=\min {\displaystyle \sum _{i=1}^n{w}_i{x}_i}$$

(12)

where

$$x_i=({\displaystyle \sum _{j=1}^{{\mathrm{k}}_i-1}\lambda v_i{}^3\frac{\left|\overrightarrow{d_{i,j}{d}_{i,j+1}}\right|}{v_g}})+\frac{D_{\max }}{v_g}{p}_0$$

(13)

Experimental verification: the number of individuals was set to 6, the maximum genetic generation was set to 100, the generation gap was set to 0.9, and the chromosome length was set to 6. After several iterations, the target assignment results of the six robots are shown in

Table 1. Assignment results of different methods.

	Capture PositionMethod	1	2	3	4	5	6
Method
GA		1	1	2	2	4	6
Exhaustive method		1	3	2	5	4	6
Proposed		1	3	2	5	4	6

.

As can be seen from Table 1, the initial genetic algorithm suffers from over- and under-assignment problems, while the improved GA method proposed in this paper achieves uniqueness in target assignment, which is consistent with the results obtained by the exhaustive method. In addition, the target assignment scheme based on the GA reflects the faster convergence speed, as shown in Figure 7. The greater the number of robots in the formation and the assignment target, the greater the computational advantage of the proposed scheme and the better its applicability to the assignment problem of different formations.

4.2. Improved Neural Self-Organizing Map (INSOM) Algorithm

SOM is an unsupervised clustering algorithm that uses the target as the input layer of the neural network and the current position of the robot as the output layer (Figure 8), and determines the winner of the next iteration position by competing for distance attributes [10], while the weight update rules for the winning neuron and its neighbors as they move towards the input neuron (the target) are defined as:

$$R_j(k+1)=\left\{\begin{array}{l}{T}_l, \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{D}_{jl}<D_{\mathit{min}}\\ R_j(k)+\alpha \cdot f(d_m,G)\cdot (T_l-R_j(k)), others \end{array}\right.$$

(14)

where $R_j=(w_{jx},w_{jy},w_{jz})$ denotes the position of the j-th AUV, $T_l=(x_l,y_l,z_l)$ denotes the position of the i-th target, $\alpha (0<\alpha \le 1)$ is the learning rate, $D_{\mathit{min}}$ denotes the minimum decision distance to reach the target, and the neighborhood function $f$ determines the degree of attraction of the winner to the neighborhood neurons, given by Equation (15):

$$f\left(d_m,G\right)=\left\{\begin{array}{l}{e}^{-d_m^2/G^2\left(\mathrm{t}\right)}, d_m\le \lambda \\ 0, d_m>\lambda \end{array}\right.$$

(15)

$d_m$ denotes the Euclidean distance of the m-th neuron from the winning neuron, λ is the neighborhood radius, and $G\left(t\right)={(1-\beta )}^t{G}_0$ is a Gaussian function determined by the decay factor β.

$$x_i(t+1)=g\left({\displaystyle \sum }_{j=1}^J{\omega }_{ij}\ast x_j(t)+I_i\right)$$

(16)

$$\left\{\begin{array}{l}{\omega }_{ij}=\left\{\begin{array}{l}{e}^{-\gamma |i-j{|}^2}, |i-j|\le r\\ 0, |i-j|>r\end{array}\right.\\ g(x)=\left\{\begin{array}{l}0, x<0\\ \beta x, x\in [0,1]\\ 1, x>1\end{array}\right.\end{array}\right.$$

(17)

The traditional SOM algorithm does not have the obstacle avoidance ability and the robot suffers from speed jumps, which may exceed the actual motion capability of the platform. Zhu Daqi et al. [20] used the GBNN model (Equations (16) and (17)) to construct an active network of neurons to solve the robot’s obstacle avoidance and speed problems; however, the computational speed in the process of iteratively spreading the target activity layer by layer to the global activity is greatly influenced by the scale and number of grids, and the finer the grids and the larger the operational scale the slower the computational speed, making it difficult to rapidly deploy the task. In addition, the robot’s manipulation constraints are not considered when traveling to the next iteration point, and there may be cases where the steering exceeds 90° (e.g., in Figure 9, if the robot drives from the green node to the red node, the next iteration point should not return to the plane where the green node is located).

To solve the above problems, this paper proposes an improved neural self-organizing map (INSOM) algorithm, which takes the target as the global origin of activity and the obstacle as the local origin. The activity value of neurons decreases layer by layer, with the origin point as the center, and the robot only needs to calculate and compare the activity value magnitude of neighboring neurons to update the path points to achieve path-planning. The algorithm flow is as follows:

• Denote $P_{tm}\in \stackrel{\circ }{U}(P_t,r)$ as the neighboring node $(r\le \sqrt{3})$ of the current node $P_t(x_t,y_t,z_t)$, and $\cos 〈\overrightarrow{A},\overrightarrow{B}〉$ denotes the angle between the vector $\overrightarrow{A}$ and $\overrightarrow{B}$. Then, the neighboring nodes should satisfy the steering constraint:

  $$\cos 〈\overrightarrow{P_{t-1}{P}_t},\overrightarrow{P_t{P}_{tm}}〉\le \frac{\pi }{2}$$

  (18)
• A simplified activity value calculation method (Equation (19)) is proposed, where the activity value of a node does not depend on the activity of neighboring nodes, thus reducing the waste of resources caused by the cumulative calculation in Equation (16).

  $$X_{tm}\left(i\right)=E_t-\gamma \cdot D_{T-i}+g\left(D_{ob-i}\right)\cdot E_{ob}$$

  (19)

  where $X_{tm}\left(i\right)$ denotes the activity of the i-th neighbor node of the current node, $E_t$ and $E_{ob}$ are the activities of the target and obstacle nodes, respectively, the target point gravitational factor $\gamma$ satisfies $0<\gamma <1$, $D_{T-i}$ denotes the distance from the i-th neighbor node to the target point, and $g\left(D_{ob-i}\right)$ is the obstacle influence activation function given by Equation (20):

  $$g(D_{ob-i}) =\left\{\begin{array}{l}\beta /D_{ob-i}^2, D_{ob-i}\le R_{ob}\\ 0, others\end{array}\right.$$

  (20)

  where β is the obstacle local repulsion factor, $D_{ob-i}$ denotes the distance from the i-th neighborhood node to the obstacle, and $R_{ob}$ is the influence range of the obstacle.
• The next virtual iteration point $Q_{t+1}$ of the robot can be calculated by Equation (21):

  $$Q_{t+1}=\mathit{arg}\mathit{max}\{X_{P_{tm}},P_{tm}\in \stackrel{\circ }{U}(P_t,r)\cap \cos 〈\overrightarrow{P_{t-1}{P}_t},\overrightarrow{P_t{P}_{tm}}〉\le \frac{\pi }{2}\}$$

  (21)
• In conclusion, the next path point $P_{t+1}$ of AUV can be calculated by Equation (22):

  $$P_{t+1}=\left\{\begin{array}{l}T, \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{D}_{T-P_t}\le D_{\mathit{min}}\\ P_t+\alpha \cdot f\cdot \left(Q_{t+1}-P_t\right),D_{T-P_t}>D_{\mathit{min}}\end{array}\right.$$

  (22)

  where $\alpha (0<\alpha <1)$ is the learning efficiency, and in this paper, the robot corresponds to the capture position of each target, so the neighborhood function $f = 1$ can further reduce the computation time.

In the improved algorithm proposed in this paper, the robot does not need to traverse the entire grid network, but only needs to compare the activity values of neighboring nodes to complete the iteration of path points, and the node activity values do not need to be cumulatively calculated in Equation (16), so the computational speed of the algorithm is improved. Equation (18) makes the steering of path points more consistent with the platform manipulation constraints. In addition, Equations (19) and (20) ensure the safety of obstacle avoidance in the robot.

In summary, when each robot in the formation determines the capture position through the task assignment in the previous section, the improved algorithm proposed in this paper can realize the rapid deployment of robots in the process of cooperative target capture.

5. Simulation Analysis

5.1. Environment Initialization

In order to further verify the effectiveness of the proposed formation transformation strategy and path-planning algorithm, and to demonstrate the integration effect of the cooperative search and target capture process, a 3D underwater environment containing an array-type obstacle domain was established with the help of the MatlabR2022a platform in this paper (Figure 3), a simulation analysis of the formation composed of six robots was carried out, and the simulation experiments were completed with several groups of different parameters.

Table 2. Simulation experiment environment setup.

Robot Number	Coordinates of the Robots	Coordinates of the Target	Coordinates of the Obstacles
1	(60, 150, 150)	(250, 150, 150)	(100, 0, 0~300)
2	(35, 125, 150)	-	(100, 120, 0~300)
3	(35, 175, 150)	-	(100, 300, 0~300)
4	(10, 100, 150)	-	-
5	(10, 200, 150)	-	-
6	(60, 150, 100)	-	-

shows the initial position of the set AUV formation and the obstacle distribution.

By calculating the power of each component of the AUV platform, the ratio of AUV motion power consumption to its own component power consumption is empirically set to 16:9 (adaptive adjustment according to different loads on different platforms). The settings of some parameters in the FCC model are shown in

Table 3. Parameter setting.

Parameter	${\mathit{E}}_{\mathit{b}}$	${\mathit{E}}_{\mathit{a}}$	${\mathit{v}}_{\mathit{g}}$	${\mathit{p}}_0$	${\mathit{D}}_{\mathbf{s}}$
Value	−20	20	4	70.3	90

, and their magnitudes can be changed according to the different environments and normalized in this paper without setting specific units.

5.2. Effect of Robot Performance on Formation Transformation

From Equation (8), the navigation state of the robot itself was shown to have a great influence on the choice of the formation transformation scheme, so this section discusses the influence of different state parameters on the transformation scheme. The performance of the robot is affected by its internal space limitation (limited battery compartment and drive unit, etc.) and water resistance, and the navigation speed was set to within 10 m/s in this paper. Because of the random nature of the taboo search, the data obtained from each trial were not identical, and

Table 4. Influence of robot navigation state on transformation scheme.

${\mathit{v}}_{\mathit{g}}$	${\mathit{p}}_0$	Transformation Scheme	Convergence Time	Total Path Length of the Transformation	Comprehensive Energy Consumption
0.5	70.3	571	92.1954	138.4584	3.8923 × 104
1	70.3	571	46.0977	138.4584	1.9582 × 104
2	70.3	571	23.0489	138.4584	1.0276 × 104
4	70.3	571	11.5244	138.4584	0.7076 × 104
5	70.3	1371	9.4868	132.4342	0.7312 × 104
10	70.3	1371	4.7434	132.4342	1.5244 × 104
4	20.3	1371	11.8585	132.4342	3.5420 × 104
4	30.3	1371	11.8585	132.4342	4.2535 × 104
4	40.3	1371	11.8585	132.4342	4.9650 × 104
4	50.3	571	11.5244	138.4584	5.6727 × 104
4	60.3	571	11.5244	138.4584	6.3641 × 104

shows several representative sets of results (values are normalized).

As can be seen from Table 4, the FCC model proposed in this paper can autonomously select dynamic formation transformation schemes according to the different robot navigation parameters ($v_g$ and $p_0$), and each scheme corresponds to a unique $\mu$ and $f$, thus constraining the formation. In addition, the FCC model also leaves an interface for environmental factors such as ocean currents, which can simulate the formation change under ocean current disturbance.

5.3. Operational Results of Robot Formations

For a clearer representation of the search, formation transformation and hunting processes, this section provides a detailed description of the transformation process by taking any of the robot navigation states in Table 4 as an example. When $v_g=5$ and $p_0=70.3$, the transformed energy consumption of different formations is shown in Figure 10. From the results in Table 4, the FCEC model is selected as the 1371st formation transformation scheme, and this scheme is the one with a less integrated energy consumption under the premise of smoothly passing the obstacle domain that corresponds to Figure 10.

The whole operational effect of the multi-AUV formation in the current motion state is shown in Figure 11, and the projection to the XOY coordinate plane is shown in Figure 12. As can be seen from the figure, the proposed scheme in this paper enables the formation of multiple AUVs to accomplish the tasks of area search and target capture in an unknown underwater 3D environment. During the cooperative search process, the formation can lead to an independent obstacle-avoidance strategy according to the detected array-shaped obstacles, determine the optimal traversal solution and complete the formation transformation through the FCC model, and return to the basic wild goose formation after traversing the obstacle domain to continue the search operation. After detecting the target, the task is assigned to the robots in the formation using the improved GA. After each robot determines its own target capture position, it completes the path-planning using the proposed INSOM algorithm and finally successfully achieves the cooperative target hunting.

Figure 13 and Figure 14 show the formation transformation process for the 3D and 2D (projected to the XOY coordinate plane) cases, respectively. From the beginning to the end of the dynamic formation transformation, the coordinate changes of each robot are shown in

Table 5. Coordinate change of the robots during the transformation.

Robot Number	1	2	3	4	5	6
State	1	0	0	0	0	0
Coordinate	(70, 160, 140)	(45, 135, 140)	(45, 185, 140)	(20, 110, 140)	(20, 210, 140)	(70, 160, 90)
	(75, 160, 140)	(45, 135, 140)	(50, 185, 140)	(25, 110, 140)	(25, 210, 140)	(75, 160, 90)
	(80, 160, 140)	(50, 135, 140)	(55, 185, 140)	(25, 115, 140)	(30, 210, 140)	(80, 160, 90)
	(85, 160, 140)	(50, 140, 140)	(55, 185, 140)	(25, 120, 140)	(30, 210, 140)	(85, 160, 90)
	(90, 160, 140)	(50, 145, 140)	(55, 185, 140)	(25, 125, 140)	(30, 210, 140)	(90, 160, 90)
	(95, 160, 140)	(50, 150, 140)	(55, 185, 140)	(25, 130, 140)	(30, 210, 140)	(95, 160, 90)
	(95, 160, 140)	(55, 150, 140)	(55, 185, 140)	(25, 135, 140)	(30, 210, 140)	(95, 160, 90)
	(95, 160, 140)	(55, 155, 140)	(55, 185, 140)	(25, 140, 140)	(30, 210, 140)	(95, 160, 90)
	(95, 160, 140)	(55, 155, 140)	(55, 185, 140)	(30, 140, 140)	(30, 210, 140)	(95, 160, 90)
	(95, 160, 140)	(55, 155, 140)	(55, 185, 140)	(30, 145, 140)	(30, 210, 140)	(95, 160, 90)
	(95, 160, 140)	(55, 155, 140)	(55, 185, 140)	(30, 150, 140)	(30, 210, 140)	(95, 160, 90)
	(95, 160, 140)	(55, 155, 140)	(55, 185, 140)	(30, 155, 140)	(30, 210, 140)	(95, 160, 90)

.

5.4. Comparison with Other Formation Transformation Solutions

To further verify the effectiveness of the proposed scheme, this section simulates and compares the transformation scheme based on the FCC model with the formation transformation scheme given in References [6,11], and the initial environment and parameter settings of the experiments are the same as those in Section 5.1.

Taking the navigation state of the robot as $v_g=4$ and $p_0=70.3$ as an example, if a fixed column formation is used to cross the obstacle domain [6], the simulation results of the whole operation process are shown in Figure 15 and Figure 16, which show the results of the formation transformation process that is projected to the XOY plane. If the method in the literature [11] is adopted, and the optimal FCT or optimal FEC model is used as the judgment criterion to select the transformation scheme passing through the obstacle domain, the whole operation process and its projection to the XOY plane are shown in Figure 17 and Figure 18. As can be seen from Figure 15, Figure 16, Figure 17 and Figure 18 the transformation schemes based on the three models in References [6,11] are all capable of avoiding small obstacles and traversing large obstacle domains; however, the energy consumption of the formation transformation schemes is different.

To obtain more obvious comparison results, the simulation results of four schemes with different navigation parameters are given in

Table 6. Comparison of different formation transformation schemes.

State	Selection Criteria	Transformation Scheme	Energy Consumption	Convergence Time	Total Length of Paths	Combine with Target Capture?
$v_g=4$	FCC model	571	0.7076 × 104	11.5244	138.4584	Yes
	Fixed column formation [6]	-	1.1334 × 104	16.2500	280.1635	No
$p_0=70.3$	FCT model [11]	551	0.7274 × 104	11.5244	150.8191	No
	FEC model [11]	1371	0.7121 × 104	11.8585	132.4342	No
$v_g=5$	FCC model	1371	0.7312 × 104	9.4868	132.4342	Yes
	Fixed column formation [6]	-	0.9963 × 104	12.9732	280.1635	No
$p_0=70.3$	FCT model [11]	551	0.7659 × 104	9.2195	150.8191	No
	FEC model [11]	1371	0.7312 × 104	9.4868	132.4342	No

by taking the energy consumption, convergence time and the total length of the paths in the formation transformation process as the judgment criteria.

According to the comparison results in Table 6, it can be seen that passing through the obstacle area in a fixed formation is the most unreasonable option; in addition to the maximum transformation path length of the robot, the formation transformation requires more time and energy than other schemes, while the transformation schemes based on the FCT and FEC models can be changed according to the environmental constraints, but will not change with the parameters of the navigation state of the AUV. Therefore, they have certain limitations. For the judgment criteria in Table 6, the FCC model proposed in this paper can obtain the optimal formation transformation scheme, which illustrates the effectiveness and compatibility of the proposed scheme, and can provide different robot navigation states according to the different formation and obstacle domains. The model can also be combined with assignment and planning in the target capture process, and has a higher overall performance in underwater operations.

6. Conclusions

This paper addresses the process of cooperative search and target capture by multi-AUV formations in unknown waters. The formation traversal mode in the array-type obstacle domain is analyzed, and the position changes of each robot during the formation transformation are effectively described using the formation parameter information matrix. For the optimal transformation problem of the formation, an FCC model that balances the convergence time, transformation distance and load energy consumption is proposed to realize the formation avoidance of array-shaped obstacles in the cooperative search phase. The FCC model is introduced to the genetic algorithm to solve the capture position assignment problem. The INSOM algorithm is proposed to realize the path-planning in the capture process, and the feasibility of the proposed scheme in different types of obstacle environments is verified by simulation experiments. In summary, the proposed scheme can provide different robot navigation states according to the different formation and obstacle domains, and can also be combined with the assignment and planning in the target capture process to improve the efficiency of robot deployment while ensuring safety.

The formation transformation scheme proposed in this article takes natural terrain such as submarine gullies and protrusions as application scenarios, and lacks research on depth-direction transformation. Therefore, the proposed scheme has strict usage conditions for caves, pipelines, and more complex array obstacles that are made manually, and further research is needed to improve the applicability of the method.