【智能系统】一种面向任务的对地观测卫星Agent团队构建方法

第12卷第5期 智能系统学报 Vol.12 No.5 2017年10月 CAAI Transactions on Intelligent Systems 0ct.2017 D0I:10.11992/is.201706017 网络出版地址：http:/kns.cmki.net/kcms/detail/23.1538.TP.20170831.1058.008.html 一种面向任务的对地观测卫星Agent团队构建方法 杨舒，陈浩，李军，景宁 (国防科技大学电子科学与工程学院，湖南长沙410073) 摘要：随着航天科技的飞速发展，逐渐出现了由多种异构卫星组成的卫星集群。相比于传统的卫星系统，卫星集 群具有规模大、平台多、载荷异构的特点，传统的卫星任务规划方法难以适用。针对卫星集群任务规划中的关键问 题一面向任务的卫星Aget团队构建问题，建立了数学模型，提出了基于分支限界的精确搜索算法，并对其时间复 杂度进行了分析。针对精确算法时间复杂度较高的缺点，引入了启发式剪枝机制，并按照任务集合排序策略的不同 设计了3种启发式卫星团队构建算法。最后，通过多组实验分析了卫星团队构建精确搜索算法与启发式剪枝搜索 算法的性能，验证了我们提出算法的有效性和实用性。 关键词：Aget团队构建：对地观测卫星集群：分支限界：启发式算法：剪枝策略：任务集合排序策略：卫星任务规划： 时间复杂度 中图分类号：TP391文献标志码：A文章编号：1673-4785(2017)05-0653-08 中文引用格式：杨舒，陈浩，李军，等.一种面向任务的对地观测卫星Aget团队构建方法[J].智能系统学报，2017,12(5)：653 -660. 英文引用格式：YANGShu,CHEN Hao,LIJun,etal.Agent team formation approach for task-oriented earth observation satellite [J].CAAI transactions on intelligent systems,2017,12(5):653-660. Agent team formation approach for task-oriented earth observation satellite YANG Shu,CHEN Hao,LI Jun,JING Ning (School of Electronic Science and Engineering,National University of Defense Technology,Changsha 410073,China) Abstract:With the ongoing development of aerospace science and technology,satellite clusters consisting of many kinds of heterogeneous satellites have gradually appeared.Compared with traditional satellite systems,satellite clusters have some particular characteristics,including large-scale heterogeneous satellite platforms and various loads.It is difficult to use traditional methods to program satellite tasks.To address the problem of the formation of an agent team for task-oriented satellites,which is one of the key problems of satellite cluster task scheduling,in this study,we built a mathematical model,designed a precise searching algorithm based on branch and bound techniques,and analyzed the associated time complexity.To overcome the high time complexity that characterizes this precise algorithm,we introduced a heuristic pruning mechanism and designed three heuristic algorithms for the formation of the satellite team according to different task sequencing strategies.Finally,we conducted a series of experiments to analyze the performances of the precise search algorithm developed for the satellite team and the heuristic pruning search algorithm and demonstrated the effectiveness and practicability of both the proposed algorithms. Keywords:Agent team formation;earth observing satellite cluster;branch and bound;heuristic algorithm;pruning tactics;task sequencing strategy;task scheduling on satellite;time complexity 对地观测卫星(earth observing satellite,EOS)信息，具有覆盖区域广、不受空域国界限制、不涉及 利用卫星遥感器对地球表面进行探测，以获取有关 人员安全等特点，在大地测绘、自然灾害检测、海洋 搜救、军事应用等领域产生了巨大效益山。 收稿日期：2017-06-07.网络出版日期：2017-08-31. 为了更好地利用宝贵的卫星资源，最大化地满 基金项目：国家自然科学基金项目(61101184：61174159). 通信作者：陈浩.E-mail:hchen(@nudt.cdu.cn 足用户需求，卫星任务规划得到了全世界学者的广

第 １２ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．５ ２０１７ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１７０６０１７ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０８３１．１０５８．００８．ｈｔｍｌ 一种面向任务的对地观测卫星 Ａｇｅｎｔ 团队构建方法 杨舒，陈浩，李军，景宁 （国防科技大学 电子科学与工程学院，湖南 长沙 ４１００７３） 摘 要：随着航天科技的飞速发展，逐渐出现了由多种异构卫星组成的卫星集群。 相比于传统的卫星系统，卫星集 群具有规模大、平台多、载荷异构的特点，传统的卫星任务规划方法难以适用。 针对卫星集群任务规划中的关键问 题———面向任务的卫星 Ａｇｅｎｔ 团队构建问题，建立了数学模型，提出了基于分支限界的精确搜索算法，并对其时间复 杂度进行了分析。 针对精确算法时间复杂度较高的缺点，引入了启发式剪枝机制，并按照任务集合排序策略的不同 设计了 ３ 种启发式卫星团队构建算法。 最后，通过多组实验分析了卫星团队构建精确搜索算法与启发式剪枝搜索 算法的性能，验证了我们提出算法的有效性和实用性。 关键词：Ａｇｅｎｔ 团队构建；对地观测卫星集群；分支限界；启发式算法；剪枝策略；任务集合排序策略；卫星任务规划； 时间复杂度 中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０５－０６５３－０８ 中文引用格式：杨舒，陈浩，李军，等．一种面向任务的对地观测卫星 Ａｇｅｎｔ 团队构建方法［ Ｊ］． 智能系统学报， ２０１７， １２（５）： ６５３ －６６０． 英文引用格式：ＹＡＮＧ Ｓｈｕ， ＣＨＥＮ Ｈａｏ， ＬＩ Ｊｕｎ， ｅｔ ａｌ． Ａｇｅｎｔ ｔｅａｍ ｆｏｒｍａｔｉｏｎ ａｐｐｒｏａｃｈ ｆｏｒ ｔａｓｋ⁃ｏｒｉｅｎｔｅｄ ｅａｒｔｈ ｏｂｓｅｒｖａｔｉｏｎ ｓａｔｅｌｌｉｔｅ ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（５）： ６５３－６６０． Ａｇｅｎｔ ｔｅａｍ ｆｏｒｍａｔｉｏｎ ａｐｐｒｏａｃｈ ｆｏｒ ｔａｓｋ⁃ｏｒｉｅｎｔｅｄ ｅａｒｔｈ ｏｂｓｅｒｖａｔｉｏｎ ｓａｔｅｌｌｉｔｅ ＹＡＮＧ Ｓｈｕ， ＣＨＥＮ Ｈａｏ， ＬＩ Ｊｕｎ， ＪＩＮＧ Ｎｉｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ， Ｃｈａｎｇｓｈａ ４１００７３， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｉｔｈ ｔｈｅ ｏｎｇｏｉｎｇ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ａｅｒｏｓｐａｃｅ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ， ｓａｔｅｌｌｉｔｅ ｃｌｕｓｔｅｒｓ ｃｏｎｓｉｓｔｉｎｇ ｏｆ ｍａｎｙ ｋｉｎｄｓ ｏｆ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｓａｔｅｌｌｉｔｅｓ ｈａｖｅ ｇｒａｄｕａｌｌｙ ａｐｐｅａｒｅｄ． Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｒａｄｉｔｉｏｎａｌ ｓａｔｅｌｌｉｔｅ ｓｙｓｔｅｍｓ， ｓａｔｅｌｌｉｔｅ ｃｌｕｓｔｅｒｓ ｈａｖｅ ｓｏｍｅ ｐａｒｔｉｃｕｌａｒ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ， ｉｎｃｌｕｄｉｎｇ ｌａｒｇｅ⁃ｓｃａｌｅ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｓａｔｅｌｌｉｔｅ ｐｌａｔｆｏｒｍｓ ａｎｄ ｖａｒｉｏｕｓ ｌｏａｄｓ． Ｉｔ ｉｓ ｄｉｆｆｉｃｕｌｔ ｔｏ ｕｓｅ ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄｓ ｔｏ ｐｒｏｇｒａｍ ｓａｔｅｌｌｉｔｅ ｔａｓｋｓ． Ｔｏ ａｄｄｒｅｓｓ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｔｈｅ ｆｏｒｍａｔｉｏｎ ｏｆ ａｎ ａｇｅｎｔ ｔｅａｍ ｆｏｒ ｔａｓｋ⁃ｏｒｉｅｎｔｅｄ ｓａｔｅｌｌｉｔｅｓ， ｗｈｉｃｈ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｋｅｙ ｐｒｏｂｌｅｍｓ ｏｆ ｓａｔｅｌｌｉｔｅ ｃｌｕｓｔｅｒ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ， ｉｎ ｔｈｉｓ ｓｔｕｄｙ， ｗｅ ｂｕｉｌｔ ａ ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌ， ｄｅｓｉｇｎｅｄ ａ ｐｒｅｃｉｓｅ ｓｅａｒｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｂｒａｎｃｈ ａｎｄ ｂｏｕｎｄ ｔｅｃｈｎｉｑｕｅｓ， ａｎｄ ａｎａｌｙｚｅｄ ｔｈｅ ａｓｓｏｃｉａｔｅｄ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ． Ｔｏ ｏｖｅｒｃｏｍｅ ｔｈｅ ｈｉｇｈ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｔｈａｔ ｃｈａｒａｃｔｅｒｉｚｅｓ ｔｈｉｓ ｐｒｅｃｉｓｅ ａｌｇｏｒｉｔｈｍ， ｗｅ ｉｎｔｒｏｄｕｃｅｄ ａ ｈｅｕｒｉｓｔｉｃ ｐｒｕｎｉｎｇ ｍｅｃｈａｎｉｓｍ ａｎｄ ｄｅｓｉｇｎｅｄ ｔｈｒｅｅ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｓａｔｅｌｌｉｔｅ ｔｅａｍ ａｃｃｏｒｄｉｎｇ ｔｏ ｄｉｆｆｅｒｅｎｔ ｔａｓｋ ｓｅｑｕｅｎｃｉｎｇ ｓｔｒａｔｅｇｉｅｓ． Ｆｉｎａｌｌｙ， ｗｅ ｃｏｎｄｕｃｔｅｄ ａ ｓｅｒｉｅｓ ｏｆ ｅｘｐｅｒｉｍｅｎｔｓ ｔｏ ａｎａｌｙｚｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｔｈｅ ｐｒｅｃｉｓｅ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｄｅｖｅｌｏｐｅｄ ｆｏｒ ｔｈｅ ｓａｔｅｌｌｉｔｅ ｔｅａｍ ａｎｄ ｔｈｅ ｈｅｕｒｉｓｔｉｃ ｐｒｕｎｉｎｇ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ａｎｄ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ａｎｄ ｐｒａｃｔｉｃａｂｉｌｉｔｙ ｏｆ ｂｏｔｈ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍｓ． Ｋｅｙｗｏｒｄｓ：Ａｇｅｎｔ ｔｅａｍ ｆｏｒｍａｔｉｏｎ； ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅ ｃｌｕｓｔｅｒ； ｂｒａｎｃｈ ａｎｄ ｂｏｕｎｄ； ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ； ｐｒｕｎｉｎｇ ｔａｃｔｉｃｓ； ｔａｓｋ ｓｅｑｕｅｎｃｉｎｇ ｓｔｒａｔｅｇｙ； ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｏｎ ｓａｔｅｌｌｉｔｅ； ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ 收稿日期：２０１７－０６－０７． 网络出版日期：２０１７－０８－３１． 基金项目：国家自然科学基金项目（６１１０１１８４； ６１１７４１５９）． 通信作者：陈浩． Ｅ⁃ｍａｉｌ：ｈｃｈｅｎ＠ ｎｕｄｔ．ｅｄｕ．ｃｎ． 对地观测卫星（ ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅ， ＥＯＳ） 利用卫星遥感器对地球表面进行探测，以获取有关 信息，具有覆盖区域广、不受空域国界限制、不涉及 人员安全等特点，在大地测绘、自然灾害检测、海洋 搜救、军事应用等领域产生了巨大效益［１］ 。 为了更好地利用宝贵的卫星资源，最大化地满 足用户需求，卫星任务规划得到了全世界学者的广

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,) 规划方法优化安排每一颗卫星的观测动作，从而达 在团队构建过程中，卫星使用代价随着承担任 到缩减任务规划中卫星资源规模，降低时间复杂度 务数增多，而不断增长

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

