基于任务分解的多星成像规划模型建立与求解

朱政霖 马广彬 黄鹏 林友明

(1 中国科学院遥感与数字地球研究所，北京 100094) (2 中国科学院大学，北京 100049)

多星成像规划是指在使用多颗成像卫星的前提下，考虑卫星性能指标、星上遥感器成像能力等因素的影响，合理安排卫星，制定成像方案，发送卫星指令，在一定的成像时间内尽可能多地对地面目标区域成像[1-2]。多星成像规划能对卫星资源进行合理分配，更好地利用遥感器，对优化卫星系统整体性能、发挥最大综合效益具有重要意义[3-4]。多星成像规划问题是一类大规模组合优化问题，常规求解算法通常无法在较短的时间内得出较优的解。这是因为：卫星在一定时间内经过目标区域上空的次数有限，而只有经过目标区域上空时才能对其成像。同时，对于星下点轨迹周围的目标区域，要通过侧摆的方式成像[5]，这就需要有足够的时间调整侧摆姿态，因此在进行成像规划时应考虑有充足的侧摆转换时间。而且，多颗卫星对同一组目标区域成像，各个目标区域会有多个可供选择的时间窗，每个目标区域可在多个时间窗内成像，大大增加了成像规划的复杂度[6-7]。另外，不同卫星的性能指标存在差异，建立统一的模型描述不同的性能指标较为困难。

对于多星成像规划，国内外已有大量研究[8-9]，通常包括规划模型的建立和求解两部分。目前，卫星的性能指标基本包括星上存储容量、电能、遥感器开关机时间、侧摆转换时间等，因此，基于性能指标建立的模型基本一致，但求解算法不同。常见的求解算法包括：①基于先验信息对各个任务节点进行评价的算法。其中，较为典型的是文献[10]中提出的基于贪心算法的调度方案：首先对所有待成像目标区域，根据其权值、与其他任务的冲突程度、占用时间窗的长短等因素进行评价，优先安排评价值较高的目标区域。此类算法根据先验信息对任务进行调度，但利用先验信息作为任务分配的标准易造成规划结果与最优解的偏离程度较大。②全局搜索算法。首先建立全部约束条件，然后利用现有软件在整个解空间进行搜索。其中，较为典型的是文献[11]中提出的尝试性全局搜索算法，该算法首先建立模型约束，在不考虑约束的情况下对组合问题利用现有的商用求解软件CPLEX进行求解，如果得到的解不满足某一约束，就在模型中添加当前解不满足的约束，重新求解，直至得到的解满足所有约束条件。此类算法从整个解空间搜索最优解，得到的解质量较高，但搜索空间过大，耗时过长。

基于以上，本文提出一种任务分解的思路，将成像规划过程分为两部分，首先通过免疫算法把成像点目标分配给卫星，然后针对每颗卫星分配到的成像点目标进行规划求解，并把当前分配方案能够成像的点目标权值总和作为反馈信息传递给免疫算法，根据反馈信息调整当前分配方案，使调整后的分配方案能够拍摄到的成像点目标权值总和增大，提高免疫算法分配成像点目标方案的合理程度。该算法采取反馈的思路处理成像点目标分配与单颗卫星调度的关系，避免根据先验信息分配成像点目标造成的分配方案不合理，同时将求解算法分为成像点目标分配和单轨道圈次调度两部分，能够减小解的搜索空间，降低算法的时间复杂度。

1 多星成像规划模型

本文研究的多星成像规划问题可简述为：有一系列光学卫星和雷达卫星，面对大量不同权值的成像点目标(指范围较小的目标，可被遥感器单次覆盖)，每个成像点目标有多个时间窗，如何在满足侧摆转换时间、最大侧摆次数的前提下，为每颗卫星合理分配成像点目标，并确定卫星每个轨道圈次的动作序列，使得成像点目标的权值总和最大。对于多星成像规划，需要考虑的限制因素较多。本文对相关限制因素进行归纳总结，重点考虑卫星侧摆次数约束、侧摆转换时间约束、电能约束和星上存储容量约束，并以此建立成像规划模型。

