Deep Space Network Scheduling Using Quantum Annealing
Alexandre Guillaume, Edwin Goh, Mark Johnston, Brian Wilson, Anita Ramanan, Frances Tibble, Brad Lackey
Abstract
NASA's Deep Space Network (DSN) is responsible for communication and navigation for several NASA and international missions. The DSN comprises three complexes located in Goldstone (California, USA), Cambera (Australia) and Madrid (Spain). This distribution in longitude guarantees a full sky coverage. Each complex has one 70-meter and several 34-meter antennas. The network routinely serves a few dozens missions. The scheduling of the DSN is complex and involves humans interventions as well as automated solutions. In order to increase the level of automation, different computing paradigms have been explored. In this paper, we report on the quadratic unconstrained binary optimization (QUBO) formulation of the DSN scheduling, as well as a custom classical solver designed around some of the unique features of this scheduling problem. Thanks to a hybrid framework that extends the size of the problems that can be solved with a quantum annealer, we are able to generate a schedule from the QUBO formulation of the problem for one week's worth of user antenna requests, which represents the time period scheduled during operation. In other words, this work describes a real- world application of quantum annealing using real-world, operational data. We compare the resulting schedules' quality to solutions obtained using a mixed-integer linear programming formulation on a commercial solver. Our custom solver, based on a quantum-inspired optimization technique called Substochatic Monte-Carlo, while much faster in generating schedules, could only treat a subset of requests and hence we report its results independently.