航天器任务调度模型、算法与通用求解技术综述

杜永浩 邢立宁 姚 锋 陈盈果

21 世纪以来,我国航天事业步入快速发展时期.随着“高分辨率对地观测系统”、“北斗卫星导航定位系统”等国家重大专项的相继开展,以及商业航天产业的蓬勃发展,我国在轨航天器规模持续增加,总数位居世界第二.在此期间,各类航天器平台与载荷能力也经历了深刻变革.为适应大规模、复杂化的航天器管控新常态,融合现代运筹学、计算科学与相关领域知识的航天器任务调度技术起到了举足轻重的作用.

航天器任务调度技术是指在航天器使命任务与管控需求的驱动下,通过对任务与资源的建模,消解航天器任务执行过程中的约束冲突,最大化航天器任务与管控效益的一种优化技术.在诸多学者与航天从业人员的推动下,航天器任务调度技术得到了快速的发展,在美国DigitalGlobe 高分辨率对地观测系统、欧盟Galileo 卫星导航系统和我国“高分”系列对地观测系统、“北斗”卫星导航系统等国内外先进的航天系统中得到了充分的实践与验证.在此过程中,作为调度技术的两大要素,航天器任务调度模型与调度算法的重要性也日益凸显.

调度模型是航天器任务调度的重要基础,是决定问题描述方式、指导算法设计、影响问题复杂度的关键因素.现阶段,线性规划模型、图论模型、约束满足模型等各类调度模型已被广泛运用于航天器任务调度问题研究中.在这些研究中,一方面,许多调度模型表现出鲜明的问题特色与针对性,引入了与调度问题紧密相关的决策手段;另一方面,许多模型也表现出了较大的相似性,折射出航天器任务调度问题的一些共性特征.因此,面对模型种类和应用场景繁多的航天器任务调度技术发展现状,建立一个怎样的调度模型,是决定调度问题是否可解、问题特征是否可描述、应用场景是否可拓展的重要环节.

调度算法是航天器任务调度的优化手段,是实现模型解算、输出调度方案、决定问题求解质量的关键因素.在航天器规模增长与能力发展的趋势下,启发式算法、精确求解算法和元启发式算法等一系列形式各异的调度算法被应用于航天器任务调度问题的求解中.这些调度算法表现出良好的优化效果,但往往也暴露出与调度模型或应用场景紧耦合的编码方式或设计思想,导致许多优秀的航天器任务调度算法在提出之后并没有得到广泛的应用或进一步的发展.由此,在琳琅满目的调度算法中挑选出合适的算法、设计合理的编码结构、吸纳优秀算法中的先进思想,也是航天器任务调度技术研究发展的必然要求.

为梳理航天器任务调度相关模型与算法、分析其特点与发展趋势,一些综述工作相继开展[1-4].不过,这些文献大多聚焦于某一类航天器(如遥感卫星)或某一种应用场景(如自主协同)的航天器任务调度模型或算法,很少站在航天领域的全局视角,探讨不同类型航天器任务调度模型的共性特征与区别,分析不同调度算法的适用性与编码特点.未来,航天器任务调度模型必须满足复杂化、组网化的问题特点,调度算法也需满足大规模、快速响应的优化需求,这就要求相关从业人员对各类航天器任务调度模型与算法深刻理解与熟练运用,摆脱“问题-模型-算法”紧耦合的传统思维.鉴于此,本文试图系统地梳理航天器任务调度研究中的模型与算法,揭示调度模型的共性特征,归纳调度算法的使用特点,为航天器任务调度技术研究未来发展提供参考.同时,在二者基础上发展起来的通用求解技术是改善航天调度系统兼容性、提升综合管控水平的关键技术,故本文也试图梳理适用于航天器任务调度的通用求解工具,探索我国航天器任务调度通用求解技术发展的新道路.

本文分别对航天器任务调度模型、算法和通用求解技术等三个方面进行了梳理与总结.第1 节根据航天器类型的不同,将现阶段具有调度需求的主要航天器任务分为遥感卫星任务、中继通信卫星任务、导航卫星任务和航天器测控任务,分别阐述了各类航天器任务调度的常用模型及特征.第2 节根据优化原理的不同,将航天器任务调度算法分为启发式算法、精确求解算法和元启发式算法,重点讨论了各类算法的编码特点和优缺点.第3 节分别介绍了CPLEX、STK/Scheduler、Europa2 和“高景一号”任务调度分系统等具有通用特色的航天器任务调度工具,并分析了其适用性与应用前景.最后,第4 节综合研究现状,对航天器任务调度领域未来的研究趋势进行了展望.

1 航天器任务调度模型

在任务调度问题的求解过程中,问题建模往往是首要步骤.在航天器任务调度相关研究中,各类航天器任务往往由不同的职能部门负责调度,并采用不同的问题建模方式,影响着任务与资源处理、决策变量设计和模型编码等诸多方面.根据职能部门的不同,可以将航天器任务分为运控任务与测控任务两大类:

定义1 (航天器运控任务).为实现遥感卫星、中继通信卫星和导航卫星等航天器的使命任务和任务数据的回传,在航天器特定工作模式和载荷的支撑下,由所属运控部门针对任务目标或数据接收目标制定的一类专门任务.

定义2 (航天器测控任务).为保障航天器正常运行,满足航天器遥测、跟踪和指令上注等日常需要,在航天器载荷和地面管控资源的共同支撑下,由测控部门针对航天器统一制定的一类任务.

由此,在上述定义的基础上,本节梳理了遥感卫星、中继通信卫星、导航卫星和航天器测控等常见的航天器任务调度模型,分析了不同航天器任务调度问题的建模特色、决策变量形式和模型优缺点,揭示不同航天器任务调度模型之间的共性特征与区别,阐明建模过程中提升模型兼容性、适用性和求解效率等方面的必要性,为航天器任务调度的模型研究提供参考.

1.1 遥感卫星任务调度模型

遥感卫星任务是指针对地表、海洋、大气和太空等环境中的目标,通过星上遥感载荷进行信息数据收集并传输给地面设备的一类航天器运控任务.遥感卫星是目前在轨数量最多的航天器,在农业、经济、军事等领域发挥着不可替代作用.因此,遥感卫星任务也是现阶段种类最为繁多、需求量最大、应用最为广泛的一类航天器运控任务.

遥感卫星任务调度是一类具有NP-Hard (Nondeterministic polynomial-time hard)特性的组合优化问题[5],该问题往往具有序列优化与资源优化的双重特点,既要决策任务执行的先后顺序,又要为任务合理地分配卫星及其载荷资源.由此,根据调度模型中决策对象的不同,本节将遥感卫星任务调度模型分为面向资源的任务排序模型(简称任务排序模型)和面向任务的资源分配模型(简称资源分配模型)两大类,并基于此对遥感卫星任务调度模型展开进一步的阐述.

1.1.1 任务排序模型

20 世纪末,面对遥感卫星任务调度这一全新的问题,人们尝试从经典运筹学模型中寻找解决方案.在这些模型中,决策变量主要表示资源执行任务的先后顺序,反映任务连续执行过程中的时序逻辑和能力约束,对早期遥感卫星任务调度问题的求解起到重要帮助.

1)车辆路径规划模型

车辆路径规划(Vehicle routing problem,VRP)模型是最早用于遥感卫星任务调度问题求解的模型之一,其中卫星被视为车辆,任务目标被视为车辆访问的城市,如图1(a)所示.Cordeau 等[6]将遥感卫星对目标的可见性转化为任务的时间窗口约束,并采用了一种VRP 求解算法[7]解决了单轨遥感卫星任务调度问题.随后,Bianchessi 等[8]将该算法应用于多星多轨的任务调度场景中.李菊芳等[9]、郭玉华等[10]和蔡德荣[11]指出卫星成像任务与数传任务可视为VRP 模型中的装卸货动作,求解了固存容量约束下的任务调度问题.虽然上述研究在卫星任务、工作模式、固存约束等方面进行了诸多简化,但VRP 模型中任务排序的建模思想为卫星任务调度研究打开了新思路.

2)图论模型

图1(b)所示的图论模型通过点和线的方式直观地描述卫星任务之间的时序与冲突关系,在遥感卫星任务调度中也得到诸多应用.例如,Gabrel 等[12]、Bianchessi 等[13]和陈浩等[14]将成像任务调度问题抽象为有向无圈图模型,陈祥国等[15]通过构造任务调度位置图和任务调度关系图分别描述了数传任务的序列与执行资源.针对多星联合调度问题,Xu 等[16]建立了基于最小生成树的图论模型,张帆等[17]和王钧[18]构建了分层优化的图论模型.不过,图论模型的缺陷也十分明显,由于该模型的约束表达能力有限,往往需要较大程度的问题简化,诸如区域目标成像、成像数传一体化调度、固存擦除等复合任务约束很难在传统图论模型中进行表示.

3)车间调度模型

