Constraint-Based Random Search for Solving Spacecraft Downlink Scheduling Problems

A. Oddi, N. Policella, A. Cesta and G. Cortellessa

In G. Kendall, E. Burke, S.Petrovic, M Gendreau (Eds), Multidisciplinary Scheduling: Theory and Applications (Springer), pp. 133-162, 2005

This paper introduces a combinatorial optimization problem called Mars Express Memory Dumping Problem (Mex-Mdp), which arises in the European Space Agency program Mars Express. The domain is characterised by complex constraints concerning bounded on-board memory capacities, limited communication windows over the downlink channels, deadlines and ready times imposed by the scientists using the spacecraft instruments. This paper lays out the problem and analyses its computational complexity showing that Mex-Mdp is NP-hard. Then the problem is modeled as a Constraint Satisfaction Problem and two different heuristic strategies for its solution are presented: a core greedy constraint-based procedure and an iterative sampling strategy based on random search. The algorithms are evaluated both against a benchmark set created on the basis of ESA documentation and a lower bound of the minimized objective function. Experimental results show the overall effectiveness of the approach.