Application of Optimal Scheduling for Synthetic Aperture Radar Satellite Constellation: Multi-Imaging Mission in High-Density Regional Area

Abstract

This study explores optimizing Synthetic Aperture Radar (SAR) satellite constellation scheduling for multi-imaging missions in densely targeted areas using an in-house-developed Modified Dynamic Programming (MDP) algorithm. By employing Mixed-Integer Linear Programming (MILP) to define the mission planning problem, this research aims to maximize observation of high-value targets within restricted planning horizons. Numerical simulations, covering a wide range of target numbers and satellite configurations, reveal the MDP algorithm’s superior mission allocation efficiency, enhanced success rates, and reduced revisit times compared to the greedy algorithm. The findings underscore the MDP algorithm’s improved operational efficiency and planning robustness for complex imaging tasks, demonstrating significant advancements over traditional approaches.

1. Introduction

Remote sensing technologies, particularly satellite-based systems, have revolutionized various sectors, offering unparalleled data for applications like environmental monitoring, urban planning, and disaster management [1]. A significant advantage of satellite-based Earth observation is its capability to operate uninhibited by international borders, providing a comprehensive geographical coverage in a single observational pass. Such an extensive array of applications has led to an ever-increasing demand for Earth observation missions, driving the projected market value close to USD 9 billion by 2027 [2]. Synthetic Aperture Radar (SAR) sensors stand out as versatile tools within this domain. Unlike optical counterparts confined to the visible spectrum, SAR sensors offer a wider range of wavelengths, enabling high-resolution imaging across varying atmospheric conditions. This versatility allows for diverse applications, ranging from hydrological mapping to environmental monitoring [3].

A noticeable paradigm shift in satellite deployment focuses on constellations of smaller satellites instead of a few large platforms [4]. This transition is fueled by diversified mission requirements, including the demand for higher temporal resolutions like shorter revisit times, and the inherent advantages of small satellites such as modularity, cost-efficiency, and shorter development cycles. South Korea aligns well with this global trend, planning to deploy small satellites comprising over 130 units by 2030 [5,6]. Internationally, entities like Finland’s ICEYE [7,8,9] and the United States’ Capella Space [10,11] have already successfully deployed SAR satellite constellations, underlining the global consensus on their utility and efficiency.

Following this trend, there is an increased complexity and frequency in mission planning. For instance, while a Sun-synchronous orbiting large satellite may revisit the Korean Peninsula every 12 h, a constellation of 40 smaller satellites in inclined orbits could accomplish this in intervals as brief as 30 min [12]. This augmented observational capability necessitates a corresponding increase in planning intricacy. Traditional approaches of programming each satellite’s mission individually are becoming impractical due to the required human resources. Furthermore, advancements in satellite attitude control technologies have led to highly maneuverable platforms, while payload enhancements enable a diverse range of imaging modes for Earth observation [13].

In addition to the agility of these satellites, advancements in payload sensor technology now allow for more versatile observational strategies. Previously, focus was placed on observing a single target or area. However, recent developments enable multiple imaging modes, such as multi-stripmap or spotlight mode, allowing for the capture of multiple targets in a single pass as shown in Figure 1. These capabilities, combined with the aforementioned advancements, add layers of complexity to the mission planning process and emphasize the crucial need for optimized strategies for the entire satellite constellation [14].

Literature Review

Optimized mission planning in satellite operations has attracted significant scholarly attention, leading to a variety of research methodologies. While traditional mathematical models often rely on Mixed-Integer Linear Programming (MILP) [15] and make use of established solvers like Gurobi, CPLEX, and Xpress, they also explore algorithms such as Branch-and-Bound (BB) [16] and Dynamic Programming (DP) [17]. These approaches have been tailored to suit different satellite configurations, including both agile [18] and non-agile types [19], as well as to interact with ground stations [20]. In addition to MILP-based studies, meta-heuristic methods like Genetic Algorithms (GAs) [21,22,23], Ant Colony Optimization (ACO) [24], and Particle Swarm Optimization (PSO) [25] have gained traction for complex scenarios, especially those requiring rapid response, such as natural disasters [26]. With the rise of Artificial Intelligence (AI), the field has seen a paradigm shift toward utilizing machine learning algorithms. Deep Reinforcement Learning (DRL) [27,28,29], in particular, is carving a niche for itself, offering enhanced capabilities in autonomous mission planning and a wide range of applications from online scheduling [30] to Agile Earth Observation Satellite (AEOS) planning [31].

