Conflict- and Fairness-Directed Heuristic Search Scheduling for NASA’s Oversubscribed Deep Space Network

This paper describes a comparison of search methods applied to the same problem of scheduling activities for NASA’s Deep Space Network (DSN). The DSN consists of large (34- and 70-meter) radio antennas at three sites around the world, and provides communications and navigation support for dozens of space missions. The DSN is over- subscribed – more time is requested than can be accommodated – and it is an ongoing challenge to schedule the available resources while also balancing the satisfaction of requests from the disparate set of users. As part of a study of state-of-the- art solution techniques for oversubscribed scheduling, a standard set of problems was defined, and solutions were attempted with several classes of algorithms developed by different teams. These included variants of Quantum Annealing (QA), Mixed-Integer Linear Programming (MILP), Reinforcement Learning (RL), and Constraint Satisfaction Problem (CSP) based heuristic search (CSP-HS). The results, first reported in this work, show that heuristic search significantly outperforms the other methods in the study in terms of solution quality and runtime performance, when objectives are to maximize the “fairness” of the resulting schedule (e.g. no starvation) while simultaneously clearing all constraint violations and fitting as much as possible into the schedule. The set of benchmark problems is made openly available for other groups to try.