CN110400002A

CN110400002A - 一种多星成像任务规划方法

Info

Publication number: CN110400002A
Application number: CN201910540739.4A
Authority: CN
Inventors: 龙军; 钱哲曼; 陈仕隆; 韩笑冬; 徐楠; 杨凯飞
Original assignee: Central South University; China Academy of Space Technology CAST
Current assignee: Central South University; China Academy of Space Technology CAST
Priority date: 2019-06-21
Filing date: 2019-06-21
Publication date: 2019-11-01
Anticipated expiration: 2039-06-21
Also published as: CN110400002B

Abstract

本发明公开了一种多星成像任务规划方法，包括：建立任务模型，将所有点目标任务均使用任务模型表示；以轨道圈次为基准，以轨道圈次内的任务作为聚类图模型的节点，并基于聚类约束条件构建聚类图模型中各节点之间的无向边，得到成像任务聚类图模型；基于启发式规则将满足聚类约束条件的点目标任务聚合为聚类任务，并基于中位数定理计算聚类任务的侧摆角；构建并利用任务规划的约束条件和目标函数，构建与成像任务聚类图模型所对应的任务规划有向无环图模型；基于任务规划有向无环图模型，并采用最大最小蚁群算法进行任务规划，得到多星成像任务规划方案。在不同的数据规模下，本发明能够获得满意的任务规划结果且具有良好的稳定性。

Description

一种多星成像任务规划方法

技术领域

本发明涉及成像卫星任务规划领域，尤其涉及一种多星成像任务规划方法。

背景技术

成像卫星是装备有成像仪器的平台，以特定的轨道围绕地球飞行，根据用户需求对地面目标进行成像拍照；具有持续成像时间长、覆盖范围广、不受国界限制等特点，被广泛应用于测绘、军事侦察、环境保护以及国土普查等领域，得到了世界各国的高度重视。用户成像需求的增加导致在任务规划周期内只能对任务集合的一个子集安排成像观测，无法尽最大可能的满足更多的用户需求。为解决成像卫星供不应求的问题，更多的卫星被发射用于对地观测，但稀少的成像卫星资源在大量的用户成像需求面前仍然异常珍贵。

发明内容

基于目前成像卫星供不应求的问题，本发明提供一种多星成像任务规划方法，在有限的成像卫星资源与大量的用户成像需求之间寻求一种合理科学的规划方案，有助于充分利用卫星资源并实现用户需求满足度的最大化。

为实现上述技术目的，本发明采用如下技术方案：

一种多星成像任务规划方法，包括以下步骤：

步骤1，建立任务模型，将所有点目标任务均使用任务模型表示；

步骤2，将所有点目标任务构建成成像任务聚类图模型；

以卫星单个轨道圈次为基准进行构建聚类图模型；以在轨道圈次内的点目标任务分别作为聚类图模型中相应轨道圈次部分的1个节点，并基于聚类约束条件构建聚类图模型中各节点之间的无向边，得到成像任务聚类图模型；

步骤3，将满足聚类约束条件且能被卫星在同一个成像条带中完成观测的点目标任务，在成像任务聚类图模型中聚合为聚类任务；

步骤4，构建任务规划的约束条件和目标函数；利用任务规划的约束条件和目标函数，构建与步骤3得到的成像任务聚类图模型所对应的任务规划有向无环图模型；

步骤5，基于任务规划有向无环图模型，并采用最大最小蚁群算法进行任务规划；

步骤5.1，在任务规划有向无环图模型的每个轨道圈次的起始节点，均设置蚁群；

步骤5.2，分别针对任务规划有向无环图模型的每个轨道圈次，以当前轨道圈次的起始节点作为蚂蚁个体移动的起始位置，以当前轨道圈次的终止节点作为蚂蚁个体移动的终止位置，并利用启发式信息和信息素浓度作为蚂蚁个体的移动规则，使蚁群中的所有蚂蚁个体从起始位置移动至终止位置，获得蚁群所有蚂蚁个体的移动路径；

其中，相邻两个节点之间的启发式信息，由相邻两个节点之间的任务数量、姿态机动角度的大小和经度差构建得到；

步骤5.3，从每个轨道圈次的所有移动路径中选择被最多蚂蚁选择的移动路径，作为当前轨道圈次当次迭代周期的最优移动路径；

步骤5.4，更新每个轨道圈次到目前迭代周期为止的最优移动路径；

步骤5.5，利用启发式信息更新任务规划有向无环图模型的信息素浓度，返回步骤5.2进入下一个迭代周期；

步骤5.6，当达到迭代结束条件时，将每个轨道圈次的最优移动路径作为最终的多星成像任务规划方案。

本方案将满足聚类约束条件的点目标任务聚合为聚类任务，从而能够有效利用有限的成像卫星资源完成多个成像任务；然后采用最大最小蚁群算法对聚类后的任务进行任务规划，并在最大最小蚁群算法中引入任务数量、姿态机动角度以及经度差构建启发式信息和更新信息素浓度，可以保证蚂蚁进行路径选择的合理性，保证得到更优的任务规划方案。

进一步地，步骤1中建立的任务模型为MetaTask，表述为：MetaTask{IDSet,TimeWindowMap,Lat,Lon,Priority}；

