arXiv CSopen access

EOS-Bench: A Comprehensive Benchmark for Earth Observation Satellite Scheduling

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

distributed-systems internet networking protocols

networking, internet, protocols, distributed systems

EOS-Bench: A Comprehensive Benchmark for Earth Observation Satellite Scheduling Qian Yina,b , Jiaxing Lib , Jiaqi Chenga , Qizhang Luoc , Annalisa Riccardid , Abhijit Chatterjeee , Rafael Vazquezf , Carlo Novarag , Michalis Mavrovouniotish,i , Ponnuthurai Nagaratnam Suganthanj , Shengzhou Baik , Xiaoxuan Hul , Lining Xingm , Ming Xun , Shuang Lio , Zixuan Zhengp , Xin Shenq , Xiaoyu Chenr , Yi Gua , Yanjie Songs , Witold Pedryczt , Evan L. Krameru , Laio Oriel Semanv , Cletah Shokow , Guohua Wuc,∗, Xinwei Wangb,∗ a

School of Traﬃc and Transportation Engineering, Central South University, Changsha 410083, China School of Engineering and Materials Science, Queen Mary University of London, London E1 4NS, UK c College of Automation, Central South University, Changsha, 410083, China d Mechanical and Aerospace Engineering, University of Strathclyde, Glasgow G1 1XQ, UK e Department of Computer Science, University of Exeter, Exeter EX4 4QJ, UK f Department of Aerospace Engineering, Universidad de Sevilla, Camino de los Descubrimientos s.n., Sevilla, 41092, Spain g Department of Electronics and Telecommunications, Politecnico di Torino, Corso Duca degli Abruzzi, 24, Turin, 10129, Italy h ERATOSTHENES Centre of Excellence, Limassol, 3012, Cyprus i Department of Civil Engineering and Geomatics, Cyprus University of Technology, Limassol, 3036, Cyprus j Department of Computer Science and Engineering, College of Engineering, Qatar University, Doha, 2713, Qatar k Department of Aerospace Engineering, Korea Advanced Institute of Science and Technology, Daejeon, 34141, South Korea l School of Management, Hefei University of Technology, Hefei, 230009, China m Key Laboratory of Collaborative Intelligence Systems, Ministry of Education, Xidian University, Xian 710071, China n School of Astronautics, Beihang University, 102206 Beijing, China o Advanced Space Technology Laboratory, College of Astronautics, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China p National Key Laboratory of Aerospace Flight Dynamics, Northwestern Polytechnical University, Xian, 710072, China q State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, 430079, China r School of Computer Science, China University of Geosciences, Wuhan, 430074, China s School of Information Science and Technology, Dalian Maritime University, Dalian, 116026, China t Department of Electrical & Computer Engineering, University of Alberta, Edmonton, AB T6R 2V4, Canada u Division of Geological and Planetary Science, California Institute of Technology, CA, USA v Department of Automation and Systems Engineering, Federal University of Santa Catarina, Florianopolis, SC, Brazil w School of Geography, Archaeology and Environmental Studies, University of the Witwatersrand, Braamfontein, Johannesburg, South Africa

arXiv:2604.25782v1 [cs.NI] 28 Apr 2026

∗

Corresponding authors Email addresses: [email protected] (Guohua Wu), [email protected] (Xinwei Wang)

Abstract Earth observation satellite imaging scheduling is a challenging NP-hard combinatorial optimisation problem that is critical to space mission operations. While next-generation agile Earth observation satellites (EOS) enhance ﬂexibility, they also increase scheduling complexity. Because the community currently lacks a uniﬁed, open-source benchmark, algorithm comparisons across private instance sets remain diﬃcult to interpret consistently. This paper introduces EOS-Bench, a comprehensive framework for the systematic and reproducible evaluation of scheduling algorithms. By integrating high-ﬁdelity orbital dynamics and diverse platform constraints, EOS-Bench generates 1,390 scenarios and 13,900 benchmark instances, ranging from small-scale exact-validation cases to large coordination tasks featuring 1,000 satellites and 10,000 requests. In addition, we introduce a scenario characterisation scheme that estimates scenario-level structural diﬃculty by aggregating instance-level descriptors describing feasible opportunity density, task ﬂexibility, pairwise conﬂict, and satellite-side congestion. We also propose a multidimensional protocol to evaluate solvers across ﬁve practical metrics: task proﬁt, completion rate, workload balance, timeliness, and runtime. We comprehensively evaluate the framework across both agile and non-agile scenarios using exact mixed-integer programming, constructive heuristics, meta-heuristics, and deep reinforcement learning. The reported results indicate that EOS-Bench can diﬀerentiate solver behaviour across scales and operating conditions, highlight practical trade-oﬀs between solution quality and runtime, and provide structural context for interpreting scenario diﬃculty. Taken together, these features make EOS-Bench a useful open testbed for future research on Earth observation satellite scheduling. The code and data are available at https://github.com/Ethan19YQ/EOS-Bench. Keywords: Earth observation satellites, Resource scheduling, Benchmark framework, Combinatorial optimisation, Deep reinforcement learning, Satellite constellation

1. Introduction Earth observation satellites (EOSs) play an essential role in a wide range of civil and strategic applications, including climate monitoring, disaster response, precision agriculture, environmental surveillance, and security-related missions [1]. As Earth observation systems expand from single platforms to large constellations, planners must allocate limited observation opportunities and onboard resources under orbital, temporal, and platform constraints [2, 3]. This leads to the Earth observation satellite scheduling problem (EOSSP), where, given a set of EOSs and a set of ground targets to be observed, imaging requests must be selected, allocated, and sequenced under constraints such as visibility, platform manoeuvrability, and onboard resources. The objective of EOSSP is typically to optimise performance metrics, for example by maximising the number of observed targets or minimising the total mission completion time. The EOSSP is therefore inherently combinatorial, computationally challenging, and are widely regarded as NP-hard [1, 4]. Consequently, over the past three decades, extensive research has been devoted to the modelling and solution of EOSSPs in settings ranging from single-satellite operations to multi-satellite constellations and integrated observation planning [5, 6].

Roll angle

Roll angle Orbit

Orbit

Pitch angle

Track of sub-satellite point

Swath Width

Yaw angle

(a) Non-agile satellite

(b) Agile satellite

Figure 1: Diﬀerences between non-agile and agile satellites. Non-agile satellites mainly observe near nadir, whereas agile satellites can actively manoeuvre to image more targets within a pass.

A central distinction in the EOSSP literature is between non-agile and agile observation platforms, as shown in Fig. 1. Non-agile satellites typically observe near nadir, with limited oﬀ-nadir pointing capability and comparatively stable viewing geometry. By contrast, agile satellites can actively manoeuvre about multiple attitude axes and revisit diﬀerent ground locations within a short time interval, thereby substantially enlarging the feasible observation set within a pass. This additional ﬂexibility improves mission responsiveness, but also makes the scheduling problem considerably harder because feasibility depends not only on visibility, but also on attitude transitions, time-dependent observation opportunities, and coupled resource usage. Non-agile and agile satellites therefore represent two related but distinct EOSSP settings, with the latter extending the former through greater pointing ﬂexibility and more complex operational constraints. Recent surveys [1, 5] show that EOSSP research spans this full spectrum, from simple single-satellite formulations to integrated constellation-level problems with proﬁts and multiple resource couplings. To solve these problems, researchers have developed a wide range of optimisation and learning-based methods. Exact approaches, especially mixed-integer programming (MIP) and decomposition-based methods, can provide optimal or near-optimal solutions for small and medium-sized instances, but their computational cost increases rapidly with constellation size, task density, and planning horizon. For larger operational settings, heuristic and meta-heuristic methods such as greedy construction, simulated annealing, tabu search, and large neighbourhood search are widely used [1]. He et al. [7] proposed an adaptive large neighbourhood search method for multi-satellite scheduling with time-dependent transition constraints. Furthermore, learning-based approaches, particularly deep reinforcement learning (DRL) and related neural decision models, have attracted increasing attention because they oﬀer the possibility of fast policy inference across diverse instances [8, 9]. However, despite the methodological diversity of the ﬁeld, most studies still evaluate their

