A Large Language Model-based Multi-Agent Framework to Autonomously Design Algorithms for Earth Observation Satellite Scheduling Problem

Jiawei Chen , Yingguo Chen , Duc Truong Pham , Yanjie Song , Jian Wu , Lining Xing , Yingwu Chen

Engineering ››

PDF (4887KB)
Engineering ›› DOI: 10.1016/j.eng.2025.10.027
Research
research-article
A Large Language Model-based Multi-Agent Framework to Autonomously Design Algorithms for Earth Observation Satellite Scheduling Problem
Author information +
History +
PDF (4887KB)

Abstract

The Earth observation satellite scheduling problem (EOSSP) is a complex optimization problem involving the selection, sequencing, and timing of observational tasks to maximize task completion rates while adhering to various constraints. However, effectively solving diverse scheduling scenarios with varying characteristics through manual design and modification of algorithm configurations is a laborious task. Concurrently, with the advent of large language models (LLMs), numerous studies have leveraged related technologies to facilitate automatic algorithm deisgn (AAD), thereby alleviating the burdensome task of crafting optimization algorithms. However, these studies primarily concentrated on traditional optimization problems, whereas the EOSSP constitutes a more intricate problem necessitating precise articulation in specialized language and comprehensive elucidation. Moreover, previous research has achieved AAD by depending on the initially defined algorithms and proposing sophisticated, detailed iterative frameworks, thereby still requiring expertise in algorithm design. In this paper, we introduce an LLM-based multi-agent framework AgentAD that automatically generates efficient algorithms for EOSSP—transforming problem descriptions in natural language into executable algorithmic code. Within this framework, the proposed agents collaborate through numerous atomic interactions, completing subtasks in each defined workflow phase. Mirroring human behavior in software development processes, these agents join forces to craft effective algorithms tailored to EOSSP scenarios. The experimental results demonstrate that the algorithms generated by AgentAD outperformed other state-of-the-art human-designed counterparts.

Keywords

Large language models / Automatic algorithm design / Earth Observation Satellite Scheduling / Multi-Agent Framework

Cite this article

Download citation ▾
Jiawei Chen, Yingguo Chen, Duc Truong Pham, Yanjie Song, Jian Wu, Lining Xing, Yingwu Chen. A Large Language Model-based Multi-Agent Framework to Autonomously Design Algorithms for Earth Observation Satellite Scheduling Problem. Engineering DOI:10.1016/j.eng.2025.10.027

登录浏览全文

4963

注册一个新账户 忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]

X. Wang, G. Wu, L. Xing, W. Pedrycz. Agile earth observation satellite scheduling over 20 years: formulations, methods, and future directions. IEEE Syst J, 15 (3) (2021), pp. 3881-3892.
[2]

K.J. Zhu, J.F. Li, H.X. Baoyin. Satellite scheduling considering maximum observation coverage time and minimum orbital transfer fuel cost. Acta Astronaut, 66 (1-2) (2010), pp. 220-229.
[3]

D.H. Cho, J.H. Kim, H.L. Choi, J. Ahn. Optimization-based scheduling method for agile earth-observing satellite constellation. J Aerosp Inf Syst, 15 (11) (2018), pp. 611-626.
[4]

J. Wu, J. Zhang, J. Yang, L. Xing. Research on task priority model and algorithm for satellite scheduling problem. IEEE Access, 7 (2019), pp. 103031-103046.
[5]

R. Xu, H. Chen, X. Liang, H. Wang. Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization. Expert Syst Appl, 51 (2016), pp. 195-206.
[6]

F. Xhafa, J. Sun, A. Barolli, A. Biberaj, L. Barolli. Genetic algorithms for satellite scheduling problems. Mob Inf Syst, 8 (4) (2012), pp. 351-377.
[7]

G. Wu, H. Wang, W. Pedrycz, H. Li, L. Wang. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy. Comput Ind Eng, 113 (2017), pp. 576-588.
[8]

Z. Zhang, N. Zhang, Z. Feng. Multi-satellite control resource scheduling based on ant colony optimization. Expert Syst Appl, 41 (6) (2014), pp. 2816-2823.
[9]

