2. 中国科学院大学电子电气与通信工程学院, 北京 100049
2. School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, Beijing 100049, China
SAR卫星具备全天时、全天候的地物信息获取能力,是一种不可或缺的对地观测手段[1],在洪涝预警[2]、舰船检测[3]、目标识别[4]、建筑物提取[5]等方面发挥着重要作用。近年来, 随着SAR卫星数量的增多及对地观测能力的持续增强,用户对遥感图像的时效性有了更高要求[6-7],采用多颗SAR卫星对地协同观测模式,从而充分发挥SAR卫星的观测能力,提高SAR图像的时效性和完整性,已成为一个亟需解决的问题。利用多颗SAR卫星协同对某一大面积区域目标进行观测,要求在给定的任务周期内合理制定SAR卫星的观测方案,从而获得最大的观测收益。
面向区域目标的多星协同观测问题是卫星任务规划与调度领域的新问题,也是运筹学领域的NP-Hard问题[8]。目前在求解该问题及其变种问题时,主要将求解步骤分为模型建立和算法设计两部分。Vasquez和Hao[9]对SPOT5卫星成像任务规划问题建立背包模型,采用禁忌搜索算法对模型进行求解;Gabrel和Vanderpooten[10]对面向点目标的单星成像任务规划问题建立无环图模型,采用基于标签的最短路径算法对模型进行求解;Lemaître等[11]对面向区域目标的单星任务规划问题建立了约束满足模型,并比较了贪婪算法、动态规划算法、约束规划算法、局部搜索算法的求解效率和求解质量;白保存[12]对点目标与区域目标混合存在的多星任务规划问题建立了任务合成的调度模型,采用动态合成启发式算法和快速模拟退火算法对模型进行求解;李曦[13]针对面向区域目标的多星任务规划问题,分别建立了时间覆盖率优先和空间覆盖率优先的模型,采用贪婪算法和遗传算法对其进行求解;阮启明[14]对面向区域目标的多星任务规划问题建立了调度模型,并采用贪婪随机变邻域搜索算法、禁忌搜索算法和模拟退火算法对模型进行求解;此外,He等[15]对地球观测卫星调度问题建立马尔可夫决策过程模型并采用强化学习方法对模型进行求解;针对统一调度无人机、飞艇、地面监控车辆和卫星等平台来观测目标区域的规划问题,Deng等[16]和李夏苗等[17]均提出了各自的两阶段协调规划方法;针对面向点目标的多星任务规划问题,Wu等[18]提出一种基于分而治之框架的元启发式算法;针对多星应急调度问题,伍国华等[19]提出一种考虑邻域结构动态调整的卫星应急调度算法。
上述模型大多为线性规划及约束满足模型,通常将卫星视场离散化来设计观测模式,不能处理大范围区域目标且观测模式数量受限;而算法大多是智能优化算法,在求解过程中易收敛于局部最优解。此外,现存的模型及算法并不能直接适用于本文要解决的问题。为此,针对面向区域目标的多颗SAR卫星协同观测问题,本文设计了一种基于区域目标网格化的观测模式,在处理大范围区域目标时根据网格动态生成观测模式,建立约束满足模型,采用改进的变邻域禁忌搜索算法,在搜索过程中设计并交替使用2种邻域结构,从而保证对不同有效解空间的搜索,以此获得更强的全局寻优能力。文中提及的卫星特指SAR卫星。
1 面向区域目标的多星协同观测问题描述在一个较短的任务周期内,采用M颗卫星协同观测一个大面积区域目标,由于区域过大或者卫星数量有限,在任务周期内无法完整观测整个区域,此时如何制定观测方案使得观测收益最大化,即本文要研究的面向区域目标的多星协同观测问题。由于该问题是一个高维度强耦合的组合优化问题,故此首先对其进行一些必要的假设和简化:1)目标区域是一个大范围区域目标,不考虑点目标和多目标观测问题;2) 执行观测任务的多颗卫星可以分布在不同轨道上,每颗卫星携带一部SAR,SAR采用正侧视模式,具备双侧成像能力;3)每个观测机会只能观测一个长度可变、宽度固定的条带区域;4)假设星载硬盘容量无穷大,即不考虑数据下传问题;5)如图 1所示,在观测收益与观测率之间建立分段线性函数[20]。
Download:
|
|
在任务周期内,每颗卫星都有若干个针对区域目标的观测机会。在一个观测机会中卫星通过选择不同的开始时间、结束时间和下视角可生成不同的观测模式。每个观测模式对应一个长度可变宽度固定的条带区域,当区域目标面积过大时需要多个观测机会才能完整观测。在求解面向区域目标的单星观测问题时,通常将区域目标并行分割成若干个条带区域,随后将这些条带分配到不同的观测机会。但这种并行分割的方式使得卫星在升轨和降轨中只能选择一种情况进行观测,观测任务的执行周期较长。由于本文的任务周期较短,执行观测任务的卫星无法完整观测区域目标,此时卫星在升轨和降轨时均要对区域目标进行观测。由于各个观测机会的星下点轨迹并不平行,如果不对观测方案进行优化,部分区域会被大量重复观测,而部分区域得不到观测。制定观测方案时首先根据卫星与区域目标的空间几何关系计算出各个观测机会的开始和结束时间,然后结合卫星的侧摆能力生成各个观测机会的观测模式集合。每个观测机会选择一个观测模式从而生成一个观测方案,观测方案的优劣由其对应的观测收益决定,优化目标即为在满足时间、角度、能量等约束条件下,最大化观测方案的观测收益。
2 面向区域目标的多星协同观测约束满足模型建立约束满足起源于人工智能领域,同时也在运筹学、逻辑规划等领域引起了广泛的关注[21]。约束满足可以对组合优化问题进行建模,其描述问题和解决问题的能力已经在规划与调度、机器视觉、集合覆盖等应用中得到了验证[22-23]。
定义1一个约束满足问题可以由一个四元组(V, D, C, Z)描述,其中:
1) V ={v1, v2, …, vi}是i个变量的有限集合;
2) D ={d(v1), d(v2), …, d(vi)}是i个变量的有限值域集合;
3) C={c1, c2, …, cj}是变量的有限约束集合,给出了V在D中的数学关系;
4) Z是有限目标函数集合。
求解一个约束满足问题就是在所有变量满足所有约束的情况下得到一个或多个方案。
2.1 基于区域目标网格化的观测模式为准确得到每个观测模式的观测率,在坐标系中将区域目标网格化。首先以特定的步长将区域目标分割成一组小正方形,随后在正方形的中心布点来代表正方形所在的区域(图 2)。用布尔向量P表示区域目标中离散点的集合
$ \boldsymbol{P}=\left\{p_1, p_2, \cdots, p_k, \cdots, p_\gamma\right\} . $ | (1) |
Download:
|
|
其中: γ表示区域目标中离散点的数量; pk表示P中的第k个点,pk=1表示该点已经被观测,pk=0表示该点未被观测。如果pk被观测到,则代表pk对应的区域已经被观测完毕,通过统计观测模式覆盖的点的数量就可以得到对应的观测率。
在一个观测机会中卫星通过选择不同的观测开始时间、观测结束时间和下视角可以生成不同的观测模式,上述3个参数均从连续空间取值,随之产生无数种观测模式。本文设计了一种从离散空间取值的基本观测模式近似代替所有的观测模式,以此将观测模式的数量控制在可接受范围之内。
定义2基本观测模式(图 2):如果P中存在3个点p1、p2、p3分别位于观测模式a对应条带区域的上边、侧边、下边,则观测模式a是一个基本观测模式。
需要指出的是只有3个点均满足所有约束条件才可以生成对应的基本观测模式,由于约束条件比较直观,这里不再详细描述。下文中观测模式特指基本观测模式。
2.2 约束满足模型1) 模型中各参数定义如下:Area是目标区域; z是任务的观测收益; x是任务的观测率; tS为任务开始时间; tE为任务结束时间; O={om 1 ≤m≤M}为观测机会集合, M是观测机会的数量; tms是om的起始时间; tme是om的结束时间; S={smn|1≤m≤M, 1≤n≤N}是观测模式集合,其中N是每个观测机会的观测模式数量; tmns是smn的起始时间; tmne是smn的结束时间; λmn是smn的下视角; Amn是smn观测到的区域; θmmax是om对应卫星的最大下视角; θmmin是om对应卫星的最小下视角; tm是om对应卫星的单次最大工作时长。
2) 函数
f: 观测收益z与观测率x之间的分段线性函数。Cov: 通过统计区域目标离散点数量而建立的面积计算函数。
3) 决策变量与值域
$ a_{m n}= \begin{cases}1, & \text { 执行观测模式 } s_{m n}, \\ 0, & \text { 不执行观测模式 } s_{m n} .\end{cases} $ | (2) |
4) 约束条件
观测模式数量约束:
$ \sum\limits_{n=1}^N a_{m n}=1, \quad 1 \leqslant m \leqslant M . $ | (3) |
每个观测机会只能选择一个观测模式,即卫星每次过境只能观测一个条带区域。
时间约束:
$ t_{\mathrm{S}} \leqslant t_m^s \leqslant t_m^e \leqslant t_{\mathrm{E}}, \quad 1 \leqslant m \leqslant M . $ | (4) |
$ t_m^s \leqslant t_{m n}^s \leqslant t_{m n}^e \leqslant t_m^e, 1 \leqslant m \leqslant M, 1 \leqslant n \leqslant N . $ | (5) |
观测机会和观测模式必须满足时间窗口约束。
角度约束:
$ \theta_m^{\min } \leqslant \lambda_{m n} \leqslant \theta_m^{\max }, \quad 1 \leqslant m \leqslant M, 1 \leqslant n \leqslant N . $ | (6) |
观测模式的下视角必须满足卫星的侧视能力约束。
能量约束:
$ t_{m n}^e-t_{m n}^{\mathrm{s}} \leqslant t_m, \quad 1 \leqslant m \leqslant M, 1 \leqslant n \leqslant N . $ | (7) |
由于卫星的能量有限,每个观测模式的观测时长必须在卫星能量允许范围内。
5) 目标函数
优化目标是在满足所有约束条件下获取最大的观测收益,该目标函数可表示为
$ z=\max f(x), $ | (8) |
$ x=\frac{\operatorname{Cov}\left(\cup_{m=1}^M \cup_{n=1}^N a_{m n} A_{m n}\right)}{\operatorname{Cov}(\text { Area })} . $ | (9) |
禁忌搜索算法(tabu search, TS)是一种基于局部搜索算法演变而来的全局逐步寻优算法,由Glover[24]首次提出,随后逐渐应用到各大领域[25-26]。禁忌搜索算法从一个选定的初始解开始搜索,根据邻域结构确定搜索范围,通过采用禁忌表和禁忌策略避免迂回搜索和反复计算,保证对不同有效解空间的搜索,以此引导算法逐渐向全局最优解前进。算法的核心在于设计初始解、邻域结构、藐视准则、禁忌对象、禁忌长度和终止准则。
传统禁忌搜索算法的邻域结构单一,易收敛于局部最优解,故此本文提出改进的变邻域禁忌搜索算法,在算法运行的过程中不断调整调整邻域结构,从而扩大搜索空间,寻找全局更优解。变邻域禁忌搜索算法设计如下:
初始解:随机生成一个初始解。
一步迭代邻域:在当前解的基础上随机选择h个观测机会,遍历1个观测机会中的N-1个观测模式可以得到N-1个候选解,遍历h个观测机会的h(N-1)个观测模式可以得到h(N-1)个候选解,将这h(N-1)个候选解作为当前解的邻域。
两步迭代邻域:在当前解的基础上随机选择2个未被禁忌的观测机会,同时改变2个观测机会的观测模式,可以得到N2-1个候选解,将这N2-1个候选解作为当前解的邻域。
藐视准则:从邻域的候选解中选择最优候选解,如果最优候选解优于当前最优解,则用其代替当前解和当前最优解,否则选择非禁忌状态的最优候选解作为当前解。
禁忌对象:每一代搜索选中一个最优候选解,将该解对应的观测机会作为禁忌对象加入禁忌表。
禁忌长度:禁忌长度要根据任务中观测机会的数量决定。
终止准则:指定总的CPU运行时间,超出时间则算法终止。
变邻域禁忌搜索算法流程如图 3所示。详细步骤如下:
Download:
|
|
步骤1 随机生成初始解,将初始解作为当前解和当前最优解。
步骤2 设置CPU运行时间和禁忌长度L、置空禁忌表,将代表邻域状态的二元变量s设置为0,设置切换邻域状态的迭代次数r。
步骤3 如果s为0,转步骤4,否则转步骤5。
步骤4 构造一步迭代邻域,随机选择h个观测机会,在当前解的基础上遍历h(N-1)个观测模式从而生成h(N-1)个邻域候选解,转步骤6。
步骤5 构造两步迭代邻域,随机选择2个未被禁忌的观测机会,在当前解的基础上遍历N2-1个观测模式从而生成N2-1个邻域候选解,转步骤6。
步骤6 从邻域候选解中选择最优候选解,如果最优候选解优于当前最优解,则用其代替当前解和当前最优解,否则选择非禁忌状态的最优候选解作为当前解。如果s为0,转步骤7,否则转步骤8。
步骤7 解禁禁忌长度为1的禁忌对象,将禁忌表中各禁忌对象的禁忌长度全部减1。禁忌步骤4中选中的观测机会,设置其禁忌长度为L,转步骤9。
步骤8 解禁禁忌长度为1和禁忌长度为2的禁忌对象,将禁忌表中各禁忌对象的禁忌长度全部减2。禁忌步骤5中选中的2个观测机会,设置其禁忌长度为L,转步骤9。
步骤9 如果步骤6中的当前最优解连续r代没有更新,则切换s的状态。
步骤10 如果CPU运行超时,则转步骤11,否则转步骤3。
步骤11 输出当前最优解。
在搜索过程中,构造一步迭代邻域可快速搜索邻近解空间,从而得到局部最优解;在此基础上构造两步迭代邻域有助于跳出局部最优解,从而保证对不同有效解空间的搜索。2种邻域交替使用可增强变邻域禁忌搜索算法的全局寻优能力。
4 仿真与分析 4.1 仿真参数计算机配置:11th Gen Intel(R) Core(TM) i7-11700 @2.50 GHz,机带RAM52.0 GHz,操作系统Windows10。
1) 数据准备:面向区域目标的多星协同观测问题暂无公开的标准数据集。本次实验根据第2节的多星协同观测约束满足模型构建约束集合,定义UTCG时间20220101T000000—20220102T000000为任务的调度周期,选择SAR卫星高分3号01、高分3号02、高分3号03、陆探1号01A、陆探1号01B组成卫星集合(表 1),5颗卫星的轨道参数从网站https://celestrak.com/获取。选择大小、纬度、形状都不相同的加蓬和白俄罗斯作为目标区域,目标区域的步长设置为12.48 km。任务调度周期内各卫星对加蓬及白俄罗斯的观测机会数量如表 2所示。
2) 算法对比:将本文变邻域禁忌搜索算法与文献[13]中的遗传算法和文献[27]中的禁忌搜索算法作对比。3种算法均采用第3节中的数据,以任务调度周期内获得的观测收益最大作为优化目标,在相同的CPU运行时间内对比观测收益。
4.2 仿真结果与分析图 4展示本文提出的变邻域禁忌搜索算法、文献[13]中的遗传算法、文献[27]中的禁忌搜索算法在CPU运行1 s内的迭代曲线,图 5展示CPU运行1 s时3种算法得到的最终观测方案。由图 4可知,相对于文献[27]中串行的禁忌搜索算法,文献[13]中并行的遗传算法可以得到一个质量较高的初始观测方案,但在迭代过程中易出现种群退化或停滞的情况,从而导致搜索过程进展缓慢或过早地结束搜索;文献[27]中的禁忌搜索算法从一个质量一般的随机初始观测方案开始搜索,其持续搜索全局最优观测方案的能力明显高于文献[13]中的遗传算法。相较于文献[27]中固定邻域模式的禁忌搜索算法,本文提出的变邻域禁忌搜索算法通过设计并交替使用2种不同的邻域模式,从而进一步地提高了算法的全局寻优能力,在相同的资源消耗下可以得到更高的观测收益。
Download:
|
|
Download:
|
|
对比图 5中CPU运行1 s时得到的最终观测方案可知,与文献[13]中的遗传算法相比,本文提出的随机变邻域禁忌搜索算法分别将白俄罗斯和加蓬的观测收益提高24.25 % 和32.70 %;与文献[27]中的禁忌搜索算法相比,本文提出的随机变邻域禁忌搜索算法分别将白俄罗斯和加蓬的观测收益提高8.78 % 和10.38 %。
上述结果表明,本文提出的变邻域禁忌搜索算法应用于面向区域目标的多星协同观测问题时,具有全局搜索能力较强,搜索效率较高的优点,并且显著提高了最终观测方案的观测收益。
5 结论多星协同观测问题的研究对于充分发挥卫星资源和快速获取区域目标的图像具有重要意义。本文分析采用多星协同模式观测区域目标的必要性,建立了多颗SAR卫星协同观测区域目标的约束满足模型,将区域目标网格化并以此设计观测模式,最后采用变邻域禁忌搜索算法对约束满足模型进行求解。仿真结果表明,相对于传统的遗传算法和禁忌搜索算法,本文设计的变邻域禁忌搜索算法搜索效率较高,持续搜索能力较强,得到的最终观测方案较优。但本文并未考虑卫星斜视和数据下传问题,此外多目标观测问题也有待进一步探究。
[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] |
Lema tre 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.
|