敏捷对地观测卫星集群调度新进展

摘 要

本文介绍了敏捷卫星的工作机理，分析了单星和多星集群调度的关键难点，从系统、模型和算法的角度回顾了敏捷卫星集群调度的发展历程，并对未来的研究方向进行了展望。

关键字

敏捷卫星集群调度；智能优化方法；不确定性优化；自主调度

0 引言

光学对地观测卫星是通过搭载光学遥感器，获取地球表面的光学图像，以响应不同用户需求的一类卫星平台。光学遥感器包含可见光、红外、高光谱遥感器等，根据不同的应用需求，使用不同类型的载荷获取高分辨率、高质量的卫星图像。其中，光学对地观测卫星的应用最为广泛，因此本文主要研究光学对地观测卫星（为简化叙述，如无特殊说明，对地观测卫星均指代光学对地观测卫星）。

对地观测卫星由于具有覆盖范围广、观测时间长、不受空域国界约束等特点，在天气预报、灾害监测、自然资源勘探和军事侦察等领域发挥着举足轻重的作用。尤其在军事领域，利用空间资源获取敌方情报，帮助制定有效的作战计划，远程精确打击敌方战略目标，已经成为了一种全新的现代化作战样式。随着现代社会对空间信息的需求日益增多，如何利用有限的卫星资源，完成更多的观测任务，提高卫星任务规划的效能，是一个亟待解决的关键问题。

卫星任务规划是指在满足航天资源能力限制，以及不同任务观测需求的情况下，通过构建任务规划模型和设计相应算法，实现卫星、地面站等空间和地面资源的合理分配，制定对信息获取、处理、传输的调度方案，最终生成卫星对地观测计划、数传计划、测控计划和数据传输计划等。其中，对卫星成像任务调度问题是卫星任务规划中至关重要的一环，也是本文着重研究的对象。成像任务调度的求解质量和效率，直接影响任务规划系统的整体效能。对地观测卫星的成像任务调度问题，是给定一组不同收益值的观测目标，从中选出部分目标进行调度，生成成像调度方案，从而最大化观测收益，同时满足一系列调度约束。而多颗对地观测卫星的集群调度问题，不仅要考虑每颗卫星的调度收益和约束，也要考虑不同卫星的能力参数和特点，以及多颗卫星之间的协同工作模式和流程。

根据姿态机动能力和工作机理的不同，对地观测卫星可分为传统对地观测卫星和敏捷对地观测卫星两种。传统对地观测卫星仅具备侧摆能力，即卫星只有经过观测目标 ( 分布于卫星运行轨迹两侧 ) 上空时，才能执行观测任务，其机动能力和观测能力十分受限，因此亦被称为非敏卫星。而作为新一代的对地观测卫星，敏捷对地观测卫星具有三个自由度的机动能力，即侧摆、俯仰和偏航三个轴向，使得卫星能在经过目标正上方之前或之后进行观测。因此，卫星一次过境某观测目标，则对应一个可见时间窗口，卫星在可见时间窗口中的任一时刻均可执行观测任务。这里的观测任务，是指卫星对观测目标执行的一次观测活动。卫星机动能力和工作机理不同，决定了对不同类型对地观测卫星的任务调度算法及其求解难度不同。

图1分别展示了非敏卫星和敏捷卫星观测目标时的工作机理。由于非敏卫星只有在经过观测目标正上方时才可观测，观测目标的可见时间窗口与观测窗口相同，调度算法只需从所有候选观测目标集合里选出合适的调度目标子集，并且满足连续观测任务间的转换时间约束。所谓转换时间约束，是指任意两个连续观测任务之间，时间间隔必须不小于从前一个任务到后一个任务的完成姿态转换所需要的时间。由于非敏卫星观测任意一个任务的姿态角 ( 即观测时间 ) 是固定的，任意两个任务之间的观测时间也可预计算出来，即任务之间可达性和时序关系已知，因此解空间相对较小，求解并不复杂。而对敏捷卫星来说，观测目标的可见时间窗口要比观测窗口长得多，因此对其调度需要确定每个观测任务的具体观测开始时间，任务之间的可达性和时序关系未知，任务的执行顺序会影响调度的收益。此外，由于转换时间长短取决于姿态变换的角度变化量，该变化量是由两个连续观测任务的观测角度决定，而观测角度取决于观测任务的观测开始时间，因此转换时间具有时间依赖特性，任意两个观测任务之间的转换时间无法提前预知，任务的观测开始时间会影响解的可行性。由此可知，单颗敏捷卫星的调度问题相当复杂，时间依赖特性和可见时间窗约束需要求解算法的巧妙设计。

