Real-time online rescheduling for multiple agile satellites with emergent tasks

doi:10.23919/JSEE.2021.000120

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (6): 1407-1420.doi: 10.23919/JSEE.2021.000120

• SYSTEMS ENGINEERING • Previous Articles Next Articles

Real-time online rescheduling for multiple agile satellites with emergent tasks

Jun WEN(), Xiaolu LIU(), Lei HE*()

¹ College of Systems Engineering, National University of Defense Technology, Changsha 410073, China

Received:2020-10-22 Accepted:2021-11-08 Online:2022-01-05 Published:2022-01-05
Contact: Lei HE E-mail:jun_wen@aliyun.com;lxl_sunny@nudt.edu.cn;helei@nudt.edu.cn
About author:|WEN Jun was born in 1997. She received her B.S. degree in information and computing science from the School of Mathematics and Statistics, Changsha University of Science and Technology (CSUST), China, in 2019. She is currently a master student in management science and engineering at the College of Systems Engineering, National University of Defense Technology (NUDT), China. Her research interests are artificial intelligence, deep reinforcement learning, and metaheuristics, mainly focusing on distribution management and satellite scheduling problems such as collaborative mission planning methods of multi-satellite mobile target tracking. E-mail: jun_wen@aliyun.com||LIU Xiaolu was born in 1985. She received her B.E. degree in system engineering from National University of Defense Technology (NUDT), China, in 2006, and Ph.D. degree in management science and engineering from NUDT in 2011. From October 2015 to October 2016, she was a visiting scholar in école des Hautes études commerciales de Montréal (HEC), Montreal, Canada. She is currently an associate professor at the College of Systems Engineering, NUDT. Her research insterests are artificial intelligence and metaheuristics, focusing on distribution management and satellite scheduling problems. E-mail: lxl_sunny@nudt.edu.cn||HE Lei was born in 1991. He received his B.E. degree in management engineering from National University of Defense Technology (NUDT), China, in 2014, and Ph.D. degree in management science and engineering from NUDT in 2019. From October 2017 to October 2019, he was a visiting Ph.D. student in Delft University of Technology, the Netherlands. He is currently a lecturer at the College of Systems Engineering, NUDT. His research interests include artificial intelligence and machine learning. His current research focuses on the optimization of scheduling and planning of Earth observation satellites missions by designing exact and metaheuristic algorithms. E-mail: helei@nudt.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (72001212, 71701204, 71801218) and the China Hunan Postgraduate Research Innovating Project (CX2018B020).

Abstract

Abstract:

The emergent task is a kind of uncertain event that satellite systems often encounter in the application process. In this paper, the multi-satellite distributed coordinating and scheduling problem considering emergent tasks is studied. Due to the limitation of onboard computational resources and time, common online onboard rescheduling methods for such problems usually adopt simple greedy methods, sacrificing the solution quality to deliver timely solutions. To better solve the problem, a new multi-satellite onboard scheduling and coordinating framework based on multi-solution integration is proposed. This method uses high computational power on the ground and generates multiple solutions, changing the complex onboard rescheduling problem to a solution selection problem. With this method, it is possible that little time is used to generate a solution that is as good as the solutions on the ground. We further propose several multi-satellite coordination methods based on the multi-agent Markov decision process (MMDP) and mixed-integer programming (MIP). These methods enable the satellite to make independent decisions and produce high-quality solutions. Compared with the traditional centralized scheduling method, the proposed distributed method reduces the cost of satellite communication and increases the response speed for emergent tasks. Extensive experiments show that the proposed multi-solution integration framework and the distributed coordinating strategies are efficient and effective for onboard scheduling considering emergent tasks.

Key words: agile satellite scheduling, emergent task, onboard rescheduling, distributed coordinating, multi-solution integration

Jun WEN, Xiaolu LIU, Lei HE. Real-time online rescheduling for multiple agile satellites with emergent tasks[J]. Journal of Systems Engineering and Electronics, 2021, 32(6): 1407-1420.

