Survey on autonomous task scheduling technology for Earth observation satellites

doi:10.23919/JSEE.2022.000141

Journal of Systems Engineering and Electronics ›› 2022, Vol. 33 ›› Issue (6): 1176-1189.doi: 10.23919/JSEE.2022.000141

• SYSTEMS ENGINEERING • Previous Articles

Survey on autonomous task scheduling technology for Earth observation satellites

Jian WU(), Yuning CHEN(), Yongming HE(), Lining XING(), Yangrui HU()

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

Received:2020-12-04 Online:2022-12-18 Published:2022-12-24
Contact: Yongming HE E-mail:1551699723@qq.com;451480978@qq.com;heyongming10@hotmail.com;xing2999@qq.com;1641241565@qq.commailto
About author:
WU Jian was born in 1994. He received his M.S. degree from Hunan University of Technology in 2018. He is currently pursuing his Ph.D. degree with National University of Defense Technology. His research interests include intelligent optimization and task scheduling. E-mail: 1551699723@qq.com

CHEN Yuning was born in 1988. He received his B.E. and M.E. degrees from National University of Defense Technology in 2010 and 2012, respectively, and Ph.D. degree in computer science from the LERIA Laboratory, University of Angers, France, in 2016. His research interests include intelligent optimization and task scheduling. E-mail: 451480978@qq.com

HE Yongming was born in 1992. He received his M.S. degree from National University of Defense Technology in 2016. He is currently pursuing his Ph.D. degree with National University of Defense Technology. His research interests include intelligent optimization and task scheduling. E-mail: heyongming10@hotmail.com

XING Lining was born in 1980. He received his B.S. degree in economics and science from Xi’an Jiaotong University, Xi’an, China, in 2002, and Ph.D. degree from National University of Defense Technology, Changsha, China, in 2009. He is currently a professor in National University of Defense Technology. His research interests include intelligent optimization and task scheduling. E-mail: xing2999@qq.com

HU Yangrui was born in 1999. He is studying for his B.S. degree in system theory at the College of Systems Engineering, National University of Defense Technology. His research interest is big data engineering. E-mail: 1641241565@qq.com
Supported by:
This work was supported by the National Natural Science Foundation of China (72001212;61773120), Hunan Postgraduate Research Innovation Project (CX20210031), the Foundation for the Author of National Excellent Doctoral Dissertation of China (2014-92), and the Innovation Team of Guangdong Provincial Department of Education (2018KCXTD031).

Abstract

Abstract:

How to make use of limited onboard resources for complex and heavy space tasks has attracted much attention. With the continuous improvement on satellite payload capacity and the increasing complexity of observation requirements, the importance of satellite autonomous task scheduling research has gradually increased. This article first gives the problem description and mathematical model for the satellite autonomous task scheduling and then follows the steps of “satellite autonomous task scheduling, centralized autonomous collaborative task scheduling architecture, distributed autonomous collaborative task scheduling architecture, solution algorithm". Finally, facing the complex and changeable environment situation, this article proposes the future direction of satellite autonomous task scheduling.

Key words: satellite autonomous task scheduling, centralized architecture, distributed architecture

Jian WU, Yuning CHEN, Yongming HE, Lining XING, Yangrui HU. Survey on autonomous task scheduling technology for Earth observation satellites[J]. Journal of Systems Engineering and Electronics, 2022, 33(6): 1176-1189.

Figures/Tables 7

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

References 95

