基于贪婪策略的灵巧卫星启发式任务规划算法

徐崇彦，何川东，邹冬冬

(北京市遥感信息研究所，北京 100192)

0 引言

近年来，高分辨率灵巧型卫星[1-2]已成为成像卫星应用的主流，比如美国的IKONOS-2、Quick Bird、WorldView-1卫星、俄罗斯的Topsat卫星、法国的SPOT-5(HRG)、PLEIADES星座和以色列的EROS-2卫星等，这些灵巧卫星具有大范围快速姿态机动能力，可实现侧视、前视、后视等灵活成像动作，已经在军民重要领域发挥了巨大作用，并显现出更加广阔的应用前景。

灵巧卫星在功能和性能上大幅提高、应用灵活性不断提升的同时，也给卫星任务规划带来了新的挑战。国内外学者对灵巧卫星任务规划问题进行了相关研究，如针对法国PLEIADES灵巧卫星，欧空局的Lemaitre[3-4]等将问题简化为单星单圈次的任务选择与调度问题；DJamal Habet[5-6]等采用禁忌搜索来解决灵巧卫星任务规划问题，并通过约束传播策略来保证邻域搜索时的一致性；国内的陈宇宁[7]、郭浩[8]、严珍珍[9]等通过分析灵巧卫星任务规划问题特点，设计了基于蚁群算法的灵巧卫星任务规划方法；向仍湘[10]针对不同问题规模，提出了基于模拟退火遗传算法的大规模问题求解算法和基于列生成算法的小规模问题求解算法。上述研究中，从不同侧面解决了灵巧卫星任务规划问题，但是，为了问题求解方便，规划模型都做了一定简化。贪婪算法由于其无需迭代、求解速度快的特点，常被用来解决最优化问题，本文从工程应用角度出发，全面考虑卫星约束和实际应用特点，设计了基于贪婪策略的灵巧卫星启发式任务规划算法。

1 灵巧卫星任务规划问题及模型

1.1 灵巧卫星成像特点

灵巧卫星利用其俯仰能力可以在一个较长的时间窗口内自由选择成像时间，对单个目标可进行成像的机会增多。如图1所示，非灵巧卫星基本仅具备侧摆的方式成像，因此对目标的成像时刻固定为一点；灵巧卫星具备星下点一定角度范围内任意角度成像的能力，拓宽了对单个目标的可见时间窗口，因此对单个目标观测的成像时刻可在较长成像范围内任选。灵巧卫星还可以在一次可见窗口内通过快速姿态机动对同一目标实施连续多次成像，实现同轨立体成像功能，进一步增强了卫星的成像能力。

图1 目标的成像时刻示意

1.2 灵巧卫星任务规划特点

灵巧卫星任务规划具有以下特点：

① 观测目标成像时间选取灵活。灵巧卫星利用俯仰能力使成像窗口可以在一个较长的可视窗口内自由地选择，这种自由度使灵巧卫星能够执行更多的成像任务，这是灵巧卫星最大的优点。

② 卫星姿态机动时间与前后目标成像时间的选择紧密相关。由于卫星运行过程中姿态的变化，灵巧卫星对前后目标的不同成像时刻选择，决定了对前后目标的不同成像角度；不同成像角度决定了卫星前后的姿态机动位置不一样，所以，也决定了不同的卫星姿态机动时间。

③ 灵巧卫星任务规划增加了卫星动作序列规划[11-12]，扩大了搜索空间、增加了难度。灵巧卫星有效载荷动作可以灵活地组合使用，比如对于非灵巧卫星完成记录时，卫星动作序列可以简单的理解为：相机开机—记录开始—记录停止—相机关机，这些动作必须全部执行，而灵巧卫星可以根据实际情况，只安排部分动作执行、部分动作不执行，这就显著增加了任务规划难度。

1.3 优化目标

任务规划的优化目标一般可以设为规划方案的收益最大，目前，在卫星数量有限、成像需求较多的情况下，规划方案的收益可以定义为：成像目标数量尽可能多、成像目标重要性等级尽可能高，这2个因素可以采用加权和得到规划方案的收益评价值。