X. Chen, G. Reinelt, G. Dai, A. Spitz. A mixed integer linear programming model for multi-satellite scheduling. Eur J Oper Res, 275 (2) (2019), pp. 694-707.
[10]

Y. He, L. Xing, Y. Chen, W. Pedrycz, L. Wang, G. Wu. A generic markov decision process model and reinforcement learning method for scheduling agile earth observation satellites. IEEE Trans Syst Man Cybern Syst, 52 (3) (2022), pp. 1463-1474.
[11]

J. Chen, M. Chen, J. Wen, L. He, X. Liu. A heuristic construction neural network method for the time-dependent agile earth observation satellite scheduling problem. Mathematics, 10 (19) (2022), p. 3498.
[12]

K. Tang, X. Yao. Learn to optimize-a brief overview. Natl Sci Rev, 11 (8) (2024), Article nwae132.
[13]

X. Zhai, X. Chu, C.S. Chai, M.S.Y. Jong, A. Istenic, M. Spector, et al. A review of artificial intelligence (AI) in education from 2010 to 2020. Complexity, 2021 (1) (2021), Article 8812542.
[14]

J. Yang, C. Wang, B. Jiang, H. Song, Q. Meng. Visual perception enabled industry intelligence: state of the art, challenges and prospects. IEEE Trans Industr Inform, 17 (3) (2020), pp. 2204-2219.
[15]

Dwivedi AK, Virmani D, Ramasamy A, Acharjee PB, Tiwari M. Modelling and analysis of artificial intelligence approaches in enhancing the speech recognition for effective multi-functional machine learning platform-a multi regression modelling approach. J Eng Res 2011;ICMET Special Issue:1-19.
[16]

M. Stone, E. Aravopoulou, Y. Ekinci, G. Evans, M. Hobbs, A. Labib, et al. Artificial intelligence (AI) in strategic marketing decision-making: a research agenda. Bottom line, 33 (2) (2020), pp. 183-200.
[17]

Campbell BA, Treude C. NLP2Code:code snippet content assist via natural language tasks. In: Proceedings of the 2017 IEEE International Conference on Software Maintenance and Evolution (ICSME); Shanghai, China. New York City: IEEE; 2017. p. 628-32.
[18]

E. Kasneci, K. Seßler, S. Kchemann, M. Bannert, D. Dementieva, F. Fischer, et al. ChatGPT for good? On opportunities and challenges of large language models for education. Learn Individ Differ, 103 (2023), Article 102274.
[19]

G. Luo. A review of automatic selection methods for machine learning algorithms and hyper-parameter values. Netw Model Anal Health Inform Bioinform, 5 (1) (2016), p. 18.
[20]

B. Jonsson, M. Norqvist, Y. Liljekvist, J. Lithner. Learning mathematics through algorithmic and creative reasoning. J Math Behav, 36 (2014), pp. 20-32.
[21]

B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M.P. Kumar, E. Dupont, et al. Mathematical discoveries from program search with large language models. Nature, 625 (7995) (2024), pp. 468-475.
[22]

Liu F, Xialiang T, Yuan M, Lin X, Luo F, Wang Z, et al. Evolution of heuristics:towards efficient automatic algorithm design using large language model. In: Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J. Proceedings of the 41st International Conference on Machine Learning; 2024 Jul 21-27; Vienna, Austria. Norfolk: JMLR.org;2024. p. 1-23.
[23]

Ye H, Wang J, Cao Z, Berto F, Hua C, Kim H, et al. ReEvo: large language models as hyper-heuristics with reflective evolution. arXiv:2402.01145.
[24]

Li Q, Zhang L, Mak-Hau V. Synthesizing mixed-integer linear programming models from natural language descriptions. arXiv:2311.15271.
[25]

J. Li, J. Zhu, D. Xu, J. Wang, Z. Li, K. Zhang. Earth observation satellite scheduling with interval-varying profits. IEEE Trans Aerosp Electron Syst, 60 (6) (2024), pp. 8273-8288.
[26]