第5期 杨舒，等：一种面向任务的对地观测卫星Aget团队构建方法 ·655. 表1符号定义 Table 1 Symbol definitions 符号 定义 TaskSet={task,i≤M} 对地观测任务集合，共有M个任务 SatSet={Sat,li≤Nl 卫星集合，包含N个卫星的卫星集群 观测任务ak,和TD,表示任务的唯一编号：O,表示观测目标： 专和表示任务的规划起始时间和结束时间：S表示任务对载荷 task;=(TID,O,S,TC,TR,TRC) 类型的要求：TC,表示完成该任务的代价：TR,表示任务的优先级： TRC:表示任务的性价比，TRC=TR,/TC SD,表示卫星Sat,的唯一编号，TW,表示卫星可用的时间窗资源， TW_used,表示卫星上已经被占用的时间窗集合， Sat (SID,TW,TW_used,SC,BTasks,RES) SC,表示Sat,的使用代价，BTasks,表示卫星在团队构建中承担的 任务集合，RES,是卫星的约束条件 卫星Sat的约束条件，△T。表示两次观测活动的最短时间间隔， RES:=(△T,△T,△T) △T.是单圈最长观测时间，△T,是单天最长观测时间 TEAM,1≤i≤M 能够胜任task,到task,的团队集合 w是一条时间窗数据，wD是时间窗的唯一编号， w=(twlD,T",Tg,S,Sat,0,Cir"),tw∈TW,1≤i≤N T和是观测起止时间，S是观测时使用的载荷类型， O,是观测目标，Ci"表示轨道圈号 0Set={0,l1≤i≤k} 观测目标集合 team表示团队，Cost是团队卫星执行ask,到task,的总代价， team =(Cost,StoTSet),team E TEAM StoTSet任务与执行该任务卫星的集合 ST =(Sat,task,),ST E StoTSet 团队中每一个任务与对应执行任务的卫星 1.3约束模型 twn∈TWo,∑(T-T)≥△T 卫星Sat,能够执行任务task,的条件：在卫星拥 式中TW表示TW中所有时间窗起始时间在第 有的时间资源TW:中，找到一组观测时间窗 Q天内的时间窗集合。 TWtasks,胜任Btasks,和task,且与卫星上已经被占 用的时间窗集合TW_used,不产生冲突。考虑卫星 2基于分枝限界的卫星任务团队构建 在执行任务时，受星上电源容量、载荷硬件特性、轨 算法 道参数等限制，将一个时间窗看作一次观测活动， 由上述模型可知，该问题是一个典型的组合优 对TWk和TW_used:组成的时间窗集合TWa进行 化问题，我们拟采用树构建与搜索方法，以初始的 以下约束检测，TW中的TW按照t,排序。 1)两次观测活动不能同时进行。卫星一次只 空团队team。作为根节点，以完成任务为条件向下 能进行一个观测活动，即 分支，形成新的团队，遍历完所有任务，可建构一颗 twm∈TWa,Tm1-Tw≥0 广义的搜索树。 2)两次观测活动最短时间间隔。卫星关机后 算法1TFCA 需要一段时间才能重新开机，即 功能基于分枝限界思想的团队构建算法的 twm∈TWa,Ta1-Tm≥△Td 主算法； 3)单圈最长观测时间约束。卫星单圈累计观 输入TaskSet,SatSet,初始的空团队teamo; 测时间要小于单圈最长开机时间，即 输出最优团队team。 Htw.eTw,∑(T-T)≥△T 1)Begin 式中TW表示TWa中所有圈号为P的时间窗。 2)set team=☑，team=teamo 4)单天最长观测时间约束。卫星单天累计观 3)TFOfEachTask(1,team,team) 测时间限制要小于单天最长观测时间，即 4)Return team

表 １ 符号定义 Ｔａｂｌｅ １ Ｓｙｍｂｏｌ ｄｅｆｉｎｉｔｉｏｎｓ 符号 定义 ＴａｓｋＳｅｔ ＝ ｛ｔａｓｋｉ ｉ ≤ Ｍ｝ 对地观测任务集合，共有 Ｍ 个任务 ＳａｔＳｅｔ ＝ ｛Ｓａｔ ｉ ｉ ≤ Ｎ｝ 卫星集合，包含 Ｎ 个卫星的卫星集群 ｔａｓｋｉ ＝ （ＴＩＤｉ，Ｏｋ，ｔ ｉ ｓ，ｔ ｉ ｅ，Ｓ，ＴＣｉ，ＴＲｉ，ＴＲＣｉ） 观测任务 ｔａｓｋｉ和 ＴＩＤｉ表示任务的唯一编号；Ｏｋ表示观测目标； ｔ ｉ ｓ 和 ｔ ｉ ｅ 表示任务的规划起始时间和结束时间；Ｓ 表示任务对载荷 类型的要求；ＴＣｉ表示完成该任务的代价；ＴＲｉ表示任务的优先级； ＴＲＣｉ表示任务的性价比，ＴＲＣｉ ＝ ＴＲｉ ／ ＴＣｉ Ｓａｔ ｉ ＝ ＳＩＤｉ，ＴＷｉ，ＴＷ＿ ｕｓｅｄｉ，ＳＣｉ，ＢＴａｓｋｓｉ，ＲＥＳｉ ( ) ＳＩＤｉ表示卫星 Ｓａｔ ｉ的唯一编号，ＴＷｉ表示卫星可用的时间窗资源， ＴＷ＿ｕｓｅｄｉ表示卫星上已经被占用的时间窗集合， ＳＣｉ表示 Ｓａｔ ｉ的使用代价，ＢＴａｓｋｓｉ表示卫星在团队构建中承担的 任务集合，ＲＥＳｉ是卫星的约束条件 ＲＥＳｉ ＝ （ΔＴ ｉ ｓｄ ，ΔＴ ｉ ｃｉｒ，ΔＴ ｉ ｄａｙ） 卫星 Ｓａｔ ｉ的约束条件， ΔＴ ｉ ｓｄ 表示两次观测活动的最短时间间隔， ΔＴ ｉ ｃｉｒ 是单圈最长观测时间， ΔＴ ｉ ｄａｙ 是单天最长观测时间 ＴＥＡＭｉ，１ ≤ ｉ ≤ Ｍ 能够胜任 ｔａｓｋ１ 到 ｔａｓｋｉ 的团队集合 ｔｗ ＝ （ｔｗＩＤ，Ｔ ｔｗ ｓ ，Ｔ ｔｗ ｅ ，Ｓ，Ｓａｔ ｉ，Ｏｋ，Ｃｉｒ ｔｗ ），ｔｗ ∈ ＴＷｉ，１ ≤ ｉ ≤ Ｎ ｔｗ 是一条时间窗数据，ｔｗＩＤ 是时间窗的唯一编号， Ｔ ｔｗ ｓ 和 Ｔ ｔｗ ｅ 是观测起止时间，Ｓ 是观测时使用的载荷类型， Ｏｋ是观测目标，Ｃｉｒ ｔｗ表示轨道圈号 ＯＳｅｔ ＝ ｛Ｏｉ １ ≤ ｉ ≤ ｋ｝ 观测目标集合 ｔｅａｍ ＝ （Ｃｏｓｔ，ＳｔｏＴＳｅｔ） ， ｔｅａｍ ∈ ＴＥＡＭｉ ｔｅａｍ 表示团队，Ｃｏｓｔ 是团队卫星执行 ｔａｓｋ１ 到 ｔａｓｋｉ的总代价， ＳｔｏＴＳｅｔ 任务与执行该任务卫星的集合 ＳＴ ＝ （Ｓａｔ ｉ，ｔａｓｋｊ），ＳＴ ∈ ＳｔｏＴＳｅｔ 团队中每一个任务与对应执行任务的卫星 １．３ 约束模型 卫星 Ｓａｔ ｉ 能够执行任务 ｔａｓｋｊ 的条件：在卫星拥 有的 时 间 资 源 ＴＷｉ 中， 找 到 一 组 观 测 时 间 窗 ＴＷｔａｓｋｓ，胜任 Ｂｔａｓｋｓｉ 和 ｔａｓｋｊ，且与卫星上已经被占 用的时间窗集合 ＴＷ＿ｕｓｅｄｉ 不产生冲突。 考虑卫星 在执行任务时，受星上电源容量、载荷硬件特性、轨 道参数等限制，将一个时间窗看作一次观测活动， 对 ＴＷｔａｓｋｓ和 ＴＷ＿ｕｓｅｄｉ 组成的时间窗集合 ＴＷｄｅｔ进行 以下约束检测，ＴＷｄｅｔ中的 ＴＷ 按照 ｔ ｓ排序。 １）两次观测活动不能同时进行。 卫星一次只 能进行一个观测活动，即 ∀ ｔｗｍ ∈ ＴＷｄｅｔ，Ｔ ｔｗｍ＋１ ｓ － Ｔ ｔｗｍ ｅ ≥ ０ ２）两次观测活动最短时间间隔。 卫星关机后 需要一段时间才能重新开机，即 ∀ ｔｗｍ ∈ ＴＷｄｅｔ，Ｔ ｔｗｍ＋１ ｓ － Ｔ ｔｗｍ ｅ ≥ ΔＴ ｉ ｓｄ ３）单圈最长观测时间约束。 卫星单圈累计观 测时间要小于单圈最长开机时间，即 ∀ ｔｗｍ ∈ ＴＷｃｉｒＰ ，∑ Ｔ ｔｗｍ ｅ － Ｔ ｔｗｍ ｓ ( ) ≥ ΔＴ ｉ ｃｉｒ 式中 ＴＷｃｉｒＰ表示 ＴＷｄｅｔ中所有圈号为 Ｐ 的时间窗。 ４）单天最长观测时间约束。 卫星单天累计观 测时间限制要小于单天最长观测时间，即 ∀ ｔｗｍ ∈ ＴＷｄａｙＱ，∑ Ｔ ｔｗｍ ｅ － Ｔ ｔｗｍ ｓ ( ) ≥ ΔＴ ｉ ｄａｙ 式中 ＴＷｄａｙＱ表示 ＴＷｄｅｔ中所有时间窗起始时间在第 Ｑ 天内的时间窗集合。 ２ 基于分枝限界的卫星任务团队构建 算法 由上述模型可知，该问题是一个典型的组合优 化问题，我们拟采用树构建与搜索方法，以初始的 空团队 ｔｅａｍ０ 作为根节点，以完成任务为条件向下 分支，形成新的团队，遍历完所有任务，可建构一颗 广义的搜索树。 算法 １ ＴＦＣＡ 功能 基于分枝限界思想的团队构建算法的 主算法； 输入 ＴａｓｋＳｅｔ， ＳａｔＳｅｔ， 初始的空团队 ｔｅａｍ０ ； 输出 最优团队 ｔｅａｍ ｂｅｓｔ Ｍ 。 １） Ｂｅｇｉｎ ２） ｓｅｔ ｔｅａｍ ｂｅｓｔ Ｍ ＝ ⌀，ｔｅａｍ ＝ ｔｅａｍ０ ３） ＴＦＯｆＥａｃｈＴａｓｋ（１，ｔｅａｍ，ｔｅａｍ ｂｅｓｔ Ｍ ） ４） Ｒｅｔｕｒｎ ｔｅａｍ ｂｅｓｔ Ｍ 第 ５ 期 杨舒，等：一种面向任务的对地观测卫星 Ａｇｅｎｔ 团队构建方法 ·６５５·

·656· 智能系统学报 第12卷 5)End 队，首先将最优团队teamy置为空，语句3)是以初 我们采用深度优先策略进行树搜索，以当前搜 始团队team。为根节点的迭代搜索。 索到的能够胜任任务集合中所有任务的最优团队 算法2从第m个任务开始搜索构建团队的迭 team的代价作为上界，根据分支限界法对树进行 代算法，语句2)~5)表示该分支的team构建完成， 剪枝，即对于当前正在构建的卫星任务团队 如果team的代价小于team的代价或者team为 Curteam,如果： 空，则更新team为最佳团队并结束该分支搜索。语 Curteam.Cost≥team·Cost 句7)~8)为基于分枝限界思想的剪枝过程，当team 则减去Curteam这个节点向下的所有分枝。 还不能胜任所有的任务，而其代价已经大于等于 基于这种搜索剪枝策略，提出了基于分枝限界 team的代价，则结束该分支搜索。语句9)表示在 思想的团队构建算法(team formation complete 当前team的情况下，完成task.产生的所有方案存 algorithm based-on a branch and bound techniques, 入teamSet。语句l0)~l2)对teamSet中的每个team TFCA),伪代码如算法1、2、3所示。 进入下一任务的搜索。 算法2 TFOfEachTask 算法3寻找在当前team下，能完成task.的所 功能从第m个任务开始搜索构建团队的迭 有团队的迭代算法。在当前team的情况，依次判断 代算法。 每颗卫星Sat,能否完成task,如果能完成，则生成 输入m,team,team; 新团队team1,并将该team,加入teamSet。 输出目标找到的最优团队team。 由算法的迭代过程可以看出，如果针对M个任 1)Begin 务，在N个卫星中构建团队，在最坏的情况下即每 2)if(m>M) 颗卫星都有能力执行所有的任务，而且没有任何剪 3)if(team.CostN) 首先，给出剪枝策略。设team1,team2∈ 3)Return TEAM,如果 4)else if(Satn能完成task) team1.Cost≥1+ teamz.Cost 5)teaml Update(team) 6)teamSet =teamSetU teaml 0<e<1记为team,<team2,则剪去team,这 7)solve(n+1,team,teamSet,m) 个团队所在的结点。其中，i是TEAM中的每个团 8)end if 队完成的任务个数，ε根据卫星初始状态调整，尽量 9)End 为团队挑选承担任务数少的卫星。 算法1是基于分枝限界思想的团队构建算法的 基于这种剪枝策略，提出了启发式团队构建算 主算法，采用深度优先的搜索方式遍历所有的团 heuristic team formation algorithm based-on a