In recent advancements, Stephenson and Schaub [32] explored the optimization of sequential target imaging scheduling for agile satellites using neural network function approximators to model transition times, enhancing the efficiency of MIP formulations. Similarly, Boshuizen et al.’s patent [33] on Earth Observation Constellation Methodology & Applications presented a method for deploying a constellation of satellites capable of capturing high-resolution planetary images in a week or less, emphasizing simplicity in satellite control for effective imaging. Further, Eddy and Kochenderfer [34] demonstrated the application of Semi-Markov Decision Processes (SMDPs) for optimizing satellite imaging plans across 1000 locations, leveraging forward search and Monte Carlo tree search to outperform traditional methods. Berger et al. [35] addressed the scheduling and task assignment for satellite clusters, utilizing the QUadratically constrainEd program Solver Technology (QUEST) based on the CPLEX problem solver, showcasing its superiority over established heuristics such as MYopic Planning-based Image aCquisition heuristic (MYPICC) and Genetic Algorithm-based collecTion scHedulER (GATHER).

In addition, the research landscape for satellite mission planning has evolved to address the distinctive challenges presented by satellite clusters. Recent studies have taken steps to optimize mission planning for satellite constellation, acknowledging their rising significance in space missions. Iacopino et al. [36] introduced the Mission Planning System (MPS), developed by Surrey Satellite Technology Ltd (SSTL), as a tool for planning Electro-Optical (EO) imaging tasks for small clusters of satellites. Moreover, Zheng et al. [37] extended optimization techniques to satellite swarms, specifically for onboard scheduling via a Hybrid Dynamic Mutation Genetic Algorithm (HDMGA). Cui and Zhang [38] tackled the problem of scheduling and assigning imaging missions and emergency tasks for clusters of up to five satellites with varying target priorities, ranging from 25 to 200. Lewis [39], on the other hand, utilized weighted-sums optimization algorithms to optimize mission planning for cubesat clusters. Furthermore, addressing the increasing challenge of orbital debris monitoring, Cardona et al. [40] introduced Networked Instrument Coordinator for Observations on debris (NICO), a scheduling system that utilizes genetic algorithms for efficient debris observation. This innovation showcases the expanded applicability of scheduling methodologies from traditional Earth observation to the critical areas of space safety and debris monitoring.

Existing research has provided valuable methodologies for optimizing mission planning for a limited number of individual satellites, particularly in the context of Earth imaging and communication objectives. However, there is a relative scarcity of research focused on satellite constellations, aligning with the recent trend in satellite development. Additionally, the current body of work often relies on widely used meta-heuristic algorithms [21,22,23,24,25,26] for mission planning optimization. These algorithms, while effective in certain scenarios, tend to fall into local optima and lack consistency in producing identical results in each iteration. Furthermore, the emerging DRL-based algorithms [27,28,29,30,31], though beneficial for their real-time computation capabilities, encounter inherent limitations in untrained areas, struggling to rectify inappropriate solutions, which poses a challenge for immediate application in required high-robustness ground station mission planning subsystems. This highlights a significant gap in the existing research, particularly in addressing mission planning scenarios involving numerous targets densely distributed within specific regional areas.

Recognizing these limitations, our research offers three contributions that aim to bridge these gaps. First, it broadens the scope of mission planning optimization to encompass satellite clusters, with a specific emphasis on South Korea’s emerging small SAR satellite constellation that has been relatively underexplored in the realm of satellite mission planning research. Second, we employ a Modified Dynamic Programming (MDP) algorithm, developed in-house [41], that surpasses traditional methods in adaptability to time-varying conditions and ensures the optimal solutions while effectively managing dynamic constraints. Lastly, our work uniquely focuses on the optimization of multi-imaging mission scheduling for high-density target regions with varying levels of significance and urgency, a challenging scenario in satellite mission planning. In summary, our research offers both a theoretical framework and practical applications for optimizing complex SAR satellite constellation operations, delivering actionable insights and robust solutions.

The remainder of this paper is organized as follows: Section 2 provides an overarching framework of the imaging mission, elaborating on the mathematical models that encapsulate the problem under study. In Section 3, we develop into the optimization algorithms, with a particular focus on the MDP algorithm developed by our team. For comparative analysis, this section will also introduce the widely utilized greedy algorithm as the heuristic approach employed in this paper. Section 4 delineates the numerical simulation scenarios and presents the resultant findings. Lastly, Section 5 offers concluding remarks and outlines potential avenues for future research.

2. Problem Definition

2.1. Imaging Mission Description