其中，IDSet是若干单目标任务编号的集合；如果IDSet只包含一个编号，则该任务MetaTask是一个点目标任务；如果IDSet包含多个编号，则该任务是一个聚类任务；TimeWindowMap是一个以卫星的编号SatelliteID为键，以卫星与任务之间的可见时间窗列表为值的map集合；Lat表示该任务MetaTask的纬度；Lon表示该任务MetaTask的经度；Priority表示该任务MetaTask的优先级；

任务模型中的卫星模型为Satellite，表述为：

Satellite{SatelliteID,AllocatedTasks<MetaTask>,Eccentricity,SemiMajorAxis,Inclination,TrueAnomaly,AscNodeRAAN,Perigee,ConeAngle,AttitudeStabilizationTime,AttitudeSpeed}；

其中：SatelliteID表示卫星的编号，AllocatedTasks表示与该卫星存在可见时间窗的任务集合，Eccentricity表示卫星轨道的离心率，SemiMajorAxis表示卫星轨道的半长轴，Inclination表示卫星轨道的倾角，TrueAnomaly表示卫星轨道的真近点角，AscNodeRAAN表示卫星轨道的升交点赤经，Perigee表示卫星轨道的近地点幅角，ConeAngle表示卫星遥感器的视场角，AttitudeStabilizationTime表示卫星遥感器姿态稳定时间，AttitudeSpeed表示卫星遥感器姿态机动角速度；

任务模型中的可见时间窗模型为TimeWindow，表述为：

TimeWindow{ID,StartTime,EndTime,RollAngle_S,RollAngle_E}；

其中：ID表示可见时间窗的编号，StartTime表示该可见时间窗的开始时间，EndTime表示该可见时间窗的结束时间，RollAngle_S表示该可见时间窗口起始时间所对应的侧摆角，RollAngle_E表示该可见时间窗口结束时间所对应的侧摆角。

进一步地，所述聚类任务T的侧摆角的计算方法为：

计算聚类任务T中所有点目标任务的侧摆角取值范围的交集，将得到的交集作为的侧摆角取值范围△θ，获取聚类任务T中各点目标任务的最佳侧摆角集合B；

对最佳侧摆角集合B中的最佳侧摆角按大小顺序排序，得到集合B′并计算集合B′的中位数M；

判断中位数M与聚类任务T的侧摆角取值范围△θ的关系：如果中位数M在聚类任务T的侧摆角取值范围△θ内，则将中位数M作为聚类任务T的侧摆角；如果中位数M大于聚类任务T的侧摆角取值范围△θ的上界，则将聚类任务T的侧摆角取值范围的上界作为聚类任务T的侧摆角；如果中位数M小于聚类任务T的侧摆角取值范围△θ的下界，则将聚类任务T的侧摆角取值范围的下界作为聚类任务T的侧摆角。

本方案基于中位数原理的聚类任务侧摆角计算方法，减少了聚类任务成像质量的损失。对于聚类任务中的每一个点目标任务，都有一个最佳侧摆角，即成像卫星遥感器转到正对点目标任务的位置，在该最佳侧摆角的位置，对点目标任务的观测效果最佳；卫星遥感器对点目标任务的侧摆角与最佳侧摆角的差值越大，对点目标任务的观测效果越差。所以在考虑成像质量的因素下，可将求聚类任务最佳侧摆角的问题转化为：在聚类任务的侧摆角取值范围内取一个侧摆角，使得其与各个点目标任务的最佳侧摆角相减得到的绝对值之和最小。而根据中位数原理可知，在数轴上，与n个点的距离之和最小的点即是n个点的中位数，由此可知，本发明基于中位数原理将聚类任务中各点目标任务的最佳侧摆角的中位数，作为聚类任务的侧摆角，可以减少聚类任务因侧摆角取值造成的成像质量的损失。

进一步地，所述聚类约束条件包括：侧摆角约束、最大开机时间约束和空闲时间约束，

所述侧摆角约束是指，如果若干个点目标任务t₁、t₂、t₃……、t_k能够聚类为聚类任务T，则相应的侧摆角△θ₁、△θ₂、△θ₃……、△θ_k需满足：

所述最大开机时间约束是指，如果若干个点目标任务能够聚类为聚类任务T，则其中任意两个点目标任务t_l、t_k均需满足：

max(te_k,te_l)-min(ts_k,ts_l)≤MaxDuration；

式中，ts_k、te_k分别表示点目标任务t_k的可见时间窗[ts_k,te_k]的起始时间和结束时间，ts_l、te_l分别表示点目标任务t_l的可见时间窗[ts_l,te_l]的起始时间和结束时间，MaxDuration表示遥感器开机执行一次成像观测的最长时间限制；

所述空闲时间约束是指，如果两个点目标任务t_l、t_k能够聚类为聚类任务T，需满足：

WT_kl＝max(te_l-te_k,0)；

式中，WT_kl表示遥感器在两个点目标任务t_l和t_k之间的成像空闲时间，表示遥感器在两个点目标任务t_l和t_k之间的姿态调整时间，D_min表示遥感器的姿态稳定时间；Roll_l、Roll_k分别表示两个点目标任务t_l和t_k在同一轨道圈次内的侧摆角，v表示遥感器姿态机动速度；

当若干个点目标任务同时满足侧摆角约束、最大开机时间约束和空闲时间约束这3个约束条件时，则该若干个点目标任务满足聚类约束条件，可以聚合为聚类任务T；