图 1 非敏卫星和敏捷卫星观测目标时的工作机理

与之相比，多颗敏捷卫星的集群调度具有更高的理论价值和应用价值，是未来敏捷卫星调度的研究重点。多星成像侦察具有单星无法比拟的优势：① 面对大面积区域监测、海洋移动目标跟踪等复杂任务时，在一段时间内单颗敏捷卫星所能实现的时空覆盖率十分有限，单纯依靠高效的调度算法也难以完成侦察任务，特别是跟踪移动目标这种对时效性要求较高的任务；② 单颗卫星携带的载荷种类十分有限，而某些大型复杂的任务则要求通过多颗不同载荷的卫星协同完成任务，从而提高任务的成功率；③ 多颗卫星集群调度的鲁棒性要优于单颗卫星。现实中很多不确定性因素影响着调度的成功率，如卫星故障、通讯链路失效、云层遮盖影响成像等，采用多颗卫星集群调度不仅可以提高调度方案的鲁棒性，降低观测失败的概率，还可以减少因调度失败而重规划所带来的资源浪费。

多敏捷卫星集群调度问题面临着严峻的挑战。一方面，敏捷卫星自身的工作特点（如时间依赖转换时间、可见时间窗约束），使单星调度问题本身具有较高复杂度，简单的贪婪构造算法或启发式策略难以得到高质量解；另一方面，多星调度往往意味着问题规模的提升，这就对调度算法的求解效率提出了很高要求。此外，卫星的集群调度研究，需要考虑多颗敏捷卫星之间的协同方式（如集中式、分布式）和工作流程。针对不同的协同方式，采用不同的集群调度方法，探究最合适的多星集群调度工作模式，是卫星调度领域的研究热点。

1 研究现状

1.1 敏捷卫星系统

随着空间科技的进步，敏捷卫星在最近 20年得到了大力发展，已经成为对地观测卫星的主流。美国于 1999 年发射的 IKONOS-2 卫星和2001 年发射的 Quick Bird 卫星，均具备了正视、前视、后视、侧视等观测能力，是敏捷卫星的早期雏形；2007 年发射的 WorldView-1 卫星，其敏捷机动能力得到较大提升。欧洲最为著名的敏捷卫星系统源自于 2003 法国航天局启动的PLEIADES 项目，该项目是由两颗完全相同的敏捷卫星 Pleiades-1 和 Pleiades-2 组成，每颗卫星都具有侧摆、俯仰和偏航三个自由度的机动能力，可实现全球大部分地区的覆盖和每日重访，快速响应客户对任何地区的高分辨率数据获取需求；西班牙于 2014 年发射的 DEIMOS-2迷你卫星，具备灵活机动的敏捷能力，可获取最高 1 m 分辨率的光学图像。国内，2008 年发射了 HJ 环境系列卫星群，该卫星群是由两颗敏捷光学卫星和 1 颗雷达卫星组成，主要用于大范围、全天候、全天时、动态的环境和灾害监测；SuperView 高景系列是由中国航天科技集团打造的高分辨率商业遥感卫星群，截止 2018 年为止，该系列已有四颗光学卫星发射升空，可实现在全球任何地方每日观测一次。

1.2 敏捷卫星调度模型

通常来说，敏捷卫星集群调度目标是最大化成像调度方案的收益，主要考虑的约束条件有可见时间窗口约束、转换时间约束、星上资源约束和任务唯一性约束。所谓任务唯一性约束，是指方案中每个观测目标最多只能观测一次。然而，根据实际工程设计、卫星能力参数及调度决策偏向的不同，敏捷卫星调度的问题模型会因观测目标类型、优化目标、约束条件和调度周期长短等因素的差别而不尽相同，这就使不同型号卫星、不同问题模型的求解算法之间难以比较，无法形成统一测试基准。