In this study, the concept of an “imaging mission” is expanded to include a comprehensive series of processes in Earth observation satellite operations. These encompass not only the remote sensing tasks where satellites equipped with sensors capture images of designated terrestrial regions but also the entire sequence of steps from initial user request to the final delivery of processed images. This intricate process is initiated with the user’s requirements, which detail the desired area for observation, level of importance, resolution, and other specifications. These requirements are then compiled and conveyed to the ground station. At the ground station, an initial imaging acquisition plan is formulated, taking into account the user’s needs. Following this, a comprehensive review of the satellite’s orbit and status information is conducted to establish an optimized imaging mission plan. As depicted in Figure 2, the process flow is represented by various colored lines: the blue line denotes the flow of user requirements, while the green line indicates the flow of information about the satellite, such as its orbit and status. These elements are integrated in the mission scheduling subsystem to develop an optimized imaging mission plan, which is then communicated to the satellite via S-band telemetry. Once the imaging plan is received, a cluster of satellites executes the mission as per the instructions and transmits the raw data back to the ground station using X-band communication, illustrated by the red line in Figure 2. These data undergo a series of corrections and post-processing steps before being rendered as a calibrated image product, ready for delivery to the user. The focus of this paper is primarily on the integration of user requirements with satellite information to establish an optimal imaging mission plan for satellite constellation, ensuring that the entire imaging mission is conducted efficiently, meeting the specific needs of the users.

2.2. Problem Modeling

This chapter describes how key subsystems are mathematically modeled for optimal scheduling based on the imaging mission flow as depicted in Figure 2.

Table 1. Notation.

Variable	Definition
i	Index number of target candidates, $i\in \left\{1,...,\left|I\right|\right\}$
j	Index number of satellites, $j\in \left\{1,...,\left|J\right|\right\}$
k	Index number of visible time windows, $k\in \left\{1,...,\left|V_{ij}\right|\right\}$
l	Index number of time intervals, $l\in \left\{1,...,\left|T_j\right|\right\}$
I	Set of target candidates
J	Set of satellites
$V_{ij}$	Set of visible time windows of target i by satellite j
$T_j$	Set of time intervals by satellite j
$v_{ijk}$	kth visible time window of target i by satellite j
$t_{jl}$	lth time interval by satellite j
$x_{ijk}$	Decision variable of target observation in $v_{ijk}$
$t_{jl}^s$	Start time of $t_{jl}$
$t_{jl}^e$	End time of $t_{jl}$
${\tau }_{ijk}^s$	Start time of observation in $v_{ijk}$
${\tau }_{ijk}^e$	End time of observation in $v_{ijk}$
${\tau }_{ijk}^o$	Observation time duration in $v_{ijk}$
${\tau }_j^g$	Gap time of satellite j
$d_j$	Duty time per pass of satellite j
$p_i$	Profit obtained when observing target i
$s_i$	Significance measure of target i
$u_i$	Urgency measure of target i
$\alpha ,\beta$	Weighting factor

summarizes the definitions of the variables used in the modeling.

2.2.1. User Requests

Satellite imaging missions commence with user requests, and in the scheduling of these missions, the requirements of the users are the most critical considerations. Therefore, the foremost factor to prioritize in mission scheduling is the parameters related to the targets requested for imaging by the users. In this study, “significance $\left(s_i\right)$” is a measure that reflects the hierarchy of importance of the targets desired for imaging from the user’s standpoint, while “urgency $\left(u_i\right)$” indicates the time sensitivity concerning the user’s need for images of the target. To enhance our mission scheduling approach, we adopt the Eisenhower matrix [42] as a guiding framework in Figure 3. This matrix, dividing tasks based on their significance and urgency, creates a comprehensive nine-cell grid, each cell representing a combination of low, medium, and high levels of these two dimensions, with low assigned a value of 0.3, medium a value of 0.6, and high a value of 0.9. The profit $\left(p_i\right)$ derived from imaging a target is then determined by combining the target’s significance and urgency with the weighting factors $(\alpha ,\beta )$. Specifically, the profit for a target with the highest significance and urgency is calculated as $\alpha \times 0.9+\beta \times 0.9$, reflecting the structured approach to prioritize satellite imaging tasks. This enables a nuanced prioritization of imaging tasks, facilitating a strategic allocation of satellite imaging resources to address the most pressing and significant targets first. This strategic application of the matrix is expressed in the following Equation (1):

$$p_i=\alpha s_i+\beta u_i$$

(1)

2.2.2. Satellite Information

The performances of available satellites and payloads, as well as orbital information, are also very important considerations in making imaging schedules. In this study, the satellite is a small satellite under 500 kg equipped with an active phased array SAR sensor. The satellite’s orbital motion is simulated using the J2 Perturbation propagator in the Systems Tool Kit (STK) program, forming a Walker Delta constellation with a total of 40 satellites. This use of J2 perturbation reflects the study’s emphasis on optimal imaging planning rather than precise orbit prediction, with the model providing a sufficient balance between simplicity and the accuracy required for our analysis. More specific parameters will be mentioned in Section 4.1, Test Scenario. There are two assumptions related to the satellite in this study: 1. It is assumed that communication between the ground station and the satellite for transmission and reception is out of research scope, and that the satellite has already received the imaging scheduling command; 2. Contingencies such as functional failures of available satellites are not considered, and it is assumed that all satellites are operating normally.