当两个点目标任务不满足空间时间约束，但是满足侧摆角约束和最大开机时间约束、且在这两个任务之间存在满足聚类条件的多个点目标任务，则该两个点目标任务满足传递性聚类条件，可以聚合为聚类任务T。

进一步地，步骤2的具体过程为：

步骤2.1，获取卫星在第i个轨道圈次存在可见时间窗的点目标任务集G；

步骤2.2，对点目标任务的侧摆角的取值范围进行调整；

步骤2.3，以每个点目标任务分别作为1个节点，判断点目标任务集G中的任意两个点目标任务是否满足聚类约束条件，若满足则在该两个点目标任务相应的两个节点之间构建无向边；

步骤2.4，找出点目标任务集G中包含的所有连通图，得到初始任务聚类模型CGM；

步骤2.5，对初始任务聚类模型CGM中的每一个连通图中的任意两个不存在无向边的点目标任务，判断是否满足传递性聚类条件，若满足则在该两个点目标任务相应的两个节点之间构建无向边；

步骤2.6，令i＝i+1，返回步骤2.1；直到得到包括所有轨道圈次部分的成像任务聚类图模型。

进一步地，步骤3的具体过程为：

步骤3.1，获取卫星S第i个轨道圈次的任务聚类图模型CGM中的一个连通图G，令P为连通图G中所包含的节点集合，初始化聚类结果集合ClusterRes；

步骤3.2，若P为空，转步骤3.9；否则，从节点集合P中选取度最大的节点p1；若度最大的节点不唯一，随机选择一个节点，并将节点p1所有的邻居节点加入到第一集合p1_Neigh；其中，节点的度是指与该节点相连的无向边的数量，节点的邻居节点是指与该节点之间具有无向边连接的节点；

步骤3.3，若第一集合p1_Neigh为空，转步骤3.8；否则，从第一集合p1_Neigh中选取与节点p1具有最多公共邻居的节点，并加入到第二集合p1_MaxCommNeigh；

步骤3.4，若第二集合p1_MaxCommNeigh包含的节点唯一，令p2＝p1_MaxCommNeigh[0]，转步骤7；若第二集合p1_MaxCommNeigh包含的节点不唯一，转步骤3.5；

步骤3.5，从第二集合p1_MaxCommNeigh中选取与节点p1具有最少无关边的节点，并加入第三集合p1_MinUnRelatedEdge；若第三集合p1_MinUnRelatedEdge中包含的节点唯一，令p2＝p1_MinUnRelatedEdge[0]，转步骤3.7；若第三集合p1_MinUnRelatedEdge中包含的节点不唯一，转步骤3.6；

步骤3.6，从第三集合p1_MinUnRelatedEdge中选取优先级最大的节点，若优先级最大的节点不唯一，则选取与节点p1组成的无向边中边权值最小的节点，并置为p2；

其中，无向边的边权值是指，无向边两端的节点之间的成像空闲时间；

步骤3.7，删除边(p1,p2)的无关边，将节点p1、p2合并为新的节点p1，从节点集合P中删除节点p2，更新第一集合p1_Neigh，转步骤3.3；

步骤3.8，将节点p1加入到聚类结果ClusterRes中，转步骤3.2；

步骤3.9，输出聚类结果ClusterRes，结束；

其中，聚类结果ClusterRes的模型为MSITCR<SatelliteID,ClusterResList<ClusterTask>>，是一个以卫星编号SatelliteID为键、以聚类任务列表ClusterResList为值的键值对集合；且聚类任务的模型为ClusterTask{OrbitID,MetaTaskIDSet,TW{StartTime,EndTime},RollAngle}；

聚类任务的模型中，OrbitID是卫星轨道圈次的编号，表明相应的聚类任务是属于卫星哪个轨道圈次；MetaTaskIDSet是组成该聚类任务的点目标任务编号的集合，TW对应着聚类任务与编号为SatelliteID的卫星在第OrbitID个轨道圈次内的可见时间窗，StartTime是开始时间，EndTime是结束时间，RollAngle是聚类任务所对应的侧摆角。

进一步地，所述任务规划的约束条件为：

s_jk+dur_j+tran_jmk+ST_i≤s_mk，

式中，y_jk表示任务t_j是否安排在卫星S_i第k个轨道圈次进行成像观测，y_jk＝1表示安排，y_jk＝0表示不安排；K_i表示卫星S_i在任务规划周期内绕地球飞行的总圈数；s_jk表示任务t_j在所属卫星第k个轨道圈次观测开始时间，t_j∈T_ik；T_ik表示卫星S_i在第k个轨道圈次有时间窗口的候选任务集合，n₂为与卫星S_i在第k个轨道圈次有时间窗口的候选任务数量，且有T_ik∈T_i；T_i表示卫星S_i所分配到的候选成像任务聚合，n₁为卫星S_i所分配到的候选成像任务数量，有s_mk表示任务t_m在所属卫星第k个轨道圈次观测开始时间，t_m∈T_ik；dur_j表示任务t_j的观测持续时长；tran_jmk表示在所属卫星第k个轨道圈次内相继执行的任务j与任务m之间所需的姿态转换时间；ST_i表示卫星S_i姿态稳定时间；EO_i表示卫星S_i在进行成像观测时，成像遥感器的能量消耗速率；x_jh表示任务t_h是否能够被安排在任务t_j后执行成像观测，x_jh＝1表示能够，x_jh＝0表示不能够；ES_i表示卫星S_i在进行姿态机动时的能量消耗速率；angle_jhk表示在卫星第k个轨道圈次相继执行的任务t_j与t_h之间的姿态机动角度；v_i表示卫星S_i进行姿态机动的速度；E_i表示卫星S_i在一个轨道圈次内能量消耗的最大值；