５） Ｅｎｄ 我们采用深度优先策略进行树搜索，以当前搜 索到的能够胜任任务集合中所有任务的最优团队 ｔｅａｍ ｂｅｓｔ Ｍ 的代价作为上界，根据分支限界法对树进行 剪枝， 即 对 于 当 前 正 在 构 建 的 卫 星 任 务 团 队 Ｃｕｒｔｅａｍ，如果： Ｃｕｒｔｅａｍ．Ｃｏｓｔ ≥ ｔｅａｍ ｂｅｓｔ Ｍ ·Ｃｏｓｔ 则减去 Ｃｕｒｔｅａｍ 这个节点向下的所有分枝。 基于这种搜索剪枝策略，提出了基于分枝限界 思想 的 团 队 构 建 算 法 （ ｔｅａｍ ｆｏｒｍａｔｉｏｎ ｃｏｍｐｌｅｔｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ⁃ｏｎ ａ ｂｒａｎｃｈ ａｎｄ ｂｏｕｎｄ ｔｅｃｈｎｉｑｕｅｓ， ＴＦＣＡ），伪代码如算法 １、２、３ 所示。 算法 ２ ＴＦＯｆＥａｃｈＴａｓｋ 功能 从第 ｍ 个任务开始搜索构建团队的迭 代算法。 输入 ｍ， ｔｅａｍ， ｔｅａｍ ｂｅｓｔ Ｍ ； 输出 目标找到的最优团队 ｔｅａｍ ｂｅｓｔ Ｍ 。 １）Ｂｅｇｉｎ ２）ｉｆ（ｍ＞Ｍ） ３） ｉｆ（ｔｅａｍ．Ｃｏｓｔ＜ ｔｅａｍ ｂｅｓｔ Ｍ ．Ｃｏｓｔ ｜ ｜ ｔｅａｍ ｂｅｓｔ Ｍ ＝ ∅ ４） ｔｅａｍ ｂｅｓｔ Ｍ ＝ ｔｅａｍ ５）Ｒｅｔｕｒｎ ６）ｅｌｓｅ ｉｆ（ ｔｅａｍ． Ｃｏｓｔ ＞ ｔｅａｍ ｂｅｓｔ Ｍ ．Ｃｏｓｔ＆＆ｔｅａｍ ｂｅｓｔ Ｍ ＝ ∅） ７）Ｒｅｔｕｒｎ ８）ｅｎｄ ｉｆ ９）ｓｏｌｖｅ（１，ｔｅａｍ，ｔｅａｍＳｅｔ，ｍ） １０）ｆｏｒ ｅａｃｈ ｔｅａｍ ｉｎ ｔｅａｍＳｅｔ １１）ＴＦＯｆＥａｃｈＴａｓｋ（ｍ＋１ ，ｔｅａｍ ， ｔｅａｍ ｂｅｓｔ Ｍ ） １２）ｅｎｄ ｆｏｒ １３）Ｅｎｄ 算法 ３ ｓｏｌｖｅ 功能 寻找 ｔｅａｍ 向下能完成 ｔａｓｋｍ的团队的迭 代算法； 输入 ｎ， ｔｅａｍ， ｔｅａｍＳｅｔ， ｍ； 输出 当前 ｔｅａｍ 下能完成 ｔａｓｋｍ 的团队集合 ｔｅａｍＳｅｔ。 １）Ｂｅｇｉｎ ２）ｉｆ（ｎ＞Ｎ） ３）Ｒｅｔｕｒｎ ４）ｅｌｓｅ ｉｆ（Ｓａｔ ｎ能完成 ｔａｓｋｍ ） ５）ｔｅａｍ１ ＝Ｕｐｄａｔｅ（ｔｅａｍ） ６）ｔｅａｍＳｅｔ ＝ ｔｅａｍＳｅｔ∪｛ｔｅａｍ１｝ ７）ｓｏｌｖｅ（ｎ＋１，ｔｅａｍ，ｔｅａｍＳｅｔ，ｍ） ８）ｅｎｄ ｉｆ ９）Ｅｎｄ 算法 １ 是基于分枝限界思想的团队构建算法的 主算法，采用深度优先的搜索方式遍历所有的团 队，首先将最优团队 ｔｅａｍ ｂｅｓｔ Ｍ 置为空，语句 ３）是以初 始团队 ｔｅａｍ０ 为根节点的迭代搜索。 算法 ２ 从第 ｍ 个任务开始搜索构建团队的迭 代算法，语句 ２） ～ ５）表示该分支的 ｔｅａｍ 构建完成， 如果 ｔｅａｍ 的代价小于 ｔｅａｍ ｂｅｓｔ Ｍ 的代价或者 ｔｅａｍ ｂｅｓｔ Ｍ 为 空，则更新 ｔｅａｍ 为最佳团队并结束该分支搜索。 语 句 ７） ～８）为基于分枝限界思想的剪枝过程，当 ｔｅａｍ 还不能胜任所有的任务，而其代价已经大于等于 ｔｅａｍ ｂｅｓｔ Ｍ 的代价，则结束该分支搜索。 语句 ９）表示在 当前 ｔｅａｍ 的情况下，完成 ｔａｓｋｍ产生的所有方案存 入 ｔｅａｍＳｅｔ。 语句 １０） ～１２）对 ｔｅａｍＳｅｔ 中的每个 ｔｅａｍ 进入下一任务的搜索。 算法 ３ 寻找在当前 ｔｅａｍ 下，能完成 ｔａｓｋｍ的所 有团队的迭代算法。 在当前 ｔｅａｍ 的情况，依次判断 每颗卫星 Ｓａｔ ｎ 能否完成 ｔａｓｋｍ ，如果能完成，则生成 新团队 ｔｅａｍ１ ，并将该 ｔｅａｍ１ 加入 ｔｅａｍＳｅｔ。 由算法的迭代过程可以看出，如果针对 Ｍ 个任 务，在 Ｎ 个卫星中构建团队，在最坏的情况下即每 颗卫星都有能力执行所有的任务，而且没有任何剪 枝操作发生，于是有 ＴＥＡＭｉ ＝ Ｎ ｉ ，那么迭代过程中 形成的方案总数为 ∑ Ｍ ｉ ＝ １ ＴＥＡＭｉ ＝ ∑ Ｍ ｉ ＝ １ Ｎ ｉ ，该算 法的时间复杂度为 Ｏ（Ｎ Ｍ＋１ ）。 由上述分析可知，在最坏的情况下，算法时间 复杂度将呈指数增长，该问题组合爆炸特征明显。 为了降低基于分枝限界思想的团队构建算法的时 间复杂度，提出了一种基于剪枝策略的启发式算法。 ３ 基于剪枝策略的启发式算法 通过 ＴＦＣＡ 算法进行树搜索，首先要找到一个 胜任所有任务的团队，以这个团队的代价作为上界 才可以进行剪枝操作，运行时间较长，剪掉的分支 有限，效率较低，为了提高树搜索效率，需要寻找一 种新的剪枝策略。 我们将深度优先的搜索方式改成广度优先，对 每一层的团队集合 ＴＥＡＭ 进行剪枝操作，从而达到 减少树分枝，降低时间复杂度的目的。 首 先， 给 出 剪 枝 策 略。 设 ｔｅａｍ１ ， ｔｅａｍ２ ∈ ＴＥＡＭｉ，如果 ｔｅａｍ１ ．Ｃｏｓｔ ≥ １ ＋ ε ｉ æ è ç ö ø ÷ ｔｅａｍ２ ．Ｃｏｓｔ ０ ＜ ε ＜ １ 记为 ｔｅａｍ１ ＜ ｔｅａｍ２ ，则剪去 ｔｅａｍ１ 这 个团队所在的结点。 其中，ｉ 是 ＴＥＡＭｉ 中的每个团 队完成的任务个数， ε 根据卫星初始状态调整，尽量 为团队挑选承担任务数少的卫星。 基于这种剪枝策略，提出了启发式团队构建算 法 （ ｈｅｕｒｉｓｔｉｃ ｔｅａｍ ｆｏｒｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ⁃ｏｎ ａ ·６５６· 智 能 系 统 学 报 第 １２ 卷

