1. Introduction
Earth observation satellites are deployed in orbits around Earth to capture photographs of specific regions at the behest of users. Satellite-based observations of the ground are distinguished by their wide coverage, extended duration, and the absence of limitations imposed by national borders. These attributes render them indispensable for time-sensitive and resource-intensive emergency operations including regional deployments, counterterrorism initiatives, stability enforcement, flood response, and similar endeavors.
This study addresses the problem of satellite scheduling observations for a collection of satellites and a large number of tasks. Each task might be observed by different satellites from different tracks at different time instants. Consequently, this scheduling challenge represents a difficult optimization problem, potentially involving numerous satellites, hundreds of requests, constraints on the timing and manner of servicing each request, and rules governing the resources.
When conducting imaging missions, satellites must rotate their cameras to capture images within their fields of view. In the traditional mode, satellites adopt a single-task observation approach for point targets, wherein the satellite sensor observes only one task at a fixed deflection angle. This single-task observation ensures imaging at an optimal angle, resulting in a high imaging accuracy and maximum user satisfaction. When the number of tasks to be observed within a region is relatively large and dense, “conflict issues” may arise between adjacent tasks during the satellite observations. For instance, conflicts can occur if the time windows of adjacent tasks overlap or if there is insufficient time for satellite attitude adjustments between consecutive tasks, forcing the satellite to choose only one of the tasks for observation. These conflicts significantly reduce the number of tasks that satellites can observe and decrease the efficiency of satellite resource utilization. In this context, to enable some adjacent tasks with “conflict issues” to be observed simultaneously by the satellite, rather than choosing only one, researchers have begun to explore the satellite scheduling problem with a “multi-task merging mechanism”. The satellite scheduling problem with a merging mechanism refers to the ability of a satellite to observe multiple individual tasks simultaneously during a single observation activity by adjusting its imaging angle. These simultaneously observed individual tasks are referred to as combined tasks, and the specific concept is introduced in
Section 2.2.
Many scholars have addressed the single-satellite scheduling problem using various methods including dynamic programming [
1], fast simulated annealing algorithms [
2], clique partition theory methods [
3], and heuristic algorithms [
4,
5]. Multi-satellite coordinated observations have demonstrated higher observation efficiency as the number of satellites in orbit increases [
6,
7,
8,
9,
10,
11]. Consequently, research on multi-satellite scheduling with merging mechanisms has primarily focused on two aspects: task-merging mechanisms and observation strategies [
12,
13,
14] and scheduling algorithms [
15,
16,
17,
18,
19,
20,
21]. However, existing task merging mechanisms are mostly based on “merging rules” and “aggregation density” between adjacent tasks, with a limited consideration of all possible task merging scenarios under a given merging mechanism; an analysis of which scheduling algorithms are most effective under different task merging mechanisms is lacking. Therefore, we aim to verify which task merging methods and scheduling algorithms work best together under different observation tasks. Additionally, we propose a two-stage satellite task scheduling method, CG + EFWA, which demonstrates superior overall performance. This work has practical significance for real-world satellite task scheduling problems.
In response to the characteristics of domestic satellites, a task-merging mechanism was proposed to improve the observation efficiency of Earth observation satellites. Based on task merging, the problem is solved using the enhanced fireworks algorithm (EFWA) as well as the enhanced ant colony optimization (EACO) algorithms. The remainder of this paper is organized as follows:
Section 2 introduces the satellite combined-task scheduling problem (SCTSP) and the establishment of its model.
Section 3 describes the methodology of the constrained graph (CG) task-merging mechanism.
Section 4 describes a satellite combined task-scheduling algorithm based on CG.
Section 5 validates the efficacy of the proposed CG method and EFWA through a multitude of simulations and comparative analyses. The comparative analyses show that, such as in the case where the number of tasks is 700 in the observation, the CG + EFWA (CG is adopted in the task merging stage and EFWA is adopted in the satellite combined-task scheduling stage) method improves observation benefits by 70.35% (compared to CG + EACO, CG is adopted in the task merging stage and EACO is adopted in the satellite combined-task scheduling stage), 78.93% (compared to MS + EFWA, MS is adopted in the task merging stage and EFWA is adopted in the satellite combined-task scheduling stage), and 39.03% (compared to MS + EACO, MS is adopted in the task merging stage and EACO is adopted in the satellite combined-task scheduling stage).
2. Problem Description and Modeling of SCTSP
The traditional satellite task scheduling problem (STSP) refers to the following: satellites image a specific observation task at an optimal angle by rotating their cameras during one of the observable time windows. The SCTSP refers to the following: satellites image several observation tasks simultaneously by rotating their camera angles during one of the observable time windows. Examples of observation tasks obtained from the above two types of problems are shown in
Table 1.
The SCTSP refers to the scenario in which, during a single observation activity of a satellite, several adjacent tasks that either satisfy the “merging mechanism” or exhibit “task conflicts” are observed simultaneously according to a specific task merging mechanism. The SCTSP, based on the task-merging mechanism, can be divided into two stages. The first stage is the task merging stage based on the task merging mechanism, and the second is the satellite combined-task scheduling stage. The task merging phase represents the initial stage of the SCTSP. Its primary objective is to ascertain the set of combined tasks according to the constraint conditions (observation time window and observation angle) and task synthesis rules. The combined-task scheduling phase represents the second stage of the SCTSP. The primary objective of this phase was to determine the observation plans for each combined task, including the satellite orbit, observation angle, and observation time.
To clarify the SCTSP, we first define the concepts of task conflict and combined tasks in the SCTSP. Building upon these definitions, we then describe the SCTSP based on the task-merging mechanism.
2.1. Task Conflict
In regions characterized by a high density of observation tasks, the conventional single-task observation strategy frequently leads to conflicts among numerous tasks, which in turn manifest as a diminished satellite observation efficiency. Satellites, which are in constant high-speed orbit, can only image target areas when they are directly overhead. The duration of continuous imaging ranges from a few seconds to several minutes. During this period, the camera orientation was adjusted to enable the observation of an individual target task. Consequently, each observation task is correlated with a distinct time window of the satellite, known as the visible time window for that task. When the visible time windows of multiple tasks overlap, indicating that several observation tasks are scheduled within the same satellite window, conflict between these tasks is highly likely. These conflicts arise from the impracticality of completing the necessary attitude transition of a satellite sensor between consecutive tasks. An illustration of the satellite sensor transition time is shown in
Figure 1.
Figure 1 demonstrates that the interval time between
and
is shorter than the transition time. Consequently, following the completion of
, the satellite will not conduct the observation of
, thereby designating
and
as conflicting tasks. Conversely, the interval time between
and
exceeds the transition time, thus there is no conflict between
and
.
2.2. Combined Task
Conflicts between adjacent single tasks can be mitigated through multi-task observations using a task-merging mechanism.
Figure 2 illustrates the task merging process. If several adjacent single tasks (e.g.,
) can be observed simultaneously by adjusting the angle of the satellite camera, they are referred to as a combined task for the observing satellite. This combined task encompasses the individual tasks
. When employing a single-task observation approach, the satellite can select only one of the tasks (
) for observation. However, by adopting a multi-task merging observation strategy, it is feasible to conduct observations of all three individual tasks.
In satellite observation scheduling, a task observed by a single satellite observation is referred to as a single task [
12]. In this study, a set of multiple single tasks that can be observed simultaneously in one combined observation were defined as a combined task.
Definition 1. Combined Task. When a satellite executes a multi-task merging observation strategy, enabling the concurrent monitoring of several single tasks within a single observational period, the resultant sequence of single tasks is referred to as a combined task. Notably, a combined task may comprise a single task.
Figure 2 depicts a sequence of tasks, designated as
, where each individual task is a single task. Notably, single tasks
can be simultaneously observed in their entirety during one observational campaign by the satellite. Thus,
are aggregated into a combined task, which can be abbreviated as the combined task
.
When the region under observation is densely populated with tasks, employing a single-task observation strategy by satellites can lead to a marked decrease in observational efficiency, primarily owing to the occurrence of task conflicts. In such cases, a multi-task observation mode based on a task-merging mechanism can be employed for satellites with limited rotation capabilities. Compared to the conventional single-task observation method, the task combining observation not only conserves satellite energy resources by reducing the number of sensor activations, but it also enhances observation benefits by mitigating task conflicts.
2.3. Satellite Combined-Task Scheduling Problem
The SCTSP can be represented as a quintuple . Here, denotes the task set, represents the time window for the combined tasks, is the set of constraints, and is the objective function. Based on the multi-task merging mechanism, the SCTSP can be described as follows: under the satisfaction of satellite resource constraints and task requirements, single tasks are first combined to generate a set of combined tasks that can be observed by the satellite. Subsequently, time windows and satellite resources are allocated to the combined tasks, thereby formulating a satellite combined task observation plan based on the task-merging mechanism. The goal was to maximize the observation benefits of the satellite.
To provide a clearer description of the SCTSP, we define it in “Definition 2” and present the relevant symbols in the table below.
Definition 2. Satellite Combined-Task Observation (SCTO). The satellite adopts a method of observation through a multi-task merging mechanism, where a combined task containing multiple single tasks is observed during a single observation activity (see Table 2). 2.3.1. Multi-Task Merging Mechanism
In the SCTSP, the initial step involves conducting a multi-single task combined based on the task-merging mechanism for the set of single tasks. How does the task-merging mechanism select single tasks to be combined into a combined task? Multi-single tasks within a combined task must simultaneously satisfy the constraints of the merging mechanism, which include angle, energy, storage, and time constraints.
- (1)
Angle constraint
Imaging satellites possess a limited finite field of view, and during a single imaging process it is necessary to adjust the satellite’s imaging angle to better cover multiple single tasks simultaneously. The field-of-view angle g of satellite s determines the range of its field-of-view for observing multiple subtasks concurrently. For instance, a combined task T (1, N) that includes a sequence of single tasks t1, t2, …, tn must adhere to the following constraint rules:
Assuming that the observation angles for the single-task sequence are , respectively, it is imperative that the following condition is satisfied: .
Assuming that the start times of the observation time windows correspond to the single-task sequence , it is necessary to fulfill the following requirement: .
In particular, when the combined task consists of only two single tasks, and , then the time window for is denoted as , and the composite observation angle is represented by
In [
12], Liu investigated the optimal observation angle algorithm for combined tasks and identified the following properties.
Character 1. For , we define its observation angle as , then and , and .
Character 2. If holds, the single-task sequence will be contained in the contained task. Suppose the maximum observation angle is ; the minimum observation angle is . The observation angle for the contained task is marked as , and then .
- (2)
Energy constraint
The solar panel is the main power supply of the satellite, and its capacity is limited. Imaging and slewing activities will consume most of the energy. The imaging and rotational activities of the satellites consume a significant portion of their energy. Consequently, the number of images that a satellite can capture are strictly limited. During a satellite’s observation activity, a threshold is established to restrict the maximum duration for which the satellite can remain operational. For combined tasks, the length of the time window cannot exceed .
- (3)
Storage constraint
The storage capacity of a satellite represents another limiting factor. If the images captured by the satellite cannot be transmitted promptly, they will be stored onboard. However, once the storage space is fully utilized, the satellite will be unable to function until the image data are transmitted and the memory is cleared. Consequently, the total amount of image storage must not exceed the maximum capacity.
- (4)
Time constraint
The transition time between two tasks is determined by their field-of-view angles and the camera’s rotation speed. If the transition time between two tasks exceeds the interval between them, one of the observation tasks will be abandoned. As illustrated in
Figure 2, the transition times between tasks t1 and t2 are short, and according to traditional satellite scheduling, only one of them can be observed. However, through task merging, they can be covered by a single observation strip of the satellite, allowing both tasks t1 and t2 to be observed. Therefore, the interval between two consecutive joint observations should be sufficiently long to enable the satellite to adjust its attitude.
2.3.2. The Model of SCTSP
Aiming to maximize observational benefits while considering constraints such as the angle constraint, time constraint, energy constraint, storage constraint, the uniqueness of tasks, and the non-interruptibility of scheduling, a mathematical formulation for the SCTSP is established.
The decision variables are as follows:
Equation (1) represents the satellite revenue, that is, the sum of the observed task revenue.
Formula (2) represents the uniqueness constraint of the task, i.e., each single task is observed at most once.
Equations (3) and (4) are the observation time constraints of merging tasks, ensuring that the start time of each merging task time window cannot be greater than its end time, and the observation period cannot exceed the maximum start-up time of satellites.
Equation (5) represents the satellite transition time constraint between two observation activities, where the termination time of the previous observation task and the satellite transition time do not exceed the observation start time of the next task.
Equation (6) represents the energy constraint. The solar panel is the main power supply of the satellite and its capacity is limited. Imaging and sleeping activities consume most of this energy.
Equation (7) represents the capacity constraint.
Equation (8) represents the non-interruptibility constraint of the tasks, indicating that once a satellite commences the execution of an observation task, it completes the observation of that task before proceeding to the next observation task.
Equation (9) represents the transition time of between the th and th task.
Formulas (10) and (11) are decision variables. Formula (10) indicates whether the single task is observed by satellite , and Formula (11) indicates whether the merging task is observed.
3. The Method of Task Merging
The first stage of the SCTSP is the task merging phase, where multiple individual tasks are synthesized. The set of combined tasks obtained during this stage serves as the data input for the combined-task scheduling stage (the second phase of the SCTSP). The diversity of the combined task solution space directly influences the observation benefits. Therefore, to enhance satellite observation efficiency, we propose a method for merging individual tasks based on the characteristics of satellite missions, using a complete graph (CG) clustering approach. Next, we introduce the principles of the CG method through the concept of undirected graphs, followed by graphical representations to illustrate the features of task synthesis using the CG method.
In satellite task planning problems, the concept of a “graph” is initially used to represent tasks, and later, a “complete graph” is used to represent the tasks and their interconnections [
22]. Complete graph (CG) clustering is a constraint-based clustering approach that identifies the sets of tasks that satisfy the constraint rules to determine the combined tasks. The process of task merging using the CG method is described in detail below. Initially, an undirected graph model G = (V, E) was constructed, where V represents the set of vertices and E denotes the set of edges. Within the set V, each vertex corresponds to a single task. Edge set E is established based on the synthesis constraints between meta-tasks; if two meta-tasks satisfy all the merging constraints, an edge is drawn between them.
Taking an imaging satellite task scheduling problem as an example, this section introduces the task merging method based on CG.
Figure 3 illustrates the transformation of a set of observation tasks into a CG model. If task1, 2, and 3 meet the observation conditions for combined satellite observation, then there is an edge connecting each pair of these three tasks. Consequently, the combined relationships among the 11 single tasks in
Figure 3 can be directly represented in the form of an undirected graph.
Character 3. Within the context of satellite task observation scheduling problems utilizing the CG approach, it is posited that when the merging conditions of tasks, including angle constraint and time constraint, can be formulated as functions over the real domain, a one-to-one correspondence exists between any complete subgraph in the undirected graph model and a combined task.
Proof. Assume that the merging conditions of combined tasks, which include the angle and time constraints, can be represented by functions over the real number domain. We denote the set of single tasks that satisfy the time merging constraints as the following:
where the observation start times of the single-task sequences are arranged in ascending order. The set of single tasks that satisfy the angle merging constraints is marked as the following:
Let the sequence of single tasks correspond to a complete subgraph in the undirected graph model . Due to , there exists an edge connecting every pair of meta-tasks and , thus satisfying and . Therefore, meets the conditions of task merging, and further, it can be deduced that and , which are equivalent to . The aforementioned proof process demonstrates that the sequence of single tasks corresponding to the complete subgraph simultaneously satisfies the conditions of task merging. Hence, constitutes a combined task.
On the other hand, if the sequence of single tasks is a combined task, then concurrently meets the conditions of and . For , there exists an edge connecting and . Therefore, any two single tasks within are connected by an edge, indicating that corresponds to a complete graph.
Thus, under the aforementioned constraints, every complete subgraph in the undirected graph model is in one-to-one correspondence with a combined task. □
4. Two-Stage Satellite Combined-Task Scheduling Algorithm Based on Task Merging Mechanism
To effectively solve the SCTSP, we designed a two-stage satellite combined-task scheduling algorithm based on the CG task-merging mechanism. The arrangement of this chapter is as follows. First, in
Section 4.1, the satellite combined task observation scheduling algorithm framework based on the task merging mechanism is introduced.
Section 4.2 introduces the task-merging algorithm based on CG.
Section 4.3 introduces the modeling process of the EFWA algorithm for the SCTSP.
4.1. Algorithmic Architecture
In accordance with the characteristics of the problem, we devised a two-stage satellite combined-task scheduling algorithm that leverages a task-merging mechanism. The algorithmic framework of this approach is illustrated in
Figure 4.
- 1.
The stage of Task Merging
The task merging phase represents the initial stage of the SCTSP. Its primary objective is to ascertain the set of combined tasks. Specifically, this involves the following steps: initially, the single-task sets for each orbit of satellite are determined based on the observation time windows of single tasks. Subsequently, the CG task merging method is employed to “combine” some single-task sets that satisfy the combined observation conditions.
For instance, if the set of single tasks is denoted as , and the combined tasks determined by the CG task merging method are and , then the corresponding set of combined tasks for the single-task set are denoted as .
- 2.
The stage of Combined tasks scheduling
The combined-task scheduling phase represents the second stage of the SCTSP. The primary objective of this phase was to determine the observation plans for each combined task, including the satellite orbit, observation angle, and observation time. Initially, feasible solutions were constructed based on the constraints of the task merging problem, thereby establishing the current population for the SCTSP. Subsequently, EFWA was employed to execute the explosion process, mutation process, mapping process, and local optimization search process to identify better elite solutions. If the algorithm converges, a population perturbation strategy is initiated. A local convergence lock was released by replacing the current population, and better solutions were explored. Finally, if the algorithm meets the iteration conditions, the current optimal solution is the output, and the satellite combined-task scheduling plan is obtained.
4.2. Task Merging Mechanism Based on CG
We designed a method based on the CG task merging mechanism, and the algorithm flow is shown in Algorithm 1.
Algorithm 1: Pseudocode of CG task merging algorithm: CG Task Merging Algorithm |
Input: Single Task Set |
Output: Merging Task Set |
1: for i = 1:num(V) |
2: Evaluate each pair of points within the set V of single tasks to ascertain whether they fulfill the merging constraints |
3: if two points met merging constraints |
4: an edge is drawn between the two points |
5: end |
6: end |
7: Constructing the neighborhood undirected graph for single task. |
8: Identify the collection of complete subgraphs within undirected graph. |
9: for i = 1:num(V) |
10: Constructing the combined task; |
11: end |
12: Output best solution |
First, a systematic evaluation is conducted on each pair of points within set V of the single tasks. The purpose was to ascertain whether these pairs met merging constraints. If the constraints are satisfied, an edge is drawn between the respective points, thereby establishing a neighborhood undirected graph for the observation task.
Subsequently, the complete subgraphs were identified within the undirected graph. This process involves a series of steps.
For each vertex in V, it is first determined whether there is an adjacency edge between the node and other nodes. If no neighboring edge exists, the task is deemed a combined task in isolation and the vertex is marked as visited. However, if a neighboring edge exists, the process proceeds to the next step.
A set of nodes, denoted by N, have a connected relationship with the current node. For a node within N, the set of nodes that have neighbor edges with both the current node and the node in N are identified.
If the identified set is empty, the nodes in N are combined into a combined task and the record is updated, marking the node as visited. If the set is non-empty, another node from N is selected, and the search for the set of nodes with neighboring connected edges continues. If the set is empty, it indicates that the current nodes form a merging task, and the record is accessed. Otherwise, the size of the current merging task is expanded by selecting nodes from the set until the set is empty.
The task merging process is completed when all nodes have been accessed. Finally, we could determine the task merging scheme based on the set of all the complete subgraphs identified.
4.3. Enhanced Fireworks Algorithm
Considering the problem characteristics of the multi-satellite scheduling problem of the merging task, the enhanced fireworks algorithm (EFWA) is chosen to solve the scheduling phase of the merging task. The firework algorithm (FWA) is a new type of evolutionary algorithm proposed in recent years. The firework algorithm is mainly a breadth-first algorithm for searching the solution space of the problem by generating sparks and mutations from firework explosions. The sparks produced by firework explosions are searched by the firework algorithm.
The SCTSP is a discrete combinatorial optimization problem, whereas the traditional FWA is primarily designed for solving optimization problems with continuous solution spaces. Given the large solution space of the SCTSP and the numerous possible combinations of tasks and satellites, it is crucial to consider both global and local search strategies simultaneously. The FWA is a search algorithm that inherently balances local and global searches. Therefore, this paper proposes a discrete FWA designed specifically for satellite combined-task scheduling, drawing upon the principles of the FWA [
23].
The conventional FWA is characterized by a broad search scope, a slower convergence rate, and suboptimal local search capabilities. To address the limitations of the traditional algorithm, we introduce two search strategies: a population perturbation strategy and a local optimization strategy. To ensure the algorithm progresses in a favorable direction, we propose a local optimization strategy known as the insert mechanism. When the population search performance becomes irrational, the algorithm activates the population perturbation strategy. The steps for EFWA are outlined in Algorithm 2.
Algorithm 2: Pseudocode of EFWA: Enhanced Fireworks Algorithm |
Input: Merging Task Set |
Output: Scheme for Allocating Time Windows to Satellites in Merging Task |
1: for i = 1: Iter |
2: sonsnum_array; |
3: for j = 1: seednum (sons_generate) |
4: for k = 1: sonsnum_array(j) |
5: search for sparks; |
6: end |
7: end |
8: GaussMutation; |
9: Local Optimization Operator for Seed Fireworks; |
10: Population intervention operator; |
11: Record and choose the best solution |
12: end |
13: Output best solution |
The EFWA comprises the explosion operator, mutation operator, mapping rules, population perturbation strategy, and local optimization strategy. The computational complexity of the EFWA can be deduced from its pseudocode in Algorithm 2, revealing that it is , where “n” denotes the number of iterations, “N” represents the population size, and “M” signifies the number of sparks generated by one seed firework.
- 1.
Explosion Operator
The explosion operator plays a pivotal role in generating offspring for seed fireworks and in determining the position and direction of algorithm optimization. It includes explosion magnitude, explosion intensity, and displacement operations.
Explosion amplitude is a critical component of the explosion operator, as it governs the step size of the algorithm’s search. If the explosion amplitude is set too large near the optimal value, it may lead to the offspring positions overshooting the optimal value, thereby failing to locate the optimal solution. The size of the explosion magnitude in the fireworks algorithm is guided by the adaptive value function of the spark. The explosion magnitude in the EFWA is defined as follows:
The explosion amplitude of the ith seed fireworks is represented by
,
is a constant that controls the explosion amplitude of fireworks.
represents the fitness value of the best offspring in the current population. Once the explosion amplitude of fireworks is determined, it is necessary to control their displacement to increase offspring diversity. The displacement of fireworks in the
kth dimension is calculated as follows:
where
represents the value of the
th seed firework in the
kth dimension, and
represents a uniform random number generated within
.
After determining the explosion amplitude of the offspring, the size of the offspring population is determined by the explosion intensity. The number of sparks produced by each seed firework is as follows:
where
represents the number of fireworks produced by the
th seed fireworks and
is a constant that limits the number of sparks produced by each seed firework during the explosion process.
represents the fitness value of the least fit individual in the current population, while
is the fitness value of the individual
.
is an extremely small control constant that prevents computational errors when the denominator equals zero.
The number of explosions obtained from Equation (14) may result in either too many or too few sparks. This can adversely affect the search efficiency of the algorithm. To circumvent this issue, we employ a piecewise function to limit the number of sparks within a certain range. The formula is as follows:
where
is a constant that limits the number of fireworks and
is an integer function.
- 2.
Mutation Operator
To enhance the diversity of the population, the algorithm employs Gaussian mutation to generate mutation sparks. The Gaussian mutation process involves randomly selecting a seed firework from the firework population and mutating it along a randomly chosen dimension of the selected firework. The Gaussian mutation calculation for the
th seed firework is as follows:
where
is a Gaussian random number with a mean of 0 and a variance of 1.
- 3.
Mapping Rules
If the offspring fireworks generated during the explosion process or Gaussian mutation exceed the feasible domain of the solution, they need to be pulled back into the feasible domain through a mapping rule. The mapping rule is as follows:
The aforementioned formula ensures that the newly generated offspring resulting from the explosion process and the Gaussian mutation are all within the feasible domain.
- 4.
Population Perturbation Strategy
As the next generation of solutions continues to be optimized, we select the best offspring as the seed firework. However, when no better solution is found after multiple generations of search, it is necessary to consider an appropriate strategy to make significant changes to the firework population. We adopt a population perturbation strategy, where new fireworks are obtained through perturbation, and subsequent searches are conducted. If multiple generations of ineffective searches are reached, population disturbance is triggered, and the worst-performing fireworks in the population are replaced by randomly generated new individuals. In this way, the population will undergo greater explosion and mutation changes, increasing the likelihood of finding a better solution.
- 5.
Local Optimization Strategy
To select several elite solutions as local optimization candidates, employ the insert algorithm for execution of the optimization process. The rules of the insert algorithm are shown in Algorithm 3.
Algorithm 3: Pseudocode of insert operator: Insert operator |
Input: M elitist solutions |
Output: Best Solution |
1: Select M elite solutions from the current iteration and insert each solution to search for optimization in turn. |
2: Choose a position P in the sequence of elite solutions, and generate different solution sequences using EFWA based on the current accessible set J(P) at position P; |
3: Construct a taboo list, and store the newly constructed solutions in the taboo list to avoid redundant construction; |
4: Output the current best solution. |
5. Experiment
This chapter constitutes the experimental section of the paper, including two subsections: the experimental setting and results analysis. First, it introduces the source of the benchmark test cases used in this study. Then, the parameter settings for the MS, CG, and EFWO algorithm are described. Finally, a detailed analysis and discussion are provided for the two experiments, “The Effectiveness of Task Merging” and “Experimental Analysis of Two-Stage Algorithms for SCTSP”. The effectiveness of the CG + EFWA method is demonstrated from the perspectives of “Variation of Optimal Values between EFWA and EACO Algorithms”, “Runtime”, and “Algorithm Stability”.
5.1. Experiment Settings
The test cases were the series of benchmark cases that were developed in [
12]. They created targets with integral priorities randomly changing in [
1,
9], whose latitudes varied from −30° to 60° and longitudes from 0° to 150°. To make the simulation more persuasive, they designed the following: uniform distribution, collective distribution, mixed distribution, which are three different distributions. Time windows between satellites and tasks were calculated by STK 10 (Satellite Tool Kit (Exton, PA, USA)) and each time window lasted about 5–9 s. “Satellite Tool Kit” is a satellite toolkit software developed by the American company Analytical Graphics (
https://www.ansys.com/products/missions/ansys-stk, accessed on 1 June 2024).
The target task set was randomly generated in China. A total of seven groups of test cases were generated, with the number of tasks ranging from 100 to 700, with an incremental step of 100. The satellite observation time was set between 5 to 7 s, and the number of satellites was 3. The field of view angles of the satellites were 3°, 5°, and 8°, with single activation times of 200 s, 150 s, and 180 s, respectively. The slew angle range was 45°, and the stabilization time after activation was 10 s. The storage and energy capacity of a single satellite orbit were set to 100 units each. In this experiment, the priority of observation tasks was defined as the benefit of the observation task. The testing experimental environment was a computer running Windows 10 with a 2.0 GHz CPU and 1 GB of memory. The programming was implemented using Matlab R2014a. The parameter settings for the EFWA are shown in
Table 3.
To validate the effectiveness of the experimental algorithm, the EACO algorithm [
16], which is known for its strength in solving discrete optimization problems, was selected for comparison.
5.2. Results Analysis
To validate the effectiveness of the proposed algorithm, a comparative experimental study was conducted. In the task merging phase, to assess the efficacy of the task merging algorithm, we compared the MS [
14] method with the proposed CG method. In the satellite combined-task scheduling phase, to evaluate the performance of the EFWA effectively, we conducted experimental comparisons between the EFWA and EACO algorithms. The comparative experiments included changes in the optimal value, the running time, and the stability of the two-stage algorithm.
5.2.1. The Effectiveness of Task Merging
To assess the efficacy of the CG task merging algorithm, we conducted an experimental comparative analysis with MS, a density-based clustering method. To evaluate the universality of the CG approach when integrated with various scheduling solution algorithms, during the satellite combined-task scheduling phase (the second stage of the SCTSP), we selected the FWA and ant colony optimization (ACO) algorithms for validation. The experimental outcomes are presented in
Table 4.
Table 4 presents the number of single tasks under four task merging models, “NO” “MS” “CG” and “Allcase”, using the FWA and ACO algorithms. “NO” denotes the single-task observation mode of the satellite; “MS” indicates the use of the MS merging method during the task merging phase; “CG” signifies the use of the CG merging method during the task merging phase; and “Allcase” represents the set of all possible combined tasks that satisfy the task merging constraints.
From the results presented in
Table 4, it was evident that for the SCTSP, regardless of whether the ACO algorithm or the FWA algorithm was used in the second stage, the number of observed tasks obtained in the task merging phase (the first stage of the SCTSP) using the “MS”, “CG”, and “Allcase” methods was higher than in the “NO” scenario. Specifically, the “Allcase” scenario yielded the highest number of observed tasks, while the number of tasks observed in the “MS” and “CG” scenarios was significantly influenced by whether the ACO or FWA algorithm was applied in the second stage. Overall, when the number of tasks in the observation area exceeded 200, the FWA algorithm in the second stage resulted in a higher number of observed tasks.
Figure 5 complements the results presented in
Table 3.
Table 3 shows the number of observed tasks obtained under different two-stage algorithms, with each task assigned a “priority”. The higher the priority, the more urgent the need for the task to be observed. For example, if the priority of task 1 is 6, the satellite will gain a benefit of 6 after observing task 1. Therefore, the higher the total benefit obtained by the algorithm, the better its performance.
Figure 5 presents the observation benefit values of satellites solved by FWA and ACO algorithms under four task merging models: “NO”, “MS”, “CG”, and “Allcase”. The x-axis represents the number of tasks in the observation area, while the y-axis represents the observation benefit of the satellite. When the number of tasks is low (less than 200), the ACO algorithm yields better benefits. However, as the number of observation tasks increases, the FWA algorithm demonstrates superior performance compared to ACO. Overall, the observation benefits obtained using the CG task merging method are better than those of the MS method, particularly as the number of observation tasks increases. The CG + FWA algorithm shows even better observation benefit performance.
5.2.2. Experimental Analysis of Two-Stage Algorithms for SCTSP
To investigate the effectiveness of the EFWA algorithm, we conducted an experimental analysis and comparison with the EACO algorithm in three aspects: the variation of optimal values, the running time, and the stability of the algorithms.
- (1)
Variation of Optimal Values between EFWA and EACO Algorithms
We selected scenarios with different numbers of single tasks in the satellite observation area, including 100, 200, 300, 400, 500, and 700, to demonstrate the revenue under the MS and CG task merging methods for both the EFWA and EACO algorithms. The results are presented in
Figure 5. In each subfigure of
Figure 5, the y-axis represents the observation value of the satellite, and the x-axis indicates the number of iterations of the solution algorithm. The symbols “MS + EACO”, “MS + EFWA”, “CG + EACO”, and “CG + EFWA” are explained in detail in
Table 5.
Figure 6 illustrates the variation in optimal values across the four two-stage algorithms under different task quantities. The findings depicted in
Figure 6 reveal that, irrespective of the algorithm used in the second stage of the SCTSP (either EACO or EFWA), the satellite observation benefits obtained from the CG-based task merging approach in the first stage outperform those from the MS-based method. This advantage is attributed to the CG-based task merging method generating a more diverse collection of merged tasks, thereby offering a broader solution space compared to the MS method.
Compared to the EACO algorithm, the EFWA algorithm demonstrates superior search performance on a larger scale. Consequently, the observation effectiveness varies with the number of tasks in the satellite’s observation area (within China). From
Figure 6, it is evident that the red solid line (CG + EACO) and the purple line (CG + EFWA) exhibit the best performance. Specifically, when the number of tasks is 100, CG + EACO yields the best solution. When the number of tasks is between 200 and 700, the CG + EFWA algorithm performs the best, with its optimal solution providing significantly higher benefits compared to the other three algorithms.
- (2)
Runtime
Table 6 presents the runtime of the four two-stage algorithms. It is evident from the table that the runtime of the EFWA algorithm is more sensitive to the number of tasks. For instance, when comparing “MS + EFWA” with “MS + EACO” (or “CG + EFWA” with “CG + EACO”), the runtime of MS + EFWA/CG + EFWA is shorter than that of MS + EACO/CG + EACO when the number of tasks does not exceed 300. However, when the task count exceeds 400, the runtime of MS + EFWA/CG + EFWA surpasses that of MS + EACO/CG + EACO. As the number of tasks increases, the runtime of EFWA grows significantly, reaching 420 s in the benchmark test with 700 tasks for CG + EFWA.
- (3)
Algorithm Stability
To verify the solution stability of the two-stage algorithms, 10 random experiments were conducted for the four algorithms: “MS + EACO”, “CG + EACO”, “MS + EFWA”, and “CG + EFWA”.
Table 7 presents the variances of several descriptive statistics, including the optimal values, average values, and runtime of the EACO and EFWA algorithms under both MS and CG task merging methods. The iteration count was set to 100. The variances listed in
Table 7 are the sum of the variances from both the task merging stage and combined tasks scheduling stage, hence they are larger than the variances observed in any single phase. Analysis of the variance values in
Table 7 indicates that the EACO and EFWA algorithms exhibit good stability when applied to the task merging methods of MS and CG.
From
Table 7, it is evident that the variances of the optimal values, average values, and runtime under the EFWA label are relatively small, indicating that the solution stability of the EFWA algorithm is better than that of the EACO algorithm. When comparing the stability of “MS + EFWA” and “CG + EFWA”, the three indicators A, B, and C for “CG + EFWA” are all smaller than those for “MS + EFWA”, indicating that the CG + EFWA algorithm exhibits the best stability.
Considering the comparison of the four two-stage algorithms in the aspects of “The Variation of Optimal Values”, “Runtime”, and “Algorithm Stability”, it can be concluded that the “CG + EFWA” algorithm demonstrates significant advantages in terms of both “Optimal Values” and “Algorithm Stability”. However, the runtime is relatively longer. This is mainly due to the EFWA algorithm’s emphasis on “wide-area search”, which leads to a longer solution time. Future research will focus on how to reduce the runtime. Therefore, when comparing different two-stage algorithms, especially in terms of “Optimal Values” and “Algorithm Stability”, the “CG + EFWA” algorithm shows superior performance.
6. Conclusions
In traditional modes, satellites adopt a single-task observation approach, which has the issue of a small number of observational tasks and low satellite resource utilization. To address this, we propose a combined-task observation method based on a multi-task merging mechanism for regions with more than one single tasks. This method reduces task conflicts to improve satellite observational efficiency.
For the SCTSP, we designed a task merging observation method based on a multi-task merging mechanism in two stages: a single-task merging stage and a satellite combined-task scheduling stage.
During the task merging stage, we proved the property that “any complete subgraph in the undirected graph model corresponds to a combined task in SCTSP”. Based on this, we designed the task merging method based on CG for the multi-task merging mechanism. By finding a set of tasks that met the constraint rules, we determined the set of combined tasks.
Although the observation of the multi-task merging mechanism effectively avoids task conflicts, the solution space of the combined tasks is more complex and larger than that of single tasks. Therefore, in the satellite combined-task scheduling stage, we constructed a mathematical description of the SCTSP, considering the angle constraint, the energy constraint, the storage constraint, and the time constraint. Based on the characteristics of the SCTSP problem and the model, we designed a two-stage satellite combined-task scheduling algorithm based on the task merging mechanism—EFWA.
Through extensive experimental analysis, the effectiveness of the CG + EFWA algorithm was validated. Specifically, we verified the superior performance of the CG merging method by analyzing “The Effectiveness of Task Merging”. Additionally, through a comprehensive analysis of “Experimental Analysis of Two-Stage Algorithms for SCTSP”, we confirmed the performance of the CG + EFWA algorithm in terms of “The Variation of Optimal Values”, “Runtime”, and “Algorithm Stability”. It can be concluded that the CG + EFWA algorithm demonstrates significant advantages in both “Optimal Values” and “Algorithm Stability”.
As shown in
Table 8, when the tasks in the observation area are densely populated, such as in the case with 700 tasks, the CG + EFWA method improves the observation benefits by 70.35% compared to CG + EACO, 78.93% compared to MS + EFWA, and 39.03% compared to MS + EACO.
This study employed the ant colony optimization (ACO) and the fireworks algorithm (FWA), primarily due to their excellent performance and application foundation in solving discrete optimization problems. In future research, we plan to explore the satellite combined-task scheduling problem, including how to flexibly respond to the immediate insertion of emergency tasks. Additionally, we will investigate the extension of the application of existing algorithms such as ACO and FWA to the whale optimization algorithm, the seal lion optimization algorithm, and other emerging metaheuristic algorithms, to further verify and enhance the performance and applicability of the algorithms in dealing with discrete optimization problems.