IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v27y2024i5d10.1007_s10951-024-00816-x.html
   My bibliography  Save this article

Scheduling of Earth observing satellites using distributed constraint optimization

Author

Listed:
  • Shai Krigman

    (Ariel University)

  • Tal Grinshpoun

    (Ariel University)

  • Lihi Dery

    (Ariel University)

Abstract

Earth observation satellites (EOS) are satellites equipped with optical sensors that orbit the Earth to take photographs of particular areas at the request of users. With the development of space technology, the number of satellites has increased continuously. Yet still, the number of satellites cannot meet the explosive growth of applications. Thus, scheduling solutions are required to satisfy requests and obtain high observation efficiency. While the literature on multi-satellite scheduling is rich, most solutions are centralized algorithms. However, due to their cost, EOS systems are often co-funded by several agents (e.g., countries, companies, or research institutes). Central solutions require that these agents share their requests for observations with others. To date, there has yet to be a solution for EOS scheduling that protects the private information of the interested parties. In this study, we model the EOS scheduling problem as a distributed constraint optimization problem (DCOP). This modeling enables the generation of timetables for the satellites in a distributed manner without a priori sharing users’ private information with some central authority. For solving the resulting DCOP, we use and compare the results of two different local search algorithms—Distributed Stochastic Algorithm and Maximum Gain Message—which are known to produce efficient solutions in a timely manner. The modeling and solving of the resulting DCOP constitute our new solution method, which we term Distributed Satellite Timetable Solver (DSTS). Experimental evaluation reveals that the DSTS method provides solutions of higher quality than a commonly used centralized greedy algorithm and is comparable to an additional centralized algorithm that we propose.

