一种面向成像卫星的启发式分层任务规划方法

张 淳 张 强 赵 阳 刘 鹤 刘晓敏

北京空间飞行器总体设计部，北京 100190

0 引言

遥感卫星覆盖区域广，可长时间运行，不受飞行空域限制，是一种重要的对地观测手段[1]。遥感卫星任务规划负责分配卫星观测资源、制定观测计划，利用有限存储、能源和可见时段等资源充分完成用户提交的成像任务，在遥感卫星成像业务应用过程中起到关键作用。随着遥感卫星应用技术的发展，相关任务规划问题得到了充分重视和广泛研究[2-3]。

遥感卫星任务规划问题与背包问题类似，均为NP难，不易获得全局最优解[4]，潜在解随遥感设备数量、卫星窗口数量、成像目标数量呈指数级增长，考虑多种因素下的优化搜索时间十分漫长。相关任务规划研究内容包括动态调度[5]、贪婪迭代[6]、禁忌搜索[7-8]、线性规划[9]、遗传算法[10-11]、蚁群算法[12]、整数规划[13-14]等等。这些任务规划求解过程均基于一些简化模型，或将任务规划问题映射为某种问题的变体，或者忽略、简化了卫星的部分实际运行约束，或者求解时间漫长，无法适应动态任务变化。目前，遥感卫星任务规划问题求解大多采用静态求解思路，即当任务需求发生变化时，将新需求与原需求整合后重新进行全局规划，并未考虑任务规划在实际运控系统中应用的实际动态响应需求。针对类似需求，采用基于规则的启发式任务规划具有更好的实用性。基于规则的启发式算法简单、直观、便于实现、运算效率高，是现实成像卫星规划系统中具有实际应用案例的算法[15-16]。

本文针对成像卫星运控系统中的高计算效率、动态任务调整应用需求，提出一种通用化的启发式分层任务规划方法，加速任务规划计算，实现在保证原规划方案结果继承性基础上响应新任务输入。

1 任务规划模型

1.1 调度路径

设计如下总体任务调度路径：首先对星上资源进行总体资源预算，评估规划周期内可执行的任务数量；然后根据维护任务规划结束后的剩余可用时间窗口，分别依序规划各层级任务，具体分为关键任务、一般任务以及次要任务；在所有任务规划完成后，进行资源复核，适时进行任务调整。

1.2 收益函数

采用如下收益函数

(1)

(2)

(3)

S=(Fkey,Ford,Fsub)

(4)

其中，Fkey为关键任务收益，Ford为一般任务收益，Fsub为次要任务收益，Tkey为关键任务集，Tord为一般任务集，Tsub为次要任务集，xi为任务i是否执行的决策变量，S表示收益计分。

1.3 资源预算

为了保障规划结果的可行性，降低任务调整的可能性，在任务规划前对卫星当前资源进行总体估算，评估当前资源能够支持的运行时间或任务数量。主要考虑能源和存储2种资源预算。

根据待规划任务i的持续时间Δti项，计算所有待规划任务集(Tkey、Tord和Tsub)的任务平均持续时间Δttotal，并使用下式计算满负荷安排任务时的预期可规划任务总量ntask,total

(5)

其中tcyc,total为规划周期内总的可用时间窗口长度；tmnv,max=2ϑmax/ω为卫星最长机动时间，ϑmax为卫星最大俯仰或滚动角，ω是卫星平均机动速率；tst,max是卫星机动后观测前的最长稳定时间。

1)能源预算

总体能源预算主要考虑卫星在光照期的充电能力和地影期的放电深度，通过计算地影期最大能源消耗、光照期充电能源、最小运行能源与卫星当前能源的关系获得能源预算

p-(∪tw,i∩tw,es)Δpo+tw,illΔpc>pmin

(6)

其中tw,i为任务i的有效时间窗序列；p是当前初始能源；pmin是卫星最小运行能源，低于此限值卫星不应再执行对地观测活动；Δpo为卫星载荷开机状态下的平均能源消耗；Δpc为卫星蓄电池光照条件下平均充电速率；tw,es为地影期；tw,ill为光照期。