2.2.3. Visible Time Window (VTW)

In this study, the concept of a Visible Time Window (VTW) is introduced to define the feasible opportunities for imaging a target with a specific satellite based on the user request and satellite information data. Figure 4 illustrates a scenario where a single satellite aims to capture images of 1000 targets over a 7-day period. Derived using the STK 11, these VTWs serve as crucial input parameters for optimization algorithms, which are tasked with formulating the most efficient imaging scheduling strategy. The analysis reveals that, on average, approximately 1000 VTWs are generated each day, culminating in nearly 7000 VTWs over the course of a week. These data suggest a proportional increase in VTWs with more satellites, a greater number of targets, and longer scheduling periods. Consequently, the effective application of optimization algorithms becomes increasingly essential to establish efficient imaging schedules, highlighting their critical role in managing the growing number of VTWs.

2.2.4. Objective Function

The mission planning problem for satellites is mathematically modeled using the Mixed-Integer Linear Programming (MILP) approach, which has been employed in previous research [15,16,18,19]. The decision variable is formulated as a binary variable, as shown in Equation (2), where it takes a value of 1 if a target is imaged and 0 otherwise. Specifically, $x_{ijk}$ represents the variable indicating whether target i is observed by satellite j during the kth VTW.

$$x_{ijk}\in \left\{0,1\right\}$$

(2)

The objective function of the imaging mission scheduling model, as defined in Equation (3), aims to maximize the number of imaged targets, prioritizing targets with higher profits $\left(p_i\right)$. Therefore, the focus is on maximizing the total profit of the imaging sequence by strategically selecting targets rather than simply capturing a large quantity of images.

$$\mathrm{maximize}\sum _{i\in I}\sum _{j\in J}\sum _{k\in V_{ij}}{p}_i{x}_{ijk}$$

(3)

2.2.5. Constraints

The constraints corresponding to the objective function are defined in Equation (4) through (8):

$$n_i^{min}\le \sum _{j\in J}\sum _{k\in V_{ij}}{x}_{ijk}\le n_i^{max}\mathrm{for}i\in I$$

(4)

$$\sum _{i\in I}\sum _{j\in J}\sum _{k\in V_{ij}}{\tau }_{ijk}^o{x}_{ijk}\le \sum _{j\in J}{d}_j$$

(5)

$$t_{jl}^s\le {\tau }_{ijk}^s\mathrm{and}{\tau }_{ijk}^e\le t_{jl}^e\mathrm{for}i\in I,j\in J,k\in V_{ij},l\in T_j$$

(6)

$${\tau }_{ijk}^s+{\tau }_{ijk}^o\le t_{jl}^e\mathrm{and}{t}_{jl}^e=t_{jl+1}^s\mathrm{for}i\in I,j\in J,k\in V_{ij},l\in T_j$$

(7)

$${\tau }_{ijk}^e+{\tau }_j^g\le {\tau }_{i^{\prime }jk}^s\mathrm{for}i\ne i^{\prime },i,i^{\prime }\in I,j\in J,k\in V_{ij},l\in T_j$$

(8)

-

Equation (4) represents the constraint regarding the minimum and maximum number of times that a target is observed. This constraint is modeled within a range to accommodate multiple imaging of the same target as per user requirements, and it is not set as a constant to allow for future model scalability.

-

Equation (5) pertains to the maximum observation time available for a satellite during one pass over the mission area. Various limitations of the satellite, such as power, thermal balance, and memory capacity, identified from the satellite development stage, are integrated into a single variable termed “duty time $\left(d_j\right)$”. Therefore, this constraint ensures that the actual imaging mission time of the satellite does not exceed this duty time.

-

Equation (6) is a constraint necessary for the application of the MDP optimization algorithm used in this study. It relates to each time interval in the sub-problem formation, indicating that the start time of the time interval should be set before the imaging starts, and the end time of the interval after the imaging ends.

-

Equation (7), also related to the MDP algorithm, expresses the constraint that the imaging mission must be completed within each respective time interval. These time intervals serve as a fundamental criterion for segmenting the total targets within the mission area into several grouped segments. This segmentation considers the VTW, observation time, and gap time, ensuring that the end of the lth interval aligns seamlessly with the start of the $(l+1)$th interval. Such alignment is critical for the effective implementation of dynamic programming, which tackles the larger problem by sequentially addressing these interconnected sub-problems, each defined by its distinct segment.

-

Equation (8) addresses the requirement for a guaranteed gap time between consecutive imaging targets. This is a critical condition, especially for multi-imaging missions using active phased array SAR sensors, and is essential in determining the next target post-imaging of the current one.

