Multi-satellite scheduling approach for emergency scenarios based on hierarchical forecasting with Transformer network

LUO Zong; DU Chun; CHEN Hao; PENG Shuang; LI Jun

doi:10.7527/S1000-6893.2020.24721

ACTA AERONAUTICAET ASTRONAUTICA SINICA >

2021 , Vol. 42 >Issue 4: 524721 - 524721

DOI: https://doi.org/10.7527/S1000-6893.2020.24721

Electronics and Electrical Engineering and Control

Multi-satellite scheduling approach for emergency scenarios based on hierarchical forecasting with Transformer network

LUO Zong ,
DU Chun ,
CHEN Hao ,
PENG Shuang ,
LI Jun

Expand

College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China

Received date: 2020-09-07

Revised date: 2020-09-27

Online published: 2020-11-27

Supported by

National Natural Science Foundation of China (U19A2058, 61806211); Natural Science Foundation of Hunan Province (2020 JJ4103)

Fold

Abstract

Emergency observation mission scheduling is a complex problem of combinatorial optimization with strong timeliness as the scheduling algorithm must complete the computation within the required time limit. Using machine learning methods to provide high-quality initial solutions for scheduling algorithms can effectively simplify the calculation process. For this reason, this paper proposes a multi-satellite scheduling approach for emergency scenarios based on hierarchical forecasting with Transformer network, which decomposes the scheduling into three steps. Firstly, using the Transformer-based task schedulability prediction model to predict whether the observation task will be executed or not, so as to obtain a set of tasks to be executed. After that, using the Transformer-based task allocation model to allocate the satellite to the task set, so as to obtain the initial scheduling scheme. Finally, a constraint modification algorithm based on random hill climbing is used to optimize the initial scheme, so as to obtain feasible scheduling schemes. To verify the effectiveness of the proposed method, simulation experiments are conducted, and the results are compared with those by CPLEX Optimization, standard genetic algorithm, Long Short-Term Memory and other methods. The simulation results show that the method proposed consumes a short calculation time and has high benefits, and is thus suitable for multi-satellite scheduling of emergency observation missions.

Key words： emergency observation mission; hierarchical forecasting; task schedulability; task allocation; Transformer

Cite this article