第5期 杨舒，等：一种面向任务的对地观测卫星Aget团队构建方法 ·657. pruning strategy,HTFA),算法伪码如算法4所示。 团队的代价偏大。为此，对输人任务集合TaskSet 算法4是基于剪枝策略的启发式算法，以teamo 进行排序： 作为根节点，从第1个任务开始搜索，TEAM是所 1)记无序的任务集合为TaskSet-S,以TaskSet-S 有完成task,的team集合，对TEAM1中每个team, 作为输入的HTFA算法为HTFA-S; 搜索ask,以此类推直到搜索到TEAM。语句8)~ 2)根据任务代价由高到低排序的任务集合为 22)是根据剪枝策略对TEAMy进行的剪枝操作。 TaskSet-.C,以TaskSet-C作为输入的HTFA算法为 算法4HTFA HTFA-C: 功能基于剪枝策略的启发式算法； 3)根据任务性价比由高到低排序的任务集合 输入TaskSet,SatSet,teamo; 为TaskSet-RC,以TaskSet--RC作为输入的HTFA算 输出team。 法为HTFA-RC。 1)Begin 4实验与分析 2)set TEAM:=☑，i∈(0，M) 3)TEAM。=TEAM。U{team,} 为了验证TFCA算法、HTFA-S算法、HTFA-C 算法、HTFA-RC算法的性能，设计了4组实验。 4)for(i=1:i≤M:i++) 计算平台：ntel(R)Core(TM)i5-6400CPU@ 5)for each teamin TEAM- 2.70GHz(4CPUs),内存8192 MB RAM,操作系统 6)set TEAM,=☑ Win7,采用Microsoft Visual Studio2010C#编码。 7)solve(1,team,teamSet,i) 实验数据在STK卫星数据库中选取50颗低 8)for each team,in teamSet 轨卫星数据模拟卫星集群的运行，以全球100个重 9)if(TEAM:= 要城市作为观测目标，从中随机挑选。设定每颗卫 10)TEAM,=TEAM,U{team, 星上携带可见光、红外、电磁探测、多光谱、超光谱5 11)else 种载荷。根据卫星硬件情况，设置卫星使用代价 12)for each team,in TEAM SC:=a(|Btasks:,|+|TW_used:)中的参数a,随机 l3)if(team1>team,） 挑选1~5个时间窗作为卫星上已经被占用的时间 14)TEAM,TEAM /(team2} 窗集合TW_used。采用随机生成一组任务的方式， 15)TEAM,TEAM,U (team 模拟真实环境下一段时间内卫星系统接收到的待 16)else 规划任务集合。 17)if(team2 team) 卫星集群按照卫星成员的数量可以分为小规 18)break 模卫星集群(small--scale satellite cluster,SSC)和大 19)else 规模卫星集群(large-scale satellite cluster,LSC)。 20)TEAM,TEAM,U {team,) 小规模卫星集群中成员数量在10颗以下，大规模卫 21)end for 星集群的成员数量大于10颗。 22)end for 实验1随机生成6组任务，在10颗卫星构成 23)end for 的小规模集群上采用TFCA、HTFA-S、HTFA-C、 24)end for HTFA-RC构建团队，比较4种算法的性能。实验结 25)for each team in TEAM 果如图1和表2。 26)if(team.Cost teamu".Cost 450r 400 OTFCA 27)teamur"=team 350 HTFA-S 28)end for 300 题HTFA-RC 250 ■HTFA-C 29)return team 200 30)End 150 100 由于HTFA算法的这种剪枝策略，TaskSet的输 50 入顺序可能会影响算法最终输出结果。如果在随 0 10 12 141618 20 机的任务集合中，代价小的任务排在前面，HT℉A将 任务数量/个 会优先挑选代价小的卫星执行该任务，代价大的任 图14种算法在小规模卫星集群上的性能对比 务只能选择代价大的卫星，会使最终构建出的卫星 Fig.1 Performances of four algorithms in SSC