在以往的多星成像规划研究中，通常以单颗卫星作为调度单位，且认为每个成像点目标在调度时间内只能被该卫星观测一次[12]。但随着调度时间的增长，同一颗卫星将会多次经过成像点目标的上方，这将造成每个成像点目标在整个调度时间内有多个时间窗，对模型的建立与求解造成困难。为此，本文以卫星的每个轨道圈次为调度单位，确保每个成像点目标在单个调度单位里只有一个时间窗。此外，卫星的电能来源是太阳电池阵，在每个轨道圈次内获得的电能是一定的；与地面站数据传输时，能够方便计算出每个轨道圈次的存储容量。因此，以每个轨道圈次为调度单位，能够方便建立电能和存储容量约束。

卫星通过侧摆的方式成像，由于侧摆会对其稳定性造成影响[13]，因此卫星在每个轨道圈次内的侧摆次数不得超过侧摆次数的最大值。此外，卫星执行成像任务需要的电量随成像时间的增长而增多，点目标成像时间较短，成像消耗的电能较少，而卫星每个轨道圈次只能获取一定的电量，通过限制卫星的单轨道圈次侧摆次数，能够同时满足电能约束。另外，卫星只会在成像时增加星上存储容量的占用，占用的存储容量随成像时间的增长而增加，而点目标成像时间较短，因此占用的存储容量较少，不会出现存储容量不足的问题。

对于成像点目标集合{R1,R2,R3,…}和轨道圈次集合{C1,C2,C3,…}，本文建立多星成像规划模型如下。

(1)

式中：xij为决策变量，xij=1表示在轨道圈次Cj对点目标Ri成像；Wi为成像点目标Ri的权值；NR为成像点目标总数；NC为轨道圈次总数；i=1,2,3,…,NR；j=1,2,3,…,NC。

(2)

(3)

式中：Mj为轨道圈次Cj内最大侧摆次数。

Twe,ij+Ttrans(i,i+1)≤Tws,(i+1)j

xij=1,x(i+1)j=1,Twe,ij≤Tws,(i+1)j

(4)

式中：Twe,ij为轨道圈次Cj内卫星遥感器对点目标Ri成像结束时间；Tws,(i+1)j为轨道圈次Cj内对点目标Ri+1成像开始时间；Ttrans(i,i+1)为Twe,ij和Tws,(i+1)j的时间间隔，也就是卫星遥感器的侧摆转换时间，见式(5)。

Ttrans(i,i+1)=Tsc,j+Tso,j+

|θ(i+1)j-θij|/Vsr,j+Tss,j

(5)

式中：Tsc,j，Tso,j，Tss,j为轨道圈次Cj内卫星遥感器的关闭时间、开启时间和稳定时间；|θ(i+1)j-θij|/Vsr,j为卫星遥感器的侧摆角度改变时间，其中，θ为侧摆角，Vsr,j为卫星遥感器的侧摆转换速率。

式(1)是优化目标，多星成像规划问题的目标是选择适当的决策变量，使得成像点目标权值总和最大。式(2)是任务排它性约束，即每个成像点目标只能被分配到一个特定轨道圈次内或者不被分配。式(3)代表侧摆次数约束，卫星遥感器通过侧摆的方式成像，在成像点目标较为稀疏的情况下，每次侧摆只能对一个点目标成像。式(4)是侧摆转换时间约束，对于分配到同一轨道圈次的成像点目标，对一个点目标成像的结束时间与对下一个点目标成像的开始时间的时间间隔，必须不小于侧摆转换时间。式(5)是侧摆转换时间的表达式，转换时间等于同一轨道圈次内卫星遥感器的关闭时间、开启时间、侧摆角度改变时间和稳定时间的总和。

求解本文建立的多星成像规划模型的难点在于：该模型是一个组合优化模型，约束较为复杂，直接求解较为困难，且随着任务规模的增大，求解的组合数将呈指数式增加。为解决这一问题，本文将求解分为两部分：①成像点目标分配。将成像点目标按照一定的规则分配给不同的轨道圈次；②单轨道圈次调度。针对每个轨道圈次分配的成像点目标，在满足最大侧摆次数约束、转换时间约束的前提下，计算出所有轨道圈次能够成像的点目标权值总和。这样就可以对组合优化模型进行分解，以减小求解的搜索空间。不过，这种求解算法存在耦合问题，即成像点目标分配和单轨道圈次调度具有耦合性，采用不同的成像点目标分配方案将影响单轨道圈次调度的结果。因此，将成像点目标分配和单轨道圈次调度作为各自独立的过程，将导致与最优解的偏离程度过大，任务调度的效果难以保证。为此，本文综合考虑成像点目标分配和单轨道圈次调度，提出求解算法，如图1所示。

