# US 2025/0086026 A1 · Methods and systems for distributed task scheduling in satellite cluster for earth observation data analytics

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0086026 A1
- Document ID: US20250086026A1
- Status: Published application
- Kind: A1
- Application number: 18/805,602
- Filed: 2024-08-15
- Published: 2025-03-13
- Earliest claimed: 2023-09-11
- Assignees: Tata Consultancy Services Limited
- Applicants: Tata Consultancy Services Limited
- Inventors: Swagata BISWAS; Himadri SEKHAR PAUL
- Web page: https://patentgrep.com/patent/US20250086026A1

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- B64G 1/1021: {Earth observation satellites}
- B64G 1/1085: {Swarms and constellations}
- G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)}
- G06F 9/5072: {Grid computing}
- H04B 7/18519: {Operations control, administration or maintenance}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- B64G: COSMONAUTICS; VEHICLES OR EQUIPMENT THEREFOR
- H04B: TRANSMISSION

## Abstract

The disclosure relates generally to methods and systems for distributed task scheduling in a satellite cluster for earth observation data analytics. Conventional techniques proposed different scheduling techniques to gather earth observation data and suitable routing algorithms to route the data gathered to the ground. However, utilizing on-board computing facility are limited. The present disclosure discloses a distributed task scheduling algorithm for effective utilization of idle computing resources, which works in two phases namely an offline or a static phase and an online or a dynamic phase. In the offline phase, a scheduler takes a first subtask of each task for execution, the soft real-time constraints, and the resource capabilities to schedule the tasks. In the dynamic phase, the scheduler takes a changing inter-satellite and satellite-to-ground station connectivity, resource status and the changing task status to schedule the tasks, through a task partitioning, a task distribution, and a task handover.

## Claims

### Claim 1

A processor-implemented method, comprising the steps of:
receiving, via one or more hardware processors, a plurality of tasks to be executed by a plurality of satellites present in a satellite cluster and one or more ground stations connected to the one or more satellites, a predefined soft real-time constraint defined for each task of the plurality of tasks, one or more resource requirements required for each task, and one or more resource capabilities of each of the one or more satellites and each of the one or more ground stations, wherein each task comprises a plurality of subtasks and one or more dependencies of each subtask on remaining subtasks of the plurality of subtasks;
assigning, via the one or more hardware processors, the plurality of tasks to the plurality of satellites present in the satellite cluster and the one or more ground stations, in a static phase and a dynamic phase in a sequence, using an optimization technique, to obtain an optimized distributed schedule of the plurality of tasks,
wherein assigning the plurality of tasks in the static phase comprising:
(i) identifying a first subtask among the plurality of subtasks for each task, wherein the first subtask is an earth observation data collection task;
(ii) receiving one or more resources required for the first subtask of each task;
(iii) identifying one or more qualifying satellites among the plurality of satellites, for the first subtask of each task, based on the one or more resource capabilities of each satellite, and the one or more resources required for the first subtask;
(iv) calculating a value of a reward function for each of the one or more qualifying satellites, for executing the first subtask of each task, based on a set of operational attributes of an associated first subtask, wherein the reward function is defined in the optimization technique; and
(v) selecting a qualifying satellite among the one or more qualifying satellites having a maximum value of the reward function, based on the predefined soft real-time constraint defined for each task, as a controller agent for each task of the plurality of tasks; and
wherein scheduling the plurality of tasks in the dynamic phase comprising:
(i) executing the first subtask of each task of the plurality of tasks, by an associated controller agent selected in the static phase;
(ii) identifying a set of remaining subtasks for each task of the plurality of tasks, after the execution of the first subtask and removing the first subtask from an associated task;
(iii) sorting one or more subtasks present in the set of remaining subtasks for each task of the plurality of tasks, in a topological order, based on the one or more dependencies of each subtask;
(iv) if there is a single subtask present in the set of remaining subtasks for each task after sorting in the topological order, at a current level of execution of one or more execution levels, then:
(a) executing the single subtask by the associated controller agent selected in the static phase, if one or more resource requirements of the single subtask matches with the one or more resource capabilities of the associated controller agent selected in the static phase and matches with the predefined soft real-time constraint; and
(b) handing over the single subtask to other satellites for execution using a handover mechanism, if the one or more resource requirements of the single subtask does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint;
(v) if there are multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution of one or more execution levels, then:
(a) executing the multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution, by the associated controller agent selected in the static phase, if one or more resource requirements of the multiple subtasks matches with the one or more resource capabilities of the associated controller agent selected in the static phase and matches with the predefined soft real-time constraint; and
(b) handing over the multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution to other satellites for execution using a handover mechanism, if the one or more resource requirements of the multiple subtasks does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint; and
executing, via the one or more hardware processors, the plurality of tasks by the plurality of satellites present in the satellite cluster and the one or more ground stations, using the optimized distributed schedule.

