卫星对地观测任务启发式自主规划算法研究

张秀秀， 王俊峰， 杨 春

(1.四川大学计算机学院, 成都 610065； 2. 四川大学空天科学与工程学院， 成都 610065； 3.四川师范大学可视化计算与虚拟现实四川省重点实验室， 成都 610068)

1 引 言

近年来小卫星发射数量愈来愈多，占据了航天活动的主要领域[1]，对地观测作为卫星技术主要应用方向之一，备受人们的重视.根据美国卫星工业协会(SIA)发布的数据显示，2017年全球发射的小卫星中将近一半用于地面观测服务[2].传统的对地观测任务规划模式为：地面控制中心就用户所提交的任务集合，根据所掌握的各种卫星参数信息，通过计算生成特定的观测计划表，上注给对应的卫星，使卫星按照计划完成观测任务.该模式往往采用离线规划的方式，计划一旦生成则不可改变，不利于对观测需求动态变化的任务的调度.且该模式计算部分严重依赖地面控制中心，容易出现因任务数量多导致规划效率低下的问题，因此卫星拥有任务自主调度能力尤为重要.

自主调度将规划权从控制中心剥离，转移到卫星的计算单元上，每颗卫星可结合自身资源约束以及任务要求来决定需要观测的任务序列，该方式已引起许多学者的重视[3-4]，国内外已有不少研究成果和应用.文献[5-6]针对敏捷对地观测卫星LemaTre建立了观测问题的简化模型，提出了快速贪婪、动态规划、约束规划、局部搜索四种算法，通过实验对比，局部搜索算法表现出了较好的性能；而Habet提出了一种禁忌搜索算法来进行求解，多数实例运行结果达到了最优，但研究对于约束的精确性还需进一步考虑.文献[7-8]分别介绍了Casper和ASPEN卫星任务规划系统.Casper采用星上自主监视，地面重新规划任务并重传机制，而ASPEN作为一个面向对象的系统，主要实现以日为周期来对卫星的活动进行规划.文献[9]针对多卫星提出了星上自主任务重新规划系统，算法核心由多目标混合动态变异遗传算法和重新规划技术组成，仿真结果表明,系统可在紧急的情况下对任务作出有效的重规划.伍保峰等人[10]提出了小卫星面向任务自主指令设计的办法，令卫星具有自行判断执行指令的能力.刘嵩等[11]针对敏捷成像卫星自主任务规划，提出了一种结合了随机机制和轮盘赌思想的迭代贪婪算法，但易陷入局部最优的困境.文献[12]针对突发性事件提出了一种双阶段规划算法，以仿真案例证明了动作并行执行可行性，但未考虑事件优先级对事件执行顺序的影响.赵萍等[13]采用了精英保存策略对遗传算法进行了改进，但对于成像操作之间有交叠的任务没有进行考虑.张弛等人[14]基于高分三号卫星的任务特点，提出了九种编排指令模版用于任务的自主规划，测试证明了设计的实用性.

卫星任务规划归根结底是一种基于组合优化理论生成可行方案的问题.已有的算法研究多数为启发式算法，该类型算法研究取得了一定的成果，但也存在着几个问题.(1) 对于观测任务就资源消耗问题都做了粗略的处理，计算结果与实际应用相差较大;(2) 对于冲突关系的处理，是基于收益最大原则在任务中做出选择观测，这样使得整体规划率不高;(3) 由于启发式算法是在解空间中进行解的搜索，因此时间耗费较长.

针对以上缺陷，本文设计并实现了一种新的用于小卫星自主调度观测任务的启发式自主规划算法.与已有的启发式算法不同的是本算法采用分而治之的思路，即将问题分为两个子问题进行求解:(1) 在对任务进行资源消耗的精确计算下，对任务间存在的冲突关系基于最小冗余原则进行消解；(2) 采用优化的蛙跳算法进行解的搜索.在冲突消解的基础上进行搜索，保证了更多任务有观测可能的同时缩小了第二模块的解空间，可在较短时间内计算得到收益最大的观测队列.

2 问题分析与建模

2.1 观测动作与问题描述

