Research on the Heterogeneous Autonomous Underwater Vehicle Cluster Scheduling Problem Based on Underwater Docking Chambers

Abstract

The onboard energy supply of Autonomous Underwater Vehicles (AUVs) is one of the main limiting factors for their development. The existing methods of deploying and retrieving AUVs from mother ships consume a significant amount of energy during submerging and surfacing, resulting in a small percentage of actual working time. Underwater docking chambers provide support to AUVs underwater, saving their precious energy and addressing this issue. When an AUV cluster is assigned multiple tasks, scheduling the cluster becomes essential, and task allocation and path planning are among the core problems in AUV cluster scheduling research. In this paper, based on the underwater docking chamber, an Improved Genetic Local Search Algorithm with Prior Knowledge (IGLSAPK) is proposed to simultaneously solve the task allocation and path planning problems. Under constraints such as onboard energy supply, AUV quantity, and AUV type, the algorithm groups AUVs, assigns tasks, and plans paths to accomplish tasks at different locations, aiming to achieve overall efficiency. The algorithm first generates an initial population using prior knowledge to improve its search efficiency. It then combines an improved local search algorithm to efficiently solve large-scale, complex, and highly coupled problems. The algorithm has been evaluated through simulation experiments and comparative experiments, and the results demonstrate that the proposed algorithm outperforms other algorithms in terms of speed and optimality. The algorithm presented in this paper addresses the grouping, task allocation, and path planning problems in heterogeneous AUV clusters. Its practical significance lies in its ability to handle tasks executed by a heterogeneous AUV group, making it more practical compared to previous algorithms.

1. Introduction

In recent years, the application of Autonomous Underwater Vehicles (AUVs) has become increasingly widespread, and the tasks they need to complete have become more complex. They are extensively utilized in marine surveys, mapping, environmental monitoring, search operations, oil and gas exploration, and for inspections of underwater pipelines and infrastructure. Due to limitations in space payloads, energy, and costs, a single AUV cannot complete complex underwater missions effectively. An AUV cluster is a system composed of multiple AUVs. AUV clusters can accomplish complex tasks more efficiently and robustly. However, the traditional method of deploying and recovering AUVs from a mother ship requires high sea conditions, which results in high costs and involves certain unknown risks. The development of AUV clusters has greatly increased the number of AUVs, posing significant challenges in deploying and recovering them. The emergence of underwater docks has eased this problem. By using an underwater dock, multiple AUVs can be deployed and recovered at once. Energy supply, data collection, maintenance and repair, and other operations can be performed on AUVs underwater. This approach provides a relatively stable underwater environment, greatly improving the reliability and safety of AUV deployment and recovery. Additionally, AUVs do not need to frequently surface or submerge, saving precious onboard energy. Based on underwater docks, the scientific scheduling of AUV clusters is required for multiple task demands.

1.1. AUV Cluster Scheduling

AUV cluster scheduling refers to the assignment of tasks, path planning, and coordinated control of a cluster composed of multiple AUVs. In order to improve the efficiency of the overall mission, the allocation of tasks for multiple AUVs is determined based on the cost and requirements of each task [1,2]. The problem studied in this paper consists of three parts: heterogeneous AUV cluster grouping, task allocation within AUV teams, and path planning. These three parts have been extensively researched, but their interdependence poses significant challenges in solving the problem. They cannot be addressed separately and require comprehensive consideration.

AUV cluster task allocation can be divided into two methods: centralized and distributed. The centralized task allocation method requires each AUV to send information about its environment and the cost function for task execution to a central control center. The control center then considers the AUVs and tasks to make reasonable assignments [3]. After obtaining the positions and statuses of all AUVs in the system, the control center allocates the tasks based on their requirements. The objective is to minimize overall consumption or travel distance. This means that AUVs only participate in the “execution” step and not the “decision-making” step. The main centralized allocation methods include model-based linear programming methods [4], objective clustering methods [5], genetic algorithms [6], ant colony algorithms [7], particle swarm optimization [8], firefly algorithm [9], etc. [10]. This method heavily relies on underwater communication and puts a heavy computational burden on the control center. Therefore, it is preferred in situations with good communication conditions and low computational complexity. The distributed allocation method, on the other hand, involves AUVs communicating and “negotiating” with each other to formulate allocation plans and then execute them. It can also be referred to as decentralized allocation. The advantage of the distributed allocation method is that it ensures maximum efficiency for individual AUVs and fully utilizes the intelligent elements of AUVs. This algorithm is widely used in the field of robotics, including applications in biological immune mechanisms [11], contract network algorithms [12], market auction algorithms [13], as well as algorithms suitable for multi-agent information communication, such as self-organizing maps (SOM) [14].

AUV clusters are divided into homogenous and heterogeneous types, and a complex task requires collaboration among AUVs with different payloads. In underwater environments, due to cost constraints, a single AUV cannot integrate all functions, and thus, multiple types of heterogeneous AUVs are needed to collaborate on tasks. Therefore, heterogeneous multi-AUV systems are receiving increasing attention. Reasonable AUV task allocation can improve the efficiency of multi-AUV collaborative work and reduce the cost of collaboration.

