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. Violation of cumulative constraints can be identified at the moment of constraint violation such that events resulting in constraint violations can be removed from the schedule while the schedule is being determined. By removing the events triggering constraint violations at the point of constraint violation, the systems and methods provided can determine optimal or near-optimal schedules in a relatively quick and efficient manner compared to systems and methods that check for violations of cumulative constraints after determining a schedule. 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 crowd-sourced data to determine events of interest for acquisition of images.
1. A system for scheduling events for a plurality of satellites, the system comprising:
a computing device configured to execute:
an event system configured to produce, store, or receive event requests;
a constraints system configured to produce, store, or receive characteristics of the plurality of satellites;
a prioritization system configured to produce, store, or receive priority information corresponding to the event requests; and
a control system operatively coupled to the event system, the constraints system, and the prioritization system, the control system comprising:
a scheduling module configured to process the event requests received from the event system, the characteristics of the plurality of satellites received from the constraints system, and the priority information received from the prioritization system and to produce a near-optimal schedule of events in near real-time that does not violate constraints of the plurality of satellites; and
a command module configured to receive the near-optimal schedule of events and create control instructions for the plurality of satellites based at least in part on the near-optimal schedule of events.
2. The system of claim 1 , wherein the scheduling module is configured to use a directed acyclic graph to produce the near-optimal schedule of events.
3. The system of claim 2 , wherein at least one event is such that all acceptable paths through the directed acyclic graph pass through the event.
4. The system of claim 1 , wherein the characteristics of the plurality of satellites include pair-wise constraints and cumulative constraints.
5. The system of claim 4 , wherein the cumulative constraints include one of a data capacity limitation, a power requirement, or a thermal value.
6. The system of claim 4 , wherein the pair-wise constraints include a slewing rate of a satellite.
7. The system of claim 1 , wherein the scheduling module is configured to produce the near-optimal schedule of events by building a sequence of events and removing a newly added event if a utilization function does not increase.
8. The system of claim 1 , wherein the scheduling module is produce the near-optimal schedule of events by building a sequence of events and removing a newly added event if a cumulative constraint would be violated by maintaining the newly added event in the near-optimal schedule of events.
9. The system of claim 1 , wherein the event system is further configured to produce an event based on crowd-sourced data.
10. The system of claim 1 , wherein the plurality of satellites comprises micro-satellites.
11. Non-transitory computer storage configured with executable instructions for scheduling events for a plurality of satellites, the executable instructions comprising:
a scheduling module configured to produce a near-optimal schedule of events in near real-time by building a temporary schedule of events one event at a time and removing a newly added event from the temporary schedule if it causes a violation of a cumulative constraint; and
a command module configured to receive the near-optimal schedule of events and create control instructions for the plurality of satellites based at least in part on the near-optimal schedule of events,
wherein the near-optimal schedule of events is the temporary schedule of events which does not violate of a cumulative constraint.
12. The non-transitory computer storage of claim 11 , wherein the near-optimal schedule of events is the temporary schedule of events which results in a higher value for a utilization function than other temporary schedules of events.
13. The non-transitory computer storage of claim 11 , wherein the scheduling module is configured to build the temporary schedule of events by starting with a first event and adding a second event later in time than the first event, wherein the second event is not pair-wise constrained from following the first event in the temporary schedule.
14. The non-transitory computer storage of claim 11 , wherein the satellite comprises an imaging satellite, and the scheduling module is further configured to:
analyze crowd-sourced data to determine an event of interest;
determine a geographic location for the event of interest using the crowd-sourced data; and
create an image acquisition request comprising the determined geographic location of the event of interest.
15. The non-transitory computer storage of claim 11 , further comprising a display module configured to display the near-optimal schedule of events.
16. A method for scheduling events for a plurality of objects, the method comprising:
under control of a computing device in communication with non-transitory data storage configured to store properties corresponding to characteristics of the plurality of objects:
determining a likely path for each of the plurality of objects;
receiving event requests and object properties for the plurality of objects;
producing a near-optimal schedule of events that does not violate constraints of the plurality of objects; and
converting the near-optimal schedule of events to control instructions for transmission to the plurality of objects,
wherein a first constraint of the plurality of objects is a cumulative constraint and a second constraint of the plurality of objects is a pair-wise constraint.
17. The method of claim 16 , wherein producing the near-optimal schedule of events comprises utilizing a directed acyclic graph to determine the near-optimal schedule of events.
18. The method of claim 16 , wherein at least some of the plurality of objects comprise imaging satellites, and the cumulative constraint is one of a data capacity limitation, a power requirement, or a thermal value.
19. The method of claim 16 , wherein at least some of the plurality of objects comprise imaging satellites, and the pair-wise constraint is a slewing rate of one of the imaging satellites.
20. The method of claim 16 , wherein at least some of the plurality of objects comprise a constellation of imaging satellites, and the method further comprises:
accessing crowd-sourced data;
analyzing the crowd-sourced data to determine an event of interest;
determining a geographic location for the event of interest using the crowd-sourced data;
determining a degree of relevance for the event of interest;
creating an image acquisition request, wherein the image acquisition request comprises the determined geographic location of the event of interest; and
including the image acquisition request in the schedule of events.
21. The method of claim 16 , wherein the method produces the near-optimal schedule of events in near real-time.
22. The method of claim 21 , wherein the method produces the near-optimal schedule of events in less than about 10 minutes.
23. The method of claim 16 , wherein at least some of the plurality of objects comprise satellites.