Agile Earth Observation Satellite Scheduling Algorithm for Emergency Tasks Based on Multiple Strategies

Abstract

During the execution of imaging tasks, satellites are often required to observe natural disasters, local wars, and other emergencies, which regularly interferes with the execution of existing schemes. Thus, rapid satellite scheduling is urgently needed. As a new generation of three degree-of-freedom (roll, pitch, and yaw) satellites, agile earth observation satellites (AEOSs) have longer variable-pitch visible time windows for ground targets and are capable of observing at any time within the time windows. Thus, they are very suitable for emergency tasks. However, current task scheduling models and algorithms ignore the time, storage and energy consumed by pitch. Thus, these cannot make full use of the AEOS capabilities to optimize the scheduling for emergency tasks. In this study, we present a fine scheduling model and algorithm to realize the AEOS scheduling for emergency tasks. First, a novel time window division method is proposed to convert a variable-pitch visible time window to multiple fixed-pitch visible time windows. Second, a model that considers flexible pitch and roll capabilities is designed. Finally, a scheduling algorithm based on merging insertion, direct insertion, shifting insertion, deleting insertion, and reinsertion strategies is proposed to solve conflicting problems quickly. To verify the effectiveness of the algorithm, 48 groups of comparative experiments are carried out. The experimental results show that the model and algorithm can improve the emergency task completion efficiency of AEOSs and reduce the disturbance measure of the scheme. Furthermore, the proposed method can support hybrid satellite resource scheduling for emergency tasks.

Keywords

Agile earth observation satellites / emergency tasks / merging insertion / shifting insertion

References

[1] Baek SW, Han SM, Cho KR, Lee DW, Yang JS, Bainum PM, Kim HD. Development of a scheduling algorithm and GUI for autonomous satellite missions. Acta Astronautica, 2011, 68(7): 1396-1402.

[2] Bianchessi N, Cordeau JF, Desrosiers J, Laporte G, Raymond V. A heuristic for the multi-satellite, multiorbit and multi-user management of Earth observation satellites. European Journal of Operational Research, 2007, 177(2): 750-762.

[3] Bunkheila F, Ortore E, Circi C. A new algorithm for agile satellite-based acquisition operations. Acta Astronautica, 2016, 123: 121-128.

[4] Chen H, Wu J, Shi W, Li J, Zhong Z. Coordinate scheduling approach for EDS observation tasks and data transmission jobs. Journal of Systems Engineering and Electronics, 2016, 27(4): 822-835.

[5] Cordeau JF, Laporte G. Maximizing the value of an Earth observation satellite orbit. Journal of the Operational Research Society, 2005, 56(8): 962-968.

[6] Cui K, Xiang J, Zhang Y. Mission planning optimization of video satellite for ground multi-object staring imaging. Advances in Space Research, 2018, 61(6): 1476-1489.

[7] Du B, Li S, She Y, Li W, Liao H, Wang H. Area targets observation mission planning of agile satellite considering the drift angle constraint. Journal of Astronomical Telescopes, Instruments, and Systems, 2018, 4(4): 047002

[8] Guo H, Zhu J, Ma M, Qiu D. Observing scheme adjustment method for agile imaging satellites to achieve environment dynamic monitoring. Research Journal of Chemistry and Environment, 2012, 16: 76-81.

[9] Habet D, Vasquez M, Vimont Y. Bounding the optimum for the problem of scheduling the photographs of an agile Earth observing satellite. Computational Optimization and Applications, 2010, 47(2): 307-333.

[10] Hao H, Jiang W, Li Y. Improved algorithms to plan missions for agile Earth observation satellites. Systems Engineering and Electronics, 2014, 25(5): 811-821.

[11] Hall N, Magazine M. Maximizing the value of a space mission. European Journal of Operational Research, 1994, 78(2): 224-241.

[12] He L, Liu X, Chen Y, Xing L, Liu K. Hierarchical scheduling for real-time agile satellite task scheduling in a dynamic environment. Advances in Space Research, 2019, 63(2): 897-912.

[13] He L, Liu X, Laporte G, Chen Y, Chen Y. An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 2018, 100: 12-25. Dec

