The Frontier Development Lab (FDL) is a National Aeronautics and Space Administration (NASA) machine learning program with the stated aim of conducting artificial intelligence research for space exploration and all humankind with support in the European program from the European Space Agency (ESA). Interdisciplinary teams of researchers and data-scientists are brought together to tackle a range of challenging, real-world problems in the space-domain. The program primarily consists of a sprint phase during which teams tackle separate problems in the spirit of 'coopetition'. Teams are given a problem brief by real stakeholders and mentored by a range of experts. With access to exceptional computational resources, we were challenged to make a serious contribution within just eight weeks. Stated simply, our team was tasked with producing a system capable of scheduling downloads from satellites autonomously. Scheduling is a difficult problem in general, of course, complicated further in this scenario by ill-defined objectives & measures of success, the difficulty of communicating tacit knowledge and the standard challenges of real-world data. Taking a broader perspective, spacecraft scheduling is a problem that currently lacks an intelligent solution and, with the advent of mega-constellations, presents a serious operational bottleneck for the missions of tomorrow.

Finding the optimal ordering of k-subsets with respect to an objective function is known to be an extremely challenging problem. In this paper we introduce a new objective for this task, rooted in the problem of star identification on spacecrafts: subsets of detected spikes are to be generated in an ordering that minimizes time to detection of a valid star constellation. We carry out an extensive analysis of the combinatorial optimization problem, and propose multiple algorithmic solutions, offering different quality-complexity trade-offs. Three main approaches are investigated: exhaustive search (branch and prune), goal-driven (greedy scene elimination, minimally intersecting subsets), and stateless algorithms which implicitly seek to satisfy the problem's goals (pattern shifting, base unrank). In practical terms, these last algorithms are found to provide satisfactory approximations to the ideal performance levels, at small computational costs.