作业车间调度(Job-shop scheduling problem,JSP)和流水车间调度(Flow-shop scheduling problem,FSP)等模型中关于工件加工顺序的约束特点满足卫星区域目标成像、立体成像等实际需求,故二者也常用于描述遥感卫星任务调度问题.早在1994 年,Hall 等[19]就给出了遥感卫星任务调度的JSP 模型.Cordeau 等[6]、李菊芳等[9]、顾中舜等[20]和贺仁杰等[21]指出,遥感卫星执行任务的过程可以看作为不同类型的机器(卫星、地面站)分配工序(成像任务、数传任务)的过程,如图1(c)所示.此外,Xiao 等[22]设计了一种两阶段式的任务调度框架,通过FSP 模型对卫星成像与数传任务进行了一体化的调度.

上述任务排序模型便于检查相邻任务之间的转换时间约束,贴近卫星管理的实际情况,加之早期遥感卫星几乎均采用“顺序回放”的工作模式,即数传顺序与成像顺序保持一致,故诸多其他遥感卫星调度文献中也保留着该建模思想.例如,Lemaître等[23]研究法国敏捷星座Pleiades 时通过决策变量表示卫星任务的先后顺序,并指出卫星电量与固存约束也可通过调整卫星任务顺序得以满足;Xu 等[24]通过决策变量表示了任务在执行序列中的位置;Lin 等[25]、程思微等[26]、任仙海等[27]、Sun 等[28]和Cui等[29]均通过决策变量表示了遥感卫星任务目标之间的路径或顺序等.

不过,任务排序模型存在一个明显的解码过程,通常仿照传统VRP、图论和JSP 模型尽可能早地执行任务,如图1(c)所示.但实际上,该解码过程在现阶段卫星复杂的约束逻辑下(如时间依赖性约束、非线性收益等)可能会丢失优质解,即“最优序列”不一定等于“最优结果”.问题约束越复杂,任务排序模型就越可能丢失优质解,同时解码过程的时间成本也越高.另一方面,随着星载固存技术的发展,诸多近年来发射的遥感卫星(如“高景一号”)已无需满足“顺序回放”的约束,即成像序列与数传序列可以不一致.若在数传窗口稀缺或某些任务有特殊需求的情况下,分别优化卫星成像序列与数传序列很可能更利于任务收益的最大化.对此,学者们提出了面向任务的资源分配模型,既保留了任务排序建模的思想,同时直接决策了任务执行的具体时间,成为各类遥感卫星任务调度研究中的重要模型.

图1 遥感卫星任务排序模型示例Fig.1 Illustrations of mission-sequencing models for remote sensing satellites

1.1.2 资源分配模型

与任务排序模型相比,资源分配模型不再决策任务顺序,而是面向任务需求,决策任务被执行的资源,如图2(a)所示.由于卫星与任务目标的可见性是任务执行的前提,二者的可见时间窗口(Visible time window,VTW)一直以来都被视为卫星调度的关键资源,故资源分配模型又可称为VTW分配模型.例如,Bensana 等[30]、Gabrel[31]、靳肖闪等[32]、Wang 等[33]、Liu 等[34]、Jiang 等[35]和Wu 等[36]以0-1决策变量表示了遥感卫星执行任务所选的VTW,求解了法国SPOT、韩国SATellite-2、我国“环境”系列和中巴“资源”系列等遥感卫星成像任务调度问题.在上述文献中,由于0-1 变量所表示的VTW同时包含了卫星载荷信息和任务执行时间,反映了卫星执行任务的顺序,无需VRP、JSP 模型中的解码过程,使得模型表示更加简洁.

图2 遥感卫星VTW 分配模型示例Fig.2 Illustrations of VTW-allocation models for remote sensing satellites

然而,敏捷遥感卫星技术的发展也暴露出了传统VTW 分配模型的局限性.近年来发射的遥感卫星通常具备俯仰成像能力,即能够先于或晚于目标上空进行远距离的倾斜成像,这一技术为遥感卫星在目标上空过境时带来了更长的VTW 和更多的成像机会[37],如图2(b)所示.因此,在敏捷遥感卫星任务调度模型中,不仅需要决策任务执行的VTW,还需要决定任务在该VTW 内具体的开始时刻.针对这一问题,学者们通过以下三种方法对模型进行了改进:

1)基于规则的VTW 分配模型

与上一节任务排序模型中的解码思想相似,Lemaître等[23]、He 等[38-39]、Mok 等[40]、Chu 等[41]和Song 等[42]基于最早开始原则,将卫星任务安排在VTW 内满足约束的最早位置;张超等[43]、Liu 等[44]以成像质量优先原则安排任务,并在模型中处理了时间依赖的姿态转换与梯段成像质量约束;Xu 等[24]根据任务安排过程中可能出现的不同情况设计了专门的卫星窗口更新策略;Kim 等[45]在SAR 星座成像调度问题中仅考虑了侧视成像模式,即在VTW的中点安排成像任务;Wu 等[46]以合并任务优先、最早开始等原则安排成像任务,并指出任务合并的相关约束导致了其模型非线性的特征.不过,虽然这些解码过程能够帮助VTW 分配模型适用于敏捷遥感卫星调度问题,但基于规则的解码方式一定程度也限制了算法对更大解空间的探索,在复杂约束情况下的时间成本可能也较高.

2)多重决策的VTW 分配模型

Lemaître 等[23]、She 等[47]、Chen 等[48]和Frank等[49]在用0-1 变量表示任务VTW 的同时,还通过一个整数变量表示了任务在VTW 内的开始时刻.Sarkheyli 等[50]通过双重决策变量表示了敏捷遥感卫星任务的VTW 和开始时刻,并考虑了星上固存整块擦除的业务约束,该约束在其他研究中很少涉及;Niu 等[51]、Chen 等[52]也采用了相同的决策变量,并计算了非线性的姿态转换时间约束.在该模型中,0-1 变量决策了执行任务的卫星以及VTW,整数变量决策了该任务的开始时间,避免了上一种方法中基于规则的解码过程,具有更好的模型完备性.

3)离散化VTW 分配模型

Wang 等[33]、Valicka 等[53]、Nag 等[54]、Zhu 等[55]、He 等[56]、Li 等[57]和杜永浩等[58]将遥感卫星成像或数传任务的VTW 进行离散化处理,通过0-1 变量直接决策了任务的离散VTW (即开始与结束时间),如图3 所示.该方法与多重决策的VTW 分配模型在本质上是相同的,但减少了决策变量的数量,使得模型更加简洁.与基于规则的VTW 分配模型相比,后两种模型在解的表示过程中摆脱了启发式规则的影响,能够保障复杂约束条件下解的多样性,更加贴近敏捷遥感卫星管控的实际情况.不过,这两种模型很大程度上扩大了问题的解空间,可能产生较多的不可行解,求解难度随之增加,故需要高性能优化算法的支持.同时,VTW 离散化的程度是可控的(现阶段卫星任务的最小精度通常为秒级),故合理的VTW 离散粒度也有助于提升该模型的有效性.

图3 敏捷遥感卫星任务离散VTW 分配模型示例Fig.3 An illustration of the discrete VTW-allocation model for agile remote sensing satellites

此外,还有学者将遥感卫星任务调度问题抽象为背包问题[6,59-61],但通常忽略了卫星执行任务的先后顺序,对问题简化程度较高,且近年来没有较大发展.许多学者基于Multi-Agent 模型[62-66]与机器学习模型[67-70]等研究了面向自主卫星的分布式协同任务调度问题,但此类问题通常突出星上自主性和快响性特点,不属于现阶段用户需求驱动与地面统一管控体制下的卫星日常任务调度范畴,故本节不讨论这些模型.

1.2 中继通信卫星任务调度模型

随着遥感卫星数量和对地观测数据量的不断提升,地面数传站难以满足现阶段遥感星群大规模、高频率的数据传输需求.因此,为在轨卫星与地面站提供数据中转服务的中继通信卫星起到了十分重要的作用.由于在轨道上承担的使命任务与地面数传站相近,中继通信卫星也被称为“天基数传站”.

中继通信卫星的任务调度问题与遥感卫星任务调度问题中的数传调度部分在诸多方面具有很大的相似度:1)二者均是在VTW 的基础上对目标执行数传任务,如图4 所示;2)二者在工作模式、电量、固存等方面具有相似的约束;3)中继通信链路的单址链路和多址链路支持不同的链路数与频段,这与遥感卫星不同的成像载荷具有相似的特点.因此,中继通信卫星任务调度模型也可参考遥感卫星任务调度模型进行分类.

图4 中继通信卫星任务调度问题与遥感卫星任务调度问题的类比Fig.4 A comparison between the mission scheduling of relay satellites and remote sensing satellites

1)任务排序模型方面

早在1986 年,Reddy 等[71-72]就用点和弧分别描述中继通信卫星任务之间的优先关系;Rojanasoonthon 等[73-74]、庄树峰等[75-76]、贺川等[77]和刘润滋等[78]指出中继卫星任务调度问题可视为一类VRP 问题或并行机器调度问题,并通过决策变量反映了卫星执行任务的先后顺序;郭超等[79]结合任务紧急程度、执行难度和VTW 属性分别定义了任务的综合优先级,并基于优先级顺序依次为任务分配VTW和开始时间.可见,此类模型延续了遥感卫星任务排序模型的建模特点,在决策变量表示和解码原则等方面具有一致性.