Figure 5 illustrates the constraints mentioned above, including the VTW, observation duration time, gap time, and time intervals. It visualizes various conditions required during consecutive imaging missions. In Figure 5, satellite j selects and images the kth VTW of target i, $i+2$, and $i+4$, ensuring an appropriate gap time between the targets, as depicted schematically.

3. Optimization Algorithm

3.1. Data Preprocessing

Before the optimization, an operation is carried out to place each $v_{ijk}$ for $V_{ij}$ within the interval $T_j$ for each satellite j. Based on the Equations (6)–(8), $v_{ijk}$ is placed on each interval $t_{jl}$. Figure 6 describes the process of placing a target in each interval $t_{jl}$ of the total interval $T_j$ and creating connections between targets in neighboring intervals. The process starts by placing a target in each interval. If it traverses each interval $t_{jl}$ and the target’s observation start and end time satisfy the interval inclusion condition, the target is defined to belong to $t_{jl}$. To reduce unnecessary computation, if a target that does not belong to $t_{jl}$ is encountered consecutively, the definition is terminated, and the same operation is performed in the next interval $t_{jl+1}$. After the placement of targets for all intervals $T_j$ is finished, connection information between each target in neighboring intervals $t_{jl}$ and $t_{jl+1}$ is created based on the azimuth of the targets. The pseudo code of the interval data preprocessor is described in Appendix A.1, Algorithm A1.

3.2. Modified Dynamic Programming (MDP)

The Modified Dynamic Programming (MDP) algorithm is an advancement developed by our research team based on deterministic Dynamic Programming (DP). Recognized for its optimal methodology in managing time-varying systems, such as satellite mission planning, DP faces challenges when the number of variables and the problem space expand, leading to an exponential increase in computational demand (curse of dimensionality) [43,44]. To address this, our team developed the MDP algorithm, which has been successfully implemented in mission planning for multiple agile satellites equipped with EO/IR payloads [41]. Further refining this approach, the current paper extends the MDP algorithm’s application to mission planning for satellite constellations carrying SAR payloads, demonstrating its adaptability and enhanced performance in complex operational contexts.

Figure 7 shows the overall procedure of MDP. The operation is performed based on the interval $T_j$, and the target connection information between neighboring intervals. MDP employs a recursive strategy until a predefined termination criterion is met, delving into the interval’s depth. Upon meeting the termination criterion, MDP reverses its exploration order, updating the schedule by leveraging the connection data. Upon completion of this reverse exploration, the schedule with the highest profit is selected as the final result. The pseudo code of the MDP algorithm is provided in Appendix A.2, Algorithm A2.

3.3. Greedy Algorithm

To facilitate a comparative analysis of optimization algorithms, this study adopts the widely used greedy algorithm for solving mission planning problems. Drawing inspiration from the greedy algorithm outlined by Cho et al. [15], we have refined this approach to suit the mission scheduling of satellite constellation. Figure 8 shows the overall procedure of the greedy algorithm. It also utilizes the same information about the intervals and the connectivity of the targets between neighboring intervals. However, unlike MDP, it does not perform the operations in the reverse order of intervals. Instead, it commences from the initial interval $t_{jl}$ within $T_j$ and updates the schedule according to the most profitable target linked with the preceding interval. The pseudo code of the greedy algorithm is expressed in Appendix A.3, Algorithm A3.

4. Experimental Results

4.1. Test Scenario

The satellite system under consideration is a cluster satellite configuration, specifically a Walker Delta constellation. This constellation is comprised of eight planes, with satellites ranging from 1 to 5 per plane, amounting to a maximum of 40 satellites. These satellites orbit at an altitude of 500 km and are equipped with state-of-the-art active phased array Synthetic Aperture Radar (SAR) sensors. The orbital trajectories and configuration of this satellite constellation are graphically represented in Figure 9, providing a clear visual understanding of the spatial arrangement.

Targets are randomly generated within the geographic boundaries of the Korean Peninsula, between latitude 32–42^∘ N and longitude 124–131^∘ E, with their count progressively increasing from 100 up to a maximum of 1000 in increments of 100. Figure 10 illustrates the spatial distribution of these targets within the mission area. Additionally, each target is randomly assigned a urgency and significance value, chosen from 0.3, 0.6, or 0.9, adding layers of complexity to the target prioritization process.

The mission planning period is set from 00:00 on 1 January 2024 to 00:00 on 8 January 2024, spanning 7 days. The test scenarios involve varying numbers of satellites, from 8 (one per plane) to 40 in total, and targets ranging from 100 to 1000. This results in 50 unique test cases for the numerical simulation. Detailed simulation parameters are listed in

Table 2. Simulation parameters.