本文首先将成像点目标分配给各轨道圈次，然后将各轨道圈次分配到的成像点目标通过单轨道圈次调度，计算出各轨道圈次可成像点目标权值的总和，将总和作为反馈信息，传递给成像点目标分配，根据反馈信息调整分配方案，使所有可成像点目标的权值总和随着迭代次数的增加而增大。

1.1 成像点目标分配

免疫算法是根据生物免疫系统原理提出的一种新的智能优化算法，它是一种启发式搜索算法，与全局搜索算法相比，效率较高[14-15]。免疫算法把确定性和随机性相结合，将目标函数作为免疫反应中的抗原，可行解作为免疫反应中的抗体，可行解的质量对应抗原与抗体的亲和度，将目标优化问题转换为求解最佳抗体的问题。该算法具有全局搜索能力强、多样性保持良好和鲁棒性强等优点[16]。采用免疫算法求解成像点目标分配问题，能够对较大的解空间进行智能搜索，使搜索方向快速向最优解靠近；同时，能够避免搜索进入局部最优解区域，最终能得出尽可能优的组合方案。免疫算法求解成像点目标分配问题的流程如图2所示。

在免疫算法求解成像点目标分配问题中，构造抗体时，针对成像点目标Ri，如果在某一轨道圈次有时间窗，则Ri可分配至该轨道圈次，Ri可分配至的轨道圈次构成集合{Cj|∃[Tws,ij,Twe,ij]}。构造抗体时，针对Ri，从轨道圈次集合中随机选取轨道圈次Si={Cj|∃[Tws,ij,Twe,ij]}，所有成像点目标选取的轨道圈次集合Ω={S1,S2,…,SNT}构成初始抗体。例如，抗体{4,6,3}表示R1分配至轨道圈次4，R2分配至轨道圈次6，R3分配至轨道圈次3。多个初始抗体构成初始抗体种群{Ω1,Ω2,…,ΩNΩ}，NΩ表示抗体种群的抗体个数。每个抗体对应一种成像点目标分配方案，抗体种群对应所有分配方案。特定抗体激励度与成像点目标分配方案在所有分配方案中的重复程度呈反比，与成像点目标分配方案的评价值呈正比。因此，合理且不重复的分配方案激励度较高，取激励度前NP/2个抗体，能保留较优的分配方案，同时淘汰较差的分配方案。经过多次迭代后，可使分配方案的合理程度越来越高。

1.2 单轨道圈次调度

经过第1.1节的成像点目标分配，所有成像点目标均被分配到特定的轨道圈次中。本节要解决的问题是，针对某一轨道圈次的所有成像点目标，如何安排卫星成像，使成像点目标的权值总和最大。另外，在免疫算法中，每轮迭代都要进行所有轨道圈次的调度运算，因此，对单轨道圈次调度的耗时具有较高的要求，需要在较短的时间内完成。为满足各种约束，本文采用图论模型求解。用图的节点表示被分配的成像点目标，用图的有向线段表示各个点目标成像之间的卫星遥感器侧摆转换时间约束，边的权值表示成像点目标的权值，侧摆次数的约束用路径包含的最多节点数表示，最终将求解成像点目标权值总和最大的问题，转换为节点总数不超过特定值时图的最长路径问题。转换方式为：将所有被分配至该轨道圈次的成像点目标{Ri}(分配至某轨道圈次的成像点目标集合，下同),按照成像开始时间的先后顺序排序，并用图的节点vi依次表示各个成像点目标，形成成像点目标节点序列{v1,v2,v3,…,vN}(N=|{Ri}|)；在节点序列的首尾依次添加2个虚节点v0，vN+1，表示开始节点和结束节点。存在vi指向vj的有向边的条件为

(6)

