By analyzing the constraints of using multiple SAR satellites to observe a specific large area target, the constraint satisfaction model is established to maximize the observation profit within a given mission time horizon. To improve the global search capabilities of the traditional tabu search algorithm, an improved tabu search algorithm with the variable neighbourhood is proposed. In implementing the algorithm with variable neighbourhood, the area target is gridded to dynamically generate observation patterns, and the observation rates are calculated for each pattern. Compared to the traditional tabu search algorithm, the variable neighbourhood tabu search algorithm proposed in this paper increases the observation profit by more than 8% while maintaining the same computational burden.
ZHENG Qicun
,
YUE Haixia
,
LIU Dacheng
,
LI Hua
,
REN Mingshan
,
JIA Xiaoxue
. Multi-satellite cooperative observation method based on area target gridding[J]. Journal of University of Chinese Academy of Sciences, 2024
, 41(6)
: 803
-809
.
DOI: 10.7523/j.ucas.2023.019
[1] 邓云凯, 禹卫东, 张衡, 等. 未来星载SAR技术发展趋势[J]. 雷达学报, 2020, 9(1):1-33. DOI:10.12000/JR20008.
[2] 高龙, 阎福礼.基于Sentinel-1A SAR影像的上下游水位响应分析及其在洪涝预警中的应用[J].中国科学院大学学报, 2022, 39(1):91-101.DOI:10.7523/j.ucas.2020.0007.
[3] 闫成章, 刘畅. 基于显著性的SAR图像船舶目标检测方法[J]. 中国科学院大学学报, 2019, 36(3): 401-409. DOI: 10.7523/j.issn.2095-6134.2019.03.014.
[4] 李松, 魏中浩, 张冰尘, 等. 深度卷积神经网络在迁移学习模式下的SAR目标识别[J]. 中国科学院大学学报, 2018, 35(1):75-83. DOI:10.7523/j.issn.2095-6134.2018.01.010.
[5] 张妙然, 刘畅. 基于特征筛选和二级分类的极化SAR建筑提取算法[J]. 中国科学院大学学报, 2018, 35(1):89-95. DOI:10.7523/j.issn.2095-6134.2018.01.012.
[6] Chen Y X, Xu M Z, Shen X, et al. A multi-objective modeling method of multi-satellite imaging task planning for large regional mapping[J]. Remote Sensing, 2020, 12(3): 344. DOI:10.3390/rs12030344.
[7] Ji H R, Huang D. A mission planning method for multi-satellite wide area observation[J]. International Journal of Advanced Robotic Systems, 2019, 16(6): 172988141989071. DOI:10.1177/1729881419890715.
[8] Karpiński M. Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete[J]. Theoretical Computer Science, 2017, 659: 88-94.DOI: 10.1016/j.tcs.2016.10.011.
[9] Vasquez M, Hao J K. A “logic-constrained” knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite [J]. Computational Optimization and Applications, 2001, 20(2): 137-157.DOI: 10.1023/A:1011203002719.
[10] Gabrel V, Vanderpooten D. Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite[J]. European Journal of Operational Research, 2002, 139(3): 533-542.DOI:10.1016/S0377-2217(01)00188-6.
[11] Lematre M, Verfaillie G, Jouhaud F, et al. Selecting and scheduling observations of agile satellites[J]. Aerospace Science and Technology, 2002, 6(5): 367-381. DOI: 10.1016/S1270-9638(02)01173-2.
[12] 白保存. 考虑任务合成的成像卫星调度模型与优化算法研究[D]. 长沙: 国防科学技术大学, 2008.
[13] 李曦. 多星区域观测任务的效率优化方法研究[D]. 长沙: 国防科学技术大学, 2005.
[14] 阮启明. 面向区域目标的成像侦察卫星调度问题研究[D]. 长沙: 国防科学技术大学, 2006.
[15] 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[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52(3): 1463-1474. DOI: 10.1109/TSMC.2020.3020732.
[16] Deng M, Liu B J, Li S M, et al. A two-phase coordinated planning approach for heterogeneous earth-observation resources to monitor area targets[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(10): 6388-6403. DOI: 10.1109/TSMC.2019.2962205.
[17] 李夏苗, 廖文昆, 伍国华, 等. 基于两阶段迭代优化的空天观测资源协同任务规划方法[J]. 控制与决策, 2021, 36(5): 1147-1156. DOI: 10.13195/j.kzyjc.2019.1193.
[18] Wu G H, Luo Q Z, Du X, et al. Ensemble of metaheuristic and exact algorithm based on the divide-and-conquer framework for multisatellite observation scheduling[J]. IEEE Transactions on Aerospace and Electronic Systems, 2022, 58(5): 4396-4408. DOI: 10.1109/TAES.2022.3160993.
[19] 伍国华, 杜潇, 王心慰, 等. 考虑邻域结构动态调整的多星应急调度算法[J]. 控制与决策, 2022, 37(7): 1685-1694. DOI: 10.13195/j.kzyjc.2021.0320.
[20] Cordeau J F, Laporte G. Maximizing the value of an Earth observation satellite orbit[J]. Journal of the Operational Research Society, 2005, 56(8): 962-968. DOI: 10.1057/palgrave.jors.2601926.
[21] Kumar V. Algorithms for constraint-satisfaction problems: a survey[J]. AI Magazine, 1992, 13(1): 32-44.DOI: 10.1609/aimag.v13i1.976.
[22] 牛鹏飞, 王晓峰, 芦磊, 等. 随机约束满足问题相变研究综述[J]. 计算机工程与科学, 2022, 44(7):1321-1330. DOI:10.3969/j.issn.1007-130X.2022.07.021.
[23] Nonobe K, Ibaraki T. A tabu search approach to the constraint satisfaction problem as a general problem solver[J]. European Journal of Operational Research, 1998, 106(2/3): 599-623. DOI: 10.1016/S0377-2217(97)00294-4.
[24] Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computers & Operations Research, 1986, 13(5): 533-549. DOI: 10.1016/0305-0548(86)90048-1.
[25] 王维琼, 许豪杰, 崔萌, 等. 优良布尔函数的混合禁忌搜索算法[J]. 通信学报, 2022, 43(5): 133-143. DOI: 10.11959/j.issn.1000-436x.2022096.
[26] 奇格奇, 邹恺杰, 邹婕, 等. 面向异质化需求的无人驾驶电动公交接驳路径优化[J]. 清华大学学报(自然科学版), 2022, 62(7): 1178-1185. DOI: 10.16511/j.cnki.qhdxxb.2022.26.001.
[27] 刘翔春. 空间目标光学监视卫星轨道设计及任务规划[D]. 长沙: 国防科技大学, 2018.