卫星在沿特定的轨道运行时，遥感成像设备[15]会在地球上形成一圈投影，这圈投影称为星下点轨迹.由于传感器具有侧摆功能，卫星在运行过程中会形成以星下点轨迹为中心的条带状区域[16]，即卫星对地球的可视范围.处于可视范围内的目标均有机会被卫星所观测，受遥感器视场限制的影响，卫星的一次成像仅能覆盖比可视范围小的区域，如图1中蓝色长方形所示.

图1 卫星对地观测示意Fig.1 Schematic diagram of satellite observation

观测目标通常分为点目标和区域目标两种，如图1中圆形形状为点目标，紫色不规则形状为区域目标.对目标进行观测时，点目标对地覆盖区域小，一般只需遥感传感器侧摆一次，而区域目标往往需要角度转换两次及以上，在实际活动中，区域目标往往被划分为几个点目标来完成观测.因此为使研究方法具有通用性，本文的研究对象选取以点目标为代表的观测需求.

卫星完成一次观测的完整步骤为：开机、侧摆、稳定、观测、关机，如图2所示.具体描述为：遥感传感器在指定时间开机，随后侧摆到规定的角度使目标为其可见，待传感器稳定后执行观测，观测达到时间要求后关机.并非每个任务都必须执行这5个步骤，在满足卫星最长开机时间条件限制下，可省略开关机操作.每个任务拥有特定的可见窗口，观测动作需在可见时间窗口内完成.以任务间可见窗口是否交叉为依据，任务间的关系可被划分为冲突或不冲突两种.如图2中共列出了三个任务，任务1与任务2的成像间隔时间足够让设备进行姿态转换，这样的两个任务互相独立，反之则互相冲突，如任务2和任务3.为了对目标点达到最佳观测，传感设备对每个目标点都有一个最佳侧摆角，若对目标都使用最佳侧摆角进行观测，那么对于形如任务2和任务3成像间隔时间小于姿态转换所需时间的任务来说，不一定能被设备同时观测到.

图2 观测任务示意Fig.2 Observation task

冲突关系的存在是造成任务规划效率较低的一个重要因素，在考虑卫星的能量、存储以及转换时间等各种约束条件下如何对任务做出选择，充分利用匮乏的资源使最终形成的观测队列收益之和最大化，是本文要解决的问题.

2.2 系统模型

2.2.1 基本假设 卫星资源约束较多，为了便于研究有必要对问题进行简化，本研究作出如下的合理假设：(1) 每颗卫星上只携带有一个遥感传感器；(2) 卫星的开机和关机均需要一定时间，且会消耗一定电量；(3) 大气、光照等自然条件以及卫星的侧摆对观测质量没有影响；(4) 在一个调度周期内，卫星所拥有的能量是一定的； (5) 在完成一个周期的调度后，卫星才进行数据的下传.

2.2.2 模型与约束 根据任务可见窗口以及卫星的唯一性，结合星载资源限制，我们采用0-1整数规划对卫星自主调度观测任务问题进行建模，便于之后使用所提出的启发式自主规划算法对任务进行调度和优化.

(1) 参数设置模型中涉及到的参数如表1所示.

表1 模型参数

其中,资源参数由卫星自身决定，任务的权重、持续观测时间以及观测角度等由需求决定，每个任务的可用窗口通过卫星计算单元利用自己的六轨道根数以及目标点的位置计算得到.轨道根数是描述卫星沿轨道运行状态的一组参数[17]，通常是指包括轨道半长轴a、轨道偏心率e、轨道倾角i、升交点赤经Ω、近地点幅角ω、指定历元的平近点角M0在内的六个参数；目标点的位置一般用经纬度坐标来确定，如Targeti=(Li,Bi)，其中Li为经度，Bi为纬度.

(2) 目标函数及约束.

subject to

C1:CNCNi=i∃CNi≠0，∃i∈[1,N]

C2:CNi≠CNj∃CNi,CNj≠0，∃i,j∈[1,N],i≠j

C3:Xi=XCNi∃CNi≠0，∃i∈[1,N]

C6:|Ai|≤Max_A∀i∈[1,N]