2)VTW 分配模型方面

在中继通信卫星执行任务的过程中,往往也会出现VTW 长度超过任务时长的情况,即相关研究中提到的“滑动窗口”.在这些研究中,通常采用启发式规则确定任务在VTW 内的开始时间.例如,顾中舜[80]、赵静等[81-82]、Zhao 等[83]通过0-1 变量表示了中继通信任务执行的VTW,并基于优先级顺序和最早开始原则依次计算任务的开始时间;方炎申等[84-86]在启发式规则的基础上引入了专家系统规则;贺川等[87]以任务最小损失机会确定开始时间;何敏藩等[88]设计了最早、最晚和随机开始策略等.

在其他一些文献中,中继通信卫星的任务调度问题并不单独考虑,例如,在遥感卫星成像与数传一体化任务调度的研究中,Li 等[57]将中继卫星视为一个地面数传站,该处理方式也是现阶段遥感卫星调度系统中的常用方法.此外,中继卫星有时也承担部分航天器的测控任务,故有相当一部分的中继通信卫星任务被纳入航天器测控任务范畴中[89].可见,中继通信卫星常被视为一种保障其他航天器任务调度需求的通用资源.因此,考虑到中继通信卫星的使命任务与管控特点,以及其在调度模型上与其他卫星调度问题的相似性,相关研究应侧重与其他类型卫星任务调度问题的集成性与协同性.

1.3 导航卫星任务调度模型

目前,世界上主要的导航系统包括美国全球定位系统(Global positioning system,GPS)、欧洲“伽利略 (Galileo)”导航系统、俄罗斯全球定位系统(Global navigation satellite system,GLONASS)和我国“北斗”导航系统.导航卫星的运控任务主要是建立卫星与地面或与其他卫星之间通信链路,以保障导航系统的定位精度和授时精度,以及导航电文、星历信息等数据的实时互传.因此,导航卫星任务调度问题可以看作为星地建链任务与星间建链任务的调度问题.

1)GPS 与GLONASS 导航系统

GPS 是全球最早建成的导航定位系统,并在2005 年就完成了全球范围的地面站部署,可在任何时刻实现星地建链,通常无需考虑VTW 约束[90].GLONASS 也在俄罗斯本土与周边国家大量部署地面站[91],卫星的可见性也较高.由此,GPS 与GLONASS 系统中的星地通信链路充裕,对任务与资源调度的需求程度较低,相关的公开文献较少.

2)Galileo 导航系统

早在1994 年,Gershman 等[92]和Marr[93]就讨论了Galileo 导航系统的任务调度问题.Toribio 等[94]介绍了Galileo 导航系统任务调度过程中的主要设备信息和组织架构,给出了短期规划、长期规划和应急规划的概念.Hall 等[95]介绍了Galileo 导航系统的调度系统(Spacecraft constellation planning facility,SCPF),给出了任务调度的主要流程,指出该系统每周约调度1 500 余项任务,周计划调度时间为10 分钟等.不过,上述研究均没有给出导航卫星任务调度的具体模型或算法.Marinelli 等[96]基于离散VTW 的0-1 变量表示了导航任务的开始与结束时间,对30 颗Galileo 导航卫星的星地建链周计划进行了调度.

3)“北斗”导航系统

针对“北斗”导航系统星地建链任务调度问题,龙运军等[97]基于0-1 变量表示了执行任务的地面站及VTW,并通过另外两个整数变量分别表示了任务的开始与结束时间,处理了测站建链数量、天线转换时间等实际约束,对建链时长、任务完成度等目标进行了优化.Tang 等[98]通过离散VTW 表示了导航任务的开始时间,对任务完成度和负载均衡度等目标进行了优化.考虑到任务等待时间和设备使用时间的双重时间约束,闫俊刚等[99]将导航卫星任务调度问题抽象为带有双重VTW 约束的JSP 问题.张忠山等[100]在星地建链任务的基础上还考虑星间建链任务,给出了基于任务排序模型的两阶段式任务调度方案.

尽管关于导航卫星任务调度的公开文献较少,但该问题中的星地建链任务和星间建链任务,分别与陆基航天器测控任务和天基航天器测控任务有较大的相似度.部分研究还将导航卫星任务调度纳入航天器测控任务调度的范畴[96-98].因此,下面重点介绍一些航天器测控任务调度的模型.

1.4 航天器测控任务调度模型

航天器测控任务是航天器遥测、跟踪、指令上注等一系列任务的统称,是保障航天器正常运行和长效管控的重要前提.航天器测控任务以地基测控任务为主,也包含部分天基(基于中继通信卫星的)测控任务.由图5 可见,与航天器运控任务调度相似,资源与目标的VTW 也是航天器测控任务调度的关键资源,其中低轨目标测控任务的VTW 长度通常等于任务时长,而高轨目标测控任务的VTW长度通常大于任务时长.因此,航天器测控任务调度问题的研究很大程度上保留了与运控任务调度相似的问题描述方式与建模习惯,主要采用优先级排序模型、图论模型和VTW分配模型等进行相关研究.

图5 航天器测控任务调度示例Fig.5 Illustration of spacecraft tracking mission scheduling

1)优先级排序模型

优先级排序模型属于一种面向资源的任务排序模型,其中任务的优先级指任务分配资源的优先级.该模型与VRP 等任务排序模型相似,但不会通过决策变量指明任务资源,而是直接根据任务排序结果依次分配资源.例如,Parish 等[101]、Barbulescu等[102-104]、郑晋军等[105]和张鹏等[106]通过0-1 变量表示了一个待调度的任务序列,并基于最早开始原则依次为任务分配VTW 与开始时间,将航天器测控任务调度问题转换为任务集的最优排序问题.Barbulescu 等[107]还指出航天器测控任务调度问题可由一类带准备时间的单机调度问题归约得到,证明了该问题的NP-Complete 性.Li 等[108]将每一个测控VTW 都视为待执行的任务,并通过0-1 变量表示了待调度的任务序列.该模型编码形式简单,受到了诸多青睐,但也因其只决策任务资源分配的顺序,且完全依靠启发式规则为任务逐一分配资源与时间,该模型在复杂的航天器测控任务调度问题中可能表现不佳.

2)面向低轨航天器的图论模型

作为另一种任务排序模型,图论模型在航天器测控任务调度研究中也应用广泛.早在1985 年,Arbabi 等[109]就给出了航天器测控任务的图论模型.Zufferey 等[110]和Blöchliger 等[111]将航天器测控任务视为图,将测控资源描述为不同颜色,将任务调度问题转化为图着色问题,而其中任务开始时间也依赖于最早开始原则;张雁等[112]、徐小辉[113]、Zhang等[114-117]和陈祥国等[118-119]以节点表示航天器VTW,通过边表示了任务在不同VTW 之间的冲突关系,处理了任务执行唯一性和无重叠等约束,将航天器测控任务调度问题转化为最大独立集问题;王海波等[120]、Vázquez 等[121]在航天器与测站可见关系图的基础上,以节点表示测控任务的开始时间,以边表示同一个测站连续执行测控任务的转换过程;Vázquez 等[122-123]还给出了分布式、鲁棒性和实时调度的模型.此外,Petri 网模型也被用于航天器测控任务调度研究中[124-127].不过,上述研究中通常仅考虑低轨航天器,由于低轨航天器测控任务时长等于其VTW 长度,故任务间的资源冲突、天线仰角和转换时间约束等相对确定、易于描述.但在高轨航天器测控任务中,VTW 长度通常超过任务所需的测控时间,故针对包含高轨航天器的测控任务调度问题,还需更加合适的模型加以描述.

3)考虑高轨航天器的VTW 分配模型

针对高、低轨航天器联合测控任务调度问题,Gooley 等[128-129]建立了两阶段式的VTW 分配模型,基于0-1 变量表示了测控任务的VTW,并优先调度低轨航天器的测控任务,再通过一个整数变量表示高轨测控任务在VTW 内的开始时间;贺仁杰等[130]、刘洋等[131]和Luo 等[132]也采用同样的决策变量描述了高、低轨航天器联合测控调度问题,建立了一体化的测控任务调度模型;Xhafa 等[133-136]、Valicka 等[137]通过整数变量直接表示了航天器测控任务的开始时间;Marinelli 等[96]基于离散VTW和0-1 变量建立了Galileo 导航星座测控任务调度模型.针对大规模测控任务调度场景,Liu 等[138]基于0-1 变量表示了测控任务的VTW,并基于冲突消解规则决定任务在VTW 内的开始时间.上述VTW 分配模型不仅决策了测控任务的VTW 与资源,同时也确定了任务在长VTW 内的具体开始时间,适合于包含高轨航天器的测控任务调度场景.

此外,还有0-1 背包模型[139]、基于本体与规则库的模型[140-142]、博弈论模型[143-144]、Multi-Agent 模型[145-146]和机器学习模型[147-148]等也被应用于航天器测控任务调度的研究中.