### Claim 2 (depends on 1)

The method of claim 1, wherein each subtask of the plurality of subtasks present in each task, is associated with a set of operational attributes comprising (i) a waiting time, (ii) a computational latency, (iii) a communication latency, and (iv) a task priority.

### Claim 3 (depends on 1)

The method of claim 1, wherein the plurality of subtasks present in each task are executed at one or more execution levels, based on the one or more dependencies of each subtask on remaining subtasks of the plurality of subtasks.

### Claim 4 (depends on 1)

The method of claim 1, wherein the plurality of subtasks present in each task are one or more of: (i) an earth observation data collection task, (ii) one or more earth observation data analytics tasks, and (iii) one or more earth observation data communication tasks, and wherein each of the one or more earth observation data collection tasks is to gather an earth observation data by each of the one or more satellites for a predefined region on earth, each of the one or more earth observation data analytics tasks is to analyze the earth observation data by the plurality of satellites or the one or more ground stations to determine one or more inferences of an associated earth observation data collection task, and each of the one or more earth observation data communication tasks is one of (i) a data exchange subtask and (ii) a command exchange subtask, between the plurality of satellites and the one or more ground stations.

### Claim 5 (depends on 1)

The method of claim 1, wherein handing over the single subtask to other satellites for execution using the handover mechanism, if the one or more resource requirements of the single subtask does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint, comprising:
sending a handover request message by the associated controller agent to one or more satellites present in a hop level for executing the single subtask;
receiving the one or more resource capabilities of each of the one or more satellites in the hop level, by the associated controller agent;
identifying the one or more qualifying satellites among the one or more satellites present in the hop level, for executing the single subtask, based on the one or more resource capabilities of each of the plurality of satellites, and the one or more resources required for the single subtask;
calculating the value of the reward function for each of the one or more qualifying satellites, for executing the single subtask of each task, based on the set of operational attributes of the single subtask; and
selecting a qualifying satellite among the one or more qualifying satellites present in the hop level having the maximum value of the reward function, based on the predefined soft real-time constraint defined for each task, as a controller agent for the associated single subtask of each task and handing over the associated subtask to an associated controller agent.

### Claim 6 (depends on 5)

The method of claim 5, wherein if the one or more qualifying satellites among the one or more satellites present in the hop level, are not identified for executing the single subtask, based on the one or more resource capabilities of each of the plurality of satellites, and the one or more resources required for the single subtask and does not match with the predefined soft real-time constraint, then the single subtask is handed over to the one or more satellites present in next hop level.

### Claim 7 (depends on 1)