观测目标类型不同，敏捷卫星调度的问题模型也不同。通常来说，观测目标可分为点目标和区域目标。点目标是指目标面积相对较小，卫星一次过境即可完成拍摄任务的观测目标。而区域目标的待观测面积较大，需要拆分成多个矩形条带观测（条带宽度受载荷视场角限制），卫星需要多次过境才可能完成全部条带覆盖。不管是点目标，还是区域目标，其收益值都受到任务紧急程度、用户优先级大小的直接影响。除此之外，区域目标的收益与其关联条带的观测完成数呈现非线性递增的关系。这是因为从实际应用角度出发，观测完成条带数越多，拼接后图像信息量越大，边际收益越高。因此，在某些文献中，区域目标的观测收益往往看作成观测覆盖面积的凸函数。

模型假设和约束条件同样也会影响敏捷卫星调度问题模型，例如，转换时间的时间依赖特性在求解过程中难以处理。很多过往研究将转换时间设为固定值，忽略其时间依赖特性。这种处理方式虽然简化了调度模型，但牺牲了一定的解的质量。另外，某些研究认为，随着卫星硬件技术发展，星上固存资源不再成为限制其观测成像影响因素之一，因此固存约束可以被忽略掉。

多星集群调度模型多采用集中式架构和集中 - 分布式架构，目标是高效地完成用户的任务需求。集中式架构是指统筹考虑所有卫星对所有任务的可见时间窗资源，将多星调度看作是一个单星多圈调度，通过现有的优化方法如贪婪规则、启发式方法等直接进行调度。这种集中式架构最为常见，也是目前工程应用中比较普遍的集群调度工作方式。在此基础上，有学者提出了基于集中 - 分布式架构的任务分配 -资源调度双层规划模型。在该双层模型中，上层模型负责将任务分配至卫星，下层模型负责对每颗卫星调度已分配的任务，下层调度的结果通过一定机制反馈到上层分配模型，指导下一步的分配。通过分层规划能降低多星统一式调度的复杂程度，提高多星调度的整体收益，减少求解大规模任务调度所需的计算时间。

除了考虑不同的集群调度模型框架之外，也有学者采用多 Agent 系统方法。在多 Agent 方法中，每个 Agent 代表了一颗卫星。当用户提出需求时，每个Agent 采用特定成本代价计算函数计算投标值，从中选出最低者完成成像任务。其中，卫星的成本代价计算函数，是根据其自身当前可用资源和任务特性来计算。此外，可通过改进合同网协议的方式，优化卫星 Agent 之间通信方式，实现动态高效的任务分配。

1.3 敏捷卫星调度算法

敏捷卫星调度问题是一个典型的组合优化问题。一般来说，这类问题的算法可划分为精确算法与启发式算法。目前，现有的敏捷卫星调度求解算法集中在启发式算法上，对精确算法的研究较少，主要原因有以下两点：① 正如前文所述，基于不同工程设计、能力参数和决策偏好，涉及的问题模型会很不一样。而精确算法相对于启发式来说，通用性较差，针对某一问题模型设计的精确算法难以推广至其他模型上。② 相比于非敏卫星，敏捷卫星调度问题是一个更为复杂、解空间更大、维度更高的优化问题。一方面，其转换时间约束为非线性不等式，传统精确算法难以处理；另一方面，问题的复杂度限制了其精确算法的求解规模，无法在可接受时间内求得最优解，难以满足实际应用的需要。现有的敏捷卫星调度精确算法主要有基于深度搜索的分支限界算法和基于最大独立集的图论算法，但这些算法只能用于求解单圈调度问题。而适用范围更广的多圈调度问题仍未有相应的精确求解算法，只能通过商业求解器求解其约束规划模型、混合整数模型或其线性松弛模型来获得最优解或上界。然而这样的求解方式只适用于超小规模的算例，对规模大于 60 的算例束手无策。

由于具有较好的通用性、较高的求解效率，启发式算法被广泛应用于调度算法的研究和工程应用中。对于单圈调度问题，已提出的启发式方法有贪婪算法、局部搜索算法、禁忌搜索算法。多圈调度问题的启发式算法有禁忌搜索算法、遗传算法、模拟退火算法、差分进化算法等。需要注意的是，以上求解算法针对的问题模型没有考虑转换时间的时间依赖特性，而是把转换时间简化成了序列依赖的固定值。在最新研究中，有学者提出了一种自适应大邻域搜索算法来求解带时间依赖转换时间的调度模型。该算法的插入算子通过二分法快速匹配可行观测开始时间和转换时间，并融入了时间松弛量的机制，通过计算待插入位置相邻任务（局部）的延后与提前的时间松弛量，从而快速获知该插入位置的可行性。有学者在此基础上改进了该快速插入算子，基于整个调度任务序列计算出全局时间松弛量，并采用迭代局部搜索算法求解该问题，获得了更高的求解质量和效率。