Suggested Citation

  • Shai Krigman & Tal Grinshpoun & Lihi Dery, 2024. "Scheduling of Earth observing satellites using distributed constraint optimization," Journal of Scheduling, Springer, vol. 27(5), pages 507-524, October.
  • Handle: RePEc:spr:jsched:v:27:y:2024:i:5:d:10.1007_s10951-024-00816-x
    DOI: 10.1007/s10951-024-00816-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-024-00816-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10951-024-00816-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
    2. Rigo, Cezar Antônio & Seman, Laio Oriel & Camponogara, Eduardo & Morsch Filho, Edemar & Bezerra, Eduardo Augusto & Munari, Pedro, 2022. "A branch-and-price algorithm for nanosatellite task scheduling to improve mission quality-of-service," European Journal of Operational Research, Elsevier, vol. 303(1), pages 168-183.
    3. Djamal Habet & Michel Vasquez & Yannick Vimont, 2010. "Bounding the optimum for the problem of scheduling the photographs of an Agile Earth Observing Satellite," Computational Optimization and Applications, Springer, vol. 47(2), pages 307-333, October.
    4. Pei Wang & Gerhard Reinelt, 2011. "Solving the Earth Observing Satellite Constellation Scheduling Problem by Branch-and-Price," Operations Research Proceedings, in: Bo Hu & Karl Morasch & Stefan Pickl & Markus Siegle (ed.), Operations Research Proceedings 2010, pages 491-496, Springer.
    5. Virginie Gabrel & Alain Moulet & Cécile Murat & Vangelis Paschos, 1997. "A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts," Annals of Operations Research, Springer, vol. 69(0), pages 115-134, January.
    6. Daniel Karapetyan & Snezana Mitrovic-Minic & Krishna T. Malladi & Abraham P. Punnen, 2015. "The Satellite Downlink Scheduling Problem: A Case Study of RADARSAT-2," International Series in Operations Research & Management Science, in: Katta G. Murty (ed.), Case Studies in Operations Research, edition 127, chapter 21, pages 497-516, Springer.
    7. Bianchessi, Nicola & Cordeau, Jean-Francois & Desrosiers, Jacques & Laporte, Gilbert & Raymond, Vincent, 2007. "A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites," European Journal of Operational Research, Elsevier, vol. 177(2), pages 750-762, March.
    8. William J. Wolfe & Stephen E. Sorensen, 2000. "Three Scheduling Algorithms Applied to the Earth Observing Systems Domain," Management Science, INFORMS, vol. 46(1), pages 148-166, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jang, Jinbong & Choi, Jiwoong & Bae, Hee-Jin & Choi, In-Chan, 2013. "Image collection planning for KOrea Multi-Purpose SATellite-2," European Journal of Operational Research, Elsevier, vol. 230(1), pages 190-199.
    2. Zhang Ye & Hu Xiaoxuan & Zhu Waiming & Jin Peng, 2018. "Solving the Observing and Downloading Integrated Scheduling Problem of Earth Observation Satellite with a Quantum Genetic Algorithm," Journal of Systems Science and Information, De Gruyter, vol. 6(5), pages 399-420, October.
    3. Chen, Xiaoyu & Reinelt, Gerhard & Dai, Guangming & Spitz, Andreas, 2019. "A mixed integer linear programming model for multi-satellite scheduling," European Journal of Operational Research, Elsevier, vol. 275(2), pages 694-707.
    4. Wang, Xin-Wei & Chen, Zhen & Han, Chao, 2016. "Scheduling for single agile satellite, redundant targets problem using complex networks theory," Chaos, Solitons & Fractals, Elsevier, vol. 83(C), pages 125-132.
    5. Philippe Monmousseau, 2021. "Scheduling of a Constellation of Satellites: Creating a Mixed-Integer Linear Model," Journal of Optimization Theory and Applications, Springer, vol. 191(2), pages 846-873, December.
    6. Tangpattanakul, Panwadee & Jozefowiez, Nicolas & Lopez, Pierre, 2015. "A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite," European Journal of Operational Research, Elsevier, vol. 245(2), pages 542-554.
    7. Karapetyan, Daniel & Mitrovic Minic, Snezana & Malladi, Krishna T. & Punnen, Abraham P., 2015. "Satellite downlink scheduling problem: A case study," Omega, Elsevier, vol. 53(C), pages 115-123.
    8. Jie Chun & Wenyuan Yang & Xiaolu Liu & Guohua Wu & Lei He & Lining Xing, 2023. "Deep Reinforcement Learning for the Agile Earth Observation Satellite Scheduling Problem," Mathematics, MDPI, vol. 11(19), pages 1-20, September.
    9. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Kidney Exchange," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 119(2), pages 457-488.
    10. Felix Brandt & Patrick Lederer & René Romen, 2024. "Relaxed notions of Condorcet-consistency and efficiency for strategyproof social decision schemes," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 63(1), pages 19-55, August.
    11. Zhiwei Cui & Yan-An Hwang, 2017. "House exchange and residential segregation in networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(1), pages 125-147, March.
    12. Ivan Balbuzanov & Maciej H. Kotowski, 2019. "Endowments, Exclusion, and Exchange," Econometrica, Econometric Society, vol. 87(5), pages 1663-1692, September.
    13. Takamiya, Koji, 2001. "Coalition strategy-proofness and monotonicity in Shapley-Scarf housing markets," Mathematical Social Sciences, Elsevier, vol. 41(2), pages 201-213, March.
    14. Kóczy Á., László, 2009. "Központi felvételi rendszerek. Taktikázás és stabilitás [Central admission systems. Stratagems and stability]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(5), pages 422-442.
    15. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    16. Lars Ehlers & Bettina Klaus, 2003. "Probabilistic assignments of identical indivisible objects and uniform probabilistic rules," Review of Economic Design, Springer;Society for Economic Design, vol. 8(3), pages 249-268, October.
    17. Mahalec, Vladimir & Chen, Yingwu & Liu, Xiaolu & He, Renjie & Sun, Kai, 2015. "Reconfiguration of satellite orbit for cooperative observation using variable-size multi-objective differential evolutionAuthor-Name: Chen, Yingguo," European Journal of Operational Research, Elsevier, vol. 242(1), pages 10-20.
    18. Bogomolnaia, Anna & Moulin, Herve, 2015. "Size versus fairness in the assignment problem," Games and Economic Behavior, Elsevier, vol. 90(C), pages 119-127.
    19. Sonmez, Tayfun & Utku Unver, M., 2005. "House allocation with existing tenants: an equivalence," Games and Economic Behavior, Elsevier, vol. 52(1), pages 153-185, July.
    20. Korpela, Ville & Lombardi, Michele & Saulle, Riccardo D., 2024. "Designing rotation programs: Limits and possibilities," Games and Economic Behavior, Elsevier, vol. 143(C), pages 77-102.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jsched:v:27:y:2024:i:5:d:10.1007_s10951-024-00816-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.