Liu F, Tong X, Yuan M, Zhang Q. Algorithm evolution using large language model. arXiv:2311.15249.
[27]

L. Wang, C. Ma, X. Feng, Z. Zhang, H. Yang, J. Zhang, et al. A survey on large language model based autonomous agents. Front Comput Sci, 18 (6) (2024), Article 186345.
[28]

Galán-Vioque J, Vázquez R, Carrizosa E, Vera C, Perea F, Martín F. Towards a visual tool for swath acquisition planning in multiple-mission EOSs. In:Proceedings of the 7th International Workshop on Planning and Scheduling for Space (IWPSS 2011); 2011 Jun 8-10; Darmstadt, Germany. Hoboken: John Wiley & Sons; 2011. p. 1-8.
[29]

F. Perea, R. Vázquez, J. Galán-Viogue. Swath-acquisition planning in multiple-satellite missions: an exact and heuristic approach. IEEE Trans Aerosp Electron Syst, 51 (3) (2015), pp. 1717-1725.
[30]

A. Chatterjee, R. Tharmarasa. Multi-stage optimization framework of satellite scheduling for large areas of interest. Adv Space Res, 73 (3) (2024), pp. 2024-2039.
[31]

X. Liu, G. Laporte, Y. Chen, R. He. An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Comput Oper Res, 86 (2017), pp. 41-53.
[32]

Globus A, Crawford J, Lohn J, Morris R. Scheduling earth observing fleets using evolutionary algorithms:problem description and approach. In:Proceedings of the 3rd International NASA Workshop on Planning & Scheduling for Space 2002; 2002 Oct 27-29; Houston, TX, USA. Mountain View: NASA Ames Research Center; 2002.
[33]

J. Wu, B. Song, G. Zhang, J. Ou, Y. Chen, F. Yao, et al. A data-driven improved genetic algorithm for agile earth observation satellite scheduling with time-dependent transition time. Comput Ind Eng, 174 (2022), Article 108823.
[34]

N.G. Hall, M.J. Magazine. Maximizing the value of a space mission. Eur J Oper Res, 78 (2) (1994), pp. 224-241.
[35]

M. Lemaître, G. Verfaillie, F. Jouhaud, J.M. Lachiver, N. Bataille. Selecting and scheduling observations of agile satellites. Aerosp Sci Technol, 6 (5) (2002), pp. 367-381.
[36]

P. Wang, G. Reinelt, P. Gao, Y. Tan. A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation. Comput Ind Eng, 61 (2) (2011), pp. 322-335.
[37]

L. He, X. Liu, G. Laporte, Y. Chen, Y. Chen. An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Comput Oper Res, 100 (2018), pp. 12-25.
[38]

J. Wu, F. Lu, J. Zhang, J. Yang, L. Xing. Design of task priority model and algorithm for imaging observation problem. J Syst Eng Electron, 31 (2) (2020), pp. 321-334.
[39]

G. Peng, R. Dewil, C. Verbeeck, A. Gunawan, L. Xing, P. Vansteenwegen. Agile earth observation satellite scheduling: an orienteering problem with time-dependent profits and travel times. Comput Oper Res, 111 (2019), pp. 84-98.
[40]

R. Vazquez, F. Perea, V.J. Galán. Resolution of an antenna-satellite assignment problem by means of integer linear programming. Aerosp Sci Technol, 39 (2014), pp. 567-574.
[41]

L. Linares, R. Vázquez, F. Perea, J. Galán-Vioque. A mixed integer linear programming model for resolution of the antenna-satellite scheduling problem. IEEE Trans Aerosp Electron Syst, 60 (1) (2024), pp. 463-473.
[42]

Chen M, Tworek J, Jun H, Yuan Q, Pinto HPDO, Kaplan J, et al. Evaluating large language models trained on code. arXiv:2107.03374.
[43]

Austin J, Odena A, Nye M, Bosma M, Michalewski H, Dohan D, et al. Program synthesis with large language models. arXiv:2108.07732.
[44]

