SATELLITE SCHEDULING SYSTEM

• US 20140039963A1
• Filed: 08/02/2013
• Published: 02/06/2014
• Est. Priority Date: 08/03/2012
• Status: Active Grant

• Current Assignee: Planet Labs PBC
• Original Assignee: Skybox Imaging, Inc. (Planet Labs PBC)
• Inventors: Mann, Julian M., Berkenstock, Daniel, Augenstein, Sean
• Granted Patent: US 9,262,734 B2
• Time in Patent Office: Days
• US Class Current: 705/7.24
• CPC Class Codes: B64G 1/1021 Earth observation satellites
• CPC Class Codes: B64G 1/1085 Swarms and constellations
• CPC Class Codes: B64G 1/242 Orbits and trajectories
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/921 Spatial

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. 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.

Claims

1. A system for scheduling events for a constellation of imaging satellites, the system comprising:

non-transitory data storage configured to store satellite properties information corresponding to characteristics of one or more imaging satellites in the constellation of imaging satellites;

a computing device in communication with the data storage, the computing device configured to execute;

an order management system configured to produce or receive requests for an image collection event;

an orbit analysis system configured to identify 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;

a maintenance system configured to produce requests for onboard maintenance for imaging satellites in the constellation of imaging satellites;

a satellite scheduling system configured to receive event requests and satellite properties and to produce a near-optimal schedule of events that does not violate constraints of the constellation of imaging satellites; and

a satellite control system configured to receive the near-optimal schedule of events and convert the near-optimal schedule of events to control instructions for transmission to the one or more imaging satellites in the constellation of imaging satellites.

2. The system of claim 1, wherein the satellite scheduling system is configured to use a directed acyclic graph to produce the near-optimal schedule of events.

3. The system of claim 1, further comprising an event analysis system configured to receive information from the one or more imaging satellites, wherein the received information is related to a result of executing the control instructions transmitted to the one or more imaging satellites.

4. The system of claim 3, wherein the satellite scheduling system is configured to receive event analysis information from the event analysis system and to produce an updated near-optimal schedule of events that incorporates the received event analysis information.

5. The system of claim 1, wherein the order management system is further configured to assign a priority to each event request and the satellite scheduling system is configured to receive the priority associated with each event request and to use the priority associated with each event request to produce the near-optimal schedule of events.

6. The system of claim 1, wherein the order management system is further configured to receive crowd-sourced data and analyze the crowd-sourced data to determine an image collection event.

7. 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 objects; and

a command module configured to receive the near-optimal schedule of events and create control instructions for the plurality of objects based at least in part on the near-optimal schedule of events.

8. The system of claim 7, wherein the scheduling module is configured to use a directed acyclic graph to produce the near-optimal schedule of events.

9. The system of claim 8, wherein at least one event is such that all acceptable paths through the directed acyclic graph pass through the event.

10. The system of claim 7, wherein the characteristics of the plurality of satellites include pair-wise constraints and cumulative constraints.

11. The system of claim 10, wherein the cumulative constraints include one of a data capacity limitation, a power requirement, or a thermal value.

12. The system of claim 10, wherein the pair-wise constraints include a slewing rate of a satellite.

13. The system of claim 7, 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.

14. The system of claim 7, 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.

15. The system of claim 7, wherein the event system is further configured to produce an event based on crowd-sourced data.

16. The system of claim 7, wherein the plurality of satellites comprises micro-satellites.

17. 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.

18. The non-transitory computer storage of claim 17, 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.

19. The non-transitory computer storage of claim 17, 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.

20. The non-transitory computer storage of claim 17, 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.

21. The non-transitory computer storage of claim 17, further comprising a display module configured to display the near-optimal schedule of events.

22. 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.

23. The method of claim 22, wherein producing the near-optimal schedule of events comprises utilizing a directed acyclic graph to determine the near-optimal schedule of events.

24. The method of claim 22, 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.

25. The method of claim 22, 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.

26. The method of claim 22, 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.

27. The method of claim 22, wherein method produces the near-optimal schedule of events in near real-time.

28. The method of claim 27, wherein method produces the near-optimal schedule of events in less than about 10 minutes.

29. The method of claim 22, wherein at least some of the plurality of objects comprise satellites.