Graph Neural Networks for the Offline Nanosatellite Task Scheduling Problem

Nanosatellites have attracted attention from the industry and academia for over a decade, primarily because of their applications at reduced development and launch costs [1, 2, 3, 4]. Due to limited computational and energy resources, this spacecraft standard is associated with difficulties in mission planning. Optimizing task scheduling is key for guaranteeing a return on investment, as it maximizes resource usage, increases data quality, and brings about cost savings and mission success. Therefore, the Offline Nanosatellite Task Scheduling (ONTS) problem is crucial in developing, deploying, and operating nanosatellites in orbit. The problem aims at finding a schedule for task execution in orbit that maximizes Quality-of-Service (QoS), taking into account factors such as priority, minimum and maximum activation events, execution time-frames, periods, and execution windows, as well as the limitations of the satellite’s power resources and the complexities of energy harvesting and management systems.

During the lifetime of a mission (from launch to disposal), the ONTS problem must be solved recurrently and iteratively. New schedules must be generated (and deployed) over time, and the optimal schedule is found by iteratively figuring out how many tasks and which tasks are possible to fit in the scheduled timespan. Traditional mathematical formulations and exact algorithms have been proposed to solve the ONTS problem, starting from Integer Programming (IP) [5] to Mixed Integer Linear Programming (MILP) [6, 7] and Continuous-Time techniques [8]. However, due to the NP-hard nature of the problem, efficiently solving large problems, i.e., fitting many tasks and planning for a long time horizon, is still an open area for research.

Meanwhile, several recent investigations [9, 10, 11, 12] have considered machine learning tools to address combinatorial optimization problems, such as the single machine problem [13], resource-constrained project scheduling [14], and knapsack problems [15]. Graph Neural Networks (GNNs), in particular, have gained popularity in recent years to solve combinatorial optimization problems when the underlying structure can be represented as a graph [16], which is the case for MILP [17].

This paper investigates the novel application of GNNs for the ONTS problem. More specifically, we consider two research questions:

• 1.

  Can a graph neural network learn the structure of the ONTS problem?

• 2.

  Is a GNN-based heuristic effective (fast and accurate) for the ONTS problem?

To address these two questions, we propose two sets of experiments. First, we train GNNs to predict the feasibility and optimality of candidate solutions given an instance of the problem. In the second set of experiments, we train GNNs to generate candidate solutions given problem instances and use the resulting models to build matheuristics [18]. Our results indicate that: the proposed GNN can learn the feasibility and optimality of candidate solutions, even when given instances larger (and harder) than those seen during training. Furthermore, GNN-based matheuristics effectively provide high-quality solutions for large problems, overcoming the MILP solver (SCIP) both in the time to generate feasible solutions and the quality of the solutions found during limited time. In summary, the main contributions of this paper are as follows:

• 1.

  The introduction of SatGNN, a pioneering GNN architecture suitable to the ONTS problem;

• 2.

  A showcase of SatGNN’s impressive performance in accurately classifying feasibility, predicting optimality, and generating effective heuristic solutions;

• 3.

  A demonstration of GNN’s robust generalization abilities for optimization problems, particularly when dealing with larger ONTS instances;

• 4.

  An implication of the potential for a transformative impact on complex space mission scheduling.

The remainder of this paper is organized as follows: Section 2 provides an overview of the related literature. Section 3 describes the problem in detail, providing context and background information and formulating the optimization problem. Section 4 provides the necessary theoretical background on graph neural networks and their application to linear optimization problems. The data acquisition, the proposed GNN architecture, and the heuristics for optimization problems are presented in Section 5. The experiments that tackle the two research questions posed above along with the results are presented in Section 6. Finally, Sections 7 and 8 discuss the key findings and provide concluding remarks and future research directions.

The ONTS problem has received significant contributions in recent years, with different approaches and formulations. At the same time, machine learning applications for optimization problems have become a prolific area of research. This section briefly overviews our paper’s most influential works in both areas.

Mathematical programming is consolidated as a practical approach for satellite scheduling problems [19, 20, 21]. Targeting small satellites, Rigo et al. [5] formulated the problem of maximizing task allocation under power availability constraints as an integer programming (IP) problem. The formulation considers discrete time steps and information such as the maximum power input at each time step along the planning horizon, power consumption of tasks, execution periods, and task priorities. This approach was able to provide energy-efficient allocations that improved mission value.