所述任务规划的目标函数为：

式中，N表示任务规划方案的成像观测活动次数。

进一步地，在步骤5.2中所述利用启发式信息和信息素浓度作为蚂蚁个体的移动规则为：蚂蚁个体ant_k当前节点为任务t_i时，计算其选择任务作为下一节点的概率，然后选择概率最大的任务作为下一节点，其中概率p_tj的计算公式为：

式中，表示蚂蚁个体ant_k从当前节点i能够达到的所有节点的集合，τ_ij表示从节点i到节点j路径上的信息素浓度值，η_ij表示从节点i到节点j路径所对应的启发式信息值，α和β分别表示信息素浓度和启发式信息的权重，q₀为常量值，q是一个大于0小于1的随机数；

所述启发式信息η_ij的计算方法为：

式中，TC_ij表示节点i到节点j路径所包含的聚类任务的数量，angle_ij表示从节点i到节点j卫星姿态机动角度的大小，Math.abs(Lon_j-Lon_i)表示节点i与节点j的经度差的绝对值；

中间量ψ的计算方法为：

信息素浓度τ_ij的迭代更新方法为：

式中，antSize表示蚁群中蚂蚁个体的数量，Q_C表示单只蚂蚁个体在当前迭代周期的移动路径的启发式信息的总和，Q_L表示蚁群所有蚂蚁个体在当前迭代周期的最优移动路径的启发式信息的总和，Q_G表示蚁群所有蚂蚁个体到目前迭代周期为止的最优移动路径的启发式信息的总和，q′₀是一个固定的常量值，q′是一个大于0小于1的随机数。

蚂蚁个体的移动规则中和信息素浓度更新策略中，引入随机性机制，可保证蚂蚁进一步搜索解空间的可能性，弥补最大最小蚁群算法容易陷入局部最优的不足，从而保证得到更优的任务规划方案。

进一步地，所述信息素浓度的限制区间为[τ_min,τ_max]，当计算得到的信息素浓度超出限制区间时，按以下公式进行修正：

该方案可以避免最大最小蚁群算法过早的收敛于局部最优解，从而保证得到更优的任务规划方案。

进一步地，所述点目标任务是指卫星遥感器对地面目标执行的成像任务。

有益效果

本发明提出了一种多星成像任务规划方法，设计了基于启发式规则的成像任务聚类算法，降低了任务聚类结果的不确定性；设计了基于中位数原理的聚类任务侧摆角计算方法，减少了聚类任务成像质量的损失。基于最大最小蚁群算法设计了进行任务规划方案局部更新的多星成像任务规划算法；任务规划方案构造过程中引入的任务数量、姿态机动角度以及经度差启发式信息保证了蚂蚁位置移动过程中的合理性；算法中引入的随机机制有效的避免了蚁群算法容易陷入局部最优的不足。成像任务聚类与成像任务规划方案局部更新成功的起到了增加任务满足度、减少算法运行时间的作用。在不同的数据规模下，本发明所提出的多星成像任务规划算法均能够获得满意的任务规划结果且具有良好的稳定性。

附图说明

图1为遥感器侧摆示意图；

图2为本发明的聚类任务侧摆角计算方法流程图；

图3为本发明任务、卫星、时间窗口关系示意图；

图4为本发明的任务聚类图模型示意图；

图5为本发明的任务规划有向无环图模型示意图；

图6为本发明的多星成像任务规划算法流程图；

图7为本发明的任务规划方案局部更新示意图。

具体实施方式

下面对本发明的实施例作详细说明，本实施例以本发明的技术方案为依据开展，给出了详细的实施方式和具体的操作过程，对本发明的技术方案作进一步解释说明。

本发明提出一种多星成像任务规划方法，包括成像任务聚类方法与任务规划方法；成像任务聚类，通过构建成像任务聚类图模型将所述成像任务聚类问题转化为图论团划分问题，并设计基于启发式规则的成像任务聚类算法，负责将能够被成像卫星在同一个成像条带中完成观测的点目标成像任务聚合为聚类任务；任务规划，通过构建任务规划有向无环图模型，将任务规划问题转化为求图中包含成像任务数量最多路径的问题，并基于最大最小蚁群算法设计了进行任务规划方案局部更新的多星任务规划算法，负责对任务聚类结果进行规划，完成成像任务时间窗口选择的关键问题。

一、成像任务聚类

1、聚类约束条件

由于成像卫星资源有限，为有效利用有限的成像卫星资源，故本发明将满足特定聚类约束条件且能够被同一个成像卫星在同一个成像条带中完成观测的点目标任务聚合为聚类任务。在本发明中，点目标任务即是指成像任务。

在本发明中，聚类约束条件包括侧摆角约束和时间约束；

所述侧摆角是指卫星遥感器因指向地面目标进行姿态机动后，地面成像目标、卫星遥感器以及卫星星下点三者之间形成的夹角；