Figures/Tables 13

Fig 1

Fig 2

Fig 3

Fig 4

Table 1

Fig 5

Fig 6

Fig 7

Table 3

Fig 7

Table 2

Fig 8

Fig 9

References 43

1	AYTUG H, LAWLEY M A, MCKAY K, et al Executing production schedules in the face of uncertainties: a review and some future directions. European Journal of Operational Research, 2005, 161 (1): 86- 110. doi: 10.1016/j.ejor.2003.08.027
2	VIEIRA G E, HERRMANN J W, LIN E Rescheduling manufacturing systems: a framework of strategies, policies, and methods. Journal of Scheduling, 2003, 6 (1): 39- 62. doi: 10.1023/A:1022235519958
3	WU M C, CHEN S Y A cost model for justifying the acceptance of rush orders. International Journal of Production Research, 1996, 34 (7): 1963- 1974. doi: 10.1080/00207549608905007
4	WU M C, CHEN S Y A multiple criteria decision-making model for justifying the acceptance of rush orders. Production Planning & Control, 1997, 8 (8): 753- 761.
5	KIM J, AHN J. Task and attitude control scheduling of multiple agile satellites considering task-dependent transition time. Proc. of the AIAA Scitech 2020 Forum, 2020. DOI: 10.2514/1.I010775.
6	ARREDONDO F, MARTINEZ E Learning and adaptation of a policy for dynamic order acceptance in make-to-order manufacturing. Computers & Industrial Engineering, 2010, 58 (1): 70- 83.
7	SNOEK M. Neuro-genetic order acceptance in a job shop setting. Proc. of the 7th International Conference on Neural Information Processing, 2000: 815–819.
8	YANG W, FUNG R Y K Stochastic optimization model for order acceptance with multiple demand classes and uncertain demand/supply. Engineering Optimization, 2014, 46 (6): 824- 841. doi: 10.1080/0305215X.2013.800056
9	NANDI A, ROGERS P Using simulation to make order acceptance/rejection decisions. Simulation, 2004, 80 (3): 131- 142. doi: 10.1177/0037549704045046
10	GHOMI S M T F, IRANPOOR M Earliness-tardiness-lost sales dynamic job-shop scheduling. Production Engineering, 2010, 4 (2/3): 221- 230. doi: 10.1007/s11740-010-0211-z
11	RAHMAN H F, SARKER R, ESSAM D A real-time order acceptance and scheduling approach for permutation flow shop problems. European Journal of Operational Research, 2015, 247 (2): 488- 503. doi: 10.1016/j.ejor.2015.06.018
12	SU L H, CHOU F D Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated. Production Planning & Control, 2000, 11 (8): 806- 819.
13	QIU D S, HE C, LIU J, et al. A dynamic scheduling method of earth-observing satellites by employing rolling horizon strategy. The Scientific World Journal, 2013. DOI: 10.1155/2013/304047.
14	LIAO D Y, YANG Y T Imaging order scheduling of an earth observation satellite. IEEE Trans. on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2007, 37 (5): 794- 802. doi: 10.1109/TSMCC.2007.900668
15	XU L, WANG Q, HUANG S M Dynamic order acceptance and scheduling problem with sequence-dependent setup time. International Journal of Production Research, 2015, 53 (19): 5797- 5808. doi: 10.1080/00207543.2015.1005768
16	WANG J J, ZHU X M, YANG L T, et al Towards dynamic real-time scheduling for multiple earth observation satellites. Journal of Computer and System Sciences, 2015, 81 (1): 110- 124. doi: 10.1016/j.jcss.2014.06.016
17	CHIEN S, TROESCH M. Heuristic onboard pointing re-scheduling for an earth observing spacecraft. Proc. of the 25th International Conference on Automated Planning and Scheduling, 2015: 1−13.
18	BEAUMET G, VERFAILLIE G, CHARMEAU M C Feasibility of autonomous decision making on board an agile earth-observing satellite. Computational Intelligence, 2011, 27 (1): 123- 139. doi: 10.1111/j.1467-8640.2010.00375.x
19	WU G H, MA M H, ZHU J H, et al Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks. Journal of Systems Engineering and Electronics, 2012, 23 (5): 723- 733. doi: 10.1109/JSEE.2012.00089
20	LI Y Q, WANG R X, XU M Q Rescheduling of observing spacecraft using fuzzy neural network and ant colony algorithm. Chinese Journal of Aeronautics, 2014, 27 (3): 678- 687. doi: 10.1016/j.cja.2014.04.027
21	HE L, LIU X L, CHEN Y W, et al Hierarchical scheduling for real-time agile satellite task scheduling in a dynamic environment. Advances in Space Research, 2019, 63 (2): 897- 912. doi: 10.1016/j.asr.2018.10.007
22	CHU X G, CHEN Y N, TAN Y J An anytime branch and bound algorithm for agile earth observation satellite onboard scheduling. Advances in Space Research, 2017, 60 (9): 2077- 2090. doi: 10.1016/j.asr.2017.07.026
23	CUI J T, ZHANG X Application of a multi-satellite dynamic mission scheduling model based on mission priority in emergency response. Sensors, 2019, 19, 14- 30.
24	WANG D J, YIN Y Q, CHENG T C E Parallel-machine rescheduling with job unavailability and rejection. Omega, 2018, 81, 246- 260. doi: 10.1016/j.omega.2018.04.008
25	BAYKASOGLU A, KARASLAN F S Solving comprehensive dynamic job shop scheduling problem by using a grasp-based approach. International Journal of Production Research, 2017, 55 (11): 3308- 3325. doi: 10.1080/00207543.2017.1306134
26	DA SILVA N C O, SCARPIN C T, PECORA JR J E, et al Online single machine scheduling with setup times depending on the jobs sequence. Computers & Industrial Engineering, 2019, 129, 251- 258.
27	WANG J J, ZHU X G, ZHU J H, et al. A realtime scheduling algorithm for multiple earth observation satellites. Proc. of the 9th IEEE International Conference on Embedded Software and Systems, 2012, 673–680.
28	GAO K, WU G H, ZHU J H Multi-satellite observation scheduling based on a hybrid ant colony optimization. Advanced Materials Research, 2013, 765, 532- 536.
29	SHI Y L, JIANG X J, ZHANG Y F, et al Static routing design of solar synchronous orbit micro-nano satellite constellation. Electronic Design Engineering, 2018, 25 (17): 25- 29.
30	WU G H, WANG H L, PEDRYCZ W, et al Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy. Computers & Industrial Engineering, 2017, 113, 576- 588.
31	YAO F, LI J T, CHEN Y N, et al Task allocation strategies for cooperative task planning of multi-autonomous satellite constellation. Advances in Space Research, 2019, 63 (2): 1073- 1084. doi: 10.1016/j.asr.2018.10.002
32	KLEINSCHRODT A, NOGUEIRA T, REED N, et al. Mission planning for the TIM nanosatellite remote sensing constellation. Proc. of the 69th International Astronautical Congress, 2018. DOI: 10.1007/978-94-011-5088-0_37.
33	XU R, CHEN H P, LIANG X L, et al Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization. Expert Systems with Applications, 2016, 51, 195- 206. doi: 10.1016/j.eswa.2015.12.039
34	FENG P, CHEN H, PENG S, et al. A method of distributed multi-satellite mission scheduling based on improved contract net protocol. Proc. of the 11th International Conference on Natural Computation, 2015, 1062–1068.
35	SKOBELEV P O, SIMONOVA E V, ZHILYAEV A A, et al Application of multi-agent technology in the scheduling system of swarm of earth remote sensing satellites. Procedia Computer Science, 2017, 103, 396- 402. doi: 10.1016/j.procs.2017.01.127
36	HE L, DE WEERDT M, YORKE-SMITH N. Tabu-based large neighbourhood search for time/sequence-dependent scheduling problems with time windows. Proc. of the 29th International Conference on Automated Planning and Scheduling, 2019: 186−194.
37	HE L, DE WEERDT M, YORKE-SMITH N Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm. Journal of Intelligent Manufacturing, 2020, 31, 1051- 1078. doi: 10.1007/s10845-019-01518-4
38	HE L, LIU X L, LAPORTE G, et al An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers and Operations Research, 2018, 100 (1): 12- 25.
39	HSIEH F S Analysis of contract net in multi-agent systems. Automatica, 2006, 42 (5): 733- 740. doi: 10.1016/j.automatica.2005.12.002
40	DE NIJS F, SPAAN M, DE WEERDT M. Preallocation and planning under stochastic resource constraints. Proc. of the 32nd AAAI Conference on Artificial Intelligence, 2018, 4662–4669.
41	PAUKSHTIS E A. Constrained Markov decision processes. Boca Raton: CRC Press, 1999.
42	IBM. IBM CPLEX Optimizer, 2018. https://www.ibm.com/analytics/cplex-optimizer.
43	LI G L, XING L N, CHEN Y W A hybrid online scheduling mechanism with revision and progressive techniques for autonomous earth observation satellite. Acta Astronautica, 2017, 140 (1): 308- 321.