模型的目标函数是使被安排观测任务的总权重最大化.约束C1～C2保证了两个任务在合成时的关联性；约束C3表示进行合成观测的两个任务具有规划一致性；约束C4～C5为任务规划时的资源限制，C4为任务数据存储约束，C5为能量约束，包括传感器开机、侧摆及稳定、观测和关机所消耗的能量，其中,f(CNi)保证因任务合成所产生的冗余数据或能量消耗不被重复计算；约束C6为侧摆角限制，任务观测所需的侧摆角度不能超过星载遥感器的最大侧摆角.

3 启发式自主规划算法

星上计算资源有限，为了快速且有效地对任务进行规划，我们基于问题模型提出了一种启发式自主规划算法(Heuristic Independent Programming Algorithm,HIPA).HIPA采用分而治之的思路，即将问题分解为任务合成与序列规划两个子模块进行求解.这两个子模块看似独立但又联系紧密，其逻辑关系如图3所示.

流程中任务资源消耗预处理部分主要完成的工作是针对每一个任务，按观测的完整过程计算可能的电量和数据存储空间耗费.

Di=TCi*DUT

(1)

式(1)中,DUT为单位时间观测数据上行传输率.

(2)

式(2)中,Tof为一次开关机所需的时间;w为传感设备的摆动角速度;Tsta指侧摆后到稳定所需的时间;EUT为开机状态时单位时间设备的耗电量.

图3 HIPA整体流程Fig.3 HIPA overall process

3.1 基于启发式规则的任务合成

任务间冲突关系以不同形式呈现，通常有两种情况.一种为任务间可见窗口交叉且观测角度不同，另一种为窗口不交叉但任务间观测间隔时间不能满足设备进行姿态转换.这两种情况均需进行冲突消解，为使存在冲突关系的任务都具有被观测的可能，本文采用合成的办法进行处理.

(1) 合成条件.合成需要满足两个条件，角度约束和时间限制.角度约束是为了保证待合成的目标均处于传感器的视野范围内，要求进行合成的两对象侧摆角之差不超过观测设备的视场角；时间限制是由传感设备自身决定的，是制造厂商为了保障设备的使用寿命而设定的最长开机时间，合成所得任务的总观测时间不能超过这个设定值.将合成条件用表达式(3)进行描述如下.

∀i,j∈[1,N],i≠j

(3)

其中,ΔFOV为卫星遥感传感器的视场角;ΔTon为传感器的最长开机时间.

任务合成后的侧摆角度以及可见窗口的起始和结束时间的计算分别如式(4)和式(5)所示.

(4)

(5)

(2) 合成任务选择.任务合成，一方面可以进行冲突关系的化解，但另一方面也可能会给观测增加一些不必要的区域，这主要针对于冲突的第二种情况而言，即可见窗口不交叉.对这种情况因合成产生的数据量化如图4所示，灰色框表示观测任务所产生的图像，即有效数据，白色框表示因观测不必要的区域所产生的冗余数据,因观测该区域所造成的能量损耗称为冗余消耗.

图4 冗余数据示意Fig.4 Redundant data

将任务m、n因合成产生的冗余存储RedDmn及冗余能量RedEmn用式(6)进行计算.

RedDmn=

RedEmn=

(6)

我们提出了基于最小耗费的启发式规则来进行最优合成对象的选择，引入评价指标EI，计算公式如式(7)所示.

∃m,n∈[1,N]

(7)

其中,α为评价参数，这里设定数据存储和能量具有相同的重要性，取α值为0.5，EI越小，代表合成造成的损耗越少，基于该值对合成对象做出选择.该规则的目的是减少对星载资源的浪费，给其它任务提供所需资源可被满足的机会，可提高任务的规划率.

3.2 基于蛙跳优化的序列规划

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)作为一种启发式群体进化算法，具有参数少、易实现的优点，其求解原理为：一群数量确定的青蛙通过在放置有不同数量食物的石头之间跳跃以找到食物最多的石头.青蛙在寻找食物过程会形成不同的族群，族群中的个体互相交流以更新自己的信息，交流完成后所有个体进行全局汇合，随后进行重新分组，直到寻找结束.

(8)

(9)

