Hierarchical satellite task scheduling system

• US 10,474,976 B2
• Filed: 10/22/2018
• Issued: 11/12/2019
• Est. Priority Date: 10/20/2017
• Status: Active Grant

• Current Assignee: HawkEye 360, Inc. (Advance Publications Incorporated)
• Original Assignee: HawkEye 360, Inc. (Advance Publications Incorporated)
• Inventors: Clancy, T. Charles, McGwier, Robert W., O'Shea, Timothy James, McCarthy, Nicholas Aaron
• Primary Examiner(s): Kamran, Mehran
• Application Number:
  US16/167,001
• Publication Number:
  US 20190121665A1
• Time in Patent Office: 386 Days
• Field of Search: 718104
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06313 Resource planning in a project environment
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: H04B 7/18502 Airborne stations
• CPC Class Codes: H04B 7/18519 Operations control, administration or maintenance

Abstract

A task scheduling system that can be used to improve task assignment for multiple satellites, and thereby improve resource allocation in the execution of a task. In some implementations, configuration data for one or more satellites is obtained. Multiple objectives corresponding to a task to be performed using the satellites, and resource parameters associated with executing the task to be performed using the satellites are identified. A score for each objective included in the multiple objectives is computed by the terrestrial scheduler based on the resource parameters and the configuration data for the one or more satellites. The multiple objectives are assigned to one or more of the satellites. Instructions are provided to the one or more satellites that cause the one or more satellites to execute the task according to the assignment of the objectives to the one or more satellites.

Claims

1. A method comprising:

obtaining, by a terrestrial scheduler of a server system, configuration data for multiple satellites associated with the server system, wherein each satellite from among the multiple satellites comprises an aerial scheduler configured to exchange communications with the terrestrial scheduler;

identifying, by the terrestrial scheduler, (i) multiple objectives corresponding to a task to be performed using the multiple satellites, (ii) respective classifications of each of the multiple objectives, and (iii) resource parameters associated with executing the task to be performed using the multiple satellites;

computing, by the terrestrial scheduler, a score for each objective included in the multiple objectives based on the resource parameters and the configuration data for the multiple satellites, each score representing a prioritization of a corresponding objective from among the multiple objectives;

based on the scores and the classifications for the multiple objectives;

assigning, by the terrestrial scheduler, a first subset of objectives to a first satellite included in the multiple satellites, and

assigning, by the terrestrial scheduler, a second subset of objectives to a second satellite included in the multiple satellites,

wherein the first and second subsets of objectives each include at least one objective that is not included in the other subset;

providing, by the terrestrial scheduler and to the aerial scheduler of the first satellite, a first instruction that, when received by the first satellite, causes the first satellite to execute the first subset of objectives; and

providing, by the terrestrial scheduler and to the aerial scheduler of the second satellite, a second instruction that, when received by the second satellite, causes the second satellite to execute the second subset of objectives.

2. The method of claim 1, wherein the first instruction causes the first satellite to configure at least one of antennas or radio tuning parameters of the first satellite.

3. The method of claim 1, wherein the scores for the objectives comprise a particular score for a particular objective that represents a predicted probability of successfully executing the particular objective.

4. The method of claim 3, wherein the particular score for the particular objective is determined based on historical data representing prior executions of the particular objective.

5. The method of claim 3, wherein the particular score for the particular objective is determined based on a probabilistic model associated with prior executions of the particular objective.

6. The method of claim 1, wherein the scores for the objectives comprise a particular score for a particular objective that represents an estimated resource consumption associated with executing the particular objective.

7. The method of claim 1, wherein the scores for the objectives comprise a particular score for a particular objective that represents an estimated resource cost associated with executing the particular objective.

8. The method of claim 1, wherein the resource parameters comprise a particular resource parameter that specifies at least one of a network bandwidth or latency required to exchange data between a particular satellite and the server system.

9. The method of claim 1, wherein the resource parameters comprise a particular resource parameter that specifies at least one of antenna or digitizer usage by a particular satellite from among the multiple satellites.

10. The method of claim 1, wherein the resource parameters comprise a particular resource parameter that specifies a power charge level of a particular satellite.

11. The method of claim 1, wherein the resource parameters comprise a particular resource parameter that specifies a computational capacity of a particular satellite.

12. The method of claim 1, wherein the resource parameters comprise a particular resource parameter that specifies a finite bandwidth of a particular satellite.

13. The method of claim 1, wherein the resource parameters comprise a particular resource parameter that specifies a storage required on a particular satellite to perform a particular objective corresponding to the task.

14. The method of claim 1, wherein the objectives corresponding to the task comprises a particular objective specifying reception of emissions from a specified geospatial region or at a specified time window.

15. The method of claim 1, wherein the objectives corresponding to the task comprise a first objective and a second objective;

and

wherein determining the score for each objective included in the multiple objectives comprises determining a first score for the first objective and a second score for the second objective, and the method further comprises determining a sequence to execute the first objective and the second objective based on values of the first score and the second score.

16. The method of claim 1, further comprising:

obtaining, by the terrestrial scheduler, execution data indicating that the objectives corresponding to the task have been performed by the multiple satellites;

processing, by the terrestrial scheduler, the execution data to compute one or more metrics corresponding to the execution of the task by the multiple satellites; and

generating, by the terrestrial scheduler, an execution report that includes at least one of the one or more metrics corresponding to the execution of the task by the multiple satellites.

17. The method of claim 1, further comprising:

computing, by the terrestrial scheduler, an aggregate score for the task based on combining the scores computed for each objective included in the objectives corresponding to the task.

18. The method of claim 1, wherein the multiple objectives comprise at least one of:

a first objective to receive emission data that identifies a presence of a ship in a particular region of the Earth;

or

a second objective to monitor movement of other ships in multiple regions of the Earth that do not include the particular region.

19. The method of claim 18, wherein the particular region of the Earth comprises a particular maritime region and the multiple regions of the Earth comprise maritime regions that do not include the particular maritime region.

20. A system comprising:

one or more computers; and

one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

obtaining, by a terrestrial scheduler of a server system, configuration data for multiple satellites associated with the server system, wherein each satellite from among the multiple satellites comprises an aerial scheduler configured to exchange communications with the terrestrial scheduler;

identifying, by the terrestrial scheduler, (i) multiple objectives corresponding to a task to be performed using the multiple satellites, (ii) respective classifications of each of the multiple objectives, and (iii) resource parameters associated with executing the task to be performed using the multiple satellites;

computing, by the terrestrial scheduler, a score for each objective included in the multiple objectives based on the resource parameters and the configuration data for the multiple satellites, each score representing a prioritization of a corresponding objective from among the multiple objectives;

based on the scores and the classifications for the multiple objectives;

assigning, by the terrestrial scheduler, a first subset of objectives to a first satellite included in the multiple satellites, and

assigning, by the terrestrial scheduler, a second subset of objectives to a second satellite included in the multiple satellites,

wherein the first and second subsets of objectives each include at least one objective that is not included in the other subset;

providing, by the terrestrial scheduler and to the aerial scheduler of the first satellite, a first instruction that, when received by the first satellite, causes the first satellite to execute the first subset of objectives; and

providing, by the terrestrial scheduler and to the aerial scheduler of the second satellite, a second instruction that, when received by the second satellite, causes the second satellite to execute the second subset of objectives.