AUV clusters can be organized into master–slave and parallel configurations. In a master–slave AUV system, one or a few vehicles serve as the master AUV with high-precision equipment, while the remaining vehicles are configured as slave AUVs with lower-precision equipment. During collaborative navigation, the master AUV transmits its own position information to the slave AUVs. The slave AUVs utilize relevant acoustic devices to obtain distance information between themselves and the master AUV. They then combine this information to collaboratively correct their own error information, thereby improving the overall navigation accuracy. Master–slave AUV systems can balance navigation accuracy and equipment cost, making them widely applicable in practical scenarios.

For AUV path planning, there are currently many commonly used methods, such as the A* algorithm [15], genetic algorithms [6,16,17,18], Ant Colony Optimization [7,19,20,21,22], particle swarm optimization [19,23,24], and Differential Evolution [25,26,27]. With the increase in environmental complexity and uncertainty, the requirements for AUV path planning are becoming increasingly high [28,29]. In recent years, with the development of deep neural networks, some self-learning methods, such as ones involving neural networks [30,31] and reinforcement learning [32,33,34], have been introduced into AUV local path planning. Deep reinforcement learning [35,36] combines deep neural networks and reinforcement learning techniques and has also been proposed and applied to AUV local path planning [37].

1.2. Challenges and Innovations

The following issues need to be resolved:

• How to group limited AUVs to complete all tasks with different requirements at each task point while minimizing the overall cost? See Figure 1.

2.

In cases with different requirements at each task point and with limitations on the energy carried by the vessel, there is an issue with respect to how different task points should be allocated to multiple AUV teams to ensure that overall consumption is minimized. See Figure 2.

3.

There is also an issue regarding the sorting of tasks while ensuring that the relevant requirements are met to find the optimal solution, as shown in Figure 3.

4.

In a scenario where all tasks need to be completed, the objective is to minimize overall consumption, as shown in Figure 4.

The proposed algorithm has the following characteristics.

• The proposed algorithm simultaneously addresses the issues of AUV grouping, task allocation, and path planning.
• By using prior experience to generate an initial population and incorporating local search algorithms, the efficiency of the algorithm is significantly improved.
• The algorithm is based on underwater docks, which is in line with the current trend of AUV deployment and retrieval, making it more practical.

2. The Optimization Model and Its Constraints

2.1. Problem Description

There are multiple tasks distributed across different locations within a certain area, as shown in Figure 5. Each task has specific requirements in terms of AUV models and quantities. The underwater dock houses several AUVs of different models, and the tasks require different quantities and types of AUVs to work together in teams. Therefore, it is necessary to group the AUVs, as shown in Figure 6. The onboard energy of the AUVs is limited, and if the energy is not sufficient for covering the energy consumption for traveling to the next location and returning, the AUVs will need to return to the dock for energy replenishment. The objective is to complete all tasks while minimizing overall cost.

The completion of tasks can be divided into three parts: AUV grouping, task allocation, and path planning. AUV grouping involves grouping AUVs of different quantities and types. Task allocation involves assigning different tasks to AUV teams. Path planning involves determining the order in which tasks are completed. Each part is strongly coupled and has a significant impact on the others. The grouping and task allocation are constrained by the availability of AUV quantities and types at each task point, while the path planning is constrained by energy availability. Each part influences the others greatly, and the previous task allocation and path planning decisions have a significant impact on subsequent tasks. To achieve minimal overall consumption, both task allocation and path planning need to be reasonable and coordinated with each other.

2.2. Modeling

Assumption: There are three types of AUVs, namely A, B, and C, in the underwater dock. Each type of AUV has a different payload capacity and is used to fulfill various task requirements. Specifically,

$${\mathrm{AUV}=\{\mathrm{AUV}}_1{, \mathrm{AUV}}_2{, \mathrm{AUV}}_3, \dots {,\mathrm{AUV}}_i\}$$

(1)

In this formula, “i” represents the index of the AUV. The AUVs are typically sorted in the order of A, B, and C models.

According to the actual requirements, tasks are decomposed into different types of task sets:

$${\mathrm{mission}=\{\mathrm{mission}}_1{, \mathrm{mission}}_2, \dots {\mathrm{mission}}_j\}$$

(2)

where j represents the index of the task.

Different types of tasks also require different types and quantities of AUVs. Often, a single task requires the collaboration of multiple AUV models.

$${\mathrm{mission}}_j=\{{\mathrm{AUV}}_{\mathit{j}\mathit{n}1}^{\mathrm{A}},{\mathrm{AUV}}_{\mathit{j}\mathit{n}2}^{\mathrm{B}},{\mathrm{AUV}}_{\mathit{j}\mathit{n}3}^C,\mathit{Mission}\_{\mathit{Energy}}_j,{\mathrm{site}}_{(x,y,z)}^j\}$$

(3)