Seman et al. [7] extended the approach by [5] and proposed a Mixed-Integer Linear Programming (MILP) formulation to tackle the task scheduling in constellations of nanosatellites. Camponogara et al. [8] applied the Multi-Operation Sequencing with Synchronized Start Times (MOS-SST) representation to the problem, maintaining an MILP formulation but extending the problem to continuous time. The continuous-time feature allowed for greater flexibility and versatility, fundamental characteristics for decision-making during the design phase. The evolution of formulations and methodologies highlights the continuous efforts to find the most efficient and effective solutions to the ONTS problem.

More recently, given the difficulty in solving complex instances of the ONTS problem, Rigo et al. [22] proposed a Dantzig-Wolfe decomposition, coupled with a branch-and-price (B&P) methodology. This approach was designed to build a unique column-based formulation that produces feasible and optimal schedules. In addition, they leveraged the Dynamic Programming (DP) technique to identify optimal columns and speed up the whole process. Their computational experiments significantly improved overall solution time compared to a commercial MILP solver, with a 70% reduction in computation time. Despite these promising results, the B&P method introduces specific challenges and limitations that preclude its universal application. One significant drawback is its heavy reliance on the suitability of the decomposition, which is notoriously problem-specific. Currently, no known method allows practitioners to a priori ascertain the presence of a decomposable structure in a given problem [23]. This lack of a deterministic approach to identifying suitable problems adds a layer of complexity to the application of B&P. Additionally, the complexity inherent in the decomposition and the optimization algorithm can result in a high development undertaking. The intricate nature of these processes requires specialized knowledge and expertise, potentially rendering the B&P method prohibitive for particular applications or settings. Consequently, while the B&P methodology offers substantial improvements in computational efficiency for specific problem instances, its applicability may be limited by these challenges, emphasizing the need for caution in considering it as a universal solution for all optimization problems.

Machine learning applications for optimization problems were first proposed in 1985, applying Hopfield neural networks to the Travelling Salesperson Problem (TSP) [24]. Due to the hardware limitations of the time [25], neural network applications to optimization problems have stayed out of the spotlight up to recent years, when developments in novel architectures, more powerful hardware, and promising published results have attracted the attention of the research community back to this area [9]. One of the drivers of this change was the proposition of structured artificial neural networks able to handle the symmetries that optimization problems have [26], such as the invariance to permutation of constraints. A significant example of such property for Combinatorial Optimization (CO) is the work of Khalil et al. [27], which developed a greedy heuristic for CO problems on graphs using a GNN. Gasse et al. [28] proposed to embed linear programming problems as a bipartite graph, generalizing the use of GNNs to any MILP. The results presented in these works indicate that GNNs can learn the structures of MILP problems.

Many authors proposed using GNNs to predict solution values, aiming at using the learned model in heuristic solutions. Ding et al. [29] proposed using such GNNs to guide the Branch and Bound (B&B) algorithm towards the variables the model had the most difficulty learning. Khalil et al. [17] use the GNNs trained to predict biases of the binary variables to perform node selection and warm starting. Nair et al. [30], in their approach named Neural Diving, proposed to train the model to provide partial solutions, which generate sub-problems through variable fixing. The multiple sub-problems are then solved using off-the-shelf solvers. Han et al. [12] compare the fixing approach of [30] to their proposed approach of defining a trust region around the partial solution generated by the GNN, showing significant improvements over off-the-shelf solvers like SCIP and Gurobi. These works highlight how promising building GNN-based heuristic approaches to MILP can be.

To the best of our knowledge, our work is the first to apply deep learning models to satellite task scheduling. Furthermore, machine learning application to MILP has not been extensively tested, as confirmed by the novelty of the works presented above and the lack of learning-based components in open-source solvers such as SCIP and CPLEX. In other words, although promising, applying GNNs to MILP still needs to be well-understood and is not guaranteed to yield positive results. In this context, the present work also contributes to the machine learning and combinatorial optimization area of research by validating novel techniques.