[14] He Y, Chen Y, Lu J, Chen C, Wu G. Scheduling multiple agile Earth observation satellites with an edge computing framework and a constructive heuristic algorithm. Journal of Systems Architecture, 2019, 95: 55-66.

[15] Lemaître M, Verfaillie G, Jouhaud F, Lachiver J, Bataille N. Selecting and scheduling observations of agile satellites. Aerospace Science and Technology, 2002, 6(5): 367-381.

[16] Li G, Xing L, Chen Y. A hybrid online scheduling mechanism with revision and progressive techniques for autonomous Earth observation satellite. Acta Astronautica, 2017, 140: 308-321.

[17] Li Z, Li X. A multi-objective binary-encoding differential evolution algorithm for proactive scheduling of agile earth observation satellites. Advances in Space Research, 2019, 63(10): 3258-3269.

[18] Liu S, Hodgson ME. Satellite image collection modeling for large area hazard emergency response. ISPRS Journal of Photogrammetry and Remote Sensing, 2016, 118: 13-21.

[19] Liu X, Laporte G, Chen Y, He R. An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 2017, 86: 41-53. Oct

[20] Mao T, Xu Z, Hou R, Peng M. Efficient satellite scheduling based on improved vector evaluated genetic algorithm. Journal of Networks, 2012, 7(3): 517-523.

[21] Niu X, Tang H, Wu L. Satellite scheduling of large areal tasks for rapid response to natural disaster using a multi-objective genetic algorithm. International Journal of Disaster Risk Reduction, 2018, 28: 813-825.

[22] Niu X, Tang H, Wu L, Deng R, Zhai X (2015). Imaging-duration embedded dynamic scheduling of Earth observation satellites for emergent events. Mathematical Problems in Engineering: 1–31.

[23] Peng S, Chen H, Li J, Jing N (2017). Approximate path searching method for single-satellite observation and transmission task planning problem. Mathematical Problems in Engineering: 1–16.

[24] Qiu D, He C, Liu J, Ma M (2013). A dynamic scheduling method of Earth-observing satellites by employing rolling horizon strategy. The Scientific World Journal: 1–11.

[25] Roychowdhury S, Allen TT, Allen NB. A genetic algorithm with an earliest due date encoding for scheduling automotive stamping operations. Computers & Industrial Engineering, 2017, 105: 201-209.

[26] Song B, Yao F, Chen Y, Chen Y, Chen Y (2018). A hybrid genetic algorithm for satellite image downlink scheduling problem. Discrete Dynamics in Nature & Society: 1–11.

[27] Sun H, Xia W, Hu X, Xu C. Earth observation satellite scheduling for emergency tasks. Journal of Systems Engineering and Electronics, 2019, 30(5): 931-945.

[28] Wang J, Zhu X, Qiu D, Yang L. Dynamic scheduling for emergency tasks on distributed imaging satellites with task merging. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9): 2275-2285.

[29] Wang M C, Dai G, Vasile M (2014). Heuristic scheduling algorithm oriented dynamic tasks for imaging satellites. Mathematical Problems in Engineering: 1–11.

[30] Wang P, Reinelt G, Gao P, Tan Y. 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.

[31] Wang S, Zhao L, Cheng J, Zhou J, Wang Y. Task scheduling and attitude planning for agile Earth observation satellite with intensive tasks. Aerospace Science and Technology, 2019, 90: 23-33.

[32] Wu G, Ma M, Zhu J, Qiu D. Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks. Journal of Systems Engineering and Electronics, 2012, 23(5): 723-733.

[33] Xie P, Wang H, Chen Y, Wang P (2019). A heuristic algorithm based on temporal conflict network for agile Earth observing satellite scheduling problem. IEEE Access: 61024–61033.

[34] Xu R, Chen H, Liang X, Wang H. Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization. Expert Systems with Applications, 2016, 51: 195-206.

[35] Zhai X, Niu X, Tang H, Wu L, Shen Y (2015). Robust satellite scheduling approach for dynamic emergency tasks. Mathematical Problems in Engineering: 1–20.

[36] Zhu X, Sim KM, Jiang J, Wang J, Chen C, Liu Z. Agent-based dynamic scheduling for Earth-observing tasks on multiple airships in emergency. IEEE Systems Journal, 2017, 10(2): 661-672.