多星集群调度方面，大多数的求解算法都采用了集中式架构，即统筹所有卫星资源和任务需求，采用调度算法统一地、一次性地对所有任务进行调度。此类算法有确定性构造算法、遗传算法、混合蚁群算等。在最新研究中，有学者在上述针对单星问题自适应大领域搜索算法基础上，提出了自适应任务分配的大邻域搜索算法。该算法参考了集中 - 分布式架构，将任务分配机制引入到大邻域搜索算法中。算法定义了多种分配算子，既考虑到卫星对任务的观测机会次数及任务间的冲突度，也考虑到卫星间负载均衡等问题。算法能自适应地选择更合适的算子来指导搜索。任务分配后，如果单星调度的结果不满意，则将部分任务重新通过分配算子分配到其余卫星。实验结果显示，自适应任务分配协同机制优于其他现有协同方法，在消耗较少的计算时间下获得了质量更好的解。

2 未来研究重点

2.1 不确定性调度

不确定性调度是未来敏捷卫星调度研究的必然发展方向，这是因为成像卫星在执行观测任务过程中会受到许多不可控因素的影响，其中最为常见的就是云层遮挡导致的无法拍摄到高质量卫星图片。据统计，我国约 60% 以上的光学卫星图像因为云层遮挡而无法生成有效的数据产品，而现有的天气预报尚不足以精准预测云层动向。云层遮挡不仅会影响图像质量，也会因为造成不必要的星上资源耗损，影响其余任务的执行。此外，云层覆盖的概率分布、天气预报准确程度、决策者的风险偏好等都会对调度结果产生影响。目前关于云层不确定性研究大多集中于非敏卫星的调度问题上，而且调度模型也是较为简单，缺乏对云层不确定性的建模，没有考虑决策者的风险决策偏好。在多星集群调度中，不确定性是非常重要的影响因素，因为多星集群调度往往要求卫星之间协同配合，以抵御和减少恶劣成像环境对整个星座系统带来的影响。如何将这些不确定性纳入多星调度算法，提高抵御不确定性风险的能力，优化解的鲁棒性是极具挑战性的难题。

2.2 卫星自主调度

卫星自主调度又称为在线式调度。与确定性、离线调度不同，自主调度是指假设任务动态到达，卫星根据自身决策辅助分析或历史经验判断，通过有限的星上计算资源，自动对任务进行分配和调度。由此可知，自主调度具有许多离线调度无法比拟的优势，比如对紧急突发任务的快速响应、不需要依赖于地面设施、对自身运行状态的智能管控。同时，自主调度也面临许多难以解决的问题。首先，星载计算机内存与运算能力有限，自主调度算法既要考虑求解质量，也要考虑算法的时间和空间复杂度；其次，自主调度往往要求多颗卫星自主协同提高卫星星座的整体效益，而卫星之间的信息交互受到通讯环境影响无法达到实时传递。针对前一个问题，以深度学习、强化学习等为代表的人工智能方法，通过在地面神经网络训练学习、星上快速求解的方式，有望解决星上计算资源不足问题。另外，多星调度可采用一颗主星、多颗辅星方式，由计算能力较强的主星完成任务调度，辅星配合执行任务。对于后一个问题，可通过优化星间链路模型、中继卫星调度等方式，提高卫星间的信息沟通效率，实现多颗卫星协同配合能力。

3 结束语

作为新一代对地观测卫星，敏捷成像卫星在过去 20 多年间取得了突破性进展，影响着国防军事、经济社会、环境保护等方方面面，为各行各业提供着非常重要的信息服务。在未来，面对层出不穷的应用需求和更精准化更快速调度要求，敏捷卫星集群调度理论和技术方法还有待进一步探索，集群调度模型需与成像卫星的未来发展战略相结合，有效地解决实际工程应用遇到的优化难题。集群调度算法既要紧贴学术前沿，与智能化、自动化相结合，也要满足实际调度场景的需求，又好又快地解决实际问题。

选自《中国人工智能学会通讯》

2021年第11卷第5期

群体智能及应用专辑