Optimal Scheduling of Earth-Imaging Satellites with Human Collaboration via Directed Acyclic Graphs

摘要

Optimal scheduling of Earth-observing satellites is crucial to satisfying Skybox Imaging's customers with timely high-resolution imagery and HD video. The company has implemented software that automatically plans which ground targets are imaged by its satellites, maximizing overall utility while not exceeding physical limitations. The software is responsive to user interactions, e.g., additions of new targets or explicit forcing of an existing target (into or out of the schedule). The result is a real-time collaboration between autonomous scheduler and human collection manager, with the former aware of how to optimize each satellite's image collection and the latter aware of late-breaking changes affecting target desirability. The scheduler encodes the problem as directed acyclic graphs (DAGs): nodes represent imaging opportunities and edges (or lack thereof) encode agility performance of the satellite. The optimal schedule of targets is the highest weighted path through a DAG. Human actions map to addition/subtraction of edges in the DAG. This paper discusses the graph-based optimization around these human interactions, and some properties of the problem that allow for computational savings.