Source-linked AI summary
Task-Driven Three-Layer Distributed Scheduling for Emergency Earth Observation in Large Low-Earth-Orbit Constellations
Qian Yin, Xinwei Wang, Guohua Wu
TL;DR
Emergency requests arriving during routine execution create a distributed scheduling problem under intermittent communication. T3L-DS coordinates task-specific satellite clusters with onboard bidding and reallocation, achieving the strongest emergency service among distributed methods while preserving routine coverage under tested conditions.
Problem
Emergency requests arriving during committed routine execution require timely insertion without excessive disruption, while intermittent contacts make constellation-wide schedule reconstruction difficult.
Method
T3L-DS maps demands and footprints to a common geographic grid, forms temporary task-specific clusters, and coordinates onboard bidding with cluster-level evaluation and reallocation.
Results
T3L-DS provides the strongest emergency service among distributed methods and preserves most routine coverage under tested conditions; SA achieves 5.5% more emergency coverage but pre-empts 79.8% of routine cells versus 2.3%.
Takeaways & Limitations
The experiments support T3L-DS as an effective distributed framework for emergency scheduling under the tested conditions.
Takeaways & Limitations
The framework assumes satellites have the onboard computing, inter-satellite communication, and target-recognition capabilities needed to process emergency requests.
Abstract
from arXiv · showhide
Large low-Earth-orbit (LEO) Earth-observation (EO) constellations offer frequent access to geographically dispersed ground targets, but emergency requests may arrive after committed routine-plan execution has begun. The resulting dynamic emergency observation scheduling problem (DEOSP) requires urgent tasks to be inserted under intermittent ground contact without excessive routine-plan disruption. To address DEOSP, we propose a task-driven three-layer distributed scheduling (T3L-DS) method, which represents task demand and sensor footprints on a common geographic grid and forms temporary clusters from observation capabilities and current inter-satellite links. For intra-cluster coordination, T3L-DS introduces onboard dual-plan bidding and joint marginal evaluation. It also designs an inter-cluster coordination mechanism for unresolved demand. Extensive computational experiments compare T3L-DS with centralised simulated annealing (SA), an adapted selective time-variant better reply process (A-SeTVBRP), and a conventional contract-net protocol (CNP). T3L-DS achieves the highest emergency coverage among the distributed methods, with average relative improvements of approximately 2.8% and 17.1% over A-SeTVBRP and CNP, respectively. Its average relative gap from SA is approximately 7.1%. Under conflict-enhanced loads, it reduces routine-coverage loss by approximately 57.9% and 87.7% relative to A-SeTVBRP and CNP, respectively. The ablation study confirms the contribution of the proposed coordination enhancements. Overall, the results show that T3L-DS provides an effective distributed approach to DEOSP.
1 Introduction
Large LEO EO constellations provide frequent, wide-area access for time-critical applications, but emergency requests arriving during routine-plan execution create a dynamic scheduling problem that is difficult to centralise under intermittent ground contact. The paper proposes T3L-DS, a task-driven distributed framework using temporary task-specific clusters and onboard coordination to improve emergency coverage while limiting routine-plan disturbance.
- Motivation: Large LEO EO constellations provide frequent access and wide spatial coverage for disaster assessment, maritime rescue, and rapid environmental monitoring.These applications require information to be collected within a valid observation window.
- Problem formulation: DEOSP arises when emergency EO requests arrive during execution of a committed routine observation plan, requiring assignments within its adjustable future portion.Completed, ongoing, and protected activities remain fixed.
- Distributed scheduling need: Centralised rescheduling is difficult because intermittent ground contacts delay global execution-state collection, leaving information outdated when revised plans are ready.The paper therefore argues that detailed rescheduling is better performed onboard by satellites able to serve emergency requests and access current local states.
- Proposed framework: T3L-DS rebuilds an event-specific coordination scope from emergency requests, observable satellites, and current ISL topology, then forms temporary task-specific clusters on a common geographic grid.Its satellite layer performs local dual-plan bidding from the current onboard plan state.
- Contributions: T3L-DS combines geographic-grid representation, onboard dual-plan bidding, cluster-level marginal evaluation, and inter-cluster reallocation of unscheduled demand.Comparative and ablation experiments use mixed point and area requests under nominal and conflict-enhanced conditions, with T3L-DS achieving the strongest emergency coverage among distributed methods while limiting routine-plan disturbance.
2 Related Work
Related work covers spatial representations, centralized constellation scheduling, and distributed task allocation for Earth-observation systems. However, existing studies do not establish a distributed DEOSP formulation that updates locally held routine plans under varying inter-satellite links, which T3L-DS addresses through onboard scheduling and temporary-cluster coordination.
- Spatial representation: Spatial representations model point targets as discrete opportunities and wide or irregular regions as subregions, grids, candidate observations, or attitude-dependent footprints.These representations support joint allocation of coverage and observation time across multiple satellites.
- Centralized scheduling: Centralized methods remain valuable benchmarks because they model constellation-wide interactions, using branch-and-bound, maximum-independent-set, divide-and-conquer, and global planning approaches.Other centralized studies incorporate time-dependent value, repeated observations, decomposition, learning, or clustering.
- Distributed scheduling: Distributed formulations vary in decision variables and coordination objectives, including request-owning agents that exchange messages and satellite agents that construct local schedules.Onboard planning has also been studied under limited ground contact, but mainly for creating task allocations or new schedules rather than updating partly executed routine plans.
- Distributed task allocation: Standard CNP treats tasks or bids as indivisible, so whole-bid acceptance can duplicate credit while whole-bid rejection can discard useful coverage when area bids partially overlap.CNP variants nevertheless provide a natural manager-contractor structure and allow heterogeneous resources to evaluate opportunities under local constraints.
- Research gap and positioning: Existing studies do not establish distributed DEOSP for constellations with locally held current plans and varying ISLs, whereas T3L-DS coordinates onboard scheduling within and between temporary clusters.Emergency insertion changes both one satellite’s adjustable routine plan and the demand remaining for other satellites.
3 Problem Description and Modelling
The section formulates emergency observation scheduling during execution of a committed routine plan, using a common geographic grid to represent demand and satellite footprints. It defines feasibility, schedule disturbance, and a centralized reference objective for distributed coordination.
- Operational setting: Emergency requests arrive during routine-plan execution and specify target geometry, release time, priority, and an observation window.Requests may be triggered by disasters, cloud cover, or resource failures.
- Operational setting: T3L-DS treats the committed constellation schedule as an external input and changes only future activities designated as adjustable.Finished, executing, and protected future activities remain fixed after an emergency wave arrives.
- Spatial representation: A common geographic grid maps both emergency demand and satellite footprints to shared cells for coverage, duplicate removal, residual-demand tracking, and disturbance measurement.Point requests map to containing cells, while area requests map to cells intersecting their polygons.
- Feasibility model: A candidate observation is feasible only when its footprint covers the demand cell, timing fits the request window, and the sensor mode matches.Feasible service pairs form the set Ωe, with service value represented by the original request priority.
- Reference model: The centralized reference model establishes a common objective and feasibility boundary combining emergency service with routine-plan disturbance and schedule-change penalties.T3L-DS uses this formulation while operating on the constellation state available when each emergency wave arrives.
4 T3L-DS Method
T3L-DS organizes emergency rescheduling across ground, temporary-cluster, and satellite layers, rebuilding event-specific clusters from current visibility and inter-satellite connectivity. Satellites generate deterministic dual local plans, while cluster heads perform cell-aware marginal allocation, atomic commitment, and staged redistribution of unresolved demand.
- Three-layer organization: The three-layer design assigns event organization to the ground segment, overlapping allocation to temporary clusters, and detailed schedule changes to individual satellites.Ground supplies request, visibility, and topology information; cluster heads issue CFPs and resolve overlapping bids, while satellites return compact local plans.
- Event-specific clustering: Temporary clusters use head-centred star topologies, retain at most Kmax satellites, assign demands by cluster visibility, and rebuild at every wave.Candidate heads rank directly linked unassigned neighbours by the number of current demands they can observe, with current cluster load breaking assignment ties.
- Dual-plan bidding: Each satellite constructs two deterministic local plans from feasible candidates, preserving execution, attitude, cell-target, and approved pre-emption information.Emergency candidates may pre-empt lower-priority routine activities but not committed emergency observations; an offline-trained policy orders only candidates passing deterministic feasibility checks.
- Joint marginal evaluation: Cluster heads repeatedly award feasible candidates with the largest positive marginal gain, crediting only new cell-target pairs and recomputing gains after each award.Earlier awards constrain later time-attitude compatibility, so partially overlapping bids can retain useful cells while duplicate credited pairs receive no additional credit.
- Inter-cluster coordination: Accepted candidates and approved pre-emptions commit atomically; conflicts return affected demand to the residual set for further intra-cluster, neighbouring-cluster, or ground-level redistribution.Inter-cluster forwarding requires a direct current ISL, while unresolved emergency demand remains deferred when a feasible future opportunity exists and becomes infeasible only when none remains.
13 end · 20 end
The scheduling process terminates after each demand unit is served, classified as infeasible, deferred, or removed following its permitted one-pass rescheduling path. The resulting cluster configuration is not retained for later emergency waves.
- 20 end: The process terminates only when every demand unit reaches a final status.Each unit must be served, classified as infeasible, deferred, or removed.
- 20 end: Demand units may be served, classified as infeasible, deferred, or removed at termination.These are the four stated terminal outcomes.
- 20 end: A demand unit can be removed only after exhausting its permitted one-pass rescheduling path.Removal is explicitly tied to exhaustion of that rescheduling path.
- 20 end: The permitted rescheduling path is one-pass rather than repeatedly retained for further processing.The passage specifies exhaustion of a permitted one-pass path.
- 20 end: The associated cluster configuration is not retained after the process terminates.The passage states that this configuration is not kept for subsequent emergency waves.
- 20 end: Subsequent emergency waves do not reuse the terminated process’s cluster configuration.The configuration is explicitly excluded from retention for later waves.
5 Computational Experiments · 5.1 Experimental protocol and scenario design
The experiments evaluate emergency-scheduling methods in an event-driven setting with identical initial conditions, while varying demand, workload, constellation, arrival concentration, and conflict conditions. Scenarios use EOS-Bench constellation data, H3 resolution 6, and ten independent random seeds per configuration.
- 5.1 Experimental protocol and scenario design: All methods start from the same committed routine schedule and may modify only its adjustable future activities.The schedule is generated by a cost-effective lazy forward (CELF) greedy procedure.
- 5.1 Experimental protocol and scenario design: Emergency point and area requests are released in successive waves during plan execution by an event-driven simulator.Each method receives identical emergency requests, observation opportunities, and satellite states within an instance.
- 5.1 Experimental protocol and scenario design: H3 resolution 6 is used for all experiments, and every reported grid-cell count refers to this resolution.The orbital data come from the EOS-Bench Earth-observation satellite-scheduling benchmark.
- 5.1 Experimental protocol and scenario design: The benchmark constellation contains 500 satellites arranged in 25 orbital planes with 20 satellites per plane.Smaller constellations are uniform subsets of this configuration.
- 5.1 Experimental protocol and scenario design: The orbital configuration is generated from a seed orbit with semi-major axis 7013.62362 km, eccentricity 0.000898, and inclination 98.04°.The passage also specifies the ascending node, argument of perigee, and true anomaly.
- 5.1 Experimental protocol and scenario design: The experiments were conducted in Python 3.10 on Windows 11 using an Intel Core i7-10700K CPU, 64 GB RAM, and an NVIDIA GeForce RTX 3090 GPU.The CPU operates at 3.80 GHz.
- 5 Computational Experiments: The computational experiments compare four algorithms across the configured scenarios.Table 3 is identified as a comparison of computational results for four algorithms.
- 5.1 Experimental protocol and scenario design: Twenty-two scenarios are organised into five groups covering emergency-demand scale, routine background load, constellation size, demand-arrival concentration, and conflict-enhanced balanced-load conditions.Every configuration is evaluated with ten independent random seeds.
5.2 Compared methods
Section 5.2 defines the three comparative methods evaluated under identical committed schedules, emergency waves, observation opportunities, and initial states. The baselines comprise centralized simulated annealing, an adapted asynchronous better-reply process, and a conventional contract-net protocol.
- Compared methods: All methods use the same committed schedule, emergency waves, observation opportunities, and initial states.
- Compared methods: SA is a centralized simulated-annealing reference that starts from a greedy solution and runs 1,000 iterations per emergency wave using the current global instance.
- Compared methods: A-SeTVBRP updates feasible local schedules through asynchronous better replies, while cluster heads exchange states through direct ISLs.
- Compared methods: CNP is a conventional contract-net baseline using the same event-specific head-centred clusters as T3L-DS.
5.3 Evaluation metrics
The evaluation uses four metrics to measure emergency service and preservation of the routine plan: emergency coverage, routine retention, routine pre-emption, and routine rescheduling. Emergency observations count only when made within the applicable request window.
- Emergency service: Emergency coverage counts unique emergency cells observed by method m within an applicable request window.A cell observed outside its emergency window receives no emergency credit.
- Routine-plan preservation: Routine retention compares routine cells in the common input schedule with those in the final schedule.The passages define routine cells for both the common input and final schedules.
- Routine-plan preservation: Routine pre-emption counts routine cells invalidated by emergency insertion.This metric captures routine-plan disruption caused by inserting emergency observations.
- Routine-plan preservation: Routine rescheduling counts pre-empted routine cells subsequently rescheduled.The rescheduled cells are defined as those contained in the routine-rescheduling set.
5.4 Experimental results and analysis
Across 22 configurations, T3L-DS provides slightly lower emergency coverage than centralised SA but greatly limits routine-plan pre-emption, while outperforming the distributed baselines. Controlled experiments show that its performance responds to demand scale, constellation size, arrival waves, and routine-background changes through candidate-level and inter-cluster coordination.
- Aggregate comparison: Across 22 configurations, SA provides 5.5% more emergency coverage than T3L-DS, but pre-empts 79.8% of committed routine cells versus 2.3% for T3L-DS.SA’s mean routine retention is only 0.13 percentage points higher because it subsequently reschedules most pre-empted cells.
- Aggregate comparison: T3L-DS exceeds A-SeTVBRP and CNP in mean emergency coverage by 2.1% and 11.1%, respectively, while rescheduling 10.7% more displaced routine cells than A-SeTVBRP.Candidate-level marginal awards retain feasible parts of overlapping bids, and inter-cluster coordination creates further opportunities for unresolved demand.
- Group A: emergency-demand scale: From A2 to A4, T3L-DS emergency coverage increases by 3.9%, compared with 3.4% for A-SeTVBRP and 1.3% for CNP, after initially falling at higher demand.Spatial overlap among denser demands allows one observation to satisfy several grid-cell demand units, offsetting capacity pressure.
- Group C: constellation size: From C1 to C4, T3L-DS emergency coverage increases by 40.7%, while routine pre-emption falls by 73.7% as constellation size grows from 100 to 400 satellites.More feasible local candidates, cross-cluster alternatives, and idle intervals reduce conflicts; T3L-DS remains slightly ahead of A-SeTVBRP.
- Group E: stronger conflicts: Under stronger conflicts, doubling the constellation improves T3L-DS emergency coverage by 7.7% relative to E3, while increasing routine background changes coverage by no more than 0.4%.Coverage declines as emergency demand rises, while added satellites provide alternative access intervals and routine-background increases mainly affect the routine plan.
5.5 Ablation study
The ablation study finds that inter-cluster coordination is the dominant contributor to emergency coverage, while dual-plan construction and candidate-level joint evaluation provide smaller local-choice refinements.
- Inter-cluster coordination: Inter-cluster coordination contributes most, with its removal reducing emergency coverage by 3.8%-11.6% across four selected cases.The largest loss occurs in D1, followed by B4 and A4.
- Inter-cluster coordination: Neighbouring clusters provide useful alternatives when local visibility and attitude margins are exhausted, whereas sparse C1 topology limits transferable demand.The smaller C1 loss reflects fewer neighbouring assets capable of accepting transferred demand.
- Dual-plan construction: Removing Plan B reduces emergency coverage by 0.26%-0.96%, with larger changes in B4 and D1.A second local plan can preserve an alternative under dense routine plans or concentrated arrivals.
- Candidate-level joint evaluation: Replacing candidate-level joint evaluation with whole-plan acceptance changes coverage by no more than 0.09% beyond the Plan-A-only setting.This mechanism has the smallest measured coverage effect among the evaluated components.
- Overall ablation findings: The contribution ordering remains inter-cluster coordination first, followed by dual-plan construction and candidate-level evaluation.Inter-cluster coordination provides the main gain under resource pressure, while the other mechanisms refine local choices.
6 Conclusions
The paper presents T3L-DS for emergency observation scheduling during routine-plan execution, using geographic-grid representation and distributed coordination while revising only adjustable future activities. Experiments show strong emergency service and routine-coverage preservation, while future work targets richer onboard models and uncertain ISL availability.
- Problem and formulation: T3L-DS addresses DEOSP by scheduling emergency point and area requests during execution of an existing routine observation plan.Its geographic-grid formulation represents emergency demand, satellite footprints, coverage credit, and routine-plan disturbance with common spatial units.
- Distributed coordination: T3L-DS coordinates scheduling through event-level ground organisation, onboard dual-plan bidding, and cluster-level allocation over available ISLs.Only adjustable future activities are modified; completed, executing, and protected routine activities remain outside the revision scope.
- Results and future work: T3L-DS provides the strongest emergency service among distributed methods while preserving most routine grid-cell coverage under tested conditions.Future work will incorporate more detailed onboard computation, energy, and communication models and evaluate uncertain ISL availability.