LUO Zong , DU Chun , CHEN Hao , PENG Shuang , LI Jun . Multi-satellite scheduling approach for emergency scenarios based on hierarchical forecasting with Transformer network[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021 , 42(4) : 524721 -524721 . DOI: 10.7527/S1000-6893.2020.24721

References

[1] 贺川,邱涤珊,朱晓敏,等. 基于滚动优化策略的成像侦察卫星应急调度方法[J]. 系统工程理论与实践, 2013, 33(10):2685-2694. HE C, QIU D S, ZHU X M, et al. Emergency sheduling method for imaging reconnaissance satellites based on rolling horizon optimization strategy[J]. System Engineering Theory and Practice, 2013, 33(10):2685-2694(in Chinese).
[2] 陈书剑, 李智, 胡敏, 等. 应急任务响应时间最优的多星成像规划方法[J]. 中国空间科学技术, 2020, 40(2):17-28. CHEN S J,LI Z,HU M, et al. Multi-satellite imaging scheduling method with optimal response time for emergency tasks[J]. Chinese Space Science and Technology, 2020, 40(2):17-28(in Chinese).
[3] MORRIS R A, DUNGAN J L, BRESINA J L. An information infrastructure for coordinating earth science observations[C]//IEEE International Conference on Space Mission Challenges for Information Technology. Piscataway:IEEE Press, 2006.
[4] YAO F, LI J F, BAI B C. Earth observation satellites scheduling based on decomposition optimization algorithm[J]. International Journal of Image, Graphics & Signal Processing, 2010, 2(1):9.
[5] 孙凯,邢立宁,陈英武. 基于分解优化策略的多敏捷卫星联合对地观测调度[J]. 计算机集成制造系统, 2013, 19(1):127-136. SUN K, XING L N, CHEN Y W. Agile earth observing satellites mission scheduling based on decomposition optimization algorithm[J]. Computer Integrated Manufacturing Systems, 2013, 19(1):127-136(in Chinese).
[6] 白保存,陈英武,贺仁杰,等.基于分解优化的多星合成观测调度算法[J].自动化学报, 2009, 35(5):596-604. BAI B C, CHEN Y W, HE R J, et al. Scheduling satellites observation and task merging based on decom position optimization algorithm[J]. Acta Automatica Sinica, 2009, 35(5):596-604(in Chinese).
[7] 朱政霖, 马广彬, 黄鹏, 等. 基于任务分解的多星成像规划模型建立与求解[J]. 航天器工程, 2018, 27(2):6-13. ZHU Z L, MA G B, HUANG P, et al. Establishment and solution of multi-satellite imaging scheduling model based on task decomposition[J]. Spacecraft Engineering, 2018, 27(2):6-13(in Chinese).
[8] LI J,LI J,JING N,et al. A satellite schedulability prediction algorithm for EO SPS[J]. Chinese Journal of Aeronautics, 2013, 26(3):705-716.
[9] 白国庆,陈英武,杨振宇,等. 基于集成BP神经网络的成像卫星任务可调度性预测方法[C]//第二届高分辨率对地观测学术年会, 2013:1-9. BAI G Q, CHEN Y W, YANG Z Y, et al. An integrated BP neural network based imaging satellite mission schedulability prediction method[C]//The Second Annual Academic Conference on High-resolution Earth Observation, 2013:1-9(in Chinese).
[10] 刘嵩,白国庆,陈英武. 地球观测网络成像任务可调度性预测方法[J]. 宇航学报, 2015, 36(5):583-588. LIU S, BAI G Q, CHEN Y W. Prediction method for imaging task schedulability of earth observation network[J]. Journal of Astronautics, 2015, 36(5):583-588(in Chinese).
[11] 邢立宁, 王原, 何永明, 等. 基于BP神经网络的星上任务可调度性预测方法[J]. 中国管理科学, 2015, 23(S1):117-124. XING L N, WANG Y, HE Y M, et al. An earth observation satellite task schedulability prediction method based on BP artificial network[J]. Chinese Journal of Management Science, 2015,23(S1):117-124(in Chinese).
[12] PENG S, CHEN H, DU C, et al. Onboard observation task scheduling for an autonomous earth observation satellite using long short-term memory[J]. IEEE Access, 2018, 99(6):65118-65129.
[13] SUTSKEVER I, VINYALS O, LE Q V. Sequence to sequence learning with neural networks[C]//Advances in Neural Information Processing Systems, 2014:3104-3112.
[14] GEHRING J, AULI M, GRANGIER D, et al. Convolutional sequence to sequence learning[DB/OL]. arXiv preprint:1705.03122,2017.
[15] VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need[C]//Advances in Neural Information Processing Systems, 2017:5998-6008.
[16] DEVLIN J, CHANG M W, LEE K, et al. BERT:Pre-training of deep bidirectional transformers for language understanding[C]//Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics:Human Language Technologies, 2019:4171-4186.
[17] 郭玉华, 李军, 赵珂, 等. 多星联合任务规划的迭代修复求解技术[J]. 系统工程与电子技术, 2009, 31(8):1958-1962. GUO Y H, LI J, ZHAO K, et al. Iterative repair method for multiple satellites united imaging scheduling[J]. Systems Engineering and Electronics, 2009, 31(8):1958-1962(in Chinese).
[18] 郭玉华, 李军, 赵珂, 等. 多星联合任务规划中的启发式求解方法研究[J]. 宇航学报, 2009, 30(2):652-658. GUO Y H, LI J, ZHAO K, et al. A heuristic method for earth observing satellites united imaging scheduling[J]. Journal of Astronautics, 2009, 30(2):652-658(in Chinese).
[19] 黄生俊, 邢立宁, 郭波. 基于改进模拟退火的多星任务规划方法[J]. 科学技术与工程, 2012, 31(12):8293-8298. HUANG S J, XING L N, GUO B. Multi-satellites mission scheduling technique based on improved simulated annealing[J]. Science Technology and Engineering, 2012, 31(12):8293-8298(in Chinese).
[20] CHEN Q W, ZHAO H, LI W, et al. Behavior sequence transformer for E-commerce recommendation in Alibaba[DB/OL]. arXiv preprint:1905.06874.
[21] SHANG S, LIU J, YANG Y. Multi-layer transformer aggregation encoder for answer generation[J]. IEEE Access, 2020, 8:90410-90419.
[22] 张小莲, 李群, 殷明慧, 等. 一种引入停止机制的改进爬山算法[J]. 中国电机工程学报, 2012, 32(14):128-134. ZHANG X L, LI Q, YIN M H, et al. An improved hill-climbing searching method based on halt mechanim[J]. Proceedings of The Chinese Society for Electrical, 2012, 32(14):128-134(in Chinese).
[23] LIU X, LAPORTE G, CHEN Y, et al. An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time[J]. Computers & Operations Research, 2017, 86(10):41-53.

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

References