3.2.1 蛙跳优化算法 SFLA局部更新策略可通过数列极限[18]被证明为是收敛的，但更新仅针对于最差个体，忽略了其他个体的有用信息，导致解的收敛速度较慢，易出现局部早熟.本模块在SFLA的基础上进行改进，使优化后的算法以较短的时间求得最优的规划序列.

算法1 局部更新策略

mark global best frog forPgb

fori←0 tom-1 do

mark thei-thsubmemeplex as memplexi

iter←0

本文研究的社区养老设施体系构建是基于规划层面的,因此应参照《城市居住区规划设计规范》《城镇养老设施规划规范》及《养老设施建筑设计规范》的相关标准．综合3部规范对养老设施类型与项目的划分及前文对3种医养结合实现方式依托的设施类型研究,构建出医养结合模式下的社区养老设施类型体系(表2)．

while iter

iter←iter+1

start←rand() % (n-1)

end←rand() % (n-1-b) +b+ 1

forj←start to end do

mark the local best frog inmemplexiasPlb

mark thej-th frog in memplexiasPij

Ptemp← updatePijwithPlb

Pij←Ptemp

else

Ptemp← updatePijwithPgb

if(fitness(Ptemp)>fitness(Pij))thenPij←Ptemp

else

Pij←randomInit( )

endif

endif

endfor

endwhile

endfor

unitvalue=Weighti/TSi

(10)

图5 全局更新策略Fig.5 Global update strategy

3.2.2 序列规划算法流程 该模块基于蛙跳优化算法实现，流程如图6所示，对于图中的主要步骤说明如下.

(1) 适应度值计算.适应度是评价青蛙个体好坏的指标，其值为模型中目标函数的计算结果.

(2) 模因分组.模因组由青蛙个体按适应度值大小排序后进行种群分组得到.种群分组采用循环依次进组原则，循环的周期为模因组数量，每次循环每组只放入一个个体.

(3) 模因演化，即青蛙按改进后的局部更新策略进行跳跃.

(4) 全局交叉变异，即全局搜索.目的是进行精英个体筛选和保留.

HIPA核心由两个具有先后逻辑关系的模块构成，对于任务集T={t1,t2,…,tn},如果存在可合成情况下，首先，基于资源浪费最少的启发式规则进行合成对象的选择，待规划任务数量将变为m，m≤n.当ti,tj|i,j∈[1,n]有冲突时，按照单独规划的原则，则必有一个不能被执行，若可对其进行合成，则两个任务具有捆绑规划的性质，由此可提高任务的规划率.在序列规划过程中每一只青蛙都是一个长度为l的二进制位串，一个种群可看作是一个状态.当种群规模为N时,算法的状态空间为Ω={0,1}l·N.由于前一模块的合成，减少了任务数量，即l的取值从n变化成了m，有效地缩小了算法的状态空间.改进后的局部更新和全局更新策略使得第k+1轮算法开始时已拥有的解的上界不小于第k轮解的上界，保证精英个体不会向下逃逸，驱使最优青蛙不断向食物最多的石头跳跃，不断逼近解空间的最优解，从而HIPA向上收敛，算法向上快速收敛的性能将在实验部分得到验证.

图6 蛙跳优化算法流程示意

4 仿真实验

4.1 仿真实验设计

实验测试集借助Satellite Tool Kit软件[19]生成.利用该软件建立场景，设置一颗星载传感器视场角FOV为10°，观测侧摆范围为±30°的卫星.地面站目标随机分布在星下点周围，保证对卫星可见，卫星沿轨道运行生成目标点的可见窗口，每个目标点的优先级为区间[1,10]上的随机整数，观测需要的侧摆角取值范围为区间[-30°,+30°]上的随机数.

为验证本文所提出的启发式自主规划算法HIPA的有效性，实验设置了遗传算法(Genetic Algorithm,GA)、变邻域搜索算法(Variable Neighborhood Search,VNS)、人工蜂群算法(Artificial Bee Colnony,ABC)、贪婪蛙跳算法(Greedy Frog Leaping Algorithm,GFLA)等4组算法作为对照实验，各算法的参数设置具体如表2所示.

表2 不同算法参数设置