在上述研究中,航天器测控任务调度算例通常分为两种:1)基于STK 的仿真算例,任务数通常小于100,测站数小于10;2)美国空军(Air Force Satellite Control Network,AFSCN)发布的7 个高、低轨航天器联合测控任务调度标准测试集(Benchmark)[149](最近更新于2003 年),其中平均每天测控任务规模为308,测站数为19.考虑到任务和资源规模上的差异,这两类算例的求解难度也截然不同.而实际上,我国航天测控部门现阶段面临的任务规模早已超过AFSCN Benchmark 的规模.由此,当前诸多基于小规模算例的相关研究均存在一定的局限性.

1.5 小结

1.5.1 模型共性与区别

本节从任务排序模型和VTW 分配模型两个角度梳理了遥感卫星、中继通信卫星、导航卫星和航天器测控任务调度研究的主要模型,并对各类模型的特点、决策变量形式和优缺点进行了分析.表1将上述内容进行了总结,其中,结合卫星型号项目研发经历,还梳理了我国航天器任务调度实际需求中极少被相关文献考虑的业务约束.这些约束很大程度上限制了航天器任务调度最新研究成果的转化和应用.因此,如何通过标准化、模块化和简洁化的方式将这些复杂的业务约束纳入航天器任务调度模型中,应成为未来研究的重要内容之一.

从表1 中不难发现,遥感卫星、中继通信卫星、导航卫星和航天器测控任务调度研究中的常用模型具有非常大的相似性,其本质上是因为上述航天器任务调度问题的相似性.尽管航天器会搭载不同的载荷、被赋予不同的任务,但任务与资源在时、空、频域的可见性始终是问题建模的出发点和落脚点.以遥感卫星为例,调度模型中主要参数的实例化关系可由图6 表示,其中资源类包含了载荷、平台等实际资源和VTW 等抽象资源,任务类包含了属性和决策变量等.基于任务与资源的可见性,任务类中的开始时间可与VTW 直接关联,形成贯通模型的信息流,还原航天器任务调度问题的本来特点.由此,围绕“任务-资源”可见性这一共性特征,上述航天器任务调度问题具有统一化描述与建模的可行性[58].

图6 航天器任务调度模型主要参数关系的一种类图表示(以遥感卫星为例)Fig.6 A class diagram of the relationships among the parameters in spacecraft mission scheduling(exampled by remote sensing satellites)

表1 航天器任务调度模型研究现状总结Table 1 A summary of the studied models for spacecraft mission scheduling

不过,由于任务使命与资源的差异,上述航天器任务调度问题也存在着诸多不同,包括:1)固存约束差异,遥感卫星、中继通信卫星通常需要重点考虑固存约束,而导航卫星任务中的数据量较小、航天器测控任务中的数据传输通常使用备用固存或无需数传,故一般不考虑固存约束;2)阳照约束差异,可见光、高光谱和近红外等光学遥感卫星任务通常对任务的阳照性有要求,而导航卫星、测控任务通常对阳照性没有要求;3)资源能力约束差异,在遥感卫星任务中,出于对卫星的保护,通常设置一些复杂的业务约束,限制了卫星资源执行任务的能力;而导航卫星、航天器测控等任务主要依靠地面资源,故资源能力约束通常较少.4)任务时长差异,遥感卫星、中继通信卫星和航天器测控任务时长通常为定值,而导航卫星的任务时长常为变量.上述约束差异是反映航天器任务调度问题特征、区别航天器任务调度类型的主要因素.

1.5.2 不足与对策

综上,在分析各类航天器任务调度模型共性特征与区别的基础上,本节总结了现有研究存在的三个方面的不足并给出对策:

1)不同类型的航天器任务调度问题模型相似却又不兼容,缺乏统一的建模理论与建模语言.

通过本节的分析发现,各类航天器任务调度模型具有很大的相似性,其围绕任务与资源在时、空、频域可见性的建模原则是统一的.然而,这些模型又因应用场景的约束特点、需求种类和求解习惯等存在一定差异.因此,设计通用化、统一化的航天器任务调度建模方法与建模语言,是研究航天器通用建模与求解技术,满足未来不同类型、不同约束和不同体制下航天器综合管控需求的重要途径.

2)诸多航天器任务调度问题简化程度高,缺乏部署航天业务管控系统的实际应用价值.

表1 列举了诸多相关研究中极少考虑的实际约束.虽然一定程度的问题简化能够缩减问题规模、提升求解效率,但有些简化(如不考虑固存擦除)已影响问题的建模方式和调度方案的可用性,导致研究成果无法转化并应用于实际航天管控系统中.因此,梳理各类航天器任务调度问题中关键约束、通用约束以及特色约束,尽可能在调度模型中还原各类航天器业务管理的真实需求,是保障相关技术实用性价值的重要前提.

3)在模型层面降低航天器任务调度问题规模、提升问题求解效率的有效机制没有得到重视.

一直以来,调度算法是航天器任务调度问题中主要研究的对象,而调度模型受到的重视程度远远不足.实际上,调度模型很大程度上决定了调度算法的编码形式、邻域结构、搜索空间等影响优化效率的关键因素.因此,在未来航天器任务调度问题研究中,设计科学的调度模型和建模策略,是缩减问题规模、降低算法编码复杂度、提升算法求解效率、促进模型与算法解耦的必然要求.

2 航天器任务调度算法

在航天器任务调度模型的基础上,任务调度算法起到模型解算、收益优化和方案输出的作用,是实例化问题模型、决定模型求解质量的关键环节.启发式算法、精确求解算法和元启发式算法是三类常用的调度算法,在航天器任务调度领域得到了诸多应用.实践表明,这三类算法通常具有独特的性能优势,例如,启发式算法可以快速构造高质量的初始解,精确求解算法能够给出特定场景下的最优解,元启发式算法具有良好的复杂解空间寻优能力以及与前两种算法的兼容性等.同时,上述算法也往往与航天器任务调度的模型紧密相关,存在适用性、可拓展性不足等现实问题,亟待更多的发展和实践的检验.

因此,本节从启发式算法、精确求解算法和元启发式算法等三个方面总结航天器任务调度研究中的常用算法,探讨不同算法的编码形式、邻域结构、辅助策略和优缺点,阐明上述调度算法的适用模型,指出算法与模型解耦、算法深度融合等方面的必要性,为航天器任务调度的算法研究提供参考.

2.1 启发式算法

1)优先级排序算法

优先级排序算法是在优先级排序模型的基础上,基于优先级顺序和其他规则为任务序列分配资源与时间的算法.该算法具有通俗易懂、结构简单、运算速度快等优点,符合人的主观经验,是航天器任务调度研究与实际调度系统中的常用算法.

这些优先级排序算法中的排序规则通常是以任务优先级顺序[81-82,105-106]为主,也包含一些与VTW时间、长度、数量等属性有关的组合优先级顺序[79-80];常用的资源分配规则包括最早开始原则[23,39-40,46,110-111]、最晚开始原则[88]、最大成像质量原则[43-44,150]和最小可能冲突原则等[138].由于此类算法往往与排序模型紧耦合,相关内容已于上文介绍,且算法原理相对简单,故不再讨论.

2)冲突消解算法

冲突消解(Conflict-avoidance 或De-conflicting)算法是指通过分析任务之间、任务与资源之间的可能冲突,在任务调度的过程中降低冲突程度、提供冲突解决方案的一类方法.

在遥感卫星任务调度应用方面,刘晓娣等[151]在任务排序模型的基础上分别设计了基于成像概率和非互斥链的冲突消解算法;冉承新等[152]在调度的过程中引入了冲突判断与冲突度评估策略,作为遗传算法交叉与变异操作的先验知识;刘彬彬等[153]通过对卫星成像任务持续时间进行压缩,实现了部分约束的冲突消解;Chen 等[52]以最小化冲突的方式完成了初始任务序列的构造,并在迭代优化的过程中也引入了该冲突消解机制.

在航天器测控任务调度应用方面,金光等[154]基于最小冲突原则设计了任务资源的分配算法;杨萍等[155]计算了航天器测控任务的可能冲突集并设计了基于冲突的回调算法,实现了在资源分配过程中的“回溯”机制;Tsatsoulis 等[156]给出了基于案例、规则和迭代的多种冲突消解机制;Luo 等[132]计算了航天器测控任务的不可消解冲突集,进而设计了航天器测控任务预调度算法和重调度算法,取得了目前AFSCN Benchmark 中的最佳结果.

此外,图论模型中边的构造通常也蕴含着冲突识别与消解的思维.可见,冲突消解算法在诸多航天器任务调度研究中表现出快速、有效的优化特点,但很少直接作为任务调度问题的求解算法,大部分情况下用于生成调度初始解或辅助其他优化算法.此外,冲突消解算法大多围绕任务与VTW 的约束关系,不同算法之间的冲突消解原理、方法较为相似,且与问题约束紧耦合,在算法理论方面难有突破.

3)任务分配算法

任务分配算法是针对航天器任务调度规模较大、优化效率偏低的问题,依据某种经验或规则对航天器任务进行预分配的算法.与冲突消解算法一样,任务分配算法通常也作为调度过程中的辅助算法.任务分配算法有助于缓解航天器任务调度问题中的“组合爆炸”现象,对缩减任务调度解空间、提升优化效率有着重要作用.