methods on private or highly problem-speciﬁc instances1 . This lack of common evaluation standards makes it diﬃcult to determine whether reported performance diﬀerences are due to genuinely stronger algorithms or simply to diﬀerences in modelling assumptions, instance construction, and evaluation criteria [5]. This gap has motivated several recent benchmark-oriented eﬀorts. Rocha et al. [10] released benchmark instances for an integrated agile EOS scheduling model together with an MIP-based heuristic. Vasegaard and Larsen [11] introduced EOSpython, an open-source framework that connects instance generation with scheduling solvers. However, while it provides the construction methodology, it lacks speciﬁc benchmark instances and remains mainly oriented towards agile EOS imaging. Wang et al. [12] proposed AEOS-Bench, a high-ﬁdelity benchmark environment built on Basilisk simulation [13]. However, AEOS-Bench focuses primarily on simulation-driven environments tailored for reinforcement learning, lacking a general combinatorial representation and multidimensional evaluation suitable for a broader range of exact and meta-heuristic solvers. Another equally critical deﬁciency in current EOSSP benchmarking practice is the overreliance on nominal scenario descriptors. Most existing literature relies solely on the number of satellites, tasks, or planning-horizon length to deﬁne problem scale. Yet, these superﬁcial metrics fail to capture the intrinsic structural diﬃculty of an instance. Scenarios of identical nominal size may still diﬀer substantially in feasible opportunity density, task ﬂexibility, conﬂict intensity, and timeline congestion. Without explicitly characterising these underlying topological and temporal bottlenecks, algorithmic performance remains diﬃcult to interpret consistently across diﬀerent studies. In a nutshell, while these studies improve reproducibility within particular EOSSP settings, they still lack the comprehensive features necessary for a robust benchmarking ecosystem (see Table 1). Speciﬁcally, existing frameworks generally omit explicit scenario characterisation to quantify structural diﬃculty, lack a standardised multi-dimensional evaluation protocol, and fail to provide integrated results visualisation tools for intuitive schedule analysis. Therefore, the ﬁeld still lacks a uniﬁed benchmark framework that simultaneously supports agile and non-agile platforms, spans substantially diﬀerent constellation scales, and enables systematic comparison across fundamentally diﬀerent solver classes under a shared evaluation protocol. To address this gap, this paper introduces EOS-Bench, a uniﬁed benchmark framework for EOSSP. The aim of EOS-Bench is not to propose yet another scheduling algorithm, but to provide a common and reproducible experimental basis for evaluating optimisation-based, heuristic, meta-heuristic, and learning-based solvers. The framework generates parametrised benchmark scenarios along four principal dimensions: satellite platform (agile or non-agile), planning horizon, constellation conﬁguration, and mission load. Within this structure, it supports both agile and non-agile platforms under a common modelling architecture, while incorporating realistic orbital dynamics, visibility generation, attitude-related feasibility, and coupled energy/storage constraints. Since agile platforms introduce complex time-dependent transition constraints that represent the most computationally demanding regime of EOSSP, our detailed analysis in this 1 Throughout this paper, a Scenario refers to a speciﬁc benchmark setting deﬁned by a unique combination of structural parameters, whereas an Instance refers to a concrete realisation of a Scenario. Formal deﬁnitions are provided in Table 4.

Table 1: Comparison of EOS-Bench with existing EOSSP benchmarks. Feature Benchmark size Satellite scale Task scale Time horizon Agile EOS imaging Non-agile EOS imaging Evaluation protocol Results visualisation Scenario characterisation

EOSpython [11]

Rocha et al. [10]

AEOSBench [12]

EOS-Bench (Ours)

/ / / / ✓ × ✓ ✓ ×

32 1∼4 200∼800 24h∼72h ✓ × × × ×

192a 1∼50 50∼300 1h ✓ × ✓ × ×

13,900 1∼1000 10∼10000 1h∼168h ✓ ✓ ✓ ✓ ✓

The AEOS-Bench work involves a total of 16,410 instances: 16,218 are randomly generated for reinforcement learning training (with no detailed information for reproduction), and the remaining 192 serve as a benchmark. Note. “/” indicates that the corresponding information is not explicitly reported in the original reference.

paper deliberately focuses on a representative subset of these agile scenarios. Comprehensive results for both agile and non-agile platforms are fully provided in Appendix B. Beyond solver-oriented evaluation, EOS-Bench also provides scenario characterisation descriptors by aggregating instance-level structural indicators under each scenario, thereby supporting more interpretable comparisons across scenario families. Speciﬁcally, this paper makes four main contributions: • We develop an open-source and extensible benchmark framework that standardises the modelling and evaluation of Earth observation satellite scheduling. The framework integrates orbital dynamics, visibility generation, platform constraints, and task modelling within a uniﬁed architecture that supports both agile and non-agile platforms. • We construct a comprehensive benchmark library comprising 1,390 scenarios and 13,900 instances covering a broad range of operational settings. The scenarios are organised into: 1,104 Standard Scenarios associated with 11,040 instances, which systematically vary platform type, planning horizon, constellation size, and mission load; and 286 Speciﬁc Scenarios associated with 2,860 instances, which support controlled sensitivity analysis with respect to resource capacity, manoeuvrability, and constellation conﬁguration. • We introduce a scenario characterisation scheme in which scenario-level descriptors are estimated from instance-level structural indicators computed before optimisation. The proposed descriptors capture key properties such as feasible opportunity structure, task ﬂexibility, conﬂict intensity, and satellite-side congestion, thereby providing a structural context for more interpretable comparison of scheduling methods across scenario families. • We establish a multi-dimensional evaluation protocol based on ﬁve complementary metrics: task proﬁt, task completion rate, workload balance, timeliness, and runtime. By demonstrating the framework’s discriminative power through extensive baselines, this study enables a structured analysis of the scalability, bottleneck vulnerabilities, and practical trade-oﬀs of existing solution paradigms. 5

The remainder of this paper is organised as follows. Section 2 reviews existing work on EOSSP models, algorithms and relevant evaluation metrics, and benchmarking practices. Section 3 presents the benchmark framework, including the scenario space and the underlying models. Section 4 describes the generation process for both Standard and Speciﬁc Scenarios. Section 5 introduces structural descriptors used to characterise benchmark scenarios before optimisation. Section 6 establishes the uniﬁed evaluation protocol and details the speciﬁc performance metrics. Section 7 reports comparative experiments on exact, heuristic, meta-heuristic, and learning-based schedulers. Section 8 outlines potential directions for future benchmark development. Finally, Section 9 concludes the paper.

2. Literature Review This section reviews the literature on EOSSP from four interconnected perspectives. First, it outlines the main problem characteristics and introduces representative modelling variants, with a particular focus on platform agility and resource couplings. Second, it surveys the principal classes of solution approaches and algorithms, ranging from exact optimisation to meta-heuristics and learning-based methods. Third, it examines experimental settings and benchmarking practices in the existing literature, highlighting the fragmentation of current instance designs. Fourth, it discusses the evaluation protocols and metrics used to assess mission eﬀectiveness and computational performance. The section concludes by summarising the main observations that motivate the benchmark framework proposed in this paper. 2.1. Problem Modelling and Variants Earth observation satellite scheduling has long been studied in both the operations research and aerospace communities, and remains one of the most active application areas in satellite operations. At its core, the EOSSP concerns the selection, assignment, and sequencing of imaging tasks subject to visibility, temporal, platform, and resource constraints. Early studies already showed that these problems are computationally diﬃcult and widely considered as NPhard [5]. Furthermore, practical formulations often involve multiple competing objectives, such as coverage, proﬁt, fairness, and responsiveness [14]. Recent survey papers have helped clarify the breadth of this research area, showing that EOS scheduling has evolved from relatively simple single-satellite formulations to integrated multisatellite problems with complex dynamic elements [1, 5]. A central distinction in this evolution is between non-agile and agile observation platforms, a feature that also serves as a primary structural dimension in the proposed EOS-Bench. Non-agile satellites typically observe near nadir with comparatively stable viewing geometries. By contrast, agile satellites can actively manoeuvre about multiple attitude axes within a short time interval. While this ﬂexibility improves mission responsiveness, it makes the scheduling problem considerably harder. For agile platforms, the feasibility of consecutive observations depends strongly on attitude manoeuvres and the associated transition times. Liu et al. [15] and Peng et al. [16], for example, model timedependent slews between targets by using a piecewise linear function of the total angular change to estimate the transition time between observations. Peng et al. [17, 18] further incorporate