Parameter	Value
Scheduling period (day)	$\left\{1,2,3,4,5,6,7\right\}$
Mission area (∘)	32–42∘ N, 124–131∘ E
Number of targets	$\left\{100,200,300,400,500,600,700,800,900,1000\right\}$
Walker Delta constellation	44.1∘: 40/8/1
Altitude (km)	500
Incidence angle (∘)	25–45
${\tau }_{ijk}^o$ (s)	20
${\tau }_j^g$ (s)	10
$d_j$ (s)	60
$n_i^{min}$, $n_i^{max}$	1
$p_i$, $u_i$	$\left\{0.3,0.6,0.9\right\}$
$\alpha ,\beta$	0.7, 0.3

.

The simulation environment is a crucial aspect, primarily focusing on the computing power and related resources required for the effective execution of the simulation. The specific simulation environment is provided in

Table 3. Simulation environments.

Index	Specification
Processor	Intel® Core™ i7-11700
Memory (RAM)	32 GB
Orbit analysis tool	AGI® STK (Systems Tool Kit)
Orbit propagator in STK	J2 perturbation
Implement tool	VS Code
Framework	Python 3.10

.

The workflow of our simulation is a multi-step process, initiated with user-inputted target information and satellite parameters fed into the STK program. Utilizing this input, STK generates target data and propagates satellite orbit. A critical output of this process is the VTW report, which becomes the foundational input for the MDP and greedy algorithms, both written in Python language. These algorithms are used to derive the solution of the optimal mission scheduling. The entirety of this workflow, from initial input to final algorithmic processing, is depicted in Figure 11, offering a comprehensive visual guide to the simulation process.

4.2. Mission Allocation

Mission allocation refers to the outcomes produced by optimization algorithms in response to user-requested mission assignments. In Figure 12, the mission allocation results are depicted over a single day for all test cases, spanning from 100 to 1000 targets. The scenarios involve different numbers of satellite constellations (8 to 40) and apply two algorithms, MDP and greedy. The upper graph illustrates the number of observed targets, representing the sum of instances where the binary decision variable $x_{ijk}$ is equal to 1. In simpler terms, it reflects the total count of occasions when targets are successfully observed, excluding the profit $\left(p_i\right)$ gained from observing a target in the objective function. Meanwhile, the lower plot corresponds to Equation (3), revealing the objective function value of total profit derived from target observation. This calculation includes the profit associated with each target. In essence, the lower plot provides a comprehensive overview of the objective function value, taking into account the profits obtained through capturing individual targets.

Figure 12 illustrates an increasing trend in mission allocation results with a growing number of targets and satellites. Notably, the MDP algorithm consistently outperforms the greedy algorithm. As the number of targets increases, the impact of an increased number of satellites on mission allocation results becomes more evident, along with the growing disparity between the MDP and greedy algorithms. Moreover, when maintaining the same number of satellites, the mission allocation results tend to converge even as the number of targets increases, suggesting a threshold beyond which adding more targets has a limited effect on the number of successfully allocated missions. For example, with eight satellites, the number of missions stabilizes at approximately 180, even as the number of targets increases to 1000. This phenomenon enables mission planners to determine the optimal number of satellites required based on the number of targets.

4.3. Mission Success Rate

To evaluate the efficacy of the mission plan in response to user requests, this study employs the mission success rate, a key concept in mission analysis being utilized by the Korea Aerospace Research Institute (KARI) [45]. Equation (9) signifies the ratio of obtained profit to the total profit when successfully observing all targets. Equation (10) expresses the ratio of observed targets to the total targets requested by the user.

$$\mathrm{Mission}\mathrm{success}\mathrm{rate}\mathrm{for}\mathrm{profit}(\%)=\frac{\sum \sum \sum p_i{x}_{ijk}}{\sum p_i}\times 100$$

(9)

$$\mathrm{Mission}\mathrm{success}\mathrm{rate}\mathrm{for}\mathrm{target}\mathrm{observation}(\%)=\frac{\sum \sum \sum x_{ijk}}{\left|I\right|}\times 100$$

(10)

Figure 13a illustrates the mission success rates achieved with 40 satellites and 500 targets over a day, utilizing both the MDP and greedy algorithms. The MDP algorithm reached a 100% mission success rate at around 17:50, surpassing the greedy algorithm, which reached the same rate at around 23:50. The efficiency of the mission planning process is highlighted by MDP’s ability to complete all missions in a shorter timeframe than greedy, despite having an identical number of targets and satellites. These findings are further detailed in Figure 13b, depicting outcomes when extending the mission planning period from 1 day to 7 days. Notably, MDP, after 4 days, attained a profit of 91.0% and target observation of 86.4%, whereas greedy achieved only 68.3% and 69.2%, respectively. Furthermore, considering the completion of a 7-day mission plan, MDP realized success rates of 95.2% and 92.4%, while greedy demonstrated a significantly lower success rate of 75.0% and 76.2%, revealing an approximately 20% difference in mission success rates.