以遥感卫星任务调度应用场景为例,Lemaître等[157]设计了遥感卫星任务公平分配原则,基于任务权重、卫星能力等将任务均匀地分配给不同的卫星;Xu 等[24]、Wang 等[33]计算了任务之间VTW 重叠度,并将任务分配给VTW 重叠度最低的卫星;Du等[158]通过VTW 重叠度、任务优先级等多种任务特征评估、预测了任务被卫星执行的可能性,并将任务分配给执行可能性最高的卫星;周军升[159]在任务分配过程中引入了合同网的“ 招标、投标、评标”机制,提升了任务分配的可靠性;邱涤珊等[160]、孙凯等[161]将任务调度问题分解为任务分配和任务合成两个子问题;He 等[56]设计了一种包含反馈机制的任务分配与调度框架,实现了任务调度进程中对未调度任务的重新分配,在大规模敏捷卫星任务调度场景中取得出色的优化效果.

上述启发式算法均有效降低了问题的决策维度和求解难度,但其应用效果很大程度上也取决于算法设计的合理程度,且大多与问题场景、任务与资源特征紧耦合,对问题的适应性不足.对此,充分利用航天器任务调度场景的特征和经验,设计通用化、自适应的启发式算法,是解决新常态下大规模、复杂化航天器任务调度问题的必要途径.

2.2 精确求解算法

精确求解算法能够在小规模的航天器任务调度问题中求得全局最优解,在动态或不确定的环境中也能保证解的全局最优性.虽然精确求解算法一般很难在有限的时间内求解大规模、复杂约束的航天器任务调度问题,但其中诸多思想对问题建模、解空间优化等方面也具有指导意义,故本节简要介绍相关研究中常用的两种精确求解算法.

1)分支定界算法

分支定界(Branch and bound,B&B)算法是由Land 等[162]于1960 年提出,并由Little 等[163]于1963 年正式命名的一种精确求解算法.B&B 算法通过分支、剪支和定界等手段缩小解空间,再通过各个分支搜寻最优解,是现阶段求解整数线性规划问题最常用的算法之一.由于航天器任务调度问题常被简化为线性规划问题,故B&B 算法在该领域也得到了诸多应用[22,41,48,53].同时,为改善在大规模任务调度问题中的求解效率,B&B 算法也常与列生成法[8,33,164]、割平面法[165-166]和Lagrangian 松弛法[25,96,167]等共同用于航天器任务调度的问题求解或边界求解中.此外,B&B 算法通常能够利用数学规划求解器CPLEX 完成设计、改进和问题求解工作,CPLEX 中的诸多剪支、松弛策略对航天领域的B&B 算法设计也起到重要的参考价值.

2)动态规划算法

动态规划算法(Dynamic programming,DP)是由Bellman 等[168]于1966 年提出的一种通过问题分解和递归手段搜寻最优解的一类精确求解算法.针对遥感卫星成像任务调度问题,Lemaître 等[23]采用基于图论模型的DP 算法对问题进行了求解;白保存等[169]将问题分解为单轨任务最优合成问题;Damiani 等[170]设计了一个包含当前任务、卫星电量和固存容量的评价向量,并将问题分解为评价向量的最优任务组合问题.针对遥感卫星数传任务调度问题,刘洋等[171]将问题分解为VTW 中数传任务的最优组合问题;秦丽等[172]将问题按时间划分成了若干个阶段.上述DP 算法所采用的问题分解思想对大规模航天器任务调度问题的求解也具有参考价值.

2.3 元启发式算法

2.3.1 演化算法

演化算法主要指通过模拟自然界生物种群演化机理和群体行为,对组合优化问题进行迭代寻优的一类元启发式算法.演化算法在航天器任务调度领域应用广泛,本节选取遗传算法、蚁群算法和粒子群算法等三类典型的演化算法,对其在航天器任务调度问题求解过程中的模型基础、编码方式和改进策略等进行介绍.

1)遗传算法

遗传算法(Genetic algorithm,GA)是由Holland[173]于1975 年提出的一种模拟进化论“自然选择”原理和遗传机理的演化算法.GA 以种群的形式和概率化的遗传机理进行迭代优化,具有隐并行性、多样化的解表示能力和出色的全局寻优能力,在航天器任务调度问题中得到广泛应用.

在任务排序模型的基础上,Parish[101]提出了求解AFSCN Benchmark 的经典算法Genitor,该算法利用基因段表示测控任务的资源分配顺序,如图7(a)所示,解码过程即依次为任务3、5、2、4、6 和1 分配资源;周毅荣[174]和Chen 等[175]设计了一种包含免疫遗传算法和学习策略的GA,在大规模多星多站测控任务调度中取得出色的优化效果.上述基因编码方式与任务排序模型契合度高,成为航天器任务调度算法中一种常见的编码方式.Sun 等[28]、Song等[42]、张鹏等[106]、李云峰等[176]和韩传奇等[177]也基于该编码形式,以及成像质量优先、局部搜索、深度优先搜索、冲突消解和精英保留等策略有效求解了航天器任务调度问题.

图7 遗传算法求解航天器任务调度问题编码示例Fig.7 Illustrations of the GA encoding for spacecraft mission scheduling

在VTW 分配模型的基础上,Kim 等[45]、Li 等[57]和Niu 等[178]通过0-1 基因值表示遥感卫星执行任务的VTW,如图7(b)所示,解码过程即为任务1分配VTW2,以此类推;Hosseinabadi 等[179]通过基因段分别表示了执行任务的卫星、VTW;孙凯等[161]用整数基因值表示遥感卫星执行任务的VTW,并在算法中引入知识模型与参数学习策略;Xhafa 等[133-134]采用直接编码的形式表示了航天器测控任务,并设计了包含种群竞争与淘汰策略的GA;Tang 等[98]和Du 等[180]通过基因值分别表示了导航卫星任务和测控任务的离散化VTW,并进一步设计了多目标的优化算法;张超等[43]还在传统GA 的迭代机制中引入Metropolis 准则,通过基因变量表示VTW和任务工作模式,实现了敏捷遥感卫星任务调度问题的优化.

可见,基于任务排序模型和VTW 分配模型,GA 都能较好地完成解的表示和问题求解.不过,受任务排序模型本身编码过程的限制,基于该模型的GA 可能会在优化过程中丢失优质解;而基于VTW分配模型的GA 可能出现编码长度过长、基因表示类型过多的情况,对算法迭代与搜索效率可能产生一定的影响.因此,合理的航天器任务调度模型与编码方式,以及有针对性地算法改进措施,对GA求解航天器任务调度问题起到重要作用.

2)蚁群算法

蚁群优化(Ant colony optimization,ACO)算法是由Colorni 等[181]于1991 年提出的一种模拟蚁群寻径行为的演化算法.ACO 通过蚁群寻径过程中信息素的积累、反馈、挥发与通讯等机制不断调整蚁群路径,表现出良好的渐近收敛性、隐并行性和全局寻优能力.

在遥感卫星任务调度方面,邱涤珊等[182]、耿远卓等[183]基于蚁群系统、最大最小蚂蚁、动态转移概率等策略求解了遥感卫星任务调度问题;严珍珍等[184]、陈宇宁等[185]在传统ACO 中引入了知识学习与信息素限制策略;针对ACO 优化周期长、易陷入局部最优的问题,朱新新等[186]等基于综合启发信息、冲突消解和扰动策略决策任务序列和VTW.此外,Gao 等[187]、Wu 等[188]在ACO 的框架中引入局部搜索策略,也取得了出色的优化效果.

在导航卫星和航天器测控任务调度方面,Zhang等[114-117]设计了蚁群间的合作交流机制;邢立宁等[189]和姚锋等[190]在ACO 中引入导向局部搜索策略和知识模型,提升了算法在大规模测控任务调度问题中的局部与全局寻优能力;陈祥国等[15]在蚂蚁转移概率中引入伪随机影响,并基于测控任务的冲突消解策略缩减了ACO 的搜索空间.针对导航卫星任务调度的问题中,黄双临等[191]在蚁群系统的基础上设计了动态的偏向探索概率,实现蚂蚁探索比例的自适应性调整;Li 等[192]考虑到ACO 优化初期信息素匮乏的现象,混合使用了GA 与ACO,也取得了良好的优化效果.

ACO 及其改进策略在航天器任务调度问题中得到诸多应用,但由于ACO 路径优化的基本思想,相关研究中的ACO 通常以蚂蚁路径表示卫星执行任务的顺序,其调度模型也以任务排序模型为主.因此,ACO 也会受解码策略的影响导致优质解的丢失,在具有复杂约束逻辑的任务调度场景中可能不利于全局寻优.

3)粒子群算法

粒子群优化(Particle swarm optimization,PSO)算法是由Kennedy 等[193]于1995 年提出的一种模拟鸟群觅食行为的演化算法.与GA 和ACO算法相比,PSO 结构简洁、易于实现,也具有收敛快、鲁棒性好的特点.最初的PSO 主要用于连续优化问题,现阶段航天器任务调度研究中采用的PSO算法大部分是以Kennedy 等[194]于1997 年提出的离散粒子群优化(Discrete particle swarm optimization,DPSO)算法为基础的.

