Deep Space Network Scheduling Using Quantum Annealing

Abstract

The National Aeronautics and Space Administration's (NASA) 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-m and several 34-m antennas. The network routinely serves a few dozen missions. The scheduling of the DSN is complex and involves human interventions as well as automated solutions. In order to increase the level of automation, different computing paradigms have been explored. In this article, 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.

Keywords

• Deep Space Network (DSN)
• quantum annealing
• quantum inspired optimization
• quadratic unconstrained binary optimization (QUBO)
• scheduling