Solving the Agile Earth Observation Satellite Scheduling Problem with CP and Local Search

Let $ℛ$ be a set of customer requests. A request $r$ involves observing an area split into a set ${ℳ}_r$ of meshes. Requests can be repeated, hence we define the set ${𝒫}_r$ of those repetitions. For instance, there can be a request to observe the area around Glasgow, which is decomposed into a grid of meshes covering the city, with a two-hour period during the CP 2025 conference.

The constellation we consider has a set $𝒮$ of satellites, that can be used to observe a mesh for a given period. Such an action is called an acquisition opportunity, although we shall use acquisition for short. Let $𝒜$ be the set of acquisitions. We define the subset ${𝒜}_{r,t,m}$ as the set of possible acquisitions of the request $r$ for the period $t$ and the mesh $m$, and ${𝒜}^s$ as the subset of acquisitions which can be made by satellite $s$. Each acquisition $a$ has a duration $p_a$ to make that observation, which must occur during a time window $[r_a,d_a]$. It is associated to a profit $v_a$, and it consumes a quantity of memory ${\gamma }_a$. Satellites may have some acquisitions in memory at the beginning of the planning period. For each satellite $s$, ${ℱ}^s$ is the set of such acquisitions, and we note $ℱ={\cup }_{s\in 𝒮}{ℱ}^s$. There can be many alternative acquisitions for the same observation task (i.e. a mesh for a given period), since the same image can be shot by different satellites or the same satellite on different orbits. Therefore, the goal is to select acquisitions among the many alternatives, so that as many requests as possible are fulfilled.

Then, the acquisitions must be scheduled. As satellites need to maneuver in order to aim at their targets (i.e. to observe a mesh), there are transition times between successive acquisitions performed by the same satellite. In agreement with our industrial partner and in line with other works in the literature [3], we assume that transition times are time-independent. Thus, $T(a_1,a_2)$ is the transition time between two acquisitions $\{a_1,a_2\}\subseteq {𝒜}^s$ on a satellite $s$.

Finally, a network of ground stations (GS) are used to download the observations. For each acquisition $a$, there is a set ${𝒲}_a$ of possible download windows. A download time window $w$ is a time window $[r_w,d_w]$ during which acquisitions can be downloaded. It has a total capacity ${\gamma }_w$ which is the product of its bandwidth by its duration. Each satellite $s$ has a memory capacity $C_s$.

Memory management is the second part of the problem. It consists of assigning each selected acquisition in the plan to a download time windows, while ensuring that onboard memory and download capacity constraints are respected.

The following model formally describes the problem. For each acquisition $i\in 𝒜$, we have a boolean selection variable $x_a\in \{0,1\}$ and a start time variable $s_a\in \{r_a,d_a-p_a\}$. Moreover, for each acquisition $a\in 𝒜\cup ℱ$ and for each of its download options $w\in {𝒲}_a$, there is a boolean selection variable $y_{a,w}\in \{0,1\}$.

The problem is to compute a mission, i.e. select and schedule the acquisitions and downloads for each satellite in order to maximize the profit, satisfying the following constraints:

Acquisitions time windows:

Selected acquisitions must occur wholly within their time windows.

$x_a⟹r_a\le s_a\le d_a-p_a$

$\forall a\in 𝒜$

(1)

Acquisitions no-overlap:

On a satellite $s\in 𝒮$, the selected acquisitions must not overlap in time.

$x_a\wedge x_b⟹s_a+p_a+T(a,b)\le s_b\vee s_b+p_b+T(b,a)\le s_a$

$\forall \{a,b\}\subseteq {𝒜}^s$

(2)

Acquisitions alternatives:

No more than one acquisition among alternatives for each observation target shall be done.

${\displaystyle \sum _{a\in {𝒜}_{r,t,m}}}{x}_a\le 1$

$\forall r\in ℛ,\forall t\in {𝒫}_r,\forall m\in {ℳ}_r$

