Satellite Scheduling System

Abstract

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 - 20 . (canceled) 
     
     
         21 . A method of controlling a constellation of imaging satellites, the method comprising:
 receiving event requests comprising one or more imaging events or one or more downlink events;   identifying one or more imaging satellites in the constellation of imaging satellites which will be positioned over one or more regions at one or more designated times suitable to perform the event requests;   producing, by accessing a graph, a schedule of events for the event requests, the schedule comprising designated times that do not violate a constraint of the constellation of imaging satellites,   wherein the 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,   wherein producing the schedule comprises 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 schedule of events, the weights for the one or more downlink events being based, at least in part, on a downlink time associated with the downlink event;   generating one or more control instructions based, at least in part, on the schedule; and   transmitting the one or more control instructions to one or more of the imaging satellites in the constellation to initiate a performance of the events in the schedule at a respective designated time.   
     
     
         22 . The method of  claim 21 , wherein weights for the one or more downlink events are higher than weights for the one or more imaging events. 
     
     
         23 . The method of  claim 21 , wherein the weights for the one or more downlink events are determined based, at least in part, on a time to downlink images from one or more of the imaging events. 
     
     
         24 . The method of  claim 21 , wherein the operations further comprise:
 receiving user input relating to changes to one or more of the event requests; and   adjusting the schedule of events based, at least in part, on the user input.   
     
     
         25 . The method of  claim 24 , wherein the schedule of events comprises one or more disabled edges in the graph that are based, at least in part, on the user input. 
     
     
         26 . The method of  claim 25 , wherein at least one edge terminating at a node associated with the user input is disabled to force out an event from the schedule of events. 
     
     
         27 . The method of  claim 21 , wherein the schedule of events is associated with a highest weighted path through the graph. 
     
     
         28 . The method of  claim 21 , wherein the graph is a directed acyclic graph. 
     
     
         29 . A system for controlling a constellation of imaging satellites, the system comprising:
 at least one memory; and   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:
 receiving event requests comprising one or more imaging events or one or more downlink events; 
 identifying one or more imaging satellites in the constellation of imaging satellites which will be positioned over one or more regions at one or more designated times suitable to perform the event requests; 
 producing, by accessing a graph, a schedule of events for the event requests, the schedule comprising designated times that do not violate a constraint of the constellation of imaging satellites, 
 wherein the 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, 
 wherein producing the schedule comprises 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 schedule of events, the weights for the one or more downlink events being based, at least in part, on a downlink time associated with the downlink event; 
 generating one or more control instructions based at least in part on the schedule; and 
 transmitting the one or more control instructions to one or more of the imaging satellites in the constellation to initiate a performance of the events in the schedule at a respective designated time. 
   
     
     
         30 . The system of  claim 29 , wherein weights for the one or more downlink events are higher than weights for the one or more imaging events. 
     
     
         31 . The system of  claim 30 , wherein the weights for the one or more downlink events are determined based, at least in part, on a time to downlink images from one or more of the imaging events. 
     
     
         32 . The system of  claim 29 , wherein the operations further comprise:
 receiving user input relating to changes to one or more of the event requests; and   adjusting the schedule of events based, at least in part, on the user input.   
     
     
         33 . The method of  claim 32 , wherein the schedule of events comprises one or more disabled edges in the graph that are based, at least in part, on the user input. 
     
     
         34 . The method of  claim 33 , wherein at least one edge terminating at a node associated with the user input is disabled to force out an event from the schedule of events. 
     
     
         35 . The method of  claim 29 , wherein the schedule of events is associated with a highest weighted path through the graph. 
     
     
         36 . The method of  claim 29 , wherein the graph is a directed acyclic graph. 
     
     
         37 . One or more non-transitory computer-readable media that store instructions that are executable by one or more processors to perform operations comprising:
 receiving event requests comprising one or more imaging events or one or more downlink events;   identifying one or more imaging satellites in the constellation of imaging satellites which will be positioned over one or more regions at one or more designated times suitable to perform the event requests;   producing, by accessing a graph, a schedule of events for the event requests, the schedule comprising designated times that do not violate a constraint of the constellation of imaging satellites,   wherein the 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,   wherein producing the schedule comprises 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 schedule of events, the weights for the one or more downlink events being based, at least in part, on a downlink time associated with the downlink event;   generating one or more control instructions based at least in part on the schedule; and   transmitting the one or more control instructions to one or more of the imaging satellites in the constellation to initiate a performance of the events in the schedule at a respective designated time.   
     
     
         38 . The one or more non-transitory computer-readable media of  claim 37 ,
 wherein the schedule of events is associated with a highest weighted path through the graph.   
     
     
         39 . The one or more non-transitory computer-readable media of  claim 37 ,
 wherein the operations further comprise:   receiving user input relating to changes to one or more of the event requests; and   adjusting the schedule of events based, at least in part, on the user input.   
     
     
         40 . The one or more non-transitory computer-readable media of  claim 39 , wherein the graph is a directed acyclic graph.