Paper deep dive
Task-Driven Three-Layer Distributed Scheduling for Emergency Earth Observation in Large Low-Earth-Orbit Constellations
Qian Yin, Xinwei Wang, Guohua Wu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/18/2026, 4:40:08 AM
Summary
The paper addresses the Dynamic Emergency Observation Scheduling Problem (DEOSP) in large Low-Earth-Orbit (LEO) constellations, where emergency requests arrive during routine plan execution. The authors propose a Task-Driven Three-Layer Distributed Scheduling (T3L-DS) method that uses a common geographic grid (H3) to represent tasks and sensor footprints. T3L-DS forms temporary clusters based on inter-satellite links and observation capabilities, employing onboard dual-plan bidding and joint marginal evaluation for intra-cluster coordination, and an inter-cluster mechanism for unresolved demand. Experiments show T3L-DS outperforms centralized Simulated Annealing (SA), Adapted Selective Time-variant Better Reply Process (A-SeTVBRP), and Contract-Net Protocol (CNP) in emergency coverage and routine-coverage preservation.
Entities (12)
Relation Signals (8)
T3L-DS → solves → DEOSP
confidence 98% · To address DEOSP, we propose a task-driven three-layer distributed scheduling (T3L-DS) method
Guohua Wu → affiliatedwith → Central South University
confidence 95% · Affiliation: Central South University, Changsha, China
Qian Yin → affiliatedwith → Central South University
confidence 95% · Affiliation: Central South University, Changsha, China
Qian Yin → affiliatedwith → Queen Mary University of London
confidence 95% · Affiliation: Queen Mary University of London, London, UK
Xinwei Wang → affiliatedwith → Queen Mary University of London
confidence 95% · Affiliation: Queen Mary University of London, London, UK
T3L-DS → uses → H3
confidence 93% · This study adopts a hierarchical hexagonal geospatial indexing system (H3) as its geographic grid system
T3L-DS → outperforms → A-SeTVBRP
confidence 90% · T3L-DS achieves the highest emergency coverage among the distributed methods, with average relative improvements of approximately 2.8% ... over A-SeTVBRP
T3L-DS → outperforms → CNP
confidence 90% · T3L-DS achieves the highest emergency coverage among the distributed methods, with average relative improvements of approximately ... 17.1% over ... CNP
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2608.14789v1
- Canonical: https://arxiv.org/abs/2608.14789v1
Trouble viewing inline? Open PDF directly →
Full Text
77,499 characters extracted from source content.
Expand or collapse full text
Task-Driven Three-Layer Distributed Scheduling for Emergency Earth Observation in Large Low-Earth-Orbit Constellations Qian Yin Thanks: 224201024@csu.edu.cn Affiliation: Central South University, Changsha, China Affiliation: Queen Mary University of London, London, UK Xinwei Wang Thanks: Corresponding author: xinwei.wang@qmul.ac.uk Affiliation: Queen Mary University of London, London, UK Guohua Wu Thanks: Corresponding author: guohuawu@csu.edu.cn Affiliation: Central South University, Changsha, China Abstract 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. Keywords: Earth observation, low-Earth-orbit constellation, emergency task scheduling, geographic grid, distributed coordination 1 Introduction Advances in spacecraft manufacturing and reusable launch services have accelerated the deployment of large low-Earth-orbit (LEO) constellations. By 2026, public satellite population statistics listed more than 16,000 active satellites in Earth orbit. More than 15,000 were in LEO, including about 1,400 payloads classified under imaging, radar imaging, Earth-observation (EO) science, or meteorological missions.11 1 Satellite population and mission-category data are from Jonathan McDowell’s public statistics: https://planet4589.org/space/stats/active.html and https://planet4589.org/space/stats/omission.html. For EO missions, large LEO constellations can provide frequent access and wide spatial coverage [32, 8]. These features are important for time-critical applications such as disaster assessment, maritime rescue, and rapid environmental monitoring. In these applications, useful information must be collected within the valid observation window. This motivates the dynamic emergency observation scheduling problem (DEOSP), in which emergency EO requests arrive during the execution of a committed routine observation plan [36, 20]. At each arrival, every satellite has a current attitude and a sequence of completed or ongoing activities, protected future activities, and adjustable future activities. Completed, ongoing, and protected activities remain fixed. The scheduler then assigns emergency tasks within the adjustable future portion of the plan while limiting the loss of routine observations. These scheduling decisions are difficult to centralise because constellation-wide coordination requires a current global execution state [34, 44]. Intermittent ground contacts delay the collection of satellite activity sequences and attitude states, and some information may already be outdated when a revised plan is ready [5]. Detailed rescheduling is therefore better performed onboard by the satellites that can serve the emergency requests and have direct access to their current local states. The ground centre retains event-level coordination by providing request data, predicted visibility, and topology information, while the relevant satellites construct and coordinate detailed schedule changes onboard. Existing studies provide useful foundations, but they do not fully address the information and plan-modification requirements of DEOSP. Centralised exact, heuristic, and metaheuristic methods provide strong schedules for planning-horizon problems [22, 33, 43], but their execution-time use depends on timely global information and becomes costly as the candidate set grows. The term distributed covers different decision settings in the current literature. Krigman et al. [18] distribute scheduling decisions among request-owning users rather than spacecraft, so their formulation does not define onboard plan modification from current satellite states. Feng et al. [7] and Zilberstein et al. [44] develop distributed scheduling methods, but their planning still runs at a ground centre with access to constellation-wide information. Yang et al. [40] propose a distributed potential-game method for allocating time-windowed observation grids, but assume real-time communication among satellites, which cannot be guaranteed in practice. In practice, DEOSP requires relevant satellites to modify their current onboard plans without a synchronised constellation-wide execution state and to coordinate through the links available at the time of each event. To meet these requirements, this paper proposes a task-driven three-layer distributed scheduling (T3L-DS) framework. Task-driven coordination rebuilds its scope for each emergency wave from the received requests, observable satellites, and current inter-satellite-link (ISL) topology. It differs from constellation-wide schedule reconstruction [33, 43] and from resource-driven partitioning based on fixed groups or static ownership [7]. In the T3L-DS, the ground layer maps requests and sensor footprints to a common geographic grid and forms temporary task-specific clusters. The satellite layer performs local dual-plan bidding from its current onboard plan state after deterministic feasibility checks. The cluster layer evaluates overlapping bids and reallocates tasks that remain unscheduled, without requiring a constellation-wide execution state. This study adopts a hierarchical hexagonal geospatial indexing system (H3) as its geographic grid system [11], while T3L-DS can also operate on conventional targets or predefined regional subtasks instead of grid cells. In summary, this work makes three contributions: • For the first time, we present a distributed formulation of DEOSP, using a common geographic-grid representation for point and area requests and satellite footprints while separating protected activities from adjustable future activities in the committed plan. • We develop T3L-DS to form an event-specific coordination scope and combine onboard dual-plan bidding, cluster-level marginal evaluation, and inter-cluster reallocation of unscheduled demand. • We conduct comparative and ablation experiments with mixed point and area requests under nominal and conflict-enhanced conditions. The results show that T3L-DS provides the strongest emergency coverage among the distributed methods while limiting disturbance to the routine plan. The rest of the paper is organised as follows. Section 2 reviews related work. Section 3 describes DEOSP and presents its mathematical model. Section 4 describes the T3L-DS method. Section 5 presents the experimental design and analyses the results. Section 6 concludes the paper. 2 Related Work Research related to DEOSP spans spatial representation, constellation scheduling, and distributed task allocation. Point targets are commonly modelled as discrete observation opportunities, whereas wide or irregular regions are divided into subregions, grids, candidate observations, or attitude-dependent footprints. Such representations support the joint allocation of coverage and observation time across several satellites [16, 39], while multi-objective formulations also consider image quality, resource use, and response time [4, 3]. For agile and super-agile satellites, the manoeuvre path couples the spatial representation directly to observation time and coverage [21, 1, 27]. Adaptive subdivision and nested grids improve geometric fidelity [37, 13], and resampling, multi-stage optimisation, and specialised heuristics limit the resulting search cost [10, 2, 17]. Grid-based formulations have also generated observation tasks or represented attitude-dependent coverage [38, 27]. In most of these studies, the grid primarily supports spatial discretisation or geometric search. DEOSP requires one spatial identity to support demand decomposition, bidding, service credit, schedule-disturbance accounting, and residual-demand processing. The identity must remain consistent across satellites and scheduling stages to control duplicate credit and record partial completion [32, 8]. Centralised methods remain valuable benchmarks because they model constellation-wide interactions [28]. Branch-and-bound, maximum-independent-set, and divide-and-conquer algorithms have addressed larger EO scheduling instances [22, 6, 33]. Other studies incorporate time-dependent value, repeated observations, decomposition, learning, or clustering while retaining a global planning model [19, 29, 23, 9]. A recent two-stage method also uses heuristic initialisation and global optimisation for long-term multi-region scheduling [43]. Such methods provide useful quality references, but execution-time use requires the ground centre to collect a changing constellation state before it rebuilds the schedule. Distributed formulations differ in both their decision variables and their coordination objectives. Krigman et al. [18] formulate a distributed constraint optimisation problem in which request-owning users act as agents and exchange messages without first disclosing all requests to a central authority. The distributed search protects request ownership, but it does not place schedule construction onboard the satellites. Feng et al. [7] assign local schedule construction to satellite agents and resolve conflicts through iterative exchanges. Zilberstein et al. [44] decompose the global scheduling problem into geometric neighbourhoods and apply decentralised stochastic search within those subproblems. Both approaches begin from a defined request set and its observation opportunities, and their reported implementations retain constellation-level problem information. Yang et al. [40] take a different route by deriving satellite utilities from a global grid-allocation objective. Their method passes a shared allocation file through sequential better replies and broadcasts the converged allocation under an assumption of real-time inter-satellite communication. Research on autonomous EO systems has further established the value of onboard planning under limited ground contact [34, 5]. These studies focus mainly on creating a task allocation or a new schedule, rather than updating a partly executed routine plan after emergency requests arrive. The contract-net protocol (CNP) offers a natural manager-contractor structure for such local decisions [25], and its variants allow heterogeneous EO resources to evaluate opportunities under local constraints [20]. A standard contract nevertheless treats a task or bid as an indivisible unit. Area-target bids may overlap on only some cells, so whole-bid acceptance can duplicate credit and whole-bid rejection can discard useful coverage. Learning-based schedulers can supply local preferences quickly after training [14, 15, 26], but feasibility and cross-satellite consistency still require explicit coordination rules. Robust EO scheduling protects plans against uncertainty before execution [31]. DEOSP instead concerns schedule modification after emergency demand becomes known during routine-plan execution. For the distributed solution developed in this study, satellites that can observe the current emergency demand are organised into temporary clusters using task visibility and available ISLs. Each cluster provides a local coordination scope, while unresolved demand can be transferred to a neighbouring cluster. Figure 1: Research setting of DEOSP. The figure shows geographic-grid conversion, intra-cluster coupling, and inter-cluster coupling. In a nutshell, existing studies have not established a distributed formulation of DEOSP for constellations whose current plans are held locally and whose ISLs vary during execution. In this setting, an emergency insertion changes both the adjustable routine plan of one satellite and the demand still available to the others. T3L-DS addresses this problem through distributed onboard scheduling and coordination within and between temporary clusters over the available ISLs. 3 Problem Description and Modelling In this section, we first describe the problem operational setting and the distributed information boundary, and then introduce a common geographic-grid representation for emergency demand and satellite observation footprints. In the end, we introduce a centralised reference model that clarifies the objective, constraints, and schedule-disturbance terms used by the distributed method. 3.1 Problem Description of DEOSP During routine operation, a large LEO EO constellation follows a committed plan with prescribed execution times and attitudes. Emergency requests caused by disasters, cloud cover, or resource failures may arrive while this plan is being executed [36, 20]. Each request specifies a point or area target, a release time, a priority, and an observation window within which the target must be observed. Following the unified grid characterisation in [41], a common geographic grid converts both request types and satellite footprints to the same cell representation, and each grid-cell-target pair forms an atomic demand unit. At each arrival, DEOSP assigns these units using predicted observation opportunities and the current local plans and attitudes of the satellites, which the ground planning centre may not hold in a fully synchronised form because contacts are intermittent. The resulting schedule changes must satisfy request windows, visibility intervals, and attitude-transition requirements. They may affect only adjustable future activities; completed, ongoing, and protected activities remain fixed. DEOSP seeks to maximise emergency coverage within the request windows while limiting the loss of valid routine coverage, without reconstructing the full mission plan. To support distributed decisions under this information boundary, T3L-DS forms temporary clusters according to the current demand-satellite visibility relation and available ISLs. Each cluster coordinates its assigned demand locally, and unresolved demand may be transferred to a neighbouring cluster. The example in Figure 1 considers an emergency wave arriving at time tet_e with point and area requests while cloud cover has made part of the routine plan ineffective. Grid conversion gives the requests and satellite footprints a common cell identity. In one region, several satellites can observe overlapping cells, but their committed activities, attitudes, and adjustable time intervals differ. Their local decisions are coupled through competition for cell credit and through the different routine activities disturbed by an insertion. Some boundary cells may remain unresolved after this intra-cluster coordination, even though a neighbouring cluster still has suitable visibility and communication access. Inter-cluster coordination must transfer these cells without losing their identity or creating duplicate credit. 3.2 Notation and assumptions Table 1 links the symbols used in the centralised reference model to those used later for distributed coordination. The request and execution-state notation is introduced below, while the cluster and candidate symbols are used in Section 4. Table 1: Main symbols and notation Symbol Definition ,NS,N Satellite set and number of satellites. ,e,teW,e,t_e Emergency waves set, wave index, and arrival time. ℛeER^E_e Requests released in wave e. Pr,trrel,trddl,ωrP_r,t_r^rel,t_r^ddl, _r Region, time window, and priority of request r. ℓ,CgG_ ,C_g Grid cells at resolution ℓ and polygon of cell g. r,eEG_r,D^E_e Grid representation and atomic emergency demands. σse,Π¯se _s^e, _s^e Execution state and committed sequence of satellite s. Π¯exee,Π¯fixe, _exe^e, _fix^e, Π¯adje _adj^e Executed, protected, and adjustable activities. se,pP_s^e,p Candidate observation of satellite s and one candidate. Fp,Γp,ΩeF_p, _p, _e Candidate footprint, covered cells, and feasible service pairs. ℰseE_s^e Pairwise candidate incompatibilities. xpe,zp,qe,vgex_p^e,z_p,q^e,v_g^e candidate selection, demand service, and routine-cell invalidation variables. se,Γo,qvisO_s^e, _o,S^vis_q Future opportunities, opportunity footprints, and visible satellites. ISLe,ℬe,KmaxG_ISL^e,B^e,K_ ISL graph, temporary clusters, and size limit. χ,se,(χ)χ,X_s^e,Y(χ) Local candidate, candidate set, and covered cell-target pairs. ΠsA,ΠsB _s^A, _s^B Primary and diverse local plans. ℒb,ΔJ(χ∣ℒb)L_b, J(χ _b) Credited pairs and marginal gain in cluster b. resD_res Residual-demand set. Let =s1,…,sNS=\s_1,…,s_N\ denote the satellite set, and let =[0,T]T=[0,T] denote the mission horizon. Emergency requests arrive in waves indexed by e∈e . Wave e arrives at time tet_e and contains the request set ℛeER^E_e. Each request r has a geographic region PrP_r, a release time trrelt_r^rel, a deadline trddlt_r^ddl, and a priority ωr _r. The interval [trrel,trddl][t_r^rel,t_r^ddl] defines the observation window of request r. At the arrival time tet_e, each satellite s is characterised by an execution state σse=(Π¯se,se,tsava). _s^e=( _s^e, θ_s^e,t_s^ava). (1) Here, Π¯se _s^e is the committed activity sequence stored onboard satellite s, and se θ_s^e is its current attitude. The term tsavat_s^ava denotes the earliest time at which the schedule can be changed. The committed constellation schedule Π¯e=⋃s∈Π¯se ^e= _s _s^e is an external input to DEOSP. T3L-DS does not create or independently optimise that schedule. For modelling purposes, the committed schedule is partitioned as Π¯e=Π¯exee∪˙Π¯fixe∪˙Π¯adje. ^e= _exe^e ∪ _fix^e ∪ _adj^e. (2) The set Π¯exee _exe^e contains activities that have finished or are already being executed. The set Π¯fixe _fix^e contains future activities protected by mission priority, operational commitment, or an uploaded execution segment. Neither set can be changed after wave e arrives. Only the future activities in Π¯adje _adj^e are available for insertion, pre-emption, or rescheduling. The formulation is based on four operational assumptions. First, each satellite has the onboard computing, inter-satellite communication, and target-recognition capability required to process an emergency request. Second, emergency requests arrive as event-triggered batches. Requests in the same batch share a release event, but they may have different observation windows and priorities [36, 20]. Third, the ground segment cannot communicate with every satellite in real time. It sends compact requests and coordination information to relevant satellites, rather than collecting every detailed onboard schedule [34, 5]. Fourth, each grid-cell-target pair receives at most one credited service in one allocation attempt [18, 40]. 3.3 Geographic Grid-Based Demand and Resource Representation Geographic gridding converts the continuous Earth surface into discrete cells with unique spatial indices. When the grid is hierarchical, it also provides parent-child relations between resolutions. These properties allow the scheduler to use the same spatial unit for demand decomposition, footprint coverage, duplicate removal, and residual-demand tracking. Hexagonal cells have six adjacent directions over most of the grid, which is useful for compact regional representation and local spatial search [41, 24]. Let ℓG_ denote the cells of a geographic grid at resolution ℓ , and let CgC_g be the geographic polygon of cell g∈ℓg _ . Note that the three-layer architecture can use other atomic spatial units, such as conventional targets or predefined regional subtasks, without changing the division of coordination responsibilities. In this study, H3 is used to instantiate the geographic-grid representation because it provides hierarchical global indexing and direct cell-neighbour operations [11]. The scheduling mechanisms require only an identifiable spatial unit, its coverage membership, and, where candidate grouping is used, its neighbourhood relation. The cell representation of emergency request r is r=g∈ℓ:Cg∩Pr≠∅.G_r= \g _ :C_g∩ P_r≠ \. (3) A point request is mapped to the cell that contains its coordinate. An area request is represented by the cells that intersect its polygon. The atomic emergency-demand set is rE=q=(r,g):g∈r,eE=⋃r∈ℛeErE.D^E_r=\q=(r,g):g _r\, ^E_e= _r ^E_eD^E_r. (4) For q=(r,g)q=(r,g), let r(q)=r(q)=r and g(q)=g(q)=g denote its request and grid-cell components. A candidate observation p belongs to satellite s(p)s(p). It is described by an inserted observation interval (tpst,tpend)(t_p^st,t_p^end), an attitude state p θ_p, and a ground footprint FpF_p. It also has a manoeuvre or change cost cpchgc_p^chg. Its grid footprint is Γp=g∈ℓ:Cg∩Fp≠∅. _p= \g _ :C_g∩ F_p≠ \. (5) Candidate p can serve demand q=(r,g)q=(r,g) only when g belongs to Γp _p, the inserted observation starts no earlier than tr(q)relt_r(q)^rel and ends no later than tr(q)ddlt_r(q)^ddl, and the sensor mode matches the request. The set Ωe _e contains all service pairs that satisfy these conditions. The service value of a feasible pair is represented by the priority of its original request. This gives the model a simple emergency-service term while keeping response-time feasibility inside the definition of Ωe _e. Figure 2: Geographic-grid representation for emergency demand and observation footprints. The figure shows how point requests, area requests, and satellite footprints are mapped to the same cell set. Figure 2 illustrates the common spatial representation used by the model. After the conversion, both request geometry and satellite-footprint geometry are represented by cell sets. The model compares rG_r and Γp _p through set operations. The intersection r∩ΓpG_r∩ _p gives the cells that candidate p can add to request r. The same cell identity is later used for service credit, duplicate removal, residual demand, and disturbance measurement. 3.4 Dynamic Emergency Observation Scheduling Model For satellite s, two candidate observations p,p′∈sep,p _s^e can conflict either because their observation intervals overlap or because the available transition time is shorter than the required manoeuvre time Δs(p,p′) _s( θ_p, θ_p ). For notation, let p precede p′p when tpst≤tp′stt_p^st≤ t_p ^st. The conflict set is ℰse=(p,p′): _s^e=\(p,p ): p≠p′,s(p)=s(p′)=s, p≠ p ,\;s(p)=s(p )=s, (6) tpst≤tp′st, t_p^st≤ t_p ^st, [tpst,tpend]∩[tp′st,tp′end]≠∅ [t_p^st,t_p^end]∩[t_p ^st,t_p ^end]≠ or tp′st−tpend<Δs(p,p′). t_p ^st-t_p^end< _s( θ_p, θ_p )\. The set Π¯e ^e is divided into executed activities Π¯exee _exe^e, protected activities Π¯fixe _fix^e, and adjustable future activities Π¯adje _adj^e. The first two subsets cannot be changed by the rescheduling process. The set Π¯fixe _fix^e contains routine activities that are still in the future but are protected by priority, operational commitment, or the start of an already uploaded execution segment. Only activities in Π¯adje _adj^e may be displaced by emergency insertions. When a selected emergency candidate p conflicts with an adjustable routine activity, the time-local cell-level update uses tpstt_p^st as its boundary. Routine cell records that start before this boundary remain valid, whereas records that start at or after it become invalid. Let xpe∈0,1x_p^e∈\0,1\ indicate whether the model selects candidate p∈ep ^e. Let zp,qe∈0,1z_p,q^e∈\0,1\ indicate whether candidate p serves emergency demand q. Let vge∈0,1v_g^e∈\0,1\ indicate whether a selected candidate invalidates future routine cell g. Here, e=⋃s∈seP^e= _s P_s^e. For each candidate p, the set (p)Q(p) contains only the adjustable future routine cells at or after the start time of p that it can invalidate. The centralised formulation is maxxe,ze,ve _x^e,z^e,v^e ∑q∈eE∑p:(p,q)∈Ωeωr(q)zp,qe _q ^E_e _p:(p,q)∈ _e _r(q)z_p,q^e (7) −λdis∑gcgdisvge−λchg∑pcpchgxpe, - _dis _gc_g^disv_g^e- _chg _pc_p^chgx_p^e, where cgdisc_g^dis is the disturbance cost of routine cell g, while λdis _dis and λchg _chg control the penalties for routine-plan disturbance and schedule change. The objective is subject to zp,qe≤xpe, z_p,q^e≤ x_p^e, ∀(p,q)∈Ωe, ∀(p,q)∈ _e, (8) ∑p:(p,q)∈Ωezp,qe≤1, _p:(p,q)∈ _ez_p,q^e≤ 1, ∀q∈eE, ∀ q ^E_e, (9) xpe+xp′e≤1, x_p^e+x_p ^e≤ 1, ∀(p,p′)∈ℰse,s∈, ∀(p,p ) _s^e,\;s , (10) vge≥xpe, v_g^e≥ x_p^e, ∀p∈e,g∈(p). ∀ p ^e,\;g (p). (11) Figure 3: Overall information flow of T3L-DS. The ground segment uses request data, future visibility, and the ISL snapshot to define event-related coordination scopes. The cluster layer sends calls for proposals (CFPs), and the satellites return local plans for cluster-level coordination. Here, shs_h denotes the cluster head, and sis_i denotes a member satellite. The model removes candidates that conflict with protected activities before optimisation. Constraint (8) links demand service to candidate selection. Constraint (9) gives each emergency demand unit at most one credited service. Constraint (10) prevents overlapping or attitude-infeasible candidates on the same satellite. Constraint (11) records which adjustable routine cells are invalidated by selected emergency insertions. Deadline feasibility is handled before optimisation by constructing Ωe _e only from candidate-demand pairs that finish within the request window. Pairwise candidate incompatibilities define an incompatibility graph, in which maximum-value observation selection can be formulated as a maximum-weight independent-set problem [6]. This class of EO satellite scheduling problems is NP-hard [35]. Pre-emption rules and schedule-change costs extend this structure to the execution-time setting. T3L-DS uses the formulation to define a common objective and feasibility boundary, while operating on the constellation state available when each emergency wave arrives. 4 T3L-DS Method 4.1 Overall framework T3L-DS takes the committed schedule, current onboard states, future observation opportunities, and the current ISL graph as its event input. For emergency wave e, ISLe=(,e)G_ISL^e=(S,Z^e) is a link-availability snapshot generated from the predicted satellite positions and the adopted line-of-sight condition at the wave-arrival epoch, where (si,sj)∈e(s_i,s_j) ^e denotes an available direct ISL between satellites sis_i and sjs_j [30] It assigns event-level organisation to the ground layer, overlapping allocation to temporary clusters, and detailed schedule changes to individual satellites. Figure 3 shows the information exchanged across the three layers. The ground segment supplies request, visibility, and topology information; cluster heads issue CFPs and resolve overlapping bids; satellites retain their committed sequences and return compact local plans. The head shown in Figure 3 is selected during the event-specific cluster construction and is not a permanent role assigned in advance. Only the cluster layer assigns final cell ownership, so each satellite can generate its local plan without access to a fully synchronised constellation-wide schedule. 4.2 Task-driven temporary clustering The ground segment identifies satellites with an opportunity that intersects both the cell and the request window: visq=s∈:∃o∈se, ^vis_q=\s :∃ o _s^e, g(q)∈Γo, g(q)∈ _o, (12) toend>tr(q)rel,tost<tr(q)ddl. t_o^end>t_r(q)^rel,\ t_o^st<t_r(q)^ddl\. Here, Γo _o denotes the grid-cell footprint of opportunity o. Satellites recorded as having tried q are excluded during redispatch. A demand is declared infeasible only when no future opportunity remains; otherwise it stays pending if the current organisation cannot accept it. Let ℬeB^e denote the temporary-cluster set for wave e, and let b∈ℬeb ^e index one cluster. Each currently unassigned satellite is first treated as a candidate cluster head. Its directly linked unassigned neighbours are ranked by the number of current demands that they can observe, and at most KmaxK_ satellites are retained. The candidate head and its retained neighbours form a head-centred cluster with a star topology, because every member has a direct ISL to the head, whereas links between members are not required. The candidate cluster covering the largest number of distinct current demands is accepted, and its central satellite becomes the cluster head. The satellites in the accepted cluster are then removed from the unassigned set, and the procedure continues until no further cluster can be formed. Each demand is then assigned to the cluster containing the most satellites in qvisS^vis_q, with current cluster load used to break ties. Clusters are rebuilt at every wave, so this organisation follows the event rather than a fixed constellation partition. 4.3 Satellite-local candidate generation and dual-plan construction After receiving a CFP, satellite s first merges demand already served by a same-cell observation inside the emergency window. It builds seX_s^e for the remaining demand from future local opportunities. A local candidate χ is the distributed representation of a candidate modification p in the reference model. Each candidate χ records one execution interval, one attitude, the cell-target set (χ)Y(χ), and any lower-priority activities approved for pre-emption. Completed cell-target records remove already served residual or routine demand before ranking; emergency demand may still require a new observation of the same cell outside the relevant emergency window. Let s,wineX_s,win^e, s,sepeX_s,sep^e, and s,prioeX_s,prio^e denote the candidates that satisfy task windows, time-attitude separation, and pre-emption priority, respectively. The local feasibility rule is sfeas(χ)=[χ∈s,wine∩s,sepe∩s,prioe].I^feas_s(χ)=I\! [χ _s,win^e _s,sep^e _s,prio^e ]. (13) The separation test uses Δs(,′) _s( θ, θ ) from Eq. (6). Emergency candidates may pre-empt lower-priority routine activities but not committed emergency observations. The implementation ranks only candidates that satisfy Eq. (13); an offline-trained local policy supplies this ordering, while all feasibility decisions remain deterministic. Figure 4: Dual-plan construction from a deterministically filtered local candidate set. As shown in Figure 4, sequential selection with a local state update produces Plan A. The exact cell-attitude candidates used by Plan A are then removed, and the same construction on the reduced set produces Plan B. Both plans carry their cell-target pairs, execution data, and approved pre-emption records to the cluster head. 4.4 Intra-cluster contract-net coordination The cluster head expands the submitted plans into a candidate set bX_b and evaluates candidates separately. Let ℒbL_b contain the cell-target pairs already credited in cluster b. The marginal gain of candidate χ is ΔJ(χ∣ℒb)=|(χ)∖ℒb|. J(χ _b)= |Y(χ) _b |. (14) A candidate must also remain time-attitude compatible with earlier awards on the same satellite. The head repeatedly selects the feasible candidate with the largest positive gain, adds only its new pairs to ℒbL_b, and recomputes the remaining gains. Hence, a partially overlapping bid can retain useful cells, while an already credited pair cannot receive duplicate credit. Figure 5 traces this update within one cluster. Each award extends the locked cell-target set, changes the marginal gains of overlapping candidates, and removes attitude-infeasible alternatives before the next selection. Figure 5: Cell-aware marginal awards within one temporary cluster. The locked set ℒbL_b stores credited cell-target pairs, and ΔJ J is recomputed after each provisional award. Input: Cluster demand set bD_b, candidate set bX_b and current satellite schedules Output: Committed set bC_b and residual set resD_res ℒb,b,b,res←∅,∅,∅,∅L_b,A_b,C_b,D_res← , , , ; 1 while b≠∅X_b≠ do 2 ℱb←χ∈b:Compatible(χ,b)F_b←\χ _b:Compatible(χ,A_b)\; 3 if ℱb=∅F_b= then 4 break; 5 end if 6 χ∗←argmaxχ∈ℱbΔJ(χ∣ℒb)χ^*← _χ _b J(χ _b); 7 if ΔJ(χ∗∣ℒb)=0 J(χ^* _b)=0 then 8 break; 9 end if 10 b←b∪χ∗A_b _b∪\χ^*\, ℒb←ℒb∪(χ∗)L_b _b (χ^*); 11 b←b∖χ∗X_b _b \χ^*\; 12 end while 13 foreach χ∈bχ _b do 14 if CommitFeasible(χ)=1CommitFeasible(χ)=1 then 15 AtomicCommit(χ)AtomicCommit(χ); b←b∪χC_b _b∪\χ\; 16 else 17 res←res∪(χ)D_res _res (χ); 18 end if 19 end foreach 20 served←⋃χ∈b(χ)D_served← _χ _bY(χ); 21 res←res∪(b∖served)D_res _res∪(D_b _served); 22 Algorithm 1 Cell-aware marginal award and atomic commitment Algorithm 1 separates provisional allocation bA_b from committed observations bC_b. The final check uses the latest satellite schedule. An accepted candidate and its approved pre-emptions are committed atomically; a new conflict instead returns the affected demand to resD_res. 4.5 Inter-cluster coordination and event termination The residual set produced by Algorithm 1 contains uncredited emergency demand and demand returned by failed atomic commitments. The current managing cluster first conducts a further intra-cluster allocation attempt using the remaining feasible candidates. An unresolved demand unit may then be forwarded to a neighbouring cluster if the two cluster heads have a direct ISL in the current topology. If the inter-cluster attempt does not yield an assignment, the ground segment updates the demand-satellite visibility relation, rebuilds the event-specific clusters under the latest ISL topology, and redispatches the demand unit. At every stage, exactly one cluster retains allocation authority for each active demand unit, preventing concurrent or duplicate awards. Routine cell demands created by an approved pre-emption are subject to a more restrictive rescheduling rule. They may undergo one local rescheduling attempt followed, if necessary, by one neighbouring-cluster attempt, but they are not eligible for subsequent ground-level redispatch. An unresolved emergency demand unit is deferred while a feasible future opportunity remains and is classified as infeasible only when no such opportunity exists. The coordination process for wave e terminates when every demand unit has been served, classified as infeasible, deferred, or removed after exhausting its permitted one-pass rescheduling path. The associated cluster configuration is not retained for subsequent emergency waves. 5 Computational Experiments 5.1 Experimental protocol and scenario design Each experiment begins with a committed routine schedule generated by a cost-effective lazy forward (CELF) greedy procedure. All methods treat this schedule as an external input and may modify only its adjustable future activities. The event-driven simulator releases emergency point and area requests in successive waves during plan execution. Within each instance, all methods receive identical committed schedules, emergency requests, observation opportunities, and satellite states. Based on preliminary experiments, the penalty coefficients in the reference model were set to λdis=10 _dis=10 and λchg=1 _chg=1 for all computational experiments. The experiments use H3 resolution 6, to which all reported grid-cell counts refer. The orbital data used in this study are taken from EOS-Bench, a comprehensive benchmark for Earth observation satellite scheduling [42]. The benchmark’s 500-satellite constellation comprises 25 orbital planes with 20 satellites per plane and is generated from a seed orbit with semi-major axis 7013.62362 km, eccentricity 0.000898, inclination 98.04∘98.04 , right ascension of the ascending node 57.345∘57.345 , argument of perigee 101.516∘101.516 , and true anomaly 96.459∘96.459 . Smaller constellations are uniform subsets of this configuration. All experiments were conducted in Python 3.10 on Windows 11 using an Intel Core i7-10700K CPU at 3.80 GHz, 64 GB RAM, and an NVIDIA GeForce RTX 3090 GPU. Table 2: Experimental scenario configurations Case Satellites Routine targets Emergency targets Waves Emergency window (min) Mean emergency H3 cells Point Region Point Region A1 500 8000 3000 50 25 5 60-120 550 A2 500 8000 3000 100 50 10 60-120 1100 A3 500 8000 3000 300 150 15 60-120 3300 A4 500 8000 3000 400 200 20 60-120 4400 B1 500 4000 1500 200 100 15 60-120 2200 B2 500 8000 3000 200 100 15 60-120 2200 B3 500 10000 4000 200 100 15 60-120 2200 B4 500 12000 5000 200 100 15 60-120 2200 C1 100 8000 3000 200 100 15 60-120 2200 C2 200 8000 3000 200 100 15 60-120 2200 C3 300 8000 3000 200 100 15 60-120 2200 C4 400 8000 3000 200 100 15 60-120 2200 D1 500 8000 3000 200 100 5 60-120 2200 D2 500 8000 3000 200 100 10 60-120 2200 D3 500 8000 3000 200 100 20 60-120 2200 D4 500 8000 3000 200 100 30 60-120 2200 E1 100 500 300 200 100 5 60-120 2200 E2 100 500 300 300 150 5 60-120 3300 E3 100 500 300 400 200 5 60-120 4400 E4 200 500 300 400 200 5 60-120 4400 E5 200 750 400 400 200 5 60-120 4400 E6 200 1000 500 400 200 5 60-120 4400 Table 3: Comparison of computational results for four algorithms Case T3L-DS SA A-SeTVBRP CNP Emg. cov. Routine ret. Pre-empt. Resched. Emg. cov. Routine ret. Pre-empt. Resched. Emg. cov. Routine ret. Pre-empt. Resched. Emg. cov. Routine ret. Pre-empt. A1 79.036 ± 3.326 99.998 ± 0.001 0.005 ± 0.002 84.391 ± 8.209 83.692 ± 2.368 99.999 ± 0.001 82.003 ± 0.257 99.999 ± 0.001 77.838 ± 4.820 99.998 ± 0.001 0.005 ± 0.003 77.702 ± 7.085 70.371 ± 4.430 99.952 ± 0.003 0.047 ± 0.003 A2 76.447 ± 1.574 99.996 ± 0.002 0.021 ± 0.008 87.871 ± 8.383 80.423 ± 1.647 99.999 ± 0.001 83.397 ± 0.266 99.998 ± 0.001 75.814 ± 1.958 99.994 ± 0.003 0.022 ± 0.007 77.321 ± 8.517 65.645 ± 0.993 99.887 ± 0.010 0.112 ± 0.010 A3 77.675 ± 0.992 99.996 ± 0.003 0.039 ± 0.013 92.791 ± 6.722 82.431 ± 0.947 99.996 ± 0.001 83.878 ± 0.255 99.996 ± 0.001 76.309 ± 1.105 99.99 ± 0.003 0.045 ± 0.016 79.159 ± 5.254 66.956 ± 0.646 99.675 ± 0.023 0.324 ± 0.023 A4 79.413 ± 1.459 99.995 ± 0.001 0.047 ± 0.009 89.856 ± 2.517 84.214 ± 1.396 99.993 ± 0.001 84.152 ± 0.274 99.992 ± 0.002 78.418 ± 1.428 99.985 ± 0.005 0.053 ± 0.017 74.115 ± 5.000 66.502 ± 1.036 99.572 ± 0.021 0.427 ± 0.021 B1 84.669 ± 1.677 99.995 ± 0.001 0.040 ± 0.018 85.652 ± 8.367 88.560 ± 1.969 99.999 ± 0.001 88.139 ± 0.209 99.999 ± 0.001 83.034 ± 1.858 99.989 ± 0.004 0.035 ± 0.008 70.672 ± 7.464 72.280 ± 2.010 99.621 ± 0.014 0.378 ± 0.014 B2 74.961 ± 1.784 99.996 ± 0.004 0.020 ± 0.011 82.808 ± 7.023 80.024 ± 2.417 99.997 ± 0.001 83.886 ± 0.217 99.996 ± 0.001 73.762 ± 1.748 99.994 ± 0.004 0.026 ± 0.014 74.124 ± 8.235 65.519 ± 1.530 99.772 ± 0.021 0.227 ± 0.021 B3 74.762 ± 0.765 99.996 ± 0.002 0.022 ± 0.010 81.723 ± 7.547 80.070 ± 1.220 99.997 ± 0.001 82.154 ± 0.252 99.996 ± 0.001 73.793 ± 1.056 99.994 ± 0.002 0.025 ± 0.009 76.209 ± 6.174 64.290 ± 2.245 99.805 ± 0.006 0.194 ± 0.006 B4 76.539 ± 2.380 99.995 ± 0.002 0.024 ± 0.008 81.138 ± 3.686 82.233 ± 2.077 99.998 ± 0.001 81.757 ± 0.128 99.997 ± 0.001 75.660 ± 1.990 99.993 ± 0.003 0.024 ± 0.011 73.896 ± 3.650 65.797 ± 1.033 99.820 ± 0.020 0.179 ± 0.020 C1 50.512 ± 1.631 99.977 ± 0.009 0.099 ± 0.018 77.828 ± 5.763 62.094 ± 2.040 99.074 ± 0.023 58.740 ± 0.322 98.425 ± 0.035 50.198 ± 1.571 99.976 ± 0.007 0.098 ± 0.020 76.794 ± 4.165 43.762 ± 2.319 99.615 ± 0.028 0.384 ± 0.028 C2 53.136 ± 2.641 99.989 ± 0.003 0.068 ± 0.023 83.966 ± 5.181 61.527 ± 2.547 99.844 ± 0.003 71.343 ± 0.394 99.782 ± 0.005 52.815 ± 2.490 99.988 ± 0.004 0.066 ± 0.021 82.769 ± 4.187 48.251 ± 3.064 99.709 ± 0.038 0.290 ± 0.038 C3 67.945 ± 1.503 99.993 ± 0.003 0.042 ± 0.010 84.490 ± 6.031 74.003 ± 1.925 99.986 ± 0.001 78.409 ± 0.166 99.982 ± 0.001 67.780 ± 1.138 99.989 ± 0.003 0.044 ± 0.013 77.723 ± 4.737 59.791 ± 0.618 99.758 ± 0.025 0.241 ± 0.025 C4 71.075 ± 1.024 99.995 ± 0.001 0.026 ± 0.006 80.932 ± 8.213 76.112 ± 1.226 99.995 ± 0.002 81.299 ± 0.342 99.994 ± 0.003 70.033 ± 0.924 99.993 ± 0.001 0.026 ± 0.005 74.633 ± 7.158 59.950 ± 2.210 99.800 ± 0.010 0.199 ± 0.010 D1 79.670 ± 3.315 99.996 ± 0.002 0.035 ± 0.009 91.556 ± 5.348 85.007 ± 3.039 99.998 ± 0.001 82.133 ± 0.288 99.997 ± 0.001 77.536 ± 2.961 99.991 ± 0.003 0.037 ± 0.009 78.861 ± 5.321 65.240 ± 2.445 99.782 ± 0.014 0.217 ± 0.014 D2 76.625 ± 3.406 99.996 ± 0.003 0.024 ± 0.011 85.829 ± 8.442 81.948 ± 2.892 99.997 ± 0.002 83.430 ± 0.318 99.996 ± 0.003 74.982 ± 2.927 99.994 ± 0.001 0.023 ± 0.010 75.710 ± 7.760 65.269 ± 2.500 99.796 ± 0.003 0.203 ± 0.003 D3 77.634 ± 0.862 99.993 ± 0.003 0.030 ± 0.008 78.755 ± 6.350 82.134 ± 0.897 99.996 ± 0.002 84.043 ± 0.176 99.995 ± 0.003 76.247 ± 0.757 99.990 ± 0.002 0.030 ± 0.008 68.822 ± 8.165 66.888 ± 1.622 99.781 ± 0.008 0.218 ± 0.008 D4 78.924 ± 0.780 99.996 ± 0.001 0.023 ± 0.006 86.307 ± 3.741 83.779 ± 0.801 99.996 ± 0.001 84.342 ± 0.144 99.995 ± 0.001 78.305 ± 0.822 99.992 ± 0.002 0.027 ± 0.006 73.154 ± 9.007 68.368 ± 1.570 99.776 ± 0.015 0.223 ± 0.015 E1 79.957 ± 2.716 98.950 ± 0.320 6.777 ± 0.555 84.703 ± 3.616 85.342 ± 2.152 99.573 ± 0.294 71.399 ± 0.665 99.402 ± 0.413 75.518 ± 2.742 97.624 ± 0.297 7.142 ± 0.816 66.698 ± 2.614 66.277 ± 0.981 93.196 ± 0.338 6.803 ± 0.338 E2 77.758 ± 1.801 98.664 ± 0.330 9.079 ± 0.729 85.341 ± 3.132 83.552 ± 1.339 99.491 ± 0.294 72.251 ± 1.096 99.298 ± 0.408 72.631 ± 1.853 97.090 ± 0.216 9.150 ± 0.647 68.189 ± 1.306 63.429 ± 1.298 91.411 ± 0.399 8.588 ± 0.399 E3 77.522 ± 2.200 98.528 ± 0.530 10.854 ± 1.495 86.717 ± 3.180 83.161 ± 1.215 99.324 ± 0.427 72.292 ± 0.943 99.069 ± 0.584 72.373 ± 1.217 96.687 ± 0.628 11.048 ± 1.366 70.167 ± 2.371 63.057 ± 0.582 89.925 ± 1.103 10.074 ± 1.103 E4 83.462 ± 3.234 99.082 ± 0.218 9.217 ± 0.900 90.034 ± 2.398 88.123 ± 2.796 99.888 ± 0.076 83.926 ± 0.987 99.868 ± 0.090 78.198 ± 2.931 97.916 ± 0.490 9.637 ± 0.571 78.366 ± 5.105 70.679 ± 2.236 91.108 ± 0.823 8.891 ± 0.823 E5 83.291 ± 1.745 99.523 ± 0.152 6.647 ± 0.893 92.919 ± 1.689 88.938 ± 1.789 99.842 ± 0.096 82.031 ± 0.433 99.808 ± 0.117 78.424 ± 1.925 98.673 ± 0.180 6.727 ± 0.534 80.283 ± 2.095 71.197 ± 0.785 93.539 ± 0.590 6.460 ± 0.590 E6 83.744 ± 0.410 99.257 ± 0.314 7.201 ± 0.430 89.720 ± 4.133 89.272 ± 0.444 99.866 ± 0.051 80.660 ± 0.397 99.834 ± 0.063 77.931 ± 1.003 98.068 ± 0.441 7.404 ± 0.347 74.035 ± 4.938 70.949 ± 1.703 93.083 ± 0.454 6.916 ± 0.454 Note: All values are percentages. Each entry reports the mean ± standard deviation across ten problem instances generated from ten independent random seeds under the same configuration; all four methods are evaluated on the same instance (seed). Emg. cov., routine ret., pre-empt., and resched. denote emergency coverage, routine retention, routine pre-emption, and routine rescheduling, respectively. CNP does not include a routine-rescheduling stage, so its rescheduling rate is zero in every case and is omitted from the table. Table 2 organises 22 distinct scenarios 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 All methods use the same committed schedule, emergency waves, observation opportunities, and initial states. The three comparative methods are: • SA: a centralised simulated-annealing reference [12] that starts from a greedy solution and runs 1,000 iterations for each emergency wave with access to the current global instance. • A-SeTVBRP: an adapted selective time-variant better reply process based on [40], where satellites update feasible local schedules by asynchronous better replies and cluster heads exchange states through direct ISLs. • CNP: a conventional contract-net protocol [20] baseline that uses the same event-specific head-centred clusters as T3L-DS. 5.3 Evaluation metrics Four metrics assess emergency service and routine-plan preservation. Let EG^E be the unique emergency cells, and let mEC^E_m contain those observed by method m within an applicable request window. Let RG^R and mRC^R_m denote the routine cells in the common input schedule and the final schedule, respectively. Finally, ℐmRI^R_m contains routine cells invalidated by emergency insertion, and ℐmR,rsc=ℐmR∩mRI_m^R,rsc=I^R_m ^R_m contains those subsequently rescheduled. CovmE ^E_m =|mE||E|, = |C^E_m||G^E|, RetmR ^R_m =|mR||R|, = |C^R_m||G^R|, (15) PremR ^R_m =|ℐmR||R|, = |I^R_m||G^R|, RscmR ^R_m =|ℐmR,rsc||ℐmR|. = |I_m^R,rsc||I^R_m|. The four quantities are emergency coverage, routine retention, routine pre-emption, and routine rescheduling. A cell observed outside its emergency window receives no emergency credit. When ℐmR=∅I^R_m= , RscmRRsc^R_m is defined as zero. 5.4 Experimental results and analysis Table 3 reports the means and standard deviations of the four core metrics for all five groups. Across the 22 configurations, SA provides 5.5% more emergency coverage than T3L-DS on average. The centralised search can use global information to consider a wider range of insertions, but it pre-empts 79.8% of the committed routine cells, compared with 2.3% for T3L-DS. SA subsequently reschedules most of those cells, so its mean routine retention is only 0.13 percentage points higher. Within the distributed comparison, T3L-DS exceeds A-SeTVBRP and CNP in mean emergency coverage by 2.1 and 11.1%, respectively. It also reschedules 10.7% more displaced routine cells than A-SeTVBRP, while CNP has no rescheduling stage. These results are consistent with candidate-level marginal awards retaining feasible parts of overlapping bids and inter-cluster coordination providing further opportunities for unresolved demand. The following analyses examine where these aggregate differences arise. Groups A, C, and D compare performance under different emergency-demand scale, constellation size, and level of temporal concentration, respectively, while holding the other principal settings fixed. Group E then considers successive changes in emergency demand, available satellites, and routine background under stronger conflicts. 5.4.1 Emergency-demand scale Group A examines how emergency-demand scale affects performance while holding the constellation and routine background fixed. Figure 6 shows that emergency coverage initially decreases and then increases at higher demand levels across all four methods. The initial growth in emergency demand intensifies competition for a fixed set of satellite access intervals, causing the covered proportion to fall. As demand becomes denser, spatial overlap among emergency requests and between emergency and routine observations becomes more frequent. A single observation can consequently satisfy several grid-cell demand units, which offsets part of the capacity pressure and causes coverage to rise at the higher demand levels. Figure 6: Emergency coverage of the four methods (upper panel) and routine pre-emption of T3L-DS (lower panel) under increasing emergency demand. Cases A1-A4 keep the 500-satellite constellation and 11,000 routine targets fixed while increasing emergency requests from 75 to 600. The difference between T3L-DS and SA stays from 4.0%4.0\% to 4.8%4.8\%. T3L-DS remains ahead of A-SeTVBRP and establishes a larger advantage over CNP at the highest demand level. From A2 to A4, the emergency coverage of T3L-DS increases by 3.9%3.9\%, compared with 3.4%3.4\% for A-SeTVBRP and 1.3%1.3\% for CNP. Candidate-level awards retain useful observations from overlapping bids, and inter-cluster coordination reallocates demand that cannot be accommodated within its initial cluster. These mechanisms become more valuable as simultaneous conflicts increase. Routine pre-emption also rises with emergency demand because more insertions encounter occupied intervals, although the increase becomes slower at the highest demand level. At this density, same-cell reuse serves more additional demand without requiring a proportional increase in displaced routine observations. 5.4.2 Constellation size Group C examines how constellation size affects performance while keeping routine and emergency demand unchanged. Figure 7 shows a pronounced rise in emergency coverage as more satellites become available. From C1 to C4, T3L-DS increases its emergency coverage by 40.7%40.7\%, compared with 22.6%22.6\% for SA. The relative gain is larger for T3L-DS because constellation expansion supplies more feasible local candidates and cross-cluster alternatives, reducing the disadvantage of making decisions with local information. SA already exploits constellation-wide opportunities in the smaller cases, so its relative benefit from the added satellites is lower. For all methods, the improvement becomes less pronounced at the largest constellation size because new satellites increasingly duplicate visibility that is already available. Figure 7: Emergency coverage of the four methods (upper panel) and routine pre-emption of T3L-DS (lower panel) under increasing constellation size. Cases C1-C4 keep the routine and emergency demand fixed while increasing the constellation from 100 to 400 satellites. T3L-DS remains slightly ahead of A-SeTVBRP across the group and reaches a larger advantage over CNP at the higher constellation sizes. Inter-cluster coordination and candidate-level evaluation allow T3L-DS to use the enlarged opportunity set without accepting or rejecting each bid as a whole. Routine pre-emption falls by 73.7%73.7\% from C1 to C4 because more emergency observations can be assigned to alternative satellites and idle intervals. The reduction gradually flattens as the remaining conflicts concentrate on requests with limited visibility or restrictive time windows. 5.4.3 Emergency-demand temporal concentration Group D keeps total emergency demand fixed and changes the number of arrival waves. Figure 8 shows that coverage first decreases and then increases as the requests are divided into more waves. With five waves, each allocation event contains more requests and provides greater scope for shared grid coverage and coordinated assignment. Increasing the number of waves initially separates requests that could otherwise be considered together, while earlier insertions occupy opportunities available to later waves. At the highest wave count, the number of simultaneous requests becomes sufficiently small to reduce competition within each allocation event, and coverage increases. Figure 8: Effect of the emergency arrival-wave count on coverage and routine rescheduling. Bars show the emergency coverage of the four methods on the left axis, and the line shows the routine rescheduling of T3L-DS on the right axis. Cases D1-D4 keep 300 emergency requests fixed while distributing them over 5 to 30 arrival waves. T3L-DS remains the strongest distributed method, while its difference from SA ranges from 4.5%4.5\% to 5.3%5.3\%. Its advantage over A-SeTVBRP narrows as each wave becomes smaller because fewer requests require cross-satellite alternatives at the same time. CNP also benefits from lower per-wave competition, but whole-bid allocation continues to lose useful observations when bids overlap. Routine rescheduling also decreases at first and then increases. At intermediate wave counts, repeated emergency commitments divide the remaining schedule into shorter feasible intervals. The smaller request set in the D4 event permits more selective insertions and leaves more feasible gaps, allowing the T3L-DS rescheduling rate to increase by 9.6%9.6\% relative to D3. 5.4.4 Conflict-enhanced balanced-load conditions Group E contains three controlled comparisons under stronger spatial and temporal conflicts. Each comparison changes only one of emergency demand, constellation size, and routine background while holding the other settings fixed. Figure 9 reports emergency service and routine-plan preservation across these comparisons. E1-E3 increase emergency demand while holding the 100-satellite constellation and routine load fixed. Coverage declines for all four methods, but T3L-DS loses 3.1%3.1\% relative to E1, compared with 4.2%4.2\% for A-SeTVBRP and 4.9%4.9\% for CNP. Its difference from SA remains almost unchanged, while its advantage over the distributed baselines grows as conflicts become denser. Partial bid retention avoids discarding non-conflicting observations, and inter-cluster coordination broadens the set of satellites that can absorb unresolved demand. Routine retention declines and pre-emption rises over the same cases because the additional emergency insertions consume a larger share of the adjustable routine plan. E3-E4 compare performance before and after the constellation size is doubled. T3L-DS improves its emergency coverage by 7.7%7.7\% relative to E3, exceeding the 6.0%6.0\% increase of SA while retaining its advantage over the distributed baselines. Under the stronger conflicts in Group E, the added satellites supply alternative access intervals and reduce the number of requests confined to a small set of feasible spacecraft. T3L-DS can exploit these alternatives through inter-cluster coordination, whereas SA already uses global information and obtains a smaller relative gain from the additional resources. Routine retention rises at the same time and routine pre-emption falls. The additional emergency coverage is obtained from new orbital opportunities rather than from greater disruption of the routine plan. Figure 9: Performance under conflict-enhanced balanced-load conditions. The upper panel combines emergency coverage (bars, left axis) and routine retention (lines, right axis); the lower panel combines routine pre-emption (bars, left axis) and routine rescheduling (lines, right axis). Cases E1-E3 use 100 satellites with a fixed routine load and increasing emergency demand. Cases E3-E4 keep both loads fixed and increase the constellation from 100 to 200 satellites. Cases E4-E6 use 200 satellites with fixed emergency demand and increasing routine load. E4-E6 then increase only the routine background. Relative to E4, T3L-DS changes its emergency coverage by no more than 0.4%0.4\% in E5 and E6, so the added routine demand mainly affects the routine plan. The pre-emption rate remains below its E4 level because displaced grid cells form a smaller share of the expanded routine plan and more emergency cells can reuse scheduled observations. Routine rescheduling also stays close to its E4 level despite the denser background. Together, the two panels show that T3L-DS preserves emergency service under severe conflict and reschedules most of the displaced routine cells. 5.5 Ablation study T3L-DS comprises three principal coordination mechanisms: inter-cluster coordination, dual-plan construction, and candidate-level joint evaluation. An ablation study is conducted to quantify the contribution of each mechanism to the overall scheduling performance. The three reduced settings remove inter-cluster coordination (No-IC), retain Plan A only (No-DP), and combine Plan-A-only generation with whole-plan acceptance in place of candidate-level joint evaluation (No-Comb), respectively. It uses A4 and B4, which impose the largest emergency and routine loads in their respective groups, C1 with the smallest constellation, and D1 with the most concentrated arrivals. Table 4 reports the four core metrics, while Figure 10 shows the loss of emergency coverage relative to the full method. Table 4: Ablation results Case Variant Emg. cov. Routine ret. Pre-empt. Resched. A4 Full 79.413 ± 1.459 99.995 ± 0.001 0.047 ± 0.009 89.856 ± 2.517 No-IC 72.285 ± 1.056 99.989 ± 0.004 0.044 ± 0.012 76.054 ± 3.367 No-DP 78.659 ± 1.559 99.996 ± 0.001 0.044 ± 0.010 90.997 ± 2.426 No-Comb 78.665 ± 1.746 99.996 ± 0.001 0.045 ± 0.007 90.948 ± 2.362 B4 Full 76.539 ± 2.380 99.995 ± 0.002 0.024 ± 0.008 81.138 ± 3.686 No-IC 68.232 ± 2.924 99.993 ± 0.003 0.021 ± 0.010 70.275 ± 3.588 No-DP 75.583 ± 2.325 99.995 ± 0.002 0.023 ± 0.008 80.752 ± 4.750 No-Comb 75.492 ± 2.270 99.995 ± 0.002 0.022 ± 0.009 79.861 ± 4.098 C1 Full 50.512 ± 1.631 99.977 ± 0.009 0.099 ± 0.018 77.828 ± 5.763 No-IC 46.761 ± 1.264 99.978 ± 0.007 0.088 ± 0.016 75.670 ± 4.016 No-DP 50.252 ± 1.583 99.977 ± 0.009 0.096 ± 0.021 77.569 ± 5.413 No-Comb 50.252 ± 1.830 99.977 ± 0.009 0.075 ± 0.018 77.691 ± 5.153 D1 Full 79.670 ± 3.315 99.996 ± 0.002 0.035 ± 0.009 91.556 ± 5.348 No-IC 68.117 ± 2.731 99.992 ± 0.003 0.032 ± 0.007 77.797 ± 5.246 No-DP 78.765 ± 3.207 99.996 ± 0.002 0.034 ± 0.007 91.061 ± 6.546 No-Comb 78.709 ± 3.046 99.996 ± 0.002 0.035 ± 0.006 90.465 ± 6.269 All values are percentages. Each entry reports the mean ± standard deviation across ten problem instances generated from ten independent random seeds under the same configuration. Emg. cov., routine ret., pre-empt., and resched. denote emergency coverage, routine retention, routine pre-emption, and routine rescheduling, respectively. Figure 10: Emergency-coverage loss relative to Full under the three ablation settings. A4, B4, C1, and D1 represent emergency-demand, routine-load, constellation-size, and temporal-concentration stress, respectively. As shown in Table 4 and Figure 10, inter-cluster coordination makes the largest contribution among the three components evaluated. Its removal reduces emergency coverage by 3.8%3.8\%-11.6%11.6\% across the four selected cases. The largest loss occurs in D1, where each arrival wave contains more simultaneous requests, followed by B4 with its dense committed routine plan and A4 with its heavy emergency load. In these cases, the visibility and attitude margins available inside one temporary cluster are more readily exhausted, so neighbouring clusters provide useful alternatives. The smaller loss in C1 is consistent with its sparse 100-satellite topology, which offers fewer neighbouring assets capable of accepting transferred demand. Local-plan diversity and candidate-level joint evaluation have smaller effects on coverage. Removing Plan B produces losses of 0.26%0.26\%-0.96%0.96\%, with the larger changes in B4 and D1. Under a dense routine plan or concentrated arrivals, a second local plan can retain an alternative that avoids a conflict affecting Plan A. Replacing candidate-level joint evaluation with whole-plan acceptance changes coverage by no more than 0.09%0.09\% beyond the Plan-A-only setting. The results therefore retain the original ordering of contributions. Inter-cluster coordination provides the main gain under resource pressure, while dual-plan construction and candidate-level evaluation refine the local choices. 6 Conclusions This paper studies DEOSP, where emergency point and area requests must be scheduled while a routine observation plan is already being executed. The proposed geographic-grid formulation uses common spatial units to describe emergency demand, satellite footprints, coverage credit, and disturbance to the committed plan. On this basis, T3L-DS coordinates scheduling through event-level ground organisation, onboard dual-plan bidding, and cluster-level allocation over available ISLs. The method modifies only adjustable future activities, while completed, executing, and protected routine activities remain outside the revision scope. The experiments show that T3L-DS gives the strongest emergency service among the distributed methods and preserves most routine grid-cell coverage under the tested conditions. Future work will add more detailed onboard computation, energy, and communication models, and will test the framework under uncertain ISL availability. Acknowledgements This work was supported by the National Natural Science Foundation of China under Grants 62503503 and 62373380. The authors used a large language model to assist with language editing, LaTeX consistency checking, and manuscript organisation. All content was reviewed by the authors, who take full responsibility for the manuscript. References [1] Z. Chang, A. P. Punnen, and Z. Zhou (2023) Multi-strip observation scheduling problem for active-imaging agile earth observation satellites. Neural Computing and Applications 37 (33), p. 27505–27524. External Links: Document Cited by: §2. [2] A. Chatterjee and R. Tharmarasa (2024) Multi-stage optimization framework of satellite scheduling for large areas of interest. Advances in Space Research 73 (3), p. 2024–2039. External Links: Document Cited by: §2. [3] Y. Chen, X. Shen, G. Zhang, and Z. Lu (2023) Large-scale multi-objective imaging satellite task planning algorithm for vast area mapping. Remote Sensing 15 (17), p. 4178. External Links: Document Cited by: §2. [4] Y. Chen, M. Xu, X. Shen, G. Zhang, Z. Lu, and J. Xu (2020) A multi-objective modeling method of multi-satellite imaging task planning for large regional mapping. Remote Sensing 12 (3), p. 344. External Links: Document Cited by: §2. [5] B. Du and S. Li (2019) A new multi-satellite autonomous mission allocation and planning method. Acta Astronautica 163, p. 287–298. External Links: Document Cited by: §1, §2, §3.2. [6] L. Eddy and M. J. Kochenderfer (2021) A maximum independent set method for scheduling earth-observing satellite constellations. Journal of Spacecraft and Rockets 58 (6), p. 1441–1455. External Links: Document Cited by: §2, §3.4. [7] Y. Feng, R. Zhang, S. Ren, S. Zhu, and Y. Yang (2023) A distributed approach for time-dependent observation scheduling problem in the agile earth observation satellite constellation. Remote Sensing 15 (7), p. 1761. External Links: Document Cited by: §1, §1, §2. [8] B. Ferrari, J. Cordeau, M. Delorme, M. Iori, and R. Orosei (2025) Satellite scheduling problems: a survey of applications in earth and outer space observation. Computers & Operations Research 173, p. 106875. External Links: Document Cited by: §1, §2. [9] M. E. Galloua, S. Li, and J. Cui (2025) Earth observation satellite imaging task scheduling with metaheuristics: multi-level clustering and priority-driven pre-scheduling. Advances in Space Research 75 (3), p. 2929–2953. External Links: Document Cited by: §2. [10] Y. Gu, C. Han, Y. Chen, S. Liu, and X. Wang (2022) Large region targets observation scheduling by multiple satellites using resampling particle swarm optimization. IEEE Transactions on Aerospace and Electronic Systems 59 (2), p. 1800–1815. External Links: Document Cited by: §2. [11] H3 Contributors (2025) H3 documentation: a hexagonal hierarchical geospatial indexing system. Note: https://h3geo.org/docs/Accessed: 2025-12-14 Cited by: §1, §3.3. [12] C. Han, Y. Gu, G. Wu, and X. Wang (2022) Simulated annealing-based heuristic for multiple agile satellites scheduling under cloud coverage uncertainty. IEEE Transactions on Systems, Man, and Cybernetics: Systems 53 (5), p. 2863–2874. External Links: Document Cited by: 1st item. [13] L. He, B. Liang, J. Li, and M. Sheng (2020) Balancing coverage and response time in area target scheduling for satellite networks. IEEE Transactions on Vehicular Technology 69 (6), p. 6848–6853. External Links: Document Cited by: §2. [14] A. Herrmann and H. Schaub (2023) Reinforcement learning for the agile earth-observing satellite scheduling problem. IEEE Transactions on Aerospace and Electronic Systems 59 (5), p. 5235–5247. External Links: Document Cited by: §2. [15] A. Herrmann, M. A. Stephenson, and H. Schaub (2024) Single-agent reinforcement learning for scalable earth-observing satellite constellation operations. Journal of Spacecraft and Rockets 61 (1), p. 114–132. External Links: Document Cited by: §2. [16] H. Ji and D. Huang (2019) A mission planning method for multi-satellite wide area observation. International Journal of Advanced Robotic Systems 16 (6), p. 1729881419890715. External Links: Document Cited by: §2. [17] R. Kandepi, H. Saini, R. K. George, S. Konduri, and R. Karidhal (2024) Agile earth observation satellite constellations scheduling for large area target imaging using heuristic search. Acta Astronautica 219, p. 670–677. External Links: Document Cited by: §2. [18] S. Krigman, T. Grinshpoun, and L. Dery (2024) Scheduling of earth observing satellites using distributed constraint optimization. Journal of Scheduling 27, p. 507–524. External Links: Document Cited by: §1, §2, §3.2. [19] J. Li, J. Zhu, D. Xu, J. Wang, Z. Li, and K. Zhang (2024) Earth observation satellite scheduling with interval-varying profits. IEEE Transactions on Aerospace and Electronic Systems 60 (6), p. 8273–8288. External Links: Document Cited by: §2. [20] B. Liu, M. Deng, G. Wu, X. Pei, H. Li, and W. Pedrycz (2022) Bottom-up mechanism and improved contract net protocol for dynamic task planning of heterogeneous earth observation resources. IEEE Transactions on Systems, Man, and Cybernetics: Systems 52 (10), p. 6183–6196. External Links: Document Cited by: §1, §2, §3.1, §3.2, 3rd item. [21] Z. Lu, X. Shen, D. Li, D. Li, Y. Chen, D. Wang, and S. Shen (2023) Multiple super-agile satellite collaborative mission planning for area target imaging. International Journal of Applied Earth Observation and Geoinformation 117, p. 103211. External Links: Document Cited by: §2. [22] G. Peng, G. Song, L. Xing, A. Gunawan, and P. Vansteenwegen (2020) An exact algorithm for agile earth observation satellite scheduling with time-dependent profits. Computers & Operations Research 120, p. 104946. External Links: Document Cited by: §1, §2. [23] J. Qi, M. Hu, and L. Xing (2025) A decompose-and-learn multi-objective algorithm for scheduling large-scale earth observation satellites. Swarm and Evolutionary Computation 92, p. 101792. External Links: Document Cited by: §2. [24] K. Sahr (2008) Location coding on icosahedral aperture 3 hexagon discrete global grids. Computers, Environment and Urban Systems 32 (3), p. 174–187. External Links: Document Cited by: §3.3. [25] R. G. Smith (1981) The contract net protocol: high-level communication and control in a distributed problem solver. IEEE Transactions on Computers 100 (5), p. 372–372. External Links: Document Cited by: §2. [26] Y. Song, L. Wei, Q. Yang, J. Wu, L. Xing, and Y. Chen (2023) RL-GA: a reinforcement learning-based genetic algorithm for electromagnetic detection satellite scheduling problem. Swarm and Evolutionary Computation 77, p. 101236. External Links: Document Cited by: §2. [27] H. Wang and S. Bai (2022) A versatile method for target area coverage analysis with arbitrary satellite attitude maneuver paths. Acta Astronautica 194, p. 242–254. External Links: Document Cited by: §2, §2. [28] X. Wang, Z. Chen, and C. Han (2016) Scheduling for single agile satellite, redundant targets problem using complex networks theory. Chaos, Solitons & Fractals 83, p. 125–132. External Links: Document Cited by: §2. [29] X. Wang, C. Han, and R. Leus (2025) Scheduling multiple agile earth observation satellites with multiple observations. Advances in Space Research. Note: Available online 2025 External Links: Document Cited by: §2. [30] X. Wang, C. Han, P. Yang, and X. Sun (2019) Onboard satellite visibility prediction using metamodeling based framework. Aerospace Science and Technology 94, p. 105377. External Links: Document Cited by: §4.1. [31] X. Wang, G. Song, R. Leus, and C. Han (2019) Robust earth observation satellite scheduling with uncertainty of cloud coverage. IEEE Transactions on Aerospace and Electronic Systems 56 (3), p. 2450–2461. External Links: Document Cited by: §2. [32] X. Wang, G. Wu, L. Xing, and W. Pedrycz (2020) Agile earth observation satellite scheduling over 20 years: formulations, methods, and future directions. IEEE Systems Journal 15 (3), p. 3881–3892. External Links: Document Cited by: §1, §2. [33] G. Wu, Q. Luo, X. Du, Y. Chen, P. N. Suganthan, and X. Wang (2022) Ensemble of metaheuristic and exact algorithm based on the divide-and-conquer framework for multisatellite observation scheduling. IEEE Transactions on Aerospace and Electronic Systems 58 (5), p. 4396–4408. External Links: Document Cited by: §1, §1, §2. [34] J. Wu, Y. Chen, Y. He, L. Xing, and Y. Hu (2022) Survey on autonomous task scheduling technology for earth observation satellites. Journal of Systems Engineering and Electronics 33 (6), p. 1176–1189. External Links: Document Cited by: §1, §2, §3.2. [35] J. Wu, F. Yao, Y. Song, L. He, F. Lu, Y. Du, J. Yan, Y. Chen, L. Xing, and J. Ou (2023) Frequent pattern-based parallel search approach for time-dependent agile earth observation satellite scheduling. Information Sciences 636, p. 118924. External Links: Document Cited by: §3.4. [36] Q. Wu, J. Pan, and M. Wang (2024) Dynamic task planning method for multi-source remote sensing satellite cooperative observation in complex scenarios. Remote Sensing 16 (4), p. 657. External Links: Document Cited by: §1, §3.1, §3.2. [37] L. Xing, W. Xia, X. Hu, W. Zhu, and Y. Wu (2024) An adaptive local grid nesting-based genetic algorithm for multi-earth observation satellites’ area target observation. Journal of Systems Science and Systems Engineering 33 (2), p. 232–258. External Links: Document Cited by: §2. [38] S. Xu, B. Song, Y. Chen, J. Chen, Y. Chen, and F. Wang (2024) A heat grid-driven method for generation of satellite observation tasks. Advances in Space Research 74 (8), p. 3983–3996. External Links: Document Cited by: §2. [39] Y. Xu, X. Liu, R. He, and Y. Chen (2020) Multi-satellite scheduling framework and algorithm for very large area observation. Acta Astronautica 167, p. 93–107. External Links: Document Cited by: §2. [40] W. Yang, Y. Chen, X. Liu, J. Wen, and L. He (2025) Distributed satellites dynamic allocation for observation grids with time windows: A potential game approach. Aerospace Science and Technology, p. 110895. External Links: Document Cited by: §1, §2, §3.2, 2nd item. [41] Q. Yin, W. Tang, Y. Gu, et al. (2026) Heatmap-based unified grid characterization and planning method for task–resource scheduling in large-scale LEO constellations. Acta Aeronautica et Astronautica Sinica 47 (23), p. 333285. Note: in Chinese External Links: Document Cited by: §3.1, §3.3. [42] Q. Yin, J. Li, J. Cheng, Q. Luo, A. Riccardi, A. Chatterjee, R. Vazquez, C. Novara, M. Mavrovouniotis, P. N. Suganthan, S. Bai, X. Hu, L. Xing, M. Xu, S. Li, Z. Zheng, X. Shen, X. Chen, Y. Gu, Y. Song, W. Pedrycz, E. L. Kramer, L. O. Seman, C. Shoko, G. Wu, and X. Wang (2026) EOS-Bench: A Comprehensive Benchmark for Earth Observation Satellite Scheduling. External Links: Link, Document Cited by: §5.1. [43] X. Zeng, R. Yuan, L. Yang, X. Huang, and S. Li (2026) Long-term multi-region observation scheduling for large-scale constellations via two-stage hybrid planning. Aerospace Science and Technology 169, p. 111358. External Links: Document Cited by: §1, §1, §2. [44] I. Zilberstein, A. Rao, M. Salis, and S. A. Chien (2025) Decentralized, decomposition-based observation scheduling for a large-scale satellite constellation. Journal of Artificial Intelligence Research 82, p. 169–208. External Links: Document Cited by: §1, §1, §2.