设规划方案的收益函数表示为：

P=v1×f1+v2×f2=

(1)

式中，v1、v2分别为目标数量、目标等级对应的准则重要性权值；f1，f2分别为目标数量、目标重要性准则评价值；M为成像目标集合；N(i)为成像目标序列中成像节点i(一个卫星开关机时段称之为一个成像节点)所含地面目标的数目；dg，dm分别表示最高、最低目标等级，且dg

则规划方案的优化目标为：

(2)

1.4 约束条件分析

1.4.1 姿态转换时间约束

后一个目标的成像开始时间须大于前一个目标的成像结束时间，加前一个目标关机稳定时间，加姿态转换时间，加后一个目标的开机准备时间。

(3)

1.4.2 任务间隔时间约束

前后目标的成像间隔时间须大于卫星载荷设备工作时间之和。

(4)

(5)

1.4.3 最大连续工作时长约束

前后相邻相机开机到相机关机的间隔时间须小于最大连续工作时长约束。

(6)

1.4.4 数传约束

成像卫星一般有多种不同数据压缩比，不同数据压缩比对应的数据录放比(记录时长与回放时长之比)也不一样，单次回放目标的回放时长之和须小于等于接收站最大接收时长，

(7)

其次，单次规划的所有目标的回放时长之和也必须小于等于所有接收站的最大接收时长之和，

(8)

1.4.5 固存容量约束

不同数据压缩比对应的所需存储容量也不一样，2次固存擦除动作之间所有目标的存储容量之和须小于卫星最大固存容量。

(9)

式中，hi为目标i的固存容量；H为卫星总存储容量。

1.4.6 能源约束

成像目标的能量消耗加卫星设备的长期功耗，须小于卫星初始能量加卫星在光照区补充的能量之和，

(10)

式中，ei为目标i的消耗能量；Ef为卫星设备长期功耗；Es为本次规划时的卫星初始能量；Ea为卫星在光照区补充的能量。

这是个具有复杂约束的约束满足、多目标优化问题，完全搜索算法难以在合理的时间内得到问题的解，而贪婪搜索算法在大量实践中被证明能有效求解该问题。

2 算法研究

2.1 贪婪算法基本思想

贪婪算法是一种解决最优化问题的近似方法[13]，在对问题求解时总是做出在当前看来是最好的选择，也就是说所做出的是在某种意义上的局部最优解。贪婪算法的关键在于贪婪准则的设定[14]，它是决策的依据和标准，即在求解的每一步依据何种标准对变量进行赋值。它无须迭代，不能保证最优，但是它的时间性能最佳，对于一些大规模的任务规划问题或涉及复杂约束的规划问题，当其它算法在有限时间内无能为力时，贪婪算法无疑是一种不错的选择[15]。

2.2 贪婪规则设计

2.2.1 目标选择规则

当多个成像目标不满足卫星某一约束时，指导按照何种顺序选取目标。主要考虑目标等级、目标数量、机动角度和太阳高度角等因素。

① 判断目标等级，优先选择目标等级较高的；

② 判断目标数量，优先选择目标数量较多的；

③ 判断机动角度，优先选择由前一目标到当前目标机动角度较小的；

④ 判断太阳高度角，优先选择太阳高度角较大的。

2.2.2 成像时间选择规则

针对可以俯仰成像的目标在较长可视窗口范围内，指导按照何种原则选择成像时间。

① 当前目标与前后目标没有冲突，则优先选择俯仰角最小的时刻为该目标的中心成像时刻；

② 如果当前目标与已安排目标存在冲突，则在当前目标可视窗口范围内从前向后进行滑动选择，最早不存在冲突的时刻作为当前目标的成像开始时间。

2.2.3 前瞻处理规则

对于密集分布的目标，当任务连续冲突且优先级依次上升的时候，可能出现只有连续冲突的最后一个任务被安排，前面的任务全部被舍弃的情况，此时，加入前瞻处理方法。

① 前瞻步长：就是在候选任务队列中前瞻任务的数量，前瞻步长是可变的。如果当前目标与后续目标可视窗口间隔大于卫星最大机动时间，则结束前瞻。