Nanosatellite scheduling problems concern the decisions on each task’s start and finish time. The tasks usually require periodic execution and during restricted moments along the orbit. Besides time, energy availability through the orbit is a crucial resource to be considered. Figure 1 shows an example of optimal scheduling, in which each job is represented by a different color and the activation and deactivations are shown through the steps of the signals. Proper scheduling must account for energy management such that the tasks do not draw more energy than the system can provide and that the battery is not depleted before the end of the mission. Energy management is a difficult task since the nanosatellite draws power from its solar panels, with the energy availability depending on the attitude of the nanosatellite (which affects the orientation of the solar panels) and the trajectory with respect to Earth’s shadow, as illustrated in Figure 2.

Graph neural networks are generalizations of convolutional neural networks from grid-structured data to graphs. The input to a GNN is a graph and a set of feature vectors associated with the graph nodes. GNNs work by propagating feature information between neighboring nodes, which can be seen as message-passing. More specifically, at each layer, the GNN computes the messages each node sends based on its feature vector and then updates each node’s feature vectors given the messages its neighbors received. We will refer to the feature update as a graph convolution, due to its similarities to the operations in convolutional neural networks.

At each layer $l\in\{1,...,L\}$, the graph convolution operation has two major components: message functions $M_{l}(\cdot)$, which compute the messages propagated by each node, and update functions $U_{l}(\cdot)$, which update the node-associated features based on the messages. Let $G=(V,E)$ be a graph and $\boldsymbol{h}^{(0)}_{v}$ be feature vectors for every node $v\in V$. The messages sent $\boldsymbol{m}_{u}^{(l)}$ are computed based on the node features

where $M_{l}(\cdot)$ is the message function of layer $l$. After computing the messages, the features of node $v$ are updated through

where $\mathcal{N}(v)$ are the neighbors of $v$, $U_{l}(\cdot)$ is the update function of layer $l$, and ${\tt Aggregation}$ is a function that receives multiple message vectors and returns a single vector.

A common choice for graph convolutions is to use feedforward neural networks as message and update functions. For these to be well-defined, we need ${\tt Aggregation}$ to return, for how many messages received, a vector with a fixed length, thus the naming. A natural choice is to sum up the messages, but many are the possibilities, such as

where $\alpha_{u,v}$ is an attention weight for node $u$ given node $v$, which can be learned along the model parameters. Furthermore, the message function can easily be extended to consider the edge weight (or even edge features) along with the feature vectors of the neighbors.

A common approach is to define the message functions $M_{l},l=1,\ldots,L$, as linear operators over the hidden features of the neighbors, aggregate these messages by summing, and use the ReLU (Rectifier Linear Unit) activation function with a bias as the update functions $U_{l},l=1,\ldots,L$. An example of such is the model proposed by Kipf and Welling [31], which uses a linear combination of the features as the message function, aggregates messages by summation, and updates using a single-layer neural network with ReLU activation. More precisely, we can describe their convolution operation as

where $c_{vu}=\sqrt{|\mathcal{N}(u)|}\sqrt{|\mathcal{N}(v)|}$ with $|\mathcal{N}(v)|$ denoting the number of neighbors, and $W^{(l)}\in\mathbb{R}^{d_{l}\times d_{l}},\boldsymbol{b}^{(l)}\in\mathbb{R}^{d_{l}}$ (layer $l$ has size $d_{l}$) are the weights and biases of the model, i.e., learnable parameters.

Another convolution operator was proposed by [32] and named SAGE (SAmple and aGgrEgate). The authors propose to directly aggregate the features of the neighbors, i.e., to use the identity as the message function and to use a single-layer network with ReLU activation as the update function. Putting it into terms, the proposed graph convolution is

where $W^{(l)}_{1},W^{(l)}_{2}\in\mathbb{R}^{d_{l}\times d_{l}},\boldsymbol{b}^{(l)}\in\mathbb{R}^{d_{l}}$ are the parameters. The authors suggest using more complex aggregation operators, such as an LSTM (Long Short-Term Memory network) and a fully connected single-layer neural network, followed by a pooling operation (element-wise maximum). Note that the SAGE convolution with summation as the aggregation function is equivalent to the one proposed by Kipf and Welling.

