Mission Planning Method for Dense Area Target Observation Based on Clustering Agile Satellites

Abstract

To address the mission planning challenge for agile satellites in dense point target observation, a clustering strategy based on an ant colony algorithm and a heuristic simulated genetic annealing optimization algorithm are proposed. First, the imaging observation process of agile satellites is analyzed, and an improved ant colony algorithm is employed to optimize the clustering of observation tasks, enabling the satellites to complete more observation tasks efficiently with a more stable attitude. Second, to solve for the optimal group target observation sequence and achieve higher total observation benefits, a task planning model based on multi-target observation benefits and attitude maneuver energy consumption is established, considering the visible time windows of targets and the time constraints between adjacent targets. To overcome the drawbacks of traditional simulated annealing and genetic algorithms, which are prone to local optimal solution and a slow convergence speed, a novel Simulated Genetic Annealing Algorithm is designed while optimizing the sum of target observation weights and yaw angles while also accounting for factors such as target visibility windows and satellite attitude transition times between targets. Ultimately, the feasibility and efficiency of the proposed algorithm are substantiated by comparing its performance against traditional heuristic optimization algorithms using a dataset comprising large-scale dense ground targets.

1. Introduction

With the rapid advancement of aerospace and satellite technology, agile satellites have emerged as a new type of earth observation satellite. Characterized by their low cost, short development cycle, strong attitude maneuverability, and high adjustment precision, they have become the focus of development for major spacefaring nations. The expanding application domains of agile satellite and the rapidly increasing demands of satellite users have made it crucial to explore how to maximize the operational efficiency of satellite and meet the needs of a large number of users. This has become a significant research problem in the field of mission planning [1].

Agile satellites operate in the orbit of the earth at a high speed compared to traditional optical satellites; agile satellites rely on sensitive attitude control systems to achieve yaw and obtain image information within a certain area near the ground track of the satellite. A schematic diagram of the angle range for agile satellite attitude observation is shown in Figure 1.

In actual mission scenarios, when a satellite conducts imaging reconnaissance, the camera has a certain viewing angle and generates an observation strip of a certain width on the ground during transportation. If multiple adjacent targets satisfy certain observation angle and time constraints, the satellite can adjust the camera’s yaw angle so that multiple targets are included in the same observation strip. Clustering multiple observation missions into one observation mission is called the satellite mission clustering method. Imaging satellite task clustering increases the number of satellite observation missions each time and achieves the purpose of rationally organizing satellite resources.

When a large number of target points exist, multiple on/off operations and attitude maneuvers are required to meet the observation conditions. In addition, there are mutually exclusive situations among tasks [2]. For example, there may be a conflict in the observation time between two tasks, or the time interval between tasks may be too short to complete attitude conversion, which results in some targets being unobservable. Traditional observation methods are characterized by low observation efficiency and high energy consumption. Clustering tasks that meet certain conditions enable multiple tasks to be completed in one observation, reduce the number of on/off operations and imaging satellite attitude maneuvers, and thus complete observation tasks more efficiently [3]. Kim [4] established a cluster partitioning model for single-star scheduling problems and provided relevant solving algorithms. Wang established a task-merging graph model [5] and proposed a task-merging algorithm based on clique partitioning (CPTM). Reference [6] proposed a dynamic clustering strategy and adopted an adaptive simulated annealing scheduling algorithm in the subsequent task scheduling stage to achieve the interaction between clustering and scheduling. Reference [7] divided the multi-point observation problem into two stages. Firstly, the minimum cluster partitioning algorithm was used to cluster the targets that meet the field of view constraints. Then, a directed acyclic graph model was established, and an improved ant colony algorithm was used to generate the optimal path. Reference [8] studied the emergency task clustering and planning problem of AEOS. Yanbin Zhao [9] clustered the densely distributed point targets according to their distance and direction and used the Tabu algorithm to generate local observation paths, significantly reducing the planning time while ensuring optimal solution quality. Yanjie Song [10] utilized the k-means clustering method and proposed a clustering-based genetic algorithm to solve the satellite ranging scheduling problem. By combining clustering with a genetic algorithm, the adaptability of the algorithm was improved. Yixin Huang [11] proposed an improved graph-based minimum clustering algorithm. This algorithm takes task priority and the observation yaw angle under constraint conditions into consideration and uses the processed clustering tasks as inputs for subsequent algorithms.

In this article, the first step in earth observation satellite missions is the preprocessing of task clustering. The second step is mission planning after clustering, where most studies employ intelligent optimization algorithms for mission planning.