考虑到传统PSO 算法不能求解离散优化问题,汤绍勋等[195]通过粒子位置矢量表示执行任务的VTW,通过粒子维度表示VTW 的数量;常飞等[196]通过粒子表示任务VTW 被选择的概率,基于概率顺序完成解码,并引入基于种群多样性的粒子自动增减机制;Chen 等[197]在粒子向量中同时表示了数传任务的VTW 和卫星工作模式,并引入量子行为和变异算子增强了算法全局寻优能力.此外,Chen等[198]、国晓博等[199]和刘建银等[200]在粒子向量中表示了任务资源,并引入遗传、禁忌和方向回溯等机制,完成了高低轨航天器联合测控任务、森林遥感卫星区域目标观测等任务调度问题的研究.

由于上述算法通常以面向离散优化的DPSO为基础,故其调度模型也以VTW 分配模型为主.不过,PSO 算法本身拥有连续优化与离散优化的双重特点,过于侧重离散化的编码形式可能不利于算法的寻优.相反,采用离散优化(决策VTW)与连续优化(决策任务开始时间)的编码方式,可能更适合现阶段具有长VTW 特点的航天器任务调度问题.

2.3.2 局部搜索算法

局部搜索算法是指从初始解出发,不断搜索邻域空间并有选择地向优质解移动的一类元启发式算法.现阶段航天器任务调度研究中常用的局部搜索算法包括禁忌搜索算法和模拟退火算法等.本节分别对两种算法在航天器任务调度求解过程中的模型基础、邻域结构和搜索策略等进行介绍.

1)禁忌搜索算法

禁忌搜索(Tabu search,TS)算法是由Glover[201-202]于1986 年提出的一种带有记忆策略的局部搜索算法.TS 算法通过禁忌表记录寻优过程中的局部最优解或产生局部最优解的操作,以避免对局部最优空间的重复搜索,达到跳出局部最优、开辟优质解空间的效果.TS 算法操作简单、实用性好,是最早用于航天器任务调度问题求解的算法之一.

在任务排序模型的基础上,Cordeau 等[6-7]利用一种求解VRP 问题的TS 算法实现了遥感卫星单轨任务的调度;贺仁杰等[203]基于JSP 模型设计了工件插入、移动、交换机器等邻域结构;左春荣等[204]设计了在任务序列中增减、替换任务的邻域结构;陈英武等[205]和李菊芳等[206]基于任务序列设计了多种邻域结构,并设计了基于变邻域策略的TS 算法;Blöchliger 等[111]基于图着色模型中的颜色选择设计邻域结构,并采用变禁忌长度的TS 算法求解航天器测控任务调度问题.

在VTW 分配模型的基础上,Xhafa 等[136]通过对VTW 和开始时间扰动的方式构造邻域;Sarkheyli等[50]设计了任务增减和VTW 内冲突消解等邻域结构,并选取任务与VTW 的匹配关系作为禁忌对象;Habet 等[207]设计了邻域评估机制,用于提升TS算法在遥感卫星任务调度过程中的邻域搜索效率.此外,禁忌搜索还被用于基于背包模型的航天器任务调度问题[60]的求解中.

TS 算法表现出良好的问题适用性和求解效果,但也由于机制较为简单,近几年来应用TS 算法直接求解航天器任务调度问题的研究较少.因此,TS算法应与最新的智能优化技术深度融合,才能更好地适应复杂化、多样化的航天器任务调度问题.

2)模拟退火算法

模拟退火(Simulated annealing,SA)算法由Metropolis 等[208]于1953 年提出,并由Kirkpatrick等[209]于1983 年应用于组合优化领域.SA 算法是一种源于固体退火原理的局部搜索算法,根据温度变化概率性地接受劣解,达到跳出局部最优、开辟优质解空间的效果.由于SA 算法通常受初始解质量和问题规模影响较小,具有良好的渐进收敛性,在航天器任务调度问题中得到诸多应用.

在任务排序模型的基础上,黄瀚等[210]通过插入或交换任务序列中互斥顶点等方式构造邻域,并设计了包含二次搜索和精英策略的SA 算法.在VTW分配模型的基础上,贺仁杰等[211]、Gao 等[212]设计了任务增减、合并或分解的邻域结构,并在SA 算法中加入了随机扰动、重调度等策略;徐欢等[213]、Du 等[214]通过交换决策变量的方式直接构造SA 算法的邻域;黄生俊等[215]借鉴蚁群算法中的反馈特性,结合先验、后验知识进行邻域设计,并在算法陷入局部最优时触发扰动;Wu 等[46]基于自适应概率设计了任务增减、迁移等邻域操作,并在SA 算法中引入自适应的温度控制和禁忌策略;Lin 等[216]通过交换任务VTW 和载荷频段的方式构造邻域,并混合使用了SA 与DP 算法,有效求解了遥感卫星多载荷任务调度问题.

此外,针对航天器任务调度问题规模巨大、易陷入局部最优的特点,近年来变邻域搜索[217]、自适应大邻域搜索[44,56]等局部搜索算法也得到诸多应用,取得了出色的优化效果.

2.3.3 其他算法

1)模因算法

模因算法(Memetic algorithm,MA)是由Moscato[218]于1989 年提出的一种融合演化算法与局部搜索算法的一类混合元启发式算法.其中,“Memetic”源于Dawkins 著作《The Selfish Gene》[219]中“Meme”一词,寓意文化层面的遗传基因,故MA 又称为文化基因算法.MA 既保留了演化算法基于种群进化的优化特点,又具有局部搜索算法出色的局部寻优能力,起到了对二者取长补短的效果.MA 在航天器任务调度领域也得到了诸多应用,根据演化算法与局部搜索算法的混合形式,可以分为以下三种:

a)基于演化算法框架的MA,即Moscato[218]最早提出的MA.例如,Du 等[180]、邢立宁等[189]、姚锋等[190]和刘建银等[200]分别在求解航天器任务调度的GA、ACO 和PSO 算法中引入了局部搜索机制.此类MA 可以视为一种基于个体改进和修复策略的演化算法,是最常用的一类MA.不过,针对个体的局部搜索机制也将增加种群迭代的时间,故设计合理的搜索频率、迭代次数与触发条件是此类MA 的关键.

b)基于局部搜索框架的MA.例如,贺仁杰等[203]和黄生俊等[215]分别在TS 和SA 中引入了个体交叉、信息素反馈等演化策略.此类MA 可以视为一种通过演化策略设计邻域结构、引导搜索方向的局部搜索算法,但由于缺乏种群的支持,此类MA 在解的多样性、隐并行性等方面不及演化算法.

c)基于分层框架的MA.例如,为发挥GA 早期寻优和SA 深度搜索的能力,Zhu 等[55]设计了基于GA 和SA 的两阶段式优化算法,在遥感星座任务调度中也取得了出色的效果.不过,此类MA 对编码形式的通用性、算法切换的合理性也有更高的要求.

可见,MA 实际上是一种演化算法与局部搜索算法组合的框架.针对复杂化、大规模的航天器任务调度需求,相互协同、取长补短、优势互补的算法组合框架对问题求解将起到十分重要的帮助.

2)基于机器学习的决策算法

基于机器学习的决策算法是指通过监督学习、强化学习等机器学习手段,训练航天器任务调度决策模型,进而对航天器任务进行调度的一类方法.在监督学习方面,Li 等[220]利用鲁棒决策树、支持向量机和人工神经网络构造了一种遥感卫星任务可调度性预测模型;刘嵩等[221]从遥感卫星历史数据中提取了任务优先级、持续时间和冲突度等特征,基于变隐含层的BP 神经网络模型构造了任务可调度性预测模型;考虑云雾遮挡等不确定性因素,邢立宁等[67]提取了气象特征,并利用任务可调度预测模型设计了遥感卫星自主任务调度算法;Du 等[158]通过进化神经网络算法训练任务可调度性预测模型,将任务分配给最有可能执行该任务的卫星,显著提高了大规模敏捷遥感卫星任务调度的效率.

在强化学习方面,针对遥感卫星协同任务调度问题,王冲等[68-69]分别通过Q 学习算法和进化神经网络算法训练了卫星在动作集中的选择策略;Wang等[70]通过A3C 算法训练了遥感卫星任务调度决策模型,当新任务达到时,该模型将决定任务执行与否,并为决定执行的任务分配一个最长的VTW,为星上任务的自主调度提供了解决方案.

基于机器学习决策算法可视为一种利用高级规则指导任务排序或任务分配的算法,具有启发式算法简单、快速和机器学习技术自适应、自学习的综合特征.目前各类航天器管控部门都积累了大量的任务调度历史数据,故相关技术具有很强的应用前景.另一方面,虽然上述算法实现了航天器任务的自主调度,但也呈现出“来一个决策一个”的局限性,难以保障大规模任务调度的全局优化性.同时,上述算法均对所研究的问题进行了大幅度简化,以便提取用于模型训练的任务与资源特征,但在现阶段航天器任务调度问题日趋复杂的情况下,基于简单特征的决策模型可能很难取得理想的效果.

