Maximum Independent Set Satellite Scheduling World Cities Data Set

Satellite Scheduling World Cities Data Set

The Satellite Scheduling World Cities Data Set is the a set of cities treated as point locations used to simulate a set of image collection tasking requests for AIAA paper "A Maximum Independent Set Method for Scheduling Earth-Observing Satellite Constellations". It provides an open reference and benchmark for the satellite task scheduling problem. This could also be considered as a sparse Maximum Independent Set problem for a generic graph. The requests represent point collects, from which we can compute multiple distinct collection opportunities. The tasking problem is then to select a subset of these collects that it is possible for the spacecraft to feasibly collect in a given time period, subject to constraints on the spacecraft's agility and constraints on only collecting a single collect per request (no duplication of effort).The data set is hosted on both Github and Zenodo. The Github repository contains the original source data, the associated requests generated from the source data, and scripts to reproduce the scenario files. Zenodo (DOI 10.5281/zenodo) hosts copies of the output Metis graph files and collect data files. Due to the large size of produced files these are not included in the Github repository.

Notes

NotesPlease note that while the source data and generation methods are identical to the satellite task planning paper it was created for. The specific generated problems do not exactly reproduce the scenario in the paper. Since the original reproduction, updates in upstream software dependencies have changed the output of the generation process (specifically, Earth orientaiton parameter handling libraries). This can be determined by considering the cardinality of the generated collect set. However, these differences are generally small and since the constriant rate is similar, the results should be comparable.

Spacecraft Count
Orignial Publication Collect Count
Reproduction Collect Count

4
59356
59624

6
90777
91204

12
180008
180939

24
359170
361519

This repository also adds additional scenarios for 1, 2, and 36 satellites. Note, the provided scenarios represent the largest 10,000 request data set. Should a smaller request set be desired, the requests should be filtered to the top `x` request based on city population and any collects not associated with those requests should be discarded.

Note the Zenodo repository excludes the collect and graph files for the 1 and 2 satellite scenarios to avoid the file limits. These can still be reproduced from the Github source code.

Acknolwedgement

If this data set is used in your research, please cite the following paper

A Maximum Independent Set Method for Scheduling Earth-Observing Satellite Constellations

@article{eddy2021maximum,
title={A Maximum Independent Set Method for Scheduling Earth-Observing Satellite Constellations},
author={Eddy, Duncan and Kochenderfer, Mykel J},
journal={Journal of Spacecraft and Rockets},
volume={58},
number={5},
pages={1416--1429},
year={2021},
publisher={American Institute of Aeronautics and Astronautics}
}

Licensing

The source of the world cities data is from the simplemaps.com website,licensed under the Creative Commons Attribution 4.0 International License with the specific license found at `./data/worldcities_license.txt`.