N. van Stein, T. Bäck. LLaMEA: a large language model evolutionary algorithm for automatically generating metaheuristics. IEEE Trans Evol Comput, 29 (2) (2025), pp. 331-345.
[45]

C. Castelfranchi. Modelling social action for ai agents. Artif Intell, 103 (1-2) (1998), pp. 157-182.
[46]

Qian C, Cong X, Yang C, Chen W, Su Y, Xu J, et al. Communicative agents for software development. arXiv:2307.07924.
[47]

Hong S, Zheng X, Chen J, Cheng Y, Wang J, Zhang C, et al. MetaGPT: meta programming for multi-agent collaborative framework. arXiv:2308.00352.
[48]

Huang D, Bu Q, Zhang JM, Luck M, Cui H. AgentCoder: multi-agent-based code generation with iterative testing and optimisation. arXiv:2312.13010.
[49]

Chen W, Su Y, Zuo J, Yang C, Yuan C, Qian C, et al. AgentVerse: facilitating multi-agent collaboration and exploring emergent behaviors in agents. arXiv:2308.10848.
[50]

Lange R, Tian Y, Tang Y. Large language models as evolution strategies. In:Proceedings of the Genetic and Evolutionary Computation Conference Companion; 2024 Jul 14-18; Melbourne, Australia. New York City: Association for Computing Machinery (ACM); 2024. p. 579-82.
[51]

Brahmachary S, Joshi SM, Panda A, Koneripalli K, Sagotra AK, Patel H, et al. Large language model-based evolutionary optimizer: reasoning with elitism. arXiv:2403.02054.
[52]

Li H, Yang X, Wang Z, Zhu X, Zhou J, Qiao Y, et al. Auto MC-Reward:automated dense reward design with large language models for minecraft. In:Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CPVR 2024); 2024 Jun 16-22; Seattle, WA, USA. New York City: IEEE; 2024. p. 16426-35.
[53]

Zhang R, Liu F, Lin X, Wang Z, Lu Z, Zhang Q. Understanding the importance of evolutionary search in automated heuristic design with large language models. In:Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN 2024); 2024 Sep 14-18; Hagenberg, Austria. Berlin:Springer; 2024. p. 185-202.
[54]

Li G, Hammoud H, Itani H, Khizbullin D, Ghanem B. Camel: communicative agents for “mind” exploration of large scale language model society. arXiv:2303.17760.
[55]

J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, et al. Chain-of-thought prompting elicits reasoning in large language models. Adv Neural Inf Process Syst, 35 (2022), pp. 24824-24837.
[56]

L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, et al. Training language models to follow instructions with human feedback. Adv Neural Inf Process Syst, 35 (2022), pp. 27730-27744.
[57]

Hurst A, Lerer A, Goucher AP, Perelman A, Ramesh A, Clark A, et al. GPT-4o system card. arXiv:2410.21276.
[58]

Liu A, Feng B, Xue B, Wang B, Wu B, Lu C, et al. DeepSeek-V3 technical report. arXiv:2412.19437.
[59]

Grattafiori A, Dubey A, Jauhri A, Pandey A, Kadian A, Al-Dahle A, et al. The llama 3 herd of models. arXiv:2407.21783.
[60]

J. Chen, F. Wang, Y. Chen, L. He, Y. Du, J. Wu, et al. A generalized bilevel optimization model for largescale task scheduling in multiple agile earth observation satellites. Knowl Base Syst, 309 (2025), Article 112809.
[61]

R. Fratty, Y. Saar, R. Kumar, S. Arnon. Random routing algorithm for enhancing the cybersecurity of LEO satellite networks. Electronics, 12 (3) (2023), p. 518.
[62]

E.K. Burke, Y. Bykov. The late acceptance hill-climbing heuristic. Eur J Oper Res, 258 (1) (2017), pp. 70-78.
[63]

Liu F, Zhang R, Xie Z, Sun R, Li K, Lin X, et al. LLM4AD: a platform for algorithm design with large language model. arXiv:2412.17287.
PDF (4887KB)

1376

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