2.4 小结

本节从启发式算法、精确求解算法和元启发式算法等三个角度梳理了航天器任务调度研究中的常用算法,并对各类算法的编码特点、邻域结构和优缺点进行了分析.表2 将上述内容进行了总结.这些算法成功求解了诸多航天器任务调度难题,贡献了重要的理论与实践经验,但与此同时,也存在以下两点不足:

表2 航天器任务调度研究中常用算法总结Table 2 A summary of commonly used algorithms for spacecraft mission scheduling

1)航天器任务调度算法与模型紧耦合,算法设计的灵活性不足.

各类航天器任务调度算法均有其适用的任务调度模型,这也是造成现阶段航天器任务调度模型与算法紧耦合、调度算法通用性不足的主要原因.因此,结合航天器任务调度模型研究现状,研究模型与算法解耦、算法灵活可配的航天器任务调度架构具有重要的实践意义.

2)不同算法之间深度协同、合理搭配的有效机制还未形成.

各类算法均有不同的优缺点和适用性,例如启发式算法常用于辅助决策,精确算法求解大规模问题能力有限,演化算法全局寻优能力强等.虽然模因算法给出了一种很好的算法协同思路,但其现阶段在求解能力、问题适用性等方面仍有提升空间.因此,对不同类型的算法进行合理搭配,形成深度协同、取长补短、优势互补的算法组合框架也是求解大规模、复杂化航天器任务调度问题的必要途径.

3 航天器任务调度通用求解技术

航天器任务调度通用求解技术是指可以针对不同类型的航天器任务建立通用化的任务调度模型,或采用不同任务调度算法进行模型解算的通用求解器、工具箱、算法包等.航天器任务调度通用求解技术可以解决不同场景下的航天器任务调度、异构多航天器协同任务调度等现实问题,方便地调用多样化、可拓展的调度算法,为从业人员提供便捷、丰富且有效的问题建模与求解手段.因此,航天器任务调度通用求解技术对提升航天器综合管控自动化、智能化和一体化水平起到重要作用,是衡量一个国家航天综合实力的重要标准,也是航天部门亟需发展的关键技术.

目前,具有通用建模与求解特色的航天器任务调度工具有CPLEX、STK/Scheduler、Europa2 和我国商业遥感卫星“高景一号”任务调度分系统等.本节对上述四种通用求解技术的建模特色、求解算法和主要功能进行梳理,总结上述通用求解技术的优缺点,结合航天综合管控的发展现状,指出我国自主研发航天器任务调度通用求解器的必要性和新的应用思路,为航天器任务调度通用求解工具的研究与设计提供参考.

3.1 数学规划求解器CPLEX

CPLEX 是美国IBM 公司开发的一款数学规划求解器,适用于线性规划、二次规划等问题[222].在建模语言方面,CPLEX 语言简洁易懂,并可以与C++、Java 和Python 等主流编程语言兼容;在求解质量方面,CPLEX 内置了单纯形、分支定界等一系列精确求解算法,可以给出问题的最优解,保持了一系列经典运筹学Benchmark 中的最优记录,因此也被应用于航天器任务调度问题的求解中.

针对遥感卫星成像与数传任务一体化调度问题,Xiao 等[22]建立了分段式的FSP 模型,并通过CPLEX 对问题进行了求解.不过,由于问题的NPHard 特性,在7 200 s 的优化时间内只能完成20 个任务的调度;考虑到敏捷卫星时间依赖的姿态转换约束无法由线性函数表示,Liu 等[44]通过CPLEX对简化后的问题进行了优化,但也仅能完成12 个任务;为保障不确定环境下任务调度的最优性,Valicka 等[53]采用CPLEX 对考虑随机云层遮挡的遥感卫星任务进行了调度,优化时间约为2 000～3 000 s;针对“资源三号”遥感卫星任务调度问题,徐忠良等[223]通过CPLEX 完成了11 个任务的优化调度;Bensana 等[59]成功利用CPLEX 对卫星单轨任务进行了调度,但无法完成多轨任务的有效调度.

另一方面,CPLEX 可与其他算法或策略混合使用,一定程度上能够提升航天器任务调度问题的求解效率.例如,针对Galileo 导航星座任务调度问题,Marinelli 等[96]在CPLEX 中引入了Lagrangian 松弛和其他启发式策略,能够在18 000 s 的优化时间内对360 个导航卫星任务进行调度.同时,Marinelli 还指出在无其他辅助策略的情况下,CPLEX 的求解能力仅为120 个任务.Xu 等[24]、王沛等[224]将局部搜索算法与CPLEX 相结合,在1 800 s的时间内对100 个遥感卫星任务进行了调度.

上述研究表明,虽然CPLEX 在求解小规模航天器任务调度问题、不确定性任务调度问题和问题边界等方面表现出色,但在求解大规模任务调度问题的时候效率低下,且无法准确描述非线性的约束条件和收益.因此,在现阶段任务规模不断增长的情况下,CPLEX 很难满足航天管控部门对任务调度质量与速率的双重需要,很难在实际的航天业务调度系统中投入使用.

3.2 通用卫星调度软件STK/Scheduler

STK/Scheduler 是美国Orbit Logic 公司开发的一款卫星任务调度商用软件[225],可在STK 6.0 以上版本中直接调用.STK/Scheduler 可以在STK模型和数据的基础上快速地建立任务调度模型,通过内置的算法给出任务调度方案,并具有友好的用户操作界面,如图8 所示.其中,STK 所计算的卫星轨道与VTW 具有较高的准确性,故STK 也常作为航天器任务调度研究中VTW 的计算工具.

图8 操作界面示例Fig.8 A view of the STK/Scheduler

STK/Scheduler 中包含以下5 种调度算法:1)One-Pass 算法,即基于任务优先级顺序和内置的期望函数分别确定任务资源与开始时间,是一种典型的任务排序算法;2)Sequential 算法,即在One-Pass 算法的基础上同时考虑任务VTW 时间、时长等其他因素;3)Multi-Pass 算法,即基于规则多次运行One-Pass 算法并调整调度方案,是一种任务排序与冲突消解相结合的算法;4)Neural network 算法,即基于规则为任务分配VTW 与开始时间并修复不可行解,是一种任务分配与冲突消解相结合的算法;5)Random 算法,与Neural Network 算法相似,但在分配VTW 与开始时间时采用随机策略.

李英先等[226]基于STK/Scheduler 实现了中继通信卫星的任务调度,但考虑约束较为简单,没有对频段匹配、切换时间等具有中继卫星特色的约束条件进行建模;李云峰等[227]指出STK/Scheduler 发送命令的时间较长,不利于大规模的任务调度;白敬培等[228]对5 种内置算法进行了测试,结果表明Multi-Pass 算法和Random 算法在短时间内的优化效果最佳;Li 等[229]在STK/Scheduler 的软件基础上引入了任务动态调整机制;Fisher 等[230]给出了STK/Scheduler 自定义算法的介绍,但也仅限于对排序规则、交换策略等的调整功能.以上,虽然STK/Scheduler 在航天器任务调度问题中取得了一定的效果,但在问题复杂化、多元化的发展趋势下,STK/Scheduler 也暴露出一些不足:

1)虽然对航天器任务、资源进行了用户友好化的封装,但也很大程度上限制了任务、资源的属性与约束格式,不利于包含复杂任务或约束的问题求解,二次开发的难度较大;

2)缺乏对任务、资源、收益或约束条件的动态调整功能,常用于静态的航天器任务调度问题;

3)主要功能最后更新于2006 年,没有包含进化算法、禁忌搜索等现阶段主流的智能优化算法,对规则的依赖性较大.随着近年来航天器任务调度问题规模与复杂性的不断提升,其内置算法的求解效果可能不佳.

另一方面,2013 年,Herz 等[231]在航天器测控任务调度的问题中使用了STK/Scheduler Online,通过互联网访问了STK/Scheduler 服务器,完成了场景建模、参数配置、优化调度等一系列功能.这种远程式的任务调度方式使得用户的访问便捷、高效,有助于服务功能的迭代更新和故障的快速修复,在高性能服务器的支持下也有助于调度效率的提升.因此,STK/Scheduler Online 也为航天器任务调度系统的设计与部署提供了一种新思路.

3.3 航天器任务规划软件Europa2

Europa2 (2nd generation of extensible universal remote operations architecture)是NASA开发的面向航天器任务规划的第二代可扩展式通用远程操作体系结构[232],已在NASA 哈勃空间望远镜[233]、DS-1 自主卫星[234]等项目中得到应用.与规划领域经典语言PDDL (Planning domain description language)不同,Europa2 所基于的NDDL(New domain description language)是一种基于状态变量、面向对象与声明性的语言,故Europa2中主要通过定义标记、事务、对象、类、时间线和规划解等完成对一类航天器任务场景的描述,并通过约束传播等约束规划技术给出一个可行的方案[235-238].