The method of claim 1, wherein handing over the multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution to other satellites for execution using the handover mechanism, if the one or more resource requirements of the multiple subtasks does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint, comprises:
partitioning each of the multiple subtasks, based on a predefined partitioning size;
sending a handover request message by the associated controller agent to the one or more satellites present in a hop level for executing the multiple subtask;
receiving the one or more resource capabilities of each of the one or more satellites in the hop level, by the associated controller agent;
identifying the one or more qualifying satellites among the one or more satellites present in the hop level, for executing the multiple subtasks after the partitioning, based on the one or more resource capabilities of each satellite, and the one or more resources required for each of the multiple subtasks;
calculating the value of the reward function for each of the one or more qualifying satellites, for executing the multiple subtasks of each task after the partitioning, based on the set of operational attributes associated to each subtask; and
selecting a qualifying satellite among the one or more qualifying satellites having the maximum value of the reward function, based on the predefined soft real-time constraint defined for each task, as a controller agent for executing the multiple subtasks of each task after the partitioning and handing over the multiple subtasks of each task to an associated controller agent.

### Claim 8 (depends on 7)

The method of claim 7, wherein if the one or more qualifying satellites among the one or more satellites present in the hop level, are not identified for executing the multiple subtasks, based on the one or more resource capabilities of each satellite, and the one or more resources required for each of the multiple subtasks and does not match with the predefined soft real-time constraint, then distributing the multiple subtasks of each task to the one or more satellites present in a next hop level.

### Claim 9

A system comprising:
a memory storing instructions;
one or more input/output (I/O) interfaces; and
one or more hardware processors coupled to the memory via the one or more I/O interfaces, wherein the one or more hardware processors are configured by the instructions to:
receive a plurality of tasks to be executed by a plurality of satellites present in a satellite cluster and one or more ground stations connected to the one or more satellites, a predefined soft real-time constraint defined for each task of the plurality of tasks, one or more resource requirements required for each task, and one or more resource capabilities of each of the one or more satellites and each of the one or more ground stations, wherein each task comprises a plurality of subtasks and one or more dependencies of each subtask on remaining subtasks of the plurality of subtasks;
assign the plurality of tasks to the plurality of satellites present in the satellite cluster and the one or more ground stations, in a static phase and a dynamic phase in a sequence, using an optimization technique, to obtain an optimized distributed schedule of the plurality of tasks,
wherein assigning the plurality of tasks in the static phase comprising:
(i) identifying a first subtask among the plurality of subtasks for each task, wherein the first subtask is an earth observation data collection task;
(ii) receiving one or more resources required for the first subtask of each task;
(iii) identifying one or more qualifying satellites among the plurality of satellites, for the first subtask of each task, based on the one or more resource capabilities of each satellite, and the one or more resources required for the first subtask;
(iv) calculating a value of a reward function for each of the one or more qualifying satellites, for executing the first subtask of each task, based on a set of operational attributes of an associated first subtask, wherein the reward function is defined in the optimization technique; and
(v) selecting a qualifying satellite among the one or more qualifying satellites having a maximum value of the reward function, based on the predefined soft real-time constraint defined for each task, as a controller agent for each task of the plurality of tasks; and
wherein scheduling the plurality of tasks in the dynamic phase comprising:
(i) executing the first subtask of each task of the plurality of tasks, by an associated controller agent selected in the static phase;
(ii) identifying a set of remaining subtasks for each task of the plurality of tasks, after the execution of the first subtask and removing the first subtask from an associated task;
(iii) sorting one or more subtasks present in the set of remaining subtasks for each task of the plurality of tasks, in a topological order, based on the one or more dependencies of each subtask;
(iv) if there is a single subtask present in the set of remaining subtasks for each task after sorting in the topological order, at a current level of execution of one or more execution levels, then:
(a) executing the single subtask by the associated controller agent selected in the static phase, if one or more resource requirements of the single subtask matches with the one or more resource capabilities of the associated controller agent selected in the static phase and matches with the predefined soft real-time constraint; and
(b) handing over the single subtask to other satellites for execution using a handover mechanism, if the one or more resource requirements of the single subtask does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint;
(v) if there are multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution of one or more execution levels, then:
(a) executing the multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution, by the associated controller agent selected in the static phase, if one or more resource requirements of the multiple subtasks matches with the one or more resource capabilities of the associated controller agent selected in the static phase and matches with the predefined soft real-time constraint; and
(b) handing over the multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution to other satellites for execution using a handover mechanism, if the one or more resource requirements of the multiple subtasks does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint; and
execute the plurality of tasks by the plurality of satellites present in the satellite cluster and the one or more ground stations, using the optimized distributed schedule.