Sarkheyli [12] designed a Tabu Search Algorithm based on graph coloring models. These are only applicable to the situation where a single satellite passes through once, without considering the situation where there are multiple regional targets to be observed, and without considering scenarios such as overlapping. Wang P designed task flexibility factors based on the time window length, task duration, and task weight for the integrated scheduling problem of satellite observation and data transmission. Task backtracking factors were designed based on the conflict set of tasks. Based on the idea of conflict avoidance, a heuristic algorithm considering priority and supplemented by limited backtracking was proposed [13,14]. Sun proposed a satellite scheduling method based on a genetic algorithm, which designed the fitness function of the scheme with task execution benefits, task incompleteness penalties, and task execution costs, but did not provide a method for adjusting the scheme after cross mutation [15]. He R proposed a fast simulated annealing algorithm, which constructs various neighborhood structures such as insertion, synthesis, deletion, and decomposition for task features and uses random perturbations, restarts, and rearrangements to escape local optima [16]. Makarov [17] explored a quantum-inspired genetic algorithm for satellite mission planning problems using data from the SPOT5 satellite and a quantum model to illustrate the problem while considering constraints such as image requests and capacity. Rainjonneau [18] used a set of quantum algorithms for problem solving, and experiments showed that hybrid quantum-enhanced reinforcement learning can significantly improve work efficiency. Wang, X [19] proposed a hybrid heuristic method involving column generation and simulated annealing to solve the agile satellite scheduling problem under cloud coverage uncertainty. Chao Han [20] proposed an improved simulated annealing-based heuristic algorithm with a fast insertion strategy to solve satellite scheduling problems under cloud coverage uncertainty. Jiawei Zhang [21] designed encoding and decoding ideas that match requests with satellite resources and designed chromosome lengths according to actual problems using an improved genetic algorithm for problem solving. Ming Chen [22] proposed an end-to-end model framework based on deep learning, which can be used to train observation sequences. The experimental results show that this method has higher performance and robustness. Yanjie Song [23] combined genetic algorithms with Q-learning methods to make the evolution of each individual dependent on the agent’s decisions, optimizing population search by designing selection evolution operators. Junwei Ou [24] proposed a deep reinforcement learning method to solve the satellites’ distance scheduling problem; this method decomposes the problem into two core problems and establishes an allocation process to effectively handle the problem. Xueying Yang [25] proposed a multi-objective evolutionary algorithm for multi-satellite dynamic task planning and established a knowledge transfer strategy for multi-objective evolutionary algorithm to accelerate the convergence process of the population. Yu Chen [26] combined the PSO (Particle Swarm Optimization) algorithm with the GA (genetic algorithm) and used a hybrid algorithm to improve the observation efficiency. Penghun Li [27] resolved conflicts by establishing relationships between tasks and resources and performed clustering before task planning based on conflict rules, ultimately leading to task planning based on clustering. Yongming He [28] proposed the idea of edge computing, where the satellite corresponds to the edge node and the central node corresponds to the center of the satellite’s operating system, and used a heuristic algorithm to plan tasks according to the task density. Jun Long [29] designed a multi-satellite collaborative task planning algorithm based on collaborative evolution and established a multi-satellite collaborative task planning architecture. Finally, the advantages of the proposed architecture and algorithm were verified through simulation experiments. Shuo Wang [30] combined genetic algorithms with pseudo spectral processes and collaborative concepts for the task planning process of a single satellite, ultimately obtaining the observation sequence with the maximum number of observations and the least energy consumption.

Intelligent search algorithms are highly versatile. Intelligent optimization algorithms are optimization methods developed by mimicking natural or social behaviors, such as particle swarm optimization and genetic algorithms. These algorithms possess stronger global search capabilities and are generally used to solve complex global optimization problems. However, a single intelligent search algorithm has the drawback of low search efficiency, and improving a single algorithm also has its limitations. To enhance the feasibility of the algorithm, this paper adopts a hybrid optimization algorithm that combines genetic algorithms and simulated annealing algorithms (SA-GA). By using the strengths of each individual algorithm to expand the search domain, this approach aims to maximize observation benefits. Experimental validation is carried out under conditions while considering the satellite’s visible window, mission observation time, memory capacity, and energy constraints.

2. Problem Statement

The satellite imaging mission planning problem studied in this paper can be described as follows: For a certain orbit of the satellite, there are numerous targets that satisfy the observation time and observation angle constraints. The targets that satisfy the clustering constraints are grouped together to reduce the number of tasks. An observation plan is formulated for the clustered target observation sequence with the goals of maximizing the observation benefit and minimizing energy consumption during the satellite’s yaw maneuver. By analyzing the characteristics of the problem, a constraint satisfaction model for satellite mission planning is established. The definitions of the model parameters, constraints, and objective functions are shown in Table 1.

2.1. Model Parameters and Definitions

As shown in the table, N represents the number of task sets that meet the clustering conditions after clustering. Each group contains multiple point targets after clustering, meaning that a group consists of multiple point targets that satisfy the clustering conditions after partitioning.

2.2. Decision Variables

The definitions of decision variables $c_i$ and $F_{ij}$ are as follows:

(1)$c_i=\left\{\begin{array}{c}1,c_i\mathrm{is}\mathrm{observed}\\ 0,otherwise\end{array}\right.$

(2)$F_{ij}=\left\{\begin{array}{c}1,c_j\mathrm{is}\mathrm{the}\mathrm{subsequent}\mathrm{observation}\mathrm{task}\mathrm{of}{c}_i\\ 0,otherwise\end{array}\right.$

2.3. Restrictions

The task planning problem for observing dense area point targets is a complex combinatorial constraint problem, and the constraints in this article are as follows:

• 1.. Time window constraints

If the target point $c_i$ is observed by a satellite, the duration interval of the satellite’s observation of it must be a subset of the time window during which the satellite is visible to it.

The time window constraints for each group target observation time are as follows:

(3)$c_i=1,T_{li}\ge t_{si}\ge T_{ei}$

• 2.. Time constraints for continuous observation

After $c_j,$ the agile observation satellite, finishes its observation, $c_i$ must complete the attitude maneuver before the end of the time window to observe $c_j$

(4)$F_{ij}=1,t_{sj}⩾t_{si}+t_{rij}+d_{ci}$

• 3.. Energy constraint

The energy consumed by a satellite during operation must not exceed its energy storage limit.

(5)${\sum }_{i=1}^N{A}_i<\mathrm{A} (\mathrm{Total} \mathrm{amount} \mathrm{of} \mathrm{energy})$

• 4.. Memory capacity constraint

The memory capacity of onboard equipment during operation does not exceed its upper limit.

(6)${\sum }_{i=1}^N{B}_i<\mathrm{B} (\mathrm{Total} \mathrm{amount} \mathrm{of} \mathrm{memory})$

2.4. Optimization Function

(7) $\mathrm{Max} {\sum }_{i=1}^N{\sum }_{j=1}^N(W_i-t_{rij})$

This article transforms the multi-objective function into a single objective by taking the benefits generated by observing $c_i$ and the attitude maneuvering the energy consumption of the satellite from observing $c_i$ to observing $c_j$ as optimization objectives. In this paper, we consider the observation income and the energy consumption of the satellite to achieve yaw and obtain a scheme with high income and low energy consumption.

3. Clique Partition Target Clustering Algorithm Based on Ant Colony Algorithm

3.1. Establishment of Observation Task Map

Task clustering reduces the number of satellite observation ground tasks, as shown in Figure 2. The blue areas represent observable point targets, and the red rectangles represent point targets clustered after satisfying certain clustering conditions. Clustering point targets that satisfy specific clustering conditions can reduce the number of satellite attitude maneuvers and imaging times, thus completing observation tasks more efficiently.

Clustering multiple tasks into one task requires satisfying the observation time and observation angle constraints.

Assume that each start-up time of the satellite is Δt, the field-of-view angle is Δg, the time windows of task i and task j within the satellite’s accessible time are [$t_{ei}$,$t_{li}$] and [$t_{ej}$,$t_{lj}$], and the observation angles are $s_i$ and $s_j$ if the following constraints are satisfied:

(8)$\max \{t_{li},t_{lj}\}-\min \{t_{ei},t_{ej}\}\le \Delta \mathrm{t}$

(9)$|s_j-s_i|<=\Delta \mathrm{g}$

If tasks i and j satisfy the clustering constraint, they are connected by an edge $E_j$, and E (GK) represents the set of all edges.

When multiple tasks can form a cluster, by analyzing the task clustering constraints of two point target tasks, the clustering constraints of any number of point target tasks can be obtained. Suppose there are w (w ∈ N) point target tasks if the following conditions are satisfied:

(10)$\max \{t_{l1},t_{l2},\dots ,t_{lw}\}-\min \{t_{e1},t_{e2},\dots ,t_{ew}\}\le \Delta \mathrm{t}$

(11)$\max \{s_1,s_2,\dots ,s_w\}-\min \{s_1,s_2,\dots ,s_w\}<=\Delta \mathrm{g}$

Then, these w point tasks satisfy the task clustering constraints. The resulting clusters have the following properties:

If there are w point target tasks that satisfy the task clustering constraints of the $c_i$ satellite in a certain orbital circle, then the start time $T_{ei}$, end time $T_{li}$, and observation angle of the clustering task $S_i$ are

(12)$T_{ei}=\min \{t_{e1},t_{e2},\dots ,t_{ew}\}$

(13)$T_{li}=\max \{t_{l1},t_{l2},\dots ,t_{lw}\}$

(14)$S_i={\displaystyle \frac{\mathrm{m}\mathrm{a}\mathrm{x}\left\{s_1,s_2,\dots ,s_w\right\}-\mathrm{m}\mathrm{i}\mathrm{n}\{s_1,s_2,\dots ,s_w\}}{2}}$

The start time of the clustering task is the earliest start time of the w point target tasks, and the end time of the clustering task is the latest end time of the w point target tasks. Since the target area of the clustering task covers the w point target tasks, the observation angle of the clustering task is the average of the maximum observation angle and the minimum observation angle in the w point target tasks.

3.2. Task Clustering Based on Clique Division

G = (V, E) is constructed according to whether the targets meet the clustering conditions. V represents the point target task set, and E represents the edge set. If any two point target tasks satisfy the clustering condition, they will be connected.

After the cluster graph is constructed, it needs to be “split”, which is essentially the problem of the division of regiments in graph theory, as shown in Figure 3.

Most studies employ a clique partitioning method based on the vertex degree. The degree of a vertex is defined as the number of vertices in the graph that are connected to it by edges. The steps are as follows:

1. Traverse all points in the graph and calculate the degree of each vertex.

2. Select vertex C with the maximum degree to be added to the clustering result. If the vertex is not unique, select the point with the largest weight and delete it from V.

3. Search for all points in V that are connected to C by edges. If there are no such points, then construct C. All vertices in C are deleted from V, and C is cleared. If none exist, go to step 4.

4. If multiple vertices in V are connected to C, select the one with the largest degree. If there are multiple vertices with the largest degree, select the one with the largest weight and add it to C, and delete the point from V. Repeat step 3. If only one vertex is connected to C, add the point to C and delete it from V.

Clique partition is a classic NPC problem. The necessary and sufficient condition for each point to form a clique is that any two points are connected. To realize the clique partition of the graph, this paper designs a clique partition algorithm based on the vertex degree of the ant colony algorithm. The steps are as follows:

Step 1: Generate a connectivity graph matrix based on clustering conditions.

Step 2: At the beginning of the iteration, a number of ants are randomly generated and distributed on each vertex in the graph. Determine the number of adjacent vertices. If the number of adjacent vertices is 0, the vertex forms an independent cluster. If the number of adjacent vertices is 1, the current point forms a cluster with the adjacent points. If the number of adjacent vertices is greater than or equal to 2, go to step 3.

Step 3: If the number of adjacent vertices of the current point is greater than the number of adjacent vertices +1, use the corresponding vertex degree as the heuristic function, and then use the roulette wheel method to select the position of the next vertex until the vertex degree of the traversed vertex is less than 2 (when the number of adjacent vertices is less than 2, the traversal ends).

Step 4: Determine whether each path generated by an ant forms a cluster. If a cluster is formed, keep the current path. If not, discard the generated path.

Step 5: For each retained path after each iteration, update the pheromone according to the corresponding path. Then, proceed to the next iteration until the iteration is completed.

3.3. Overlapping and Conflicting Clustering Task Handling

The agile satellite task set containing multiple point target tasks can be solved by the improved ant colony algorithm to obtain multiple clustering tasks so that $R_C^N$ represents the clustering results that can be obtained after task clustering is solved by the abovementioned algorithm as follows: $R_C^N$ = {$R_C^1$, $R_C^2$, $R_C^3$,…, $R_C^m$}. These clustering tasks may still have overlapping or conflicting point target tasks. Therefore, further research is needed on how to solve this problem and ensure that each point target task can only exist in one clustering task. To solve this problem, we propose the following solutions:

• (1). Resolve conflicting clustering tasks: In $R_C^N$ = {$R_C^1$, $R_C^2$, $R_C^3$, …, $R_C^m$}, if two clustering tasks contain the same point target, it is necessary to decide which clustering task this point should be divided into. Since the goal of task clustering is to include as many point targets as possible, in this case, the conflicting point target needs to be divided into the clustering task with more point targets. This is mathematically described as the case where there is $R_C^1$ ⊄ $R_C^2$ and $R_C^2$ ⊄ $R_C^1$ in $R_C^N$, and $R_C^1$ ∩ $R_C^2$ ≠ Ø; if |$R_C^1$| ≥ |$R_C^2$|, then {$R_s^1$|$R_s^1$ ∈ $R_C^2$, $R_s^1$ ∉ $R_C^1$} → $R_s^{2\prime }$, {$R_C^{2\prime }$, $R_C^1$} → $R_C^N$.

• (2). Solve overlapping clustering tasks: In $R_C^N$ = {$R_C^1$, $R_C^2$, $R_C^3$,…, $R_C^m$}, there will be overlapping clustering tasks; if there is a clustering task that is a subset of another clustering task (that is, the point target contained in one of the clustering tasks appears in another clustering task), then the two clustering tasks are overlapping clustering tasks. The way to solve them is to discard the subset and select the clustering task that contains the greater number of point targets as the final clustering task, which is mathematically described as follows: if $R_C^2$ ⊆ $R_C^1$, then $R_C^1$ → $R_C^N$.

The treatment of the above two clustering tasks can be generalized to the case of multiple tasks.

The pseudo code for clustering is as follows (Algorithm 1):

Algorithm 1: Ant Colony Clustering Algorithm

4. Mission Planning Based on Heuristic Algorithms

When multiple target groups are formed through task clustering, it is necessary to select and plan the observation sequence of each group to optimize the observation benefit, as shown in Figure 4. In this section, by focusing on the observation time window constraints and satellite attitude maneuvering constraints of each target group and taking the target weight and attitude maneuvering energy consumption as the optimization objectives, a Simulated Genetic Annealing Algorithm will be designed to plan the target observation sequence.

4.1. Algorithm Flow of SA-GA Heuristic Algorithm

Compared with traditional genetic algorithms, the SA-GA (Simulated Genetic Annealing Algorithm) proposed in this paper conducts genetic operations such as crossover and mutation at each temperature of the simulated annealing (SA) algorithm. Before iterating with the genetic algorithm, the SA is first utilized to optimize the solution, and the optimal solution found is used as the initial feasible solution for the genetic algorithm. This increases the probability of finding an optimal solution. Additionally, the population updating and optimization operations carried out during each temperature decrease in the simulated annealing process expand the search range of the feasible domain in comparison with traditional intelligent optimization algorithms, thereby enhancing the possibility of finding the optimal solution under the same conditions. The algorithm flow diagram is shown in Figure 5.

4.2. Encoding Method

The encoding rule used in this paper is 0–1 encoding. The length of each individual in the population represents the number of point target groups after task clustering. The 0–1 encoding represents the solution of the problem as a 0–1 sequence and arranges the number of tasks after each clustering in chronological order. If the cluster task is represented as 0, it means that it is not selected after task planning; if it is 1, it is selected after task planning. As shown in Figure 6.

4.3. Initial Solution Generation Rules

Firstly, a certain number of population individuals are randomly generated. Then, within the number of iterations, a feasible individual is randomly selected for optimization operations to determine whether the new solution is superior to the optimal solution. If it is superior to the original solution, the new solution is retained to replace the original solution in the population, and the solution follows. After a certain number of updates, the new population is used as the initial solution of the genetic algorithm. After selection, crossover, and mutation, individuals with better fitness are selected for population updates to complete an SA (simulated annealing) iteration for optimization until the temperature drops to the set lower temperature bound.

4.4. SA-GA Genetic Operation Algorithm

4.4.1. Crossover Operation

Crossover operation is a necessary operation in genetic algorithms. It can enhance the search range of feasible solutions and help the population break away from the local optimal solution. In this paper, the chosen crossover operation involves iterating through individuals in the population based on the crossover probability and determining whether to select the current individual. For selected individuals, another individual from the population is randomly chosen for the crossover operation. Two gene positions on the parent individuals are then randomly selected, and the genes in these positions are exchanged. The crossover operation is shown in Figure 7.

4.4.2. Mutation Operation

Mutation can enhance the algorithm’s search ability within the feasible domain. This paper adopts binary mutation. It traverses the individuals in the population one by one and judges whether each individual in the population will mutate according to the preset mutation probability. If an individual mutates, two positions are randomly generated on the individual, and the gene value is inverted at the generated positions. The mutation operation is shown in Figure 8.

4.4.3. Copying Operation

The copying operation involves using certain rules or methods to duplicate individuals into a new population. Generally, individuals with higher fitness are selected from the population and copied into the new population. In this paper, the population formed after genetic operations is subject to selection and copying. By duplicating a certain number of excellent individuals within the population, the newly formed population has higher individual benefits and can reach the optimal solution more quickly.

4.4.4. Parameters Related to Simulated Annealing Algorithm

There are different annealing rate strategies in simulated annealing algorithms, which balance exploration and development by controlling the cooling strategy. The exponential cooling rule, linear cooling rule, logarithmic cooling rule, inverse temperature cooling rule, and different cooling rules and parameters have a significant impact on the effectiveness of the simulated annealing algorithm. This article chooses the following exponential cooling rule:

(15)$T_{k+1}=a{T}_k$

where $T_k$ is the temperature at iteration k, and a is a constant less than 1 (usually between 0.8 and 0.99).

In this article, according to the Metropolis criterion, a new solution generated by a new solution generation function is accepted at each temperature:

(16)$\mathrm{r}=\min (1,e^{-{\displaystyle \frac{\mathsf{\Delta }E}{\mathrm{T}}}})$

In the early stages of the algorithm, when the temperature, T, is high, the algorithm allows for the acceptance of poorer solutions (even if the new solution is worse than the current one), which is helpful for exploring a larger search space. As the algorithm progresses, the temperature T gradually decreases, and the algorithm tends to only accept solutions that are better than or equivalent to the current solution, gradually converging to an optimal solution in the search space. Through this mechanism, the Metropolis criterion enables the simulated annealing algorithm to have the ability to escape from local optima and search for global optima.

5. Simulation Analysis

This section conducts simulation verification on the task clustering algorithm and task planning algorithm proposed in this article. The range (latitude 62–72°, longitude 145–150°) generates a uniform distribution of 20,50 dense area point targets. The observation angle of the satellite to the target area of the meta-mission is calculated by the STK 11.60. The simulation time is in the period of 00:00:00 1 February 2024–00:00:00 2 February 2024. The sensor field of view is 10 degrees, the maximum start-up time is 150 s, and the maximum yaw angle is 45 degrees; if two tasks can cluster, the time window interval Δt is 5 s. The parameters of the satellite sensor are shown in Table 2.

The distribution map of point targets is shown in Figure 9.

The experimental environments are Windows 11 and the Inter Core i7 processor, and MATLAB R2022b is the programming used.

The orbital parameters of the satellite and the parameters of the remote sensors it carries are shown in Table 3.

In the task planning simulation process, the clustering tasks obtained by the above clustering algorithm are used as the input data for task planning. The obtained clustering data will be used for task planning in the SA-GA (Simulated Genetic Annealing Algorithm) and compared with traditional intelligent search algorithms; the experimental conclusions were obtained by comparing the Particle Swarm Algorithm (PSO), simulated annealing algorithm (SA), genetic algorithm (GA), Differential Evolution Algorithm (DE), and Tabu Search Algorithm (TS). Some experimental simulation parameters are shown below (Table 4).

When the number of point targets is 20, the observed benefits of running the algorithm once are as shown in Figure 10.

The results shown in Figure 10 were obtained by randomly selecting 100 iterations of the SA (simulated annealing algorithm) and the SA-GA (Simulated Genetic Annealing Algorithm), representing the relationship between the algorithm returns obtained in the process of 100 iterations during the operation of an algorithm. As can be seen from the graph, the SA-GA (Simulated Genetic Annealing Algorithm) is the most stable and approaches the optimal solution faster than other algorithms.

The results of running the algorithm 50 times are shown below (Figure 11).

The comparison of algorithm benefits after 50 runs of the algorithm is shown in Figure 11, and it can be seen that the experimental results obtained by the SA-GA (Simulated Genetic Annealing Algorithm) are more stable than those obtained by other algorithms after 50 algorithm runs, but the algorithm benefits obtained by the SA-GA (Simulated Genetic Annealing Algorithm) are not significantly better than those of other algorithms, which may be due to the small data range of the experimental data.

When the number of point targets is 50, the observed benefits of running the algorithm once are as shown below (Figure 12).

The observed benefits of the first 50 runs of the algorithm are shown in the following figure (Figure 13).

From the simulation results in Figure 12 and Figure 13, it can be observed that the SA-GA (Simulated Genetic Annealing Algorithm) approaches the optimal solution faster, the performance of the GA (genetic algorithm) and the SA-GA (Simulated Genetic Annealing Algorithm) is more stable, and the SA-GA (Simulated Genetic Annealing Algorithm) is the best compared with the GA (genetic algorithm); the SA-GA (Simulated Genetic Annealing Algorithm) carries out the search update of the dataset in advance before the genetic iteration and combines the characteristics of the SA (simulated annealing algorithm) to update the population every time the temperature drops so as to expand the search range.

The observation time windows for each cluster after clustering 50 point targets are shown in Table 5.

The comparison results of the SA-GA (Simulated Genetic Annealing Algorithm) between the benefits before and after clustering are shown below (Figure 14 and Figure 15).

When the target is 20 points;

Figure 14

Benefits before and after clustering.

[Figure omitted. See PDF]

When the target is 50 points.

Figure 15

Benefits before and after clustering.

[Figure omitted. See PDF]

From Figure 14 and Figure 15, it can be seen that the observation benefits significantly improved after clustering. This is because clustering reduces the number of regional point target tasks, which can reduce the number of satellite oscillations during observation, thereby improving the observation benefits of the satellite. The observation benefits of this article are related to the energy consumption of satellite sensors during the yaw process. However, the energy consumption during the yaw process of satellite sensors in this article is set by the authors, which may differ from actual engineering. From the comparison between the ant colony clustering algorithm in this article and the simple graph clustering algorithm in the figure, it can be seen that the difference between the two clustering algorithms for task planning after clustering is small, which may be caused by the different treatment methods of the clustering results, but this also confirms the feasibility of the ant colony clustering algorithm used in this paper.

6. Conclusions

This paper studies the clustering method and mission planning of the dense area point targets of single-orbit agile satellites. The research results are as follows:

• Before planning the task, the point targets are preprocessed according to the clustering conditions to reduce the task amount and the number of observations. The ant colony clustering method is used to effectively generate the smallest number of clusters while ensuring the generated clusters are of higher quality.

• For the generated clustering task group, considering the constraints of the satellite observation process, the improved SA-GA (Simulated Genetic Annealing Algorithm) is adopted, and the weight of the point target and the energy consumed in the yaw process are used as the optimization strategies. Compared with traditional intelligent algorithms, an observation scheme with a small total maneuver yaw angle and a high sum of observation weights are effectively selected, resulting in better algorithm convergence and stability.

Author Contributions

Conceptualization, C.Y. and X.N.; methodology, C.Y.; software, X.N.; validation, C.Y., Y.C. (Yuan Chen) and Y.C. (Yilin Chen); formal analysis, C.Y.; investigation, C.Y.; resources, C.Y. and X.N.; data curation, C.Y.; writing—original draft preparation, C.Y.; writing—review and editing, C.Y. and X.N.; visualization, Y.C. (Yilin Chen); supervision, Y.C. (Yilin Chen) and X.N.; project administration, X.N.; funding acquisition, X.N. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

The data are contained within the article.

Conflicts of Interest

The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript; or in the decision to publish the results.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. Satellite observation attitude.

Figure 2. Task clustering.

Figure 3. Group division.

Figure 4. Task planning.

Figure 5. SA-GA process.

Figure 6. The rule of 0–1 encoding.

Figure 7. Crossover operation.

Figure 8. Mutation operation.

Figure 9. Point target distribution map.

Figure 10. Iteration benefit comparison.

Figure 11. The benefit of each algorithm run.

Figure 12. Iteration benefit comparison.

Figure 13. The benefit of each algorithm run.

Table 1

Variable names and definitions.

Variable Name	Variable Definitions
N	Number of groups
n	Number of point targets
M	Target point set$M=\{m_1$$,m_2$$,\dots ,m_n$$\},\mathrm{where}{m}_i$ represents i-th point target
C	group target set $C=\{c_1$$,c_2$$,\dots ,c_n$}, $\mathrm{where}{c}_i$ is i-th group target
$t_{ei}$	$m_i$ earliest observable time
$t_{li}$	$m_i$latest observable time
$T_{ei}$	$c_i$ earliest observable time
$T_{li}$	$c_i$ latest observable time
$t_{si}$	$c_i$ actual start time of observation
$t_{rij}$	$c_i$ $\mathrm{to}{c}_j$ satellite attitude conversion time
$d_{mi}$	$m_i$ continuous observation time required
$d_{ci}$	$c_i$ continuous observation time required
$s_i$	$m_i$ satellite observation angle
$S_i$	$c_i$ satellite observation angle
$w_i$	$m_i$ observation benefit (task weights)
$a_i$	$m_i$ observed energy consumption
$b_i$	$m_i$ observed memory consumption
$A_i$	$c_i$  $\mathrm{observed}\mathrm{energy}\mathrm{consumption},A_i$ $=\sum _{j\in c_i}{a}_j$
$B_i$	$c_i$  $\mathrm{observed}\mathrm{memory}\mathrm{consumption},B_i$ $=\sum _{j\in c_i}{b}_j$
$W_i$	$c_i$  $\mathrm{observation}\mathrm{benefits}\left(\mathrm{task}\mathrm{priority}\right),W_i$ $=\sum _{j\in c_i}{w}_j$

Table 2

Satellite sensor parameters.

Fov (°)	Max T (s)	Max θ (°)
10	150	45

Table 3

Track-related parameters.

Satellite-Related Parameters	Parameter
Semi-major axis	7000 km
Orbital eccentricity	0.006°
Orbital inclination	97°
Ascending node right ascension	285°
Perigee	286°
True Anomaly	73°

Table 4

Experimental parameters.

Starting Temperature	Temperature Drop Ratio	Minimum Temperature Limit	Iterations	Mutation Probability	Crossover Probability	Total Group Number
1000	0.98	1 × 10−12	100	0.1	0.6	100

Table 5

Cluster observation times after clustering.

Group Observation Number	Group Visible Time Window/s	Group Observation Time/s
1	[673.04, 842.09]	[673.04, 678.04]
2	[692.96, 844.41]	[692.96, 697.96]
3	[710.33, 846.91]	[710.33, 715.33]
4	[755.31, 801.74]	[755.31, 760.31]
5	[775.45, 799.20]	[775.45, 780.45]
6	[795.37, 823.31]	[795.37, 800.37]
7	[812.67, 902.48]	[812.67, 817.67]
8	[816.26, 1015.43]	[825.02, 830.02]
9	[844.39, 856.06]	[844.39, 849.39]
10	[853.69, 925.03]	[864.62, 869.62]

References

1. Long, X.; Wu, S.; Wu, X.; Huang, Y.; Mu, Z. A GA-SA Hybrid Planning Algorithm Combined with Improved Clustering for LEO Observation Satellite Missions. Algorithms; 2019; 12, 231. [DOI: https://dx.doi.org/10.3390/a12110231]

2. Cui, J.; Zhang, X. Application of a Multi-Satellite Dynamic Mission Scheduling Model Based on Mission Priority in Emergency Response. Sensors; 2019; 19, 1430. [DOI: https://dx.doi.org/10.3390/s19061430] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/30909562]

3. Song, Y.-J.; Zhou, Z.-Y.; Zhang, Z.-S.; Yao, F.; Chen, Y.-W. A framework involving MEC: Imaging satellites mission planning. Neural Comput. Appl.; 2020; 32, pp. 15329-15340. [DOI: https://dx.doi.org/10.1007/s00521-019-04047-6]

4. Kim, H.; Chang, Y.K. Mission scheduling optimization of SAR satellite constellation for minimizing system response time. Aerosp. Sci. Technol.; 2015; 40, pp. 17-32. [DOI: https://dx.doi.org/10.1016/j.ast.2014.10.006]

5. Wang, J.; Zhu, X.; Qiu, D.; Yang, L.T. Dynamic Scheduling for Emergency Tasks on Distributed Imaging Satellites with Task Merging. IEEE Trans. Parallel Distrib. Syst.; 2014; 25, pp. 2275-2285. [DOI: https://dx.doi.org/10.1109/TPDS.2013.156]

6. Wu, G.; Wang, H.; Pedrycz, W.; Li, H.; Wang, L. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy. Comput. Ind. Eng.; 2017; 113, pp. 576-588. [DOI: https://dx.doi.org/10.1016/j.cie.2017.09.050]

7. Wu, G.; Liu, J.; Ma, M.; Qiu, D. A two-phase scheduling method with the consideration of task clustering for earth observing satellites. Comput. Oper. Res.; 2013; 40, pp. 1884-1894. [DOI: https://dx.doi.org/10.1016/j.cor.2013.02.009]

8. Li, Z.; Hao, G.; Xu, P.; Qiu, D. Agile Imaging Satellite Intensive Task Clustering and Scheduling for Disaster Monitoring. Res. J. Chem. Environ.; 2013; 17, pp. 170-179.

9. Zhao, Y.; Du, B.; Li, S. Agile Satellite Mission Planning Via Task Clustering and Double-Layer Tabu Algorithm. Comput. Model. Eng. Sci.; 2020; 122, pp. 235-257. [DOI: https://dx.doi.org/10.32604/cmes.2020.08070]

10. Song, Y.; Ou, J.; Wu, J.; Wu, Y.; Xing, L.; Chen, Y. A cluster-based genetic optimization method for satellite range scheduling system. Swarm Evol. Comput.; 2023; 79, 101316. [DOI: https://dx.doi.org/10.1016/j.swevo.2023.101316]

11. Huang, Y.; Mu, Z.; Wu, S.; Cui, B.; Duan, Y. Revising the Observation Satellite Scheduling Problem Based on Deep Reinforcement Learning. Remote Sens.; 2021; 13, 2377. [DOI: https://dx.doi.org/10.3390/rs13122377]

12. Sarkheyli, A.; Bagheri, A.; Ghorbani-Vaghei, B.; Askari-Moghadam, R. Using an effective tabu search in interactive resources scheduling problem for LEO satellites missions. Aerosp. Sci. Technol.; 2013; 29, pp. 287-295. [DOI: https://dx.doi.org/10.1016/j.ast.2013.04.001]

13. Wang, P.; Reinelt, G. A Heuristic for an Earth Observing Satellite Constellation Scheduling Problem with Download Considerations. Electron. Notes Discret. Math.; 2010; 36, pp. 711-718. [DOI: https://dx.doi.org/10.1016/j.endm.2010.05.090]

14. Wang, P.; Reinelt, G.; Gao, P.; Tan, Y. A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation. Comput. Ind. Eng.; 2011; 61, pp. 322-335. [DOI: https://dx.doi.org/10.1016/j.cie.2011.02.015]

15. Sun, B.; Wang, W.; Xie, X.; Qin, Q. Satellite mission scheduling based on genetic algorithm. Kybernetes; 2010; 39, pp. 1255-1261. [DOI: https://dx.doi.org/10.1108/03684921011063538]

16. He, R.; Gao, P.; Bai, B.C.; Li, J.F.; Yao, F.; Xing, L.N. Models, algorithms and applications to the mission planning system of imaging satellites. Xitong Gongcheng Lilun Yu Shijian/Syst. Eng. Theory Pract.; 2011; 31, pp. 411-422.

17. Makarov, A.; Pérez-Herradón, C.; Franceschetto, G.; Taddei, M.M.; Osaba, E.; Cabello, P.d.B.; Villar-Rodriguez, E.; Oregi, I. Quantum Optimization Methods for Satellite Mission Planning. IEEE Access; 2024; 12, pp. 71808-71820. [DOI: https://dx.doi.org/10.1109/ACCESS.2024.3402990]

18. Rainjonneau, S.; Tokarev, I.; Iudin, S.; Rayaprolu, S.; Pinto, K.; Lemtiuzhnikova, D.; Koblan, M.; Barashov, E.; Kordzanganeh, M.; Pflitsch, M. et al. Quantum Algorithms Applied to Satellite Mission Planning for Earth Observation. IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens.; 2023; 16, pp. 7062-7075. [DOI: https://dx.doi.org/10.1109/JSTARS.2023.3287154]

19. Wang, X.; Gu, Y.; Wu, G.; Woodward, J.R. Robust scheduling for multiple agile Earth observation satellites under cloud coverage uncertainty. Comput. Ind. Eng.; 2021; 156, 107292. [DOI: https://dx.doi.org/10.1016/j.cie.2021.107292]

20. Han, C.; Gu, Y.; Wu, G.; Wang, X. Simulated Annealing-Based Heuristic for Multiple Agile Satellites Scheduling Under Cloud Coverage Uncertainty. IEEE Trans. Syst. Man Cybern. Syst.; 2023; 53, pp. 2863-2874. [DOI: https://dx.doi.org/10.1109/TSMC.2022.3220534]

21. Zhang, J.; Xing, L. An improved genetic algorithm for the integrated satellite imaging and data transmission scheduling problem. Comput. Oper. Res.; 2022; 139, 105626. [DOI: https://dx.doi.org/10.1016/j.cor.2021.105626]

22. Chen, M.; Chen, Y.; Chen, Y.; Qi, W. Deep Reinforcement Learning for Agile Satellite Scheduling Problem. Proceedings of the 2019 IEEE Symposium Series on Computational Intelligence (SSCI); Xiamen, China, 6–9 December 2019; pp. 126-132.

23. Song, Y.; Wei, L.; Yang, Q.; Wu, J.; Xing, L.; Chen, Y. RL-GA: A Reinforcement Learning-based Genetic Algorithm for Electromagnetic Detection Satellite Scheduling Problem. Swarm Evol. Comput.; 2023; 77, 101236. [DOI: https://dx.doi.org/10.1016/j.swevo.2023.101236]

24. Ou, J.; Xing, L.; Yao, F.; Li, M.; Lv, J.; He, Y.; Song, Y.; Wu, J.; Zhang, G. Deep reinforcement learning method for satellite range scheduling problem. Swarm Evol. Comput.; 2023; 77, 101233. [DOI: https://dx.doi.org/10.1016/j.swevo.2023.101233]

25. Yang, X.; Hu, M.; Huang, G.; Wang, Y. A Hybrid Preference Interaction Mechanism for Multi-Satellite Imaging Dynamic Mission Planning. Electronics; 2024; 13, 2374. [DOI: https://dx.doi.org/10.3390/electronics13122374]

26. Chen, Y.; Zhang, D.; Zhou, M.; Zou, H. Multi-satellite Observation Scheduling Algorithm Based on Hybrid Genetic Particle Swarm Optimization. Proceedings of the Advances in Information Technology and Industry Applications; Shenzhen, China, 24–25 December 2011; Springer: Berlin/Heidelberg, Germany, 2012; pp. 441-448.

27. Li, P.; Li, J.; Li, H.; Zhang, S.; Yang, G. Graph Based Task Scheduling Algorithm for Earth Observation Satellites. Proceedings of the 2018 IEEE Global Communications Conference (GLOBECOM); Abu Dhabi, United Arab Emirates, 9–13 December 2018; pp. 1-7.

28. He, Y.; Chen, Y.; Lu, J.; Chen, C.; Wu, G. Scheduling multiple agile earth observation satellites with an edge computing framework and a constructive heuristic algorithm. J. Syst. Archit.; 2019; 95, pp. 55-66. [DOI: https://dx.doi.org/10.1016/j.sysarc.2019.03.005]

29. Long, J.; Qian, Z.; Xie, F.; Ding, Z.; Liu, L. An Improved Multi-Satellite Cooperative Task Planning Method Based on Distributed Multi-agent System. Proceedings of the 2021 13th International Conference on Measuring Technology and Mechatronics Automation (ICMTMA); Beihai, China, 16–17 January 2021; pp. 539-542.

30. Wang, S.; Zhao, L.; Cheng, J.; Zhou, J.; Wang, Y. Task scheduling and attitude planning for agile earth observation satellite with intensive tasks. Aerosp. Sci. Technol.; 2019; 90, pp. 23-33. [DOI: https://dx.doi.org/10.1016/j.ast.2019.04.007]