Upon examining the correlation between the number of observed targets and resulting profit, it becomes evident that while greedy consistently displays an increase in both metrics throughout all time periods, MDP consistently achieves a higher profit relative to the number of observed targets. Starting from the 4th day onward in Figure 13b, the objective function value in the case of the greedy algorithm starts to fall below the target observation value. This observation underscores the clear alignment of MDP with the problem’s objective function, emphasizing the prioritization of high-profit target observation. These data described in Figure 13 can serve as a valuable reference for analyzing the completion of user-requested missions within the available satellite resources during the mission planning phase. To summarize, the outcomes indicate that the quantity of observed targets and resulting profits depend on the number of satellites and the planning horizon. The efficacy of the MDP algorithm is demonstrated by its adept implementation of the problem’s objective function. Employing the mission success rate as a metric proves instrumental in evaluating the efficiency of incorporating users’ requests into the mission plan.

4.4. Revisit Time

Revisit time is a crucial figure of merit (FOM) in satellite mission planning, representing the periodicity of a satellite’s return to a designated imaging target or region. In Figure 14, the mean revisit time is depicted based on the profit associated with each target under a test scenario involving a constellation of 16 satellites observing 100 targets five times over a 7-day period. It is calculated as the temporal difference between the initiation of the first observation and the conclusion of the fifth, divided by four intervals. Target profit is determined by Equation (1), categorized into nine segments. Figure 14 illustrates that, across all target profit segments, the mean revisit time for the MDP algorithm consistently outperforms that of the greedy algorithm. Furthermore, the outcomes of linear regression fitting, as expressed in Equations (11) and (12), indicate that MDP exhibits a steeper slope and a smaller y-intercept.

Delving into more detailed analysis, the mean revisit time for MDP at the lowest profit of 0.3 is 9.02 h compared to 10.56 h for the greedy algorithm, and, at the highest profit of 0.9, MDP’s mean revisit time significantly shortens to 3.2 h versus 5.1 h for greedy. This trend demonstrates that the difference between the two algorithms becomes more pronounced with increasing profit. The slope of the graph indicates that MDP is more effective at capturing as many high-profit targets as possible within the constraints of satellite mission planning.

Following this detailed analysis, it becomes pertinent to examine how this research diverges from prior work. Previous studies [12,46,47] have predominantly aimed at optimizing satellite constellations and orbits to reduce the mean revisit time to tens of minutes across areas such as the Korean Peninsula, often treating it as a single, uniform target for system-level performance evaluations. Contrary to this approach, the present study advances by accurately calculating the mean revisit times for individual targets within specific regions, thereby offering a more refined analysis. This shift from a broad, areal focus to a targeted, precise evaluation underscores the novelty and significance of our approach, setting it apart from earlier methodologies.

$$\mathrm{MDP}\mathrm{Fit}\mathrm{Line}:\mathrm{y}=-9.70\mathrm{x}+11.93$$

(11)

$$\mathrm{Greedy}\mathrm{Fit}\mathrm{Line}:\mathrm{y}=-9.10\mathrm{x}+13.29$$

(12)

For a quantitative analysis of the results dataset, we present the mean revisit time using a box plot in Figure 15, along with key statistical metrics in

Table 4. Statistics of mean revisit time.

Statistic	MDP (Hour)	Greedy (Hour)
Mean	6.08	7.80
Standard deviation	3.77	6.00
Minimum	1.48	0.78
25th percentile	3.20	3.48
Median	5.13	6.25
75th percentile	8.23	9.49
Maximun	17.84	23.56

The bold text indicates the best parameter values for the two algorithms.

. As illustrated in both Figure 15 and Table 4, the MDP algorithm exceeds greedy’s performance in all metrics, excluding the minimum value. Notably, the standard deviation and presence of outlier values are significantly reduced in the case of the MDP algorithm. This emphasizes that the efficacy of the MDP algorithm is demonstrated in the satellite mission planning domain, where a robust algorithm is essential.

4.5. Computation Time

Figure 16 presents the computation times for the MDP and greedy algorithms as functions of the total number of targets, with the data displayed on a logarithmic scale. This visualization underscores the correlation between increased computation times and the rising numbers of both targets and satellites. It specifically highlights the exponential growth in computational demand as the number of satellites increases, a factor that is precisely plotted to illustrate its impact on computational time. Upon detailed analysis, it becomes apparent that the volume of targets exerts a more substantial impact on the computational complexity than does the satellite count. This augmented complexity primarily arises from the intricacies of generating sub-problems. Specifically, as the target count increases, the task of calculating each target’s visibility window and the intervals between them necessitates a significant escalation in computational resources.