(3)

Acquisitions download:

Selected acquisitions cannot be downloaded more than once, they must be finished before being downloaded²²2We make the conservative assumption that an acquisition can be downloaded only if the acquisition is finished at the start of the download time window..

		${\displaystyle \sum _{w\in {𝒲}_a}}{y}_{a,w}\le x_a$	$\forall a\in 𝒜$		(4)
		$y_{a,w}⟹s_a+p_a\le r_w$	$\forall a\in 𝒜,\forall w\in {𝒲}_a$		(5)

Satellite memory:

At any given time $t$, the quantity of data stored on a satellite $s\in 𝒮$ (equal to the total acquired before $t$ minus the total download before $t$) must not exceed its capacity³³3We make the conservative assumption that memory is released at the end of the download time windows..

$\forall t$

(6)

Downloads capacity:

The total quantity of data downloaded during a time window must not exceed its capacity.

${\displaystyle \sum _{a\in 𝒜}}{y}_{a,w}{\gamma }_a\le {\gamma }_w$

$\forall w\in 𝒲$

(7)

The objective is then simply to maximize the total profit:

This objective function might seem overly simple. However, from the point of view of the operators, this is relatively easy way to steer the plan toward their true objectives. In particular, some efforts have been put into complex requests with non-additive rewards [25]. For instance, imagine that you want a complete map of Scotland. It requires to perform a large set of acquisitions, hence having only a subset of the observations may be worthless, or at least the profit should not be linear with the ratio of the observations that were made. However, such complex requests are likely to span over several planning horizons. Therefore, modeling a complex cost system might be detrimental if the whole request can never fit within one planning horizon. On the other hand, with a simple additive objective, the operators may for instance start with attaching low profits to each observation of a complex request, and then increase the weight associated to missing observations on subsequent planning sequences, depending on how close to completion they are.

Substantial differences exist in the scope of the AEOSSP used throughout the literature, mainly on extensions to the core observation scheduling problem [13]. This core is NP-hard [13]. Moreover, exhaustively taking into account all possible extensions of the AEOSSP can make it too complex, therefore intractable for existing methods. As a consequence, all the publications that we are aware of about AEOSSP consider only a subset of the constraints with more or less radical simplifications. We also defined with our industrial partner a somewhat simplified version of AEOSSP in this paper, as previously discussed in Sect. 2.

Some models [28, 6, 14] consider the breakdown into meshes and strips (i.e. long polygons imaged while the satellite is moving) of the requests’ areas of interest as decision. As in most of the literature, we assume that this step is part of some preprocessing and therefore outside of the scope of our work.

Depending on the AEOSs’ capabilities, the nature of the requests themselves can vary. Indeed, they can be simple, one-shot images of a given area, strips covering long areas [1], repetitive, stereoscopic [20], video requests [5], or even be instrument-specific when several sensors are on the spacecrafts [18, 17, 37]. Our solver is agnostic to the nature of the acquisitions; expressing punctual and stereoscopic requests can be done at preprocessing time using repetitions.

The quality of the images is time-dependent [21, 16, 29, 33, 22] and multifaceted (shooting angle, luminosity, cloud cover, customer preferences, etc.), leading some authors to consider AEOSSP as a multi-objective problem [16, 15]. Hence, in addition to profit, those works seek to maximize image quality or use of the satellites. Profit itself can be time-dependent [28] since it is quality-dependent. It can also be affected by urgency and priority policies among requests [29, 27], and even be sequence-dependent in the case of repetitive or stereoscopic requests [4, 12, 14, 20]. In our work, we have a black-box approach to profit as it is determined for each acquisition by our partner: quality and urgency are therefore sidelined as they are embedded within the profit, hence removing its time-dependence.