### Claim 10 (depends on 9)

The system of claim 9, wherein each subtask of the plurality of subtasks present in each task, is associated with a set of operational attributes comprising (i) a waiting time, (ii) a computational latency, (iii) a communication latency, and (iv) a task priority.

### Claim 11 (depends on 9)

The system of claim 9, wherein the plurality of subtasks present in each task are executed at one or more execution levels, based on the one or more dependencies of each subtask on remaining subtasks of the plurality of subtasks.

### Claim 12 (depends on 9)

The system of claim 9, wherein the plurality of subtasks present in each task are one or more of: (i) an earth observation data collection task, (ii) one or more earth observation data analytics tasks, and (iii) one or more earth observation data communication tasks, and wherein each of the one or more earth observation data collection tasks is to gather an earth observation data by each of the one or more satellites for a predefined region on the earth, each of the one or more earth observation data analytics tasks is to analyze the earth observation data by the plurality of satellites or the one or more ground stations to determine one or more inferences of an associated earth observation data collection task, and each of the one or more earth observation data communication tasks is one of (i) a data exchange subtask and (ii) a command exchange subtask, between the plurality of satellites and the one or more ground stations.

### Claim 13 (depends on 9)

The system of claim 9, wherein the one or more hardware processors are configured to hand over the single subtask to other satellites for execution using the handover mechanism, if the one or more resource requirements of the single subtask does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint, by:
sending a handover request message by the associated controller agent to one or more satellites present in a hop level for executing the single subtask;
receiving the one or more resource capabilities of each of the one or more satellites in the hop level, by the associated controller agent;
identifying the one or more qualifying satellites among the one or more satellites present in the hop level, for executing the single subtask, based on the one or more resource capabilities of each satellite, and the one or more resources required for the single subtask;
calculating the value of the reward function for each of the one or more qualifying satellites, for executing the single subtask of each task, based on the set of operational attributes of the single subtask; and
selecting a qualifying satellite among the one or more qualifying satellites present in the hop level having the maximum value of the reward function, based on the predefined soft real-time constraint defined for each task, as a controller agent for the associated single subtask of each task and handing over the associated subtask to an associated controller agent.

### Claim 14 (depends on 13)

The system of claim 13, wherein the one or more hardware processors are configured to hand over the single subtask to the one or more satellites present in next hop level, if the one or more qualifying satellites among the one or more satellites present in the hop level, are not identified for executing the single subtask, based on the one or more resource capabilities of each satellite, and the one or more resources required for the single subtask and does not match with the predefined soft real-time constraint.

### Claim 15 (depends on 9)

The system of claim 9, wherein the one or more hardware processors are configured to hand over the multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution to other satellites for execution using the handover mechanism, if the one or more resource requirements of the multiple subtasks does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint, by:
partitioning each of the multiple subtasks, based on a predefined partitioning size;
sending a handover request message by the associated controller agent to the one or more satellites present in a hop level for executing the multiple subtask;
receiving the one or more resource capabilities of each of the one or more satellites in the hop level, by the associated controller agent;
identifying the one or more qualifying satellites among the one or more satellites present in the hop level, for executing the multiple subtasks after the partitioning, based on the one or more resource capabilities of each of the plurality of satellites, and the one or more resources required for each of the multiple subtasks;
calculating the value of the reward function for each of the one or more qualifying satellites, for executing the multiple subtasks of each task after the partitioning, based on the set of operational attributes associated to each subtask; and
selecting a qualifying satellite among the one or more qualifying satellites having the maximum value of the reward function, based on the predefined soft real-time constraint defined for each task, as a controller agent for executing the multiple subtasks of each task after the partitioning and handing over the multiple subtasks of each task to an associated controller agent.