如果上式条件满足，则卫星当前能源预算充足；如果条件不满足，需要限制卫星在地影期的载荷最大开机时间，即

(7)

其中tduty,max表示地影期最长工作时间。

2)存储预算

在总体存储预算中，考虑可规划任务总量、平均持续时间、最大存储容量、存储容量消耗速率与卫星当前可用存储容量之间的关系获得存储预算

m+ntask,totalΔttotalΔm

(8)

其中m为卫星当前存储容量；mmax是卫星最大可使用存储容量；Δm是卫星观测单位时间消耗的存储容量。如果上式条件满足，则卫星当前存储预算满足要求；如果条件不满足，可添加数据下传任务或限制卫星的可规划任务总量进行处理。

1.4 约束复核

1)观测约束

观测约束主要考虑对目标的成像情况，考虑每个目标只能被观测一次的规划约束条件

(9)

其中Wtotal为全部时间窗口集，Ttotal为全部任务集，xi,k表示在第k个时间窗口安排对第i个任务进行观测的决策变量。

2)任务准备约束

任务准备约束主要考虑由前一个任务执行过程中所需要的姿态机动到下一个待执行任务姿态所需要的机动转换时间约束

(10)

其中ws,l,i,k为活动开始时间；we,l,i,k为活动结束时间,as,l和ae,l分别表示第l活动的第一组和最后一组姿态角。考虑到

ws,l+1,i,k-we,l,i,k>tmnv,max+tst,max

(11)

进一步，约束式可简化为

(12)

3)存储约束

存储约束对任务规划结果所消耗的存储容量进行复核

(13)

4)能源约束

能源约束对规划结果所消耗的能源进行复核

(14)

5)地影期时间约束

能源约束中考虑了规划周期内整体的能源平衡情况，但无法保证每一时刻卫星能源均大于最小运行能源。为保证解的合理性，根据能源预算中获得的最大地影期工作时间，对地影期的任务执行时间进行约束，保证能源平衡，如式(15)：

(15)

2 启发式分层任务规划

为提高计算效率，缩小潜在的解空间搜索范围，采用层次化的决策思路。先进行待规划任务的选取，然后选取可用时间窗，在选中的时间窗内确定具体的执行任务时间段。通过这种规划层级的划分，可以将需要考虑多种因素的复杂规划问题拆分为3个较小的决策问题，通过递进式的搜索策略降低解空间维度，在启发式规则引导下提高计算效率。

图1 启发式分层任务规划

2.1 任务选取规则

任务规划的第1层搜索为在待规划任务集中选择需要规划的任务。评价任务选择有2个维度，分别是任务权重和任务紧迫性。任务权重由任务构造模型定义，任务紧迫性则衡量任务可以被执行的机会，也即在规划周期内该任务可以使用的观测时间段的多少。为对任务权重和任务紧迫性进行综合评估，定义任务需求度如式(16)：

(16)

其中nmission,i表示第i个任务的需求度，oi表示剩余观测机会数量，即规划周期tcyc,total内对任务观测的剩余时间窗时间总和与该任务预期占用时间Δti之比。任务权重wi越高，任务权重越高，剩余观测次数oi越少，任务紧迫性越高，因此任务需求度nmission,i可综合评估剩余待规划任务的优先级，选取其中最大者以作为本轮规划的选取任务。

2.2 时间窗选取规则

任务规划的第2层搜索是在已选中待规划任务的可用时间窗口序列tw,i,k=[taccs,i,k,tacce,i,k]中选择合适的时间窗口。由于每个待规划任务可能对应了多个可用时间窗，因此需要对时间窗进行选择。评价某个时间窗是否适合作为该任务的可执行窗口需要考虑2个方面，分别是该时间窗相对于任务所需要的执行时间Δti是否宽裕，以及该时间窗是否与其他任务所对应的可用时间窗或潜在执行时段存在冲突。为评价时间窗相对于任务执行时间的宽裕程度，定义时间窗自由度如式(17)：