In the above expression, “j” denotes the task number, “n” represents the required quantity, $Mission\_Energ{y}_j$ indicates the energy consumed for the completion of this task by an AUV. It is assumed that each AUV model consumes the same amount of energy for the same task. ${\mathrm{site}}_{(x,y,z)}^j$ represents the location of the task, with the underwater dock being set as the origin, denoted as ${\mathrm{site}}_{(0,0,0)}^{\mathrm{O}}$.

To determine a set of AUV deployments based on the requirements of task ${\mathrm{mission}}_j$.

$$AUV\_swar{m}_j=\{AU{V}_{i_1},AU{V}_{i_2},AU{V}_{i_3},\text{......}\}$$

(4)

$AUV\_swar{m}_j$ denotes the configuration of the AUV for the j-th mission, while $AU{V}_i$ with i indicates the i-th AUV.

Define the decision variable ${\mathrm{h}}_j$, which represents whether ${\mathrm{mission}}_j$ is completed. A value of 1 indicates that ${\mathrm{mission}}_j$ has been completed; otherwise, it indicates that it has not been completed.

$${\mathrm{h}}_j=\{\begin{array}{l}1,Complete the mission;\hfill \\ 0,Fail to complete the mission.\hfill \end{array}$$

(5)

Each goal includes tasks that must be executed, totaling M tasks; that is,

$${\displaystyle \sum _{j=1}^M{\mathrm{h}}_j=M}$$

(6)

With the prerequisite of completing all tasks, the objective is to minimize costs, primarily focusing on time to achieve the shortest overall duration.

$$\mathrm{Cost}=\min {\displaystyle \sum _{j=1}^{M}h\_\cos t_j}$$

(7)

where $\mathrm{Cos}t$ represents the overall time cost, and $h\_{\cos \mathrm{t}}_j$ denotes the time spent from ${\mathrm{site}}_{(x,y,z)}^{j-1}$ to ${\mathrm{site}}_{(x,y,z)}^j$ to reach and complete the task.

Define the decision variable $x_{\left(i,j\right)}$ to represent whether $missio{n}_j$ is executed. A value of 1 indicates that $missio{n}_j$ is executed for $AU{V}_i$; otherwise, it indicates that it is not executed.

$$x_{(i,j)}=\{\begin{array}{l}1,AU{V}_i\to missio{n}_{j;}\hfill \\ 0,other.\hfill \end{array}$$

(8)

At the same moment, a task can be executed by multiple AUVs; that is,

$${\displaystyle \sum _{i=1}^{\mathrm{n}}{x}_{(i,j)}\ge 1,j=1,2,\dots ,M.}$$

(9)

At the same moment, any given AUV can only execute one task; that is,

$${\displaystyle \sum _{j=1}^{\mathrm{n}}{x}_{(i,j)}\le 1,i=1,2,\dots ,N.}$$

(10)

The same AUV can execute a specific task only once; that is,

$${\displaystyle \sum _{c=1}^C{x}_{(i,j)}\le 1}.$$

(11)

where $c$ represents the number of times an AUV performs the same task.

When a group of AUVs is assigned a set of tasks, each AUV needs to assess its energy status before undertaking the next task. The energy level after completing the subsequent task should be sufficient for supporting its return. It is required that each AUV in the group satisfies this constraint. If any AUV fails to meet this requirement, the entire group must return.

$$E\_\mathrm{r}emai{n}_j^i\ge E{\_\mathrm{path}}_{j\to j+1}^i+E\_missio{n}_{j+1}^i+E\_bac{k}_{j+1}^i, i=1,2,\dots N;j=1,2,\dots M.$$

(12)

where $E\_\mathrm{r}emai{n}_j^i$ represents the remaining energy of AUV i after completing task j, $E{\_\mathrm{path}}_{j\to j+1}^i$ denotes the energy consumed in reaching the next task point, $E\_missio{n}_{j+1}^i$ represents the energy consumed by AUV i in executing task j, and $E\_bac{k}_{j+1}^i$ stands for the energy consumed by AUV i in returning to the underwater dock at task point j + 1.

After completing a task and returning to the underwater dock, the AUV will undergo energy replenishment, data exchange, and maintenance. Assuming different AUV models consume the same amount of time and the duration is fixed, upon completing charging and maintenance, the AUVs will be reorganized based on the task requirements to continue task execution. $\mathrm{Min}T=120 \min$.The time required for this process is at least 120 min, with no specified maximum duration.

$${\mathrm{t}}_{j+1}^{\mathrm{D}}-t_j^A\ge 120$$

(13)

where the unit is in minutes, ${\mathrm{t}}_{j+1}^D$ represents the moment of leaving the dock and commencing the j + 1 task, and ${\mathrm{t}}_j^A$ represents the moment of completing the j task and arriving at the dock. The time spent by the AUV entering and leaving the dock is entirely encompassed within $MinT$.

The successful completion of the task relies on three underlying assumptions. These are as follows:

Assumption 1.

The marine environment is stable, and there is no interference from ocean currents.

Assumption 2.

All target points are reachable, and there are no obstacles blocking the path.

Assumption 3.

AUVs of different models consume the same amount of energy under the same range of navigation.

Integrating the aforementioned constraints, establish a mathematical model for the scheduling of a heterogeneous AUV cluster:

$$\{\begin{array}{l}{\displaystyle \sum _{\mathrm{j}=1}^M{\mathrm{h}}_j=M}\hfill \\ \mathrm{Cos}t=\min {\displaystyle \sum _{j=1}^{M}h\_\cos t_j}\hfill \\ {\displaystyle \sum _{i=1}^{\mathrm{n}}{x}_{(i,j)}\ge 1,j=1,2,\dots ,M.}\hfill \\ {\displaystyle \sum _{\mathrm{j}=1}^{\mathrm{n}}{x}_{(i,j)}\le 1,\mathrm{i}=1,2,\dots ,N.}\hfill \\ {\displaystyle \sum _{\mathrm{c}=1}^{\mathrm{C}}{x}_{(i,j)}\le 1}.\hfill \\ E\_\mathrm{r}emai{n}_j^i\ge E{\_\mathrm{path}}_{j\to j+1}^i+E\_missio{n}_{j+1}^i+E\_bac{k}_{j+1}^i, i=1,2,\dots N;j=1,2,\dots M.\hfill \\ {\mathrm{t}}_{j+1}^{\mathrm{D}}-t_j^A\ge 120\hfill \end{array}$$

(14)

Therefore, each AUV group must be equipped to meet the minimum requirements for each task before returning to the dock for charging after completing the mission, and the charging time for each type of AUV is predetermined. Ultimately, the AUVs need to return to the dock. The goal is to minimize the total number of dispatches of AUV groups and the overall energy consumption.

3. Method

Solving the aforementioned problem poses significant challenges due to the complexity introduced by a large number of variables and linear constraints, especially in the context of large-scale problems. Relying on precise algorithms to address such issues proves to be highly inefficient. There is a need for an efficient algorithm capable of obtaining high-quality solutions within a reasonable timeframe. Therefore, this paper proposes a metaheuristic algorithm called IGLSAPK. The algorithm is an improved genetic algorithm that initially obtains a value through prior knowledge and incorporates a local search algorithm during the iterative process. A flowchart of the algorithm’s process is illustrated in Figure 7.

The approach begins by considering the demands of each task point as a formation plan for AUVs, encoding them together with the task points to create a new coding format. An initial population is generated using a total group generation algorithm that incorporates prior knowledge, facilitating a more direct and efficient algorithm. Additionally, a penalty factor is introduced, doubling the penalty for chromosomes violating the constraints related to AUV types, quantity, and onboard energy limits. This accelerates the elimination of chromosomes that violate constraints, thereby enhancing efficiency. To prevent the algorithm from converging to local optima, a local search algorithm is incorporated into the program, significantly improving convergence speed. As a result, a relatively optimal solution is achieved after only 100 iterations. Further details on specific aspects will be discussed in the following sections.

3.1. Chromosome Encoding

Using a genetic algorithm to solve the problem requires analyzing the problem and designing a chromosome encoding method. Chromosome encoding is a crucial task as it determines the feasibility and efficiency of the algorithm. The chromosome is composed of task points and formation plans. The allocation plan is generated from the demands of task points, so the number of task points is the same as the number of allocation plans.

Initially, 100 task points will be randomly generated, each containing three-dimensional coordinate information and AUV demand information, as shown in Figure 8.

Using the bubble sort method to sort the task points, first, sort the “sum” in descending order. When two task points have the same “sum”, compare their A-AUV demand. If the A-AUV demand is also the same, compare their B-AUV demand. If they are still the same, compare their C-AUV demand. If the C-AUV demand is also the same, it means that the AUV demands of the two task points are identical, and their order remains unchanged, as shown in Figure 9. After sorting, assign numbers to the task points in sequence, totaling 100, with numbers ranging from 1 to 100.

Each row represents the data for a task point, including three-dimensional coordinate information and the quantity and type demands of AUVs.

For the AUV scheduling problem with N task points, the following approach is taken: first, sort the N task points and then consider the demands of these N task points as a formation plan. Subsequently, assign numbers from 1 to N for the task points and from N + 1 to 2N for the formation plans. In this scheme, the first N genes in the chromosome represent the task points, and the subsequent N genes represent the formation plans. The order of the first N genes indicates the sequence in which the task points are executed and represents the path of the AUV formation, as shown in Figure 10.

Each task point contains three-dimensional coordinate information and specifications regarding the AUV types and quantities required for that task point.

In terms of AUV formation, formations will be generated based on the demands of task points. Normally, there would be $4^3-1$ possible formation plans; however, in actual scenarios, each formation plan may not necessarily be used only once. Therefore, based on the AUV demands of each task point, corresponding formation plans are generated and labeled accordingly. As mentioned earlier, they have been sorted, so the labeling starts with 101 for the demands of the first task point and continues in sequence. This results in a total of 100 formation plans. As shown in Figure 11, scheduling plans can be generated based on the formation plans.

3.2. Data Preprocessing

For computational convenience, the data of the task points need to be processed to obtain a $100\times 100$ matrix. In this matrix, columns represent 100 formation plans, and rows represent the demands of 100 task points. If a formation plan satisfies the demands of a task point, the corresponding entry is 1; otherwise, it is 0. Since the demands of the 100 task points correspond to the respective formation plans, the matrix forms a main diagonal of 1 s, indicating whether the formation plans satisfy the task points’ requirements. This information is stored in a matrix denoted as WORK, as shown in Equation (14).

$$WORK={\left(\begin{array}{l}1 1 1 1 1 1 1 1 \cdots 1 1 1 1 1 1 1 1\\ 1 1 1 1 1 1 1 1 \cdots 1 1 1 1 1 1 1 1\\ 0 0 1 1 0 0 0 0 \cdots 1 1 1 1 1 1 1 1\\ 0 0 1 1 0 0 0 0 \cdots 1 1 1 1 1 1 1 1\\ 0 0 0 0 1 1 1 1 \cdots 1 1 1 1 1 1 1 1\\ 0 0 0 0 1 1 1 1 \cdots 1 1 1 1 1 1 1 1\\ 0 0 0 0 1 1 1 1 \cdots 1 1 1 1 1 1 1 1\\ 0 0 0 0 1 1 1 1 \cdots 1 1 1 1 1 1 1 1\\ ⋮⋮⋮ \\ 0 0 0 0 0 0 0 0 \cdots 1 1 1 0 0 0 0 1\\ 0 0 0 0 0 0 0 0 \cdots 1 1 1 0 0 0 0 1\\ 0 0 0 0 0 0 0 0 \cdots 1 1 1 0 0 0 0 1\\ 0 0 0 0 0 0 0 0 \cdots 0 0 0 1 1 1 0 0\\ 0 0 0 0 0 0 0 0 \cdots 0 0 0 1 1 1 0 0\\ 0 0 0 0 0 0 0 0 \cdots 0 0 0 1 1 1 0 0\\ 0 0 0 0 0 0 0 0 \cdots 0 0 0 0 0 0 1 0\\ 0 0 0 0 0 0 0 0 \cdots 0 0 0 0 0 0 0 1\end{array}\right)}_{100\times 100}$$

(15)

Given the coordinates of each task point, the distances between each pair of task points can be determined, including the dock, resulting in a total of 101 coordinate points. As shown in Equation (15), the matrix is a square matrix of size 101 × 101, where the main diagonal is entirely composed of 0 s. Rows and columns correspond to the 101 coordinate points, and the values represent the distances between them. If we disregard the influence of ocean currents, these distances can be considered as the energy consumption for movement. In practical marine environments, ocean currents are often present. Thus, to account for their impact, the data below can be modified according to actual ocean currents or multiplied by relevant coefficients. However, this paper does not consider the influence. of ocean currents at this time.

$$\mathrm{OCEAN}={\left(\begin{array}{ccccccccc}0& 1208.492& 1905.632& 1825.795& \cdots & 1850.779& 1902.151& 1962.931& 1434.964\\ 1208.492& 0& 1742.127& 1270.379& \cdots & 1269.796& 2229.182& 1508.438& 1313.938\\ 1905.632& 1742.127& 0& 639.5139& \cdots & 779.0372& 1379.095& 1248.187& 489.1646\\ 1825.795& 1270.379& 639.5139& 0& \cdots & 334.797& 1703.106& 1024.552& 575.2999\\ ⋮& & & & ⋮& & & & ⋮\\ 1850.779& 1269.796& 779.0372& 334.797& \cdots & 0& 1554.455& 697.1349& 703.0057\\ 1902.151& 2229.182& 1379.095& 1703.106& \cdots & 1554.455& 0& 1290.498& 1352.749\\ 1962.931& 1508.438& 1248.187& 1024.552& \cdots & 697.1349& 1290.498& 0& 1155.109\\ 1434.964& 1313.938& 489.1646& 575.2999& \cdots & 703.0057& 1352.749& 1155.109& 0\end{array}\right)}_{101\times 101}$$

(16)

3.3. Determining the Initial Population

According to the constraints imposed by the limitations and leveraging prior knowledge, the initial population is generated, as shown in Algorithm 1. When the number and types of AUVs in a formation are greater than or equal to the demands of a task point, the task associated with that point can be executed. If the AUV count and types are less than the task point’s demands, the task cannot be executed. Therefore, when forming AUV formations, priority should be given to task points with higher AUV counts and diverse AUV types. The AUV formation is established based on the demands of the task points. The first step involves forming AUV formations to fulfill tasks associated with high-demand task points, followed by randomly completing tasks associated with this formation. The remaining AUVs are then grouped to maximize the completion of tasks associated with other points. This approach involves sorting the formation plans according to the allocation scheme and sequentially completing tasks associated with each task point.

Algorithm 1 Initial population generation algorithm based on prior knowledge
Input: Coordinates and demands of task points(newsorted_data), AUV-carried energy(cap), Number of A-type AUVs(AUV_a), Number of A-type AUVs(AUV_b), Number of A-type AUVs(AUV_c), Distance between task points(dist) Output: Initial population(myinit_vc) Set: c ← 0//Task counter, m ← 0//AUV task group counter
1:	while any task in newsorted_data is not equal to 0
2:	c ← c + 1//new round of task scheduling
3:	m ← 0//clear AUV task group
4:	cap ← 10,000//Initialize the energy upper limit
5:	residues ← [AUV_a, AUV_b, AUV_c]//Remaining quantity of AUVs
6:	for i ← 1 to size(newsorted_data) do
7:	if newsorted_data[i] != 0 then
8:	if residues ≥ newsorted_data[i] then
9:	m ← m + 1//Create a new task group
10:	route ← []
11:	for j ← 1 to size(newsorted_data) do
12:	if newsorted_data [i,j] != 0 then
13:	append j to route
14:	end if
15:	end for
16:	route ← randomize(route)
17:	new_route ← [i, route]
18:	for k ← 1 to size(new_route) do//Check if cap is remaining
19:	if cap >= required then
20:	update cap, cell_route
21:	zero newsorted_data [k]//Delete this task point
22:	else
23:	save cell_route to myinit_vc
24:	break
25:	end if
26:	end for
27:	end if
28:	end if
29:	end for
30:	residues ← residues—newsorted_data
31:	end while
32:	return myinit_vc

3.4. Fitness Function

In genetic algorithms, fitness is the primary indicator describing the performance of an individual. Individuals are ranked based on the magnitude of their fitness, and the fitness function is the driving force behind genetic algorithm operations [38]. For maximization problems, individuals with higher fitness values are preferred, while for minimization problems, those with lower fitness values are favored. The selection of the fitness function directly affects the convergence speed of the genetic algorithm and its ability to find the optimal solution. From a biological perspective, fitness is analogous to the survival capability in the process of “survival of the fittest”, playing a crucial role in the genetic process. Establishing a mapping relationship between the objective function of the optimization problem and the fitness of individuals enables the optimization of the objective function during the population evolution process.

$$\mathrm{Fit}\left(\mathrm{x}\right)=\frac{1}{f(x)}$$

(17)

In this context, $\mathrm{Fit}\left(\mathrm{x}\right)$ represents the fitness of an individual, and $f(x)$ denotes the total consumption after completing tasks where a larger value of $f(x)$ corresponds to lower fitness. In the algorithm proposed in this paper, fitness is defined based on the total consumption involved in the completion of all tasks. After completing all tasks, the lower the resource consumption for each task, the higher the fitness. Therefore, the algorithm aims to minimize the consumption for each task and minimize the overall number of task executions.

3.5. Penalty Factor

The introduction of a “penalty factor” enables the algorithm to search for solutions that meet the problem requirements more efficiently [39]. When the chromosome encoding violates the problem’s constraints, the penalty factor reduces the probability of its selection, as shown in Algorithm 2. This encourages the algorithm to converge more quickly and obtain an optimal solution by penalizing solutions that do not adhere to the specified constraints.

$$\mathrm{P}=N\_\mathrm{ec}\times alpha+N\_tc\times belta+N\_qc\times cfnum$$

(18)

where $N\_\mathrm{ec}$ is the count of violations against the vessel’s energy constraints, $alpha$ is the penalty function coefficient for violating the vessel’s energy constraints, $N\_tc$ is the count of violations against AUV type constraints, $belta$ is the penalty function coefficient for violating AUV type constraints, $N\_qc$ is the count of violations against AUV quantity constraints, and $cfnum$ is the penalty function coefficient for violating AUV quantity constraints.

Algorithm 2 Fitness algorithm with penalty factor
input: Chromosome(chrom),Shipboard battery capacity(cap) output: Chromosome Cost(costF),Penalty function coefficient for violated battery constraints(alpha), Penalty function coefficient for violated AUV type constraints(belta), Penalty function coefficient for violated AUV quantity constraints(cfnum) set: numcost = 0, cisu = 1, count = 0, sumcap = 0, alpha = 51,000, belta = 51,000, cfnum = 5000
1:	violate_num = 0//Reset the count of violated battery constraints, violate_cus = 0//Reset the count of violated AUV type constraints
2:	Find the indices location0 in chrom where values are greater than 100
3:	for i = 1 to length(location0)
4:	if i = 1
5:	route = chrom(1:location0(i))//Extract the path
6:	xinghao = chrom(location0(i))//Record the AUV index
7:	else
8:	route = chrom(location0(i − 1):location0(i))
9:	xinghao = chrom(location0(i))
10:	end if
11:	count = count + 1
12:	VC{count} = route//Record the path
13:	VC{count} = xinghao//Record the AUV serial number
14:	end for
15:	for h1 = 1 to 100
16:	if VC{h1} is not empty
17:	l1 = Path of VC{h1}
18:	Check each task point in l1 one by one:
19:	If there is a violation of the battery constraint, increment the violate_num by 1 and record it in numcos.
20:	If the constraint is satisfied, accumulate it in sumcap
21:	end if
22:	end for
23:	for h2 = 1 to 100
24:	if VC{h2} is not empty
25:	Check if the task points on the path satisfy the AUV type constraints recorded in VC{h2}
26:	If violated, increment the violate_cus counter
27:	end if
28:	end for
29:	Initialize the AUV usage count to 0
30:	for h3 = 1 to 100
31:	if VC{h3} is not empty
32:	Attempt to subtract the corresponding AUV usage count for this path scheme
33:	If not exceeding the maximum usage count, then subtract accordingly
34:	If exceeding the maximum usage count, then reset the AUV usage count to zero before subtracting
35:	end if
36:	end for
37:	costF = violate_num × alpha + violate_cus × belta + cisu × cfnum + numcost × 10 + sumcap
38:	costF = costF + 10,000

3.6. Crossover Operation

Genetic algorithms maintain population diversity through crossover operators, where chromosomes exchange portions of genes to form two new individuals. There are various crossover operators designed for different optimization problems [40].

Currently, the standard crossover operators commonly used to address sorting and scheduling problems include the Heuristic Crossover, Partially Mapped Crossover (PMX), Edge Recombination Crossover (EER), Ordered Crossover (OX), Uniform Order-Based Crossover (UOX), and Cycle Crossover (CX).

In Ordered Crossover (OX), random start and end positions are selected in both parent chromosomes. The genes within the chosen region of parent chromosome 1 are copied to the same position in offspring 1. Subsequently, the missing genes in offspring 1 are sequentially filled in from parent chromosome 2. The other offspring is obtained in a similar manner. Unlike PMX, OX does not require conflict detection, as shown in Figure 12.

3.7. Mutation Operation

The mutation probability is denoted as $P_e$. It is set so that the first gene of each chromosome does not undergo mutation. For each other gene $i$, a random floating-point number $r_i$ is generated in the range of 0 to 1. If $r_i$ is less than $P_e$, the gene is placed in the mutation gene pool $G$ and removed from the chromosome. Otherwise, the gene remains unchanged. Subsequently, based on the “trial allocation method”, genes from $G$ are randomly inserted one by one into the chromosome.

3.8. Local Search Algorithm

Due to the drawbacks of the crossover operator in genetic algorithms, where the crossover rate results in randomness in chromosome crossover and cannot guarantee high-quality offspring, it is necessary to select appropriate crossover partners for chromosomes. Once parents are selected, the best crossover scheme is chosen for each pair of parents to ensure the generation of the best possible offspring. By combining local optimization algorithms with genetic algorithms, the quality of solutions is progressively improved, accelerating the convergence speed.

4. Simulation Experiment

4.1. Experimental Setup

To validate the effectiveness of the Improved Genetic Local Search Algorithm with Prior Knowledge (IGLSAPK) proposed in this paper, a simulation experiment was conducted. After 100 iterations of the program, the overall optimal solution was calculated. The parameters for the genetic algorithm were set as follows: a population size of 100, 100 iterations, a crossover probability of 0.9, a mutation probability of 0.05, and a generation gap of 0.9. The chromosome length was set to 200. The decision to iterate 100 times was based on the observation that increasing the iteration count beyond 100 resulted in minimal changes in the optimal value. Considering computational time costs, the iteration count was set to 100. The chromosome length of 200 corresponds to 100 task points and 100 allocation schemes.

To compare the performance of the proposed algorithm, two other algorithms were used for comparison: the Improved Genetic Local Search Algorithm (IGLSA) and the Improved Genetic Algorithm with Priori Knowledge (IGAPK). IGLSA does not have prior knowledge and initialization population algorithms, while IGAPK does not include a local search algorithm, unlike IGLSAPK. The parameters are set the same as before, with 100 iterations.

4.2. Experimental Simulation and Result Analysis

Firstly, we validated the proposed Improved Genetic Local Search Algorithm with Prior Knowledge (IGLSAPK). Within a specified region, 100 task points were randomly generated, and for each task point, task requirements were generated randomly. Each task point set a limit for each of the three types of AUVs, ensuring that the limit for each type could not exceed three vessels. Through simulation experiments, an optimal deployment scheme that minimizes the number of deployments while optimizing overall efficiency was obtained. The final optimal paths meet the requirements of the task points while minimizing overall consumption. The total number of deployments is 5, as shown in the table below

Table 1. Illustrative table of AUV group paths.

Mission	Group	Route	Scheme Number	Scheme
Mission1	Group1	0 → 4 → 64 → 66 → 8 → 94 → 14 → 69 → 24 → 2 → 25 → 100 → 43 → 49 → 95 → 28 → 29 → 42 → 52 → 15 → 0	102	A3B3C3
Mission2	Group1	0 → 45 → 87 → 98 → 90 → 61 → 31 → 73 → 62 → 97 → 47 → 46 → 63 → 13 → 71 → 0	112	A2B2C3
	Group2	0 → 83 → 40 → 70 → 56 → 50 → 37 → 3 → 38 → 33 → 57 → 9 → 17 → 68 → 89 → 86 → 0	103	A3B3C2
Mission3	Group1	0 → 39 → 75 → 84 → 99 → 58 → 92 → 77 → 36 → 81 → 55 → 0	125	A2B2C2
	Group2	0 → 32 → 34 → 54 → 0	108	A3B2C3
Mission4	Group1	0 → 74 → 80 → 72 → 5 → 59 → 18 → 53 → 10 → 6 → 19 → 51 → 65 → 85 → 44 → 67 → 20 → 48 → 76 → 91 → 93 → 0	105	A3B2C3
Mission5	Group1	0 → 23 → 60 → 11 → 26 → 1 → 7 → 21 → 41 → 88 → 79 → 22 → 96 → 30 → 27 → 35 → 12 → 82 → 16 → 78 → 0	101	A3B3C3

. Notably, during the second and third tasks, two groups are deployed to accomplish the mission.

The overall path is illustrated in Figure 13 (below). It can be observed that, based on the requirements of each task point, all task points are traversed through 5 missions. IGLSAPK simultaneously accomplishes the scheduling and path planning for AUVs, ensuring minimum overall energy consumption. In large-scale problems, precise algorithms often require extensive computation time, and with multiple constraints, the computational workload becomes significantly burdensome, often hindering the rapid acquisition of effective solutions. In the presence of constraints such as AUV-type limitations, quantity restrictions, and on-board energy limitations, where each constraint is coupled with others, the difficulty of solving the problem sharply increases, leading to an exceptionally large computational workload. Heuristic algorithms such as IGLSAPK can rapidly obtain high-quality feasible solutions under these conditions.

Figure 14 depicts the genetic evolution curve over 100 iterations, where the horizontal axis represents the number of iterations, and the vertical axis represents the optimal value for each iteration. With the presence of penalty factors, the initial solutions exhibit higher energy consumption. As the chromosomes undergo iterations, the solutions gradually approach optimality, and around the 100th iteration, the convergence tends to plateau, reaching a relative optimum.

5. Comparative Experiment

To further validate the effectiveness of the proposed IGLSAPK, simulations were conducted separately for IGLSA and IGAPK. To ensure fairness in the experiments, the parameters and initial data were kept consistent with IGLSAPK, and an iteration count of 100 was used. After the simulation experiments, the data were compared and plotted on a single graph (Figure 15).

It can be observed that IGLSA, lacking prior knowledge in generating the initial population and with the presence of penalty factors, started with a very high optimal value. With the assistance of local search algorithms, the optimal value decreased rapidly after multiple iterations. However, it required more iterations to achieve a value close to IGLSAPK. On the other hand, IGAPK, which is without a local search algorithm but benefits from prior knowledge, started with the same optimal value as IGLSAPK. However, the descent of the optimal value was much slower, requiring more iterations to approach the values obtained by IGLSAPK. Additionally, IGAPK was more prone to getting stuck in local optima. Despite this, each iteration ran relatively faster compared to IGLSAPK.

Table 2. A table comparing the optimal values for the IGLSAPK, IGLSA, and IGAPK algorithms at the 25th, 50th, 75th, and 100th iterations.

Algorithm	Number of Iterations
	25	50	75	100
IGLSAPK	106,482.50	85,298.34	82,935.19	82,768.82
IGLSA	1,250,001.21	1,080,032.35	530,031.92	200,031.78
IGAPK	173,131.74	170,121.81	150,023.62	135,021.43

reveals that the optimal values obtained with the initial population from prior knowledge were reduced by 91%, 92%, 84%, and 58% in the 25th, 50th, 75th, and 100th iterations, respectively, compared to IGLSA. It indicates that in the early stages where optimal values are relatively small, the efficiency of the solution process is significantly improved. By introducing the local search algorithm, the optimal values decreased by 38%, 49%, 44%, and 38%, respectively, compared to IGAPK. This suggests that the local search algorithm facilitates the rapid convergence of optimal values, greatly enhancing the efficiency of the solution process.

6. Conclusions

This paper addresses the problem of AUV scheduling in underwater docks and proposes the IGLSAPK algorithm. The algorithm tackles the coupled challenges of grouping, task assignment, and path planning for a heterogeneous AUV fleet under complex constraints. Initially, the algorithm introduces a method to convert task point requirements into AUV formation plans. By encoding AUV task points and formation plans simultaneously, the genetic algorithm efficiently addresses both AUV grouping and task assignment. To enhance the algorithm’s efficiency, a knowledge-based initialization algorithm was incorporated, enabling the rapid attainment of low optimal values in the initial iterations. To further improve efficiency and prevent the algorithm from getting trapped in local optima, an enhanced local search algorithm was introduced, significantly boosting the algorithm’s performance. The results of our comparative experiments demonstrate that IGLSAPK outperforms existing genetic algorithms, substantially increasing efficiency. The proposed model is more applicable to real-world scenarios, and the introduced OCEAN matrix can be adjusted based on actual ocean currents, making it more adaptable to real marine environments.

In future research, we will study the AUV swarm scheduling algorithm for multiple underwater docks and investigate the collaborative scheduling algorithm for AUV swarm between surface mother ships and underwater docks.