-
摘要: 如何利用有限的星上资源执行复杂繁重的空间任务长期以来备受关注，随着卫星载荷能力不断提升，响应时间要求不断缩短，卫星自主与协同任务调度规划研究的重要性逐渐增大.本文从单星任务调度规划为起点，对单星地面离线任务调度规划、单星星上在线任务调度规划、单星星地一体化自主任务调度规划研究现状进行梳理与分析，然后延展至多星领域，综述了多星地面离线协同任务调度规划、多星星上在线协同任务调度规划、多星星地一体协同任务调度规划研究现状.最后，对卫星自主与协同任务调度规划研究进行了总结与展望.Abstract: How to make use of limited resources on a satellite for complex and heavy space tasks has attracted much attention. With the continuous improvement on satellite load capacity and reduction of response time requirements, the importance of satellite autonomous and collaborative task scheduling research has gradually increased. This paper starts with the research status of single-satellite task schedule planning. From single-satellite ground off-line task schedule planning and online task schedule planning, this paper analyzes the research on single-satellite integrated autonomous task schedule planning, then extends up to the present situation of satellite task schedule planning research including multiple-satellite ground offline collaborative task schedule plan and satellite onboard collaborative task schedule plan. Finally, the research on satellite autonomous and collaborative task scheduling is prospected.
-
以往的管理控制卫星运作的方式主要是通过地面事先规划好任务计划来完成, 但当前卫星任务越来越复杂, 需要时刻面对突发应急情况和运行环境的变化, 对传统的地面离线管控模式提出了诸多挑战: 1)当前所部署的地面测控系统受到地域、密度等多方面约束, 各地面站与各卫星之间的可见通信时间受限; 2)测控时间窗口的约束导致了对突发性事件的响应时间产生了更多变数, 难以即时获取全面、精确的灾情信息; 3)同样的测控时间窗口的约束给数据回传带来滞后的问题, 影响卫星系统执行任务的效率; 4)星上资源的离线预测在动态环境下难以把握, 地面管控方式无法根据实时情况调整任务计划, 影响系统整体效能的发挥.由此可见, 只依靠地面管控中心进行卫星任务调度很难胜任常态化动态观测需求的工作, 完全地面离线的管控模式难以适应未来航天任务的需求.
随着卫星载荷能力的不断提升, 卫星响应时间要求不断缩短, 为了缓解卫星资源紧张有限的现状, 提高卫星对突发情况的快速响应能力, 目前最现实的办法是赋予卫星自主决策、自主通信协调、自主调度规划的能力, 使卫星根据动态环境进行自主任务规划.星上自主规划能力可以使卫星不再完全依靠外界的控制信息, 能够根据动态到达的观测需求、实时气候条件和卫星运行状态, 进行星上在线规划, 在轨生成动作指令.星间协同规划的能力可以让协作需求不经地面, 直接通过星间链路到达指定卫星.自主与协同规划技术能够将原先由地面系统所承担的规划、控制等功能转移到卫星上.不但能够缩小地面站规模, 节约运营成本, 降低星地间的信息交互, 更重要的是能够及时响应动态观测需求, 能够通过多星协作的方式实现大范围、全天候、全天时连续观测监视, 实现目标发现即确认.同时, 星上自主规划考虑的是卫星实时状态, 因此能够实现对星上资源的优化配置, 继而可对卫星长时间的稳定运行起到推进作用.由此, 卫星自主与协同任务调度规划的研究热度与日俱增.
目前国内卫星任务调度规划方面的研究和应用主要针对地面管控模式, 星上自主任务调度规划研究尚处于起步阶段, 其主要的任务调度研究以单星为基础, 进一步拓展到多星协同框架下.本文以卫星自主与协同调度规划研究为中心, 按照"单星地面离线-单星星上在线-星地一体化"的结构对单星自主任务调度规划研究现状进行梳理与分析, 按照"多星地面离线-多星星上在线-多星星地一体化"的结构对多星协同任务调度规划研究现状进行梳理与分析, 最后对卫星自主与协同调度规划研究进行总结.
1. 单星自主任务调度规划研究
1.1 单星地面离线任务调度规划
单星地面离线任务规划一般可以分为4个阶段[1], 其中任务预处理阶段主要分析用户需求并研究任务分解与聚类方法, 模型构建阶段主要按照形式化的需求确定目标函数, 在考虑约束条件下对任务规划目标进行建模, 设计算法阶段研究求解卫星规划问题的算法, 评估阶段研究算法的性能和方案的优劣.为了能够完成这些阶段复杂的过程, 对处理单元计算能力要求较高, 因此常规的任务调度规划一般选择地面离线的方式.在任务预处理阶段中, 为了提高稀缺卫星资源的利用率, 相关研究首先考虑到卫星任务的分解与聚类, Wu等[2]提出了两阶段调度的方法, 先用改进的最小团划分算法获得聚类任务, 再基于总体任务和获得的簇任务完成一种混合蚁群算法来实现局部最优或近似最优调度, 针对这种静态的聚类策略的缺点, 后续研究提出了动态的任务聚类策略[3], 也有研究从用户需求出发, 提出基于指标的多目标局部搜索方法来对多个用户需求进行规划[4], 从而提升资源的总体效益.模型构建阶段里相关研究从多个方面, 如:图论问题模型[5-7]、背包问题模型[8-9]、整数规划模型[10-11]和其他模型[12-13]等来对任务调度规划问题进行建模.设计算法阶段一般在考虑存储容量、时间窗约束[14]等条件下求解卫星任务规划方案, 当前地面离线任务规划的算法研究比较丰富, 主要研究算法整理见表 1, 此外相关研究从复杂网络[15]、容错调度[16]等角度求解调度问题.对于卫星调度规划算法的评估一般比较时间窗内任务安排数量或任务总体收益, 也有用AHP (Analytic hierarchy process)方法[17]来衡量调度算法的. 表 2对当前的单星地面离线任务调度规划系统进行梳理分析.
表 1 卫星地面离线任务调度规划算法Table 1 Single-satellite offline task scheduling algorithms算法类型 算法名称 应用场景/算法特性 精确算法 动态规划[28] 基于合成任务间时序特征, 将问题按照卫星的最大侧摆次数划分为多个阶段, 利用动态规划思想, 得到了问题的最优解. 分支定价[29] 用期望模型和机会约束规划模型对卫星调度问题进行数学建模, 将分支定界与列生成混合起来求解该问题. 贪婪算法[30] 在卫星可见时间窗和任务时间窗的约束条件下, 满足最大化资源利用的目标. 禁忌搜索[31] 针对操作约束下的对地观测卫星任务选取与调度问题, 使用禁忌搜索寻找近似最优方案. 拉格朗日松弛和线性搜索[32] 将对地观测卫星的日常成像调度问题建模成整数规划问题, 结合拉格朗日松弛法和线性搜索法来求解此问题. 遗传算法[33] 结合电磁探测卫星的具体约束条件, 建立了观测任务和数据传输的坐标调度模型, 使用遗传算法求解. 近似算法 粒子群算法[34] 在粒子群算法中使用局部领域拓扑结构来避免过早收敛, 并引入分支定界法来提高局部搜索能力. 差分进化[35-36] 为实现突变和交叉对进化个体进行实数编码, 用贪婪规则选择每代较优个体, 解码获得资源分配方案与任务执行时间序列. 蚁群算法[37] 应用均匀设计确定蚁群算法的组件, 设计出了高效求解敏捷卫星调度问题的蚁群算法. 蜂群算法[38] 采用人工蜂群算法对中继卫星调度问题进行求解, 对比发现蜂群算法优于其他群智能算法. 模拟退火[3] 设计模拟退火诸多机制:自适应温度控制、基于禁忌表重访限制机制和领域结构的智能组合, 高效地完成了卫星观测调度问题. 表 2 单星地面离线任务调度规划系统Table 2 Single-satellite offline task scheduling system调度规划系统 调度规划策略与方法 系统实际应用场景 SPIKE调度系统[39] 启发式调度规划方法 NASA的哈勃太空望远镜 ASPEN系统 局部提前规划, 迭代搜索 NASA的深空一号DS-1和对地观测EO-1 APSI系统 基于时间线的方法 欧洲太空局ESA 在时间层管理任务时间网络 MAPGEN系统 在简单时序约束网络上, 将混合主动式任务规划与约束规划框架相结合 火星探测器项目 ASPEN (Automated scheduling and planning environment)设计了一种易于表达与使用的建模语言和多个搜索推理机制, 提出了适合于混合主动操作的重规划方法, 提供了对卫星任务的实时规划和响应[18]. APSI (Advanced planning and scheduling initiative)构建了一个软件框架来提升任务规划支持工具开发的成本效益和灵活性, 把智能调度规划技术应用到空间任务规划业务上[19]. MAPGEN (Mixed-initiative activity plan generation system)将已有的规划编辑和资源建模的工具与一个基于约束的推理规划框架结合起来, 从而实现航天器的自动规划[20].
1.2 单星星上在线任务调度规划
相比地面离线而言, 星上在线任务调度规划要求卫星具备一定的自主性: 1)提高对突发事件的应对能力, 如森林火灾、火山爆发、船只的探测发现以及完全被云遮挡的图像失效, 卫星自主任务调度规划可直接触发针对同一目标点的二次成像, 对于有云层覆盖的图像和火灾监控任务中没有发现起火点的图像可以在星上立刻删除, 腾出存储空间; 2)快速响应任务冲突, 可用于其他低优先级任务和未被调度安排的任务; 3)提升卫星运行效能, 任务调度规划时可以考虑到星上资源的精确状态, 如当前的仪器温度、太阳能电池板的电量以及星上存储器的剩余空间, 进一步提升执行任务的效益; 4)减少对地面测控的依赖, 使卫星不必保持与地面间频繁通信, 增强卫星独立运行的鲁棒性[21].而受星上计算能力制约, 星上在线任务调度规划的约束更加复杂, 相关研究主要从规划方法和策略开展[22], Chien等[23-25]基于领域知识的迭代修复规划策略提出了星上自治架构并进行了拓展, Khatib等[26]使用了前向启发式贪婪搜索算法来对星上自主规划进行探索, Damiani等[27]将动态规划算法引入星上自主调度规划, Beaumet等[40-42]提出了一种迭代的随机贪婪搜索算法来对卫星的状态、任务优先级、成像时间与能量需求等进行计算和处理, 实现云探测能力的自主规划, Sa等[43]提出了一种基于Hopfield神经网络的多任务模式实时容错算法探讨实时应急任务的自主响应, Baek等[44]提出了一种改进遗传算法并设计了一个GUI来提高卫星自主任务调度的总体收益, 孙雅茹等[45]基于遗传算法提出了求解卫星自主运行任务调度问题的新型调度算法, Kono等[46]利用一个存储历史飞行运行计划的知识库来指导卫星的自主任务规划, 田志新等[47]利用实时遥测获取任务运行过程的动态约束参数, 基于有向图模型在线生成任务指令序列.此外, 针对星上在线任务调度规划要求快速、高效及算法收敛的特征, 当前研究多采用基于目标顺序的启发式算法, 通过混合多种规则对算法进行优化. Kim等[48]为实现SAR卫星编队接收到用户观测请求后快速地进行数据处理和目标分配, 设计了基于遗传算法的快速求解方法, Herz等[49]介绍了OrbView任务系统, 它整合了一个高保真飞行器仿真器, 在协调诸多约束下采用多种优化算法和预先设定计划快速得出最优成像方案. 表 3对当前的单星在线任务调度规划系统进行梳理分析.
表 3 单星星上在线任务调度规划系统Table 3 Single-satellite online task scheduling system调度规划系统 调度规划策略与方法 系统实际应用场景 RAX-PS系统 启发式调度规划方法 NASA的哈勃太空望远镜 ASE环境、CASPER系统 连续性规划 NASA对地观测EO-1 迭代修复 TechSat-2 采用局部搜索进行计划渐次精细化 AGATA 在线决策的反应型/慎重型架构 法国灵巧对地观测Pleiades卫星 反应型部分采用决策规则 慎重型部分采用迭代随机贪婪搜索算法 NASA的DS-1 (Deep space-1)搭载了第一个航天器自主控制系统RA (Remote agent), 凭借着RAX-PS (Remote agent experiment planner/scheduler)使得卫星能够根据高层目标自主生成任务规划方案. RAX-PS系统建立了基于约束的规划模型, 将高层目标以及系统初始状态作为规划模型的输入, 然后利用规划引擎进行求解[50-51].在RA的基础上, NASA在EO-1 (Earth observing-1)上实现各种自主功能, 开发了自主科学实验包ASE (Autonomous sciencecraft experiment)[26], 主要提供若干个自主软件组件[52]: 1)星上科学算法模块, 用于星上处理图像数据, 提取"有意思"的特征, 以发现突发事件并进行决策响应; 2)鲁棒式执行软件采用SCL语言包(Spacecraft command language)实现事件驱动的底层自主; 3)星上自主规划与调度软件, 采用连续活动调度规划执行重规划系统CASPER (Continuous activity scheduling planning execution and replanning), 可实现包括观测、数传等任务重规划. CASPER能够生成初始规划方案, 并在执行过程中处理包括新的科学事件、删除低价值图片和卫星故障等事件, 对初始方案进行在线星上重规划. CASPER采用一种基于迭代修复的局部搜索算法生成规划方案[53-54].该算法首先生成一个可能存在冲突或违反约束的原始方案, 每次尝试解决一个冲突, 直到所有的冲突都得到解决为止.对于已经生成好的规划方案, 如果发现了异常或者新的科学事件, 也采用迭代修复的方法进行可行解的搜索[55].
法国航天局的Pleiades系列卫星使用了自动化通用体系演示应用平台AGATA (Autonomy generic architecture——test and application)来实现星上自主调度规划, 当接收到来自环境变化的信息, 星上系统就会自主调整任务触发相关的参数, 同时重新计算下一次规划的触发时间, 并改变相应待规划任务的一些状态信息.随着时间的推移, 当到达规划触发时间时, 星载处理器开始进行任务规划, 并生成新的任务计划.在任务完成后, 星载处理器同样可以分析与处理成像结果, 从中自主生成需要的成像任务, 避免了地面管控与星地数据传输过程中的复杂流程.其中, 单星规划模型采用基于时间线的约束网络方法进行建立[56-57], 并构建在线决策的反应型/慎重型架构[58], 其中反应型控制部分采用启发式规则, 慎重型推理部分采用迭代随机贪婪算法, 将启发式规则与随机选择算子相结合, 允许从当前状态以逐次递增的方式制定活动计划.
1.3 星地一体化自主任务调度规划
单星地面离线与星上在线调度之间存在不同优势, 见表 4.星上平台与地面平台两者之间的配置取舍往往取决于决策时所需信息的可用性.比如, 针对对系统故障的快速响应要求, 显然采用星上自主是首要选择; 而对于及时响应用户的需求, 则地面自主更适用于处理其复杂性, 因此星地一体化任务调度比单纯地面或星上调度更符合未来实际应用.目前对星地一体自主任务调度规划的研究还处于探索阶段, 相关研究包括:规划框架[59-60]、规划方法[61]、调度模型[62], 总体而言, 地面和星上的两种配置均需要.
表 4 单星地面离线调度与单星在线调度的优势比较Table 4 The comparison of the advantages between single-satellite offline task scheduling and onboard task scheduling单星地面离线自主调度规划 星上在线自主任务调度规划 可用的CPU计算处理能力强大 软件更改灵活性强 对环境响应速度快 测试过程不影响星上任务执行 在无通信延迟的情况下处理图像数据 与操作员和用户的交互及时快捷 减少星地之间的通信交互次数 软件开发成本低 德国航空航天中心针对FireBIRD项目开发的VAMOS (Verification of autonomous mission planning onboard a spacecraft)是面向星地一体化的任务规划框架.该框架通过赋予卫星一定的规划能力的方法来解决地面约束推理不精确的问题[63].首先地面根据资源的上下界限制生成任务计划并通过指令上传到卫星上, 在与地面站的通信间隔时间内, 地面任务规划系统仍然运行并可以更改调整任务计划, 同时星上模块通过扫描图像探测发现起火点等突发事件, 根据具体环境信息触发星上任务规划流程, 生成实时命令序列并将其插入到任务计划中, 及时调整下传计划完成对突发事件快速响应. VAMOS充分结合地面硬件的计算性能和星上软硬件在响应时间内的资源传播推理能力, 在星上自主实现规划, 调度和指令序列生成, 以验证一个任务调度规划系统的适用性, 实用性和收益[64], 共分为三个模块部分: 1)任务规划系统的地面附属部分, 自动生成可进行任务计划拓展的场景和条件. 2)星上模块OBoTiS (Onboard timeline selection), 用于是否激活已经在地面处理计算过的候选任务; 当该模块激活时, 星上规划器会在提前选定的时间点, 检测各资源参数是否处于地面预先计算的值域内.若满足条件, 则执行任务计划的拓展. 3)星上模块OBETTE (Onboard event triggered timeline extension), 用于调度插入任务; 当该模块被激活时, 星上规划器得到突发事件的触发信息. OBETTE模块得到该事件的执行时间和观测角度等任务参数, 并将相应的参数装订到预定义的命令任务模板中去, 一并发送给OBoTiS模块, 作为新的拓展任务计划.
算法中加入了OBoTiS On-Ground Add-on和OBETTE On-Ground Add-On模块, 其功能就是对比实际资源使用情况和规划时资源使用情况, 并对当前时刻之后的资源进行重新预测.在星上自主调整的同时, 地面系统的信息也要相应更新, 以辅助后续决策.星上部分则能实现星上实时调整卫星状态检查与调整, 从而决定某个行动是否能正常被执行, 同时可星上实时发现可疑任务, 利用卫星的独特位置优势来挖掘具有潜在价值的活动.所以这就要求对于自主探测到的事件快速反应、最大化星上资源利用率.为了实现这个目标, 首先需要对程序的触发机制进行设计. FireBIRD中设计触发机制有两种:第一种是星上每执行完一个指令, 对约束与资源信息进行检查与更新, 若发现约束与资源等信息的预测值与真实值差距大于可接受范围, 那么针对这个动作及其相关动作进行重规划; 第二种是VIMOS模块通过图像处理, 生成新的任务.在触发规划的时间点, 星上采用一种不变的优先级来进行规划(即某种贪婪规则), 目的是为了降低星上软件系统的复杂性.同时, 星上资源的预测也应随着实际已使用的情况实时改变, 即通过对星上实际约束环境信息与地面的预测信息比较, 实现星上时间窗的调整.
2. 多星协同任务调度规划研究
2.1 多星地面离线协同任务调度规划
对比单星, 多星具有诸多优势: 1)从时空、光谱等方面提高对地观测效益; 2)多颗不同载荷的卫星的协同能够取代大型复杂的单星以实现更完备的功能; 3)多星的鲁棒性强于单星.多星地面离线任务调度规划多采用集中式架构[65-67]和集中-分布式架构[68-69], 主要目标是高效地完成用户的任务需求.观测计划由地面生成并上注到卫星星座中去, 具有重规划能力, 从而将自主需求从星上部分转换到地面部分.
在对多星地面离线任务调度规划的方法研究中, 学者们通过设计不同规则提出对应的算法来解决多星调度问题. Globus等[70-71]将观测任务放置在多个卫星中没有约束冲突的最早可用的时间窗内来进行任务分配, Richards等[72]对于星座任务规划问题, 采用知识库来安排不同任务, Bianchessi等[73]采用了先到先服务的方式来安排多星成像和数传任务的顺序序列, 设计了基于前瞻和回滚功能的调度算法来解决不同载荷资源的分配问题, Dilkina等[74]针对多敏捷卫星任务规划问题展开研究, 提出了一种将排列调度方法和约束传播算法相结合的求解方法.贺川等[75]利用最小时间窗窗口冲突度来将不同观测任务分配值对应的时间窗口.王沛等[12, 76]设计了一个任务的灵活度指标, 利用该指标修正的任务优先级及竞争度来确定任务的排序, 同时提出了一种基于优先级的避免冲突、有限回溯、按需下传的启发式方法算法, 完成对地球观测卫星星座的调度. Wang等[77]针对任务属性变化等动态性特点, 设计了两套启发式策略来解决该多星动态调度问题. Li等[78]引入模糊数和神经网络来判断扰动对系统的影响, 若扰动达到阈值则启动重规划.姜维等[79]对组网卫星在地面离线模式下带有任务协同工作的卫星任务调度规划问题进行了定性分析, 包括形式化表示多种协同方式以及相对应的新约束关系.
在多星地面离线协同任务调度规划中, 多Agent系统方法与分布式计算架构的研究热度越来越高, Agogino等[80]针对面向空间测量的Cube-Sats集群, 采用多Agent系统方法, 以每个Agent代表单个Cube-Sat, 在用户给定观测任务请求时, 各Agent采用特定的成本代价计算函数计算投标值, 按照投标值进行任务分配. Cheng等[81]提出了多星联合规划系统MSCPS (Multiple satellites collaborative planning system), 将多星地面离线协同任务规划问题转化为卫星之间的协同任务分配问题, 然后采用多Agent系统方法, 基于群智能和多属性决策的模糊综合评价方法在扩展合同网协议ECNP (Extended contract net protocol)下进行招标, 形成有效的任务规划. Skobelev等[82]采用分布式的多Agents系统来解决多星调度问题, 将观测需求视为需求Agent, 将卫星和地面站视为是资源Agent, 通过资源和需求的迭代匹配来优化调度方案.
表 5归纳了目前比较成熟的两套系统, 其中, 美国空军研究实验室的TechSat21卫星主要使用SpaceCAPS (Spacecraft cluster automatic planner/scheduler)来完成对星簇的任务规划, 它是基于NASA的ASPEN环境设计了一个分层规划的调度机制, 按照星座、星群和单个卫星或传感器的层次分配任务, 其中每个卫星编队采用集中迭代修复的构造式调度方法来确定各个传感器的调度方案, 在迭代修复过程中采用多种启发式规则[83-84].
表 5 多星地面离线任务调度规划系统Table 5 Multi-satellite ground offline task scheduling system调度规划系统 调度规划策略与方法 系统实际应用场景 SpaceCAPS系统 分为星座、星群和单个卫星三个层次上的规划 TechSat21计划 构造算法与迭代修正方法相结合 PLANET系统 支持任务动态重规划 MUSIS项目 欧洲多国合作的MUSIS项目(Multinational space-based imaging system for surveillance, reconnaissance and observation)使用了PLANET系统来进行多星任务协同任务规划, 它将任务分成不同优先级, 逐级利用一种按照时间顺序排序算法来分配任务至各个卫星, 并且遵循效率性(快速构造新方案)、最优性(尽可能安排优先级高的任务)、稳定性(与旧方案尽可能接近)的原则滚动地进行重规划[85].
2.2 多星星上在线协同任务调度规划
大部分研究将多星协同任务调度规划问题简化为优化问题, 并用传统的优化方法, 如贪婪式[86-87]、回溯法[88]和简单启发式[89]等算法进行解决, 这些研究一般只考虑小规模问题, 无法满足需要面对的动态任务环境的多星协同任务调度的需求.类似于单星, 多星任务调度规划也逐渐要求放置星上处理, 以应对多星更为复杂的动态环境, 不同之处在于多星还要求实现星间协同.而出于保守考虑, 多星星上在线协同任务调度规划一般采用集中式架构, 如NASA在ASE环境中将卫星编队中一个航天器作为母星, 通过星间通信来调度伴飞航天器的运行. Truszkowski等[90]提出一种航天器星座交互场景, 构建以高轨卫星为主星, 低轨卫星为成员星的完全集中式架构.该星座由16颗低轨道太阳同步卫星和4颗高轨卫星(其中第4颗作为备份星)组成, 其中高轨卫星接收低轨成员星发送的资源状态信息, 对星座的全局行为进行掌控, 其星载计算机具有强大的处理能力, 负责整个星座的管理运行, 与地面控制站时刻保持通信交互; 低轨卫星相对简单, 从高轨卫星处接受到使命目标的指令与变化, 并将自身的资源状态数据传送给高轨卫星. Zheng等[91]以深空低频电磁波探测项目为背景, 让主星负载整个系统所有卫星的任务规划工作, 采用自适应遗传算法来分解任务目标, 完成星座的任务规划调度, 仿真实验表明这种完全集中式的规划体系在短期规划中可获得一个较优的调度解. Qin等[92]针对异构低轨小卫星网络, 采用完全集中式架构, 提出了基于截止日期的资源平衡式任务分配算法(Deadline based resource balancing, DBRB). DBRB算法配置在卫星集群的主星上, 需要主星维护每个成员星的最新状态, 利用每个成员星的剩余电源电量和搭载的载荷类型选取侯选星, 进行任务执行.但集中式架构对主星的计算能力和星间通信链路要求较高, 且一旦主星发生故障, 则系统效能会大打折扣.
为了应对更加复杂的通信环境, 减轻对中心卫星的依赖, 去中心化的分布式调度方法受到了青睐, Bonnet等[93]针对Fuego项目的对地观测星群任务调度规划[94]提出了分散式架构及相应的混合优化方法:对于单星规划, 采用慎重型方法, 星上生成预案, 并将任务请求集合和执行意图共享给其他卫星; 对于多星协同, 采用反应式规则, 分别针对冗余分配导致的软冲突和硬冲突采用不同的冲突消解策略和步骤, 后续研究[95]考虑任务请求异步到达和间断性通信的情况下分布式卫星系统中的分布式任务分配问题, 提出了在线渐近式动态组织机制, 用以下三步来表示:各卫星独立规划; 各卫星之间相互通信, 构建共同的知识; 复杂任务需要多个卫星实现不同的子任务来完成, 则各卫星构建和修改联盟编队.该应用场景中的通信约束表现为:地面控制站仅与高轨道卫星进行通信; 高轨道卫星在其自身, 地面站和低轨道卫星之间起到通信中继的作用; 低轨道卫星仅能与高轨道卫星进行通信. Van Der Horst[96]研究分布式卫星系统的任务分配问题, 使用完全分布式的市场拍卖机制来有效地分配不稳定网络中的任务, 而不需要全局的状态知识, 各成员星根据各自的资源剩余水平, 计算投标值, 并将其相对适应度作为投标值, 与任务分配星进行通信. Bonnet[97]采用面向方案优化的自适应多Agent系统来解决多目标的星座调度问题, 系统采用去中心化的分布式调度方法来解决星座的动态调度问题, 各个卫星通过本地调度和多次协同沟通来与其他卫星获得一致性意见.张正强[98]将分布式卫星系统任务规划与控制问题分为星群任务规划与单星自主控制两个层次, 进而建立了一种高可靠性的集中-分布式架构; 构建了成像卫星Agent的分层混合结构, 包括全局控制层、通信与协作层、局部规划层、监控层和执行层等5层.在上述框架基础上, 提出与之相匹配的星群任务规划方法——基于约束的诚实合同网协议, 分别设计多种招标任务选择策略和评标策略.高黎[99]则从协商和任务优化分配两方面展开了任务协作机制的研究, 对传统合同网协议进行扩充, 引入信任度、合作频度等智能体心智状态参数.庞中华[100]从低轨卫星在线任务规划的时效要求高, 冲突调整要求高和资源类型多样三个特点入手, 对传统的集中-分布式架构进行拓展, 在主星和成员星的基础上加入一类中层管理Agent, 从而形成包含三类Agent的多Agent架构.
2.3 多星星地一体协同任务调度规划
星地一体化的多星协同任务调度规划多采用集中-分布式架构, 首先地面管控是整个系统的中心实体, 通过最新的星上状况和任务属性等信息, 在各个局部实体中进行任务分配, 并在可见时间窗内向各卫星发布初步规划方案, 每个卫星作为本地实体, 将自身的状态, 中心实体的任务请求/建议, 以及突发事件等因素考虑进来, 与星群间协同进行自主调度规划.星地一体化架构既利用到地面强大的计算能力, 又兼顾到星上自主的优势, 如星上自主决策可以实时得到卫星自身的状态信息, 而地面控制站不能; 星上自主探测到新的地面情况并能对探测到的情况进行及时响应[52]; 星上自主云判能够使卫星避免无用的可见光成像活动[101]; 星上的图像处理分析使卫星能够首先移除无用的观测图像数据, 然后保存到星上的存储空间, 避免无用的数据下传[102-103].
DIPS (Distributed intelligent planning and scheduling)系统是一个分布式智能规划和调度系统[104], 见表 6, 基于DIPS的卫星只接收来自地面站的高阶目标, 并在星上执行自主调度与规划, 与其他卫星合作完成目标任务, 它将每颗卫星建模为带有自主功能的Agent, 并采用了一种域分配算法, 该算法通常在第一次协调工作之后创建一个可行的调度方案, 从而减少调度过程中的Agent间协商, 在保持约束和约束的基础上, 根据约束传播范式, 采用优化Agent来优化时间和资源的使用, 实现基于优先级的调度, 并在Agent之间采用层次化的确认/授权机制实现全局目标协调[105-107].
表 6 多星星地一体化协同任务调度规划系统Table 6 Multi-satellite and ground integrated task scheduling system调度规划系统 调度规划策略与方法 系统实际应用场景 DIPS系统 采用分散的架构 3CSAT星座 层次任务分解 层次化的确认/授权机制 基于优先级的调度算法 Damiani等[94]以Bird项目(http://spacesen-sors.dlr.de/-SE/bird/)和Fuego项目[108]为研究背景, 针对星上自主规划调度模块进行研究, 并提出了一套星地一体化的多星协同任务规划方案, 其中所建立的集中-分布式决策架构由两部分组成: 1)以地面控制站为中心的跟踪任务分配机制, 会被频繁触发; 2)每颗卫星具有星上的反应式决策/规划机制, 时刻处于工作状态, 可随时中断. Tripp等[109]提出了基于Agent间接通信协同的任务管理系统, 采用集中-分布式的架构, 其中地面站将一系列的任务请求一次性全部发布给所有的卫星, 然后各个卫星根据它们自身的工作负荷, 已被其他卫星标记为待执行的任务集合和上轮中重复执行的任务集合等情况, 选择能够执行的任务.
Cesta等[110]在全球环境与安全监测计划GMES的背景下, 针对分布式智能体自治(Distributed agents for autonomy, DAFA)技术展开研究, 论证多Agent技术在卫星应用领域的优势, 旨在基于Agent的设计框架, 定义、设计和研发Agent系统; Grey[111]针对GMES项目, 构建面向多Agent系统的自律分散型空间控制架构(Holonic agent space architecture, HASA), 其中包含4类Agents: Product、Executor、Planner和Resource.分别从空间分布和任务类型两个维度, 对各Agent进行划分, 具体如下:面向多星协同任务的地面段, 包括用户优先级定义模块, 任务分配模块和地面站; 面向单星任务的地面段, 包括飞行动力学模块, 数据处理模块, 任务规划器和任务优先级定义模块; 面向单星任务的空间段, 包括星上规划模块、星上通信模块、星上执行器、星上监视、星上规划调度器和星上探测载荷.
3. 结论与展望
3.1 本文结论
本文综述了卫星自主与协同任务调度规划的研究现状, 对单星和多星任务调度规划问题按照"地面离线-星上在线-星地一体"的研究进展进行了梳理总结.可以看到在该领域已经有很多有价值的研究成果, 而且相关研究已经得到了世界各国学者的普遍关注.但是不难发现, 目前的研究成果很多都有其具体的应用背景, 因此难免有一定的缺陷:
1) 单星在线调度研究多是针对随机到达或自身生成的单个应急任务进行重调度, 而面对动态性越来越强的应急任务环境, 其中应急任务会有多个来源, 包括地面应急上注、他星通信传递和自身应急生成等等, 亟需一种兼顾应急响应性能和星上有限计算条件的单星在线调度机制和方法.
2) 大部分研究在考虑自主与协同任务调度规划问题时会对研究对象进行多项简化与假设, 如:分布式架构下星间具备完全通信或稳定通信链路; 星上计算能力达到较高水平, 计算时间满足星上响应的时效性; 任务接收与数据下传都作为一种周期性或者确定性活动; 系统内所有卫星是同构的, 所搭载的成像载荷类型一样等, 这些简化和假设, 导致了这些研究成果的实际应用将十分困难.
3) 大部分在线调度算法的研究都是面向非敏捷卫星的, 对敏捷卫星在线调度算法研究较为薄弱, 而多敏捷自主卫星调度问题是未来自主卫星大规模应用中必须要解决的关键性问题, 同时, 只有少数学者对问题中时间依赖的时序约束进行研究, 该时序约束由时间窗约束和时间依赖的姿态机动约束组成, 是制约敏捷卫星应用效率的关键.
4) 当前的多星协同任务调度研究大多数停留在架构设计层面, 缺乏针对不同架构的算法机制详细设计, 进而无法对所提出的架构进行定量分析验证, 不能形成面向架构设计的反馈机制.另外, 对多星协同内部协调控制策略的研究较少, 导致不能很好地控制自主与协同调度规划问题的求解过程, 各模块间的配合程度较低.
针对上述提出的相关研究不足之处, 为满足日益迫切、复杂的军事情报保障和国土监测需求, 未来卫星自主与协同任务调度规划的研究还有许多工作要做:
1) 对于卫星在线调度问题, 需要同时考虑卫星所处的动态环境和计算能力:其他卫星的状态信息获取延迟滞后、任务发布与任务到达之间存在动态不确定的时间差、应急任务的时效可用性、星上计算能力对动态任务的应急响应性能等, 制定任务规划/重规划的决策时间点、机制策略、规划算法等, 将动态观测需求常态化.此外, 进一步深入研究需要考虑完成任务所需动作, 既完成任务规划, 又要完成相应动作的规划.
2) 未来分布式卫星系统大多是异构的, 多星在线协同的架构多种多样, 不同的功能配置方式形成不同的协同架构, 而不同的协同架构又决定了不同的协同算法机制, 因此亟需从具体的协同算法设计入手, 对不同的协同架构进行系统效能和运行成本的评估分析, 进而从提高效费比的角度, 对功能配置方式形成反馈.
3) 卫星自主规划技术的本质是将原先由地面系统所承担的规划、控制等功能全部转移到卫星上, 因此自主规划过程十分复杂, 不仅需要模型和算法, 还要依靠各种功能模块的协调配合.对自主规划模块的功能结构进行准确划分, 有效分解复杂的自主规划问题求解过程.确定协调控制策略, 控制自主规划问题的求解过程, 实现模块间的协调配合.
3.2 未来展望
综上所述, 卫星自主与协同任务调度规划具有广阔的研究前景, 其未来可能的发展方向有:
1) 面向大规模卫星集群的协作任务调度规划.目前所应用到的分布式对地观测卫星系统规模较小, 随着卫星规模的扩大、载荷种类增多, 单一的管控结构势必会影响到卫星集群协作效率, 完全分布式的星座结构会是大规模卫星集群协作任务规划的发展方向.在未来的研究中, 如何在大规模卫星集群中, 高质量地动态响应某一特定任务需求, 协同多载荷完成对目标多手段侦查, 保持星座稳定运行, 成为了研究大规模卫星集群的协作任务调度规划的关键问题.
2) 接近完全考虑约束的卫星调度规划.大部分研究只针对某一特殊场景进行假设实验, 没有考虑诸多在实际工程应用中的约束, 如:区域目标/移动目标的观测窗口变化; 星上能量与固存的不确定性; 通信时间窗口和通信环路对通信的约束等.随着未来卫星技术的发展, 要求对卫星实现精细化调度规划, 具体时刻点的确定需考虑相应资源的调度情况, 并对这些调度子问题一并建模求解, 这种接近完全考虑约束的要求为卫星调度规划研究带来新的方向.另外, 星上计算能力有限, 如何在考虑复杂的约束下提高算法的速度和效率, 也是下一步研究方向.
3) 引入机器学习的星上自主任务规划.自主卫星在执行任务时, 会产生大量的对地观测动作、数据回传动作、对日定向动作等数据.可以引入机器学习的模块来解析这些数据, 让卫星可以通过自动获取知识的方式, 提高自主规划模块的性能.把机器学习与自主卫星任务规划结合涉及到对环境和卫星自身关键信息提取、状态监视和综合评估、基于历史数据和决策模型调整调度策略等多个研究问题.未来星载计算机能力逐渐加强、自主卫星应用场景不断拓宽, 对智能化自主卫星的决策能力、任务规划能力也会有更高的研究需求.
-
表 1 卫星地面离线任务调度规划算法
Table 1 Single-satellite offline task scheduling algorithms
算法类型 算法名称 应用场景/算法特性 精确算法 动态规划[28] 基于合成任务间时序特征, 将问题按照卫星的最大侧摆次数划分为多个阶段, 利用动态规划思想, 得到了问题的最优解. 分支定价[29] 用期望模型和机会约束规划模型对卫星调度问题进行数学建模, 将分支定界与列生成混合起来求解该问题. 贪婪算法[30] 在卫星可见时间窗和任务时间窗的约束条件下, 满足最大化资源利用的目标. 禁忌搜索[31] 针对操作约束下的对地观测卫星任务选取与调度问题, 使用禁忌搜索寻找近似最优方案. 拉格朗日松弛和线性搜索[32] 将对地观测卫星的日常成像调度问题建模成整数规划问题, 结合拉格朗日松弛法和线性搜索法来求解此问题. 遗传算法[33] 结合电磁探测卫星的具体约束条件, 建立了观测任务和数据传输的坐标调度模型, 使用遗传算法求解. 近似算法 粒子群算法[34] 在粒子群算法中使用局部领域拓扑结构来避免过早收敛, 并引入分支定界法来提高局部搜索能力. 差分进化[35-36] 为实现突变和交叉对进化个体进行实数编码, 用贪婪规则选择每代较优个体, 解码获得资源分配方案与任务执行时间序列. 蚁群算法[37] 应用均匀设计确定蚁群算法的组件, 设计出了高效求解敏捷卫星调度问题的蚁群算法. 蜂群算法[38] 采用人工蜂群算法对中继卫星调度问题进行求解, 对比发现蜂群算法优于其他群智能算法. 模拟退火[3] 设计模拟退火诸多机制:自适应温度控制、基于禁忌表重访限制机制和领域结构的智能组合, 高效地完成了卫星观测调度问题. 
下载: 导出CSV
表 2 单星地面离线任务调度规划系统
Table 2 Single-satellite offline task scheduling system
调度规划系统 调度规划策略与方法 系统实际应用场景 SPIKE调度系统[39] 启发式调度规划方法 NASA的哈勃太空望远镜 ASPEN系统 局部提前规划, 迭代搜索 NASA的深空一号DS-1和对地观测EO-1 APSI系统 基于时间线的方法 欧洲太空局ESA 在时间层管理任务时间网络 MAPGEN系统 在简单时序约束网络上, 将混合主动式任务规划与约束规划框架相结合 火星探测器项目
下载: 导出CSV
表 3 单星星上在线任务调度规划系统
Table 3 Single-satellite online task scheduling system
调度规划系统 调度规划策略与方法 系统实际应用场景 RAX-PS系统 启发式调度规划方法 NASA的哈勃太空望远镜 ASE环境、CASPER系统 连续性规划 NASA对地观测EO-1 迭代修复 TechSat-2 采用局部搜索进行计划渐次精细化 AGATA 在线决策的反应型/慎重型架构 法国灵巧对地观测Pleiades卫星 反应型部分采用决策规则 慎重型部分采用迭代随机贪婪搜索算法
下载: 导出CSV
表 4 单星地面离线调度与单星在线调度的优势比较
Table 4 The comparison of the advantages between single-satellite offline task scheduling and onboard task scheduling
单星地面离线自主调度规划 星上在线自主任务调度规划 可用的CPU计算处理能力强大 软件更改灵活性强 对环境响应速度快 测试过程不影响星上任务执行 在无通信延迟的情况下处理图像数据 与操作员和用户的交互及时快捷 减少星地之间的通信交互次数 软件开发成本低
下载: 导出CSV
表 5 多星地面离线任务调度规划系统
Table 5 Multi-satellite ground offline task scheduling system
调度规划系统 调度规划策略与方法 系统实际应用场景 SpaceCAPS系统 分为星座、星群和单个卫星三个层次上的规划 TechSat21计划 构造算法与迭代修正方法相结合 PLANET系统 支持任务动态重规划 MUSIS项目
下载: 导出CSV
表 6 多星星地一体化协同任务调度规划系统
Table 6 Multi-satellite and ground integrated task scheduling system
调度规划系统 调度规划策略与方法 系统实际应用场景 DIPS系统 采用分散的架构 3CSAT星座 层次任务分解 层次化的确认/授权机制 基于优先级的调度算法
下载: 导出CSV
-
[1] 姜维, 郝会成, 李一军.对地观测卫星任务规划问题研究述评.系统工程与电子技术, 2013, 35(9):1878-1885 doi: 10.3969/j.issn.1001-506X.2013.09.13Jiang Wei, Hao Hui-Cheng, Li Yi-Jun. Review of task scheduling research for the Earth observing satellites. Systems Engineering & Electronics, 2013, 35(9):1878-1885 doi: 10.3969/j.issn.1001-506X.2013.09.13 [2] Wu G H, Liu J, Ma M H, Qiu D S. A two-phase scheduling method with the consideration of task clustering for earth observing satellites. Computers & Operations Research, 2013, 40(7):1884-1894 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=4831ab531941104e73b131b252c5acd4 [3] Wu G H, Wang H L, Li H F, Pedrycz W, Qiu D S, Ma M H, et al. An adaptive Simulated Annealing-based satellite observation scheduling method combined with a dynamic task clustering strategy. eprint arXiv: 1401.6098, 2014 [4] Tangpattanakul P, Jozefowiez N, Lopez P. A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite. European Journal of Operational Research, 2015, 245(2):542-554 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=31aae510d0726be78cc13ee0da604c9a [5] Gabrel V, Vanderpooten D. Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite. European Journal of Operational Research, 2002, 139(3):533-542 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=d3170607ec4ed47cd92e03843bdcd662 [6] Sarkheyli A, Vaghei B G, Moghadam R A, Bagheri A. Scheduling earth observation activities in LEO satellites using graph coloring problem. In: Proceedings of the 5th International Symposium on Telecommunications. Tehran, Iran: IEEE, 2010. 928-931 [7] Augenstein S. Optimal scheduling of earth-imaging satellites with human collaboration via directed acyclic graphs. Journal of Experimental Psychology, 2014, 38(3):338-346 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=CC0214403449 [8] Wolfe W J, Sorensen S E. Three scheduling algorithms applied to the earth observing systems domain. Management Science, 2000, 46(1):148-166 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=8af8b954508eaf410ed6982338b76097 [9] Vasquez M, Hao J K. A "Logic-Constrained" knapsack formulation and a Tabu algorithm for the daily photograph scheduling of an earth observation satellite. Computational Optimization & Applications, 2001, 20(2):137-157 doi: 10.1023-A-1011203002719/ [10] Gabrel V, Murat C. Mathematical programming for earth observation satellite mission planning. Operations Research in Space and Air. Boston, MA: Springer, 2003. 103-122 [11] Spangelo S, Cutler J, Gilson K, Cohn A. Optimization-based scheduling for the single-satellite, multi-ground station communication problem. Computers & Operations Research, 2015, 57:1-16 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=a2d940dba1ac975722acbef7ff68162d [12] Wang P, Reinelt G, Gao P, Tan Y J. A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation. Computers & Industrial Engineering, 2011, 61(2):322-335 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=1b9f4075623677a059762396113dd878 [13] 冉承新, 熊纲要, 王慧林, 邱涤珊.电子侦察卫星任务规划调度模型与算法研究.通信对抗, 2009, (1):3-8, 13 http://cdmd.cnki.com.cn/Article/CDMD-10213-1015980871.htmRan Cheng-Xin, Xiong Gang-Yao, Wang Hui-Lin, Qiu Di-Shan. Study of electronic reconnaissance satellites mission scheduling model and algorithm. Communication Countermeasures, 2009, (1):3-8, 13 http://cdmd.cnki.com.cn/Article/CDMD-10213-1015980871.htm [14] 顾中舜, 陈英武.对地观测卫星调度的混合整数规划模型及求解.飞行器测控学报, 2007, 26(1):19-24 http://d.old.wanfangdata.com.cn/Periodical/fxqckxb200701005Gu Zhong-Shun, Chen Ying-Wu. MIP model and algorithm for resolving scheduling of Earth observation satellites. Journal of Spacecraft TT & C Technology, 2007, 26(1):19-24 http://d.old.wanfangdata.com.cn/Periodical/fxqckxb200701005 [15] Wang X W, Chen Z, Han C. Scheduling for single agile satellite, redundant targets problem using complex networks theory. Chaos, Solitons & Fractals, 2016, 83:125-132 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=19c3fd7543c7b03d0ae0faa032ae1672 [16] 喻兴标, 郑昌文, 胡晓惠, 赵军锁.空间环境中的多处理器混合容错调度算法.宇航学报, 2013, 34(6):808-817 doi: 10.3873/j.issn.1000-1328.2013.06.010Yu Xing-Biao, Zheng Chang-Wen, Hu Xiao-Hui, Zhao Jun-Suo. A hybrid fault-tolerant scheduling algorithm for multiprocessor in space environment. Journal of Astronautics, 2013, 34(6):808-817 doi: 10.3873/j.issn.1000-1328.2013.06.010 [17] 陈济舟, 王钧, 李军, 景宁.卫星任务规划算法综合评价技术研究.计算机工程, 2009, 35(20):59-61, 65 doi: 10.3969/j.issn.1000-3428.2009.20.020Chen Ji-Zhou, Wang Jun, Li Jun, Jing Ning. Research on comprehensive evaluation technology of satellite mission schedule algorithm. Computer Engineering, 2009, 35(20):59-61, 65 doi: 10.3969/j.issn.1000-3428.2009.20.020 [18] Chien S, Rabideau G, Knight R, Sherwood R, Engelhardt B, Mutz D, et al. ASPEN-automated planning and scheduling for space mission operations. In: SpaceOps 2000. France, 2000. [19] Cesta A, Fratini S, Donati A, Oliveira H, Policella N. Rapid prototyping of planning & scheduling tools. In: Proceedings of the 3rd IEEE International Conference on Space Mission Challenges for Information Technology. Pasadena, CA, USA: IEEE, 2009. 270-277 [20] Bresina J L, Jónsson A K, Morris P H, Rajan K. Mixed-initiative planning in MAPGEN: capabilities and shortcomings. In: Proceedings of the ICAPS-05 Workshop on Mixed-initiative Planning and Scheduling. Monterey, CA, United States, 2005. [21] 赵萍, 陈志明.应用于卫星自主任务调度的改进遗传算法.中国空间科学技术, 2016, 36(6):47-54 http://d.old.wanfangdata.com.cn/Periodical/zgkjkxjs201606006Zhao Ping, Chen Zhi-Ming. An adapted genetic algorithm applied to satellite autonomous task scheduling. Chinese Space Science and Technology, 2016, 36(6):47-54 http://d.old.wanfangdata.com.cn/Periodical/zgkjkxjs201606006 [22] 陈浩, 李军, 景宁, 刘湘辉, 唐宇.电磁探测卫星星上自主规划模型及优化算法.航空学报, 2010, 31(5):1045-1053 http://d.old.wanfangdata.com.cn/Periodical/hkxb201005022Chen Hao, Li Jun, Jing Ning, Liu Xiang-Hui, Tang Yu. Scheduling model and algorithms for autonomous electromagnetic detection satellites. Acta Aeronautica Et Astronautica Sinica, 2010, 31(5):1045-1053 http://d.old.wanfangdata.com.cn/Periodical/hkxb201005022 [23] Chien S, Sherwood R, Rabideau G, Castano R, Davies A, Burl M, et al. The Techsat-21 autonomous space science agent. In: Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems. Bologna, Italy: ACM, 2002. 570-577 [24] Chien S, Engelhardt B, Knight R, Rabideau G, Sherwood R. Onboard autonomy on the three corner sat mission. In: Proceedings of the 6th International Symposium on Artifical Intelligence, Robotics and Automation in Space. Montreal, Quebec, Canada, 2001. [25] Chien S, Sherwood R, Tran D, Cichy B, Rabideau G, Castano R, et al. Using autonomy flight software to improve science return on earth observing one. Journal of Aerospace Computing, Information, & Communication, 2005, 2(4):196-216 doi: 10.2514/1.12923 [26] Khatib L, Frank J, Smith D E, Morris R, Dungan J, Technology K. Interleaved observation execution and rescheduling. In: Proceedings of the Icaps-03 Workshop on Plan Execution. Moffett Field, CA, United States, 2003. [27] Damiani S, Verfaillie G, Charmeau M C. An anytime planning approach for the management of an earth watching satellite. In: Proceedings of the 4th International Workshop on Planning and Scheduling for Space (IWPSS-04). Darmstadt, Germany, 2004. [28] 白保存, 贺仁杰, 李菊芳, 陈英武.卫星单轨任务合成观测问题及其动态规划算法.系统工程与电子技术, 2009, 31(7):1738-1742 doi: 10.3321/j.issn:1001-506X.2009.07.046Bai Bao-Cun, He Ren-Jie, Li Ju-Fang, Chen Ying-Wu. Satellite orbit task merging problem and its dynamic programming algorithm. Systems Engineering & Electronics, 2009, 31(7):1738-1742 doi: 10.3321/j.issn:1001-506X.2009.07.046 [29] Wang J J, Demeulemeester E, Qiu D S. A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds. Computers & Operations Research, 2016, 74:1-13 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=05cb63154934dbe075e3241c73704e7f [30] 刘洋, 陈英武, 谭跃进.基于贪婪算法的卫星地面站任务规划方法.系统工程与电子技术, 2003, 25(10):1239-1241 doi: 10.3321/j.issn:1001-506X.2003.10.019Liu Yang, Chen Ying-Wu, Tan Yue-Jin. Mission planning method of the satellite ground station based on the greedy algorithm. Systems Engineering & Electronics, 2003, 25(10):1239-1241 doi: 10.3321/j.issn:1001-506X.2003.10.019 [31] Bianchessi N, Cordeau J F, Desrosiers J, Laporte G, Raymond V. A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites. European Journal of Operational Research, 2007, 177(2):750-762 doi: 10.1016-j.ejor.2005.12.026/ [32] Lin W C, Liao D Y, Liu C Y, Lee Y Y. Daily imaging scheduling of an Earth observation satellite. IEEE Transactions on Systems, Man, and Cybernetics-Part A:Systems and Humans, 2005, 35(2):213-223 doi: 10.1109/TSMCA.2005.843380 [33] Chen H, Wu J J, Shi W Y. Coordinate scheduling approach for EDS observation tasks and data transmission jobs. Journal of Systems Engineering and Electronics, 2016, 27(4):822-835 doi: 10.21629/JSEE.2016.04.11 [34] Zhang D Y, Guo L, Cai B, Sun N, Wang Q. A hybrid discrete particle swarm optimization for satellite scheduling problem. In: Proceedings of the 2011 IEEE Conference Anthology. China: IEEE, 2011. 1-5 [35] Wu J G, Wang S, Li Y, Dou C P, Hu J. Application of differential evolution algorithm in multi-satellite monitoring scheduling. In: Proceedings of the 27th Conference of Spacecraft TT&C Technology in China. Lecture Notes in Electrical Engineering, vol.323. Berlin, Heidelberg: Springer, 2015. 347-357 [36] 皮本杰, 翟淑宝.信号采集卫星系统星地资源快速调度优化方法.宇航学报, 2016, 37(3):348-356 doi: 10.3873/j.issn.1000-1328.2016.03.014Pi Ben-Jie, Zhai Shu-Bao. Quick optimal schedule method of onboard and ground resources for signal collection satellite system. Journal of Astronautics, 2016, 37(3):348-356 doi: 10.3873/j.issn.1000-1328.2016.03.014 [37] 严珍珍, 陈英武, 邢立宁.基于改进蚁群算法设计的敏捷卫星调度方法.系统工程理论与实践, 2014, 34(3):793-801 http://d.old.wanfangdata.com.cn/Periodical/xtgcllysj201403028Yan Zhen-Zhen, Chen Ying-Wu, Xing Li-Ning. Agile satellite scheduling based on improved ant colony algorithm. Systems Engineering-Theory & Practice, 2014, 34(3):793-801 http://d.old.wanfangdata.com.cn/Periodical/xtgcllysj201403028 [38] Zhuang S F, Yin Z D, Wu Z L, Shi Z G. The relay satellite scheduling based on artificial bee colony algorithm. In: Proceedings of the International Symposium on Wireless Personal Multimedia Communications (WPMC). Sydney, NSW, Australia: IEEE, 2015. 635-640. [39] Johnston M D. Spike: AI scheduling for NASA's Hubble Space Telescope. In: Proceedings of the 6th Artificial Intelligence Applications. Santa Barbara, CA, USA: IEEE, 1990. 184-190 [40] Beaumet G, Verfaillie G, Charmeau M C. Estimation of the minimal duration of an attitude change for an autonomous agile earth-observing satellite. In: Principles and Practice of Constraint Programming-CP 2007. Lecture Notes in Computer Science, vol. 4741. Berlin, Heidelberg: Springer, 2007. 3-17 [41] Beaumet G, Verfaillie G, Charmeau M C. Autonomous planning for an agile earth-observing satellite. In: Proceedings of the 9th International Symposium on Artificial Intelligence, Robotics and Automation in Space.Hollywood, USA: IEEE, 2008. [42] Beaumet G, Verfaillie G, Charmeau M C. Feasibility of autonomous decision making on board an agile earth-observing satellite. Computational Intelligence, 2011, 27(1):123-139 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=b57776de85ad47a77cc5f8f9aa172aa2 [43] Sa P F, Zhao M, Liu Y F. Study of algorithms of real-time scheduling with fault-tolerance in small satellite on-board computer systems. In: Proceedings of the 6th World Congress on Intelligent Control and Automation. Dalian, China: IEEE, 2006. 2949-2953 [44] Baek S W, Han S M, Cho K R, Lee D W, Yang J S, Bainum P M, et al. Development of a scheduling algorithm and GUI for autonomous satellite missions. Acta Astronautica, 2011, 68(7-8):1396-1402 doi: 10.1016/j.actaastro.2010.08.011 [45] 孙雅茹, 王凤阳, 韩月平, 刘泳.卫星自主运行任务调度问题的优化算法.计算机工程与设计, 2005, 26(2):461-464 doi: 10.3969/j.issn.1000-7024.2005.02.061Sun Ya-Ru, Wang Feng-Yang, Han Yue-Ping, Liu Yong. Optimization algorithm for solving autonomous operation mission scheduling problem of satellites. Computer Engineering & Design, 2005, 26(2):461-464 doi: 10.3969/j.issn.1000-7024.2005.02.061 [46] Kono Y, Pereira L M, Ferreira M. Strategies for implementation of an automated planning system. In: Proceedings of the SpaceOps 2010 Conference. Huntsville, Alabama: AIAA, 2010. [47] 田志新, 汤海涛, 王中果, 汪大宝, 曹京.基于星上动态指令调度的卫星使用效能提升技术.宇航学报, 2014, 35 (10):1105-1113 doi: 10.3873/j.issn.1000-1328.2014.10.001Tian Zhi-Xin, Tang Hai-Tao, Wang Zhong-Guo, Wang Da-Bao, Cao Jing. Satellite utility improvement technique based on dynamic on-board command scheduling. Journal of Astronautics, 2014, 35(10):1105-1113 doi: 10.3873/j.issn.1000-1328.2014.10.001 [48] Kim H, Chang Y K. Mission scheduling optimization of SAR satellite constellation for minimizing system response time. Aerospace Science & Technology, 2015, 40:17-32 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=94870ae2648cba239b6abe7ace45d0db [49] Herz A, Mignogna A. Collection planning for the OrbView-3 high resolution imagery satellite. In: Proceedings of the SpaceOps 2006 Conference. Rome, Italy: AIAA, 2006. [50] Smith B, Millar W, Dunphy J, Tung Y W, Nayak P, Gamble E, et al. Validation and verification of the remote agent for spacecraft autonomy. In: Proceedings of the Aerospace Conference. Snowmass at Aspen, CO, USA: IEEE, 1999. 449-468 [51] Muscettola N, Nayak P P, Pell B, Williams B C. Remote Agent: to boldly go where no AI system has gone before. Artificial Intelligence, 1998, 103(1-2): 5-47 [52] Chien S, Sherwood R, Tran D, Cichy B, Rabideau G, Castano R, et al. The EO-1 autonomous science agent. In: Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems. New York: IEEE, 2004. 420-427 [53] Rabideau G, Knight R, Chien S, Fukunaga A, Govindjee A. Iterative repair planning for spacecraft operations using the ASPEN system. In: Proceedings of the 5th International Symposium on Artificial Intelligence, Robotics and Automation in Space. Noordwijk, The Netherlands, 1999. [54] Chien S, Knight R, Stechert A, Sherwood R, Rabideau G. Using iterative repair to improve the responsiveness of planning and scheduling. In: Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems. Breckenridge, CO: AAAI, 2000. 300-307 [55] Chien S, Knight R, Rabideau G. An empirical evaluation of the effectiveness of local search for replanning. In: Local Search for Planning and Scheduling. Lecture Notes in Computer Science, vol. 2148. Berlin, Heidelberg: Springer, 2001. 79-94 [56] Verfaillie G, Pralet C, Lemaitre M. Constraint-based modeling of discrete event dynamic systems. Journal of Intelligent Manufacturing, 2010, 21(1):31-47 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=03a001a89ed9a63a7f68d42b568a4a83 [57] Pralet C, Verfaillie G. Using constraint networks on timelines to model and solve planning and scheduling problems. In: Proceedings of the 18th International Conference on Artificial Intelligence Planning and Scheduling. Sydney, Australia: AAAI, 2008. 272-279 [58] Lemaître M, Verfaillie G. Interaction between reactive and deliberative tasks for on-line decision-making. In: Proceedings of the ICAPS-07 Workshop on Planning and Plan Execution for Real world Systems, Providence. Rhode Island, USA, 2007. [59] 李菊芳, 贺仁杰, 姚锋.星地一体的敏捷卫星规划调度框架.见: 第二届高分辨率对地观测学术年会.北京: 中国宇航学会中科院电子学研究所, 2013. 1-14Li Ju-Fang, He Ren-Jie, Yao Feng. A Planning and Scheduling Framework for Agile Satellite Combining On-ground and On-board Decisions. In: Proceedings of the 2nd China High Resolution Earth Observation Conference. China, Beijing: IECAS, 2013. 1-14 [60] 邢立宁.面向新型遥感卫星的星上自主任务规划框架.见: 第三届高分辨率对地观测学术年会.北京: 中国科学院高分重大专项管理办公室, 2014.Xing Li-Ning. An Autonomous Mission Planning Framework for the New Remote Sensing Satellite. In: Proceedings of the 3rd China High Resolution Earth Observation Conference. China, Beijing: IECAS, 2014. [61] 李建军, 郭浩, 祝江汉.星地一体成像侦察任务规划组合求解方法.小型微型计算机系统, 2012, 33(1):159-164 doi: 10.3969/j.issn.1000-1220.2012.01.030Li Jian-Jun, Guo Hao, Zhu Jiang-Han. Research on a combinational solution on space-ground integration imaging reconnaissance task scheduling. Journal of Chinese Computer Systems, 2012, 33(1):159-164 doi: 10.3969/j.issn.1000-1220.2012.01.030 [62] 陈峰, 武小悦.天地测控资源一体化调度模型.宇航学报, 2010, 31 (5):1405-1412 doi: 10.3873/j.issn.1000-1328.2010.05.024Chen Feng, Wu Xiao-Yue. Space and ground TT&C resource integrated scheduling model. Journal of Astronautics, 2010, 31(5):1405-1412 doi: 10.3873/j.issn.1000-1328.2010.05.024 [63] Lenzen C, Wörle M T, Göttfert T, Mrowka F, Wickler M. Onboard planning and scheduling autonomy within the scope of the FireBird mission. In: Proceedings of the 13th International Conference on Space Operations, SpaceOps 2014. Pasadena, California, USA: AIAA, 2014. [64] Wörle M T, Lenzen C. Ground assisted onboard planning autonomy with VAMOS. In: Proceedings of the 8th International Workshop on Planning and Scheduling for Space (IWPSS-13). Moffett Field, CA, 2013. [65] Dang V D, Dash R K, Rogers A, Jennings N R. Overlapping coalition formation for efficient data fusion in multi-sensor networks. In: Proceedings of the National Conference on Artificial Intelligence. Boston, Massachusetts: AAAI Press, 2006. 635-640 [66] Goradia H J, Vidal J M. An equal excess negotiation algorithm for coalition formation. In: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems. Honolulu, Hawaii: ACM, 2007. Article No. 250 [67] Rahwan T, Ramchurn S D, Dang V D, Jennings N R. Near-optimal anytime coalition structure generation. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence. Hyderabad, India: Morgan Kaufmann Publishers Inc., 2007. 2365——2371 [68] Abdallah S, Lesser V. Organization-based cooperative coalition formation. In: Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology. Beijing, China: IEEE, 2004. 162-168 [69] Sims M, Goldman C V, Lesser V. Self-organization through bottom-up coalition formation. In: Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems. Melbourne, Australia: ACM, 2003. 867-874 [70] Globus A, Crawford J, Lohn J, Pryor A. A comparison of techniques for scheduling earth observing satellites. In: Proceedings of the 19th National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence. San Jose, California, USA: DBLP, 2004. 836-843 [71] Globus A, Crawford J, Lohn J, Pryor A. Scheduling earth observing satellites with evolutionary algorithms. In: Proceedings of the International Conference on Space Mission Challenges for Information Technology. Pasadena, CA, 2003. [72] Richards R A, Houlette R T, Mohammed J L. Distributed satellite constellation planning and scheduling. In: Proceedings of the 14th International Florida Artificial Intelligence Research Society Conference. AAAI Press, 2001. 68-72 [73] Bianchessi N, Righini G. Planning and scheduling algorithms for the COSMO-SkyMed constellation. Aerospace Science & Technology, 2008, 12(7):535-544 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=6c8e3a946f032266d6096c3220e6f516 [74] Dilkina B, Havens B. Agile satellite scheduling via permutation search with constraint propagation[Online], Available: http://www.cs.sfu.ca/CourseCentral/827/havens/papers/topic%2312(SatelliteScheduling)/SatelliteSched.pdf, 2005 [75] 贺川, 朱晓敏, 邱涤珊.面向应急成像观测任务的多星协同调度方法.系统工程与电子技术, 2012, 34(4):726-731 doi: 10.3969/j.issn.1001-506X.2012.04.16He Chuan, Zhu Xiao-Min, Qiu Di-Shan. Cooperative scheduling method of multi-satellites for imaging reconnaissance in emergency condition. Systems Engineering & Electronics, 2012, 34(4):726-731 doi: 10.3969/j.issn.1001-506X.2012.04.16 [76] 王沛.基于分支定价的多星多站集成调度方法研究[博士学位论文], 国防科学技术大学, 中国, 2011Wang Pei. Research on Branch-and-Price Based Multi-satellite Multi-station Integrated Scheduling Method[Ph.D. dissertation], National University of Defense Technology, China, 2011 [77] Wang M C, Dai G M, Vasile M. Heuristic scheduling algorithm oriented dynamic tasks for imaging satellites. Mathematical Problems in Engineering, 2014, 2014:Article ID 234928 [78] Li Y Q, Wang R X, Xu M Q. Rescheduling of observing spacecraft using fuzzy neural network and ant colony algorithm. Chinese Journal of Aeronautics, 2014, 27(3):678-687 doi: 10.1016/j.cja.2014.04.027 [79] 姜维, 庞秀丽, 郝会成.成像卫星协同任务规划模型与算法.系统工程与电子技术, 2013, 35(10):2093-2101 doi: 10.3969/j.issn.1001-506X.2013.10.13Jiang Wei, Pang Xiu-Li, Hao Hui-Cheng. Collaborative scheduling model and algorithm for imaging satellite network. Systems Engineering & Electronics, 2013, 35(10):2093-2101 doi: 10.3969/j.issn.1001-506X.2013.10.13 [80] Agogino A, HolmesParker C, Tumer K. Evolving distributed resource sharing for CubeSat constellations. In: Proceedings of the 14th Annual Conference on Genetic & Evolutionary Computation. Philadelphia, Pennsylvania, USA: ACM, 2012. 1015-1022 [81] Cheng S W, Chen J, Shen L C, Tao Y. ECNP-based method of distributed dynamic task allocation for multiple observation satellite planning. In: Proceedings of the 2nd International Conference on Advanced Computer Control. Shenyang, China: IEEE, 2010. 325-328 [82] Skobelev P O, Simonova E V, Zhilyaev A A, Travin V S. Application of multi-agent technology in the scheduling system of swarm of earth remote sensing satellites. Procedia Computer Science, 2017, 103:396-402 doi: 10.1016/j.procs.2017.01.127 [83] Mohammed J L. Mission planning for formation-flying satellite cluster. In: Proceedings of the 14th International Florida Artificial Intelligence Research Society Conference. Key West, Florida, USA: AAAI Press, 2001. 58-62 [84] Mohammed J L. SpaceCAPS: automated mission planning for the TechSat 21 formation-flying cluster experiment. In: Proceedings of the 15th International Florida Artificial Intelligence Research Society Conference. Pensacola Beach, Florida, USA: DBLP, 2002. 24-27 [85] Grasset-Bourdel R, Verfaillie G, Flipo A. PLANET: a planning and replanning tool for a constellation of agile earth-observing satellites. In: Proceedings of the 21st International Conference on Automated Planning and Scheduling. Freiburg, Germany: AAAI, 2011: 23. [86] Pralet C, Verfaillie G, Olive X, Rainjonneau S, Sebbag I. Planning for an ocean global surveillance mission. Methods & Findings in Experimental & Clinical Pharmacology, 2012, 13(7):499-503 http://jeannicod.ccsd.cnrs.fr/CNES/hal-01061393 [87] Wang P, Tan Y J. Joint scheduling of heterogeneous earth observing satellites for different stakeholders. In: Proceedings of the SpaceOps 2008 Conference. Heidelberg, Germany: AIAA, 2013. [88] Grasset-Bourdel R, Verfaillie G, Flipo A. Building a really executable plan for a constellation of agile earth observation satellites. In: International Workshop on Planning & Scheduling for Space, ESOC. Darmstadt, Germany, 2011. [89] De Florio S. Performances optimization of remote sensing satellite constellations: a heuristic method. In: International Workshop on Planning and Scheduling for Space. Baltimore, MD, USA, 2006. [90] Truszkowski W, Hallock H L, Rouff C, Karlin J, Rash J, Hinchey M, et al. Autonomous and Autonomic Systems:With Applications to NASA Intelligent Spacecraft Operations and Exploration Systems. London:Springer, 2009. [91] Zheng Z X, Guo J, Gill E. Multi-satellite onboard behaviour planning using adaptive genetic algorithm. In: Proceedings of the 67th International Astronautical Congress. Guadalajara, Mexico, 2016. [92] Qin J, Liu Y G, Mao X, McNair J. Deadline based resource balancing task allocation for clustered heterogeneous LEO small satellite network. In: Proceedings of the 2013 IEEE Military Communications Conference. San Diego, CA, USA: IEEE, 2013. 1825-1831 [93] Bonnet G, Tessier C. Collaboration among a satellite swarm. In: Proceedings of the 6th International Joint Conference on Autonomous Agents & Multiagent Systems. Honolulu, Hawaii, USA: ACM, 2007. Article No.54 [94] Damiani S, Verfaillie G, Charmeau M C. An earth watching satellite constellation: how to manage a team of watching agents with limited communications. In: Proceedings of the 4th International Joint Conference on Autonomous Agents & Multiagent Systems. The Netherlands: ACM, 2005. 455-462 [95] Bonnet G, Tessier C. Coordination despite constrained communications: a satellite constellation case. In: Proceedings of the 3rd National Conference on Control Architectures of Robots. Bourges, 2008. [96] Van Der Horst J. Market-based Task Allocation in Distributed Satellite Systems[Ph.D. dissertation], University of Southampton, UK, 2012 [97] Bonnet J. Multi-Criteria and Multi-Objective Dynamic Planning by Self-Adaptive Multi-Agent System, Application to Earth Observation Satellite Constellations[Ph.D. dissertation], Université de Toulouse, France, 2017 [98] 张正强.基于MAS的分布式成像卫星系统任务规划与控制问题研究[博士学位论文], 国防科学技术大学, 中国, 2006Zhang Zheng-Qiang. Research on Mission Planning and Control Problem for Distributed Imaging Satellite System Based on MAS[Ph.D. dissertation], National University of Defense Technology, China, 2006 [99] 高黎.对地观测分布式卫星系统任务协作问题研究[博士学位论文], 国防科学技术大学, 中国, 2007Gao Li. Research on Earth Observation Task Cooperation for Distributed Satellites System[Ph.D. dissertation], National University of Defense Technology, China, 2007 [100] 庞中华.高低轨对地观测卫星协同任务规划方法研究[硕士学位论文].哈尔滨工业大学, 2013.Pang Zhong-Hua. Research on Collaborative Mission Scheduling Methods of High-orbit and Low-orbit Earth Observation Satellite[Master thesis], Harbin Institute of Technology, China, 2013. [101] Lachiver J, Laherrere J, Sebbag I, Bataille N, et al. System feasibility of onboard clouds detection and observations scheduling. In: Proceedings of the 6th International Symposium on Artificial Intelligence, Robotics, and Automation for Space (i-SAIRAS-01). Montreal, Canada, 2001. [102] Khatib L, Frank J, Smith D, Morris R, Dungan J. Interleaved observation execution and rescheduling on earth observing systems. In: Proceedings of the 13th International Conference on Artificial Intelligence Planning and Scheduling Workshop on Plan Execution. Trento, Italy, 2003. [103] Morris R A, Dungan J, Frank J, Khatib L, Smith D E. An integrated approach to earth science observation scheduling. In: Proceedings of the 3rd NASA Earth Science Technology Conference (ESTC-03). University of Maryland, USA, 2003. [104] Das S, Knights D, Wu C, Truszkowski W. Distributed intelligent planning and scheduling (DIPS). In: Proceedings of the 1st International Conference on Multi-Agent Systems. San Francisco, California, USA: AAAI, 1995. [105] Das S, Wu C, Truszkowski W. Enhanced satellite constellation operations via distributed planning and scheduling. In: Proceeding of the 6th International Symposium on Artificial Intelligence and Robotics & Automation in Space: i-SAIRAS 2001. Canadian Space Agency, St-Hubert, Quebec, Canada, 2001. [106] Das S, Krikorian R, Truszkowski W. Distributed planning and scheduling for enhancing spacecraft autonomy. In: Proceedings of the 3rd Annual Conference on Autonomous Agents. Seattle, Washington, USA: ACM, 1999. 422-423 [107] Das S, Wu C, Truszkowski W. Distributed intelligent planning and scheduling for enhanced spacecraft autonomy. In: AAAI Technical Report SS-01-06. AAAI, 2018. 37-45 [108] Escorial D, Tourne I F, Reina F J, Gonzalo J, Garrido B. Fuego:a dedicated constllation of small satellites to detect and monitor forest fires. Acta Astronautica, 2003, 52(9-12):765-775 doi: 10.1016/S0094-5765(03)00052-3 [109] Tripp H, Palmer P. Stigmergy based behavioural coordination for satellite clusters. Acta Astronautica, 2010, 66(7-8): 1052-1071 [110] Cesta A, Ocon J, Rasconi R, Montero A M S. Simulating on-board autonomy in a multi-agent system with planning and scheduling. In: Scheduling and Planning Applications Workshop at International Conference on Automated Planning and Scheduling. Toronto, Canada, 2010. [111] Grey S. Distributed Agents for Autonomous Spacecraft [Ph. D. dissertation], The University of Glasgow, UK, 2013 -
下载:
![](data:image/svg+xml,<svg xmlns='http://www.w3.org/2000/svg' width='210' height='179'><foreignObject width='2000' height='100%'><div xmlns='http://www.w3.org/1999/xhtml' style='font-size:16px;font-family:Helvetica'><table>
<thead>
<tr>
<td class="table_top_border" align="center">算法类型</td><td class="table_top_border" align="center">算法名称</td>
<td class="table_top_border">应用场景/算法特性</td>
</tr>
</thead>
<tbody>
<tr>
<td class="table_top_border2" align="center" rowspan="2">精确算法</td>
<td class="table_top_border2" align="center">动态规划<sup>[<span class="xref"><a href="#b28" ref-type="bibr">28</a></span>]</sup></td>
<td class="table_top_border2">基于合成任务间时序特征, 将问题按照卫星的最大侧摆次数划分为多个阶段, 利用动态规划思想, 得到了问题的最优解.</td>
</tr>
<tr>
<td align="center">分支定价<sup>[<span class="xref"><a href="#b29" ref-type="bibr">29</a></span>]</sup></td>
<td>用期望模型和机会约束规划模型对卫星调度问题进行数学建模, 将分支定界与列生成混合起来求解该问题. </td>
</tr>
<tr>
<td align="center">
</td><td align="center">贪婪算法<sup>[<span class="xref"><a href="#b30" ref-type="bibr">30</a></span>]</sup></td>
<td>在卫星可见时间窗和任务时间窗的约束条件下, 满足最大化资源利用的目标.</td>
</tr>
<tr>
<td align="center">
</td><td align="center">禁忌搜索<sup>[<span class="xref"><a href="#b31" ref-type="bibr">31</a></span>]</sup></td>
<td>针对操作约束下的对地观测卫星任务选取与调度问题, 使用禁忌搜索寻找近似最优方案. </td>
</tr>
<tr>
<td align="center">
</td><td align="center">拉格朗日松弛和线性搜索<sup>[<span class="xref"><a href="#b32" ref-type="bibr">32</a></span>]</sup></td>
<td>将对地观测卫星的日常成像调度问题建模成整数规划问题, 结合拉格朗日松弛法和线性搜索法来求解此问题.</td>
</tr>
<tr>
<td align="center">
</td><td align="center">遗传算法<sup>[<span class="xref"><a href="#b33" ref-type="bibr">33</a></span>]</sup></td>
<td>结合电磁探测卫星的具体约束条件, 建立了观测任务和数据传输的坐标调度模型, 使用遗传算法求解.</td>
</tr>
<tr>
<td align="center">近似算法</td>
<td align="center">粒子群算法<sup>[<span class="xref"><a href="#b34" ref-type="bibr">34</a></span>]</sup></td>
<td>在粒子群算法中使用局部领域拓扑结构来避免过早收敛, 并引入分支定界法来提高局部搜索能力.</td>
</tr>
<tr>
<td align="center">
</td><td align="center">差分进化<sup>[<span class="xref"><a href="#b35" ref-type="bibr">35</a></span>-<span class="xref"><a href="#b36" ref-type="bibr">36</a></span>]</sup></td>
<td>为实现突变和交叉对进化个体进行实数编码, 用贪婪规则选择每代较优个体, 解码获得资源分配方案与任务执行时间序列.</td>
</tr>
<tr>
<td align="center">
</td><td align="center">蚁群算法<sup>[<span class="xref"><a href="#b37" ref-type="bibr">37</a></span>]</sup></td>
<td>应用均匀设计确定蚁群算法的组件, 设计出了高效求解敏捷卫星调度问题的蚁群算法. </td>
</tr>
<tr>
<td align="center">
</td><td align="center">蜂群算法<sup>[<span class="xref"><a href="#b38" ref-type="bibr">38</a></span>]</sup></td>
<td>采用人工蜂群算法对中继卫星调度问题进行求解, 对比发现蜂群算法优于其他群智能算法.</td>
</tr>
<tr>
<td class="table_bottom_border" align="center">
</td><td class="table_bottom_border" align="center">模拟退火<sup>[<span class="xref"><a href="#b3" ref-type="bibr">3</a></span>]</sup></td>
<td class="table_bottom_border">设计模拟退火诸多机制:自适应温度控制、基于禁忌表重访限制机制和领域结构的智能组合, 高效地完成了卫星观测调度问题.</td>
</tr>
</tbody>
</table></div></foreignObject></svg>)