基于状态变量的特点,Europa2 主要面向航天器任务规划问题,如航天器执行任务的动作逻辑、状态转移等.该问题主要描述航天器任务的逻辑关系,给出满足约束的可行方案,对资源调度的需求较少.而本文所探讨的任务调度问题主要解决任务资源与时间的分配,例如执行任务的VTW、航天器及其电量、固存等载荷资源等.故针对航天器任务调度问题,Europa2 存在以下不足:

1)缺乏收益函数和调度优化机制,Europa2 通过约束规划等方法给出可行的航天器动作序列,但无法在收益函数的驱动下迭代地给出更优的调度方案;

2)基于约束传播的约束规划算法只能适用于小规模的任务场景,例如单星单轨20 个任务的规划时间已非常长,且最新版本Europa2.6 发布于2011 年[232],已很难适应现阶段大规模、复杂化的航天器管控新常态.

不过,Europa2 中的约束传播算法能够在新任务到达、任务或资源属性变更的情况下快速给出可行方案,这对面向快速响应需求的动态任务调度算法与框架设计具有启发意义.此外,NASA 于2015年公布了一款基于Europa2 的开源规划调度工具包OpenSPIFe (Open scheduling and planning interface for exploration)[239].OpenSPIFe 具备动作规划、动态调整、界面可视化等功能,但相关应用较少,有待进一步研究.

3.4 “高景一号”任务调度分系统

“高景一号”是我国首个商用敏捷遥感星座,目前由4 颗位于太阳同步轨道的0.5 米分辨率光学成像卫星构成,每颗卫星的轨道周期约为97 分钟.按照相关计划,还将陆续发射20 余颗敏捷遥感卫星,与现有的4 颗卫星组建新的“高景一号”星座网络.鉴于“高景一号”星座的商业化运营模式和不断增加的卫星数量,如何充分调度卫星任务、最大化经济收益是“高景一号”运控部门迫切关心的问题.

目前,“高景一号”任务调度分系统采用的调度模型之一为任务排序模型,并基于成像质量最高原则(即在VTW 中点处执行任务)对任务序列进行解码.由于在模型解码过程中会对任务序列进行约束检查,解码后均为可行方案.因此,该调度模型的通用性也较强,在此过程中复杂任务约束也均能得到处理.

在任务排序模型的基础上,“高景一号”任务调度分系统所采用的调度算法主要为任务分配算法和优先级排序算法.例如,基于任务收益、持续时间、窗口数量等一系列任务与资源属性,定义任务的综合优先级,并基于优先级降序构建单星任务序列、依次分配资源.由于机制简单,“高景一号”任务调度分系统能够较快地给出单星任务调度结果,但也暴露出任务调度效果不佳、卫星缺乏协同、资源利用不充分等问题.

另一方面,当通过人工调整的方式对任务排序结果进行进一步优化时,仍需重新进行解码与约束检查工作.由于人工调整的结果并不能得到实时反馈,故人工调整的方式存在一定的盲目性,即可能出现人工调整结果不及原方案的情况.由此,该模型与算法虽然能够处理复杂的卫星业务约束,但任务调度效率和快速响应能力仍有待提高.

3.5 小结

本节梳理了CPLEX、STK/Scheduler、Europa2和“高景一号”任务调度分系统的基本原理、适用性和优缺点,表3 对本节内容进行了总结.通过本节的综述与分析可知:

表3 用于航天任务调度的通用求解器总结Table 3 A summary of the general techniques for spacecraft mission scheduling

1)现阶段尚无能够满足航天器任务调度需求的通用求解器.

虽然上述航天器任务调度通用求解器均在一些应用场景中取得了良好的求解效果,但每一款求解器的局限性也非常明显:例如,CPLEX 难以处理大规模与非线性问题,STK/Scheduler 复杂约束处理与二次开发难度大,Europa2 缺乏对收益函数的优化,“高景一号”任务调度分系统优化能力有限等.即使STK/Scheduler 与Europa2 能够适用于简单的航天器任务调度问题,但其内置算法也相对落后,已多年未发布新版本.目前,航天器任务调度问题正向着大规模、复杂化和动态需求常态化的趋势快速发展,上述航天器任务调度通用求解器尚不能满足发展的要求.

2)我国需要研发具有自主知识产权的航天器任务调度通用求解技术.

综合考虑约束描述能力、求解效果、版权与服务支持等因素,CPLEX、STK/Scheduler、Europa2并未在我国航天系统中得到应用.或许STK/Scheduler和Europa2 等航天器任务调度通用求解器已有融合先进技术的新版本,但并未对外公布.因此,我国需要研发适合我国国情、具有自主知识产权的航天器任务调度通用求解技术,在核心技术上掌握主动权,为提升我国航天综合管控实力提供技术支撑.

3)基于云平台的远程航天器任务调度服务是一种新的应用思路.

STK/Scheduler Online 提供了一种在线式的航天器任务调度服务新模式.该模式使用户访问更加便捷、高效,有助于服务功能的迭代更新和故障的快速修复,在高性能服务器的支持下也能提升任务调度的效率.因此,结合现阶段云计算的技术优势,向航天部门提供远程的任务调度服务是一种新颖、高效的应用思路.

4 结束语

航天器任务调度是航天器管控的重要内容,是发挥航天系统社会经济效益、实现航天器使命价值的重要保障.随着航天事业的快速发展,作为调度技术的两大要素,航天器任务调度模型与调度算法已得到广泛研究,并在各大航天调度系统中得以检验.在此过程中,涌现出一批优秀的调度模型、算法和通用求解技术,为航天器任务调度研究贡献了重要的理论体系与实践经验.本文系统地梳理了近年来航天器任务调度研究中的模型、算法与通用求解技术,总结了相关技术中的共性特征与区别,为未来航天器任务调度的研究工作提供了参考.

本文的主要工作如下:1)根据航天器任务目标的不同,将现阶段具有调度需求的主要航天器任务分为遥感卫星任务、中继通信卫星任务、导航卫星任务和航天器测控任务,阐述了各类航天器任务调度的常用模型及特征;2)根据优化原理的不同,将航天器任务调度算法分为启发式算法、精确求解算法和元启发式算法,探讨了各类算法的编码特点和优缺点;3)介绍了CPLEX、STK/Scheduler、Europa2和“高景一号”任务调度分系统等具有通用特色的航天器任务调度工具,分析了其适用性与应用前景.

然而,通过本文的综述也发现,现阶段航天器任务调度研究暴露出“模型-问题-算法”紧耦合的弊端,模型与算法的兼容性与可拓展性不足,难以适应航天系统灵活组网、快速响应的新常态.由此,本文指出以下几点未来航天器任务调度研究的新方向:

1)研究航天器任务调度统一化建模语言.

航天器任务调度统一化建模语言是解决航天器任务调度模型兼容性问题的根本途径.通过本文综述发现,诸多航天器任务调度模型具有很大的相似性,其围绕任务与资源在时、空、频域可见性的建模原则是统一的.现阶段已有几款成熟的统一化建模语言,但这些语言缺乏航天领域和组合优化领域的应用特色.由此,研究统一化且具备领域特色的航天器任务调度建模语言,是发展航天器通用建模与求解技术,满足未来航天器灵活管控需要的内在要求.

2)研究航天系统管控体制下有效应对大规模任务调度问题的解空间优化技术.

随着航天器规模持续增加以及航天系统组网的常态化发展,解空间规模已成为限制航天器任务调度效率的关键因素.目前,任务分配、分层规划等方法可将大规模航天器任务调度问题分解为诸多子问题,虽然提升了调度效率,但也违背了航天系统综合管控、一体化调度的发展趋势,丢失了问题的全局优化特点.近年来,深度学习、强化学习等技术发展迅速,并在旅行商、车辆路径规划等经典组合优化问题中得到了成功应用.基于机器学习的技术优势,可以研究航天器任务调度解空间优化技术,在保留全局性优化特点的基础上,实现大规模任务调度解空间规模的精准缩减,以满足航天系统综合管控与快速响应的双重需求.

3)共同打造航天器任务调度算法库与测试集.

以往,调度模型兼容性不足是限制航天器任务调度算法通用化发展的主要原因,而上述航天器统一化建模语言可以解决这一问题.以后,航天器任务调度算法不再局限于某一特定的航天应用场景,而将适用于更多的具有普遍意义的航天器任务调度问题.鉴于此,打造一个开源的、持续更新的航天器任务调度算法库,有助于营造世界范围内相关学者及业务人员共研共享的发展环境.同时,为检验算法性能、促进良性竞争,打造兼具算法测试、教学、新案例发布等功能的航天器任务调度标准测试集也具有十分重要的意义.

4)研发具有自主知识产权的航天器任务调度通用求解技术.

在上述研究方向的基础上,研发适合我国国情、具有自主知识产权、满足国家航天战略发展需要的航天器任务调度通用求解技术势在必行.通用求解技术的研发是实现我国在轨航天器综合管控、灵活组网这一目标的出发点和落脚点.未来,在通用求解技术的支撑下,资源卫星、商业卫星、侦察卫星、导航卫星、中继卫星、空间站与地面站网等不同类型、隶属不同部门的航天任务资源将密切联动,更大限度地发挥我国航天系统的社会经济效益.