time-dependent task proﬁts, making the problem closely related to an orienteering model with time-dependent travel times and rewards. Beyond platform agility, other important modelling directions concern the deﬁnition of observation targets and environmental uncertainty. Many studies formulate EOS scheduling as an area-coverage problem over continuous geographic regions [19]. In contrast, studies involving highly agile constellations often discretise demand into point-target requests to manage geometric and combinatorial complexity. Although this approach frequently creates redundant target formulations, such redundancy can be eﬀectively managed using complex network theory [20]. Additionally, extensions have addressed uncertainty in the observation environment, such as cloud-cover stochasticity [21, 22], as well as explicit couplings between subsystems like attitude, energy, and onboard storage [23]. Overall, EOS scheduling models now span a wide spectrum, from compact point-target representations to highly integrated systems involving multiple coupled resources, directly motivating the need for a versatile benchmarking framework. 2.2. Algorithmic Solution Methods The increasing complexity of EOS scheduling models has led to the development of a wide range of solution methods. Exact approaches, particularly those based on mixed-integer programming and decomposition, remain important because they provide structural insight and high-quality baselines. Peng et al. [16, 18] develop exact and branch-and-price algorithms for agile satellites with time-dependent proﬁts and transition times, while Rigo et al. [24] apply branchand-price to nano-satellite task scheduling. Similarly, discrete-time and ﬁxed-interval mathematical models have been formulated to address multiple observations across multi-satellite systems [25]. For smaller missions, continuous-time and energy-aware models have also been proposed [26, 27]. Related work includes mixed open- and closed-loop planning models and stochastic models for constellation planning under cloud and weather uncertainty [21, 28]. These exact and related approaches can often produce optimal or near-optimal solutions for small- to medium-sized instances. However, their computational burden rises sharply with constellation size, task density, and planning horizon. In practical EOS settings, especially those involving large constellations or multi-day horizons, exact optimisation often becomes diﬃcult to apply within reasonable computational budgets. To address larger and more operationally demanding instances, many studies turn to heuristic and meta-heuristic methods. Adaptive large neighbourhood search is one of the most successful frameworks for agile EOS scheduling with time-dependent transition constraints [7, 29]. Other representative approaches include multi-objective local search [14], hybrid genetic and memetic algorithms for constellation and integrated scheduling [30, 31], divide-and-conquer ensembles combining meta-heuristics with exact subroutines [32], and decompose-and-learn strategies for large constellations [33]. Further work has explored distributed game-negotiation mechanisms [34], task-network aggregation strategies [35], and approaches tailored to emergency observation tasks [36]. More recently, quantum-inspired and quantum-enhanced meta-heuristics have also been investigated for agile EOS scheduling [37–41]. In parallel, learning-based methods, especially deep reinforcement learning (DRL), have become an increasingly active research direction. Early studies formulated EOS scheduling

as a Markov decision process and learned control policies for single satellites and small constellations [42, 43]. Subsequent work extended this idea to more complex settings, including multi-type observation scheduling [44] and hybrid actor–critic schemes for joint imaging decisions [45, 46]. More recent studies have considered DRL for rolling-horizon control [47], deep Q-learning combined with heuristic repair [48], two-stage scheduling architectures [49], and pretrained MDP models for online decision-making [50]. Learning-based methods have also been applied to time-sensitive constellation-level observation [51], multi-point imaging with spiking neural networks and proximal policy optimisation [52], and conﬂict-aware resource allocation in imaging missions [53, 54]. Overall, the EOSSP literature now contains a rich methodological spectrum, including exact optimisation, heuristics, meta-heuristics, learning-based, and quantum-based approaches. This diversity makes standardised evaluation increasingly important, because fair comparison across such diﬀerent solver classes is diﬃcult without shared scenario families and consistent performance metrics. 2.3. Performance Evaluation Metrics The evaluation of EOS scheduling methods typically relies on a combination of missionoriented and computational-performance metrics. Mission-oriented metrics assess how eﬀectively a schedule fulﬁls operational objectives, whereas computational metrics determine the practical viability of the underlying algorithm, particularly for large-scale deployments. Within mission-oriented evaluation, the most frequently reported metric is the total mission reward, typically deﬁned as the sum of task weights, priorities, or proﬁts [17, 18, 29]. Closely related measures include the absolute number of completed tasks and the overall completion ratio, which are especially prevalent in point-target scheduling [30, 55]. As mission models expand to encompass continuous areas or regions, coverage-speciﬁc metrics such as total covered area, mapping completeness, and regional workload balance become necessary [56–60]. Furthermore, in time-sensitive or dynamic contexts, response time, tracking continuity, revisit intervals, and service timeliness are often emphasized [61–63]. For environments characterised by uncertainty, evaluation criteria frequently shift towards expected mission value, success rates under cloud-cover stochasticity, or robustness against operational disturbances [22, 64, 65]. Finally, in integrated scheduling studies, indicators such as downlink completion, data latency, and memory utilisation are increasingly reported to capture end-to-end service eﬃciency [66, 67]. Alongside mission eﬀectiveness, computational-performance metrics are essential for assessing algorithm scalability. Runtime remains the standard benchmark, usually reported as wallclock time or average execution time across multiple instances [33, 57, 68]. For heuristic and meta-heuristic approaches, convergence speed and iteration eﬃciency provide additional algorithmic insights [29, 55]. In online or rolling-horizon applications, the ability to generate feasible decisions within strict decision cycles often supersedes the pursuit of global optimality [47, 69]. Moreover, because EOS scheduling is inherently multi-objective, relying on a single aggregated score is often inadequate. Consequently, there is a growing consensus that evaluation protocols should report multiple independent objective values, Pareto fronts, or dominance statistics, thereby making trade-oﬀs among reward, fairness, timeliness, and computational cost more transparent [31, 44, 70]. 8

To illustrate the fragmentation of current evaluation standards, Table 2 provides an illustrative summary of how representative EOS scheduling studies relate to the main evaluation dimensions considered in this paper. It shows that existing studies often emphasise diﬀerent subsets of performance criteria, and that the corresponding deﬁnitions are not always directly aligned. Table 2: Representative use of evaluation dimensions in the EOSSP literature. Reference Wu et al. [32] Qi et al. [33] Barkaoui and Berger [30] Li et al. [71] Ren et al. [72] Li et al. [73] Sun et al. [36] Li et al. [47] Liu et al. [51] Herrmann and Schaub [43] Stollenwerk et al. [37] EOS-Bench (Ours)

TP √ √ × × × √ × × × √ √ √

TCR √ × √ √

× √

× × × × × × √ √ √

× × √ √

× × √

× × × × × √

× × × × √

× × √

RT √ × × × × √ × × × √ √ √

Note. TP = Task Proﬁt; TCR = Task Completion Rate; BD = Balance Degree; TM = Timeliness; RT = Runtime.

In summary, while the community has developed a rich set of evaluation criteria to capture diverse operational and computational goals, the selective reporting of these metrics across diﬀerent studies heavily impedes direct algorithmic comparisons. A method that excels in total proﬁt might struggle with computational scalability or workload fairness, yet such trade-oﬀs remain hidden when studies report only a narrow subset of indicators. This highlights the critical need for a standardised, multi-dimensional evaluation protocol, such as the one proposed in this framework, that systematically and simultaneously assesses value, completion rate, fairness, timeliness, and runtime to provide a holistic and transparent view of solver performance. 2.4. Benchmarking and Experiments Despite the richness of the modelling and algorithmic literature, benchmarking practice in EOS scheduling remains uneven. Many studies evaluate their methods on bespoke instances designed for a particular problem formulation, platform type, or operational assumption. While such case-speciﬁc evaluation is often reasonable for demonstrating a new method, it makes comparison across papers diﬃcult. For example, Cho et al. [74] study optimisation-based methods for agile constellations over planning horizons of up to one week, whereas Barkaoui and Berger [30] consider a 12-hour horizon for a three-satellite constellation. Valicka et al. [21] examine 24-hour schedules under cloud uncertainty for one or two satellites, while Tharmarasa et al. [28] analyse mixed open- and closed-loop planning over a single day. Other studies focus on particular system architectures, such as multi-agent planning for multi-satellite systems [75, 76], autonomous goal-based onboard planning [77], or intelligent planning for distributed satellite systems [78]. Although some of these papers describe their experimental settings carefully, 9

reusable generators and public datasets remain relatively uncommon. As a consequence, many published test sets cannot readily serve as common benchmarks for the wider community. To better understand current experimental practice and to inform the design of EOS-Bench, we conduct a structured review of representative EOS scheduling studies. For each study, we record the planning horizon, the number of satellites, the platform type (agile or non-agile), and the mission scale. The resulting summary is presented in Table 3. A short horizon of 1–3 hours is often used in studies concerned with rolling or online decision-making for relatively small constellations and task sets. Medium horizons of 12–24 hours are the most common in the literature, and appear in both exact and meta-heuristic studies for agile and non-agile platforms, with problem sizes ranging from a single satellite to several tens of satellites and from a few tens to several thousand tasks. Longer horizons, such as 96 or 168 hours, are more often associated with higher-level constellation planning or large-scale mission-planning studies. Table 3: Representative experimental settings in the EOSSP literature. Period

Sats

Type

Tasks

Ref.

Period

Sats

Type

Tasks

Ref.

1h 1h 1.5h 1.5h 3h 3h 12h 12h 21h 24h 24h 24h 24h 24h 24h 24h 24h 24h 24h 24h

4∼7 7 1 1 10 1 3 3 10 3 3∼5 10 4 60 1 10 5 10 10 2∼10

non-agile non-agile agile non-agile agile agile non-agile non-agile non-agile non-agile non-agile non-agile agile non-agile agile non-agile non-agile non-agile non-agile non-agile

50∼400 50∼150 55∼60 25∼50 100∼250 50∼200 10∼60 10∼400 1500 100∼300 100∼1000 400∼1100 100∼200 1000∼3000 100∼600 400∼800 500 200∼1600 100∼5000 848