式中：E(i,j)为1，表示vi和vj之间存在有向边，此时应满足的条件是节点i结束时间与节点j开始时间的时间间隔大于卫星遥感器的侧摆转换时间，转换时间见式(5)。

另外，对于开始节点v0，存在该节点指向所有成像点目标节点的有向边，表示成像任务可以从任何一个成像点目标节点处开始；对于结束节点vN+1，存在所有成像点目标节点指向该节点的有向边，表示成像任务可以在任何一个成像点目标节点成像后终止。有向边权值的计算方法如下。

(7)

每个边的权值表示该有向边所指向的成像点目标节点的权值，结束节点的权值为0。

基于以上，建立单轨道圈次调度问题的约束优化模型为

(8)

式中：h1,h2,h3,…,hNh为求解的成像点目标节点序列；Nh为成像点目标节点序列中的成像点目标节点总数。

s.t.Nh≤MjNh=|{hi}|

(9)

1≤h1

(10)

E(h1,hi+1)=1i∈{1,2,3,…,Nh-1}

(11)

式(8)为目标函数，表示成像点目标节点序列的权值总和最大。式(9)表示成像点目标节点序列中的成像点目标节点个数不超过最大侧摆次数。式(10)表示成像点目标节点序列是被分配至该轨道圈次所有成像点目标节点的一个有序子集。式(11)表示成像点目标节点序列中相邻2个成像点目标节点存在有向边相连。

通过以上转换，将单轨道圈次调度问题转化为一个有向无环图的最长路径问题。对有向无环图最长路径的求解，当前已有大量的成熟算法。但是，本文研究的难点在于求解带有约束条件的有向无环图的最长路径问题。为此，引入网树算法[17-18]，并对该算法进行改进，提出一种以路径节点数为约束条件的有向无环图最长路径求解算法。算法的基本思路为：利用动态规划算法的思路，针对每个节点总数，依次计算以有向图的每个节点为最后一个成像点目标节点的最长路径，计算公式如下。

Pm,k=We(i,k)+max{Pm-1,k}

i∈{1,2,…,k-1},E(i,k)=1

(12)

式中：Pm,k为最后一个成像点目标节点为k、成像点目标节点总数为m的所有路径中最长路径的权值。

最长路径求解算法流程如图3所示。设成像点目标节点总数为1，依次计算成像点目标节点总数为1的所有路径的最大权值，当成像点目标节点总数小于最大侧摆次数时，将成像点目标节点总数加1；重复上述过程，直至成像点目标节点总数等于最大侧摆次数，此时，以每个成像点目标节点为最后一个成像点目标节点的所有路径的最大权值max{Pm,i} (i∈{1,2,…,Nh})，就是卫星单轨道圈次内最大可成像点目标权值总和。

2 测试结果与分析

在多星成像规划领域，至今尚无公开的标准测试集[19]。本文随机生成一组测试数据对本文算法进行测试。在我国所在的经纬度范围内随机依次抽取100，200，300，400个成像点目标，各个成像点目标的权值从[1,9]中均匀选取，成像点目标的权值表示其重要程度，性能较优的算法能够使成像点目标的权值总和尽可能大。选取5颗光学卫星作为测试卫星，规划的时间周期为24 h，卫星与成像点目标的时间窗采用STK软件计算获取。每个成像点目标的成像持续时间约为5 s。

为验证本文算法的性能，将计算结果与文献[11]中的全局搜索算法、文献[20]中蚁群-禁忌搜索算法作比较。3种算法均以上文所述测试数据集为测试对象，测试硬件均采用Intel Xeon CPU E31225，16GB RAM平台。文献[11]中提出的全局搜索算法采用整数规划模型直接求解，采用暴力求解的方式在整个解空间内搜索全局最优解。文献[20]中采用的蚁群-禁忌搜索算法，通过成像点目标分配和单颗卫星调度相互迭代求解，与本文算法类似。蚁群-禁忌搜索算法和本文算法的参数取值如表1所示，全局搜索算法采用暴力算法对模型直接求解，不涉及参数取值的问题。测试时，每组测试数据用3种算法测试多次，结果取平均值，以减小随机误差，如表2所示。图4(a)是4颗卫星时3种算法求解耗时与成像点目标数的关系，图4(b)是4颗卫星时3种算法获得的成像点目标权值总和与成像点目标数的关系。