ｐｒｕｎｉｎｇ ｓｔｒａｔｅｇｙ， ＨＴＦＡ），算法伪码如算法 ４ 所示。 算法 ４ 是基于剪枝策略的启发式算法，以 ｔｅａｍ０ 作为根节点，从第 １ 个任务开始搜索，ＴＥＡＭ１ 是所 有完成 ｔａｓｋ１ 的 ｔｅａｍ 集合，对 ＴＥＡＭ１ 中每个 ｔｅａｍ， 搜索 ｔａｓｋ２ ，以此类推直到搜索到 ＴＥＡＭＭ 。 语句８） ～ ２２）是根据剪枝策略对 ＴＥＡＭＭ 进行的剪枝操作。 算法 ４ ＨＴＦＡ 功能 基于剪枝策略的启发式算法； 输入 ＴａｓｋＳｅｔ， ＳａｔＳｅｔ，ｔｅａｍ０ ； 输出 ｔｅａｍ ｂｅｓｔ Ｍ 。 １） Ｂｅｇｉｎ ２） ｓｅｔ ＴＥＡＭｉ ＝ ∅，ｉ ∈ （０，Ｍ） ３） ＴＥＡＭ０ ＝ ＴＥＡＭ０ ∪ ｔｅａｍ０ { } ４）ｆｏｒ（ｉ ＝ １； ｉ ≤ Ｍ ；ｉ＋＋） ５）ｆｏｒ ｅａｃｈ ｔｅａｍｉｎ ＴＥＡＭｉ－１ ６）ｓｅｔ ＴＥＡＭｉ ＝ ∅ ７）ｓｏｌｖｅ（１，ｔｅａｍ，ｔｅａｍＳｅｔ，ｉ） ８）ｆｏｒ ｅａｃｈ ｔｅａｍ１ ｉｎ ｔｅａｍＳｅｔ ９）ｉｆ（ ＴＥＡＭｉ ＝ ∅ ） １０） ＴＥＡＭｉ ＝ ＴＥＡＭｉ ∪ ｔｅａｍ１ { } １１）ｅｌｓｅ １２）ｆｏｒ ｅａｃｈ ｔｅａｍ２ ｉｎ ＴＥＡＭｉ １３）ｉｆ（ ｔｅａｍ１ ＞ ｔｅａｍ２ ） １４） ＴＥＡＭｉ ＝ ＴＥＡＭｉ ／ ｔｅａｍ２ { } １５） ＴＥＡＭｉ ＝ ＴＥＡＭｉ ∪ ｔｅａｍ１ { } １６）ｅｌｓｅ １７）ｉｆ（ ｔｅａｍ２ ＞ ｔｅａｍ１ ） １８）ｂｒｅａｋ １９）ｅｌｓｅ ２０） ＴＥＡＭｉ ＝ ＴＥＡＭｉ ∪ ｔｅａｍ１ { } ２１）ｅｎｄ ｆｏｒ ２２）ｅｎｄ ｆｏｒ ２３）ｅｎｄ ｆｏｒ ２４）ｅｎｄ ｆｏｒ ２５）ｆｏｒ ｅａｃｈ ｔｅａｍ ｉｎ ＴＥＡＭＭ ２６） ｉｆ（ ｔｅａｍ．Ｃｏｓｔ ＜ ｔｅａｍ ｂｅｓｔ Ｍ ．Ｃｏｓｔ ） ２７） ｔｅａｍ ｂｅｓｔ Ｍ ＝ ｔｅａｍ ２８）ｅｎｄ ｆｏｒ ２９）ｒｅｔｕｒｎ ｔｅａｍ ｂｅｓｔ Ｍ ３０） Ｅｎｄ 由于 ＨＴＦＡ 算法的这种剪枝策略，ＴａｓｋＳｅｔ 的输 入顺序可能会影响算法最终输出结果。 如果在随 机的任务集合中，代价小的任务排在前面，ＨＴＦＡ 将 会优先挑选代价小的卫星执行该任务，代价大的任 务只能选择代价大的卫星，会使最终构建出的卫星 团队的代价偏大。 为此，对输入任务集合 ＴａｓｋＳｅｔ 进行排序： １）记无序的任务集合为 ＴａｓｋＳｅｔ⁃Ｓ，以 ＴａｓｋＳｅｔ⁃Ｓ 作为输入的 ＨＴＦＡ 算法为 ＨＴＦＡ⁃Ｓ； ２）根据任务代价由高到低排序的任务集合为 ＴａｓｋＳｅｔ⁃Ｃ，以 ＴａｓｋＳｅｔ⁃Ｃ 作为输入的 ＨＴＦＡ 算法为 ＨＴＦＡ⁃Ｃ； ３）根据任务性价比由高到低排序的任务集合 为 ＴａｓｋＳｅｔ⁃ＲＣ，以 ＴａｓｋＳｅｔ⁃ＲＣ 作为输入的 ＨＴＦＡ 算 法为 ＨＴＦＡ⁃ＲＣ。 ４ 实验与分析 为了验证 ＴＦＣＡ 算法、ＨＴＦＡ－Ｓ 算法、ＨＴＦＡ－Ｃ 算法、ＨＴＦＡ－ＲＣ 算法的性能，设计了 ４ 组实验。 计算平台：Ｉｎｔｅｌ（Ｒ） Ｃｏｒｅ（ＴＭ） ｉ５⁃６４００ ＣＰＵ ＠ ２．７０ ＧＨｚ （４ ＣＰＵｓ），内存 ８１９２ ＭＢ ＲＡＭ，操作系统 Ｗｉｎ７，采用 Ｍｉｃｒｏｓｏｆｔ Ｖｉｓｕａｌ Ｓｔｕｄｉｏ ２０１０ Ｃ＃编码。 实验数据 在 ＳＴＫ 卫星数据库中选取 ５０ 颗低 轨卫星数据模拟卫星集群的运行，以全球 １００ 个重 要城市作为观测目标，从中随机挑选。 设定每颗卫 星上携带可见光、红外、电磁探测、多光谱、超光谱 ５ 种载荷。 根据卫星硬件情况，设置卫星使用代价 ＳＣｉ ＝ α Ｂｔａｓｋｓｉ ＋ ＴＷ＿ｕｓｅｄｉ ( ) 中的参数 α，随机 挑选 １～５ 个时间窗作为卫星上已经被占用的时间 窗集合 ＴＷ＿ｕｓｅｄ。 采用随机生成一组任务的方式， 模拟真实环境下一段时间内卫星系统接收到的待 规划任务集合。 卫星集群按照卫星成员的数量可以分为小规 模卫星集群（ ｓｍａｌｌ⁃ｓｃａｌｅ ｓａｔｅｌｌｉｔｅ ｃｌｕｓｔｅｒ， ＳＳＣ） 和大 规模卫星集群 （ ｌａｒｇｅ⁃ｓｃａｌｅ ｓａｔｅｌｌｉｔｅ ｃｌｕｓｔｅｒ， ＬＳＣ）。 小规模卫星集群中成员数量在 １０ 颗以下，大规模卫 星集群的成员数量大于 １０ 颗。 实验 １ 随机生成 ６ 组任务，在 １０ 颗卫星构成 的小 规 模 集 群 上 采 用 ＴＦＣＡ、 ＨＴＦＡ⁃Ｓ、 ＨＴＦＡ⁃Ｃ、 ＨＴＦＡ⁃ＲＣ 构建团队，比较 ４ 种算法的性能。 实验结 果如图 １ 和表 ２。 图 １ ４ 种算法在小规模卫星集群上的性能对比 Ｆｉｇ．１ Ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｉｎ ＳＳＣ 第 ５ 期 杨舒，等：一种面向任务的对地观测卫星 Ａｇｅｎｔ 团队构建方法 ·６５７·

·658. 智能系统学报 第12卷 表24种算法在小规模卫星集群上的运行时间对比 图2展现了在大规模卫星集群上HTFA-S、 Table 2 Running time of four algorithms in SSC HTFA-RC、HTFA-C算法的性能差异。HTFA-RC HTFA-C算法构建团队的效果普遍优于HTFA-S算 任务数量 TFCA HTFA-S HTFA-RC HTFA-C 法。从图3中可以看出，随着任务增多，HTFA-S、 10 7.591 0.026 0.054 0.054 HTFA-RC、HTFA-C算法构建团队时间都在逐渐增 12 42.479 0.107 0.057 0.088 加，而HT℉A-C构建团队时间的增长速度明显高于 153.379 0.179 0.096 0.209 HTFA-S和HTFA-RC,这是因为HTFA-C任务的有 序性在相同的剪枝策略下相比于其他两种算法， 16 1086.749 0.179 0.158 0.158 HT℉A-C在每一层会更多地保留效果好的分枝，因 18 8019.749 0.258 0.399 1.339 此整个团队构建过程中，搜索的分枝更多。 20 90078.369 0.418 1.241 2.096 实验3随机生成一组由10个任务构成的任 从图1可以看出，在小规模卫星集群中，HT℉A- 务集合，在不同规模的卫星集群上构建团队，比较 S、HTFA-RC、HTFA-C算法构建的团队效果接近 TFCA、HTFA-S、HTFA-C、HTFA-RC算法性能，实验 TFCA算法。HTFA-S算法由于任务输入的无序性， 结果如表3、图4所示。 在大部分情况下构建团队的效果比HTFA-RC 表34种算法的运行时间对比 HTFA-C算法差。表2展示了4种算法的时间特 Table 3 Running time of four algorithms 性，T℉CA算法的运行时间随着任务的增多，呈现指 卫星数量/个 TFCA HTFA-S HTFA-RC HTFA-C 数增长趋势，HTFA-S、HTFA-RC、HTFA-C算法的运 行时间增长缓慢。 5 0.158 0.007 0.007 0.014 实验2为了进一步验证我们提出的算法在大 规模卫星集群上的性能，在50颗卫星组成的卫星集 > 1.356 0.029 0.010 0.018 群上重新测试实验1中的6组任务数据。但由于 3.925 0.032 0.025 0.071 T℉CA算法运行时间太长（在50颗卫星组成的集群 上，对12个任务构建团队时，运行超过12h仍然不 11 14.640 0.039 0.033 0.014 能给出有效结果)我们仅对比HTFA-S、HTFA-RC和 13 20.877 0.042 0.016 0.009 HTFA-C的实验结果，如图2、3所示。 0.014 200 41.286 0.045 0.007 HTFA-S 150 OHTFA-RC ■HTFA-C 250 225 OTFCA 图HITFA-S 100 2 138 ▣HTFA-RC ■HTFA-C 50 12 10 12 14 16 18 20 29 任务数量/个 N 图23种启发式算法在LSC上的性能对比 9 11 13 Fig.2 Performances of three algorithms in LSC 卫星数量/个 30 图44种算法在不同规模卫星集群上的性能对比 3 .HTFA-S Fig.4 Performances of four algorithms in different 20 -HTFA-RC scales of SC HTFA-C 图4是在中小规模的多个卫星集群上对同一组 任务数据构建团队对比4种算法的性能。随着卫星 5 规模的逐步增大，团队的代价越来越小。多数情况 下，HTFA-C、HTFA-RC算法的性能优于HTFA-S算 10 12 141618 20 任务数量/个 法。从表3中可以看出，T℉CA算法的运行时间随 图33种启发式算法在LSC上的运行时间对比 着集群规模增大爆发式增长。而HTFA-S、HTFA Fig.3 Time comparison of three algorithms in LSC RC、HTFA-C算法的运行时间增长不明显

