Observation scheduling problem for AEOS with a comprehensive task clustering

doi:10.23919/JSEE.2021.000029

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (2): 347-364.doi: 10.23919/JSEE.2021.000029

• INTELLIGENT OPTIMIZATION AND SCHEDULING • Previous Articles Next Articles

Observation scheduling problem for AEOS with a comprehensive task clustering

Zhongxiang CHANG^1,^2,^3,*(), Zhongbao ZHOU^1,²(), Feng YAO⁴(), Xiaolu LIU⁴()

¹ School of Business Administration, Hunan University, Changsha 410082, China
² Institute of Data Science and Decision Optimization, Hunan University, Changsha 410082, China
³ Department of Mathematics, Simon Fraser University, Surrey V3T 0A3, Canada
⁴ School of System Engineering, National University of Defense Technology, Changsha 410073, China

Received:2020-09-21 Online:2021-04-29 Published:2021-04-29
Contact: Zhongxiang CHANG E-mail:zx_chang@hnu.edu.cn;Z.B.Zhou@163.com;yaofeng@nudt.edu.cn;lxl_sunny_nudt@live.cn
About author:|CHANG Zhongxiang was born in 1990. He received his M.S. degree from National University of Defense Technology in 2016. Currently he is a Ph.D. student in Hunan University. His research interests include multi-objective optimization algorithm and some practical problems for managing complex systems, like observation scheduling problem for EOS(s) and satellite image data downlink scheduling problem. E-mail: zx_chang@hnu.edu.cn||ZHOU Zhongbao was born in 1977. He received his Ph.D. degree from National University of Defense Technology in 2006. Currently he is working in Hunan University as a professor. He is interested in all optimization applications and artificial intelligence, including observation scheduling problem for earth observation satellite, satellite image data downlink scheduling problem, performance evaluation and so on. E-mail: Z.B.Zhou@163.com||YAO Feng was born in 1978. He received his Ph.D. degree from National University of Defense Technology in 2013. Currently he is working in National University of Defense Technology as a professor. His research mainly focuses on management approaches for complex systems, including observation scheduling problem for EOS(s) and satellite image data downlink scheduling problem. E-mail: yaofeng@nudt.edu.cn||LIU Xiaolu was born in 1986. She received her Ph.D. degree from National University of Defense Technology in 2011. Currently she is working in National University of Defense Technology as an associate professor. Her research mainly focuses on artificial intelligence and metaheuristics, solving distribution management and scheduling problems for earth observation satellite. E-mail: lxl_sunny_nudt@live.cn
Supported by:
This work was supported by the China Scholarship Council;This work was supported by the China Scholarship Council

Abstract

Abstract:

Considering the flexible attitude maneuver and the narrow field of view of agile Earth observation satellite (AEOS) together, a comprehensive task clustering (CTC) is proposed to improve the observation scheduling problem for AEOS (OSPFAS). Since the observation scheduling problem for AEOS with comprehensive task clustering (OSWCTC) is a dynamic combination optimization problem, two optimization objectives, the loss rate (LR) of the image quality and the energy consumption (EC), are proposed to format OSWCTC as a bi-objective optimization model. Harnessing the power of an adaptive large neighborhood search (ALNS) algorithm with a nondominated sorting genetic algorithm II (NSGA-II), a bi-objective optimization algorithm, ALNS+NSGA-II, is developed to solve OSWCTC. Based on the existing instances, the efficiency of ALNS+NSGA-II is analyzed from several aspects, meanwhile, results of extensive computational experiments are presented which disclose that OSPFAS considering CTC produces superior outcomes.

Key words: observation scheduling, comprehensive task clustering (CTC), bi-objective optimization, image quality, energy consumption (EC)