[32, 47] [15, 72] [23] [43] [80] [82] [30] [28] [78] [53] [44] [32, 33] [84] [32, 85] [87] [15, 32, 71] [50] [32] [15, 31] [75]

24h 24h 24h 24h 24h 24h 24h 96h 168h 168h / / / / / / / / /

1 6 4 1∼2 1 1 6 30 1∼3 12 1 1 1 5∼30 1 1 2 const. 2∼10 4∼6

agile agile agile non-agile agile agile agile non-agile non-agile non-agile non-agile non-agile non-agile non-agile agile agile non-agile non-agile agile

50∼300 300∼1000 150∼300 223∼520 100 50∼200 100∼2000 140 10∼700 1000 9∼24 5∼10 10∼25 500∼3000 100∼600 5∼10 2000 848 40∼1000

[49] [15, 79] [22] [21] [81] [15] [7] [83] [74] [10] [24] [26] [77] [86] [17] [88] [76] [75] [89]

Note. “/” in the Period column indicates that the scheduling horizon is not explicitly speciﬁed in the original reference. “Sats” denotes the number of satellites (Satellite Scale), and “Tasks” denotes the number of tasks (Mission Scale).

This review conﬁrms that there is still no common standard for instance design in EOS scheduling. Moreover, most studies report only nominal descriptors such as planning horizon, satellite count, and task volume, while providing little information about structural properties such as feasible opportunity sparsity, task ﬂexibility, pairwise conﬂict, or satellite-side congestion. As a result, two scenarios of similar nominal scale may still diﬀer substantially in intrinsic scheduling diﬃculty, which makes cross-study interpretation of algorithmic performance more diﬃcult. Even when studies use similar planning horizons, such as 24 hours, they may diﬀer substantially in constellation size, agility assumptions, resource models, and mission scale. The 10

diversity reﬂected in Table 3 illustrates both the breadth of the ﬁeld and the diﬃculty of making direct comparisons across published results. Many studies on large multi-satellite scenarios with thousands of tasks rely on advanced meta-heuristics or DRL, whereas exact and hybrid methods are typically evaluated only on small- and medium-scale instances. Although some recent work [10, 12] has begun to provide benchmark-style instance sets for speciﬁc integrated formulations, the literature still lacks a uniﬁed, open, and extensible benchmark framework that spans multiple EOSSP settings under a common evaluation protocol. 2.5. Summary The literature on EOSSP reveals ﬁve broad patterns. First, modelling has become progressively richer and closer to operational reality, with increasing attention to platform agility, time-dependent transition times, coupled resource constraints, and multi-satellite coordination [15–18]. Second, the range of solution approaches has expanded considerably, from exact mixed-integer optimisation and decomposition to meta-heuristics, DRL, imitation learning, and quantum-inspired methods [30, 32, 33]. Third, evaluation metrics vary signiﬁcantly depending on the speciﬁc study’s focus. The community employs a rich diversity of evaluation metrics, including total proﬁt, response time, and scalability. However, there remains a lack of standardised, multi-dimensional protocols capable of simultaneously assessing mission reward, completion rates, workload balance, timeliness, and computational eﬃciency across diﬀerent solver classes. Fourth, benchmarking practice remains fragmented: planning horizons, constellation scales, task volumes, and resource assumptions vary widely across studies, as illustrated in Table 3. Fifth, existing studies generally overlook the formal characterisation of intrinsic scenario diﬃculty. Most literature relies solely on nominal scale descriptors (such as the number of tasks or satellites), which fail to capture underlying structural bottlenecks like feasible opportunity sparsity, task ﬂexibility, pairwise conﬂict intensity, or satellite-side congestion. Consequently, algorithms are often evaluated without a clear understanding of why nominally similar instances can induce vastly diﬀerent computational challenges. This literature review on EOSSP therefore indicates that the main diﬃculty is no longer a lack of modelling ideas or algorithmic techniques, but rather the absence of a common experimental basis on which such methods can be compared systematically. This gap motivates the benchmark framework developed in this paper, which combines scenario-rich benchmark generation, structural scenario characterisation, and a multi-metric evaluation protocol for Earth observation satellite scheduling.

3. Benchmark Framework Design This section presents the benchmark framework underlying EOS-Bench, which is designed to support both agile and non-agile scenarios within a uniﬁed architecture. The section begins by deﬁning the scenario spacethe design domain encompassing planning horizons, constellation settings, mission loads, and related factors. It then describes the core modelling components: the satellite model, the task model, and the visibility module responsible for converting orbital motion and attitude constraints into feasible observation windows.