表 ２ ４ 种算法在小规模卫星集群上的运行时间对比 Ｔａｂｌｅ ２ Ｒｕｎｎｉｎｇ ｔｉｍｅ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｉｎ ＳＳＣ ｓ 任务数量 ＴＦＣＡ ＨＴＦＡ⁃Ｓ ＨＴＦＡ⁃ＲＣ ＨＴＦＡ⁃Ｃ １０ ７．５９１ ０．０２６ ０．０５４ ０．０５４ １２ ４２．４７９ ０．１０７ ０．０５７ ０．０８８ １４ １５３．３７９ ０．１７９ ０．０９６ ０．２０９ １６ １ ０８６．７４９ ０．１７９ ０．１５８ ０．１５８ １８ ８ ０１９．７４９ ０．２５８ ０．３９９ １．３３９ ２０ ９０ ０７８．３６９ ０．４１８ １．２４１ ２．０９６ 从图 １ 可以看出，在小规模卫星集群中，ＨＴＦＡ⁃ Ｓ、ＨＴＦＡ⁃ＲＣ、 ＨＴＦＡ⁃Ｃ 算法构建的团队效果接近 ＴＦＣＡ 算法。 ＨＴＦＡ⁃Ｓ 算法由于任务输入的无序性， 在大部 分 情 况 下 构 建 团 队 的 效 果 比 ＨＴＦＡ⁃ＲＣ、 ＨＴＦＡ⁃Ｃ 算法差。 表 ２ 展示了 ４ 种算法的时间特 性，ＴＦＣＡ 算法的运行时间随着任务的增多，呈现指 数增长趋势，ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ、ＨＴＦＡ⁃Ｃ 算法的运 行时间增长缓慢。 实验 ２ 为了进一步验证我们提出的算法在大 规模卫星集群上的性能，在 ５０ 颗卫星组成的卫星集 群上重新测试实验 １ 中的 ６ 组任务数据。 但由于 ＴＦＣＡ 算法运行时间太长（在 ５０ 颗卫星组成的集群 上，对 １２ 个任务构建团队时，运行超过 １２ ｈ 仍然不 能给出有效结果）我们仅对比 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ⁃Ｃ 的实验结果，如图 ２、３ 所示。 图 ２ ３ 种启发式算法在 ＬＳＣ 上的性能对比 Ｆｉｇ．２ Ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｉｎ ＬＳＣ 图 ３ ３ 种启发式算法在 ＬＳＣ 上的运行时间对比 Ｆｉｇ．３ Ｔｉｍｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｉｎ ＬＳＣ 图 ２ 展现了在大规模卫星集群上 ＨＴＦＡ⁃Ｓ、 ＨＴＦＡ⁃ＲＣ、ＨＴＦＡ⁃Ｃ 算法的性能 差 异。 ＨＴＦＡ⁃ＲＣ、 ＨＴＦＡ⁃Ｃ 算法构建团队的效果普遍优于 ＨＴＦＡ⁃Ｓ 算 法。 从图 ３ 中可以看出，随着任务增多，ＨＴＦＡ⁃Ｓ、 ＨＴＦＡ⁃ＲＣ、ＨＴＦＡ⁃Ｃ 算法构建团队时间都在逐渐增 加，而 ＨＴＦＡ⁃Ｃ 构建团队时间的增长速度明显高于 ＨＴＦＡ⁃Ｓ 和 ＨＴＦＡ⁃ＲＣ，这是因为 ＨＴＦＡ⁃Ｃ 任务的有 序性在相同的剪枝策略下相比于其他两种算法， ＨＴＦＡ⁃Ｃ 在每一层会更多地保留效果好的分枝，因 此整个团队构建过程中，搜索的分枝更多。 实验 ３ 随机生成一组由 １０ 个任务构成的任 务集合，在不同规模的卫星集群上构建团队，比较 ＴＦＣＡ、ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃Ｃ、ＨＴＦＡ⁃ＲＣ 算法性能，实验 结果如表 ３、图 ４ 所示。 表 ３ ４ 种算法的运行时间对比 Ｔａｂｌｅ ３ Ｒｕｎｎｉｎｇ ｔｉｍｅ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｓ 卫星数量／ 个 ＴＦＣＡ ＨＴＦＡ⁃Ｓ ＨＴＦＡ⁃ＲＣ ＨＴＦＡ⁃Ｃ ５ ０．１５８ ０．００７ ０．００７ ０．０１４ ７ １．３５６ ０．０２９ ０．０１０ ０．０１８ ９ ３．９２５ ０．０３２ ０．０２５ ０．０７１ １１ １４．６４０ ０．０３９ ０．０３３ ０．０１４ １３ ２０．８７７ ０．０４２ ０．０１６ ０．００９ １５ ４１．２８６ ０．０４５ ０．０１４ ０．００７ 图 ４ ４ 种算法在不同规模卫星集群上的性能对比 Ｆｉｇ． ４ Ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｓｃａｌｅｓ ｏｆ ＳＣ 图 ４ 是在中小规模的多个卫星集群上对同一组 任务数据构建团队对比 ４ 种算法的性能。 随着卫星 规模的逐步增大，团队的代价越来越小。 多数情况 下，ＨＴＦＡ⁃Ｃ、ＨＴＦＡ⁃ＲＣ 算法的性能优于 ＨＴＦＡ⁃Ｓ 算 法。 从表 ３ 中可以看出，ＴＦＣＡ 算法的运行时间随 着集群规模增大爆发式增长。 而 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ ＲＣ、ＨＴＦＡ⁃Ｃ 算法的运行时间增长不明显。 ·６５８· 智 能 系 统 学 报 第 １２ 卷

第5期 杨舒，等：一种面向任务的对地观测卫星Aget团队构建方法 ·659· 实验4为了进一步比较3种启发式算法在大 星任务规划领域出现的新而亟待解决的问题。在 规模卫星集群上的性能，随机生成一组由20个任务 对问题进行分析的基础上，建立了数学模型，提出 组成的任务集合，在10、20、30、40、50颗卫星组成的 了基于分枝限界的卫星团队构建精确搜索算法 卫星集群上进行实验。由于TFCA算法运行时间太 (TFCA)。针对TFCA算法时间复杂度高的缺点，引 长（在20颗卫星组成的集群上，对20个任务构建团 入了启发式剪枝策略，并根据算法输入中任务集合 队时，运行超过12h仍然不能给出有效结果)，我们 的次序不同，提出了3种启发式卫星团队构建算法： 仅对比HTFA-S、HTFA-RC和HTFA-C的实验结果， HTFA-S、HTFA-RC和HTFA-C算法。实验结果表 如图5、6所示。 明：3种启发式算法HTFA-S、HTFA-RC和HTFA-C, 500 构建团队所需的时间成本远小于T℉CA算法，而其 SHTFA-S 400 性能与T℉CA算法相差不大，对任务集合根据任务 ▣HTFA-RC ■HTFA-C 代价排序的HTFA-C构建的团队的代价最接近 300 TFCA算法构建的团队的代价。 200 在下一步的工作中，我们将从理论上分析 HTFA-S、HTFA-RC和HTFA-C算法近似程度，并给 出算法性能上界。 o 20 30 40 0 卫星数量/个 参考文献： 图53种启发式算法在不同规模卫星集群上的性能对比 [1]LIN Zhenhai.Mission planning for electromagnetic Fig.5 Performances of three algorithms in different environment monitors satellite based on simulated scales of SC annealing algorithm C]//2015 IEEE 28th Canadian 25 Conference on Electrical and Computer Engineering 汤 …·HTFA-S CCECE).Halifax,Canada,2015:530-535 HTFA-RC [2]姜维，郝会成，李一军对地观测卫星任务规划问题研究 15 +一HTFA-C 述评[J].系统工程与电子技术，2013,35(9)： 10 1878-1885 JIANG Wei,HAO Huicheng,LI Yijun.Review of task scheduling research for the earth observing satellites[J]. 10 20 30 40 50 Systems engineering and electronics,2013,35 (9 ) 卫星数量/个 1878-1885. [3]WANG Jun,JING Ning,LI Jun,et al.A multi-objective 图63种启发式算法在不同规模的卫星集群上运行时间 imaging scheduling approach for earth observing satellites Fig.6 Time comparison of three algorithms in different [C]//Proceedings of the 9th annual conference on Genetic scales of SC and evolutionary computation.London,England,2007: 图6中随着卫星规模的增大，对同一组任务构 2211-2218. 建的团队代价逐渐减少，而构建团队的时间逐渐增 [4 CHEN Hao,LI Jun,JING Ning.User-oriented data 大。这是因为规模增大，可以挑选多个卫星承担任 acquisition chain task planning algorithm for operationally 务，无需一个卫星承担多个任务，团队代价随之 responsive space satellite[].Journal of systems engineering and electronics,2016,27(5):1028-1039. 降低。 [5]WANG P,REINELT G,GAO P,et al.A model,a 整体上来看，3种启发式算法HTFA-S、HTFA- heuristic and a decision support system to solve the RC和HTFA-C构建团队所需的时间成本远小于 scheduling problem of an earth observing satellite TFCA算法，而其性能与TFCA相差不大，对任务集 constellation [J].Computers industrial engineering, 合根据任务代价排序的HT℉A-C构建的团队的代价 2011.61(2):322-335. 最接近T℉CA算法构建的团队的代价，也就是最接 [6]郭玉华.多类型对地观测卫星联合任务规划关键技术研 究[D].长沙：国防科技大学，2009：19-57. 近全局最优解，HTFA-RC次之。 GUO Yuhua.The study on key technologies of multiple types of 5结束语 earth observing satellites united scheduling[D].Changsha: national university of defense technology,2009:19-57. 面向任务的对地观测卫星团队构建问题，是卫 [7]BIANCHESSI N,RIGHINI G.Planning and scheduling

