Neil Dhingra, Auria; Cameron DeJac, Auria; Clayton McGuire, Auria
Keywords: Sensor Resource Management, Sensor Tasking, Space Domain Awareness, Space Situational Awareness, Global Optimality, NP Hard Problems, Machine Learning, Supervised Learning, Reinforcement Learning
Abstract:
We present our novel approach using machine learning (ML) methods to train sensor scheduling algorithms for Space Domain Awareness (SDA). Since the full SDA sensor scheduling problem is NP hard, methods for identifying globally optimal sensor schedules do not scale well with the problem dimension. Rather than modifying traditional combinatorial optimization techniques to run at operational speeds, we train an ML algorithm to match their performance in less time.
Sensor Scheduling for Space Domain Awareness (SDA) is a large, complicated, time-varying, and NP hard problem even under restrictive assumptions. As a result, solving full SDA sensor scheduling problems to global optimality is intractable, especially when scheduling algorithms must satisfy operational constraints such as those on runtime or a need to maintain an ‘anytime’ property. Conventional approaches often require identifying problem characteristics that can be exploited to deploy algorithms that create high quality schedules while satisfying operational constraints. We have employed such approaches successfully for scheduling SDA sensors and other space operations. However, identifying and exploiting these characteristics can be manually intensive and require expert knowledge.
Our approach in this paper, in contrast, is to use machine learning (ML) techniques to train a scheduling algorithm that satisfies operational constraints and accomplishes this mission without explicitly exploiting problem characteristics. Rather, the ML training process is designed to learn these problem characteristics implicitly through the training data. We use supervised learning techniques to develop an algorithm that performs well on representative subproblem benchmarks, for whom optimal solutions are known, and use reinforcement learning to extend and further optimize its performance on the large and complex full SDA sensor scheduling problem.
By limiting problem size, complexity, or both, we have identified several relevant and representative subproblems over which we can design optimal schedules. We generate high quality schedules offline using different methods that can solve these problems to global optimality. We then use supervised ML to initialize an ML scheduling algorithm using the optimal schedules as training data. Finally, we use reinforcement learning to further improve that algorithm’s performance for the full SDA sensor scheduling problem while maintaining performance on the benchmark subproblems.
The framework used to train this sensor scheduling algorithm is also extensible to other problem cases which are even less amenable to combinatorial methods. For example, many combinatorial problems are represented by mixed integer linear programs which require that the FOM is a linear function of the optimization variables. The ML framework developed in this paper imposes no such constraint on the form of the FOM. This framework can also be extended to support human feedback for the FOM. This is desirable in cases where operator preferences are hard to characterize mathematically, but where operators can score schedules to provide feedback on how well they do.
We deploy the ML algorithm in our SDA sensor scheduling software, Heimdall, for evaluation. Heimdall runs several algorithms in parallel and chooses the one with the best FOM for execution. This framework enhances Heimdall’s SDA sensor scheduling algorithm suite and facilitates the continued improvement of the other Heimdall SDA sensor scheduling algorithms. Heimdall has been deployed in support of SDA sensor scheduling for several customers and will support the forthcoming Deep Space Advanced Radar Concept (DARC) system.
Date of Conference: September 17-20, 2024
Track: Machine Learning for SDA Applications