Satellite scheduling system
Systems and methods are provided for scheduling objects having pair-wise and cumulative constraints. The systems and methods presented can utilize a directed acyclic graph to increase or maximize a utilization function. The objects can comprise satellites in a constellation of satellites. In some implementations, the satellites are imaging satellites, and the systems and methods for scheduling can use human collaboration to determine events of interest for acquisition of images. In some implementations, dominant edges are removed from the directed acyclic graph. In some implementations, dynamic weights are assigned to nodes associated with downlink events in the directed acyclic graph.
1. A system for controlling a constellation of imaging satellites, the system comprising:
memory configured to store satellite properties information corresponding to characteristics of one or more imaging satellites in the constellation of imaging satellites;
one or more computing devices in communication with the memory, the one or more computing devices configured to execute instructions that cause the one or more computing devices to perform operations, the operations comprising:
producing or receiving requests for an image collection event;
identifying one or more imaging satellites in the constellation of imaging satellites which will be positioned over a region suitable to perform a requested image collection event;
receiving event requests comprising one or more imaging events and one or more downlink events, and the satellite properties information and user input relating to changes to one or more of the event requests;
producing a near-optimal schedule of events that does not violate constraints of the constellation of imaging satellites, the near-optimal schedule taking into account at least in part the received user input and comprising one or more scheduled events, wherein the scheduled events include the one or more imaging events and the one or more downlink events, wherein producing the near-optimal schedule of events comprises:
accessing a directed acyclic graph, wherein the directed acyclic graph comprises one or more first nodes representative of the one or more imaging events and one or more second nodes representative of the one or more downlink events,
traversing a path through the directed acyclic graph such that a set of dominated edges are not traversed or removed from the directed acyclic graph, the near-optimal schedule of events comprising a highest weighted path through the directed acyclic graph, and
applying a respective weight to each of the one or more imaging events and the one or more downlink events, wherein each respective weight is indicative of a priority of the imaging event or downlink event for inclusion in the near-optimal schedule of events, a higher weight indicating that the associated imaging event or downlink event is to be given a higher priority for inclusion in the near-optimal schedule of events than an imaging event or downlink event with a lower priority, wherein weights for the one or more downlink events are higher than weights for the one or more imaging events, wherein the weights for the one or more downlink events are determined based, at least in part, on a time to downlink all images;
converting the near-optimal schedule of events into one or more control instructions for transmission to the one or more imaging satellites in the constellation of imaging satellites; and
communicating with the one or more imaging satellites to initiate a performance of the one or more scheduled events based at least in part on the one or more control instructions, wherein the performance of the one or more scheduled events comprises a performance of the one or more downlink events which increase available data storage for the one or more imaging satellites.
2. The system of claim 1 , wherein the satellite scheduling system is configured to take into account at least in part the received user input by disabling edges in the directed acyclic graph based at least in part on the user input.
3. The system of claim 2 , wherein edges terminating at a node associated with the user input are disabled to force out an event from the schedule of events.
4. The system of claim 2 , wherein edges crossing a node associated with the user input are disabled to force in an event from the schedule of events.
5. The system of claim 1 , wherein edges of the directed acyclic graph are determined to not be part of the longest path through the directed acyclic graph are not traversed or are removed from the directed acyclic graph.
6. The system of claim 1 , wherein weights for the one or more downlink events in the directed acyclic graph are determined based at least partly on a time available to perform a downlink.
7. A method of controlling a constellation of imaging satellites, the method comprising:
receiving, by one or more computing devices, a request for an image collection event;
identifying, by the one or more computing devices, one or more imaging satellites in the constellation of imaging satellites which will be positioned over a region suitable to perform a requested image collection event;
receiving, by the one or more computing devices, data indicative of a plurality of event requests comprising one or more imaging events and one or more downlink events, and data indicative of satellite properties;
receiving, by the one or more computing devices, data indicative of user input relating to changes to one or more of the event requests;
producing, by the one or more computing devices, a near-optimal schedule of events that does not violate constraints of the constellation of imaging satellites, the near-optimal schedule taking into account at least in part the user input relating to changes to one or more of the event requests and comprising one or more scheduled events, wherein the scheduled events include the one or more imaging events and one or more downlink events, wherein producing the near-optimal schedule of events comprises:
accessing a directed acyclic graph, wherein the directed acyclic graph comprises one or more first nodes representative of the one or more imaging events and one or more second nodes representative of the one or more downlink events,
traversing a path through the directed acyclic graph such that a set of dominated edges are not traversed or removed from the directed acyclic graph, the near-optimal schedule of events comprising a highest weighted path through the directed acyclic graph, and
applying a respective weight to each of the one or more imaging events and the one or more downlink events, wherein each respective weight is indicative of a priority of the imaging event or downlink event for inclusion in the near-optimal schedule of events, a higher weight indicating that the associated imaging event or downlink event is to be given a higher priority for inclusion in the near-optimal schedule of events than an imaging event or downlink event with a lower priority, wherein weights for the one or more downlink events are higher than weights for the one or more imaging events, wherein the weights for the one or more downlink events are determined based, at least in part, on a time to downlink all images;
converting, by the one or more computing devices, the near-optimal schedule of events to one or more control instructions for transmission to one or more imaging satellites in the constellation of imaging satellites; and
communicating, by the one or more computing devices, with the one or more imaging satellites in the constellation of imaging satellites to initiate a performance of the one or more scheduled events using the one or more control instructions, wherein the performance of the one or more scheduled events comprises performance of the one or more downlink events.
8. The method of claim 7 , wherein producing, by the one or more computing devices, the near-optimal schedule of events comprises disabling, by the one or more computing devices, edges in the directed acyclic graph based at least in part on the user input.
9. The method of claim 8 , wherein edges terminating at a node associated with the user input are disabled to force out an event from the schedule of events.
10. The method of claim 8 , wherein edges crossing a node associated with the user input are disabled to force in an event from the schedule of events.
11. The method of claim 7 , wherein edges of the directed acyclic graph are determined to not be part of the longest path through the directed acyclic graph are not traversed or are removed from the directed acyclic graph.
12. The method of claim 7 , wherein weights for the one or more downlink events in the directed acyclic graph are determined based at least partly on a time available to perform a downlink.