实验 ４ 为了进一步比较 ３ 种启发式算法在大 规模卫星集群上的性能，随机生成一组由 ２０ 个任务 组成的任务集合，在 １０、２０、３０、４０、５０ 颗卫星组成的 卫星集群上进行实验。 由于 ＴＦＣＡ 算法运行时间太 长（在 ２０ 颗卫星组成的集群上，对 ２０ 个任务构建团 队时，运行超过 １２ ｈ 仍然不能给出有效结果），我们 仅对比 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ⁃Ｃ 的实验结果， 如图 ５、６ 所示。 图 ５ ３ 种启发式算法在不同规模卫星集群上的性能对比 Ｆｉｇ． ５ Ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｓｃａｌｅｓ ｏｆ ＳＣ 图 ６ ３ 种启发式算法在不同规模的卫星集群上运行时间 Ｆｉｇ．６ Ｔｉｍｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｓｃａｌｅｓ ｏｆ ＳＣ 图 ６ 中随着卫星规模的增大，对同一组任务构 建的团队代价逐渐减少，而构建团队的时间逐渐增 大。 这是因为规模增大，可以挑选多个卫星承担任 务，无需一个卫星承担多个任务， 团队代价随之 降低。 整体上来看，３ 种启发式算法 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ ＲＣ 和 ＨＴＦＡ⁃Ｃ 构建团队所需的时间成本远小于 ＴＦＣＡ 算法，而其性能与 ＴＦＣＡ 相差不大，对任务集 合根据任务代价排序的 ＨＴＦＡ⁃Ｃ 构建的团队的代价 最接近 ＴＦＣＡ 算法构建的团队的代价，也就是最接 近全局最优解，ＨＴＦＡ⁃ＲＣ 次之。 ５ 结束语 面向任务的对地观测卫星团队构建问题，是卫 星任务规划领域出现的新而亟待解决的问题。 在 对问题进行分析的基础上，建立了数学模型，提出 了基于分枝限界的卫星团队构建精确搜索算法 （ＴＦＣＡ）。 针对 ＴＦＣＡ 算法时间复杂度高的缺点，引 入了启发式剪枝策略，并根据算法输入中任务集合 的次序不同，提出了 ３ 种启发式卫星团队构建算法： ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ－Ｃ 算法。 实验结果表 明：３ 种启发式算法 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ⁃Ｃ， 构建团队所需的时间成本远小于 ＴＦＣＡ 算法，而其 性能与 ＴＦＣＡ 算法相差不大，对任务集合根据任务 代价排序的 ＨＴＦＡ⁃Ｃ 构建的团队的代价最接近 ＴＦＣＡ 算法构建的团队的代价。 在下一 步 的 工 作 中， 我 们 将 从 理 论 上 分 析 ＨＴＦＡ⁃Ｓ、ＨＴＦＡ⁃ＲＣ 和 ＨＴＦＡ⁃Ｃ 算法近似程度，并给 出算法性能上界。 参考文献： ［ １ ］ ＬＩＮ Ｚｈｅｎｈａｉ． Ｍｉｓｓｉｏｎ ｐｌａｎｎｉｎｇ ｆｏｒ ｅｌｅｃｔｒｏｍａｇｎｅｔｉｃ ｅｎｖｉｒｏｎｍｅｎｔ ｍｏｎｉｔｏｒｓ ｓａｔｅｌｌｉｔｅ ｂａｓｅｄ ｏｎ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ ［ Ｃ ］ ／ ／ ２０１５ ＩＥＥＥ ２８ｔｈ Ｃａｎａｄｉａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｉｃａｌ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ （ＣＣＥＣＥ）． Ｈａｌｉｆａｘ， Ｃａｎａｄａ， ２０１５： ５３０－５３５． ［２］姜维，郝会成，李一军．对地观测卫星任务规划问题研究 述 评 ［ Ｊ ］． 系 统 工 程 与 电 子 技 术， ２０１３， ３５ （ ９ ）： １８７８－１８８５． ＪＩＡＮＧ Ｗｅｉ， ＨＡＯ Ｈｕｉｃｈｅｎｇ， ＬＩ Ｙｉｊｕｎ． Ｒｅｖｉｅｗ ｏｆ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｒｅｓｅａｒｃｈ ｆｏｒ ｔｈｅ ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅｓ ［ Ｊ］． Ｓｙｓｔｅｍｓ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｅｌｅｃｔｒｏｎｉｃｓ， ２０１３， ３５ （ ９ ）： １８７８－１８８５． ［３］ＷＡＮＧ Ｊｕｎ， ＪＩＮＧ Ｎｉｎｇ， ＬＩ Ｊｕｎ， ｅｔ ａｌ． Ａ ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ ｉｍａｇｉｎｇ ｓｃｈｅｄｕｌｉｎｇ ａｐｐｒｏａｃｈ ｆｏｒ ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ９ｔｈ ａｎｎｕａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｅｎｅｔｉｃ ａｎｄ ｅｖｏｌｕｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ． Ｌｏｎｄｏｎ， Ｅｎｇｌａｎｄ， ２００７： ２２１１－２２１８． ［４ ］ ＣＨＥＮ Ｈａｏ， ＬＩ Ｊｕｎ， ＪＩＮＧ Ｎｉｎｇ． Ｕｓｅｒ⁃ｏｒｉｅｎｔｅｄ ｄａｔａ ａｃｑｕｉｓｉｔｉｏｎ ｃｈａｉｎ ｔａｓｋ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｏｐｅｒａｔｉｏｎａｌｌｙ ｒｅｓｐｏｎｓｉｖｅ ｓｐａｃｅ ｓａｔｅｌｌｉｔｅ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｓｙｓｔｅｍｓ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｅｌｅｃｔｒｏｎｉｃｓ， ２０１６， ２７（５）： １０２８－１０３９． ［５］ ＷＡＮＧ Ｐ， ＲＥＩＮＥＬＴ Ｇ， ＧＡＯ Ｐ， ｅｔ ａｌ． Ａ ｍｏｄｅｌ， ａ ｈｅｕｒｉｓｔｉｃ ａｎｄ ａ ｄｅｃｉｓｉｏｎ ｓｕｐｐｏｒｔ ｓｙｓｔｅｍ ｔｏ ｓｏｌｖｅ ｔｈｅ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ ｏｆ ａｎ ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅ ｃｏｎｓｔｅｌｌａｔｉｏｎ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒｓ ＆ ｉｎｄｕｓｔｒｉａｌ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１１， ６１（２）： ３２２－３３５． ［６］郭玉华． 多类型对地观测卫星联合任务规划关键技术研 究［Ｄ］． 长沙：国防科技大学， ２００９： １９－５７． ＧＵＯ Ｙｕｈｕａ． Ｔｈｅ ｓｔｕｄｙ ｏｎ ｋｅｙ ｔｅｃｈｎｏｌｏｇｉｅｓ ｏｆ ｍｕｌｔｉｐｌｅ ｔｙｐｅｓ ｏｆ ｅａｒｔｈ ｏｂｓｅｒｖｉｎｇ ｓａｔｅｌｌｉｔｅｓ ｕｎｉｔｅｄ ｓｃｈｅｄｕｌｉｎｇ ［Ｄ］． Ｃｈａｎｇｓｈａ： ｎａｔｉｏｎａｌ ｕｎｉｖｅｒｓｉｔｙ ｏｆ ｄｅｆｅｎｓｅ ｔｅｃｈｎｏｌｏｇｙ，２００９： １９－５７． ［７ ］ ＢＩＡＮＣＨＥＳＳＩ Ｎ， ＲＩＧＨＩＮＩ Ｇ． Ｐｌａｎｎｉｎｇ ａｎｄ ｓｃｈｅｄｕｌｉｎｇ 第 ５ 期 杨舒，等：一种面向任务的对地观测卫星 Ａｇｅｎｔ 团队构建方法 ·６５９·