After recurrent graph convolutions through the $L$ layers of a GNN, we can use the resulting node features $H^{(L)}=\left[\boldsymbol{h}_{v}^{(L)}\right]_{v\in V}$ straight-away, which is suitable for, e.g., node classification tasks, or we can aggregate them further into a single feature vector, suitable for, e.g., graph classification tasks. The GNN can be trained end-to-end by minimizing a prediction loss based on its outputs, optimizing its parameters (e.g., $W^{(l)}$ and $\boldsymbol{b}^{(l)}$ of (8)) in the same way as a traditional deep learning model.

In this section, we provide a detailed description of our methodological approach to tackle the two research questions proposed in the introduction. Namely, we describe our approach to generating ONTS problem data used to train GNNs, our proposed GNN architecture (SatGNN), and how we embed our trained models in heuristics.

The experiments for this paper were conducted in Python, using PyTorch, the DGL libraries, and the SCIP solver, on a server with an Intel i7-12700 16-Core (12 cores, 20 threads), an NVIDIA RTX A4000, 16 GB of memory, and Ubuntu 22.04.1 LTS 64 bits. Implementation details are available in the paper’s accompanying repository⁴⁴4https://github.com/brunompacheco/sat-gnn.

In the following sections, we present three experiments addressing the two research questions raised in the introduction (Sec. 1). In the first experiment, we train the proposed SatGNN model to classify the feasibility of candidate solutions for problem instances. We consider three scenarios of increasing difficulty with respect to the generalization performance. In the second experiment we train SatGNN models to predict the bias for the binary variables of problem instances, effectively learning the probability that each binary variable has to assume a positive value in an optimal solution. We compare two training approaches, considering either the optimal solution as the target or multiple feasible solutions as targets for each instance. Finally, we use the models trained for optimality prediction to generate candidate solutions, which are used to construct heuristics to the ONTS problem. More specifically, we use the trained models to construct three approaches (as presented in Sec. 5.4) to improve the SCIP solver in its off-the-shelf setting: warm-starting, early-fixing, and trust region.

In this section, we discuss the results obtained from a series of experiments conducted to address the research questions posed in the introduction. The experiments aimed to evaluate the effectiveness of GNNs in solving the ONTS problem. More specifically, we use our proposed model, SatGNN, which is based in the models by Gasse et al. [28] and Hamilton et al. [32]. Our experiments evaluate whether SatGNN can learn feasibility and optimality given large instances of the ONTS problem, and whether the trained model can be used in heuristic solutions.

The results of the first set of experiments (Sec. 6.2) indicate that the SatGNN can provide accurate feasibility estimations even in challenging scenarios. Three scenarios of increasing difficulty were considered, and the results were quite promising, with over 89% accuracy in all experiments. In the most challenging scenario, SatGNN is evaluated on large ($J\in\{20,22,24\}$) unseen instances, but trained on small instances ($J\in\{9,13,18\}$), and it achieved 94.15% accuracy in feasibility classification. The remarkable accuracy indicates that SatGNN is highly effective at learning the constraints of the ONTS problem. This performance is expected as the feasibility classification task requires the model to learn linear classification boundaries, which are derived from the linear constraints of the problem. In other words, the model learns the indicator function of a convex set (considering the LP relaxation of the problem), which neural networks are known to be suitable for.

The second set of experiments (Sec. 6.3) aimed to predict optimal solutions to ONTS instances using SatGNN. More specifically, SatGNN was trained to predict the biases of the binary variables for multiple instances of the ONTS problem. Two training approaches were explored: one trained with a single target (the quasi-optimal solution) and another trained with multiple solutions (the best feasible solutions found). Both approaches showed promising results, with no signs of overfitting, as indicated by the small difference between validation and test set performance. Interestingly, the model trained with multiple solutions tended to be more confident in its predictions, particularly for the binary variables. This increased confidence could be valuable in guiding the optimization process, as it indicates the model’s certainty about its predictions.

