Neil Dhingra, Orbit Logic; Cameron DeJac, Orbit Logic; Alex Herz, Orbit Logic; Roderick Green, Orbit Logic
Keywords: Sensor Resource Management, Sensor Tasking, Space Domain Awareness, Space Situational Awareness, Global Optimality, Optimality Gap
Abstract:
Sensor Scheduling for Space Domain Awareness (SDA) is a large, complicated, time-varying, and NP hard problem even under restrictive assumptions. In addition to complicating the design of algorithms that can plan feasible sensor schedules, it makes it difficult to formally characterize the solution quality of those schedules across the entire space of SDA problems, even when such characterization is crucial to ensure the efficacy of deployed algorithms supporting operational systems. Here, algorithm performance or solution quality is quantified by an objective function or Figure of Merit (FOM) (e.g., total slew time) associated with a given sensor schedule as long as it meets sensing requirements (e.g., plan observations of all space objects of interest); sensor schedules with a lower objective function or FOM score are better. To facilitate analysis and development of deployed SDA scheduling algorithms, we have developed a framework wherein we formally characterize algorithm performance on relevant but tractable subproblems. In other words, we infer overall algorithm performance based on performance in representative special cases.
We have applied this framework to analyze and improve the quality of solutions generated by our Heimdall SDA sensor scheduling software. We demonstrate that our Heimdall algorithms identify optimal or near-optimal solutions in several specific SDA scheduling problem instances and improve solution quality relative to baseline approaches while satisfying operational requirements.
First, we identify several tractable subproblems of the full SDA scheduling problem which are, due to their size and/or complexity, amenable to analysis via integer linear programming techniques, convex relaxation, exhaustive search, and/or other formal methods. We characterize solution quality over these subproblems and from that infer solution quality in more complicated problem instances. An analogy is evaluating a student it is infeasible to characterize their performance in every possible situation, but it is possible to give them tests or coding exercises to evaluate them in a representative sample of scenarios and use that to infer an assessment of their mastery across the entire subject.
To analyze these specific subproblems, we employ complex, expensive, and slow methods which would be impractical in an operational system. We then compare the objective values of sensor schedules planned by Heimdall algorithms with the optimality bounds and sensor schedule objective value scores generated by the more comprehensive methods. Both sets of algorithms are designed around characteristics of the problem itself revisit rate requirements, moving objects, time-varying slew times between targets, sensor keepout constraints, track accuracy requirements, etc. but the algorithms used for analysis may be more computationally intensive. The Heimdall algorithms are designed for deployment so must obey operational considerations on runtime, memory, anytime algorithm requirements, limited information sharing across different sites, etc.
We present the results of this analysis which indicates the Heimdall often achieves global optimal or near optimal solutions. When we identify cases in which Heimdall schedules are suboptimal, this analysis drives development to improve those algorithms. In particular, since Heimdall runs several algorithms in parallel and then selects the plan output with the best FOM, novel algorithms can be developed to target especially challenging classes of problems and they can run alongside the existing algorithms. Algorithm development may involve adjusting algorithmic parameters, developing new algorithm approaches, or leveraging specific pieces of the larger more expensive solvers within the deployed Heimdall algorithms.
This framework enables analysis of the value of Heimdall and other sensor scheduling problems for the SDA mission and facilitates the continued improvement of the 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 19-22, 2023
Track: Space Domain Awareness