1	DU Y H, XING L N, CHEN Y G Unified modeling and multi-strategy collaborative optimization for satellite task scheduling. Control and Decision, 2019, 34 (9): 1847- 1856.
2	DU Y H, XING L N, CAI Z Q Survey on intelligent scheduling technologies for unmanned flying craft clusters. Acta Automatica Sinica, 2020, 46 (2): 222- 241.
3	LIU Y, CHEN Y W, TAN Y J A modeling and algorithm for the new tasks ’ arriving in multi-satellites dynamic scheduling. Systems Engineering-Theory & Practice, 2005, 25 (4): 35- 41.
4	YAO F, XING L N, HE R J Model and algorithm to mission planning of agile earth observing satellites. Computer Integrated Manufacturing Systems, 2013, 19 (5): 1035- 1040.
5	WU J, SONG B Y, ZHANG G T, et al A data-driven improved genetic algorithm for agile earth observation satellite scheduling with time-dependent transition time. Computers & Industrial Engineering, 2022, 174 (12): 108823.
6	HE Y M. Research on agile satellite autonomous mission planning system and re-planning method. Changsha: National University of Defense Technology, 2016. (in Chinese)
7	LIU S, CHEN Y W, XING L N Time-dependent autonomous task planning of agile imaging satellites. Journal of Intelligent & Fuzzy Systems, 2016, 31 (3): 1365- 1375.
8	XIE P, DU Y H, YAO F, et al Literature review for autonomous scheduling technology of agile earth observation satellites. Journal of Astronautic, 2019, 40 (2): 127- 138.
9	LI Z L, LI X J, WANG Z H Current status and prospect of agile satellite mission planning. Journal of Equipment Academy, 2016, 27 (1): 69- 75.
10	SUN K, XING L N, CHEN Y W Agile earth observing satellites mission scheduling based on decomposition optimization algorithm. Computer Integrated Manufacturing Systems, 2013, 19 (1): 127- 136.
11	SMITH B, MILLAR W, DUNPHY J, et al Validation and verification of the remote agent for spacecraft autonomy. Proc. of the IEEE Aerospace Conference, 1999, 1, 449- 468.
12	MUSCETTOLA N, NAYAK P P, PELL B, et al Remote agent: to boldly go where no AI system has gone before. Artificial Intelligence, 1998, 103 (1/2): 5- 47.
13	KHATIB L, FRANK J, SMITH D, et al. Interleaved observation execution and rescheduling on earth observing systems. Proc. of the 13th International Conference on Artificial Intelligence Planning and Scheduling Workshop on Plan Execution, 2003. https://www.docin.com/p-1825808639.html.
14	CHIEN S, SHERWOOD R, TRAN D, et al. The EO-1 autonomous science agent. Proc. of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems, 2004, 1: 420−427.
15	RABIDEAU G, KNIGHT R, CHIEN S, et al. Iterative repair planning for spacecraft operations using the ASPEN system. Artificial Intelligence, Robotics and Automation in Space, 1999, 440: 99.
16	CHIEN S A, KNIGHT R, STECHERT A, et al Using iterative repair to improve the responsiveness of planning and scheduling. Proc. of the 5th International Conference on Artificial Intelligence Planning Systems, 2000, 300- 307.
17	LIU Z, GAO L, CHAI Y Research on task scheduling mechanism of distributed satellite system. Journal of Computational Information Systems, 2014, 10 (24): 10703- 10713.
18	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, 2013, 304047.
19	NIU X N, ZHAI X J, TANG H, et al Multi-satellite scheduling approach for dynamic areal tasks triggered by emergent disaster. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2016, 1, 475- 481.
20	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
21	PARISH D A. A genetic algorithm approach to automating satellite range scheduling. Ohio: Air Force Institute of Technology, 1994.
22	WANG P. Research on branch-and-price based multi-satellite multi-station integrated scheduling method. Changsha: National University of Defense Technology, 2011. (in Chinese)
23	MARINELLI F, NOCELLA S, ROSSI F, et al A Lagrangian heuristic for satellite range scheduling with resource constraints. Computers & Operations Research, 2011, 38 (11): 1572- 1583.
24	WANG P, REINELT G, GAO P, et al A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation. Computers & Industrial Engineering, 2011, 61 (2): 322- 335.
25	LI Z X, LI J, MU W T Space-ground TT&C resources integrated scheduling based on the hybrid ant colony optimization. Proc. of the Conference of Spacecraft TT& C Technology in China, 2016, 179- 196.
26	XU X Y, WANG C H, JIN Z H Design, analysis and optimization of random access inter-satellite ranging system. Journal of Systems Engineering and Electronics, 2020, 31 (5): 871- 883.
27	HE R J, CAO P, BAO B C, et al Models, algorithms and applications to the mission planning system of imaging satellites. Systems Engineering-Theory & Practice, 2011, 31 (3): 411- 422.
28	WANG H J, HE H, YANG Z Scheduling of agile satellites based on an improved quantum genetic algorithm. Journal of Astronautics, 2018, 39 (11): 1266- 1274.
29	LIU X, LAPORTE G, CHEN Y, et al An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 2017, 86, 41- 53.
30	ABRAMSON M, CARTER D, KOLITZ S, et al. The design and implementation of draper’s earth phenomena observing system (epos). Proc. of the AIAA Space Conference, 2001. DOI: 10.2514/6.2001-4565.
31	SHE Y C, LI S, ZHAO Y B Onboard mission planning for agile satellite using modified mixed-integer linear programming. Aerospace Science and Technology, 2018, 72, 204- 216. doi: 10.1016/j.ast.2017.11.009
32	HE L, LIU X L, LAPORTE G, et al An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 2018, 100, 12- 25.
33	LIU S, CHEN Y W, XING L N, et al Method of agile imaging satellites autonomous task planning. Computer Integrated Manufacturing Systems, 2016, 22 (4): 928- 934.
34	ACKERMANN S, ANGRISANO A, DEL PIZZO S, et al Digital surface models for GNSS mission planning in critical environments. Journal of Surveying Engineering, 2014, 140 (2): 21- 29.
35	SONG Y J, HUANG D J, ZHOU Z Y, et al An emergency task autonomous planning method of agile imaging satellite. EURASIP Journal on Image and Video Processing, 2018, 2018 (1): 29. doi: 10.13196/j.cims.2016.04.006
36	GLOBUS A, CRAWFORD J, LOHN J, et al. Scheduling earth observing fleets using evolutionary algorithms: problem description and approach. Proc. of the International NASA Workshop on Planning & Scheduling for Space, 2002. https://www.researchgate.net/publication/244139540.
37	GLOBUS A, CRAWFORD J, LOHN J, et al A comparison of techniques for scheduling earth observing satellites. Proc. of the 16th Conference on Innovative Applications of Artificial Intelligence, 2004, 836- 843.
38	VASQUEZ M, HAO J K A “logic-constrained” knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite. Computational Optimization and Applications, 2001, 20 (2): 137- 157. doi: 10.1023/A:1011203002719
39	WANG J, LI J, CHEN J Multi-objective EOSs joint imaging scheduling method. Journal of Astronautics, 2007, 28 (2): 354- 359.
40	BAI G Q, CHEN Y W, YANG Z Y, et al Method for predicting imaging satellite task schedulability based on integrated BP neural network. Proc. of the 2nd Annual Conference on High Resolution Earth Observation, 2013, 1- 9.
41	BECK J C, PROSSER P, SELENSKY E Vehicle routing and job shop scheduling: What’s the difference? Proc. of the 13th International Conference on International Conference on Automated Planning and Scheduling, 2003, 267- 276.
42	LI J F, TAN Y J VRP and JSP model of satellite observation joint scheduling problem. System Engineering, 2006, 24 (6): 111- 115.
43	WANG H J. Research on large-scale online dispatch method of satellite based on reinforcement learning. Beijing: Chinese Academy of Sciences University, 2018. (in Chinese)
44	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
45	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
46	LI J, CHEN H, JING N A data transmission scheduling algorithm for rapid-response earth-observing operations. Chinese Journal of Aeronautics, 2014, 27 (2): 349- 364. doi: 10.1016/j.cja.2014.02.014
47	WU J, LU F, ZHANG J W, et al Design of task priority model and algorithm for imaging observation problem. Journal of Systems Engineering and Electronics, 2020, 31 (2): 321- 334. doi: 10.23919/JSEE.2020.000010
48	XI T, LI J F Research on rolling rescheduling method of imaging satellites for dynamic demand. Chinese Journal of Management Science, 2015, (S1): 269- 274.
49	ZHENG Z X, GUO J, GILL E Distributed onboard mission planning for multi-satellite systems. Aerospace Science and Technology, 2019, 89, 111- 122. doi: 10.1016/j.ast.2019.03.054
50	DANG V D, DASH R K, ROGERS A, et al Overlapping coalition formation for efficient data fusion in multi-sensor networks. Proc. of the 21st National Conference on Artificial Intelligence, 2006, 6, 635- 640.
51	GORADIA H J, VIDAL J M. An equal excess negotiation algorithm for coalition formation. Proc. of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, 2007: 1−3.
52	RAHWAN T, RAMCHURN S D, DANG V D, et al. Near-optimal anytime coalition structure generation. Proc. of the 20th International Joint Conference on Artificial Intelligence, 2007, 7: 2365–2371.
53	CHIEN S, SHERWOOD R, BURL M, et al A demonstration of robust planning and scheduling in the Techsat-21 autonomous sciencecraft constellation. Ear Nose & Throat Journal, 2014, 86 (8): 506- 511.
54	MARTIN M, KILBERG S, WINTER J TechSat 21 and revolutionizing space missions using microsatellites. Proc. of the 15th AIAA/USU Conference on Small Satellites, 2001, 1- 3.
55	TRUSZKOWSKI W, HALLOCK H L, ROUFF C, et al. Autonomous and autonomic systems with applications to NASA intelligent spacecraft operations and exploration systems. London: Springer-Verlag, 2009.
56	ZHENG Z X, GUO J, GILL E Onboard autonomous mission re-planning for multi-satellite system. Acta Astronautica, 2018, 145, 28- 43. doi: 10.1016/j.actaastro.2018.01.017
57	QIN J, LIU Y G, MAO X, et al Deadline based resource balancing task allocation for clustered heterogeneous LEO small satellite network. Proc. of the IEEE Military Communications Conference, 2013, 1825- 1831.
58	YAO M, ZHAO M Design of autonomous scheduling of small satellite tasks based on fuzzy neural network. Journal of Astronautics, 2007, 28 (2): 385- 388.
59	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 (11): 576- 588.
60	BONNET G, TESSIER C. Collaboration among a satellite swarm. Proc. of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, 2007: 1−8.
61	DAMIANI S, VERFAILLIE G, CHARMEAU M C An earth watching satellite constellation: how to manage a team of watching agents with limited communications. Proc. of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems, 2005, 455- 462.
62	SCHETTER T, CAMPBELL M, SURKA D Multiple agent-based autonomy for satellite constellations. Artificial Intelligence, 2003, 145 (1/2): 147- 180.
63	SMITH R G, DAVIS R Frameworks for cooperation in distributed problem solving. IEEE Trans. on Systems, Man, and Cybernetics, 1981, 11 (1): 61- 70. doi: 10.1109/TSMC.1981.4308579
64	XIANG S, CHEN Y G, LI G L, et al Review on satellite autonomous and collaborative task scheduling planning. Acta Automatica Sinica, 2019, 45 (2): 252- 264.
65	AGOGINO A, TUMER K Efficient agent-based cluster ensembles. Proc. of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems, 2006, 1079- 1086.
66	CHENG S W, JING C, SHEN L C, et al ECNP-based method of distributed dynamic task allocation for multiple observation satellite planning. Proc. of the 2nd International Conference on Advanced Computer Control, 2010, 4, 325- 328.
67	YANG W Y, LIU X L Multi-satellite autonomous coordination and mission planning based on dynamic contract network. Proc. of the 6th Annual Conference on High Resolution Earth Observation, 2019, 1- 28.
68	ZHANG Z Q. Research on mission planning and control of distributed imaging satellite system based on MAS. Changsha: National University of Defense Technolog, 2015. (in Chinese)
69	CHIEN S, SHERWOOD R, RABIDEAU G, et al The Techsat-21 autonomous space science agent. Proc. of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems: Part 2, 2002, 570- 577.
70	XUE Z J, YANG Z, LI J Satellite autonomous mission planning for emergencies. Command Control and Simulation, 2015, 37 (1): 24- 30.
71	WANG M C, LUO X, SONG Z M Design of double layer cooperative earth observation satellite constellation. Journal of Huazhong University of Science and Technology, 2018, 46 (2): 100- 105.
72	GAO L. Research on mission cooperation of earth observation distributed satellite. Changsha: National University of Defense Technology, 2009. (in Chinese)
73	LIN W C, LIAO D Y, LIU C Y, et al Daily imaging scheduling of an earth observation satellite. IEEE Trans. on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2005, 35 (2): 213- 223. doi: 10.1109/TSMCA.2005.843380
74	GLOVER F Tabu search—part I. ORSA Journal on Computing, 1989, 1 (3): 190- 206. doi: 10.1287/ijoc.1.3.190
75	GLOVER F Tabu search—part II. ORSA Journal on Computing, 1990, 2 (1): 4- 32. doi: 10.1287/ijoc.2.1.4
76	METROPOLIS N, ROSENBLUTH A W, ROSENBLUTH M N, et al Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 1953, 21 (6): 1087- 1092. doi: 10.1063/1.1699114
77	KIRKPATRICK S, GELATT C D, VECCHI M P Optimization by simulated annealing. Science, 1983, 220 (4598): 671- 680. doi: 10.1126/science.220.4598.671
78	HOLLAND J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Massachusetts: MIT Press, 1992.
79	CHEN H, ZHOU Y R, DU C, et al A satellite cluster data transmission scheduling method based on genetic algorithm with rote learning operator. Proc. of the IEEE Congress on Evolutionary Computation, 2016, 5076- 5083.
80	KENNEDY J, EBERHART R Particle swarm optimization. Proc. of the International Conference on Neural Networks, 1995, 4, 1942- 1948.
81	KENNEDY J, EBERHART R C A discrete binary version of the particle swarm algorithm. Proc. of the IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, 1997, 5, 4104- 4108.
82	BENSANA E, LEMAITRE M, VERFAILLIE G Earth observation satellite management. Constraints, 1999, 4 (3): 293- 299. doi: 10.1023/A:1026488509554
83	CHITTY D M. An evolved autonomous controller for satellite task scheduling. Proc. of the Genetic & Evolutionary Computation Conference, 2004. DOI: 10.1007/978-3-540-24854-5-5-23.
84	SUN Y R, WANG F Y, HAN Y P, et al Optimal algorithm for satellite autonomous operation task scheduling. Computer Engineering and Design, 2005, 26 (2): 461- 464.
85	MIAO Y, WANG F, ZHANG Y Q Autonomous mission planning of formation imaging satellites based on improved genetic algorithm. Optical Precision Engineering, 2017, 25 (12): 168- 179.
86	HE Q Z, TIAN Y, LI D C, et al Satellite imaging task planning using particle swarm optimization and tabu search. Proc. of the IEEE 21st International Conference on Software Quality, Reliability and Security Companion, 2021, 589- 595.
87	LI J T. Research on collaborative mission planning methods of autonomous multi-satellite—Take geostationary orbit and low-orbit satellites collaborative mission as example. Changsha: National University of Defense Technology, 2017. (in Chinese)
88	CHEN H, WU J J, SHI W Y, et al Coordinate scheduling approach for EDS observation tasks and data transmission jobs. Journal of Systems Engineering and Electronics, 2016, 27 (4): 822- 835. doi: 10.21629/JSEE.2016.04.11
89	GUO X B, LIU J C, ZHOU H B Research on distributed satellite system data transmission scheduling. Radio Communication Technology, 2016, 42 (4): 29- 32.
90	LI J, JING N, HU W D, et al A satellite schedulability prediction algorithm for EO SPS. Chinese Journal of Aeronautics, 2013, 26 (3): 705- 716. doi: 10.1016/j.cja.2013.04.058
91	LIU S, BAI G Q, CHEN Y W Prediction method for imaging task schedulability of earth observation network. Journal of Astronautics, 2015, 36 (5): 583- 588.
92	XING L N, WANG Y, HE Y M, et al An earth observation satellite method based on BP task schedulability prediction artificial network. Chinese Journal of Management Science, 2015, (S1): 117- 124.
93	DU Y H, WANG T, XIN B, et al A data-driven parallel scheduling approach for multiple agile earth observation satellites. IEEE Trans. on Evolutionary Computation, 2019, 24 (4): 679- 693.
94	HE Y M, XING L N, CHEN Y W, et al A generic Markov decision process model and reinforcement learning method for scheduling agile earth observation satellites. IEEE Trans. on Systems, Man, and Cybernetics: Systems, 2022, 52 (3): 1463- 1474.
95	WANG H J, YANG Z, ZHOU W G, et al Online scheduling of image satellites based on neural networks and deep reinforcement learning. Chinese Journal of Aeronautics, 2019, 32 (4): 1011- 1019. doi: 10.1016/j.cja.2018.12.018

Survey on autonomous task scheduling technology for Earth observation satellites

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 7

References 95

Related Articles 1

Recommended Articles

Metrics

Comments