Although the results from the second set of experiments suggest that SatGNN can effectively predict optimal or near-optimal solutions to ONTS instances, we put the models to the test through a third set of experiments (Sec. 6.4) in which we build (mat)heuristic solutions based on the output of the SatGNN trained for optimality prediction. Namely, as detailed in Sec. 5.4, three approaches were evaluated for applying the model’s output: warm-start, early fix, and trust region. Each approach is optimized for finding the best solution, giving the time budget (2 min.) and reducing the time to find a feasible solution (2 separate experiments). First, we notice that in all direct comparisons, the SatGNN model trained with multiple solutions resulted in better heuristic solutions than the model trained with a single solution, as was suggested by the results of the second set of experiments.

Early-fixing the partial solution provided by the SatGNN models yielded the best results overall, showing a 43% gain in the evaluation of the expected objective value within the time budget, and a 35% reduction in the evaluation of the expected time to find a feasible solution. The trust region approach, which can be seen as a relaxation of the early-fixing, was comparable to early-fixing in terms of the best solution found within the time limit, but overall seems to provide a worse trade-off, as both early-fixing and trust region do not provide optimality guarantees, but trust region takes longer to find good solutions to the ONTS problem. Using the SatGNN models to warm-start the SCIP solver significantly reduced the time to find a feasible solution (in comparison to the baseline), but was overall worse than the two other approaches. However, warm-start has the advantage of providing optimality guarantees, which makes it more widely applicable.

Across all experiments, a highlight of the GNNs’ performance was the generalization to larger instances. This characteristic is essential for problems with varying instance size and is not trivially achievable with traditional deep-learning models. However, it is also key for tasks with higher acquisition costs for certain problem sizes, as in the case of the ONTS problem. Large instances of optimization problems are the ones that drive the research of heuristic solutions, as they are usually more expensive to solve; however, as we need to solve instances to create a training dataset, it often becomes infeasible to train the deep learning models on large instances. In this context, the generalization results from our experiments suggest that GNNs can be effectively trained using easy (cheap to acquire) instances of the problem, and be used on the hard instances of interest.

Generating reliable instances to train and evaluate solvers is a key point in such a project, as the confidence of the results depends on how carefully instances are designed to compose the test set [39]. Data generation is particularly critical when historical data is not available [9], which motivates the research on algorithms for generating reliable instances [39, 40]. We follow the problem definition of the FloripaSat-I mission [35] to define the parameters’ ranges used to sample new instances uniformly. Although the data generation process is reliable, it still depends on the optimization of every randomly generated instance. Furthermore, as we restrict ourselves to feasible instances, we only add to the dataset instances for which the solver could find at least one feasible solution within the time budget, effectively restricting our data to an easier sub-problem [41]. Given the nature of the ONTS problem, a future research direction could be generating large instances by combining the job parameters from easier instances, thus generating instances that extrapolate the time budget restriction.

This work has proposed a novel approach to tackle the ONTS problem using graph neural networks. More specifically, we investigated whether a GNN can learn the structure of the problem and be used to build effective heuristic solutions. Our experiments showed that our proposed architecture, SatGNN, successfully classifies the feasibility of candidate solutions and is also able to provide reliable partial solutions to varied instances of the ONTS problem. Not only was the model able to generalize to unseen instances, but it also showed promising results on out-of-distribution instances, which were larger than the ones seen during training. This outcome shows how the inherent symmetries of graph neural networks make them suitable for dealing with the structures of the optimization problem.

By leveraging partial solutions provided by the SatGNN model, we built heuristic solutions to the ONTS problem that outperformed the SCIP solver in hard instances. More specifically, by fixing the variable assignment from the partial solution provided by SatGNN, our heuristics were able to improve up to 43% in the expected objective value of the best solution found within the time budget, and reduce up to 35% in the expected time to find a feasible solution.

Overall, the experiments presented in this paper showcase the potential of GNNs for addressing the ONTS problem. The high accuracy in feasibility classification, the ability to predict optimal solutions, and the effectiveness of SatGNN-based heuristics suggest that this approach has the potential to revolutionize the way complex space mission scheduling problems are tackled, enabling more efficient and reliable scheduling for nanosatellite missions. Further research could explore the scalability of these methods to larger problem instances, problems with satellite constellations, and real-world applications in space mission planning and scheduling.

The authors acknowledge support from CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico) under grant number 150281/2022-6, 404576/2021-4 as well as FAPESC under grant number 2021TR001851.