A comparative assessment reveals that, across all tested scenarios, the greedy algorithm outperforms the MDP algorithm in computation time, especially in complex scenarios involving 1000 targets, where greedy’s computation time is merely 101 s compared to MDP’s 998 s. This efficiency of greedy stems from its strategy of optimizing each sub-problem individually for immediate results, in contrast to MDP, which assesses the overall benefit pathway, leading to a more thorough optimization at the cost of longer computation times. However, despite its DP-based nature, MDP manages to complete even the most computationally demanding scenarios within a reasonable timeframe. With advancements in computing powers such as CPU and RAM, it is feasible to significantly reduce computation times, establishing the MDP algorithm’s suitability for satellite constellation mission planning by providing higher objective function outcomes efficiently. This underscores the need to balance algorithmic efficiency with optimization potential in computational resource allocation for complex tasks.

Furthermore, an interesting aspect of the computation times for both the MDP and greedy algorithms emerges when considering the interplay between the number of targets and satellites. While the computation time for the greedy algorithm increases directly with the number of targets and satellites, the MDP algorithm displays a more complex pattern of behavior. Specifically, scenarios with a lower count of satellites have occasionally demanded more computational time than those with a higher count. This observation is tied to the mission success rates discussed in Section 4.3. For example, an MDP scenario with 40 satellites and 1000 targets reaches a 100% mission success rate by 3 January, whereas, with only 8 satellites, a 95% success rate is only achieved by 7 January. This indicates that scenarios with fewer satellites, despite their reduced satellite count, incur greater computational demands due to the prolonged duration required to achieve mission success. In contrast, scenarios employing the greedy algorithm for 1000 targets fail to reach a 100% mission success rate by 7 January, regardless of the satellite count, necessitating ongoing mission planning throughout the seven-day period. This scenario accounts for the relatively shorter computation times observed in situations with fewer satellites.

5. Conclusions

This research utilizes an MDP algorithm, developed in-house [41], aimed at optimizing imaging mission schedules for SAR satellite constellations. The core of this study lies in addressing the challenges of scheduling in regions with a high density of targets, showcasing the algorithm’s effectiveness by contrasting it with the greedy algorithm, which is widely used in existing literature. The formulation of the problem utilizes MILP to ensure the observation of the maximum number of high-profit targets within a set planning horizon.

Critical to the mission planning process, parameters such as VTWs, time intervals, and gap times are calculated through satellite orbit propagation using the STK software. The MDP algorithm, by segmenting the mission planning into discrete time intervals based on VTWs, strategically schedules consecutive target imaging. This includes calculating both the observation time duration and gap time to establish a comprehensive schedule for target imaging across various test scenarios. Additionally, this study provides a comparative analysis of optimal sequencing strategies for imaging targets utilizing both the MDP and greedy algorithms.

For the numerical simulations, the mission area around the Korean Peninsula is set, with 100 to 1000 targets of various levels of significance and urgency. The satellite constellation, equipped with SAR sensors, is configured as a Walker Delta constellation comprising five inclined orbits, with the satellite count ranging from 8 to 40, over a 7-day mission planning period. The evaluation of 50 test scenarios using both the MDP and greedy algorithms yielded significant findings as follows:

1.

In mission allocation analysis, the quantity of satellites significantly impacts the observation strategy, diminishing the importance of the total number of targets. This highlights the crucial role of satellite count in enhancing observation efficiency and profitability, despite the limited benefits of increasing target numbers.

2.

Across all scenarios, the mission success rate for profit surpasses that for target observation, validating the goal of maximizing profit through prioritizing high-value targets—a strategy effectively implemented by the MDP algorithm.

3.

Analysis of revisit times reveals that targets of higher value benefit from shorter intervals between observations. Confirmed by box plot analysis, this result highlights the robustness of the MDP algorithm.

Lastly, the MDP algorithm, despite taking more time than the greedy algorithm, consistently achieves better outcomes in mission allocation, success rates, and revisit times. With advancements in computing power, the computational efficiency of MDP can be enhanced, making it a more suitable choice for complex satellite mission planning.

A notable limitation in our study is the assumption that all satellites function without failure throughout their missions. This overlooks potential operational contingencies, such as technical failures, that could impact mission planning and execution. Addressing this limitation, future research will incorporate the consideration of satellite failures and the necessary re-planning of imaging tasks. This inclusion will provide a more realistic approach to satellite mission planning, acknowledging the complex and unpredictable nature of space operations. Also, we plan to broaden the optimization scope to encompass both imaging missions and communication planning with ground stations. As ground stations become more globally accessible, satellite communication planning emerges as being equally vital as imaging scheduling. This expansion includes integrating tasks such as receiving commands from ground stations, conducting imaging missions, and then transmitting the raw data back to Earth. By optimizing this whole mission workflow, we aim to significantly improve the operational efficiency of satellite constellations.