表1 蚁群-禁忌搜索算法和本文算法参数取值Table 1 Parameters of ant colony-tabu searchalgorithm and the algorithm proposed in this paper

表2 3种算法仿真测试结果对比Table 2 Contrast of 3 algorithm simulation test results

根据表2和图4，对比本文算法与蚁群-禁忌搜索算法的结果可知：当成像点目标数较小(约为100个)时，蚁群-禁忌搜索算法的耗时与本文算法相当，平均约为12 s，成像点目标权值总和基本一致。当成像点目标数大于等于200时，蚁群-禁忌搜索算法的耗时为本文算法的1.5～3.0倍。随着成像点目标数越来越多，蚁群-禁忌搜索算法的耗时将大幅增加，本文算法的时间优势更为明显。从权值上看，本文算法有6个权值大于蚁群-禁忌搜索算法，3个小于蚁群-禁忌搜索算法，说明本文算法得到的权值总和略优于蚁群-禁忌搜索算法。

全局搜索算法要对整个解空间进行遍历求解，能够遍历所有可行解，因此得出的解对应的成像点目标权值总和较高；但其缺点是耗时较多，当成像点目标数较多时，采用该算法不能在可接受的时间范围内得出结果。从成像点目标的权值总和来看，全局搜索算法略优于本文算法；但从时间上看，本文算法的耗时只是全局搜索算法的10%～30%。图4(a)中的曲线显示，全局搜索算法的耗时随着成像点目标数的增加呈指数式增长，极大限制了它的实际应用。

以上分析表明：与蚁群-禁忌搜索算法相比，本文算法的求解耗时明显较短，且成像点目标权值总和略高；全局搜索算法虽然能得出成像点目标权值总和较高的规划方案，但存在耗时过长的问题，本文算法在耗时方面具有较大的优势，且耗时并不会随问题规模的增大而显著增加。因此，本文算法能在较短的时间内求解模型，且得出较优的解。本文模型适用性较强，能够成功解决多星成像规划问题。

3 结束语

本文对多星成像规划问题进行研究，根据卫星成像的实际情况，建立成像规划模型，将求解分为成像点目标分配和单轨道圈次调度两部分，减小搜索空间，在逐次迭代的过程中，将单轨道圈次调度结果作为反馈信息，不断调整成像点目标分配方案，使规划结果尽可能接近全局最优解。成像点目标分配采用免疫算法，有较强的全局搜索能力，能够很好地保持解的多样性，避免搜索进入局部最优解。单轨道圈次调度采用图的最长路径算法，能够在考虑侧摆次数约束的情况下输出该轨道圈次所能成像点目标的最大权值，且具有较低的时间复杂度。测试结果表明：本文模型能够得出相对较优的规划结果，且效率较高。尤其在问题规模较大的情况下，本文提出的模型求解算法效率优势更加明显。

参考文献(References)

[1] 陈克伟，安蓓，王炎娟，等.基于PDDL的成像卫星任务规划建模[J].兵工自动化,2008,27(12):41-44

Chen Kewei, An Bei, Wang Yanjuan, et al. Modeling of mission planning for imaging satellite based on PDDL [J]. Ordnance Industry Automation, 2008, 27(12): 41-44 (in Chinese)

[3] 贺川，孟宪贵，祝转民，等.基于执行时段滑动调整策略的中继卫星任务规划算法设计[J].飞行器测控学报,2015,34(3):246-253

He Chuan, Meng Xiangui, Zhu Zhuanmin, et al. Design of mission programming algorithm for TDRS based on execution time slide adjustment strategy [J]. Journal of Spacecraft TT&C Technology, 2015, 34(3): 246-253 (in Chinese)

[4] 张倩，赵砚，徐梅.卫星星座的空域覆盖性能计算模型[J].飞行器测控学报,2011,30(1):6-10

Zhang Qian, Zhao Yan, Xu Mei. Computation model of constellation space coverage performance [J]. Journal of Spacecraft TT&C Technology, 2011, 30(1): 6-10 (in Chinese)

[5] 白保存，贺仁杰，李菊芳，等.面向点及区域目标的遥感卫星任务调度[J].国防科技大学学报,2009,31(2):59-63