There are also operational constraints. Firstly, transition times, which is the time the satellite needs to maneuver towards its target. They are by nature dependent on the time and sequence of acquisitions made by AEOS [3, 22, 2]. They are either modeled as such, or approximated by piecewise linear functions or constants, or simply ignored. Our approach also approximates transition time using a transition time matrix between categories of attitude adopted by the AEOSs when performing the acquisitions. Hence, it allows to take into account time and sequence dependencies at a granularity defined at preprocessing time while formally removing time-dependence from our model.

Then there can be constraints about onboard energy management. The energy comes from solar panels, and the rate at which batteries are refilled therefore depends on both the time (the exposition to the sun depends on the orbit of the satellites) and the tasks performed by the satellite since it constrains the orientation of the solar panels [32, 33]. However, on-board energy management is rarely a bottleneck, and hence it is usually not taken into account when planning the observations. In accordance with the needs expressed by our industrial partner, this aspect is not covered in our work.

Finally, there is the management of onboard memory and its corollary: the management of downloads [21, 10, 11, 19]. Scheduling both acquisitions and downloads is often referred to integrated scheduling in the literature [34]. Memory can be looked at in two ways. By ignoring the files, it becomes a reservoir that is filled and emptied according to linear functions. If the files are taken into account, then it is a set of blocks that must be distributed between the download windows according to their capacity. We take the second approach, as it best fits our partner’s processes.

The wide range of variations in AEOSSP has resulted in the study of numerous resolution methods.

Exact methods have been extensively used to solve the AEOSSP. For instance, a branch-and-bound algorithm taking into account time-dependent constraints was proposed and shown to be effective on small instances [3]. Several MILP formulations have also been proposed [29, 12], including in the context of integrated scheduling [10, 11]. Some work only focus on data download [19] and are more in line with broader work on the Antenna-Satellite scheduling problem. Although MILP was successfully used to perform integrated scheduling with a commercial solver for Planet Lab’s constellation of over a hundred spacecrafts [23], they are not agile satellites and hence the scheduling problem is a lot easier than the AEOSSP. Moreover, while projects with a problem statement roughly similar to ours [11] does use MILP, their instances are way smaller (4 satellites, up to 3 ground stations and 200 requests), do not take into account transition times, and have a time limit orders of magnitude too high (approx. 3 h) to be used in our industrial partner’s processes. For all these reasons, we have not retained the possibility of using CP to solve the problem as a whole, but rather to solve sub-problems as a local search move.

Much of the work on AEOSSP has chosen to abandon optimality guarantees and propose methods based on heuristics and metaheuristics. Several methods solely based on heuristics have been proposed to solve AEOSSP. The scheduler of the COSMO-SkyMed constellation, comprising four spacecrafts, simply selects as much acquisitions as it can by descending order of priority [1]. Heuristics can also be used to compute the acquisitions given areas of interest in the context of an online scheduler [14]. A method using deep reinforcement learning and heuristic algorithm has also recently been proposed to solve AEOSSP for a single satellite [2]. Although those heuristics-based methods are easy to implement and yield good results for a single satellite or smaller constellation, they are not expected to be as good when applied to a whole constellation because of the larger number of alternative acquisitions. Methods using machine learning are also of great interest to solve AEOSSP, as satellite operators accumulate many instances over time, but the size of the instances and the lack of real-world data from our industrial partner led us away from learned heuristics.

Many metaheuristics-based methods has also been proposed since the first studies on AEOSSP, such as taboo search [4]. Genetic algorithms have been widely used to tackle multi-objective versions of the AEOSSP, for instance when considering operator’s preferences [16], load balancing [7], or solution stability in an online setting [15] in addition to profit. They were also applied to decompose sub-problems. In a first example, it is used for single-satellite scheduling within a broader game theory framework where satellites are players [20]. In a second example, it is used to choose between overlapping acquisitions within multi-level clusters computing using priority metrics [8]. Agent-based methods are also interesting to solve small-scale instances of AEOSSP [5].

