Automating Algorithm Design for Agile Satellite Task Assignment with Large Language Models and Reinforcement Learning

CHEN Yingguo; WANG Feiran; HU Yunpeng; YANG Bin; YAN Bing

doi:10.11999/JEIT250991

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

CHEN Yingguo, WANG Feiran, HU Yunpeng, YANG Bin, YAN Bing. Automating Algorithm Design for Agile Satellite Task Assignment with Large Language Models and Reinforcement Learning[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250991

Citation:

CHEN Yingguo, WANG Feiran, HU Yunpeng, YANG Bin, YAN Bing. Automating Algorithm Design for Agile Satellite Task Assignment with Large Language Models and Reinforcement Learning[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250991

Citation:

CHEN Yingguo, WANG Feiran, HU Yunpeng, YANG Bin, YAN Bing. Automating Algorithm Design for Agile Satellite Task Assignment with Large Language Models and Reinforcement Learning[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250991

PDF( 3882 KB)

Automating Algorithm Design for Agile Satellite Task Assignment with Large Language Models and Reinforcement Learning

doi: 10.11999/JEIT250991 cstr: 32379.14.JEIT250991

1.
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
2.
Beijing Institute of Remote Sensing Information, Beijing 100011, China

Funds: The National Natural Science Foundation of China (U23B2039)

Received Date: 2025-09-26
Accepted Date: 2026-01-06
Rev Recd Date: 2026-01-06

Available Online: 2026-01-10

Abstract

Abstract

Objective The Multi-Agile Earth Observation Satellite Mission Scheduling Problem (MAEOSMSP) is an NP-hard problem. Algorithm design for this problem has long been constrained by reliance on expert experience and limited adaptability across diverse scenarios. To address this limitation, an Adaptive Algorithm Design (AAD) framework is proposed. The framework integrates a Large Language Model (LLM) and Reinforcement Learning (RL) to enable automated generation and intelligent application of scheduling algorithms. It is built on a novel offline evolution-online decision-making architecture. The objective is to discover heuristic algorithms that outperform human-designed methods and to provide an efficient and adaptive solution methodology for the MAEOSMSP. Methods The AAD framework adopts a two-stage mechanism. In the offline evolution stage, LLM-driven evolutionary computation is used to automatically generate a diverse and high-quality library of task assignment algorithms, thereby alleviating the limitations of manual design. In the online decision-making stage, an RL agent is trained to dynamically select the most suitable algorithm from the library based on the real-time solving state (e.g., solution improvement and stagnation). This process is formulated as a Markov decision process, which allows the agent to learn a policy that adapts to problem-solving dynamics. Results and Discussions The effectiveness of the AAD framework is evaluated through comprehensive experiments on 15 standard test scenarios. The framework is compared with several state-of-the-art methods, including expert-designed heuristics, an advanced deep learning approach, and ablation variants of the proposed framework. The results show that the dynamic strategies generated by AAD consistently outperform the baselines, with performance improvements of up to 9.8% in complex scenarios. Statistical analysis further indicates that AAD achieves superior solution quality and demonstrates strong robustness across different problem instances. Conclusions A novel AAD framework is presented to automate algorithm design for the MAEOSMSP by decoupling algorithm generation from algorithm application. The combination of LLM-based generation and RL-based decision making is validated empirically. Compared with traditional hyper-heuristics and existing LLM-based methods, the proposed architecture enables both the creation of new algorithms and their dynamic application. The framework provides a new paradigm for solving complex combinatorial optimization problems and shows potential for extension to other domains.
- Large Language Model (LLM),
- Reinforcement learning,
- Algorithm design,
- Satellite mission scheduling

FullText(HTML)

References(28)

References

[1]	ZHAO Qiang, YU Le, DU Zhenrong, et al. An overview of the applications of Earth observation satellite data: Impacts and future trends[J]. Remote Sensing, 2022, 14(8): 1863. doi: 10.3390/rs14081863.
[2]	HE Lei, DE WEERDT M, and YORKE-SMITH N. Time/sequence-dependent scheduling: The design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm[J]. Journal of Intelligent Manufacturing, 2020, 31(4): 1051–1078. doi: 10.1007/s10845-019-01518-4.
[3]	WANG Xinwei, WU Guohua, XING Lining, et al. Agile Earth observation satellite scheduling over 20 years: Formulations, methods, and future directions[J]. IEEE Systems Journal, 2021, 15(3): 3881–3892. doi: 10.1109/JSYST.2020.2997050.
[4]	PENG Guansheng, SONG Guopeng, HE Yongming, et al. Solving the agile Earth observation satellite scheduling problem with time-dependent transition times[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52(3): 1614–1625. doi: 10.1109/TSMC.2020.3031738.
[5]	CHO D H, KIM J H, CHOI H L, et al. Optimization-based scheduling method for agile Earth-observing satellite constellation[J]. Journal of Aerospace Information Systems, 2018, 15(11): 611–626. doi: 10.2514/1.I010620.
[6]	WU Jian, YAO Feng, SONG Yanjie, et al. Frequent pattern-based parallel search approach for time-dependent agile earth observation satellite scheduling[J]. Information Sciences, 2023, 636: 118924. doi: 10.1016/j.ins.2023.04.003.
[7]	WEI Luona, CUI Yongqiang, CHEN Ming, et al. Multi-objective neural policy approach for agile earth satellite scheduling problem considering image quality[J]. Swarm and Evolutionary Computation, 2025, 94: 101857. doi: 10.1016/j.swevo.2025.101857.
[8]	LI Lei, DU Yonghao, YAO Feng, et al. Learning memetic algorithm based on variable population and neighborhood for multi-complex target scheduling of large-scale imaging satellites[J]. Swarm and Evolutionary Computation, 2025, 92: 101789. doi: 10.1016/j.swevo.2024.101789.
[9]	彭观胜, 宋国鹏, 刘晓路, 等. 考虑时间依赖收益特性的敏捷卫星调度问题[J]. 运筹与管理, 2024, 33(8): 1–7. doi: 10.12005/orms.2024.0243. PENG Guansheng, SONG Guopeng, LIU Xiaolu, et al. Agile earth observation satellite scheduling with time-dependent profits[J]. Operations Research and Management Science, 2024, 33(8): 1–7. doi: 10.12005/orms.2024.0243.
[10]	DU Yonghao, WANG Tao, XIN Bin, et al. A data-driven parallel scheduling approach for multiple agile earth observation satellites[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(4): 679–693. doi: 10.1109/TEVC.2019.2934148.
[11]	WANG Xinwei, GU Yi, WU Guohua, et al. Robust scheduling for multiple agile Earth observation satellites under cloud coverage uncertainty[J]. Computers & Industrial Engineering, 2021, 156: 107292. doi: 10.1016/j.cie.2021.107292.
[12]	SUN Haiquan, XIA Wei, WANG Zhilong, et al. Agile earth observation satellite scheduling algorithm for emergency tasks based on multiple strategies[J]. Journal of Systems Science and Systems Engineering, 2021, 30(5): 626–646. doi: 10.1007/s11518-021-5506-4.
[13]	YAO Feng, CHEN Yingguo, WANG Ling, et al. A bilevel evolutionary algorithm for large-scale multiobjective task scheduling in multiagile earth observation satellite systems[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2024, 54(6): 3512–3524. doi: 10.1109/TSMC.2024.3359265.
[14]	CHEN Jiawei, WANG Feiran, CHEN Yingguo, et al. A generalized bilevel optimization model for large-scale task scheduling in multiple agile earth observation satellites[J]. Knowledge-Based Systems, 2025, 309: 112809. doi: 10.1016/j.knosys.2024.112809.
[15]	HE Yongming, WU Guohua, CHEN Yingwu, et al. A two-stage framework and reinforcement learning-based optimization algorithms for complex scheduling problems[J]. arXiv preprint arXiv: 2103.05847, 2021.
[16]	FENG Xiaoen, LI Yuqing, and XU Minqiang. Multi-satellite cooperative scheduling method for large-scale tasks based on hybrid graph neural network and metaheuristic algorithm[J]. Advanced Engineering Informatics, 2024, 60: 102362. doi: 10.1016/j.aei.2024.102362.
[17]	LI Rui, WANG Ling, SANG Hongyan, et al. LLM-assisted automatic memetic algorithm for lot-streaming hybrid job shop scheduling with variable sublots[J]. IEEE Transactions on Evolutionary Computation, 2025, Early Access. doi: 10.1109/TEVC.2025.3556186.
[18]	LIU Fei, TONG Xialiang, YUAN Mingxuan, et al. Algorithm evolution using large language model[J]. arXiv preprint arXiv: 2311.15249, 2023.
[19]	LIU Fei, TONG Xialiang, YUAN Mingxuan, et al. Evolution of heuristics: Towards efficient automatic algorithm design using large language model[C]. Forty-first International Conference on Machine Learning, Vienna, Austria, 2024.
[20]	YE Haoran, WANG Jiarui, CAO Zhiguang, et al. ReEvo: Large language models as hyper-heuristics with reflective evolution[C]. The 38th International Conference on Neural Information Processing Systems, Vancouver, Canada, 2024: 1381. doi: 10.5555/3737916.3739297.
[21]	LI Hanxiao, GAO Kaizhou, DUAN Peiyong, et al. An improved artificial bee colony algorithm with Q-learning for solving permutation flow-shop scheduling problems[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2023, 53(5): 2684–2693. doi: 10.1109/TSMC.2022.3219380.
[22]	QI Rui, LI Junqing, WANG Juan, et al. QMOEA: A Q-learning-based multiobjective evolutionary algorithm for solving time-dependent green vehicle routing problems with time windows[J]. Information Sciences, 2022, 608: 178–201. doi: 10.1016/j.ins.2022.06.056.
[23]	CHEN Ming, DU Yonghao, TANG Ke, et al. Learning to construct a solution for the agile satellite scheduling problem with time-dependent transition times[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2024, 54(10): 5949–5963. doi: 10.1109/TSMC.2024.3411640.
[24]	GONG Yupeng, LI Anshou, and PENG Xuan. Geometrical design method of Walker constellation in non-terrestrial network[J]. Acta Astronautica, 2024, 219: 618–626. doi: 10.1016/j.actaastro.2024.03.069.
[25]	KOLAEE M H, JABBARZADEH A, and AL-E-HASHEM S M J M. Sustainable group tourist trip planning: An adaptive large neighborhood search algorithm[J]. Expert Systems with Applications, 2024, 237: 121375. doi: 10.1016/j.eswa.2023.121375.
[26]	JIA Shengyang, DENG Lei, ZHAO Quanwu, et al. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization[J]. Journal of Industrial and Management Optimization, 2023, 19(2): 1187–1210. doi: 10.3934/jimo.2021225.
[27]	WU Guohua, XIANG Zhiqing, WANG Yalin, et al. Improved adaptive large neighborhood search algorithm based on the two-stage framework for scheduling multiple super-agile satellites[J]. IEEE Transactions on Aerospace and Electronic Systems, 2024, 60(5): 7185–7200. doi: 10.1109/TAES.2024.3416427.
[28]	HE Lei, LIU Xiaolu, LAPORTE G, et al. An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling[J]. Computers & Operations Research, 2018, 100: 12–25. doi: 10.1016/j.cor.2018.06.020.