所述卫星星下点是指卫星在地面的投影点；

如图1所示，σ表示卫星S的视场角；表示卫星对任务t_i执行观测时的观测角度，记该观测角度为卫星执行任务t_i的侧摆角；成像遥感器对准地面目标时的成像效果最好，将此时成像遥感器的观测角度记为卫星对任务t_i执行观测时的最佳观测角度θ_i；

只要地面点目标任务t_i在遥感器的覆盖范围内，对于任意侧摆角遥感器都能对其进行成像观测；

一般情况下，出于对观测图像质量的考虑，需要对侧摆角取值范围进行修正，设修正后的侧摆角取值范围为：

所述侧摆角约束指：如果若干个观测任务t₁、t₂、t₃……、t_k能够聚类，必有成立。

所述时间约束包括最大开机时间约束和成像空闲时间约束；

成像遥感器开机进行一次成像观测的时间长度是受到限制的，设为MaxDuration，所述最大开机时间约束指：若点目标观测任务t₁、t₂、t₃……、t_k能够聚类为聚类任务T，必有式(2)成立：

max(te_k,te_l)-min(ts_k,ts_l)≤MaxDuration 公式(2)；

所述成像空闲时间是指成像遥感器对地面连续两个点目标任务执行成像观测过程中，耗费在两个点目标任务之间的无效观测区域上的时间；

设点目标任务t_i和t_k在同一个轨道圈次内对应的侧摆角分别为Roll_i、Roll_k，则成像遥感器在两个点目标t_i和t_k之间的姿态调整时间为：

其中：v(°/s)表示遥感器姿态机动速度；

设卫星对任务t_k、t_l在同一轨道圈次内的可见时间窗口分别为[ts_k,te_k]、[ts_l,te_l]，且设ts_k<ts_l，则任务t_k与t_l之间的成像空闲时间为：

WT_kl＝max(te_l-te_k,0) 公式(4)；

所述成像空闲时间约束指：设成像遥感器的姿态稳定时间为D_min，则两个点目标任务t_i和t_k如果在同一轨道圈次内能够聚类，须有式(5)成立：

此外，也许两个点目标任务t_i和t_j不满足成像空闲时间约束，却满足侧摆角约束和最大开机时间约束，且在这两个任务之间存在多个满足聚类约束的任务，即满足传递性聚类，仍然可以将点目标任务t_i和t_j聚合到一个聚类任务中。

2、关系建模

一个成像任务，可以为点目标任务或经聚合得到的聚类任务，可能与多颗成像卫星在多个轨道圈次内存在多个时间窗口，三者之间的关系如图3所示，且根据三者之间的关系建立如下模型：

(1)可见时间窗模型TimeWindow，表述为：

TimeWindow{ID,StartTime,EndTime,RollAngle_S,RollAngle_E}

(2)任务模型MetaTask，表述为：

MetaTask{IDSet,TimeWindowMap,Lat,Lon,Priority}；

其中：IDSet是若干单目标任务编号的集合；如果IDSet只包含一个编号，则该任务MetaTask是一个点目标任务；如果IDSet包含多个编号，则该任务是一个聚类任务；TimeWindowMap是一个以卫星的编号SatelliteID为键，以卫星与任务之间的可见时间窗列表为值的map集合；Lat表示该任务MetaTask的纬度；Lon表示该任务MetaTask的经度；Priority表示该任务MetaTask的优先级。

(3)卫星模型为Satellite，表述为：

其中：SatelliteID表示卫星的编号，AllocatedTasks表示与该卫星存在可见时间窗的任务集合，Eccentricity表示卫星轨道的离心率，SemiMajorAxis表示卫星轨道的半长轴，Inclination表示卫星轨道的倾角，TrueAnomaly表示卫星轨道的真近点角，AscNodeRAAN表示卫星轨道的升交点赤经，Perigee表示卫星轨道的近地点幅角，ConeAngle表示卫星遥感器的视场角，AttitudeStabilizationTime表示卫星遥感器姿态稳定时间，AttitudeSpeed表示卫星遥感器姿态机动角速度。

3、任务聚类图模型构建

将点目标任务使用上述任务模型表示，然后使用聚类约束条件将能被卫星在同一个成像条带中完成观测的点目标任务，在成像任务聚类图模型中聚合为聚类任务，并将聚类任务同样使用上述任务模型表示。其中在成像任务聚类图模型中聚合为聚类任务的过程为：

本发明以点目标任务作为聚类图模型中的节点，以卫星单个轨道圈次为基准，构建聚类图模型ClusterGraphModel:List<G,V>，简称CGM，CGM是一个由若干个连通图组成的连通图集合。G代表一个连通图，V表示连通图G的节点集(即图论中的顶点)，节点之间的无向边通过聚类约束条件逐步构建；

其中，成像任务聚类图模型的具体构建步骤如下所述：

步骤A1，获取卫星在第i个轨道圈次存在时间窗口的点目标任务集G；

步骤A2，对点目标任务的侧摆角的取值范围进行调整；

步骤A3，以每个点目标任务分别作为1个节点，判断点目标任务集G中的任意两个点目标任务是否满足聚类约束条件，若满足则在该两个点目标任务相应的两个节点之间构建无向边；

步骤A4，找出点目标任务集G中包含的所有连通图，得到初始任务聚类模型CGM；

