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