To facilitate reading, Table 4 summarises the principal terms used throughout this section, and Figure 2 provides a visual overview of the framework. Furthermore, the complete source code and examples of the main modules are available on GitHub (https://github. com/Ethan19YQ/EOS-Bench). Scenario Space Scenario Construction

[Sec. 3.1]

Benchmark Generation

Instantiate

(Parameters: Platform, Time, Constellation, Payload, Target Distribution)

[Sec. 4]

(Instances: Standard Scenarios, Specific Scenarios )

Configuration Paramenters Satellite [Sec. 3.2] Modelling

(Orbit, Platform, Payload, Attitude Transition)

Task [Sec. 3.3]

Visibility Analysis

(Distribution, Attributes)

[Sec. 3.4]

(Visibility Calculation, Access Window)

Benchmark Instances Task-Oriented

Scenario Characterisation

[Sec. 5.1]

(Task Perspective: Average available opportunities, Task interference ratio, etc.)

Algorithm Benchmarking

Satellite-Oriented [Sec. 5.2] (Satellite Perspective: Observation contention ratio, Timeline overload ratio, etc. )

[Sec. 7.1]

Baselines (Algorithm Pool: MIP, Greedy, GA/SA/ACO, DRL)

Algorithm-Agnostic Interface

Scheduling Plans Evaluation & Visualisation

Visualisation Engine [Sec. 7.4] (Spatiotemporal Visualisation Rendering)

Display

Multi-dimensional Protocol [Sec. 6] (Evaluation: TP, TCR, BD, TM, RT)

Figure 2: Modular architecture and end-to-end workﬂow of the EOS-Bench framework, from initial modelling to multi-dimensional evaluation. A key component is the pre-optimisation characterisation layer used to quantify intrinsic scenario diﬃculty. Abbreviations: MIP = Mixed Integer Programming, GA = Genetic Algorithm, SA = Simulated Annealing, ACO = Ant Colony Optimisation, DRL = Deep Reinforcement Learning, TP = Task Proﬁt, TCR = Task Completion Rate, BD = Balance Degree, TM = Timeliness, RT = Runtime.

3.1. Benchmark Scenario Space To provide a systematic testbed for algorithmic evaluation, EOS-Bench constructs a multidimensional scenario space. Rather than relying on isolated test cases, the framework systematically varies fundamental operational parameters to create a broad spectrum of scheduling environments. This parameterised design allows for the precise isolation of algorithmic performance drivers under increasing levels of structural complexity. For mathematical clarity, we write the benchmark scenario space as Σ = P × H × C × L × D × Z,

(1)

Table 4: Key terms and deﬁnitions used in the EOS-Bench framework. Term

Deﬁnition

Scenario space

The overall design domain of the benchmark, that is, the range of satellite platform types (agile or non-agile), planning horizons, constellation settings, mission loads, target distributions, and other conﬁgurable factors from which benchmark scenarios are constructed. A speciﬁc benchmark setting deﬁned by one unique combination of structural parameters, such as platform type, planning horizon, constellation setting, mission load, target distribution, and the relevant platform or environment settings. A concrete realisation of a scenario, obtained by selecting a speciﬁc target subset, random seed, or other stochastic variation while keeping the structural scenario parameters ﬁxed. A geographically referenced imaging request, deﬁned by its target location, required observation duration, priority, and proﬁt. A satellite that can actively slew about roll, pitch, and yaw so as to point substantially away from nadir, thereby enabling the observation of diﬀerent ground targets within a single pass [1, 5]. A satellite whose attitude is ﬁxed or only weakly manoeuvrable, so that the payload points at nadir or only slightly oﬀ nadir and observations are mainly made along the ground track [1, 5]. A family of benchmark scenarios that systematically vary planning horizon, number of satellites, and number of tasks in order to support broad comparison of algorithms across problem scales. A family of benchmark scenarios that vary one aspect of the system at a time (for example, resource capacity, manoeuvrability proﬁle, or constellation geometry) in order to study algorithm sensitivity and robustness.

Scenario

Instance

Task/Target Agile satellite

Non-agile satellite

Standard Scenarios

Speciﬁc Scenarios

where P is the set of satellite platform types, H is the set of planning horizons, C is the set of constellation conﬁgurations, L is the set of mission-load settings, D is the set of targetdistribution patterns, and Z collects any additional scenario-speciﬁc parameters used in the Speciﬁc Scenarios. A scenario is therefore one element σ = (p, h, c, ℓ, d, z) ∈ Σ.

(2)

Given a scenario σ and a random seed ξ, the instance generator produces one concrete benchmark instance ( ) I(σ, ξ) = S, T , W, h, Θsat , Θtask , (3) where S is the satellite set, T is the task/target set (note that the terms task and target are used interchangeably throughout the paper. ), W is the family of feasible access-window sets, and Θsat and Θtask collect the associated satellite-side and task-side parameters. This notation makes explicit that EOS-Bench is a distribution over structured scheduling instances rather than a single ﬁxed dataset. Speciﬁcally, along the temporal dimension (H), the benchmark includes short planning horizons of 1, 12, and 24 hours, as well as extended horizons of 72 hours and 7 days. Short

horizons approximate a rolling or online decision-making setting, restricting attention to local choices within a limited window, whereas longer horizons enable the examination of cumulative eﬀects, such as repeated resource usage and long-term schedule stability. Along the resource and mission dimensions (C and L), scenarios are grouped into three size classes. Small-scale scenarios involve 1–20 satellites and up to 1,000 tasks, serving as testbeds for exact or near-exact methods. Medium-scale scenarios feature 50–200 satellites and up to 2,000 tasks, representing moderately complex operational settings. Finally, large-scale scenarios encompass 500–1,000 satellites and 500–10,000 tasks, designed to evaluate scalability and push algorithms toward their computational limits. By systematically varying these elements, EOSBench forms a structured grid that supports comparisons across problem scales. 3.2. Satellite Modelling The satellite model provides a uniﬁed representation of orbital dynamics, platform kinematics, and payload behaviour across all benchmark scenarios. Its primary purpose is to deﬁne when a satellite can observe a ground target, which attitude manoeuvres are admissible, and how imaging activities consume onboard resources. Formally, to encapsulate these operational characteristics, EOS-Bench associates each satellite s ∈ S with a parameter tuple: ( ) θs = o s , a s , r s , q s ,

(4)

where os denotes the orbital description, as the admissible attitude envelope, rs the onboard resource capacities, and qs the payload-consumption parameters. The benchmark is solverneutral in the sense that these quantities are deﬁned independently of any optimisation or learning architecture and are supplied directly as instance data. 3.2.1. Orbital Information and Constellation Design The orbital component of EOS-Bench is generated using a hybrid strategy that combines real satellites for small-scale scenarios with synthetic Walker–Delta constellations for medium- and large-scale scenarios. This design balances physical realism with controlled coverage properties and repeatable large-scale experimentation. To instantiate the orbital component os deﬁned in Equation (4), EOS-Bench employs realworld satellite data for small-scale scenarios (i.e., conﬁgurations involving 1, 3, 5, 10, and 20 satellites). The raw data are sourced from the “Earth Resources” category on CelesTrak2 , which encompasses a diverse range of operational Earth observation platforms. For standardisation, these data are extracted as the six classical Keplerian elements at a uniﬁed reference epoch of 18 Nov 2025 12:00:00 UTC. The selected satellites and their speciﬁc Keplerian elements are detailed in Table 5, and their corresponding ground tracks are visualised in Figure 3. For medium- and large-scale scenarios, EOS-Bench constructs synthetic Walker–Delta constellations in order to provide controlled and repeatable global coverage. The real satellite 2

https://celestrak.org/NORAD/elements/

Table 5: Orbital elements of the real satellites. Satellite

Country

Semi-major Axis

Eccentricity

Inclination

RAAN

Arg of Perigee

True Anomaly

ALOS-2 AQUA CARTOSAT-2C DEIMOS-1 DEIMOS-2 GAOFEN_10R GOKTURK_1A GPM-CORE KENT_RIDGE_1 SCD_1 SCD_2 SKYSAT-C2 SKYSAT-C9 SMOS SRMSAT TERRASAR-X WORLDVIEW-1 YAOGAN_21 YAOGAN_4 ZIYUAN_3-2

Japan USA India Spain Spain China Turkey Japan Singapore Brazil Brazil USA USA ESA India Germany USA China China China

7013.62362 7054.608686 6885.388452 7026.003591 6955.196768 7004.506326 7061.790586 6801.857205 6884.956782 7121.14563 7123.258992 6833.433187 6825.950288 7129.70257 7236.742741 6877.192296 6874.558678 6866.60274 6993.513131 6866.915774

0.000898 0.002665 0.002331 0.001598 0.002894 0.002046 0.001387 0.001294 0.000964 0.003755 0.001882 0.00167 0.00325 0.000962 0.002142 0.000926 0.001374 0.003193 0.00264 0.002603

98.04 98.264 97.526 97.832 97.569 97.874 98.061 64.827 15.043 25.1 24.859 97.006 97.567 98.521 19.826 97.37 97.524 97.197 97.779 97.497

57.345 282.658 19.64 123.909 198.785 269.586 214.868 293.591 31.097 68.138 291.105 347.712 92.251 147.596 254.192 327.892 79.993 6.525 252.523 36.721

101.516 100.906 129.493 99.999 83.505 82.424 112.033 284.823 207.516 73.8 37.112 69.009 106.838 18.842 78.797 6.52 89.387 115.547 84.41 72.615

96.459 181.914 269.449 287.41 180.934 282.074 286.074 176.995 57.259 157.166 275.948 149.715 162.537 100.232 37.063 107.452 281.492 184.675 221.626 202.817

ALOS-2 in Table 5 is used as the seed orbit. ALOS-2 ﬂies in a sun-synchronous orbit that is representative of many modern Earth observation missions. To ensure realistic orbital topologies, the Walker pattern parameters, speciﬁcally the number of orbital planes, the number of satellites per plane, and the relative phasing, are purposefully structured to maintain a balanced spatial-temporal distribution of assets. Rather than arbitrarily populating orbits, these conﬁgurations scale the number of planes and satellites symmetrically. This design choice ensures that as the constellation grows, both the global revisit frequency (driven by orbital plane diversity) and the instantaneous observation capacity (driven by intra-plane density) improve proportionally, thereby accurately reﬂecting the architectural principles of contemporary and next-generation commercial EO mega-constellations. The speciﬁc Walker–Delta conﬁgurations, selected to generate constellations with progressively higher operational densities, are detailed in Table 6. Table 6: Synthetic Walker–Delta constellation conﬁgurations across medium and large scales.

Scale Category

Total Satellites

Orbital Planes

Satellites per Plane

Medium-scale

50 100 200

10 10 20

5 10 10

Large-scale

500 1000

25 50

20 20

Figure 3: Orbital ground tracks of the 20 real satellites. These ground tracks illustrate the orbital diversity of the real satellite set adopted for the small-scale benchmark scenarios.

All satellites in the benchmark constellations carry an optical imaging payload. The current release adopts this single payload type in order to maintain consistency across benchmark scales. At the same time, the framework retains a dedicated payload interface, allowing additional payload models, such as SAR, to be incorporated in future work without changing the rest of the benchmark structure. 3.2.2. Satellite Platform Model The satellite platform model details the admissible attitude envelope as deﬁned in Equation (4), accommodating both agile and non-agile conﬁgurations. In EOS-Bench, this envelope is parametrised by bounding limits on the roll, pitch, and yaw axes, which collectively determine the instantaneous ﬁeld of regard. For agile satellites, the model assumes a highly ﬂexible three-axis envelope. Based on representative values from the literature [1, 15, 17], EOS-Bench adopts the symmetric bounds summarised in Table 7. For non-agile satellites, rather than employing an ambiguous nadirdominant characterisation, the model explicitly parametrises them as roll-only manoeuvrable platforms. This means pitch and yaw capabilities are disabled (ﬁxed at 0◦ ), while the roll axis retains the bounds speciﬁed in Table 7 to enable standard cross-track targeting. Table 7: Satellite platform parametrisation. Default attitude-envelope parameters for representing satellite pointing capability in EOS-Bench.

Parameter Max roll angle Max pitch angle Max yaw angle

Default Value ◦

±45 ±45◦ ±90◦

Rationale Typical ﬁeld-of-regard for agile Earth observation satellites [1, 15] Symmetric along-track pointing envelope [17] Additional cross-track ﬂexibility for agile platforms [17]

3.2.3. Satellite Payload Model The payload model describes how imaging activities consume onboard resources. Following common practice in EOSSP [15, 17, 47, 49], EOS-Bench expresses energy and data budgets in normalised units rather than in physical joules or bits. For scheduling purposes, what matters is the relative scale between observation time, slewing eﬀort, and per-orbit resource limits, rather than the absolute physical values. The parameters adopted in the benchmark are listed in Table 8. Table 8: Payload and imaging parametrisation. Default resource-consumption and capacity parameters used to model imaging activities in EOS-Bench.

Parameter

Default Value

Rationale

Observation energy rate

1 unit/s

Observation memory rate Energy capacity per orbit

1 unit/s 200 units

Storage capacity per orbit

2400 units

Attitude manoeuvre energy rate

1 unit/deg

Normalised per-second energy draw in imaging mode [15, 49] Normalised data-acquisition rate [47] Normalised energy budget per orbit, consistent with per-orbit modelling in [15, 49] Normalised data buﬀer capacity, suﬃcient for multiple long observations [47] Linearised energy cost for slews, as in [15, 17]

3.2.4. Attitude Transition-Time Model For agile satellites, the time required to change the line-of-sight between two observations has a strong eﬀect on schedule feasibility. EOS-Bench adopts a piecewise linear transition-time function linking transition time to the total change in look angle, following the time-dependent models proposed by [15] and [16–18]. Let ∆g = |∆γ| + |∆π| + |∆ψ| denote the sum of the absolute changes in roll, pitch, and yaw angles between two imaging attitudes. The transition time is then deﬁned as   11.66,     ∆g   a + , 1   v1    ∆g T rans(∆g) = a2 + v2 ,   ∆g    , a3 +   v3    ∆g   a4 + , v4

∆g ≤ 10, 10 < ∆g ≤ 30, 30 < ∆g ≤ 60,

(5)

60 < ∆g ≤ 90, ∆g > 90,

Here v1 , . . . , v4 are angular velocities in degrees per second, and a1 , . . . , a4 are oﬀsets chosen so that T rans(∆g) is continuous and non-decreasing at the breakpoint angles. EOS-Bench uses the parameter values reported in [16–18], with v1 = 1.5◦ /s, v2 = 2.0◦ /s, v3 = 2.5◦ /s and v4 = 3.0◦ /s. The oﬀsets a1 , a2 , a3 , and a4 are set so that T rans(∆g) remains continuous at all

breakpoints. For two consecutive observations i and j with start times ti and tj , the required slew time is written as T ransi,j (ti , tj ), and is enforced in the scheduling model as a minimum time-gap constraint between the two tasks. This transition-time model is widely used in the agile EOSSP literature [5, 16–18], so adopting it here keeps the kinematic assumptions of EOS-Bench consistent with recent work. The model is intended as a benchmark-level approximation rather than as a full attitude-control simulation. Speciﬁcally, ∆g = |∆γ| + |∆π| + |∆ψ| provides a conservative axis-wise estimate of manoeuvre cost, and the transition is evaluated from a representative viewing geometry rather than from a continuously updated line of sight throughout the slew. These simpliﬁcations improve tractability for large-scale benchmark generation while retaining the main time-dependent features relevant to EOSSP. In contrast to the dynamic reorientation of agile platforms, non-agile satellites operate under much stricter kinematic constraints. As widely adopted in non-agile EOSSP literature (e.g., the operational constraints of platforms like SPOT-5) [4], continuous angle-dependent transition calculation is unnecessary. Consequently, EOS-Bench applies a ﬁxed transition time of 10 seconds between any two consecutive non-agile observations. This constant duration represents the standard hardware stabilisation delay required for instrument reset and minor cross-track mirror adjustments. 3.3. Task Modelling The task model is designed to reﬂect the diversity and time-dependent character of real Earth observation demand while retaining a problem structure compatible with most existing scheduling methods. In EOS-Bench, each task is represented as a point target together with an associated priority, proﬁt weight, and required observation duration. In the current release, EOS-Bench assumes an oﬄine setting in which all task information is available at the initial decision time t0 . Speciﬁcally, the full task set for a scenario is known in advance, including target location, proﬁt, priority, and required observation duration. Formally, for each task i ∈ T , we write τi = (zi , ρi , pi , di ),

(6)

where zi ∈ R2 is the geodetic target location, ρi is the priority level, pi is the task proﬁt, and di is the required continuous observation duration. At the benchmark level, EOS-Bench therefore treats task generation as the construction of a ﬁnite set T = {τ1 , . . . , τNT } together with the access-window family induced by the orbital and visibility models. In the EOSSP literature, a number of studies consider area-type requests such as regions or strips [2, 57]. These requests are often discretised into sets of point targets or small tiles for scheduling. For example, several agile-satellite studies sample representative points within polygons or along strips in order to approximate area requests [2, 88, 90]. Recent large-scale constellation studies follow the same principle and convert region demands into collections of point-like missions [46, 91]. However, to follow the point-target convention and for simplicity, the ﬁrst release of EOS-Bench focuses on point targets. As detailed in Section 8, future releases could

accommodate area and strip targets by generating suitable sets of point tasks, grouping related points into higher-level missions, or adopting set-covering formulations, without changing the core benchmark interfaces. 3.3.1. Task Distribution EOS-Bench uses three simple synthetic spatial distributions of targets in order to test algorithms under diﬀerent geographical demand patterns: • Global-Random: targets are sampled approximately uniformly over the Earth’s land surface. • Region-Clustered: targets are grouped within ﬁve broad continental regions (Asia, Europe, Africa, the Americas, and Oceania). • Hybrid: each task set combines some Global-Random targets with others drawn from the Region-Clustered pattern. For each distribution pattern, a pool of 10,000 candidate target locations is ﬁrst generated. This pool is then divided into 10 disjoint subsets, each containing 1,000 targets. For any given benchmark instance, the required number of tasks is drawn from one chosen subset. As a result, when the task count increases, the additional tasks come from the same subset, so the mission load changes while the spatial pattern remains comparable. In addition to these synthetic pools, EOS-Bench also includes a set of 1,000 real-world city targets. These cities comprise national capitals and ﬁrst-level administrative capitals. Their coordinates are obtained from the GeoNames geographical database3 . 3.3.2. Task Attributes Each observation task is described by a small set of attributes specifying its spatial location and relative importance. These attributes are summarised in Table 9. Table 9: Task attributes. Main attributes and their mathematical symbols used to deﬁne observation tasks τi in EOS-Bench.

Attribute Name

Symbol

Description and Values

Task ID Target Location Priority Proﬁt

i zi ρi pi

Observation Duration

Unique identiﬁer for the task. Geodetic latitude and longitude coordinates. Integer from 1 to 10, indicating task urgency. Integer from 1 to 10, indicating the value gained upon task completion. Random integer between 5 and 15 seconds, indicating the required continuous imaging time.

https://download.geonames.org/export/

Priority and proﬁt jointly deﬁne a multi-objective optimisation landscape, encouraging algorithms to trade oﬀ the service of urgent requests against the maximisation of total reward. Variation in observation duration introduces heterogeneity in resource consumption, since longer tasks consume more energy and storage and may reduce the number of tasks that can be accommodated within a given orbit. In a more detailed physical model, observation duration may depend on the satellite–task pair, because it is inﬂuenced by relative motion, viewing geometry, and the spatial extent of the target region. In the current release of EOS-Bench, however, observation duration is treated as a task-level attribute and generated randomly within a predeﬁned range. More detailed region-based and geometry-dependent duration models are left to future extensions. 3.4. Visibility Analysis Model The visibility module links constellation orbital dynamics to the spatio-temporal availability of ground targets, discretising continuous trajectories into valid access windows based on lineof-sight and FOV conditions. Following established models [92–94], EOS-Bench applies scalable geometric tests to generate candidate contacts, which are then ﬁltered against the attitude constraints of both agile and non-agile platforms. Currently, environmental uncertainty is not explicitly modelled. By excluding time-varying cloud cover and post-scheduling execution failures, access windows are generated under strictly deterministic assumptions. This ensures a standardised and reproducible baseline for algorithm evaluation, preserving the framework’s ﬂexibility to support stochastic extensions in the future. 3.4.1. Visibility Calculation Method The visibility module links the orbital trajectories of the constellation to the spatio-temporal availability of ground targets. Because orbit propagation is a mature technology, EOS-Bench relies on the standard SGP4 model to eﬃciently generate baseline satellite positions. For any given satellite–target pair, instantaneous visibility is determined by a binary predicate: χsi (t) = 1(LOSsi (t) ∧ FOVsi (t) ∧ ATTsi (t)) ,

(7)

where LOSsi (t) denotes line-of-sight feasibility, FOVsi (t) denotes payload ﬁeld-of-view feasibility, and ATTsi (t) denotes platform attitude feasibility. Crucially, ATTsi (t) explicitly reﬂects the speciﬁc kinematic constraints of either the agile or non-agile platforms deﬁned in Section 3.2.2. Consecutive visible epochs satisfying Equation (7) are merged into discrete access windows, which serve as the direct input for all downstream scheduling algorithms. While the standard SGP4 geometric engine provides a robust and reproducible default, the modular architecture of EOS-Bench allows users to seamlessly integrate advanced visibility accelerators [93–95] without altering the scenario structure or solver interfaces. 3.4.2. Access Window Representation For each satellite–target pair, the visibility module returns a set of access windows that serves as the standard input for all downstream scheduling algorithms in EOS-Bench. To accurately 20

capture the distinct kinematic capabilities of diﬀerent platforms, the data structure of these windows is tailored according to satellite agility, as detailed in Table 10. While core temporal and identiﬁcation attributes are shared across all platforms, the representation of pointing geometry diverges. For agile satellites, the window incorporates a discretetime dynamic attitude sequence. This high-resolution proﬁle is essential for scheduling algorithms to precisely evaluate the time-dependent reorientation costs between consecutive tasks. Conversely, the representation for non-agile platforms is strictly simpliﬁed to a single, ﬁxed roll angle, implicitly assuming that pitch and yaw remain locked at 0◦ throughout the entire observation. By relying on these transparent and standardised data structures, EOS-Bench ensures that the resulting benchmark instances remain solver-agnostic and computationally manageable for large-scale constellation studies. Table 10: Access-window attributes. Standardised data ﬁelds deﬁning observation opportunities for agile and non-agile platforms in EOS-Bench.

Attribute Name

Platform Type

Description and Values

Task ID Satellite ID Time Window

Both Both Both

Attitude Sequence

Agile Only

Fixed Roll Angle

Non-agile Only

Unique identiﬁer for the observation task. Identiﬁer of the satellite executing the task. [tstart , tend ], the continuous feasible observation period. A discrete-time sequence of (γ, π, ψ) triplets deﬁning the dynamic pointing proﬁle required to track the target. A single, constant roll value (γ ∗ ) for the entire observation, with pitch and yaw ﬁxed at 0◦ .

3.5. Formal Benchmark Speciﬁcation The benchmark can now be formalised at the level of feasible assignments, schedules, and evaluation maps. This formalisation is intentionally solver-agnostic: it does not prescribe a speciﬁc optimisation model, but instead deﬁnes the rigorous mathematical structure that any solver interacting with EOS-Bench must process. For a ﬁxed instance I = (S, T , W, h, Θsat , Θtask ), deﬁne the set of candidate observation assignments as A(I) = {(s, i, ℓ, t) : s ∈ S, i ∈ T , wsiℓ ∈ Wsi , t ∈ Fsiℓ } . (8) Each element a = (s, i, ℓ, t) ∈ A(I) represents the decision to execute task i on satellite s by starting within access window wsiℓ at time t. EOS-Bench does not assume that all such assignments are jointly executable. Instead, it induces a compatibility relation C(a, a′ ) ∈ {0, 1}, where C(a, a′ ) = 1 if assignments a and a′ can coexist without violating window overlap, minimum transition-time separation, or singlesatellite exclusivity. Furthermore, EOS-Bench induces instance-dependent resource-feasibility

maps, written abstractly as RE (X) ≤ BE ,

RM (X) ≤ BM ,

(9)

where RE and RM aggregate energy and memory consumption over the selected assignments X ⊆ A(I), and BE , BM denote the corresponding satellite capacity limits. A feasible schedule is therefore any subset X ⊆ A(I) that simultaneously satisﬁes pairwise compatibility, task uniqueness (each task is executed at most once), and satellite-side resource feasibility: ∀a, a′ ∈ X, a ̸= a′ =⇒ C(a, a′ ) = 1, (10) ∀i ∈ T ,

|{a = (s, j, ℓ, t) ∈ X : j = i}| ≤ 1,

RE (X) ≤ BE ,

RM (X) ≤ BM .

(11) (12)

This deﬁnition yields the feasible-set view F(I) = {X ⊆ A(I) : X satisﬁes (10)–(12)} ,

(13)

which is the central mathematical space presented by the benchmark to any downstream solver. Finally, EOS-Bench operates as an evaluation pipeline over a distribution of instances. Let PΣ denote a scenario distribution over Σ, let G be the instance generator, and let f be any solver mapping instances to feasible schedules. The benchmark evaluates f through [ ( )] E(f ; σ) = Eξ∼P (·|σ) m f (G(σ, ξ)) ,

(14)

where m(·) returns the vector of reported benchmark metrics. In practice, EOS-Bench approximates this expectation by averaging over a ﬁnite number of generated instances per scenario. This formulation clariﬁes that the benchmark is not merely a collection of handcrafted test cases, but an empirical protocol for estimating solver behaviour under controlled distributions of scheduling challenges. 3.6. Scope and Limitations of EOS-Bench While EOS-Bench is designed to provide a comprehensive and extensible benchmark for EOSSP, the current release reﬂects a set of deliberate modelling choices that deﬁne its scope. • Presentation focus on agile scheduling: Although EOS-Bench supports both agile and non-agile satellite conﬁgurations and extensive experiments were conducted for both, the detailed analysis presented in the main text focuses on agile scenarios due to space limitations. The complete non-agile experimental results are provided in the benchmark’s public repository. • Oﬄine and deterministic setting: The benchmark adopts an oﬄine scheduling formulation with deterministic access windows and known task parameters. It does not currently 22

model execution uncertainty, such as cloud cover, task failure, or onboard replanning, which are relevant in operational settings. • Simpliﬁed task representation: The current version focuses on point targets, enabling controlled evaluation across large scenario sets. More complex task types, such as area or strip imaging, are not explicitly modelled in this release. • Abstracted resource modelling: Energy and storage capacities are represented using normalized units rather than hardware-calibrated values. While this supports scalability and comparability across scenarios, it abstracts away mission-speciﬁc resource constraints. • Benchmark-level operational modelling: Attitude transition and resource consumption are modelled using simpliﬁed but representative approximations. The benchmark is not intended to serve as a high-ﬁdelity spacecraft simulator, but rather as a controlled environment for algorithm evaluation. • Limited environmental and sensing factors: The current release does not explicitly account for environmental factors such as weather conditions, lighting variability beyond geometric constraints, or sensor-speciﬁc characteristics. These aspects can inﬂuence real-world scheduling outcomes. • Selective reporting of empirical results: Although the released library covers both platform types and a comprehensive cross-platform experimental campaign was conducted, the main text discusses only a selected agile subset to ensure a focused narrative. Users interested in the full comparative assessment across both agile and non-agile platforms should refer to the supplementary data repository. Future extensions could further incorporate environmental uncertainty and heterogeneous constellations to strengthen external validity. These design choices are intentional to ensure tractability, reproducibility, and broad applicability of the benchmark. Future extensions of EOS-Bench can progressively incorporate richer task models, uncertainty, and additional operational constraints, which are discussed in Section 8.

4. Benchmark Generation EOS-Bench can be viewed as a two-stage map for benchmark generation. First, a structural scenario template σ ∈ Σ is ﬁxed. Second, independent seeds ξ1 , . . . , ξM are used to instantiate I (m) = G(σ, ξm ),

m = 1, . . . , M,

(15)

where G denotes the benchmark generator. The resulting instance family shares the same structural parameters and diﬀers only through the stochastic elements admitted by the template, such as target-subset selection or seed-dependent task sampling. Benchmark scenarios are constructed by combining the main modelling dimensions introduced in Section 3: satellite platform (agile or non-agile), the planning horizon, the constellation 23

and platform conﬁguration, and the task set. Each unique combination of these elements deﬁnes one benchmark scenario. From a given scenario, multiple instances can then be generated by varying the sampled target subset or the random seed used in task generation. To keep the benchmark library structured and interpretable, EOS-Bench divides scenarios into two groups and each scenario has generated 10 instances, as illustrated in Figure 4. Formally, we write Σ = Σstd ∪ Σspec ,

Σstd ∩ Σspec = ∅,

(16)

where Σstd denotes the Standard Scenario family and Σspec denotes the Speciﬁc Scenario family. Standard Scenarios provide the main benchmark grid for broad comparison across solver classes, whereas Speciﬁc Scenarios are designed to isolate the eﬀects of particular factors, including resource capacity, manoeuvrability, constellation geometry, and realistic target geography. In total, EOS-Bench contains 1,390 scenarios and 13,900 instances, comprising 1,104 Standard Scenarios (11,040 instances) and 286 Speciﬁc Scenarios (2,860 instances). EOS-Bench [ 1,390 Scenarios / 13,900 Instances ] Standard Scenarios (  ) [ 1,104 Scenarios / 11,040 Instances ]

Specific Scenarios (  spec) [ 286 Scenarios / 2,860 Instances ]

std

Resource Capacity Constellation Config

Satellite Platform Mission Load Planning Horizon Target Distribution

Manoeuvrability Realistic Target

Structural Template  A unique parameter combination

Random Seeds (  ) Target subsets sampling

Generator ( G ( ,  ) )

Generated Instance

I (1)

I (2)

I (3)

...

I (10)

Figure 4: Hierarchical organisation and generation mechanism of the EOS-Bench. It illustrates the mapping of combinatorial parameters to structural templates (σ), which are instantiated via a stochastic generator (G(σ, ξ)) to form the Standard and Speciﬁc scenario libraries.

4.1. Standard Scenarios The Standard Scenarios form the core of the benchmark library. They systematically vary four principal dimensions: platform type, planning horizon, constellation size, and mission load. Four planning horizons are considered, including 0.5, 1, 3, and 7 days. Ten constellation sizes are included, speciﬁcally 1, 3, 5, 10, 20, 50, 100, 200, 500, and 1000 satellites. For small constellations (1–20 satellites), the real satellites deﬁned in Section 3 are used. For medium- and large-scale constellations (50–1000 satellites), the default Walker–Delta architectures introduced in Section 3 are adopted. For each satellite count, several task-load levels are deﬁned in order to produce scenarios of increasing density. The admissible task counts are listed in Table 11. Each combination of planning horizon, satellite count, and task count deﬁnes one structural Standard Scenario. For each structural template, EOS-Bench distinguishes between agile and non-agile platform instantiations under the common framework introduced in Section 3. In the agile branch, the benchmark uses the standard agile attitude and transition model. In the non-agile branch, it uses the nadir-dominant non-agile observation model described in Section 3. Table 11: Mission-load levels used in Standard Scenario templates.

Satellite Count

Task Count

1 3 5 10 20 50 100 200 500 1000

10, 20, 30, 40, 50, 100 10, 50, 100, 200 50, 100, 200, 500 100, 200, 500, 1000 100, 200, 500, 1000 50, 100, 150, 200, 500 100, 300, 500, 1000, 2000 200, 500, 1000, 1500, 2000 500, 1000, 1500, 2000, 5000 1000, 2000, 5000, 10000

Table 11 contains 46 distinct combinations of satellite count and task count. Combined with the four planning horizons, this yields 184 structural scenario templates. When the three target-distribution patterns and the two platform types (agile and non-agile) are also taken into account, the benchmark comprises 1,104 Standard Scenarios in total. With 10 instances generated for each scenario, the Standard suite therefore contains 11,040 instances. Because each target pool is pre-generated and split into 10 disjoint subsets for each distribution pattern, multiple instances can be produced for the same Standard Scenario without altering its structural parameters. 4.2. Speciﬁc Scenarios Whereas the Standard Scenarios span a broad range of benchmark settings, they keep the main platform parameters at their nominal values. To vary these parameters in a controlled

manner, 286 Speciﬁc Scenarios are further designed to examine individual settings through targeted sensitivity analysis. EOS-Bench includes four families of Speciﬁc Scenarios: resourcecapacity variants, manoeuvrability proﬁles, constellation-conﬁguration variants, and realistictarget scenarios. Among them, the manoeuvrability-proﬁle family is speciﬁc to agile satellites. 4.2.1. Resource-Capacity Variants The resource-capacity scenarios examine how algorithmic performance changes under diﬀerent energy and storage budgets. This scenario family is deﬁned at the benchmark-library level for both agile and non-agile platforms under the same resource parametrisation. The baseline per-orbit energy and storage capacities are those given in Table 8. To keep the number of scenarios manageable while still providing a comprehensive evaluation across diﬀerent problem scales, four representative Standard Scenarios are selected as baseline conﬁgurations. As detailed in Table 12, these conﬁgurations capture a progressive scale from small-satellite clusters to massive constellations, all operating under a standard 24-hour planning horizon. Table 12: Baseline conﬁgurations for resource-capacity scenarios.

Scale Category

Satellite Count

Task Count

Planning Horizon

Small-Scale Small-Scale Medium-Scale Large-Scale

3 10 100 500

200 500 500 2000

24 hours 24 hours 24 hours 24 hours

For each of these three baseline scenarios, all six capacity patterns are systematically evaluated using the scaling proﬁles listed in Table 13. These include three homogeneous variants (Low-Capacity, Standard-Capacity, and High-Capacity) and three heterogeneous variants (Mixed-Capacity A–C). The Standard-Capacity setting coincides with the underlying Standard Scenario and is therefore not counted as an additional Speciﬁc Scenario. This yields 120 distinct resource-capacity scenarios and 1,200 instances in total (4 baseline settings × 5 capacity patterns × 3 target distributions × 2 platform types, with 10 instances per scenario). Table 13: Resource-capacity scenario conﬁgurations.

Pattern

Conﬁguration Name

Capacity Distribution

Homogeneous

Low-Capacity Standard-Capacity High-Capacity

All satellites: 50% energy and storage capacity All satellites: 100% energy and storage capacity (baseline) All satellites: 150% energy and storage capacity

Heterogeneous

Mixed-Capacity A Mixed-Capacity B Mixed-Capacity C

20% high-capacity, 60% standard-capacity, 20% low-capacity 25% high-capacity, 50% standard-capacity, 25% low-capacity 30% high-capacity, 40% standard-capacity, 30% low-capacity

These scenarios require algorithms to balance task selection, energy expenditure, and databuﬀer usage under both uniformly constrained ﬂeets and ﬂeets with mixed resource levels. 26

4.2.2. Manoeuvrability Proﬁles Satellite manoeuvrability determines how rapidly a platform can adjust its attitude between successive observations. In EOS-Bench, attitude changes are modelled by the piecewise linear transition-time function T rans(∆g) in Equation (5), which is widely used in agile Earth observation satellite scheduling studies with time-dependent transition times and proﬁts [15–18]. In this model, the transition time between two observations depends on the total change in look angle ∆g and on four angular velocities v1 , . . . , v4 , which describe the slew rate over diﬀerent angular ranges. Following [16–18], EOS-Bench ﬁxes the breakpoint angles at ∆g = 10◦ , 30◦ , 60◦ , 90◦ and uses a minimum transition time of 11.66 s for very small attitude changes. The constant terms in Equation (5) are ﬁxed at a1 = 5, a2 = 10, a3 = 16, and a4 = 22. These values correspond to the reference agile optical satellite adopted in [16–18] and give a continuous, monotonically non-decreasing transition-time curve under the standard parameter setting. To examine the eﬀect of agility on scheduling performance, EOS-Bench deﬁnes four manoeuvrability proﬁles by scaling the angular velocities v1 , . . . , v4 within the ranges reported for agile satellites in [15–18]. The breakpoint angles and constants ak in Equation (5) are kept unchanged across all proﬁles, so that the proﬁles share the same basic functional form and minimum transition time, but diﬀer in their eﬀective slew rates. The resulting velocity values are listed in Table 14. Table 14: Manoeuvrability proﬁles and their angular-velocity settings.

Proﬁle

v1 (ř/s)

v2 (ř/s)

v3 (ř/s)

v4 (ř/s)

High-Agility Standard-Agility Low-Agility Limited-Agility

3.00 1.50 0.75 0.50

4.00 2.00 1.00 0.67

5.00 2.50 1.25 0.83

6.00 3.00 1.50 1.00

For the agile Standard Scenarios, EOS-Bench uses the Standard-Agility proﬁle. The nonagile Standard Scenarios use the corresponding non-agile platform model deﬁned in Section 3. For the manoeuvrability-speciﬁc analysis, EOS-Bench again utilises the four representative baseline conﬁgurations established in the resource-capacity study (as detailed previously in Table 12). For each baseline conﬁguration, all four manoeuvrability proﬁles (High-Agility, StandardAgility, Low-Agility, and Limited-Agility) are systematically evaluated. This yields 36 distinct manoeuvrability-speciﬁc scenarios and 360 instances in total (4 baseline settings × 3 new manoeuvrability proﬁles × 3 target distributions, with 10 instances per scenario). Because the constants ak are ﬁxed and only the angular velocities vk are varied, the relative ordering of transition times across proﬁles is preserved: more agile proﬁles always produce shorter transition times for a given ∆g, whereas less agile proﬁles produce longer ones. This design provides a controlled setting in which to test the sensitivity of scheduling methods to satellite agility.

4.2.3. Constellation-Conﬁguration Variants This scenario family can be instantiated under either satellite platform type, since it changes orbital layout rather than the underlying observation model. The constellation-conﬁguration scenarios examine how diﬀerent orbital layouts aﬀect scheduling performance when the total number of satellites is held ﬁxed. All constellations follow Walker–Delta patterns and retain the seed orbit of ALOS-2, including altitude and inclination, so that the benchmark varies only the number of planes and the number of satellites per plane. Five medium- and large-scale satellite counts are considered in this study: 50, 100, 200, 500, and 1000 satellites. For each scale, three constellation architectures are deﬁned: the Default pattern (identical to the baseline used in the Standard Scenarios), the Few-Planes pattern (fewer planes with more satellites per plane), and the Many-Planes pattern (more planes with fewer satellites per plane). The corresponding Walker–Delta conﬁgurations and their assigned task loads are listed in Table 15. For each scale, the Default pattern coincides with the conﬁguration already used in the Standard Scenarios, so the constellation-conﬁguration study focuses on comparing it against the Few-Planes and Many-Planes alternatives. Table 15: Walker–Delta constellation conﬁgurations and task loads for constellation-conﬁguration scenarios.

Satellite Count

Task Count

Conﬁguration

Walker–Delta Pattern (planes × sats/plane)

100, 200