步骤A5，对初始任务聚类模型CGM中的每一个连通图中的任意两个不存在无向边的点目标任务，判断是否满足传递性聚类条件，若满足则在该两个点目标任务相应的两个节点之间构建无向边；

步骤A6，令i＝i+1，返回步骤A1；直到得到包括所有轨道圈次部分的成像任务聚类图模型。

如图4所示为例，进一步阐述任务聚类图模型的构建：在图4(a)中，小矩形的高度表示成像遥感器的视场角范围，任务{1,2,3}、任务{5,6,7,8,9}、任务{11,12}、任务{7,9,10}、任务{8,11}能够聚合为一个聚类任务；其中，任务{1,3}、任务{5,7}、任务{5,8}、任务{5,9}、任务{6,8}、任务{6,9}、任务{7,9}、任务{10,9}不满足成像空闲时间约束，但满足传递性聚类，从而也能够聚类；其他任务因不满足聚类约束条件无法聚类。如果若干个点目标任务可以聚类，则任意两个点目标任务之间均有一条无向边相连。综合上述内容，构建了图4(b)所示的任务聚类图模型，进而将点目标任务聚类问题转化为团划分问题。

4、基于启发式规则的成像任务聚类算法

本发明提出的成像任务聚类方法的步骤如下所述：

步骤B1，获取卫星S第i个轨道圈次的任务聚类图模型CGM中的一个连通图G，令P为连通图G中所包含的节点集合，初始化聚类结果集合ClusterRes；

步骤B2，若节点集合P为空，转步骤B9；否则，从节点集合P中选取度最大的节点p₁；若度最大的节点不唯一，随机选择一个节点，并将节点p₁所有的邻居节点加入到第一集合p₁_Neigh；其中，节点的度是指与该节点相连的无向边的数量，节点的邻居节点是指与该节点之间具有无向边连接的节点；

步骤B3，若第一集合p₁_Neigh为空，转步骤B8；否则，从第一集合p₁_Neigh中选取与节点p₁具有最多公共邻居的节点，并加入到第二集合p1_MaxCommNeigh；

步骤B4，若第二集合p1_MaxCommNeigh包含的节点唯一，令p₂＝p1_MaxCommNeigh[0]，转步骤7；若第二集合p1_MaxCommNeigh包含的节点不唯一，转步骤B5；

步骤B5，从第二集合p1_MaxCommNeigh中选取与节点p₁具有最少无关边的节点，并加入第三集合p1_MinUnRelatedEdge；若第三集合p1_MinUnRelatedEdge中包含的节点唯一，令p₂＝p1_MinUnRelatedEdge[0]，转步骤B7；若第三集合p1_MinUnRelatedEdge中包含的节点不唯一，转步骤B6；

无关边的理解为：若边e1以边e2的一个顶点为顶点，但另一个顶点不是e2的公共邻居，则称e1为e2的无关边。

步骤B6，从第三集合p1_MinUnRelatedEdge中选取优先级最大的节点，若优先级最大的节点不唯一，则选取与节点p1组成的无向边中边权值最小的节点，并置为p2；

步骤B7，删除边(p₁,p₂)的无关边，将节点p₁、p₂合并为新的节点p₁，从节点集合P中删除节点p₂，更新第一集合p₁_Neigh，转步骤B3；

步骤B8，将节点p₁加入到聚类结果ClusterRes中，转步骤B2；

步骤B9，输出聚类结果ClusterRes，结束。

聚类任务的模型中，OrbitID是卫星轨道圈次的编号，表明相应的聚类任务是属于卫星哪个轨道圈次；MetaTaskIDSet是组成该聚类任务的点目标任务编号的集合，TW对应着聚类任务与编号为SatelliteID的卫星在第OrbitID个轨道圈次内的时间窗口，StartTime是开始时间，EndTime是结束时间，RollAngle是聚类任务所对应的侧摆角。

对各点目标任务聚类得到的聚类任务，其侧摆角的计算方法如图2所示，如果得到的中位数在聚类任务的侧摆角取值范围内，则聚类任务的侧摆角的大小等于该中位数；如果该中位数大于聚类任务侧摆角取值范围的上界，则聚类任务的侧摆角的大小等于侧摆角取值范围的上界；否则，聚类任务的侧摆角的大小等于侧摆角取值范围的下界。

二、任务规划

经上述第一部分成像任务聚类后，将满足聚类约束条件的若干个点目标任务被聚合为聚类任务，且统一将聚类任务使用前述的任务模型表示，然后需要对聚类后的任务(包括聚合任务和未被聚合的点目标任务)通过构建问题模型以生成任务规划方案。

所述问题模型包括任务规划优化目标模型与任务规划有向无环图模型；

所述任务规划方案指：由一组相邻两个成像任务能够先后执行观测的成像任务组成的集合；任务规划方案中的每一个成像任务均包含成像观测起止时间和卫星遥感器侧摆角信息；此外，任务规划方案还包括任务完成度和卫星姿态机动角度总和两个评价指标。

1、构建问题模型

对任务规划优化目标模型中的参数进行定义，如下所述：

根据任务规划目标与任务规划模型参数，本发明设计了如下任务规划模型：

约束条件：

s_jk+dur_j+tran_jmk+ST_i≤s_mk 公式(7)；

任务规划目标函数：