·660· 智能系统学报 第12卷 algorithms for the COSMO-SkyMed constellation J ] [16]OKIMOTO T,SCHWIND N,CLEMENT M,et al.How to Aerospace science technology,2008,12(7):535-544. form a task-oriented robust team[C]//Proceedings of the [8 BOTELHO S C,Alami R.M+:a scheme for multi-robot 2015 International Conference on Autonomous Agents and cooperation through negotiated task allocation and Multiagent Systems.International Foundation for achievement[C]//1999 IEEE International Conference on Autonomous Agents and Multiagent Systems.Istanbul, Robotics and Automation.Detroit,USA,1999,2:1234-1239. Turkey,2015:395-403. [9]PENG Shuang,CHEN Hao,LIN Jun,et al.Multi-agent [17]HE L,IOERGER T R.A quantitative model of capabilities collaborative planning method of emergency mission based in multi-agent systems C ]//Proceeding of the on scheme fusion strategy[C]//2014 IEEE Symposium on Intemational Conference on Artificial Intelligence(IC-Al) Computer Applications and Communications (SCAC). Las Vegas,USA,2003:730-736. Weihai,China,2014:87-92. [18]CRAWFORD C,RAHAMAN Z,Sen S.Evaluating the [10]FENG Peng,CHEN Hao,PENG Shuang,et al.A method efficiency of robust team formation algorithms [C]// of distributed multi-satellite mission scheduling based on Intemational Conference on Autonomous Agents and improved contract net protocol[C]//2015 11th International Multiagent Systems.Tulsa,USA,2016:14-29. Conference on Natural Computation (ICNC).Zhangjiajie, 作者简介： China.2015:1062-1068. 杨舒，女，1992年生，硕士研究生 [11]WANG Chong,JING Ning,et al.A distributed cooperative 主要研究方向为卫星任务规划、多 dynamic task planning algorithm for multiple satellites Agent协同规划。 based on multi-agent hybrid learning[J].Chinese journal of aeronautics,2011,24(4):493-505. [12]董云峰，王兴龙.卫星集群概念研究[J].航天器工程， 2012,21(4):83-88. DONG Yunfeng,WANG Xinglong.Research on conception 陈浩，男，1982年生，副教授，主要 of satellite cluster[J].Spacecraft engineering,2012,21 研究方向为计算机智能、机器学习、卫 (4):83-88. 星智能规划。 [13]MOORES J E,CARROLL K A,DESOUZE I,et al.The small reconnaissance of atmospheres mission platform concept,part 2:design of carrier spacecraft and atmospheric entry probes[].International journal of space science engineering,2014,2(4):345-364. 李军，1973年生，教授，博士生导 [14]HINCHEY M G,STERRITT R,ROUFF C.Swarms and 师，主要研究方向为大数据分析与处 swarm intelligence[]].Computer,2007,40(4): 理、卫星智能规划和控制。 111-113. [15]DEKENS E,ENGELEN S,NOOMEN R.A satellite swarm for radio astronomy[J].Acta astronautica,2014,102: 321-331

ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ＣＯＳＭＯ⁃ＳｋｙＭｅｄ ｃｏｎｓｔｅｌｌａｔｉｏｎ ［ Ｊ ］． Ａｅｒｏｓｐａｃｅ ｓｃｉｅｎｃｅ ＆ ｔｅｃｈｎｏｌｏｇｙ， ２００８， １２（７）： ５３５－５４４． ［８］ ＢＯＴＥＬＨＯ Ｓ Ｃ， Ａｌａｍｉ Ｒ． Ｍ ＋： ａ ｓｃｈｅｍｅ ｆｏｒ ｍｕｌｔｉ⁃ｒｏｂｏｔ ｃｏｏｐｅｒａｔｉｏｎ ｔｈｒｏｕｇｈ ｎｅｇｏｔｉａｔｅｄ ｔａｓｋ ａｌｌｏｃａｔｉｏｎ ａｎｄ ａｃｈｉｅｖｅｍｅｎｔ［Ｃ］ ／ ／ １９９９ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ． Ｄｅｔｒｏｉｔ， ＵＳＡ， １９９９， ２： １２３４－１２３９． ［９］ ＰＥＮＧ Ｓｈｕａｎｇ， ＣＨＥＮ Ｈａｏ， ＬＩＮ Ｊｕｎ， ｅｔ ａｌ． Ｍｕｌｔｉ⁃ａｇｅｎｔ ｃｏｌｌａｂｏｒａｔｉｖｅ ｐｌａｎｎｉｎｇ ｍｅｔｈｏｄ ｏｆ ｅｍｅｒｇｅｎｃｙ ｍｉｓｓｉｏｎ ｂａｓｅｄ ｏｎ ｓｃｈｅｍｅ ｆｕｓｉｏｎ ｓｔｒａｔｅｇｙ［Ｃ］ ／ ／ ２０１４ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ （ ＳＣＡＣ ）． Ｗｅｉｈａｉ， Ｃｈｉｎａ， ２０１４： ８７－９２． ［１０］ＦＥＮＧ Ｐｅｎｇ， ＣＨＥＮ Ｈａｏ， ＰＥＮＧ Ｓｈｕａｎｇ， ｅｔ ａｌ． Ａ ｍｅｔｈｏｄ ｏｆ ｄｉｓｔｒｉｂｕｔｅｄ ｍｕｌｔｉ⁃ｓａｔｅｌｌｉｔｅ ｍｉｓｓｉｏｎ ｓｃｈｅｄｕｌｉｎｇ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｃｏｎｔｒａｃｔ ｎｅｔ ｐｒｏｔｏｃｏｌ［Ｃ］ ／ ／ ２０１５ １１ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎａｔｕｒａｌ Ｃｏｍｐｕｔａｔｉｏｎ （ ＩＣＮＣ）． Ｚｈａｎｇｊｉａｊｉｅ， Ｃｈｉｎａ， ２０１５： １０６２－１０６８． ［１１］ＷＡＮＧ Ｃｈｏｎｇ， ＪＩＮＧ Ｎｉｎｇ， ｅｔ ａｌ． Ａ ｄｉｓｔｒｉｂｕｔｅｄ ｃｏｏｐｅｒａｔｉｖｅ ｄｙｎａｍｉｃ ｔａｓｋ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｌｔｉｐｌｅ ｓａｔｅｌｌｉｔｅｓ ｂａｓｅｄ ｏｎ ｍｕｌｔｉ⁃ａｇｅｎｔ ｈｙｂｒｉｄ ｌｅａｒｎｉｎｇ［Ｊ］．Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ａｅｒｏｎａｕｔｉｃｓ ， ２０１１， ２４（４）：４９３－５０５． ［１２］董云峰， 王兴龙． 卫星集群概念研究［ Ｊ］． 航天器工程， ２０１２， ２１（４）：８３－８８． ＤＯＮＧ Ｙｕｎｆｅｎｇ， ＷＡＮＧ Ｘｉｎｇｌｏｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ｃｏｎｃｅｐｔｉｏｎ ｏｆ ｓａｔｅｌｌｉｔｅ ｃｌｕｓｔｅｒ ［ Ｊ］． Ｓｐａｃｅｃｒａｆｔ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１２， ２１ （４）： ８３－８８． ［１３］ＭＯＯＲＥＳ Ｊ Ｅ， ＣＡＲＲＯＬＬ Ｋ Ａ， ＤＥＳＯＵＺＥ Ｉ， ｅｔ ａｌ． Ｔｈｅ ｓｍａｌｌ ｒｅｃｏｎｎａｉｓｓａｎｃｅ ｏｆ ａｔｍｏｓｐｈｅｒｅｓ ｍｉｓｓｉｏｎ ｐｌａｔｆｏｒｍ ｃｏｎｃｅｐｔ， ｐａｒｔ ２： ｄｅｓｉｇｎ ｏｆ ｃａｒｒｉｅｒ ｓｐａｃｅｃｒａｆｔ ａｎｄ ａｔｍｏｓｐｈｅｒｉｃ ｅｎｔｒｙ ｐｒｏｂｅｓ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｓｐａｃｅ ｓｃｉｅｎｃｅ ＆ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１４， ２（４）： ３４５－３６４． ［１４］ＨＩＮＣＨＥＹ Ｍ Ｇ， ＳＴＥＲＲＩＴＴ Ｒ， ＲＯＵＦＦ Ｃ． Ｓｗａｒｍｓ ａｎｄ ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ［Ｊ］． Ｃｏｍｐｕｔｅｒ， ２００７， ４０ （ ４ ）： １１１－１１３． ［１５］ＤＥＫＥＮＳ Ｅ， ＥＮＧＥＬＥＮ Ｓ， ＮＯＯＭＥＮ Ｒ． Ａ ｓａｔｅｌｌｉｔｅ ｓｗａｒｍ ｆｏｒ ｒａｄｉｏ ａｓｔｒｏｎｏｍｙ ［ Ｊ］． Ａｃｔａ ａｓｔｒｏｎａｕｔｉｃａ， ２０１４， １０２： ３２１－３３１． ［１６］ＯＫＩＭＯＴＯ Ｔ， ＳＣＨＷＩＮＤ Ｎ， ＣＬＥＭＥＮＴ Ｍ， ｅｔ ａｌ． Ｈｏｗ ｔｏ ｆｏｒｍ ａ ｔａｓｋ⁃ｏｒｉｅｎｔｅｄ ｒｏｂｕｓｔ ｔｅａｍ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０１５ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｕｔｏｎｏｍｏｕｓ Ａｇｅｎｔｓ ａｎｄ Ｍｕｌｔｉａｇｅｎｔ Ｓｙｓｔｅｍｓ． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｆｏｕｎｄａｔｉｏｎ ｆｏｒ Ａｕｔｏｎｏｍｏｕｓ Ａｇｅｎｔｓ ａｎｄ Ｍｕｌｔｉａｇｅｎｔ Ｓｙｓｔｅｍｓ． Ｉｓｔａｎｂｕｌ， Ｔｕｒｋｅｙ， ２０１５： ３９５－４０３． ［１７］ＨＥ Ｌ， ＩＯＥＲＧＥＲ Ｔ Ｒ． Ａ ｑｕａｎｔｉｔａｔｉｖｅ ｍｏｄｅｌ ｏｆ ｃａｐａｂｉｌｉｔｉｅｓ ｉｎ ｍｕｌｔｉ⁃ａｇｅｎｔ ｓｙｓｔｅｍｓ ［ Ｃ ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ（ ＩＣ⁃ＡＩ） Ｌａｓ Ｖｅｇａｓ， ＵＳＡ ， ２００３： ７３０－７３６． ［１８］ ＣＲＡＷＦＯＲＤ Ｃ， ＲＡＨＡＭＡＮ Ｚ， Ｓｅｎ Ｓ． Ｅｖａｌｕａｔｉｎｇ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｒｏｂｕｓｔ ｔｅａｍ ｆｏｒｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ［ Ｃ ］ ／ ／ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｕｔｏｎｏｍｏｕｓ Ａｇｅｎｔｓ ａｎｄ Ｍｕｌｔｉａｇｅｎｔ Ｓｙｓｔｅｍｓ． Ｔｕｌｓａ， ＵＳＡ， ２０１６： １４－２９． 作者简介： 杨舒， 女，１９９２ 年生，硕士研究生， 主要 研 究 方 向 为 卫 星 任 务 规 划、 多 Ａｇｅｎｔ 协同规划。 陈浩，男，１９８２ 年生，副教授，主要 研究方向为计算机智能、机器学习、卫 星智能规划。 李军，１９７３ 年生，教授，博士生导 师，主要研究方向为大数据分析与处 理、卫星智能规划和控制。 ·６６０· 智 能 系 统 学 报 第 １２ 卷