Zhongxiang CHANG, Zhongbao ZHOU, Feng YAO, Xiaolu LIU. Observation scheduling problem for AEOS with a comprehensive task clustering[J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 347-364.

Figures/Tables 18

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Table 1

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Table 2

Fig.12

Fig.13

Table 3

Comparing results among CTC, CSEO and KSOA"

Scenario	CTC						CSEO						KSOA
Scenario	$ \check{{V}_{1}} $	$ \overline {{V}_{1}} $	$ \widehat{{V}_{1}} $	$ \check{{V}_{2}} $	$ \overline {{V}_{2}} $	$ \widehat{{V}_{2}} $	$ \check{{V}_{1}} $	$ \overline {{V}_{1}} $	$ \widehat{{V}_{1}} $	$ \check{{V}_{2}} $	$ \overline {{V}_{2}} $	$ \widehat{{V}_{2}} $	$ \check{{V}_{1}} $	$ \overline {{V}_{1}} $	$ \widehat{{V}_{1}} $	$ \check{{V}_{2}} $	$ \overline {{V}_{2}} $	$ \widehat{{V}_{2}} $
CD-50	0.2763	0.5746	0.9653	0.0015	0.0370	0.0786	0.6132	0.7716	0.9632	0.0011	0.0508	0.1001	0.2617	0.6005	0.9831	0.0015	0.2013	0.5258
CD-75	0.3827	0.6538	0.9760	0.0015	0.0374	0.0788	0.7262	0.8198	0.9747	0.0010	0.0512	0.0876	0.4482	0.7315	0.9845	0.0014	0.1504	0.4956
CD-100	0.4500	0.7162	0.9712	0.0029	0.0376	0.0807	0.7857	0.8738	0.9804	0.0008	0.0379	0.0744	0.4853	0.7516	0.9804	0.0013	0.3653	0.7486
CD-125	0.5793	0.7811	0.9867	0.0013	0.0307	0.0643	0.8042	0.8969	0.9843	0.0007	0.0325	0.0730	0.5518	0.7619	0.9843	0.0012	0.3651	0.7039
CD-150	0.5499	0.7669	0.9845	0.0023	0.0401	0.0846	0.8464	0.9144	0.9875	0.0006	0.0304	0.0631	0.5864	0.7923	0.9875	0.0011	0.3575	0.6531
CD-175	0.6318	0.8171	0.9817	0.0024	0.0348	0.0722	0.8747	0.9290	0.9897	0.0005	0.0272	0.0523	0.6103	0.8120	0.9892	0.0020	0.3736	0.6225
CD-200	0.6657	0.8448	0.9910	0.0010	0.0309	0.0748	0.8723	0.9273	0.9910	0.0005	0.0292	0.0576	0.6945	0.8553	0.9931	0.0010	0.3440	0.5764
CD-225	0.6964	0.8455	0.9966	0.0009	0.0350	0.0710	0.8892	0.9358	0.9930	0.0004	0.0279	0.0524	0.7110	0.8603	0.9933	0.0010	0.3234	0.5498
CD-250	0.7352	0.8845	0.9941	0.0009	0.0298	0.0685	0.9160	0.9568	0.9932	0.0004	0.0190	0.0427	0.7221	0.8657	0.9934	0.0011	0.2970	0.5740
CD-275	0.7329	0.8651	0.9936	0.0008	0.0346	0.0714	0.9157	0.9515	0.9936	0.0004	0.0215	0.0395	0.7498	0.8771	0.9968	0.0008	0.2814	0.4960
CD-300	0.7451	0.8860	0.9964	0.0009	0.0297	0.0694	0.9254	0.9649	0.9948	0.0003	0.0164	0.0416	0.7515	0.8760	0.9894	0.0020	0.3007	0.5185
CD-325	0.7683	0.8882	0.9958	0.0008	0.0309	0.0676	0.9340	0.9665	0.9949	0.0003	0.0151	0.0343	0.7559	0.8823	0.9927	0.0020	0.3099	0.4961
CD-350	0.7929	0.8956	0.9964	0.0007	0.0290	0.0606	0.9312	0.9639	0.9955	0.0003	0.0169	0.0362	0.7795	0.8866	0.9920	0.0019	0.3048	0.4716
CD-375	0.8020	0.8973	0.9971	0.0007	0.0302	0.0584	0.9352	0.9652	0.9958	0.0003	0.0171	0.0338	0.7908	0.8867	0.9956	0.0007	0.3041	0.4524
CD-400	0.7995	0.8992	0.9957	0.0007	0.0294	0.0646	0.9356	0.9614	0.9957	0.0003	0.0190	0.0362	0.8185	0.9178	0.9957	0.0007	0.2362	0.4006

Table 3

Fig.14

References 37

1	MCELROY J Observation of the Earth and its environment: survey of missions and sensors, third edition. EOS Transactions, 1996, 77 (31): 292. doi: 10.1029/96EO00211
2	CHANG Z X, CHEN Y N, YANG W Y, et al Mission planning problem for optical video satellite imaging with variable image duration: a greedy algorithm based on heuristic knowledge. Advances in Space Research, 2020, 66 (11): 2597- 2609. doi: 10.1016/j.asr.2020.09.002
3	WU G H, LIU J, MA M H, et al A two-phase scheduling method with the consideration of task clustering for earth observing satellites. Computers & Operations Research, 2013, 40 (7): 1884- 1894.
4	LIU X L, LAPORTE G, CHEN Y W, et al An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 2017, 86, 41- 53.
5	YANG W Y, CHEN Y N, HE R J, et al. The bi-objective active-scan agile Earth observation satellite scheduling problem: modeling and solution approach. Proc. of the IEEE Congress on Evolutionary Computation, 2018: 1–6.
6	LEMAITRE M, VERFAILLIE G, JOUHAUD F, et al Selecting and scheduling observations of agile satellites. Aerospace Science and Technology, 2002, 6 (5): 367- 381. doi: 10.1016/S1270-9638(02)01173-2
7	WANG J J, DEMEULEMEESTER E, HU X J, et al Exact and heuristic scheduling algorithms for multiple Earth observation satellites under uncertainties of clouds. IEEE Systems Journal, 2019, 13 (3): 3556- 3567. doi: 10.1109/JSYST.2018.2874223
8	WU K, ZHANG D X, CHEN Z H, et al Multi-type multi-objective imaging scheduling method based on improved NSGA-III for satellite formation system. Advances in Space Research, 2019, 63 (8): 2551- 2565. doi: 10.1016/j.asr.2019.01.006
9	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
10	LIU S K, YANG J. A satellite task planning algorithm based on a symmetric recurrent neural network. Symmetry, 2019. DOI: 10.3390/sym1111373.
11	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
12	BERGER J, LO N, BARKAOUI M. QUEST – a new quadratic decision model for the multi-satellite scheduling problem. Computers & Operations Research, 2020. DOI: 10.1016/j.cor.2019.104822.
13	NIU X N, TANG H, WU L X 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. doi: 10.1016/j.ijdrr.2018.02.013
14	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.
15	LONG X Y, WU S F, WU X F, et al. A GA-SA hybrid planning algorithm combined with improved clustering for LEO observation satellite missions. Algorithms, 2019. DOI: 10.3390/a12110231.
16	LONG J, CHEN S L, LI C. A task clustering method for multi agile satellite based on clique partition. Proc. of the 11th International Conference on Intelligent Computation Technology and Automation, 2018, 1: 332−336.
17	WANG S, JIN R, ZHU J D SuperView-1—China’s first commercial remote sensing satellite constellation with a high resolution of 0.5 m. Aerospace China, 2018, 19 (1): 30- 38.
18	HUANG W, SUN S R, JIANG H B, et al GF-2 satellite 1m/4m camera design and in-orbit commissioning. Chinese Journal of Electronics, 2018, 27 (6): 1316- 1321. doi: 10.1049/cje.2018.09.018
19	WANG S, ZHAO L, CHENG J H, et al Task scheduling and attitude planning for agile earth observation satellite with intensive tasks. Aerospace Science and Technology, 2019, 90, 23- 33. doi: 10.1016/j.ast.2019.04.007
20	PENG G S, DEWIL R, VERBEECK C, et al Agile earth observation satellite scheduling: an orienteering problem with time-dependent profits and travel times. Computers & Operations Research, 2019, 111, 84- 98.
21	ZHAO L, WANG S, HAO Y, et al Energy-dependent mission planning for agile Earth observation satellite. Journal of Aerospace Engineering, 2019, 32 (1): 04018118. doi: 10.1061/(ASCE)AS.1943-5525.0000949
22	PENG G S, SONG G P, XING L N, et al An exact algorithm for agile Earth observation satellite scheduling with time-dependent profits. Computers & Operations Research, 2020, 120, 104946.
23	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.
24	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, 2019, 31, 1051- 1078. doi: 10.1007/s10845-019-01518-4
25	XU Y J, LIU X L, HE R J, et al Multi-satellite scheduling framework and algorithm for very large area observation. Acta Astronautica, 2020, 167, 93- 107. doi: 10.1016/j.actaastro.2019.10.041
26	WANG X W, CHEN Z, HAN C Scheduling for single agile satellite, redundant targets problem using complex networks theory. Chaos, Solitons & Fractals, 2016, 83, 125- 132.
27	KIDD M P, LUSBY R, LARSEN J Equidistant representations: connecting coverage and uniformity in discrete biobjective optimization. Computers & Operations Research, 2020, 117, 104872.
28	DEB K, PRATAP A, AGARWAL S, et al A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation, 2002, 6 (2): 182- 197. doi: 10.1109/4235.996017
29	SRINIVAS N, DEB K Multi-objective function optimization using nondominated sorting genetic algorithms. Evolutionary Computation, 1995, 2 (3): 221- 248.
30	GONG M G, JIAO L C, YANG D D, et al Research on evolutionary multi-objective optimization algorithms. Journal of Software, 2009, 4 (2): 271- 289.
31	HAMACHER H W, PEDERSEN C R, et al Finding representative systems for discrete bicriterion optimization problems. Operations Research Letters, 2007, 35 (3): 336- 344. doi: 10.1016/j.orl.2006.03.019
32	ZHANG Q F, LI H MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2007, 11 (6): 712- 731. doi: 10.1109/TEVC.2007.892759
33	CORNE D, KNOWLES J. Techniques for highly multiobjective optimisation: some nondominated points are better than others. Proc. of the Genetic and Evolutionary Computation Conference, 2007: 773–780.
34	PURSHOUSE R C, FLEMING P J On the evolutionary optimization of many conflicting objectives. IEEE Trans. on Evolutionary Computation, 2007, 11 (6): 770- 784. doi: 10.1109/TEVC.2007.910138
35	WANG R, PURSHOUSE R C, FLEMING P J Preference-inspired coevolutionary algorithms for many-objective optimization. IEEE Trans. on Evolutionary Computation, 2013, 17 (4): 474- 494. doi: 10.1109/TEVC.2012.2204264
36	BRADSTREET L, WHILE L & BARONE L A fast incremental hypervolume algorithm. IEEE Trans. on Evolutionary Computation, 2008, 12 (6): 714- 723. doi: 10.1109/TEVC.2008.919001
37	DURILLO J J, NEBRO A J jMetal: A Java framework for multi-objective optimization. Advances in Engineering Software, 2011, 42 (10): 760- 771. doi: 10.1016/j.advengsoft.2011.05.014

Parameter	Meaning	Value
N_S	The population size of all solutions	100
N_Best	The population size of elitist solutions	50
N_A	The population size of archive solutions	100
MaxIter	The maximum number of iterations	200
R_S	The probability for selecting a ground target from AGT	0.3
R_BM	The probability of each ground target observed in the best image quality	0.7
T_R	The rate of the size of the taboo list to the total ground targets	0.1
removeRate	The rate of removing a ground target/task from a set of scheduled ground targets/tasks	0.6
insertRate	The rate of inserting a ground target into a given scheme	0.4
crossRate	The rate of the number of ground targets/tasks needed to be swapped to the number of scheduled ground targets/tasks	0.1
$ {\sigma }_{1} $	The score an operator will be added when the new solution generated by the operator dominates all current solutions	30
$ {\sigma }_{2} $	The score an operator will be added when the new solution generated by the operator dominates one of the current non-dominated solutions	20
$ {\sigma }_{3} $	The score an operator will be added when the new solution is generated by the operator in the current Pareto frontier	10
$ {\sigma }_{4} $	The score an operator will be added when the new solution generated by the operator is dominated by one of the current non-dominated solutions	0
$ \lambda $	The value of the reaction factor to control how sensitive the weights are to changes in the performance of operators	0.5

Scenario	RGHA		G		ALNS
Scenario	$ {R}_{p} $	$runT/{\rm{s}}$	$ {\mathit{G}}_{\mathit{p}} $ /%	$ {\mathit{G}}_{\mathit{t}} $ /%	$ \widehat{{R}_{p}} $	$ \overline {{R}_{p}} $	$ \check{{R}_{p}} $	$runT/{\rm{s}}$
WD-50	1.0000	0.0007	100	50	1.0000	1.0000	1.0000	0.0014
WD-100	0.9978	0.0011	100	1.08	0.9978	0.9978	0.9978	0.1018
WD-150	0.9985	0.0034	100	1.48	0.9985	0.9985	0.9985	0.2290
WD-200	0.9865	0.0031	99	1.20	0.9955	0.9955	0.9955	0.2585
WD-250	0.9748	0.0053	99	1.39	0.9820	0.9820	0.9820	0.3808
WD-300	0.9571	0.0078	99	1.46	0.9707	0.9707	0.9707	0.5356
WD-350	0.9542	0.0114	98	1.66	0.9697	0.9697	0.9697	0.6866
WD-400	0.9378	0.0152	98	1.77	0.9561	0.9561	0.9561	0.8595
WD-450	0.9087	0.02	96	1.68	0.9412	0.9423	0.9427	1.1898
WD-500	0.886	0.0258	96	1.96	0.9265	0.9273	0.9278	1.3140
WD-550	0.8755	0.0297	95	1.34	0.9228	0.9239	0.9248	2.2106
WD-600	0.8597	0.0362	94	1.65	0.9100	0.9107	0.9115	2.1887

Observation scheduling problem for AEOS with a comprehensive task clustering

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 18

References 37

Related Articles 1

Recommended Articles

Metrics

Comments