(17)

其中fi,k表示任务i对其第k个可用时间窗口的时间窗自由度。显然可用时间窗越宽，其自由度越高，表示选中该时间窗后进行后续时间段选取的灵活性越大。

比较使用所选任务可用时间窗与其他待规划任务的所有可用时间窗，对冲突程度近似评估。定义时间窗冲突度如式(18)：

(18)

其中ci,k表示任务i第k个可用时间窗口所对应的冲突度；tconf,i,k,j表示任务j有效时间窗序列tw,j中与任务i中的第k个可用时间窗tw,i,k相冲突的时间长度，这里均考虑了tmnv,max和tst,max的影响，即用时间窗起始时刻减去机动和稳定时间，以近似获得最大可能的冲突区间；nust表示当前规划层未规划任务中与时间窗tw,i,k存在冲突的剩余任务数，即计算冲突度时不再考虑已规划完毕的任务。冲突区间tconf,i,k,j越长、所对应的冲突任务权重越高，表示当与其他高权重任务出现长时间交叠时，时间窗冲突度越大；选中的待规划任务可用时间窗越小、任务权重越小，表示该任务时间窗越不重要，时间窗冲突度越大。

综合考虑时间窗自由度与时间窗冲突度，定义时间窗需求度如式(19)：

(19)

时间窗自由度fi,k越高，任务段分配越自由，越不易与其他任务产生时间段冲突；时间窗冲突度ci,k越小，该任务窗口与其他任务的潜在可用时间窗口冲突程度越低。因此时间窗需求度nwindow,i,k可综合评估所选取任务的时间窗序列的优先级，选取其中最大者以作为本轮规划的选取时间窗。

2.3 时间段选取规则

任务规划的第3层搜索是在已选中的可用时间窗口中进一步选择实际执行任务时间段。考虑基于任务重叠度的方式选取实际任务执行时间段，增强后续任务分配时间段的自由性，计算思路如图3所示。

图2 基于任务重叠度的时间段分配示意

图3 冲突区间示意

将选中时间窗tw,i,k内的时间进行均匀采样，获得时间窗的采样时刻总数nsi。对除选中任务外的任意剩余任务j，如果其所对应的时间窗序列tw,j包含时间窗tw,i,k的第m个采样时刻，则设该时刻的冲突量为cnum,i,k,m,j=1，否则cnum,i,k,m,j=0。考虑除选中任务外的所有剩余任务，则有第m时刻的总冲突量为

(20)

而对于整个窗口，有总冲突量为

(21)

采用滑动窗口机制，在tw,i,k内滑动宽度为Δti的子窗口，寻找cnum,i,k最小的位置，此时表示该时段与其他任务冲突度最低，令ws,l,i,k等于此刻子窗口的开始时间，we,l,i,k等于此刻子窗口的结束时间，从而获得实际任务执行时段。

2.4 活动序列更新规则

活动序列更细规则根据任务规划过程结果更新任务列表，主要计算可用时间窗口的变化，即在给定当前任务序列和可见弧段序列基础上，占用或释放某时间段，并更新任务序列和相应可见弧段序列。限于篇幅，活动序列更新规则不再赘述。

2.5 低收益任务消减规则

对于任务规划结果中不合理的部分，需要采用调整策略对规划结果进行修改。低效益任务消减规则分为2步，首先确定消减的作用时间窗口范围，对于资源约束，消减作用范围一般为整个规划周期，对于地影期时间约束，消减作用范围为地影期，对于冲突任务则为冲突区间。其次，根据任务规划结果计算最低级别各规划任务的收益率，定义如下

(22)

将收益率最低的任务删除，释放可用资源和时间段，重新进行约束复核计算，如果满足约束则停止，如果不满足则继续删除任务。如果在最低级别任务已全部删除时仍然无法满足约束，则进一步删除次低级别任务，以此类推。

2.6 冲突任务消解规则

当出现紧急任务需要插入已规划出的任务序列中时，采用冲突任务消解规则进行应急任务插入，步骤如下：