② 回滚操作：当前任务安排后，在前瞻范围内再次从后向前判断前面的目标是否能够安排。

2.2.4 接收方案生成规则

① 优先将指定接收站的目标安排给对应接收站；

② 能实传近实传的目标优先安排相应站为实传站；

③ 对于回放接收站，依次安排成像目标进行回放，直到该接收站时间被用尽或没有目标需要回放。

2.2.5 能源补充规则

为了快速补充卫星能源，当卫星在阳照区且空闲时间超过一定时限，安排卫星对日定向进行能源补充。

2.2.6 固存擦除规则

为了便于固存管理和提高固存使用效率，每次回放后如果星上记录数据全部回放完毕，则进行固存擦除。

2.3 算法流程

任务规划算法总体流程如图2所示。

图2 任务规划算法总体流程

步骤2：根据成像目标、接收站的开始时间进行排序，形成候选任务队列M1，S1；

步骤4：对目标序列M2检验相机工作时间、单圈侧摆次数等约束，如果不满足约束则根据目标选择规则进行冲突消解，生成目标序列M3∈M2；

步骤5：生成接收方案：依次对候选接收任务队列S1中的接收任务进行安排，并考虑各接收站接收任务均衡原则，直到无待传输的成像目标或者当前接收站无剩余接收时间，此时，得到初步任务规划方案，即目标序列M4∈M3，接收序列S2∈S1；

步骤6：生成接收方案后再次检验卫星约束，如工作时间约束、固存约束等，如果不满足约束则根据目标选择规则进行冲突消解，得到目标序列M5∈M4，转步骤5；否则转步骤7，此时M5=M4；

步骤7：根据能源补充规则与动作序列组合使用规则，添加对日定向、对地定向动作，生成卫星动作序列A；

步骤8：检验卫星能源约束，如果不满足约束则根据目标选择规则进行冲突消解，得到目标序列M6∈M5，转步骤5；否则(M6=M5)，生成最终任务规划方案(包括目标序列M6、接收序列S2与卫星动作序列A)，算法结束。

3 算法仿真实验

目前，各个国家成像卫星的使用约束不尽相同，在卫星任务规划领域尚没有公认的benchmark测试问题集，很难与现有的解决方法进行比较[16]。本文参考法国PLEIADES卫星的主要参数，其主要参数为：空间分辨率全色0.5 m，多光谱2 m；标准幅宽20 km；轨道高度694 km，轨道周期98.64 min/圈；侧视角度±30°；每8 h制定并更新成像计划，每天3次。分别模拟规划周期为12 h与24 h，基于STK软件分别生成10组，共20组实验数据，展示本算法的有效性。详细实验情况如表1和表2所示。

表1 周期为12 h实验情况

表2 周期为24 h实验情况

由实验结果可以看出，20组实验数据中成像目标平均安排率为84.15%，算法平均耗时为11.4 s。未安排目标原因主要有2点：① 由于目标密集分布，卫星机动能力不足导致目标没有安排，在20组测试数据中均有此原因，并且在目标数较少的时候该因素是未安排目标的主要原因；② 由于模拟的国境内地面站由于地理位置限制，导致数据传输有一定时间延迟，同时，卫星存储容量不足从而导致目标没有安排；并且，随着目标数量增加，该因素成为未安排目标的显著因素之一。综上可知，本文算法可以处理灵巧卫星的所有约束条件、适应不同模式的成像目标(点目标、立体成像目标)，生成卫星动作序列与任务规划方案，算法耗时较短、成像目标落实率较高，能够满足工程应用要求。

4 结束语

本文针对新一代灵巧卫星对地成像任务规划问题，针对灵巧卫星机动能力强、卫星载荷动作使用灵活的特点，通过分析灵巧卫星任务规划特点、优化目标与约束条件，建立了灵巧卫星任务规划模型；基于贪婪思想，运用专家知识的任务规划启发式规则，建立了基于贪婪策略的灵巧卫星任务规划算法。该算法能针对灵巧卫星多种工作模式，综合考虑成像目标与卫星动作序列，在较短时间内生成任务规划方案，并通过仿真实例验证了模型和算法的有效性。