公式(6)表示成像任务执行唯一性约束，即任意一个成像任务最多执行一次；公式(7)为卫星连续观测时间约束，对于两个能够安排在卫星S_i第k个轨道圈次内相继执行观测的成像任务t_j、t_m，需要满足此约束条件；公式(8)是能量约束条件，表示卫星S_i在某个轨道圈次内的耗能不能超过能量消耗的上限；公式(9)为成像任务规划问题的优化目标函数，表示最大化的任务完成数量；

对于两个不同的任务规划方案，若它们的任务满足度相等，优先选择姿态机动角度总和较小的任务规划方案。用数学方式表示如下：

公式(10)中N表示任务规划方案的成像观测活动次数；

本发明对多星成像任务规划问题构建了如图5所示的任务规划有向无环图模型，图5中每个子图Gi对应着一个轨道圈次，白色表示任务只存在一个时间窗口，黑色表示任务存在多个时间窗口出于美观的目的，图5只画出了每个子图Gi中部分从S节点指向非E节点的有向边；

2、基于最大最小蚁群算法的多星成像任务规划算法

结合任务规划有向无环图模型，本发明设计了一种基于最大最小蚁群算法的多星成像任务规划算法(Max-Min Ant Colony Optimization-Local Update,MM-ACO-LU)，将多星成像任务规划问题转化为求图中满足目标优化函数的最佳路径问题，算法流程如图6所示；

所述MM-ACO-LU算法包括任务规划方案构造、任务规划方案的局部更新以及信息素的更新三大模块；

所述任务规划方案构造负责构造有向无环图模型每个子图中由节点S到节点E的路径，所有路径组成了最终的任务规划结果；

所述任务规划方案的构造通过蚂蚁位置的移动完成，假设蚂蚁ant_k当前位置为任务t_i，则蚂蚁ant_k选择任务作为下一个位置的规则如下：

所述规则中，表示从蚂蚁ant_k当前所在位置i能够达到的所有节点的集合，τ_ij表示从节点i到节点j路径上的信息素浓度值，η_ij表示从节点i到节点j路径所对应的启发式信息值，α和β分别表示信息素浓度和启发式信息的权重，q₀是一个固定的常量值，q是一个大于0小于1的随机数。

本发明，在蚂蚁个体的移动规则中引入随机性机制，可保证蚂蚁进一步搜索解空间的可能性，弥补蚁群算法容易陷入局部最优移动路径的不足，从而能得到最优的任务规划方案。

公式(11)的含义为：假设蚂蚁ant_k当前位置为i，生成一个随机数q，如果q≤q₀，则将[τ_ij]^α×[η_ij]^β的值作为蚂蚁ant_k选取任务t_j作为下一个节点的概率，否则将ψ作为蚂蚁k选取任务t_j作为下一个节点的概率；最终蚂蚁从集合中选取p_tj值最大的节点作为下一个节点；

所述启发式信息η_ij的计算方法如下：

公式(12)中，TC_ij表示节点i到节点j路径所包含的成像任务的数量，angle_ij表示从节点i到节点j卫星姿态机动角度的大小，Math.abs(Lon_j-Lon_i)表示节点i与节点j的经度之差的绝对值。

本发明通过引入相邻两个节点之间的任务数量、姿态机动角度以及经度差构建启发式信息，从而保证蚂蚁个体在任务规划有向无环图模型中选择下一个移动节点的合理性。

公式(11)中，ψ的计算方法如下所示：

所述任务规划方案局部更新负责对任务规划方案构造步骤生成的任务规划方案进行更新，且只寻找相邻两个任务之间长度为二的路径，如图7所示，进行任务规划方案局部更新能够得到更符合目标优化函数的任务规划方案，从而降低任务规划方案的运行时间。

本发明提出了一种基于任务数量优先规则的任务规划方案局部更新方法，步骤如下：

步骤C1，令schedule为轨道圈次O₁的任务规划方案，i＝0，t1＝schedule.get(i)；

步骤C2，若i等于schedule包含的任务数量，转步骤C7，否则，转步骤C3；

步骤C3，令next为t1在轨道圈次O₁未安排成像观测的后继节点集合，t2＝schedule.get(i+1)，j＝0；

步骤C4，j＝j+1，若j小于next集合的大小，转步骤5，否则，转步骤C2；

步骤C5，t3＝next.get(j)，若t3等于t2，且t3加入到schedule后满足公式(8)约束，则将t3添加到schedule的第i+1个位置，转步骤C6，否则，转步骤C4；

步骤C6，i＝i+1，t1＝＝schedule.get(i)，t2＝schedule.get(i+1)，转步骤C2；

步骤C7，结束。

所述信息素更新负责当所有蚂蚁完成任务规划方案的构造后对有向无环图所有路径上的信息素浓度进行更新，本发明设计了一种充分利用全局信息与局部信息的信息素更新方式，如下所示：

其中，antSize表示蚁群中蚂蚁个体的数量，Q_C表示单只蚂蚁个体在当前迭代周期的移动路径的启发式信息的总和，Q_L表示蚁群所有蚂蚁个体在当前迭代周期的最优移动路径的启发式信息的总和，Q_G表示蚁群所有蚂蚁个体到目前迭代周期为止的最优移动路径的启发式信息的总和；q′₀是一个固定的常量值，q′是一个大于0小于1的随机数；

Q_C的计算方式如下：