步骤1.待规划应急关键任务序列已遍历完毕，若是则转步骤4；若否，则转步骤2。

步骤2.根据任务选取规则确定当前待规划应急关键任务，尝试在现有可用时间窗口下插入应急任务，若成功插入，则返回步骤1；若失败，转步骤3。

步骤3.分别确定当前待规划应急关键任务与任务序列中已规划未执行任务的冲突区间，针对存在多段冲突的情况，采用低收益任务消减规则依次删除冲突任务，并尝试插入当前应急任务，在删除冲突任务但插入不成功情况下恢复原冲突任务，直至插入成功或全部冲突任务遍历结束。若成功，或失败但待规划任务没有与现有关键任务相冲突的区间，则返回步骤1；否则转步骤4。

步骤4.若仍有未规划的应急关键任务，且该应急任务与已安排应急任务存在冲突区间，则删除全部未执行任务，将应急任务加入未执行任务形成新的待规划任务序列，重新规划任务。若没有未规划的应急关键任务，则结束。

3 仿真验证

本节对所提出的启发式分层规划算法进行仿真验证，仿真参数选择某科学试验卫星数据。最大俯仰角和滚动角45°，视场角8°*4°，卫星平均机动速率2(°)/s，卫星最长机动时间45s，最长稳定时间60s，规划周期24h，半长轴24628km，偏心率0.72°，轨道倾角19.6°，近地点幅角290°，升交点赤经20°，真近点角0°。

配置含有108个观测目标的高密度成像观测任务表，观测目标在地球表面沿经纬度均匀分布，其中经纬以(0°，0°)为起点，沿经度和纬度上分别每间隔30°、20°排布一个观测目标。并分别定义不同任务层级(1至3)、权重和持续观测时间(60s、180s、300s、600s)。使用STK对该108个目标的可见性进行分析仿真，除第84个目标点不可见外，其余均可见，可见窗口数量从1到4不等。使用本文所提算法对上述待规划任务进行仿真计算，成功规划任务107个，未规划任务1个，其中未成功规划的第84个任务没有可见时间段。限于篇幅，这里不再单列任务规划表。所有规划结果满足预先定义的任务要求，规划时间窗口处于STK分析得到的可见弧段内，满足任务规划预期，规划结束后按照式(4)得到的计分结果为(10,150,93)。

仿真验证中任务规划算法运行平台配置为处理器Core i5-7200U 2.50GHz、内存8GB。108个成像任务规划耗时2.8946s，所提启发式分层任务规划算法计算速度较高，同时能够保证大量、多维度任务输入下规划解的覆盖性和正确性。

在上述结果基础上，于全球范围内取随机目标位置插入持续时间均为300s的关键任务，检验算法对动态输入的响应能力。插入应急关键任务数量与结果如表1所示。

表1 插入应急关键任务后结果

除有一个应急关键任务没有可见弧段外，其余任务均插入成功。当插入任务数量达到30时，触发了冲突任务消解规则中规定的任务重排。由该组仿真可见，本文所提启发式分层任务规划算法能够响应动态任务插入需求，保障对原规划方案一定程度上的继承性，当输入变动过大时能够支持快速任务重排，具备较强的实用性。

4 结论

针对成像卫星运控系统设计中的高计算效率、动态任务调整应用需求，提出了一种通用化的启发式分层任务规划方法，采用资源预算、分层规划、约束复核、动态调整的思路构建任务调度路径，引入了完整的观测性、任务准备、存储、能源、地影期等实际约束条件，利用启发式贪婪策略，设计任务选取、时间窗选取、时间段选取三层复合搜索规则，逐级引导任务规划求解过程，在每一层上缩减问题规模实现解空间的分步降维，从而加速任务规划计算。同时提出低收益任务消减和冲突任务消解策略处理应急动态任务请求，实现在保证原规划方案结果继承性基础上响应新任务输入。仿真验证结果表明所提算法能够有效规划高密度任务，同时具备较好的计算性能。