Satellite	$ax$	$ e $	$ic$	$ \omega $ /(°)	RAAN	$ m $
Satellite 1	7 200 000	0.000 627	96.576	0	175.72	0.075
Satellite 2	7 200 000	0.000 627	96.576	0	145.72	30.075
Satellite 3	7 200 000	0.000 627	96.576	0	115.72	60.075

Satellite	Number of tasks	FR	MMDPOP	GS	MIPS	SSR
1	100	1.6698	<0.0001	<0.0001	0.0082	<0.0001
1	200	4.0864	<0.0001	<0.0001	0.0134	<0.0001
1	300	7.0089	<0.0001	<0.0001	0.0174	<0.0001
1	400	9.9342	<0.0001	<0.0001	0.0238	<0.0001
2	100	1.4958	<0.0001	<0.0001	0.0087	<0.0001
2	200	3.9623	0.0001	0.0001	0.0171	<0.0001
2	300	7.2068	0.0001	0.0001	0.0280	0.0001
2	400	10.7444	0.0001	0.0001	0.0379	0.0001
3	100	1.4547	0.0001	0.0001	0.0086	<0.0001
3	200	3.5889	0.0001	0.0001	0.0183	0.0001
3	300	6.6247	0.0001	0.0001	0.0295	0.0001
3	400	10.1203	0.0002	0.0002	0.0460	0.0001
Average	?	5.6507	0.0001	0.0001	0.0239	0.0001

Satellite	Number of tasks	FR	MMDPOP	GS	MIPS	SSR
1	100	330.01	325.33	325.87	325.87	325.15
1	200	556.12	535.77	539.46	539.32	530.05
1	300	671.67	669.51	672.26	674.24	658.34
1	400	731.87	738.24	738.47	743.85	724.70
2	100	451.75	442.75	447.61	448.21	447.42
2	200	870.55	849.99	860.48	859.14	848.56
2	300	1190.67	1186.92	1185.50	1209.66	1153.84
2	400	1385.66	1415.30	1410.54	1443.27	1369.31
3	100	458.75	454.49	458.00	457.98	458.43
3	200	945.23	928.32	933.77	935.87	934.42
3	300	1446.54	1427.96	1435.84	1439.00	1419.59
3	400	1770.61	1785.36	1775.09	1809.00	1749.47
Average	?	900.78	896.66	898.57	907.12	884.94

Real-time online rescheduling for multiple agile satellites with emergent tasks

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 13

References 43

Related Articles 0

Recommended Articles

Metrics

Comments