本文实验在操作系统为macOS High Sierra (10.13)，处理器为2.3 GHz Intel Core i5，内存为8 GB的笔记本上进行，实验开发平台为CLion 2018.3.1，开发语言为C++.

4.2 实验结果

本文对于任务数量分别为100、200、300的样本在星载资源条件不同的情况下分别用每种算法进行仿真验证，实验结果如表3和表4所示.

从表3和表4中可知，对于3种数量不同的任务集，本文提出的启发式自主规划算法在每种情况下均取得了收益最大值.通过对相同任务数量、不同资源限制的实验结果比较，发现资源因素对规划结果有着举足轻重的影响.在两种不同的星载资源限制条件下，随着样本数量的增加，5种算法取得的收益最优及平均都在逐渐增加，但遗传算法、人工蜂群算法的增长幅度略小于其他3种算法.本文提出的算法在对计算资源的消耗上达到了最小，尽管贪婪蛙跳算法和邻域搜索算法在收益上比遗传算法和人工蜂群算法得到了较优的回报，但时间耗费比人工蜂群算法多，且大于本文算法运行时长.

表3 算法在资源不充足时的实验结果

表4 算法在资源充足时的实验结果

星载资源有限且宝贵，充分利用有限的资源进行规划是需要不断追求的目标.为了直观地反映每种算法对于资源的利用率，我们就电量和存储两种资源做了统计和分析，如图7所示.

图7反映了不同算法在不同情况下对于不同资源的利用率不同.在资源不充足情况下，对于任务数为100的样本，本文所提出的算法对于两种资源的利用率皆达到了最高，但在任务数分别为200和300的样本集上，邻域搜索和本文算法相差无几. 值得注意的是在资源充足情况下，邻域搜索算法对于资源的利用率低于本文算法，略次于贪婪蛙跳算法.

(a) 存储利用率(资源不充足)

(b) 能量利用率(资源不充足)

(c) 存储利用率(资源充足)

(d) 能量利用率(资源充足)

为表明算法的收敛性，实验选取了GFLA作为对照试验组，将迭代终止条件手动设置为1 200，分别统计了不同迭代次数下的结果，如图8所示，横坐标为迭代次数，纵坐标为任务规划收益.

从图8可知，无论是资源充足或者资源不充足，HIPA都较快地收敛到了最优值，表现出了较好的收敛性能.

为清楚地反应不同算法运行不同次数所得规划方案结果的差异性，我们以序列总收益为指标，计算了资源限制不同、样本不同情况下各算法运行10次所得值的标准差，结果如图9所示.

从图9可以看出，启发式自主规划算法在相同样本相同资源条件下不同次数的运行所得收益的离散程度总体较小.尽管在样本任务数为300，资源不充足情况下，本文所提出的算法运行所得结果数值分布不如遗传算法集中，但遗传算法在其他情况下均表现出较大的离散性，因此我们可以认为启发式自主规划算法在任务规划结果上具有一定的稳定性.

(a) 算法在任务数为200，资源不充足情况下的收敛情况 (b) 算法在任务数为100，资源充足情况下的收敛情况

图8 算法收敛性能比较

Fig.8 Algorithm convergence performance comparison

(a) 资源不充足

(b) 资源充足

综合以上实验结果分析可得，本文所提出的面向小卫星的启发式自主规划算法能够在最短的时间内，使卫星利用自身有限的资源，以任务总收益最大化为目标进行观测序列的自主规划.

5 结 论

卫星自主规划任务作为提高卫星运行效率的手段之一，其重要性日渐增大[22-23].针对星上计算单元与星载资源有限的现状，本文提出了一种面向小卫星观测任务的启发式自主规划算法，算法采用分块思想将问题分为两个子模块求解，即基于启发式规则的任务合成与蛙跳优化序列规划，通过仿真实验表明所提出的启发式规划算法性能优于贪婪蛙跳算法、邻域搜索算法、遗传算法、人工蜂群算法等几种算法，能够有效利用计算资源生成任务序列，可为诸如工业生产、无人机任务规划、车辆路径规划等组合优化问题提供求解思路.下一步研究将在此基础上展开在动态资源下的大规模多窗口卫星任务自主规划；数传任务的自主规划体系以及规划算法的研究.