### Claim 16 (depends on 15)

The system of claim 15, wherein the one or more hardware processors are configured to distribute the multiple subtasks of each task to the one or more satellites present in a next hop level, if the one or more qualifying satellites among the one or more satellites present in the hop level, are not identified for executing the multiple subtasks, based on the one or more resource capabilities of each of the plurality of satellites, and the one or more resources required for each of the multiple subtasks and does not match with the predefined soft real-time constraint.

### Claim 17

One or more non-transitory machine-readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors cause:
receiving a plurality of tasks to be executed by a plurality of satellites present in a satellite cluster and one or more ground stations connected to the one or more satellites, a predefined soft real-time constraint defined for each task of the plurality of tasks, one or more resource requirements required for each task, and one or more resource capabilities of each of the one or more satellites and each of the one or more ground stations, wherein each task comprises a plurality of subtasks and one or more dependencies of each subtask on remaining subtasks of the plurality of subtasks;
assigning the plurality of tasks to the plurality of satellites present in the satellite cluster and the one or more ground stations, in a static phase and a dynamic phase in a sequence, using an optimization technique, to obtain an optimized distributed schedule of the plurality of tasks,
wherein assigning the plurality of tasks in the static phase comprising:
(i) identifying a first subtask among the plurality of subtasks for each task, wherein the first subtask is an earth observation data collection task;
(ii) receiving one or more resources required for the first subtask of each task;
(iii) identifying one or more qualifying satellites among the plurality of satellites, for the first subtask of each task, based on the one or more resource capabilities of each satellite, and the one or more resources required for the first subtask;
(iv) calculating a value of a reward function for each of the one or more qualifying satellites, for executing the first subtask of each task, based on a set of operational attributes of an associated first subtask, wherein the reward function is defined in the optimization technique; and
(v) selecting a qualifying satellite among the one or more qualifying satellites having a maximum value of the reward function, based on the predefined soft real-time constraint defined for each task, as a controller agent for each task of the plurality of tasks; and
wherein scheduling the plurality of tasks in the dynamic phase comprising:
(i) executing the first subtask of each task of the plurality of tasks, by an associated controller agent selected in the static phase;
(ii) identifying a set of remaining subtasks for each task of the plurality of tasks, after the execution of the first subtask and removing the first subtask from an associated task;
(iii) sorting one or more subtasks present in the set of remaining subtasks for each task of the plurality of tasks, in a topological order, based on the one or more dependencies of each subtask;
(iv) if there is a single subtask present in the set of remaining subtasks for each task after sorting in the topological order, at a current level of execution of one or more execution levels, then:
(a) executing the single subtask by the associated controller agent selected in the static phase, if one or more resource requirements of the single subtask matches with the one or more resource capabilities of the associated controller agent selected in the static phase and matches with the predefined soft real-time constraint; and
(b) handing over the single subtask to other satellites for execution using a handover mechanism, if the one or more resource requirements of the single subtask does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint;
(v) if there are multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution of one or more execution levels, then:
(a) executing the multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution, by the associated controller agent selected in the static phase, if one or more resource requirements of the multiple subtasks matches with the one or more resource capabilities of the associated controller agent selected in the static phase and matches with the predefined soft real-time constraint; and
(b) handing over the multiple subtasks present in the set of remaining subtasks for each task after sorting in the topological order, at the current level of execution to other satellites for execution using a handover mechanism, if the one or more resource requirements of the multiple subtasks does not match with the one or more resource capabilities of the associated controller agent selected in the static phase and does not match with the predefined soft real-time constraint; and
executing, via the one or more hardware processors, the plurality of tasks by the plurality of satellites present in the satellite cluster and the one or more ground stations, using the optimized distributed schedule.