Q_G的计算方式如下：

Q_L的计算方式如下：

S_L表示当前迭代周期得到的最优移动路径，S_C表示蚂蚁当前迭代周期得到的移动路径，S_G表示到目前为止得到的最优移动路径，Q_G表示蚁群所有蚂蚁个体到目前迭代周期为止的最优移动路径的启发式信息的总和；η_all表示所有路径上的启发式信息的总和，函数f()用于计算相应路径的启发式信息总和。

本发明，在信息素更新策略中引入随机性机制，可保证蚂蚁进一步搜索解空间的可能性，弥补蚁群算法容易陷入局部最优移动路径的不足，从而能得到最优的任务规划方案。

为避免MM-ACO-LU算法过早的收敛于局部最优解，在进行信息素的更新过程中将路径上的信息素限制于[τ_min,τ_max]，即：

以上实施例为本申请的优选实施例，本领域的普通技术人员还可以在此基础上进行各种变换或改进，在不脱离本申请总的构思的前提下，这些变换或改进都应当属于本申请要求保护的范围之内。

Claims

1.一种多星成像任务规划方法，其特征在于，包括以下步骤：

步骤2，将所有点目标任务构建成成像任务聚类图模型；

2.根据权利要求1所述的方法，其特征在于，步骤1中建立的任务模型为MetaTask，表述为：MetaTask{IDSet,TimeWindowMap,Lat,Lon,Priority}；

其中，IDSet是若干单目标任务编号的集合；如果IDSet只包含一个编号，则该任务MetaTask是一个点目标任务；如果IDSet包含多个编号，则该任务是一个聚类任务；

TimeWindowMap是一个以卫星的编号SatelliteID为键，以卫星与任务之间的可见时间窗列表为值的map集合；Lat表示该任务MetaTask的纬度；Lon表示该任务MetaTask的经度；Priority表示该任务MetaTask的优先级；

任务模型中的卫星模型为Satellite，表述为：

任务模型中的可见时间窗模型为TimeWindow，表述为：

TimeWindow{ID,StartTime,EndTime,RollAngle_S,RollAngle_E}；

3.根据权利要求2所述的方法，其特征在于，所述聚类任务T的侧摆角的计算方法为：

4.根据权利要求2所述的方法，其特征在于，所述聚类约束条件包括：侧摆角约束、最大开机时间约束和空闲时间约束，

max(te_k,te_l)-min(ts_k,ts_l)≤MaxDuration；

5.根据权利要求4所述的方法，其特征在于，步骤2的具体过程为：

步骤2.2，对点目标任务的侧摆角的取值范围进行调整；

6.根据权利要求5所述的方法，其特征在于，步骤3的具体过程为：

步骤3.2，若P为空，转步骤3.9；否则，从节点集合P中选取度最大的节点p₁；若度最大的节点不唯一，随机选择一个节点，并将节点p₁所有的邻居节点加入到第一集合p₁_Neigh；其中，节点的度是指与该节点相连的无向边的数量，节点的邻居节点是指与该节点之间具有无向边连接的节点；

步骤3.3，若第一集合p₁_Neigh为空，转步骤3.8；否则，从第一集合p₁_Neigh中选取与节点p₁具有最多公共邻居的节点，并加入到第二集合p1_MaxCommNeigh；

步骤3.4，若第二集合p1_MaxCommNeigh包含的节点唯一，令p₂＝p1_MaxCommNeigh[0]，转步骤7；若第二集合p1_MaxCommNeigh包含的节点不唯一，转步骤3.5；

步骤3.5，从第二集合p1_MaxCommNeigh中选取与节点p₁具有最少无关边的节点，并加入第三集合p1_MinUnRelatedEdge；若第三集合p1_MinUnRelatedEdge中包含的节点唯一，令p₂＝p1_MinUnRelatedEdge[0]，转步骤3.7；若第三集合p1_MinUnRelatedEdge中包含的节点不唯一，转步骤3.6；

步骤3.7，删除边(p₁,p₂)的无关边，将节点p₁、p₂合并为新的节点p₁，从节点集合P中删除节点p₂，更新第一集合p₁_Neigh，转步骤3.3；

步骤3.8，将节点p₁加入到聚类结果ClusterRes中，转步骤3.2；

步骤3.9，输出聚类结果ClusterRes，结束；

7.根据权利要求2所述的方法，其特征在于，所述任务规划的约束条件为：

s_jk+dur_j+tran_jmk+ST_i≤s_mk，

所述任务规划的目标函数为：

式中，N表示任务规划方案的成像观测活动次数。

8.根据权利要求2所述的方法，其特征在于，在步骤5.2中所述利用启发式信息和信息素浓度作为蚂蚁个体的移动规则为：蚂蚁个体ant_k当前节点为任务t_i时，计算其选择任务作为下一节点的概率，然后选择概率最大的任务作为下一节点，其中概率的计算公式为：

所述启发式信息η_ij的计算方法为：

中间量ψ的计算方法为：

信息素浓度τ_ij的迭代更新方法为：

9.根据权利要求8所述的方法，其特征在于，所述信息素浓度的限制区间为[τ_min,τ_max]，当计算得到的信息素浓度超出限制区间时，按以下公式进行修正：

10.根据权利要求1所述的方法，其特征在于，所述点目标任务是指卫星遥感器对地面目标执行的成像任务。