Bai Baocun, He Renjie, Li Jufang, et al. Remote sensing satellites observing scheduling toward spot and ploygon targets [J]. Journal of Nation University of Defense Technology, 2009, 31(2): 59-63 (in Chinese)

[6] 王智勇，王永强，王钧，等.多星联合任务规划方法[J].中国空间科学技术,2012,32(1):8-14

Wang Zhiyong, Wang Yongqiang, Wang Jun, et al. Multi-satellite task scheduling method [J]. Chinese Space Science and Technology, 2012, 32(1): 8-14 (in Chinese)

[7] 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

[8] 王建江，朱晓敏，吴朝波，等.面向应急条件的多星动态调度方法[J].航空学报,2013,34(5):1151-1164

Wang Jianjiang, Zhu Xiaomin, Wu Chaobo, et al. Multi-satellite dynamic scheduling method for emergency condition [J]. Acta Aeronautica et Astronautica Sinica, 2013, 34(5): 1151-1164 (in Chinese)

[9] Zhu K J, Li J F, Baoyin H X. Satellite scheduling considering maximum observation coverage time and minimum orbital transfer fuel cost [J]. Acta Astronautica, 2010, 66(1/2): 220-229

[10] Wang X W, Chen Z, Han C. Scheduling for single agile satellite, redundant targets problem using complex networks theory [J]. Chaos Solitons and Fractals, 2016, 83: 125-132

[11] Wang J J, Demeulemeester E, Qiu D, et al. A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds [J]. Computers & Operations Research, 2016, 74: 1-13

[12] Wang J, Zhu X, Zhu J, et al. Towards dynamic real-time scheduling for multiple earth observation satellites [J]. Journal of Computer & System Sciences, 2015, 81(1): 110-124

[13] 白保存，贺仁杰，李菊芳，等.卫星单轨任务合成观测问题及其动态规划算法[J].系统工程与电子技术,2009,31(7):1738-1742

Bai Baocun, He Renjie, Li Jufang, et al. Satellite orbit task merging problem and its dynamic programming algorithm [J]. Systems Engineering and Electronics, 2009, 31(7): 1738-1742 (in Chinese)

[14] 余建军，孙树栋，吴秀丽，等.四种改进免疫算法及其比较[J].系统工程,2006,24(2):106-112

Yu Jianjun, Sun Shudong, Wu Xiuli, et al. Four modified immune algorithm and its compare [J]. Systems Engineering, 2006, 24(2): 106-112 (in Chinese)

[15] Bagheri A, Zandieh M, Mahdavi I, et al. An artificial immune algorithm for the flexible job-shop scheduling problem [J]. Future Generation Computer Systems, 2010, 26(4): 533-541

[16] Yang S, Wang M, Jiao L. Quantum-inspired immune clone algorithm andmultiscale bandelet based image representation [J]. Pattern Recognition Letters, 2010, 31(13): 1894-1902

[17] 李艳，孙乐，朱怀忠，等.网树求解有向无环图中具有长度约束的简单路径和最长路径问题[J].计算机学报，2012，35(10):2193-2203

Li Yan, Sun Le, Zhu Huaizhong, et al. Anettree for simple paths with length constraint and the longest path in directed acyclic graphs [J]. Chinese Journal of Computers， 2012， 35(10): 2193-2203 (in Chinese)

[18] Chia W L, Chen P L, Hsieha S Y, et al. Weight-constrained and density-constrained paths in a tree:enumerating, counting, and k-maximum density paths [J]. Discrete Applied Mathematics, 2015, 180: 126-134

[19] 蔡德荣.基于蚁群算法的多星联合成像任务规划问题研究[D].成都:电子科技大学,2012

Cai Derong. Multi-satellite imaging task scheduling problem research based on ant algorithm [D]. Chengdu: University of Electronic Science and Technology of China, 2012 (in Chinese)

[20] 李菊芳，白保存，陈英武，等.多星成像调度问题基于分解的优化算法[J].系统工程理论与实践,2009,29(8):134-143

Li Jufang, Bai Baocun, Chen Yingwu, et al. Optimization algorithm based on decomposition for satellites observation scheduling problem [J]. Systems Engineering Theory & Practices, 2009, 29(8): 134-143 (in Chinese)