Finally, local search and large neighborhood search (LNS) methods have also been extensively studied, including in the context of multi-objective optimization [28, 37] and online solvers [27]. Moves proposed in the literature rely on a wide array of algorithms. On the more complex side, there is a move based on computing maximum independent sets within acquisitions interval graphs using an evolutionary algorithm [6]. Unsupervised learning has also been used as a preprocessing tool for destructive LNS moves [21]. However, most of the constructive LNS moves are simpler, as they widely rely on random choices [9] and greedy algorithms [9, 22, 25]. It should be noted that these local search and LNS methods are similar to what can be found in the team orienteering problem [30], since it shares many characteristics of the acquisition selection sub-problem of AEOSSP.

The solver we present in this article is also in this line of work, as local search methods are particularly effective for solving complex instances in satellite constellations, while making it easier to break down the problem into acquisition planning and download management.

The acquisition planning phase aims at building a sequence of acquisitions for each satellite maximizing the profit under the aforementioned constraints 1, 2 and 3.

Our method uses the fact that there exists subsets of acquisitions of a given satellite that are temporally independent of each other [6, 26]. This can happen when the satellite flies over a large area with little interest (e.g. an ocean, cloudy areas, etc.), or simply because of the satellite’s orbital nighttime. Formally, for each satellite $s\in 𝒮$ we can define a dependence graph whose nodes are the acquisitions $a\in {𝒜}^s$. There is an edge between two acquisitions $\{a,b\}\subseteq {𝒜}^s$ if $d_a+T(a,b)>r_b\vee d_b+T(b,a)>r_a$, i.e., when their time windows overlap while taking into account transition time. As a consequence, each connected component of these graphs are temporally independent of each other (see example in Fig. 2). Hence, local optimization may be performed over each connected component in order to build the plan in the form of sequences of acquisitions.

Our algorithm for acquisition planning has two phases. Firstly, it builds a solution from scratch with a greedy algorithm. Secondly, a local search phase aims at improving the solution until a local minimum is reached.

The download planning phase takes place when a local minimum is found. Its aim is twofold. It first computes a download plan by affecting download windows to the planned acquisitions and the initial memory elements aboard the satellite. Then, it fixes potential remaining memory overloads on the satellites by progressively deselecting acquisitions.

For each satellite, the algorithm iterates over the download windows by increasing order of their starting time, in order to greedily affect acquisitions until the download window’s capacity is reached or there is no remaining acquisition to download. This greedy algorithm starts by collecting the acquisitions that are still on board at the starting time of the download time window, and sort them by decreasing order of their memory consumption. Then acquisitions are assigned in this order to the window if they fit.

Despite download decisions being taken, memory constraints may still be violated as the algorithm is blind to memory overloads. Hence, a memory overload repairing procedure is applied to satellites with overloads. Since we assume that the memory is freed at the end of the download window, overloads are checked at these time points. When one is found, a knapsack problem is solved over the onboard acquisitions. The knapsack capacity is the memory capacity of the satellite, the weights are the memory consumption of the acquisitions, and the values are the profits of the acquisitions. We use a simple greedy algorithm with a profit over size ratio utility to solve the knapsack problem.

It should be noted that while both procedures are using greedy algorithms, it is not an issue as download planning is often an easy task and memory is rarely a bottleneck. Finally, it should be noted that since our overall method is solved on a rolling horizon, some images may not be downloaded during the current planning horizon. They will be the content of the set $ℱ$ of the next planning horizon.

Experiments were run on a cluster of computers with 2,1 GHz Intel CPUs and 256 GB RAM. Results are the aggregation of 5 runs with different seeds and a 10 min timeout. We implemented our solver with C++ 20.

We compared our algorithm with the results of the aforementioned LNS method from the literature, as well as a baseline model with IBM’s CP Optimizer (CPO).

We now present and discuss the experimental results, by first comparing our method with the aforementioned comparison approaches. Then, we assess the impact of our use of the CP-SAT solver Tempo within the local search move, as well as the consequences of how our method manages satellite’s memory.