654 智能系统学报 第12卷 泛关注。当前，卫星任务规划的对象是整个卫星集 的目的。 合，规划的目的是安排整个卫星集合的动作，使得 我们拟对子问题1展开研究。但由于卫星异构 在满足卫星所有约束的前提下，能够最大化满足用 的特性，不同团队执行同一组对地观测任务的代价 户需求。主要的研究工作可以分为集中式规划和 通常不同。如何构建能够完成多组观测任务的最 分布式规划两个类别。 小卫星团队（团队中不存在冗余观测能力），且执行 集中式的任务规划方法[)]通常采用约束满足 代价最小，已经成为卫星任务规划领域出现的新而 问题模型】、图模型[)等对多星任务调度问题进行 亟待解决的问题。 统一建模，然后采用贪婪算法、启发式算法)以及 T.Okimoto等[16]处理巴黎火灾救援问题时，将 各种智能优化算法[6-)进行求解，处理的卫星均为 救援设备建模为Agent,根据火势大小，向各个火灾 同种类型。 点组织消防车团队进行救援，是一种面向任务的 而分布式任务规划研究则主要是将卫星建模 Agent团队构建思想。受此启发，我们拟对观测任 为具有自主性、协同性、社会性的Agent,.多颗卫星 务集合、卫星集群能力[可进行建模，研究面向任务 通过自主协商完成任务优化分配，目前多采用基于 的卫星Agent团队构建方法。设定卫星集群中的每 拍卖的协商协议[8)。例如，采用基于方案融合的合 颗卫星在执行每一个对地观测任务时，可以获得对 同网方法)，采用聚类降载与演化计算相结合的协 应的收益和代价，执行不同的任务，代价不同。因 同方法[，基于协同进化与迁移学习的协同方 此在胜任集合中所有任务的前提下，合理挑选卫 法[山]等。分布式卫星任务规划较集中式卫星任务 星，使卫星团队执行所有任务的总代价最小8]。 规划而言，有更大的灵活性，可以将不同类型的卫 1 问题描述 星建模为异构的卫星规划Agent,.从而能处理不同 种类卫星的任务规划问题，且可采用Agent并行协 面向任务的对地观测卫星团队构建问题就是 同方式提升规划效率。但随着卫星规模的增加，任 在已知系统的初始状态、可用资源、每颗卫星的负 务协同计算代价增长明显。 载情况的前提下，针对对地观测任务集合，基于卫 传统卫星任务规划问题中，卫星数量通常在几 星在执行任务时产生的代价从卫星集群中挑选出 颗到十几颗左右，当问题规模上升为数十颗乃至上 一组能胜任所有观测任务的卫星，组成卫星团队， 百颗卫星时，集中式规划方法会因为问题规模巨大 使得执行所有任务的总代价最小。 很难给出用户满意解，分布式规划方法也会因为协 1.1符号定义 同耗时太长很难在有效时间内给出问题可行解。 为了方便描述，首先给出相关符号定义，如表1 随着航天科技的飞速发展，逐渐出现了由多种 所示。 异构卫星组成的卫星集群)]，如用于木星大气层探 1.2目标函数 测的SMARA微型卫星群)、用于小行星探测的 面向任务的对地观测卫星团队构建问题的目 ANTS群卫星系统[14)、用于天文观测的OLFAR卫星 标是从卫星集群中找到一个能够胜任这些任务的 集群吲]等，这些卫星集群的规模都在几十颗到上百 卫星团队，并使团队的总代价最小，即当team∈ 颗之间。与传统的卫星系统相比，卫星集群的规模 TEAM时： 更大，能力更多，通常只需从集群中挑选一个子集 ieam.Cost=∑Cn(Say,task)→MIN (称为面向任务的卫星团队，简称卫星团队)，即可 团队的总代价是团队中所有卫星执行任务的 完成一组对地观测任务。 代价之和。 可见，卫星群任务规划在规划场景、规划目的、 卫星Sat,执行任务task的代价Csr(Sat:,task) 问题规模上均与传统的卫星任务规划方法存在较 可由SC:和TC计算得到： 大差别，传统的任务规划方法难以直接应用。 Csr(Sati,task;)=SC;x TC 基于上述分析，对卫星集群的任务规划可分解 SC,由卫星Sat:当前时刻执行任务情况决定。 为两个子问题：子问题1，根据任务集特点从整个卫 卫星的使用代价SC:与执行的任务数、被占用的时 星集群中筛选出一个能够胜任该任务集的卫星团 间窗数正相关： 队：子问题2，针对筛选出的卫星团队采用传统任务 SC:=a(Btasks,+TW_used,) 规划方法优化安排每一颗卫星的观测动作，从而达 在团队构建过程中，卫星使用代价随着承担任 到缩减任务规划中卫星资源规模，降低时间复杂度 务数增多，而不断增长。泛关注。 当前，卫星任务规划的对象是整个卫星集 合，规划的目的是安排整个卫星集合的动作，使得 在满足卫星所有约束的前提下，能够最大化满足用 户需求。 主要的研究工作可以分为集中式规划和 分布式规划两个类别。 集中式的任务规划方法［２］ 通常采用约束满足 问题模型［３］ 、图模型［４］ 等对多星任务调度问题进行 统一建模，然后采用贪婪算法、启发式算法［５］ 以及 各种智能优化算法［６－７］ 进行求解，处理的卫星均为 同种类型。 而分布式任务规划研究则主要是将卫星建模 为具有自主性、协同性、社会性的 Ａｇｅｎｔ，多颗卫星 通过自主协商完成任务优化分配，目前多采用基于 拍卖的协商协议［８］ 。 例如，采用基于方案融合的合 同网方法［９］ ，采用聚类降载与演化计算相结合的协 同方法［１０］ ， 基于协同进化与迁移学习的协同方 法［１１］等。 分布式卫星任务规划较集中式卫星任务 规划而言，有更大的灵活性，可以将不同类型的卫 星建模为异构的卫星规划 Ａｇｅｎｔ，从而能处理不同 种类卫星的任务规划问题，且可采用 Ａｇｅｎｔ 并行协 同方式提升规划效率。 但随着卫星规模的增加，任 务协同计算代价增长明显。 传统卫星任务规划问题中，卫星数量通常在几 颗到十几颗左右，当问题规模上升为数十颗乃至上 百颗卫星时，集中式规划方法会因为问题规模巨大 很难给出用户满意解，分布式规划方法也会因为协 同耗时太长很难在有效时间内给出问题可行解。 随着航天科技的飞速发展，逐渐出现了由多种 异构卫星组成的卫星集群［１２］ ，如用于木星大气层探 测的 ＳＭＡＲＡ 微型卫星群［１３］ 、用于小行星探测的 ＡＮＴＳ 群卫星系统［１４］ 、用于天文观测的 ＯＬＦＡＲ 卫星 集群［１５］等，这些卫星集群的规模都在几十颗到上百 颗之间。 与传统的卫星系统相比，卫星集群的规模 更大，能力更多，通常只需从集群中挑选一个子集 （称为面向任务的卫星团队，简称卫星团队），即可 完成一组对地观测任务。 可见，卫星群任务规划在规划场景、规划目的、 问题规模上均与传统的卫星任务规划方法存在较 大差别，传统的任务规划方法难以直接应用。 基于上述分析，对卫星集群的任务规划可分解 为两个子问题：子问题 １，根据任务集特点从整个卫 星集群中筛选出一个能够胜任该任务集的卫星团 队；子问题 ２，针对筛选出的卫星团队采用传统任务 规划方法优化安排每一颗卫星的观测动作，从而达 到缩减任务规划中卫星资源规模，降低时间复杂度 的目的。 我们拟对子问题 １ 展开研究。 但由于卫星异构 的特性，不同团队执行同一组对地观测任务的代价 通常不同。 如何构建能够完成多组观测任务的最 小卫星团队（团队中不存在冗余观测能力），且执行 代价最小，已经成为卫星任务规划领域出现的新而 亟待解决的问题。 Ｔ． Ｏｋｉｍｏｔｏ 等 ［１６］处理巴黎火灾救援问题时，将 救援设备建模为 Ａｇｅｎｔ，根据火势大小，向各个火灾 点组织消防车团队进行救援，是一种面向任务的 Ａｇｅｎｔ 团队构建思想。 受此启发，我们拟对观测任 务集合、卫星集群能力［１７］ 进行建模，研究面向任务 的卫星 Ａｇｅｎｔ 团队构建方法。 设定卫星集群中的每 颗卫星在执行每一个对地观测任务时，可以获得对 应的收益和代价，执行不同的任务，代价不同。 因 此在胜任集合中所有任务的前提下，合理挑选卫 星，使卫星团队执行所有任务的总代价最小［１８］ 。 １ 问题描述 面向任务的对地观测卫星团队构建问题就是 在已知系统的初始状态、可用资源、每颗卫星的负 载情况的前提下，针对对地观测任务集合，基于卫 星在执行任务时产生的代价从卫星集群中挑选出 一组能胜任所有观测任务的卫星，组成卫星团队， 使得执行所有任务的总代价最小。 １．１ 符号定义 为了方便描述，首先给出相关符号定义，如表 １ 所示。 １．２ 目标函数 面向任务的对地观测卫星团队构建问题的目 标是从卫星集群中找到一个能够胜任这些任务的 卫星团队，并使团队的总代价最小，即当 ｔｅａｍ ∈ ＴＥＡＭＭ 时： ｔｅａｍ．Ｃｏｓｔ ＝ ∑ Ｍ ｉ ＝ １ ＣＳＴ Ｓａｔ ｊ，ｔａｓｋｉ ( ) → ΜΙΝ 团队的总代价是团队中所有卫星执行任务的 代价之和。 卫星 Ｓａｔ ｉ 执行任务 ｔａｓｋｊ 的代价 ＣＳＴ（Ｓａｔ ｉ，ｔａｓｋｊ） 可由 ＳＣｉ 和 ＴＣｊ 计算得到： ＣＳＴ（Ｓａｔ ｉ，ｔａｓｋｊ） ＝ ＳＣｉ × ＴＣｊ ＳＣｉ 由卫星 Ｓａｔ ｉ 当前时刻执行任务情况决定。 卫星的使用代价 ＳＣｉ 与执行的任务数、被占用的时 间窗数正相关： ＳＣｉ ＝ α Ｂｔａｓｋｓｉ ＋ ＴＷ＿ｕｓｅｄｉ ( ) 在团队构建过程中，卫星使用代价随着承担任 务数增多，而不断增长。 ·６５４· 智 能 系 统 学 报 第 １２ 卷