2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

无人飞行器集群智能调度技术综述

杜永浩 邢立宁 蔡昭权

杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2020, 46(2): 222-241. doi: 10.16383/j.aas.c170681
引用本文: 杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2020, 46(2): 222-241. doi: 10.16383/j.aas.c170681
DU Yong-Hao, XING Li-Ning, CAI Zhao-Quan. Survey on Intelligent Scheduling Technologies for Unmanned Flying Craft Clusters. ACTA AUTOMATICA SINICA, 2020, 46(2): 222-241. doi: 10.16383/j.aas.c170681
Citation: DU Yong-Hao, XING Li-Ning, CAI Zhao-Quan. Survey on Intelligent Scheduling Technologies for Unmanned Flying Craft Clusters. ACTA AUTOMATICA SINICA, 2020, 46(2): 222-241. doi: 10.16383/j.aas.c170681

无人飞行器集群智能调度技术综述


DOI: 10.16383/j.aas.c170681
详细信息
    作者简介:

    杜永浩   国防科技大学系统工程学院博士研究生. 2017年获国防科技大学硕士学位.主要研究方向为智能优化理论、方法与应用. E-mail: duyonghao15@163.com

    蔡昭权   惠州学院教授. 2006年获华中科技大学硕士学位.主要研究方向为计算机网络, 智能计算和数据库. E-mail: 13502279833@126.com

    通讯作者: 邢立宁   国防科技大学系统工程学院研究员, 全国优秀博士学位论文获得者, 入选教育部新世纪优秀人才计划, 湖南省自然科学杰出青年基金获得者. 2009年获国防科技大学博士学位.主要研究方向为智能优化理论、方法与应用.本文通信作者. E-mail: xinglining@gmail.com
  • 本文责任编委 孙富春
  • 基金项目:

    国家自然科学基金 61773120

    国家自然科学基金 61873328

    国家自然科学基金 61772225

    国家杰出青年科学基金 61525304

    高等学校全国优秀博士学位论文作者专项资金 2014-92

    广东省自然科学基金 2018B030311046

    广东省自然科学杰出青年基金 2017KZDXM081

    湖南省研究生科研创新项目 CX2018B022

Survey on Intelligent Scheduling Technologies for Unmanned Flying Craft Clusters

More Information
    Author Bio:

    DU Yong-Hao Ph. D. candidate at the College of Systems Engineering, National University of Defense Technology. He received his master degree from National University of Defense Technology in 2017. His research interest covers intelligent optimization theory, method and application

    CAI Zhao-Quan Professor at Huizhou University. He received his master degree from Huazhong University of Science and Technology in 2006. His research interest covers computer networks, intelligent computing and database

    Corresponding author: XING Li-Ning Professor at the College of Systems Engineering, National University of Defense Technology. He was awarded with the National Excellent Ph. D. Dissertation of China and the New Century Excellent Researcher of Ministry of Education. He is also supported by the Natural Science Funds for Distinguished Young Scholar of Hunan Province. He received his Ph. D. degree from National University of Defense Technology in 2009. His research interest covers intelligent optimization theory, method and application. Corresponding author of this paper
  • Recommended by Associate Editor SUN Fu-Chun
  • Fund Project:

    Supported by National Natural Science Foundation of China 61773120

    Supported by National Natural Science Foundation of China 61873328

    Supported by National Natural Science Foundation of China 61772225

    National Science Fund for Distinguished Young Scholars 61525304

    National Excellent Doctoral Dissertation Foundation of China 2014-92

    Natural Science Foundation of Guangdong 2018B030311046

    Foundation for Distinguished Young Talents in Higher Education of Guangdong 2017KZDXM081

    Hunan Postgraduate Research Innovation Project CX2018B022

  • 摘要: 随着飞行器技术的快速发展, 以无人机和卫星为代表的无人飞行器在集群任务中得到广泛应用, 但日益增长的多样化任务需求和不平衡、不充足的任务资源也对无人飞行器集群调度技术提出新的挑战.针对无人飞行器任务类型特点, 分别从无人机群和多星两个角度出发, 介绍了无人机群访问、打击和察打一体化任务调度技术进展, 阐述了多星成像、数传与天地一体化任务调度研究成果.同时, 梳理了无人机群和多星任务调度问题的主要约束与收益指标, 综述了无人机群和多星任务调度常用的智能优化算法.最后, 面向未来无人飞行器技术应用需求, 指出了无人飞行器集群智能调度技术进一步的研究方向.
    本文责任编委 孙富春
    Recommended by Associate Editor SUN Fu-Chun
  • 图  1  无人飞行器集群任务分类图

    Fig.  1  Mission classification of unmanned flying craft clusters

    图  2  覆盖任务的优化策略

    Fig.  2  Optimization strategy for coverage missions

    图  3  无人机群智能调度问题常见约束

    Fig.  3  Common constraints in intelligent scheduling for unmanned aerial vehicles

    图  4  敏捷卫星与传统卫星成像策略对比

    Fig.  4  Comparison on observation strategies between agile satellites and traditional satellites

    图  5  多星智能调度问题常见约束

    Fig.  5  Common constraints in intelligent scheduling for multi-satellites

  • [1] Luo C, Yu L J, Ren P. A vision-aided approach to perching a bioinspired unmanned aerial vehicle. IEEE Transactions on Industrial Electronics, 2018, 65(5): 3976-3984 doi:  10.1109/TIE.2017.2764849
    [2] De Castro A I, Torres-Sánchez J T, Peña J M, Jiménez-Brenes F M, Csillik O, López-Granados F. An automatic random forest-OBIA algorithm for early weed mapping between and within crop rows using UAV imagery. Remote Sensing, 2018, 10(2): Article No. 285 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=remotesensing-10-00285
    [3] Kim B O, Yun K H, Chang T S, Bahk J J, Kim S P. A preliminary study on UAV photogrammetry for the hyanho coast near the military reservation zone, eastern coast of Korea. Ocean and Polar Research, 2017, 39(2): 159-168 doi:  10.4217/OPR.2017.39.2.159
    [4] 王宁, 王永.基于模糊不确定观测器的四旋翼飞行器自适应动态面轨迹跟踪控制.自动化学报, 2018, 44(4): 685-695 doi:  10.16383/j.aas.2017.c160481

    Wang Ning, Wang Yong. Fuzzy uncertainty observer based adaptive dynamic surface control for trajectory tracking of a quadrotor. Acta Automatica Sinica, 2018, 44(4): 685-695 doi:  10.16383/j.aas.2017.c160481
    [5] 罗木生, 姜青山, 侯学隆.直升机使用吊声应召反潜兵力需求仿真.系统仿真学报, 2012, 24(6): 1277-1281, 1286 http://d.old.wanfangdata.com.cn/Periodical/xtfzxb201206025

    Luo Mu-Sheng, Jiang Qing-Shan, Hou Xue-Long. Simulation of optimum helicopter force in definite second time submarine search by dipping sonar. Journal of System Simulation, 2012, 24(6): 1277-1281, 1286 http://d.old.wanfangdata.com.cn/Periodical/xtfzxb201206025
    [6] Lee T K, Baek S H, Choi Y H, Oh S Y. Smooth coverage path planning and control of mobile robots based on high-resolution grid map representation. Robotics and Autonomous Systems, 2011, 59(10): 801-812 doi:  10.1016/j.robot.2011.06.002
    [7] 陈海, 王新民, 焦裕松, 李俨.一种凸多边形区域的无人机覆盖航迹规划算法.航空学报, 2010, 31(9): 1082-1088 http://d.old.wanfangdata.com.cn/Periodical/hkxb201009015

    Chen Hai, Wang Xin-Min, Jiao Yu-Song, Li Yan. An algorithm of coverage flight path planning for UAVs in convex polygon areas. Acta Aeronautica et Astronautica Sinica, 2010, 31(9): 1082-1088 http://d.old.wanfangdata.com.cn/Periodical/hkxb201009015
    [8] Kolling A, Kleiner A. Multi-UAV motion planning for guaranteed search. In: Proceedings of the 12th International Conference on Autonomous Agents and Multi-agent Systems. St. Paul, USA: IFAAMS, 2013. 79-86
    [9] Barrientos A, Colorado J, del Cerro J, Martinez A, Rossi C, Sanz D, et al. Aerial remote sensing in agriculture: a practical approach to area coverage and path planning for fleets of mini aerial robots. Journal of Field Robotics, 2011, 28(5): 667-689 doi:  10.1002/rob.20403
    [10] 晋一宁, 吴炎烜, 范宁军.群无人机动态环境分布式持续覆盖算法.北京理工大学学报, 2016, 36(6): 588-592 http://d.old.wanfangdata.com.cn/Periodical/bjlgdxxb201606007

    Jin Yi-Ning, Wu Yan-Xuan, Fan Ning-Jun. Distributed cooperative control of swarm UAVs for dynamic environment persistent coverage. Transactions of Beijing Institute of Technology, 2016, 36(6): 588-592 http://d.old.wanfangdata.com.cn/Periodical/bjlgdxxb201606007
    [11] Varela G, Caamaño P, Orjales F, Deibe Á, López-Peña F, Duro R J. Autonomous UAV based search operations using Constrained Sampling Evolutionary Algorithms. Neurocomputing, 2014, 132: 54-67 doi:  10.1016/j.neucom.2013.03.060
    [12] Lanillos P, Gan S K, Besada-Portas E, Pajares G, Sukkarieh S. Multi-UAV target search using decentralized gradient-based negotiation with expected observation. Information Sciences, 2014, 282: 92-110 doi:  10.1016/j.ins.2014.05.054
    [13] Wang J J, Zhang Y F, Geng L, Fuh J Y H, Teo S H. Mission planning for heterogeneous tasks with heterogeneous UAVs. In: Proceedings of the 13th International Conference on Control Automation Robotics & Vision (ICARCV). Singapore: IEEE, 2014. 1484-1489
    [14] 符小卫, 魏广伟, 高晓光.不确定环境下多无人机协同区域搜索算法.系统工程与电子技术, 2016, 38(4): 821-827 http://d.old.wanfangdata.com.cn/Periodical/xtgcydzjs201604015

    Fu Xiao-Wei, Wei Guang-Wei, Gao Xiao-Guang. Cooperative area search algorithm for multi-UAVs in uncertainty environment. Systems Engineering and Electronics, 2016, 38(4): 821-827 http://d.old.wanfangdata.com.cn/Periodical/xtgcydzjs201604015
    [15] Ru C J, Qi X M, Guan X N. Distributed cooperative search control method of multiple UAVs for moving target. International Journal of Aerospace Engineering, 2015, 2015: Article No. 317953
    [16] 马纯超, 尹栋, 朱华勇.网络化战场环境下多无人机调度问题.火力与控制指挥, 2015, 40(10): 31-36 http://d.old.wanfangdata.com.cn/Periodical/hlyzhkz201510008

    Ma Chun-Chao, Yin Dong, Zhu Hua-Yong. A study on multi-UAVs scheduling in networked battlefield. Fire Control & Command Control, 2015, 40(10): 31-36 http://d.old.wanfangdata.com.cn/Periodical/hlyzhkz201510008
    [17] 倪谣, 周德云, 马云红, 贺宝财.基于MILP模型的多无人机对地攻击任务分配.火力与指挥控制, 2008, 33(11): 62-65 doi:  10.3969/j.issn.1002-0640.2008.11.018

    Ni Yao, Zhou De-Yun, Ma Yun-Hong, He Bao-Cai. The air-to-ground tasks assignment for multi-UAV based mixed integer linear programming. Fire Control & Command Control, 2008, 33(11): 62-65 doi:  10.3969/j.issn.1002-0640.2008.11.018
    [18] 周小程, 严建钢, 谢宇鹏, 翟鸿君.多无人机对地攻击任务分配算法.海军航空工程学院学报, 2012, 27(3): 308-312 http://d.old.wanfangdata.com.cn/Periodical/hjhkgcxyxb201203003

    Zhou Xiao-Cheng, Yan Jian-Gang, Xie Yu-Peng, Zhai Hong-Jun. Task distributed algorithmic for multi-UAV based on auction mechanism. Journal of Naval Aeronautical and Astronautical University, 2012, 27(3): 308-312 http://d.old.wanfangdata.com.cn/Periodical/hjhkgcxyxb201203003
    [19] Weinstein A L, Schumacher C. UAV scheduling via the vehicle routing problem with time windows. In: Proceedings of the AIAA Infotech@Aerospace 2007 Conference and Exhibit. Rohnert Park: AIAA, 2007.
    [20] Zhen Z Y, Xing D J, Gao C. Cooperative search-attack mission planning for multi-UAV based on intelligent self-organized algorithm. Aerospace Science and Technology, 2018, 76: 402-411 doi:  10.1016/j.ast.2018.01.035
    [21] 常一哲, 李战武, 杨海燕, 罗卫平, 徐安.未来中远距协同空战多目标攻击决策研究.火力与指挥控制, 2015, 40(6): 36-40 doi:  10.3969/j.issn.1002-0640.2015.06.009

    Chang Yi-Zhe, Li Zhan-Wu, Yang Hai-Yan, Luo Wei-Ping, Xu An. A decision-making for multiple target attack based on characteristic of future long-range cooperative air combat. Fire Control & Command Control, 2015, 40(6): 36-40 doi:  10.3969/j.issn.1002-0640.2015.06.009
    [22] 陈洁钰, 姚佩阳, 唐剑, 贾方超.多无人机分布式协同动态目标分配方法.空军工程大学学报(自然科学版), 2014, 15(6): 11-16 doi:  10.3969/j.issn.1009-3516.2014.06.003

    Chen Jie-Yu, Yao Pei-Yang, Tang Jian, Jia Fang-Chao. Multi-UAV decentralized coopertative dynamic target assignment method. Journal of Air Force Engineering University (Natural Science Edition), 2014, 15(6): 11-16 doi:  10.3969/j.issn.1009-3516.2014.06.003
    [23] 刘重, 高晓光, 符小卫, 牟之英.未知环境下异构多无人机协同搜索打击中的联盟组建.兵工学报, 2015, 36(12): 2284-2297 doi:  10.3969/j.issn.1000-1093.2015.12.011

    Liu Chong, Gao Xiao-Guang, Fu Xiao-Wei, Mu Zhi-Ying. Coalition formation of multiple heterogeneous unmanned aerial vehicles in cooperative search and attack in unknown environment. Acta Armamentarii, 2015, 36(12): 2284-2297 doi:  10.3969/j.issn.1000-1093.2015.12.011
    [24] Deng Q B, Yu J Q, Wang N F. Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes. Chinese Journal of Aeronautics, 2013, 26(5): 1238-1250 doi:  10.1016/j.cja.2013.07.009
    [25] 吴蔚楠, 关英姿, 郭继峰, 崔乃刚.基于SEAD任务特性约束的协同任务分配方法.控制与决策, 2017, 32(9): 1574-1582 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201709005

    Wu Wei-Nan, Guan Ying-Zi, Guo Ji-Feng, Cui Nai-Gang. Research on cooperative task assignment method used to the mission SEAD with real constraints. Control and Decision, 2017, 32(9): 1574-1582 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201709005
    [26] 戚泽旸, 王强, 黄英杰.多无人机侦察打击任务分配建模仿真.计算机仿真, 2015, 32(9): 142-146, 188 doi:  10.3969/j.issn.1006-9348.2015.09.031

    Qi Ze-Yang, Wang Qiang, Huang Ying-Jie. Task assignment modeling and simulation for cooperative surveillance and strike of multiple unmanned aerial vehicle. Computer Simulation, 2015, 32(9): 142-146, 188 doi:  10.3969/j.issn.1006-9348.2015.09.031
    [27] Zeng J, Yang X K, Yang L Y, Shen G Z. Modeling for UAV resource scheduling under mission synchronization. Journal of Systems Engineering and Electronics, 2010, 21(5): 821-826 doi:  10.3969/j.issn.1004-4132.2010.05.016
    [28] Di Franco C, Buttazzo G. Coverage path planning for UAVs photogrammetry with energy and resolution constraints. Journal of Intelligent & Robotic Systems, 2016, 83(3-4): 445-462 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=ccaa7b190871ef35e766f3826444f298
    [29] 李炜, 张伟.基于粒子群算法的多无人机任务分配方法.控制与决策, 2010, 25(9): 1359-1363, 1368 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201009016

    Li Wei, Zhang Wei. Method of tasks allocation of multi-UAVs based on particles swarm optimization. Control and Decision, 2010, 25(9): 1359-1363, 1368 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201009016
    [30] Kim J, Morrison J R. On the concerted design and scheduling of multiple resources for persistent UAV operations. Journal of Intelligent & Robotic Systems, 2014, 74(1-2), 479-498
    [31] 罗德林, 吴顺祥, 段海滨, 李茂青.无人机协同多目标攻击空战决策研究.系统仿真学报, 2008, 20(24): 6778-6782

    Luo De-Lin, Wu Shun-Xiang, Duan Hai-Bin, Li Mao-Qing. Air-combat decision-making for UAVs cooperatively attacking multiple targets. Journal of Systems Simulation, 2008, 20(24): 6778-6782
    [32] Kim M H, Baik H, Lee S. Resource welfare based task allocation for UAV team with resource constraints. Journal of Intelligent & Robotic Systems, 2015, 77(3-4): 611-627 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=9ab4b76628dd4d0c1274bd4c2e67054a
    [33] 张民强, 宋建梅, 薛瑞彬.通信距离受限下多无人机分布式协同搜索.系统工程理论与实践, 2015, 35(11): 2980-2986 doi:  10.12011/1000-6788(2015)11-2980

    Zhang Min-Qiang, Song Jian-Mei, Xue Rui-Bin. Multiple UAVs cooperative search under limited communication range. Systems Engineering-Theory & Practice, 2015, 35(11): 2980-2986 doi:  10.12011/1000-6788(2015)11-2980
    [34] Sujit P B, Sousa J B. Multi-UAV task allocation with communication faults. In: Proceedings of the 2012 American Control Conference. Montreal, Canada: IEEE, 2012. 3724-3729
    [35] Mirzaei M, Gordon B W. Cooperative multi-UAV search problem with communication delay. In: Proceedings of the 2010 AIAA Guidance, Navigation, and Control Conference. Toronto, Canada: AIAA, 2010. 519-524
    [36] Ahmadzadeh A, Sayyar-Roudsari B, Homaifar A. A hybrid projected gradient-evolutionary search algorithm for capacitated multi-source multiuavs scheduling with time windows. Recent Developments in Cooperative Control and Optimization. Boston, USA: Springer, 2004. 1-21
    [37] 伍思远.无人机安保任务的调度研究---以杨浦区为例.科技风, 2016, (9): 143 doi:  10.3969/j.issn.1671-7341.2016.09.127
    [38] Ramirez-Atencia C, Bello-Orgaz G, R-Moreno M D, Camacho D. A hybrid MOGA-CSP for multi-UAV mission planning. In: Proceedings of the 2015 Companion Publication of the the 2015 Annual Conference on Genetic and Evolutionary Computation. Madrid, Spain: ACM, 2015. 1205-1208
    [39] 曹文静, 杨林.多无人机自主协同方法协同性能研究.飞航导弹, 2017, (5): 43-49 http://d.old.wanfangdata.com.cn/Periodical/fhdd201705010
    [40] Shima T, Schumacher C. Assignment of cooperating UAVs to simultaneous tasks using genetic algorithms. In: Proceedings of the 2005 Guidance, Navigation, and Control Conference and Exhibit. San Francisco, USA: AIAA, 2005. 1-14
    [41] 仲筱艳, 黄大庆.一种典型任务的多无人机协同任务分配算法研究.自动化技术与应用, 2016, 35(8): 7-12, 22 http://d.old.wanfangdata.com.cn/Periodical/hljzdhjsyyy201608002

    Zhong Xiao-Yan, Huang Da-Qing. Research of cooperation task allocation algorithm for a kind of typical mission. Techniques of Automation and Applications, 2016, 35(8): 7-12, 22 http://d.old.wanfangdata.com.cn/Periodical/hljzdhjsyyy201608002
    [42] Khosiawan Y, Park Y, Moon I, Nilakantan J M, Nielsen I. Task scheduling system for UAV operations in indoor environment. Neural Computing and Applications, 2019, 31(9): 5431-5459 doi:  10.1007/s00521-018-3373-9
    [43] 赵明, 苏小红, 马培军, 赵玲玲.复杂多约束UAVs协同目标分配的一种统一建模方法.自动化学报, 2012, 38(12): 2038-2048 doi:  10.3724/SP.J.1004.2012.02038

    Zhao Ming, Su Xiao-Hong, Ma Pei-Jun, Zhao Ling-Ling. A unified modeling method of UAVs cooperative target assignment by complex multi-constraint conditions. Acta Automatica Sinica, 2012, 38(12): 2038-2048 doi:  10.3724/SP.J.1004.2012.02038
    [44] Wang Z, Liu L, Long T, Wen Y L. Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding. Chinese Journal of Aeronautics, 2018, 31(2): 339-350 doi:  10.1016/j.cja.2017.09.005
    [45] 尹高扬, 周绍磊, 莫骏超, 曹明川, 康宇航.基于多目标粒子群优化的无人机协同多任务分配.计算机与现代化, 2016, (8): 7-11 doi:  10.3969/j.issn.1006-2475.2016.08.002

    Yin Gao-Yang, Zhou Shao-Lei, Mo Jun-Chao, Cao Ming-Chuan, Kang Yu-Hang. Multiple task assignment for cooperating unmanned aerial vehicles using multi-objective particle swarm optimization. Computer and Modernization, 2016, (8): 7-11 doi:  10.3969/j.issn.1006-2475.2016.08.002
    [46] Oh G, Kim Y, Ahn J, Choi H L. Task allocation of multiple UAVs for cooperative parcel delivery. Advances in Aerospace Guidance, Navigation and Control. Cham, Germany: Springer, 2018. 443-454
    [47] Oh G, Kim Y, Ahn J, Choi H L. PSO-based Optimal task allocation for cooperative timing missions. IFAC-PapersOnLine, 2016, 49(17): 314-319 doi:  10.1016/j.ifacol.2016.09.054
    [48] 赵宏伟, 许锦州.一种基于在线仿真的多无人机任务调度方法研究.见: 2009年中国高校通信类院系学术研讨会论文集.北京, 中国: 电子工业出版社, 2009. 54-59
    [49] Zhang J X, Zhu Q, Shen F Q, Miao S X, Cao Z Y, Weng Q Q. Hierarchical scheduling method of UAV resources for emergency surveying. In: Proceedings of the 2015 the International Conference on Intelligent Earth Observing and Applications. Guilin, China: SPIE, 2015. Article No. 98083B
    [50] 郑晓辉.无人机协同作战的目标分配算法研究.兵工自动化, 2014, 33(3): 16-18, 31 http://d.old.wanfangdata.com.cn/Periodical/bgzdh201403005

    Zheng Xiao-Hui. Research on target assignment algorithm for multi-UAV cooperative combat. Ordnance Industry Automation, 2014, 33(3): 16-18, 31 http://d.old.wanfangdata.com.cn/Periodical/bgzdh201403005
    [51] 刘毅, 李为民, 邢清华, 徐小来.基于双层规划的攻击无人机协同目标分配优化.系统工程与电子技术, 2010, 32(3): 579-583 http://d.old.wanfangdata.com.cn/Periodical/xtgcydzjs201003031

    Li Yi, Li Wei-Min, Xing Qing-Hua, Xu Xiao-Lai. Cooperative mission assignment optimization of unmanned combat aerial vehicles based on bilevel programming. Systems Engineering and Electronics, 2010, 32(3): 579-583 http://d.old.wanfangdata.com.cn/Periodical/xtgcydzjs201003031
    [52] Wu H S, Li H, Xiao R B, Liu J. Modeling and simulation of dynamic ant colony$'$s labor division for task allocation of UAV swarm. Physica A: Statistical Mechanics and Its Applications, 2018, 491: 127-141 doi:  10.1016/j.physa.2017.08.094
    [53] Perez-Carabaza S, Besada-Portas E, Lopez-Orozco J A, de la Cruz J M. Ant colony optimization for multi-UAV minimum time search in uncertain domains. Applied Soft Computing, 2018, 62: 789-806 doi:  10.1016/j.asoc.2017.09.009
    [54] Gao C, Zhen Z Y, Gong H J. A self-organized search and attack algorithm for multiple unmanned aerial vehicles. Aerospace Science and Technology, 2016, 54: 229-240 doi:  10.1016/j.ast.2016.03.022
    [55] Cekmez U, Ozsiginan M, Sahingoz O K. A UAV path planning with parallel ACO algorithm on CUDA platform. In: Proceedings of the 2014 International Conference on Unmanned Aircraft Systems (ICUAS). Orlando, USA: IEEE, 2014. 347-354
    [56] 陆志强, 刘欣仪.考虑资源转移时间的资源受限项目调度问题的算法.自动化学报, 2018, 44(6): 1028-1036 doi:  10.16383/j.aas.2017.c160834

    Lu Zhi-Qiang, Liu Xin-Yi. Algorithm for resource-constrained project scheduling problem with resource transfer time. Acta Automatica Sinica, 2018, 44(6): 1028-1036 doi:  10.16383/j.aas.2017.c160834
    [57] Ramirez-Atencia C, Bello-Orgaz G, R-Moreno M D, Camacho D. A simple CSP-based model for unmanned air vehicle mission planning. In: Proceedings of the 2014 International Symposium on Innovations in Intelligent Systems and Applications. Alberobello, Italy: IEEE, 2014. 146-153
    [58] Turker T, Yilmaz G, Sahingoz O K. GPU-accelerated flight route planning for multi-UAV systems using simulated annealing. In: Proceedings of the 17th International Conference on Artificial Intelligence: Methodology, Systems, and Applications. Varna, Bulgaria: Springer, 2016. 279-288
    [59] Darrah M A, Niland W, Stolarik B. Multiple UAV Task Allocation for an Electronic Warfare Mission Comparing Genetic Algorithms and Simulated Annealing (Preprint), Technical Report AFRL-VA-WP-TP-2006-340, Air Force Research Laboratory, USA, 2006
    [60] 施蓉花, 吴庆宪, 姜长生.无人机协同攻击的混合粒子群算法.火力与指挥控制, 2009, 34(9): 10-13 doi:  10.3969/j.issn.1002-0640.2009.09.003

    Shi Rong-Hua, Wu Qing-Xian, Jiang Chang-Sheng. Heuristic particle swarm optimization algorithm of multi-UAV cooperative attacking logic. Fire Control & Command, 2009, 34(9): 10-13 doi:  10.3969/j.issn.1002-0640.2009.09.003
    [61] Zhang Y Z, Li J W, Hu B, Zhang J D. An improved PSO algorithm for solving multi-UAV cooperative reconnaissance task decision-making problem. In: Proceedings of the 2016 International Conference on Aircraft Utility Systems (AUS). Beijing, China: IEEE, 2016. 434-437
    [62] Cao L, Tan H S, Peng H, Pan M C. Multiple UAVs hierarchical dynamic task allocation based on PSO-FSA and decentralized auction. In: Proceedings of the 2014 International Conference on Robotics and Biomimetics (ROBIO 2014). Bali, Indonesia: IEEE, 2014. 2368-2373
    [63] 石岭.基于改进的模拟退火PSO无人机资源分配[硕士学位论文], 南京航空航天大学, 中国, 2015

    Shi Ling. UAVs Resource Allocation based on Improved SA-PSO [Master dissertation], Nanjing University of Aeronautics and Astronautics, China, 2015
    [64] 梁国强, 康宇航, 邢志川, 尹高扬.基于离散粒子群优化的无人机协同多任务分配.计算机仿真, 2018, 35(2): 22-28 doi:  10.3969/j.issn.1006-9348.2018.02.005

    Liang Guo-Qiang, Kang Yu-Hang, Xing Zhi-Chuan, Yin Gao-Yang. UAV cooperative multi-task assignment based on discrete particle swarm optimization algorithm. Computer Simulation, 2018, 35(2): 22-28 doi:  10.3969/j.issn.1006-9348.2018.02.005
    [65] 曹攀峰, 崔升.考虑信息延迟的无人机分布式协同搜索算法.电光与控制, 2010, 17(3): 27-29, 34 doi:  10.3969/j.issn.1671-637X.2010.03.007

    Cao Pan-Feng, Cui Sheng. An cooperative search algorithm for multi-UAV with time-delays. Electronics Optics & Control, 2010, 17(3): 27-29, 34 doi:  10.3969/j.issn.1671-637X.2010.03.007
    [66] Kingston D B, Beard R W, Holt R S. Decentralized perimeter surveillance using a team of UAVs. IEEE Transactions on Robotics, 2008, 24(6): 1394-1404
    [67] Li W J, Bi Y Z, Zhu X F, Yuan C A, Zhang X B. Hybrid swarm intelligent parallel algorithm research based on multi-core clusters. Microprocessors and Microsystems, 2016, 47: 151-160 doi:  10.1016/j.micpro.2016.05.009
    [68] Yao P, Wang H L, Ji H X. Multi-UAVs tracking target in urban environment by model predictive control and Improved Grey Wolf Optimizer. Aerospace Science and Technology, 2016, 55: 131-143 doi:  10.1016/j.ast.2016.05.016
    [69] 马焱, 赵捍东, 张玮, 陈白禹, 邵先锋, 张晓东, 等.基于自适应烟花算法的多无人机任务分配.电光与控制, 2018, 25(1): 37-43

    Ma Yan, Zhao Han-Dong, Zhang Wei, Chen Bai-Yu, Shao Xian-Feng, Zhang Xiao-Dong, et al. Task allocation for multi-UAVs based on adaptive fireworks algorithm. Electronics Optics & Control, 2018, 25(1): 37-43
    [70] 刘跃峰, 张安.有人机/无人机编队协同任务分配方法.系统工程与电子技术, 2010, 32(3): 584-588 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtgcydzjs201003032

    Liu Yue-Feng, Zhang An. Cooperative task assignment method of manned/unmanned aerial vehicle formation. Systems Engineering and Electronics, 2010, 32(3): 584-588 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtgcydzjs201003032
    [71] 刘洋, 陈英武, 谭跃进.一种有新任务到达的多卫星动态调度模型与方法.系统工程理论与实践, 2005, 25(4): 35-41 doi:  10.3321/j.issn:1000-6788.2005.04.006

    Liu Yang, Chen Ying-Wu, Tan Yue-Jin. A modeling and algorithm for the new tasks$'$ arriving in multi-satellites dynamic scheduling. Systems Engineering-Theory & Practice, 2005, 25(4): 35-41 doi:  10.3321/j.issn:1000-6788.2005.04.006
    [72] Qiu D S, He C, Liu J, Ma M H. A dynamic scheduling method of earth-observing satellites by employing rolling horizon strategy. The Scientific World Journal, 2013, 2013: Article No. 304047
    [73] Niu X N, Zhai X J, Tang H, Wu L X. Multi-satellite scheduling approach for dynamic areal tasks triggered by emergent disasters. In: Proceedings of the 2016 International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Prague, Czech Republic: ISPRS, 2016. 475-481
    [74] 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
    [75] Lemaȋtre M, Verfaillie G, Jouhaud F, Lachiver J M, Bataille N. Selecting and scheduling observations of agile satellites. Aerospace Science and Technology, 2002, 6(5): 367-381 doi:  10.1016/S1270-9638(02)01173-2
    [76] 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 doi:  10.1016/j.ejor.2015.03.011
    [77] 章登义, 郭雷, 王骞, 邹华.一种面向区域目标的敏捷成像卫星单轨调度方法.武汉大学学报$\cdot$信息科学版, 2014, 39(8): 901-905, 922 http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb201408004

    Zhang Deng-Yi, Guo Lei, Wang Qian, Zou Hua. An improved single-orbit scheduling method for agile imaging satellite towards area target. Geomatics and Information Science of Wuhan University, 2014, 39(8): 901-905, 922 http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb201408004
    [78] Sarkheyli A, Bagheri A, Ghorbani-Vaghei B, Askari-Moghadam R. Using an effective tabu search in interactive resources scheduling problem for LEO satellites missions. Aerospace Science and Technology, 2013, 29(1): 287-295 doi:  10.1016/j.ast.2013.04.001
    [79] Liu X L, Laporte G, Chen Y W, He R J. An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computers & Operations Research, 2017, 86: 41-53 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=1176d7c33ea3f15f8326d945dd22d54b
    [80] He L, Liu X L, Laporte G, Chen Y W, Chen Y G. An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling. Computers & Operations Research, 2018, 100: 12-25 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f04b55028114ff3001cd437b6bde8ebe
    [81] Parish D A. A Genetic Algorithm Approach to Automating Satellite Range Scheduling [Master dissertation], Air Force Institute of Technology, USA, 1994.
    [82] 朱小满, 王钧, 李军, 景宁. SAR卫星成像任务规划的DHIP方法.计算机工程与科学, 2011, 33(9): 179-183 doi:  10.3969/j.issn.1007-130X.2011.09.032

    Zhu Xiao-Man, Wang Jun, Li Jun, Jing Ning. A DHIP algorithm for SAR satellite imaging planning. Computer Engineering and Science, 2011, 33(9): 179-183 doi:  10.3969/j.issn.1007-130X.2011.09.032
    [83] 王沛.基于分支定价的多星多站集成调度方法研究[博士学位论文], 国防科学技术大学, 中国, 2011

    Wang Pei. Research on Branch-and-Price based Multi-satellite Multi-station Integrated Scheduling Method [Ph. D. dissertation], National University of Defense Technology, China, 2011
    [84] Marinelli F, Nocella S, Rossi F, Smriglio S. A Lagrangian heuristic for satellite range scheduling with resource constraints. Computers & Operations Research, 2011, 38(11): 1572-1583
    [85] Pemberton J C, Galiber Ⅲ F. A constraint-based approach to satellite scheduling. In: Proceedings of the 2001 Constraint Programming and Large Scale Discrete Optimization. Piscataway, USA: American Mathematical Society, 2001. 101-114
    [86] 李云峰, 武小悦.基于多星联合侦察的卫星数传调度问题模型.北京航空航天大学学报, 2008, 34(8): 948-951, 960 http://d.old.wanfangdata.com.cn/Periodical/bjhkhtdxxb200808020

    Li Yun-Feng, Wu Xiao-Yue. Model of satellite data transmission scheduling problem based on multi-satellite combined reconnaissance. Journal of Beijing University of Aeronautics and Astronautics, 2008, 34(8): 948-951, 960 http://d.old.wanfangdata.com.cn/Periodical/bjhkhtdxxb200808020
    [87] Bianchessi N, Righini G. Planning and scheduling algorithms for the COSMO-SkyMed constellation. Aerospace Science and Technology, 2008, 12(7): 535-544 doi:  10.1016/j.ast.2008.01.001
    [88] Xu B, Wang D H, Liu W X, Sun G F. A hybrid navigation constellation inter-satellite link assignment algorithm for the integrated optimization of the inter-satellite observing and communication performance. In: Proceedings of the 2015 China Satellite Navigation Conference. Berlin, Germany: Springer, 2015. 283-296
    [89] 陈祥国, 武小悦.基于解构造图的卫星数传调度ACO算法.系统工程与电子技术, 2010, 32(3): 592-597 http://d.old.wanfangdata.com.cn/Periodical/xtgcydzjs201003034

    Chen Xiang-Guo, Wu Xiao-Yue. ACO algorithm of satellite data transmission scheduling based on solution construction graph. Systems Engineering and Electronics, 2010, 32(3): 592-597 http://d.old.wanfangdata.com.cn/Periodical/xtgcydzjs201003034
    [90] Corrao G, Falone R, Gambi E, Spinsante S. Ground station activity planning through a multi-algorithm optimisation approach. In: Proceedings of the 2012 AESS European Conference on Satellite Telecommunications (ESTEL). Rome, Italy: IEEE, 2012. 1-6
    [91] Skobelev P, Simonova E V, Ivanov A, Mayorov I, Travin V, Zhilyaev A. Real time scheduling of data transmission sessions in a microsatellites swarm and ground stations network based on multi-agent technology. In: Proceedings of the 2014 International Conference on Evolutionary Computation Theory and Applications. Rome, Italy: SciTePress, 2014. 153-159
    [92] 王远振, 赵坚, 聂成.多卫星--地面站系统的Petri网模型研究.空军工程大学学报(自然科学版), 2003, 4(2): 7-11 doi:  10.3969/j.issn.1009-3516.2003.02.002

    Wang Yuan-Zhen, Zhao Jian, Nie Cheng. Study on Petri net model for multi-satellites-ground station system. Journal of Air Force Engineering University (Natural Science Edition), 2003, 4(2): 7-11 doi:  10.3969/j.issn.1009-3516.2003.02.002
    [93] 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
    [94] Li Z X, Li J, Mu W T. Space-ground TT&C resources integrated scheduling based on the hybrid ant colony optimization. In: Proceedings of the 28th Conference of Spacecraft TT&C Technology. Singapore: Springer, 2016. 179-196.
    [95] Chen H, Wu J J, Shi W Y, Li J, Zhong Z N. 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
    [96] Sun K, Yang Z Y, Wang P, Chen Y W. Mission planning and action planning for agile earth-observing satellite with genetic algorithm. Journal of Harbin Institute of Technology, 2013, 20(5): 51-56 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=hebgydxxb-e201305010
    [97] Zhu W M, Hu X X, Xia W, Jin P. A two-phase genetic annealing method for integrated Earth observation satellite scheduling problems. Soft Computing, 2019, 23(1): 181-196 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=67afc6f1ee6311f76d89bca4f1610710
    [98] Dilkina B, Havens B. Agile Satellite Scheduling via Permutation Search with Constraint Propagation. Actenum Corporation: Vancouver Canada, 2005: 1-20
    [99] Xu R, Chen H P, Liang X L, Wang H M. Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization. Expert Systems with Applications, 2016, 51: 195-206 doi:  10.1016/j.eswa.2015.12.039
    [100] Zhu K J, Li J F, Baoyin H X. Satellite scheduling considering maximum observation coverage time and minimum orbital transfer fuel cost. Acta Astronautica, 2010, 66(1-2): 220-229 doi:  10.1016/j.actaastro.2009.05.029
    [101] 邱涤珊, 郭浩, 贺川, 伍国华.敏捷成像卫星多星密集任务调度方法.航空学报, 2013, 34(4): 882-889 http://d.old.wanfangdata.com.cn/Periodical/hkxb201304019

    Qiu Di-Shan, Guo Hao, He Chuan, Wu Guo-Hua. Intensive task scheduling method for multi-agile imaging satellites. Acta Aeronautica et Astronautica Sinica, 2013, 34(4): 882-889 http://d.old.wanfangdata.com.cn/Periodical/hkxb201304019
    [102] 范国伟, 常琳, 杨秀彬, 王旻, 王绍举.面向新颖成像模式敏捷卫星的联合执行机构控制方法.自动化学报, 2017, 43(10): 1858-1868 doi:  10.16383/j.aas.2017.c160579

    Fan Guo-Wei, Chang Lin, Yang Xiu-Bin, Wang Min, Wang Shao-Ju. Control strategy of hybrid actuator for novel imaging modes of agile satellites. Acta Automatica Sinica, 2017, 43(10): 1858-1868 doi:  10.16383/j.aas.2017.c160579
    [103] 赵琳, 王硕, 郝勇, 刘源, 柴毅.基于地面任务-空间姿态映射的敏捷卫星任务规划.航空学报, 2018, 39(10): Article No. 322066 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=hkxb201810014

    Zhao Lin, Wang Shuo, Hao Yong, Liu Yuan, Chai Yi. Mission planning for agile satellite based on the mapping relationship between ground missions and spatial attitudes. Acta Aeronautica et Astronautica Sinica, 2018, 39(10): Article No. 322066 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=hkxb201810014
    [104] 经飞, 王钧, 李军, 景宁.考虑多数传模式组合的卫星数传调度方法.系统工程学报, 2012, 27(2): 160-168 doi:  10.3969/j.issn.1000-5781.2012.02.003

    Jing Fei, Wang Jun, Li Jun, Jing Ning. Approach considers multiform data transmission mode for satellite data transmission scheduling problem. Journal of Systems Engineering, 2012, 27(2): 160-168 doi:  10.3969/j.issn.1000-5781.2012.02.003
    [105] Chen H, Li L M, Zhong Z N, Li J. Approach for earth observation satellite real-time and playback data transmission scheduling. Journal of Systems Engineering and Electronics, 2015, 26(5): 982-992 doi:  10.1109/JSEE.2015.00107
    [106] Kim H, Chang Y K. Mission scheduling optimization of SAR satellite constellation for minimizing system response time. Aerospace Science and Technology, 2015, 40: 17-32 doi:  10.1016/j.ast.2014.10.006
    [107] Zhang Z J, Zhang N, Feng Z R. Multi-satellite control resource scheduling based on ant colony optimization. Expert Systems with Applications, 2014, 41(6): 2816-2823 doi:  10.1016/j.eswa.2013.10.014
    [108] Verfaillie G, Lemaȋtre M, Bataille N, Lachiver J M. Management of the Mission of Earth Observation Satellites Challenge Description, Technical Report, Centre National d$'$Etudes Spatiales, France, 2002
    [109] Li J, Li J, Chen H, Jing N. A data transmission scheduling algorithm for rapid-response earth-observing operations. Chinese Journal of Aeronautics, 2014, 27(2): 349-364 doi:  10.1016/j.cja.2014.02.014
    [110] Wu G H, Ma M H, Zhu J H, Qiu D S. Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks. Journal of Systems Engineering and Electronics, 2012, 23(5): 723-733 doi:  10.1109/JSEE.2012.00089
    [111] 姜维, 庞秀丽.提高卫星服务寿命的任务规划方法研究.自动化学报, 2014, 40(5): 909-920 doi:  10.3724/SP.J.1004.2014.00909

    Jiang Wei, Peng Xiu-Li. The task scheduling model and algorithm for imaging satellites with optimizing satellite service life. Acta Automatica Sinica, 2014, 40(5): 909-920 doi:  10.3724/SP.J.1004.2014.00909
    [112] Karapetyan D, Minic S M, Malladi K T, Punnen A P. Satellite downlink scheduling problem: a case study. Omega, 2015, 53: 115-123 doi:  10.1016/j.omega.2015.01.001
    [113] 严珍珍, 陈英武, 邢立宁.基于改进蚁群算法设计的敏捷卫星调度方法.系统工程理论与实践, 2014, 34(3): 793-801 http://d.old.wanfangdata.com.cn/Periodical/xtgcllysj201403028

    Yan 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
    [114] 陈宇宁, 邢立宁, 陈英武.基于蚁群算法的灵巧卫星调度.科学技术与工程, 2011, 11(3): 484-489, 502 doi:  10.3969/j.issn.1671-1815.2011.03.012

    Chen Yu-Ning, Xing Li-Ning, Chen Ying-Wu. Scheduling of agile satellites based on ant colony algorithm. Science Technology and Engineering, 2011, 11(3): 484-489, 502 doi:  10.3969/j.issn.1671-1815.2011.03.012
    [115] 朱新新, 谭跃进, 邓宏钟, 邢立宁.求解成像卫星调度问题的改进蚁群算法.科学技术与工程, 2012, 12(31): 8322-8326 doi:  10.3969/j.issn.1671-1815.2012.31.037

    Zhu Xin-Xin, Tan Yue-Jin, Deng Hong-Zhong, Xing Li-Ning. The improved ant colony algorithm solving the scheduling problem of imaging satellites. Science Technology and Engineering, 2012, 12(31): 8322-8326 doi:  10.3969/j.issn.1671-1815.2012.31.037
    [116] Gao K B, Wu G H, Zhu J H. Multi-satellite observation scheduling based on a hybrid ant colony optimization. In: Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation. Paris, France: Atlantis Press, 2013. 675-678
    [117] Zhang N, Feng Z R. Cooperative ant colony optimization for multisatellite resource scheduling problem. In: Proceedings of the 2007 Congress on Evolutionary Computation. Singapore: IEEE, 2007. 2822-2828
    [118] 邢立宁, 陈英武.基于混合蚁群优化的卫星地面站系统任务调度方法.自动化学报, 2008, 34(4): 414-418 doi:  10.3724/SP.J.1004.2008.00414

    Xing Li-Ning, Chen Ying-Wu. Mission planning of satellite ground station system based on the hybrid ant colony optimization. Acta Automatica Sinica, 2008, 34(4): 414-418 doi:  10.3724/SP.J.1004.2008.00414
    [119] 姚锋, 邢立宁.求解卫星地面站调度问题的演化学习型蚁群算法.系统工程与电子技术, 2012, 34(11): 2270-2274 doi:  10.3969/j.issn.1001-506X.2012.11.14

    Yao Feng, Xing Li-Ning. Learnable ant colony optimization algorithm for solving satellite ground station scheduling problems. Systems Engineering and Electronics, 2012, 34(11): 2270-2274 doi:  10.3969/j.issn.1001-506X.2012.11.14
    [120] Hosseinabadi S, Ranjbar M, Ramyar S, Amel-Monirian M. Scheduling a constellation of agile earth observation satellites with preemption. Journal of Quality Engineering and Production Optimization, 2017, 2(1): 47-64
    [121] 孙凯, 邢立宁, 陈英武.基于分解优化策略的多敏捷卫星联合对地观测调度.计算机集成制造系统, 2013, 19(1): 127-136 http://d.old.wanfangdata.com.cn/Conference/9007689

    Sun Kai, Xing Li-Ning, Chen Ying-Wu. Agile earth observing satellites mission scheduling based on decomposition optimization algorithm. Computer Integrated Manufacturing Systems, 2013, 19(1): 127-136 http://d.old.wanfangdata.com.cn/Conference/9007689
    [122] Niu X N, Tang H, Wu L X. Satellite scheduling of large areal tasks for rapid response to natural disaster using a multi-objective genetic algorithm. International Journal of Disaster Risk Reduction, 2018, 28: 813-825 doi:  10.1016/j.ijdrr.2018.02.013
    [123] Xhafa F, Herrero X, Barolli A, Takizawa M. A comparison study on meta-heuristics for ground station scheduling problem. In: Proceedings of the 17th International Conference on Network-Based Information Systems. Salerno, Italy: IEEE, 2015. 172-179
    [124] 周毅荣, 陈浩, 李龙梅, 陈荦, 景宁.一种基于免疫遗传的卫星数传调度方法.小型微型计算机系统, 2015, 36(12): 2725-2729 doi:  10.3969/j.issn.1000-1220.2015.12.020

    Zhou Yi-Rong, Chen Hao, Li Long-Mei, Chen Luo, Jing Ning. Immune genetic algorithm for satellite data transmission scheduling. Journal of Chinese Computer Systems, 2015, 36(12): 2725-2729 doi:  10.3969/j.issn.1000-1220.2015.12.020
    [125] Chen H, Zhou Y R, Du C, Li J. A satellite cluster data transmission scheduling method based on genetic algorithm with rote learning operator. In: Proceedings of the 2016 Congress on Evolutionary Computation. Vancouver, Canada: IEEE, 2016. 5076-5083.
    [126] 贺仁杰, 高鹏, 白保存, 李菊芳, 姚锋, 邢立宁.成像卫星任务规划模型、算法及其应用.系统工程理论与实践, 2011, 31(3): 411-422 http://d.old.wanfangdata.com.cn/Periodical/xtgcllysj201103004

    He Ren-Jie, Gao Peng, Bao Bai-Cun, Li Ju-Fang, Yao Feng, Xing Li-Ning. Models, algorithms and applications to the mission planning system of imaging satellites. Systems Engineering-Theory & Practice, 2011, 31(3): 411-422 http://d.old.wanfangdata.com.cn/Periodical/xtgcllysj201103004
    [127] 黄瀚, 张晓倩.基于图论模型的成像卫星任务规划方法研究.桂林航天工业学院学报, 2016, 21(2): 155-158 doi:  10.3969/j.issn.1009-1033.2016.02.005
    [128] Xhafa F, Herrero X, Barolli A, Takizawa M. A simulated annealing algorithm for ground station scheduling problem. In: Proceedings of the 16th International Conference on Network-based Information Systems. Gwangju, South Korea: IEEE, 2013. 24-30
    [129] Xhafa F, Herrero X, Barolli A, Takizawa M. A tabu search algorithm for ground station scheduling problem. In: Proceedings of the 28th International Conference on Advanced Information Networking and Applications. Victoria, Canada: IEEE, 2014. 1033-1040
    [130] 张超, 李艳斌.多敏捷卫星协同任务规划调度方法.科学技术与工程, 2017, 17(22): 271-277 doi:  10.3969/j.issn.1671-1815.2017.22.044

    Zhang Chao, Li Yan-Bin. Planning and scheduling method for multi agile satellite coordinated mission. Science Technology and Engineering, 2017, 17(22): 271-277 doi:  10.3969/j.issn.1671-1815.2017.22.044
    [131] Chen Y, Zhang D Y, Zhou M Q, Zou H. Multi-satellite observation scheduling algorithm based on hybrid genetic particle swarm optimization. Advances in Information Technology and Industry Applications. Berlin, Germany: Springer, 2012. 441-448
    [132] 汤绍勋, 易先清, 罗雪山.面向预警卫星调度问题的改进粒子群算法.系统工程, 2012, 30(1): 116-121 doi:  10.3969/j.issn.1001-2362.2012.01.059

    Tang Shao-Xun, Yi Xian-Qing, Luo Xue-Shan. An improved particle swarm optimization algorithm for early warning satellites scheduling problems. Systems Engineering, 2012, 30(1): 116-121 doi:  10.3969/j.issn.1001-2362.2012.01.059
    [133] 常飞, 武小悦.基于改进粒子群算法的卫星数传任务调度.系统工程与电子技术, 2009, 31(10): 2404-2408 doi:  10.3321/j.issn:1001-506X.2009.10.028

    Chang Fei, Wu Xiao-Yue. Satellite data transmission task scheduling based on advanced particle swarm optimization. Systems Engineering and Electronics, 2009, 31(10): 2404-2408 doi:  10.3321/j.issn:1001-506X.2009.10.028
    [134] 国晓博, 刘金灿, 周红彬.分布式卫星系统数传调度研究.无线电通信技术, 2016, 42(4): 29-32 doi:  10.3969/j.issn.1003-3114.2016.04.08

    Guo Xiao-Bo, Liu Jin-Can, Zhou Hong-Bin. Research on transmission task scheduling for distributed satellite systems. Radio Communications Technology, 2016, 42(4): 29-32 doi:  10.3969/j.issn.1003-3114.2016.04.08
    [135] Zhang T J, Ke L J, Li J S, Li J, Li Z X, Huang J Q. Fireworks algorithm for the satellite link scheduling problem in the navigation constellation. In: Proceedings of the 2016 Congress on Evolutionary Computation (CEC). Victoria, Canada: IEEE, 2016. 4029-4037
    [136] 经飞, 王钧, 李军, 陈浩, 景宁.基于吱呀轮优化的多卫星数传调度问题求解方法.宇航学报, 2011, 32(4): 863-870 doi:  10.3873/j.issn.1000-1328.2011.04.024

    Jing Fei, Wang Jun, Li Jun, Chen Hao, Jing Ning. A new scheduling method for multi-satellite data transmission based on squeaky-wheel optimization. Journal of Astronautics, 2011, 32(4): 863-870 doi:  10.3873/j.issn.1000-1328.2011.04.024
    [137] 李志亮, 李小将, 张东来.基于改进DE算法的敏捷成像卫星前摄式调度.系统工程与电子技术, 2018, 40(2): 353-359 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtgcydzjs201802017

    Li Zhi-Liang, Li Xiao-Jiang, Zhang Dong-Lai. Proactive scheduling of agile imaging satellite based on improved differential evolution algorithm. Systems Engineering and Electronic, 2018, 40(2): 353-359 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=xtgcydzjs201802017
  • [1] 李勇, 李坤成, 孙柏青, 张秋豪, 王义娜, 杨俊友. 智能体Petri网融合的多机器人 多任务协调框架[J]. 自动化学报, 2019, 45(): 1-21. doi: 10.16383/j.aas.c190400
    [2] 韩敏, 闫阔, 秦国帅. 基于改进KAZE的无人机航拍图像拼接算法[J]. 自动化学报, 2019, 45(2): 305-314. doi: 10.16383/j.aas.2018.c170521
    [3] 陈世明, 化俞新, 祝振敏, 赖强. 邻域交互结构优化的多智能体快速蜂拥控制算法[J]. 自动化学报, 2015, 41(12): 2092-2099. doi: 10.16383/j.aas.2015.c150254
    [4] 彭孝东, 张铁民, 李继宇, 陈瑜. 基于传感器校正与融合的农用小型无人机姿态估计算法[J]. 自动化学报, 2015, 41(4): 854-860. doi: 10.16383/j.aas.2015.c140277
    [5] 温乃峰, 苏小红, 马培军, 赵玲玲. 低空复杂环境下基于采样空间约减的无人机在线航迹规划算法[J]. 自动化学报, 2014, 40(7): 1376-1390. doi: 10.3724/SP.J.1004.2014.01376
    [6] 刘钢, 老松杨, 谭东风, 周智超. 反舰导弹航路规划问题的研究现状与进展[J]. 自动化学报, 2013, 39(4): 347-359. doi: 10.3724/SP.J.1004.2013.00347
    [7] 王小乐, 黄宏斌, 邓苏. 处理顺序约束的信息物理融合系统静态任务表调度算法[J]. 自动化学报, 2012, 38(11): 1870-1879. doi: 10.3724/SP.J.1004.2012.01870
    [8] 邢立宁, 陈英武. 基于知识的智能优化引导方法研究进展[J]. 自动化学报, 2011, 37(11): 1285-1289. doi: 10.3724/SP.J.1004.2011.01285
    [9] 李祖欣, 王万良, 成新民. 资源约束网络的优化带宽调度[J]. 自动化学报, 2009, 35(4): 443-448. doi: 10.3724/SP.J.1004.2009.00443
    [10] 白保存, 陈英武, 贺仁杰, 李菊芳. 基于分解优化的多星合成观测调度算法[J]. 自动化学报, 2009, 35(5): 596-604. doi: 10.3724/SP.J.1004.2009.00596
    [11] 邢立宁, 陈英武. 基于混合蚁群优化的卫星地面站系统任务调度方法[J]. 自动化学报, 2008, 34(4): 414-418. doi: 10.3724/SP.J.1004.2008.00414
    [12] 杜晓丽, 王俊丽, 蒋昌俊. 异构环境下基于松弛标记法的任务调度[J]. 自动化学报, 2007, 33(6): 615-621. doi: 10.1360/aas-007-0615
    [13] 杨建军, 刘扬, 魏立新, 战 红. 多源注水系统泵站优化调度的双重编码混合遗传算法[J]. 自动化学报, 2006, 32(1): 154-160.
    [14] 支青, 蒋昌俊. 一种适于异构环境的任务调度算法[J]. 自动化学报, 2005, 31(6): 865-872.
    [15] 翟桥柱, 管晓宏, 郭燕, 孙岚, 范炜. 具有混合动态约束的生产系统优化调度新算法[J]. 自动化学报, 2004, 30(4): 539-546.
    [16] 杨根科, 吴智铭, 陈贇. 减链约束多处理器任务在三处理器中的调度[J]. 自动化学报, 2004, 30(4): 583-587.
    [17] 李为民, 黄田, D.J.Whitehouse. 数控铣削过程有约束广义预测控制解析算法[J]. 自动化学报, 1999, 25(6): 796-799.
    [18] 齐向彤, 陈秋双, 涂菶生. 具有约束条件的单机JIT调度问题[J]. 自动化学报, 1998, 24(3): 421-423.
  • 加载中
图(5)
计量
  • 文章访问数:  913
  • HTML全文浏览量:  640
  • PDF下载量:  275
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-11-30
  • 录用日期:  2019-03-28
  • 刊出日期:  2020-02-20

无人飞行器集群智能调度技术综述

doi: 10.16383/j.aas.c170681
    基金项目:

    国家自然科学基金 61773120

    国家自然科学基金 61873328

    国家自然科学基金 61772225

    国家杰出青年科学基金 61525304

    高等学校全国优秀博士学位论文作者专项资金 2014-92

    广东省自然科学基金 2018B030311046

    广东省自然科学杰出青年基金 2017KZDXM081

    湖南省研究生科研创新项目 CX2018B022

    作者简介:

    杜永浩   国防科技大学系统工程学院博士研究生. 2017年获国防科技大学硕士学位.主要研究方向为智能优化理论、方法与应用. E-mail: duyonghao15@163.com

    蔡昭权   惠州学院教授. 2006年获华中科技大学硕士学位.主要研究方向为计算机网络, 智能计算和数据库. E-mail: 13502279833@126.com

    通讯作者: 邢立宁   国防科技大学系统工程学院研究员, 全国优秀博士学位论文获得者, 入选教育部新世纪优秀人才计划, 湖南省自然科学杰出青年基金获得者. 2009年获国防科技大学博士学位.主要研究方向为智能优化理论、方法与应用.本文通信作者. E-mail: xinglining@gmail.com
  • 本文责任编委 孙富春

摘要: 随着飞行器技术的快速发展, 以无人机和卫星为代表的无人飞行器在集群任务中得到广泛应用, 但日益增长的多样化任务需求和不平衡、不充足的任务资源也对无人飞行器集群调度技术提出新的挑战.针对无人飞行器任务类型特点, 分别从无人机群和多星两个角度出发, 介绍了无人机群访问、打击和察打一体化任务调度技术进展, 阐述了多星成像、数传与天地一体化任务调度研究成果.同时, 梳理了无人机群和多星任务调度问题的主要约束与收益指标, 综述了无人机群和多星任务调度常用的智能优化算法.最后, 面向未来无人飞行器技术应用需求, 指出了无人飞行器集群智能调度技术进一步的研究方向.

本文责任编委 孙富春

English Abstract

杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2020, 46(2): 222-241. doi: 10.16383/j.aas.c170681
引用本文: 杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2020, 46(2): 222-241. doi: 10.16383/j.aas.c170681
DU Yong-Hao, XING Li-Ning, CAI Zhao-Quan. Survey on Intelligent Scheduling Technologies for Unmanned Flying Craft Clusters. ACTA AUTOMATICA SINICA, 2020, 46(2): 222-241. doi: 10.16383/j.aas.c170681
Citation: DU Yong-Hao, XING Li-Ning, CAI Zhao-Quan. Survey on Intelligent Scheduling Technologies for Unmanned Flying Craft Clusters. ACTA AUTOMATICA SINICA, 2020, 46(2): 222-241. doi: 10.16383/j.aas.c170681
  • 无人飞行器集群技术是指多个具有共同任务目标的无人飞行个体, 借助现代控制与决策手段, 维持无人飞行器以群体形式有序执行任务的智能技术.随着控制技术、通讯技术、传感器技术和智能调度技术的快速发展, 无人飞行器集群技术在区域测控与搜索、军事侦察与打击、信息通讯、气象监测和物流运输等民用与军事领域得到广泛应用[1-4].无人飞行器集群技术能够在极少人为干预的情况下做出智能决策, 具有自组织性、协同性、并行性和安全性的优点, 是未来飞行器技术信息化、智能化发展的必然趋势.

    从无人飞行器的飞行高度与工作环境看, 目前无人飞行器集群的对象主要为无人机和卫星两类.无人机和卫星集群具有诸多相同的特点:飞行运动约束强、速率大; 集群任务中响应频繁、容错率低; 受天气等环境因素及动态因素影响显著等.而随着无人机和卫星技术的蓬勃发展, 在任务需求、任务规模、任务与资源约束和工作环境等方面, 无人机和卫星集群的复杂性和不确定性也急剧增长, 严重影响着集群任务执行的效率与可靠性.因此, 如何通过调度技术为无人飞行器个体分配任务和有限的资源、避免任务和资源冲突、实现全局任务收益的最大化, 成为无人飞行器集群技术的关键.

    考虑到无人飞行器集群调度问题的任务复杂性、强约束性和NP (Non-deterministic polynomial)难特性, 合理的任务特征分析、准确的资源与约束建模, 以及针对性的智能求解方法尤为重要.由此, 本文分别基于无人机群和多星任务调度问题的特点, 按图 1分类介绍了无人机群和多星的任务类型, 梳理了无人机群和多星任务调度问题的主要约束, 总结并阐述了智能优化算法在无人机群和多星任务调度中的应用.最后, 面向未来无人飞行器技术应用需求, 指出了无人飞行器集群智能调度技术进一步的研究方向.

    图  1  无人飞行器集群任务分类图

    Figure 1.  Mission classification of unmanned flying craft clusters

    • 无人机群在执行民用任务(如监测、救援)和军用任务(如侦察、打击)方面具有广阔的应用前景, 特别是在偏远、危险或人员不可达的工作环境中已逐步取代有人系统.随着任务需求、规模和复杂度的不断提升, 无人机群任务调度技术已成为无人机研究领域的热点之一.无人机群任务调度技术是在满足各项约束条件的前提下, 以实现收益最大化为目的, 为无人机合理安排任务和有限的任务资源, 对提高任务执行效率和资源利用率具有重要意义.针对无人机群调度技术的应用领域, 本节将梳理无人机群任务调度的类型和主要约束条件, 并结合不同类型的任务调度问题介绍常用的几种无人机群任务智能调度算法.

    • 根据无人机资源利用与任务目标的不同, 可将无人机任务分为访问任务和打击任务.前者是利用无人机能量资源, 根据任务需求对目标点逐一进行覆盖或侦测; 后者则是利用机载武器资源, 对目标进行攻击.同时, 在现代无人机作战任务中, 侦察与打击任务往往密不可分、同步进行, 具有一体化的调度需求.由此, 本节将分类阐述一些代表性的无人机群任务调度研究.

    • 无人机群访问任务调度是在主要满足侦测设备与能量约束的条件下, 通过对机群进行合理的任务分配, 有效覆盖、搜索或评估访问目标, 实现访问收益最大化的过程.

      1) 覆盖任务

      无人机群覆盖任务主要体现于对区域目标的持续监控和确定性的侦测搜索.根据无人机覆盖任务是否依赖于某种行为, 任务的执行策略又可分为行为式覆盖策略和非行为式覆盖策略, 如图 2所示.

      图  2  覆盖任务的优化策略

      Figure 2.  Optimization strategy for coverage missions

      行为式覆盖策略是基于某种无人机行为, 优化各无人机的初始方向和飞行时长, 以实现对任务区域最大化覆盖的目的.例如, 罗木生等[5]考虑了反潜无人机吊放雷达的搜索特点, 设计了"回字型"拓展方阵覆盖策略, 并对比了单机覆盖与多机协同覆盖的效果. Lee等[6]设计了一种"内旋式"无人机覆盖策略, 通过引入机器人边界跟随行为的分段启发式算法实现了不规则区域的有效遍历.针对大规模区域目标覆盖任务, 陈海等[7]通过对目标区域的分割与任务分配, 建立了无人机"牛耕式"覆盖任务的约束满足模型. Kolling等[8]设计了无人机"并列推扫"策略, 通过优化并列数量、搜索角度和高度完成了不规则2.5D环境区域的持续覆盖.行为式覆盖策略具有较小的问题规模和良好的可执行性, 是覆盖问题的主要优化策略.

      非行为式覆盖策略则不拘泥于无人机的某种行为, 直接优化无人机飞行路径, 在覆盖问题中也表现了出色的优化效果.例如Barrientos等[9]将待搜索区域进行栅格化处理, 在网格轨迹优化的基础上辅以飞行动力控制修正, 提升了无人机群分布式协同覆盖的效果.晋一宁等[10]针对区域目标持续覆盖问题, 以每个网格单元最短未覆盖时间为优化目标, 借助无人机群局部感知和通信策略, 实现了无人机系统对动态目标持续涌现的覆盖行为.

      2) 搜索任务

      无人机群搜索任务主要体现于对不确定性或动态目标的搜索需求.民用方面, 针对海上失事人员搜索问题, Varela等[11]设计了基于约束采样的进化算法, 使得搜索过程具备自组织性和引导性, 表现出较高的发现概率和鲁棒性. Lanillos等[12]研究了不确定环境中失踪目标的搜索问题, 通过预期观测信息有效引导机群搜索, 并基于滚动时域不断更新观测信息, 极大程度地提升了目标发现概率和机群搜索效率. Wang等[13]将无人机群搜索任务分为航迹规划与任务分配两个阶段, 分别采用了无障碍图搜索算法和混合线性整数规划方法进行求解.

      军用方面, 符小卫等[14]研究了无人机对地移动目标协同侦察任务调度问题, 在无人机群成员通讯交互的基础上, 基于预测控制思想考虑了无人机当前搜索代价和长期搜索代价, 提高了无人机群协同搜索效能.为降低目标不确定性运动的影响, Ru等[15]通过机载传感器探测和敌机潜在运动范围分析, 基于贝叶斯理论对敌机运动概率图进行实时更新, 有效提升了三维战场环境中敌机的发现概率.针对通用战术网络环境下的无人机群协同侦察问题, 马纯超等[16]将无人机群的控制任务分配给不同的地面管控中心, 并基于无人机网络信息通讯实现了对随机动态目标的搜索与遍历.

      3) 评估任务

      无人机群评估任务主要来源于军用无人机在完成作战行动后对目标毁伤效果的评估需求.评估任务是一种通过具备评估功能的无人机对目标实施遍历的访问任务, 但由于其与无人机打击任务存在严格的时序约束, 故通常在打击任务或察打一体化任务中执行.

    • 无人机群打击任务调度是指在获得目标属性、位置和速度的情况下, 分配无人机及其机载武器资源, 在满足一定约束条件的情况下对目标完成打击任务的过程.例如, 倪谣等[17]建立了满足时序约束的打击任务混合整数规划模型, 实现了6架无人机对4个地面固定目标的攻击任务分配.在动态任务频繁到达的情况下, 周小程等[18]研究针对动态打击目标的无人机群实时调度问题, 并借助分布式的竞拍机制提升了任务调度效率.

      不过, 随着无人机作战任务要求和作战对象不确定性程度的不断提升, 无人机打击任务与侦察任务已经密不可分, 而独立的打击任务已经很难应对复杂多变的战场环境.因此, 侦察与打击任务一体化的调度模式是现代无人机群军事作战任务的必然趋势.

    • 现代无人机的作战任务流程一般为侦察、打击和评估, 即战前目标搜索、战时目标打击和战后毁伤评估三个步骤.针对这一任务流程, 为实现无人机作战"看得到, 打得到, 打得好"的战术指标, 现代无人机作战任务向着察打一体化的格局发展.然而, 察打一体化任务具有多样化的任务需求, 对参战无人机群的功能要求也较高.由此, 无人机群存在着两种不同的察打一体化任务协同方式.

      传统的协同方式为同构协同, 即无人机群内所有成员的属性与功能一致, 该协同方式具有统一的问题描述方法与约束条件, 单机失效后其功能也较容易及时补充.例如, 美国航天航空研究院[19]借鉴带有时间窗约束的车辆路径规划问题, 综合分析了无人机最大续航时间和优先级任务需求, 建立了混合整数规划模型, 研究了双无人机察打一体任务调度问题. Zhen等[20]为无人机定义了能量耗尽前自主返回基地充能的工作策略, 直接提升了机群侦察与打击任务的续航能力.常一哲等[21]针对先进战斗机特点和未来中远距协同空战发展需求, 将空战能力划分为攻击能力与防御能力, 前者包括先敌发现、先敌打击与先敌摧毁能力, 后者包括机动能力、隐身能力与干扰能力, 实现了复杂任务环境中的无人机群侦察与攻击决策.

      另一种协同方式是异构协同, 即无人机群内成员属性与功能存在差异, 该协同方式具有良好的功能多样性和任务适应性, 但约束性更强, 对任务调度的要求也更高.例如, 陈洁钰等[22]研究了无人攻击机和电子干扰机协同动态调度问题, 当攻击机探测到敌方雷达时则迅速触发干扰机的电子干扰.刘重等[23]研究了不确定环境下异构无人机群协同察打一体化的任务调度, 在满足机群同时打击目标的前提下提出了一种分阶次优联盟快速组建算法, 并采用Monte-Carlo仿真分析了无人机数量与目标数量对任务效果的影响.考虑到侦察机具备更远的雷达测距而攻击机拥有更强的挂弹能力, Deng等[24]建立了侦察机与攻击机混合的异构机群任务调度约束满足模型.吴蔚楠等[25]构建了侦察机、攻击机和察打一体机的异构协同无人机编队, 完成了对敌防空阵地识别、攻击和评估一体化的任务调度.戚泽旸等[26]考虑了无人机隐身性能和侦察代价, 分析了具备不同隐身能力、武器挂载能力和打击毁伤能力的异构无人机群协同任务执行效能.

      可见, 无人机群任务调度技术已得到诸多研究与应用, 对提升无人机群智能化水平和多样化任务执行能力具有重要意义.同时, 现有研究也存在调度问题与通讯机制简化程度较高、异构协同多样性不足、大规模任务调度与调度系统研发涉猎较少等问题, 暴露出对无人机执行能力与策略、复杂需求、异构系统等约束描述能力不足的现状.由此, 下文对各类无人机集群调度问题中的关键性约束进行分类阐述, 为相关调度问题研究中的约束建模过程提供参考.

    • 无人机群在执行任务过程中的各类约束条件是限制任务收益的根本因素, 故无人机群任务约束的准确描述是开展优化调度的前提.无人机群智能调度问题的常见约束如图 3所示, 其中收益约束反映了无人机群执行任务的收益需求, 通常作为软约束或直接作为收益函数.除图中所示的通用任务收益外, 还包括无人机群侦察发现概率与覆盖率、毁伤与战损概率、战役全局价值等实际工程应用背景下的收益指标.

      图  3  无人机群智能调度问题常见约束

      Figure 3.  Common constraints in intelligent scheduling for unmanned aerial vehicles

      1) 无人机资源约束

      无人机资源约束是无人机群任务调度问题的基本约束, 主要包括无人机所携带的电量、油量及其续航能力等能源资源约束, 目标侦察、打击等机载设备资源约束, 以及通讯天线、频道及容量等通讯资源约束.

      能源与续航约束是无人机执行任务的首要前提. Zeng等[27]规定了无人机油量耗尽前必须返回基地. Franco等[28]根据真实无人机单位时间功率曲线计算了飞行能耗约束值.李炜等[29]将无人机航行时间与最大航行时间的比值作为任务分配的影响因子, 达到航行极限的无人机将不再获得任务.韩国科学技术院[30]引入了无人机在服务点补充能量并继续执行任务这一实际工况, 从根本上提升了无人机群执行任务的可持续性.

      在侦察与武器资源约束方面, 罗德林等[31]基于攻击目标至少分配一枚导弹的约束条件, 将无人机协同多目标攻击决策问题转化为导弹目标攻击配对的优化问题.陈洁钰等[22]研究了基于无人攻击机携弹量约束和电子干扰机雷达功率约束的异构协同动态调度问题. Kim等[32]将无人机携带的军事资源抽象为不同类型的资源单元, 设计了资源平衡、资源预留和资源分享策略引导了无人机群的任务调度.

      在通讯资源约束方面, 张民强等[33]研究了通信距离受限情况下的无人机群协同目标搜索问题. Sujit等[34]考虑了无人机群通讯故障的不确定性情况, 并基于Monte-Carlo仿真模拟了机群通讯对任务调度效果的影响.针对通信延迟情况下的无人机群协同搜索问题, Mirzaei等[35]对通信不一致情况进行补偿, 减轻了延迟带来的影响.马纯超等[16]指出传统无人机任务调度很少考虑无人机基地通信链路约束, 故引入了地面站及通信覆盖范围约束、地面站最大可控无人机数等实际约束, 实现了8架无人机由3个地面站跨域联合控制指挥的任务调度仿真.此外, 无人机群的通信链路还需满足带宽、功率等现实约束.

      无人机集群调度问题中对资源约束描述通常较为完备, 但大多基于确定性资源消耗的前提.而在无人机群实际的任务执行环境中, 机群的资源消耗往往具有一定的不确定性, 故针对资源不确定性的无人机群任务资源预测、调度鲁棒性研究也具有现实意义.

      2) 时序约束

      任务可执行时间窗、任务时效性和任务序列约束也是无人机群任务调度问题最常见的约束, 反映了无人机群任务调度问题的时序特征.美国国家航空航天局[36]很早就开展了多时间窗与资源约束下的无人机群调度问题研究.伍思远[37]以上海市杨浦区无人机安保任务调度问题为背景, 基于区域人口密度定义了无人机巡查周期的时间约束. Ramirez-Atencia等[38]考虑了无人机连续侦察任务中前序任务的时间与顺序约束.针对无人机群自主协同调度问题, 曹文静等[39]考虑了无人机感知、战场态势同步、决策与决策传递过程中的时间消耗与序列约束, 分析了基于工作流和基于多Agent技术的无人机群协同性能.

      时序约束反映了无人机群调度场景中待执行任务的执行机会和逻辑关系, 但目前时间窗、任务截止时间和执行顺序等约束的提取往往较为简单, 以人为规划为主, 缺乏科学依据, 故此类约束建模过程还需要完备任务属性与需求的分析, 以及充分工程实践经验的支持.

      3) 几何与动力学约束

      在几何约束方面, Shima等[40]考虑了机载传感器探测距离和角度约束.仲筱艳等[41]考虑了无人机作战高度与作战半径约束. Khosiawan等[42]研究了区域目标成像捕获和货物投送等复杂任务调度问题, 并通过预处理技术将真实的室内房间结构转化为无人机可执行任务的区域模型.赵明等[43]借助数字高程模型(Digital elevation model, DEM)描述了区域空间的地貌形态, 在满足地形跟随和飞行高度约束的前提下开展了无人机群协同目标分配研究.

      在飞行动力学方面, 晋一宁等[10]考虑了无人机飞行航向角和最大转弯角约束, 通过分散航向图引导机群规避碰撞, 实现了无人机群对目标区域的持续覆盖. Wang等[44]考虑了无人机航迹连续性因素, 借助Dubins路径连接模型求解了无人机群侦察点状与区域目标的混合优化问题.

      在编队与协同方面, Zhen等[20]考虑了无人机群规避相互碰撞和障碍物的安全距离约束, 设计了飞行姿态调整规则, 完成了编队协同打击任务调度.针对异构无人机群对不同类型目标的侦察、打击与评估任务, 尹高扬等[45]建立了一体化协同任务分配的约束满足模型, 实现了敌机"发现即毁"的仿真战术目标. Gyeongtaek等[46]针对无人机物流配送问题, 考虑到货物重量超过单机配送承载极限, 设计了多无人机协同抓取货物的配送策略, 在任务调度中灵活地组合与调整无人机编队, 取得了满意的调度效果.

      不过, 目前无人机群调度问题中的几何与动力学约束简化程度较高, 且受无人机类型及属性(如固定翼和旋翼无人机)影响显著, 故相关研究还应针对异构无人机行为与能力特点, 结合相关学科知识对转向半径、航速变化、编队结构保持、三维运动连续性等约束进行准确描述, 进一步提升问题建模的可靠性.

      4) 收益约束

      无人机群任务调度问题的收益约束主要包括时间收益、能耗收益和任务收益等.结合不同工程或军事需求, 收益约束通常以组合的形式作为调度问题的收益函数.

      在时间与能耗收益方面, Gyeongtaek等[47]以最小化任务完成时间为优化目标.赵宏伟等[48]则对机群损耗和任务耗时赋予了不同的权重.李炜等[29]优化了无人机群对各类敌对目标打击的代价总和. Ramirez-Atencia等[38]以最低油耗、最短飞行时间和最小无人机出动架次为优化目标设计了约束满足优化模型, 对比了无人机数量、任务前序约束等对调度效率的影响.

      在任务收益方面, Zhang等[49]以任务完成率和无人机群平均资源占有率为收益函数, 在基本任务合成与分层处理的基础上取得了良好的求解效果.郑晓辉[50]基于我方攻击态势和敌方抗击能力两个方面, 以单机对敌的优先权为基础约束, 以最大化无人机协同作战的效能和我方飞机总体优势为收益目标.刘毅等[51]以目标优先程度、目标打击效果上下限作为收益约束, 并以打击效果最大化作为收益目标, 开展了无人机群任务双层协同调度. Wu等[52]以毁伤不同属性的异构敌方目标为收益函数, 完成了动态环境中的无人机群最大作战效能优化.不过, 任务收益的量化及定义也需要充分的科学论证, 针对无人机群需求筹划与任务预处理的相关研究也应得到关注.

    • 针对小规模的无人机群任务调度问题, 启发式方法得到广泛运用并取得满意的优化效果.但在当今任务调度规模不断增加、任务需求和约束条件更加严格的背景下, 启发式方法很难取得满意的求解效果.而实践表明, 智能优化算法具有良好的收敛速率和优化能力, 是解决NP难问题的有效方法, 适合于解决无人机群任务调度中出现的"组合爆炸"问题.由此, 针对无人机群访问任务与察打一体化任务调度问题, 本节介绍一些常用的智能优化算法.

      1) 蚁群算法

      无人机群任务调度问题通常包含无人机航段的规划与调度, 故蚁群算法在此类问题中具有良好的适用性和拓展性.在访问任务方面, Zhang等[49]对基本任务进行合成并分层分配给无人机群, 再利用引入启发式规则的蚁群算法调度单机的任务序列. Perez-Carabaza等[53]通过栅格化无人机群的搜索空域, 将无人机运动划分为8个不同权重等级的方向, 并在迭代过程中引导无人机向累计概率权重高的区域移动.该算法取得了优于单一蚁群算法的收敛速度和优化质量. Gao等[54]设计了一种基于蚂蚁通讯的分布式蚁群算法, 分别设计了局部、全局和发现目标后的信息素更新策略, 提升了算法在无人机群大规模密集搜索问题中的自组织能力和收敛效果.

      在察打一体化任务方面, Cekmez等[55]构建了无人机群执行任务过程中的无线传感网络, 结合CUDA (Compute unified device architecture)平台构建了一种并行蚁群算法.该算法在求解多目标复杂任务调度问题时表现出出色的收敛性. Zhen等[20]设计了一种自组织的分布式蚁群算法, 当无人机发现目标后立即实施打击活动, 同时更新全局信息素以引导无人机向未知区域搜索.针对无人机群作战任务环境的动态性、非线性和强对抗性特点, Wu等[52]提出了一种基于动态劳动分配的蚁群算法(Dynamic ant colony$ ' $s labor division, DACLD).算法在动态任务、不确定威胁和重调度任务中表现出高度的自组织性、快响性和灵活性.

      2) 遗传算法

      遗传算法以概率化的寻优方式获取和优化搜索空间, 具有良好的环境适应性、隐并行性和全局寻优能力, 适合于求解资源受限的强约束调度问题[56].

      在访问任务方面, 美国国家航空航天局[36]混合使用了遗传算法和梯度投影法(Gradient projection method, GPM), 对带有时间窗约束的无人机群任务调度问题开展了早期研究. Ramirez-Atencia等[57]设计了一种多目标遗传算法, 基于多目标的适应度函数优化了无人机群在执行多区域目标访问任务中的油耗和任务完成时间. Wang等[44]设计了一种基于双染色体编码和多段变异的遗传算法, 有效增强了算法种群多样性, 提升了算法在大规模无人机访问任务中的收敛效果.

      在察打一体化任务方面, Shima等[40]通过遗传算法实现了无人机群执行动态打击任务的仿真调度, 详细讨论了变异与交叉算子对收敛速度和效果的影响.针对无人机跨域飞行、信息共享而导致任务区域与规模扩大、引发任务分配难度增加的问题, 马纯超等[16]首先根据目标属性进行分组, 有效降低问题复杂度, 随后利用遗传算法生成局部最优解.该方法在较大规模的无人机目标分配问题中取得了良好的时效性和适应性.

      3) 模拟退火算法

      模拟退火算法是一种源于固体退火原理的概率演化算法, 受初始解质量和问题规模影响较小, 具有良好的渐进收敛性.在访问任务方面, 为提升模拟退火算法在大规模问题中的优化速率, Turker等[58]基于并行计算平台CUDA加速了模拟退火算法优化进程, 完成了高复杂性无人机群任务的有效调度.美国空军研究实验室[59]针对无人机群电磁作战场景, 应用模拟退火算法对机群任务进行了分配, 指出模拟退火算法虽然优化时间普遍长于遗传算法, 但在各类规模问题中均能取得满意结果.

      同时, 模拟退火算法与遗传算法有良好的组合优化效果.赵宏伟等[48]考虑到无人机战场环境发生改变时, 任务收益和约束也随之改变的现实特点, 提出了一种基于在线仿真的无人机群任务调度方法, 并通过结合遗传策略的模拟退火算法完成求解.针对无人机群协同多目标导弹攻击决策问题, 罗德林等[31]对遗传算法中的子代个体进行模拟退火操作, 验证了该混合算法优于单一算法的收敛速率和收益效果.

      4) 粒子群算法

      粒子群算法在无人机群任务调度研究中应用广泛, 并常与其他启发式或智能算法混合使用.在访问任务方面, Gyeongtaek等[47]通过在粒子群算法中引入全局贪心策略, 有效缩短了无人机群任务调度时间.为避免粒子群算法陷入局部最优, 施蓉花等[60]在算法中引入交叉变异策略, 取得了显著优于使用单一算法的任务优化结果. Zhang等[61]还在算法中加入了自适应惯性因子, 在无人机群军事侦察任务中取得出色的调度效果.

      在察打一体化任务方面, 刘毅等[51]设计了一种基于粒子群算法的交互式策略, 同时在迭代过程中引入定期初始化和保留历史最优值的机制, 有效摆脱了局部最优解的吸引, 完成了机群打击顺序、投弹量和打击时间的多目标优化.尹高扬等[45]通过矩阵编码的方式设计了一种多目标离散粒子群算法, 在协同任务分配的复杂约束环境下取得了良好的调度效果. Cao等[62]基于粒子群–鱼群算法和分布式拍卖策略, 实现了复杂时序约束和通讯约束条件下的分布式无人机群动态调度.石岭[63]针对粒子群算法易陷入早熟的缺陷, 在算法引入模拟退火策略, 验证了算法求解静态无人机群协同攻击任务的优越性, 并结合博弈论设计了复杂战场环境下的动态资源分配方案.梁国强等[64]设计了一种混合遗传策略的离散粒子群算法, 并将任务时序约束和多机协同约束融入到算法的粒子矩阵编码中, 有效求解了无人机群广域察打一体化任务的协同调度问题.

      5) 分布式算法

      在无人机群任务调度过程中, 基于并行、协同、通信和多Agent策略的分布式算法具备较强的问题导向性和可拓展性, 对降低无人机群任务调度规模, 提升优化速度和鲁棒性起到重要作用.

      周小程等[18]考虑到无人机打击任务的强时效性, 设计了一种不公开出价的分布式拍卖策略, 出价高者直接赢得拍品, 有效缩短了动态任务到达后的调度响应时间.针对无人机通讯延迟问题, 曹攀峰等[65]提出了一种基于分布式预测模型(Decentralized model predictive control, DMPC)的分布式算法, 该算法通过引入缓冲周期和协商机制, 在恶劣多变的任务环境中表现出强鲁棒性和灵活性. Kingston等[66]设计了一种基于共识与协商策略的分布式算法, 算法在求解过程中可以灵活地增减执行任务的无人机数量, 具有较好的动态收敛性和优化能力.晋一宁等[10]提出了基于局部感知和局部通信策略的在线分布式覆盖算法, 算法促进了无人机系统对动态目标覆盖行为的持续涌现, 在机群和任务规模持续增加的情况下仍保持了良好的稳定性和调度效果.

      除此以外, 还有人工鱼群算法[67]、狼群算法[68]、烟火算法[69]、合同网协议算法[70]等诸多智能优化算法应用于无人机群调度技术研究中.综上可见: a)智能优化算法在无人机群任务调度技术中应用广泛, 极大提升了无人机群任务调度问题求解效率; b)结合无人机群任务调度特点, 引入启发式、自适应、多种群、通讯交互和算法混合策略的智能优化算法在避免算法早熟、增强局部寻优能力和提升收敛速率方面起到重要作用; c)分布式算法缩小了无人机群调度问题规模、降低了问题复杂性, 实现了无人机由单智能体向智能集群的涌现行为.与此同时, 智能优化算法的鲁棒性问题也一直是影响其推广应用的重要因素, 而目前针对无人机群智能调度的鲁棒性研究还较少.未来研究应更多地关注无人机集群调度算法的鲁棒性特点, 为复杂任务调度问题的求解和机群调度系统的研发提供优质、可靠的算法支撑.

      无人机调度与卫星调度在任务目的、约束类型与求解方法方面有不少相似之处.例如, 二者均包括以成像、侦察为主要目标的任务需求; 均需要满足几何与飞行约束、各类时间窗与时序约束以及飞行器所能携带的资源约束; 均需要通过智能优化方法求解集群带来的大规模任务调度问题等.由此, 结合本节无人机群任务调度问题与约束的分析思路, 下面本文将介绍多星任务智能调度技术.

    • 编队或组网的卫星工作方式具有协同性能好、运行成本低、飞行效率高、执行任务可靠性高和适应性强等优点, 是卫星在轨服务形式的必然趋势.但卫星管理数量与类型的持续增长也带来了更大的问题规模和更多的约束冲突, 对卫星任务调度技术提出了新的挑战.本节梳理了多星任务调度的类型和主要约束条件, 并针对不同类型的调度问题介绍一些常见的多星智能调度算法.

    • 目前, 卫星任务调度通常分为成像任务调度和数传任务调度两类, 二者以独立调度为主.但考虑到卫星数储容量和任务时效性等实际约束, 为进一步发挥多星成像任务和数传任务的执行效率, 成像与数传联合的天地一体化任务调度技术也逐渐得到学者们的重视.

    • 多星成像任务调度是针对目标成像需求, 合理安排卫星及星载传感器、数储、能量等载荷资源, 有效消解任务与约束冲突, 以获得最大成像收益的过程.成像任务调度是多星任务调度技术的重要组成部分, 也是开展数传任务调度的重要前提.根据成像卫星轨道机动能力的不同, 卫星成像任务可以分为传统卫星成像任务和敏捷卫星成像任务两种.

      1) 传统卫星成像任务

      传统卫星是相对敏捷卫星而言, 只具备侧摆机动能力的一种卫星, 是目前成像卫星的主要形式.目前, 传统卫星在各类轨道上承担了大部分成像观测任务, 故基于传统卫星的多星成像任务调度依然十分重要.

      传统卫星成像任务通常针对点目标和条带目标开展成像活动.点目标和条带目标相对于卫星成像幅宽较小, 能够被卫星单次成像的视场所覆盖, 常用于标识区域范围较小的重要目标.点目标与条带目标成像任务简单、可以一次性完成, 故许多成像目标常被简化为点目标、条带目标或其合成形式, 如图 4(a)4(b)所示.由此, 传统卫星成像任务调度问题本质上是点目标与条带目标成像窗口与资源分配的问题.

      图  4  敏捷卫星与传统卫星成像策略对比

      Figure 4.  Comparison on observation strategies between agile satellites and traditional satellites

      传统卫星成像任务调度问题中成像目标、资源和环境都是静态的, 但随着近年来成像任务中不确定性的不断增加, 以优先安排紧急任务、最小化任务总延迟为目标的动态任务调度和重调度策略也尤为重要.针对动态任务到达的问题, 刘洋等[71]研究了多星成像动态约束满足问题与求解方法, 以任务调整最少为优化目标实现了多星成像任务的动态调度, 但星群和目标规模均较小, 未能表现出大规模任务调度的适用性调度策略. Qiu等[72]在时域内周期性或基于事件地触发重调度, 并对比了不同优先级和启发策略影响下的算法求解效果.不过, 基于优先级的调度策略牺牲了低优先级的任务收益, 在动态事件触发频繁的情况下会影响调度效果.面向自然灾害等突发性成像任务需求, Niu等[73]基于动态分割策略划分成像区域目标, 对汶川地震灾区开展了仿真调度试验, 在自然灾害成像方面具有较强的应用价值. Skobelev等[74]结合Multi-agent技术, 将对地遥感星群成像任务调度问题划分为控制、数储、规划、轨道和可视化模块, 基于贪婪算法设计了考虑事件变化的动态任务调度系统.

      国内外学者已针对传统卫星成像任务调度开展广泛研究, 但同时也暴露出传统卫星单次过境成像形式单一、对区域目标成像能力有限、资源利用率低、受轨道约束影响较大等问题.虽然多星联合成像调度技术的发展可以一定程度上避免上述弊端, 但仍很难满足如今不断增长的成像任务规模和多样化需求.所以, 在日益成熟的多星成像调度研究基础上, 发展轨道机动与成像能力更加灵活的敏捷卫星调度技术是未来多星任务调度研究与应用的必然趋势.

      2) 敏捷卫星成像任务

      与传统卫星相比, 敏捷卫星具有侧摆、俯仰、偏航三个轴向的快速机动能力, 在成像任务中表现出以下优势: a)成像时间窗口更长; b)任务与约束冲突消解方式更多; c)姿态转换更加灵活、快速.由此, 敏捷卫星在单次过境中具备更强的任务执行能力和执行效率, 其针对区域目标的成像方式与传统卫星有本质差别, 如图 4(b)4(d)所示.对同一区域目标而言, 传统卫星必须借助多次过境或多星协同成像的方式, 而敏捷卫星可以在单次过境中通过多次姿态调整实现对其成像, 表现出强大的任务执行效率和多星联合执行任务的兼容性.另一方面, 敏捷卫星灵活机动的优势也增加了成像任务观测时间与序列的不确定性, 为敏捷卫星任务调度带来了新的挑战. Lemaitre等[75]最早提出了敏捷卫星调度问题, 考虑了敏捷卫星在对条带目标成像时的角度约束和姿态转换时间约束, 建立了数学模型, 对比了贪婪搜索、动态规划等启发式算法的优化效果.现有的敏捷卫星成像调度研究较多地基于单星单轨的形式[76], 而多敏捷卫星联合成像调度可以最大限度发挥敏捷卫星的轨道机动优势, 使成像任务收益获得更大提升.同时, 许多研究采用固定宽度的条带对区域目标进行分解, 但忽略了敏捷卫星频繁姿态调整过程中成像幅宽的变化.针对这一问题, 章登义等[77]设计了一种基于动态幅宽的区域目标平行条带动态分割方法, 取得了更高的条带拼接精度与综合成像效果.

      由于在敏捷卫星成像任务调度问题中, 任务可见时间窗的选择属于离散决策问题, 而窗口内任务执行时刻的选择则是连续决策问题.故多数研究中依旧采用传统卫星的调度方式来调度敏捷卫星, 即优化过程仅决策到时间窗层面, 再利用启发式或约束消解策略决定任务在窗口内的开始时间[78-79].这样虽然降低了敏捷成像卫星任务调度问题规模, 但也限制了解的提升空间.实际工程中也有将任务可见时间窗进行离散处理的做法, 将问题转换为完全离散决策问题, 但离散化的程度也影响着调度精度与效率.此外, 敏捷卫星的高机动性同时也伴随着很强的时间依赖性[79-80], 准确描述敏捷卫星在不同情况下的姿态转换时间也是获取高质量、可靠调度解的必要条件.

    • 数传任务调度指卫星与地面测控中心分别分配天线传输资源, 将星上储存的信息数据通过天地链路传输给地面测控中心的调度问题.随着卫星技术的发展和任务需求的日益增加, 如今多星数传调度问题面临以下难点: a)卫星数量和任务数量较多; b)地面测控中心资源和可见时间窗有限; c)天地链路的数据传输带宽和允许传输的任务类型有限.可见, 多星数传任务调度也是一个具有NP难计算特性的复杂优化问题.所以, 合理的建模方法和有效的智能算法在求解多星数传调度难题中常常发挥着重要作用.下面, 介绍几种最常用的多星数传任务调度模型.

      1) 整数规划模型

      上世纪90年代起, 美国空军技术学院[81]就开始通过混合整数规划模型研究空军卫星控制网络(Air force satellite control network, AFSCN)的调度问题, 给出了多星数传任务调度问题的标准测试集.朱小满等[82]基于0-1整数规划模型, 通过启发式算法有效消解了多星数传调度问题的任务冲突, 实现了动态任务调度的快速求解, 但优化效果有待进一步提高.王沛[83]对多星调度问题中卫星耦合、地面站分离等约束条件进行了简化, 建立了累计收益最大化的整数规划模型.为求解大规模多星多站数传调度问题, Marinelli等[84]建立了基于时间指数的0-1整数规划模型, 并通过拉格朗日松弛算法取得了良好的调度效果, 该模型成功运用于欧洲航天局伽利略导航系统的数传任务调度中.

      2) 约束满足模型

      约束满足模型以决策变量的函数表达式作为约束条件, 对大规模多约束问题的简化和描述起到重要帮助.基于这一特点, Pemberton等[85]将卫星调度问题描述为包含任务、事件、约束和资源四个模块的约束满足模型, 得到了学者们的广泛认可.李云峰等[86]充分考虑了用户需求和问题约束, 在单数传任务模型的基础上建立了多星联合数传调度的约束满足优化模型, 并基于单数传任务和卫星数传的综合优先度有效求解了多星数传调度任务的优化问题.

      3) 图论模型

      图论模型通过点和线的方式简单而直观地描述问题本质, 处理方式多样、灵活, 在多星数传调度中运用广泛.针对意大利高分辨率雷达卫星星座COSMO-SkyMed, Bianchessi等[87]构建了基于有向无圈图的任务调度模型, 通过前瞻和回溯功能实现了大规模冲突消解和任务快速调度.针对同步轨道卫星群数传任务调度, Xu等[88]建立了最小生成树的图论模型.陈祥国等[89]构建了基于任务调度关系(弧模式)和基于任务调度位置(结点模式)的解构造图. Corrao等[90]提出了包含图论理论、混合遗传算法和线性规划模型的多星数传任务组合调度系统, 系统体现出良好的算法耦合效果, 在大规模数传任务调度中取得出色的优化结果.

      除此以外, 还有Multi-agent模型[91]、Petri网模型[92]等应用于多星数传调度的研究中.不过, 数传调度问题往往建立在成像方案的基础上, 两者常常独立调度, 成像任务的调度结果作为数传任务的调度输入.考虑到成像任务与数传任务的高耦合性, 全局考虑成像与数传的天地一体化任务调度应当成为卫星任务调度科学研究与工程系统设计的首要调度形式.

    • 卫星数传任务的调度依赖于成像任务的执行结果, 而成像任务的最终目的是通过数传调度的途径传输给用户, 故两者是密切相关、相辅相成的.传统的卫星成像与数传任务是独立考虑的, 而近年来随着星上存储技术和卫星调度技术的不断发展, 以及天地综合资源管控的迫切需求, 综合考虑卫星成像与数传活动的天地一体化任务调度问题得到了越来越多的重视.一体化任务调度的主要优势有: a)已成像的任务选择性数传, 有效缓解卫星存储容量的压力; b)先成像的任务拥有更多的数传窗口, 易满足时效性的任务需求; c)多圈次、阶段性或重复成像任务分批次数传, 可缓解任务与时间窗的约束冲突.但与此同时, 多星天地一体化任务带来了更庞大的任务规模、更多的时间窗约束和更加频繁的卫星姿态转换, 无疑对卫星任务调度技术提出了更高的要求.

      Wang等[93]针对我国"环境一号"环境与灾害监测预报卫星, 研究了多星天地一体化调度混合整数规划模型, 基于一种启发式求解算法实现了多星成像与数传任务的一体化调度, 并在此基础上设计了任务与有效载荷管理系统. Li等[94]设计了多星天地一体化调度系统, 该系统可以同时对中轨道卫星、同步轨道卫星和倾斜同步轨道卫星进行联合任务调度, 体现出良好的适用性和鲁棒性.针对电磁探测卫星天地一体化调度问题, Chen等[95]以任务优先级、紧急任务完成率等为优化目标, 基于约束冲突消解和遗传算法对成像与数传任务实现了有效调度. Sun等[96]针对敏捷卫星的功能特点, 综合考虑了"实拍实传"、"立体成像"等复杂任务模式约束, 建立了多星多站成像与数传调度一体化约束满足优化模型, 并通过引入启发式规则的遗传算法取得了理想的调度结果. Zhu等[97]针对我国高分、风云、遥感和资源卫星异构协同问题, 建立了成像、数传和中继多星一体化任务调度约束满足模型, 并通过一种遗传退火算法完成了密集任务的有效调度.

      天地一体化任务调度技术刚刚起步, 在学者们的共同推动下已取得一定的研究成果.但随着未来航天技术的不断发展, 还将有更多的具备各式各样功能和任务目标的卫星发射升空.这样一来, 持续增加的卫星与任务规模、更加拥挤的天地链路通道和各式各样的任务需求与约束条件将成为天地一体化任务调度技术未来发展的重要挑战.针对各类多星调度场景, 下文对多星任务调度问题中的关键性约束进行分类阐述, 为相关调度问题研究中的约束提取与建模过程提供参考.

    • 多星智能调度问题的常见约束与无人机调度问题类似, 如图 5所示, 其中收益约束反映了多星执行任务的收益需求, 通常作为软约束或收益函数.下面举例说明多星智能调度问题中典型的约束类型.

      图  5  多星智能调度问题常见约束

      Figure 5.  Common constraints in intelligent scheduling for multi-satellites

      1) 卫星资源约束

      与无人机资源约束相似, 卫星固存、电量, 以及任务执行时间、次数等约束是任务调度中最基本、最常见的约束形式.例如, Dilkina等[98]考虑了星上存储、能量限制等实际约束, 混合使用了基于排序策略的调度方法和约束传播方法, 求解了大规模点目标成像任务调度问题. Xu等[99]考虑了星上存储和连续工作时长等约束, 基于调度收益和资源消耗的优先级指标求解了敏捷卫星调度问题.针对可变轨卫星成像任务调度问题, Zhu等[100]优化了卫星最小变轨燃料消耗和最大成像覆盖率.邱涤珊等[101]基于卫星开机功率、开关机及状态调整耗能, 准确计算了卫星单圈次能量需求, 并在满足能量和固存资源约束的情况下对多星密集任务完成了有效调度.

      同时, 卫星在执行数传任务的时候还存在地面数传中心及数传天线资源的约束问题. Wang等[93]综合考虑了地面站位置与天线资源等约束, 将多星成像与数传任务的一体化调度系统成功应用于我国环境与灾害监测卫星的调度中.

      考虑到卫星可控时间短、重访周期长、太空环境未知性大等特点, 卫星资源的不确定性将对任务调度结果产生更大的影响.工程实践表明, 卫星在轨资源消耗常常与地面仿真结果相差较大, 造成部分任务调度方案无法执行的结果.故考虑资源不确定的卫星任务调度问题应得到重点关注.

      2) 时间依赖性约束

      多星任务调度具有很强的时间依赖性, 一方面体现在卫星成像与数传任务的时间窗口约束和任务序列约束中, 例如在条带拼接或立体成像任务中, 部分任务必须依次连续执行[76]; 在天地一体化任务调度中, 数传任务必须安排在成像活动之后[94], 且任务必须满足目标与用户的时效性需求等.

      另一方面, 卫星成像相机、数传天线在执行任务过程中都需要调整和对准的过程, 故时间依赖性还体现在卫星连续执行任务的时间间隔上, 即卫星姿态转换时间受前序任务与后续任务状态的约束[102].例如Liu等[79-80]通过下式描述敏捷卫星成像任务的时间间隔:

      $$ \begin{align} \Delta t = \frac{\Delta g}{v} + C(\Delta g) \end{align} $$ (1)

      其中, $ \Delta g $为卫星前序任务与后续任务的综合姿态转角, $ v $为姿态转速, $ C(\Delta g) $为根据$ \Delta g $所计算的额外转换时间.可见, 在卫星执行任务过程中, 任意两个任务之间的转换约束均严格依赖于卫星执行任务的时间.不过, 目前研究中卫星姿态转换时间的计算以分段线性函数为主, 还不能准确地反映卫星机动过程中加速、均速机动、减速、稳定的四个过程, 且缺乏轨道动力学知识的验证[103], 故相关研究还需进一步深入.

      3) 轨道与模式约束

      与无人机不同, 卫星只能沿着既定的轨道飞行, 故卫星任务调度问题具有极强的轨道约束性.卫星调度问题中的轨道约束通常体现在时间窗口约束中, 即时间窗口中已包含卫星所属轨道信息.但为提升在轨执行任务的能力, 卫星通常具备多种工作模式.

      针对高轨对地观测卫星多数传模式和长可见时间窗的服务特点, 经飞等[104]建立了基于最大收益比的约束满足模型, 采用启发式方法对一周内数传任务完成了多次调度. Chen等[105]考虑了成像卫星任务中"实拍实传"和"储存转发"两种实际工作模式, 有效消解了任务资源冲突, 在10颗卫星的联合调度试验中取得出色的调度结果. Sun等[96]针对敏捷卫星的功能特点, 综合考虑了"实拍实传"、"立体成像"等复杂任务需求, 求解了多星多站成像与数传一体化调度问题.

      同时, 受卫星机动能力的限制和在轨稳定性的影响, 卫星姿态调整的幅度、频率、功率均应控制在额定范围内, 且不同工作模式的任务之间也需要一定的模式转换时间.此外, 由于卫星在轨服务周期长, 其飞行轨道会随着时间的推移发生变化, 故在轨道预报的基础上引入一定的不确定性因素有助于提升卫星长周期任务调度的可靠性.

      4) 收益约束

      收益约束代表用户对卫星完成任务效果和服务效率的基本要求, 也常直接作为调度问题的收益函数.最大限度完成任务、提升任务综合优先级、避免冲突始终是任务调度的根本目的.故与无人机群任务收益相似, 绝大部分研究中均将任务完成率、任务综合优先级或权重作为多星调度的首选收益指标.

      在任务完成时间方面, Kim等[106]针对合成孔径雷达(Synthetic aperture radar, SAR)星座区域目标重复成像的调度问题, 以最小化系统响应时间为优化目标, 有效规避了约束冲突和目标成像重叠的问题. Zhang等[107]以最小化任务完成总时间为优化目标, 求解了多星、多轨多站的数传调度问题.

      在成像质量方面, Verfaillie等[108]考虑了区域目标形状、面积和立体成像需求, 简化了Pleiades敏捷卫星区域目标成像调度数学模型. Liu[79]等针对用户成像质量的要求, 假设卫星成像质量是关于成像开始时间和最佳成像时间的分段线性函数, 开展了大规模任务场景下的敏捷卫星成像调度研究.成像质量还常与任务完成度、任务优先级同时作为收益约束或组合收益函数.

      在动态任务影响方面, Li等[109]指出大部分数传调度问题集中关注约束冲突消解和调度收益最大化等问题, 他们针对紧急任务插入的动态数传任务调度问题, 控制了由紧急任务插入引起的总体任务延误, 实现了10颗卫星紧急数传任务的快响式调度. Wu等[110]将成像任务分为普通任务和紧急任务, 在确保紧急任务优先级的同时实现任务总收益的最大化. Chen等[95]以任务优先级、紧急任务完成率等为目标优化了多星天地一体化任务调度问题.

      此外, 姜维等[111]还考虑了多星组网的任务风险要素, 对卫星在轨使用寿命进行了优化.现有的多星任务调度研究中, 通常对卫星各类约束条件进行了一定的简化.结合不同的实际工程需求, 还有诸多特殊的约束条件, 例如:出于用户特定要求, 某目标只能由指定卫星或在指定轨道内进行观测; 受限于传统卫星固存技术, 无法随时更新任务内存, 只能一次性格式化处理; 卫星存在"对日充能"和"对地定向"不同的能量消耗模式等.这些复杂的约束对研究者们提出了更高的问题描述与建模要求, 带来了更强的约束性和问题复杂性.为了应对上述问题, 智能调度算法发挥着不可或缺的作用.

    • 研究表明, 对于小规模的卫星任务调度问题, 启发式算法通常可以在较短的时间内获得满意解, 是工程系统中的常用方法.但随着问题规模的不断增长, 传统的启发式方法很难取得理想的求解效果[112].由此, 大规模的多星任务调度问题通常依赖于智能优化算法进行求解.常用的智能优化算法包括蚁群算法、遗传算法、模拟退火算法和粒子群算法等.

      1) 蚁群算法

      蚁群算法基于正反馈的搜索机制易于获得全局最优解, 在大规模、多目标的多星任务调度问题中得到很好的应用.

      在成像任务方面, 邱涤珊等[101]针对密集点目标成像任务调度问题, 使用了一种借鉴蚁群系统和最大最小蚂蚁系统思想的蚁群算法, 并通过任务优先级、成像时间窗等因素调整转移概率, 实现了多星密集点目标成像任务的快速有效调度.针对双敏捷卫星成像调度问题, 严珍珍等[113]通过优化蚁群算法组件对问题进行了求解, 在大规模成像任务调度中取得了出色的调度速率和效果.陈宇宁等[114]针对双敏捷卫星成像任务调度问题, 在蚁群算法中加入信息素限制策略避免陷入局部最优, 实现了大规模点目标任务95 %以上的调度完成率.朱新新等[115]针对蚁群算法响应时间长, 易陷入局部最优的问题, 在初始种群中选择一种综合启发信息和扰动机制来生成任务链, 并用分类消减的方法进行时间窗更新, 验证了算法在成像任务调度中的可行性和优越性.此外, Gao等[116]设计了一种带有迭代局部搜索策略的蚁群算法. Wu等[110]在蚁群算法中引入迭代局部搜索策略, 在确保紧急任务优先级的同时实现了任务总收益的最大化.

      在数传任务方面, Zhang等[117]提出了一种合作型蚁群算法(Cooperative ant colony optimization, CACO), 通过蚂蚁间的交流机制提高算法向更优解的转移概率.邢立宁等[118]在数传任务调度问题中混合使用了蚁群算法和导向局部搜索算法, 充分发挥了蚁群算法的全局搜索能力和导向搜索算法的局部寻优能力, 以最大化综合任务权重为目标完成了多天线地面站系统的数传任务调度.陈祥国等[89]在蚂蚁转移规则中引入伪随机概率, 通过划分数传任务的冲突集来限制蚁群的搜索邻域, 并限制信息素浓度在一定范围内以避免算法早熟现象.姚锋等[119]设计了一种演化学习型蚁群算法(Learnable ant colony optimization, LACO), 实现了知识模型和蚁群优化模型优势互补, 通过优化过程的知识挖掘进一步指导后续优化工作, 极大提高了算法寻优能力, 在大规模多星数传调度实例中取得出色的调度结果. Li等[94]针对蚁群算法优化初期信息素缺乏和早熟收敛的现象, 设计了一种基于遗传策略的蚁群算法, 很好地求解了多星天地一体化任务调度问题.

      2) 遗传算法

      在成像任务方面, Kim等[106]针对SAR星座区域目标重复成像的调度问题, 利用改进的遗传算法有效规避了约束冲突和目标成像重叠的问题, 取得了理想的求解速率和调度完成率. Hosseinabadi等[120]通过非沿轨的区域目标条带划分方式, 设计了多星成像重叠区域优先级调度策略, 减少了多星成像任务的重叠, 并通过遗传算法的求解显著降低了调度资源的消耗.孙凯等[121]建立了多敏捷卫星多圈次成像任务调度约束满足模型, 并将问题分解为任务资源匹配和单星任务处理两个模块, 分别通过学习型遗传算法和最优插入位置策略解决了这一问题.针对自然灾害的突发任务观测需求, Niu等[122]利用多目标遗传算法NSGA-Ⅱ (Nondominated sorting genetic algorithm-Ⅱ)对汶川地震灾区完成了多星多轨成像与条带拼接任务调度, 与历史数据对比取得了显著的成像效率提升.

      在数传任务方面, 美国空军技术学院[81]针对空军卫星控制网络(AFSCN), 利用遗传算法完成了多星数传任务96 %的调度完成率, 该算法目前依然是求解该标准测试问题最为有效的算法之一. Xhafa等[123]设计了一种基于竞争策略的遗传算法(Struggle genetic algorithm, SGA), 通过在遗传过程中淘汰种群中的劣势个体, 并生成新的种群, 保持了进化过程中种群的多样性. Li等[109]混合使用了遗传算法和$ K $条最短路径算法($ K $-shortest path selection, KSPS), 有效控制了由紧急任务插入引起的任务总延误, 实现了多星紧急数传任务的快响式调度.针对数传调度中地面测控中心位置集中、资源争用冲突显著的问题, 周毅荣等[124]设计了一种免疫遗传算法(Immune genetic algorithm, IGA), 通过免疫记忆机制记录了周期性数传任务中的历史信息, 很好地求解了多星重访飞行中的数传调度问题; 并进一步提出了基于学习策略的遗传算法(Genetic algorithm with rote learning operator, GARLO), 算法在大规模多星多站数传调度中表现出优越的搜索效率、收敛速度和鲁棒性[125].

      3) 模拟退火算法

      在成像任务方面, 贺仁杰等[126]针对卫星成像任务合成特点, 在模拟退火算法中设计了随机扰动、重排列和重启动三种分化策略, 以实现对局部最优值的逃逸.黄瀚等[127]构建了多星天地一体化任务调度图论模型, 并在模拟退火算法中加入了精英解保持和二次搜索策略, 显著提升了算法的收敛性.

      在数传任务方面, Xhafa等[128]指出模拟退火算法能够在多星数传调度问题中快速获得可行解, 在各类规模的任务场景中具有良好的适用性.他们还设计了考虑窗口、冲突、需求和资源的多目标禁忌搜索策略, 并验证了算法的时效性和鲁棒性[129].张超等[130]考虑了敏捷卫星大角度侧摆、同轨立体观测、多条带拼接等成像模式特点, 引入了基于观测质量的成像选择策略, 通过基于相似度和聚集度的遗传退火算法求解了10颗敏捷卫星成像任务调度问题, 并设计了交互式调度软件.

      4) 粒子群算法

      粒子群算法结构简洁、易于实现, 在多维问题求解中表现出寻优速度快、鲁棒性好等特点, 但也存在易早熟、易陷入局部最优的不足.

      在成像任务方面, Chen等[131]提出了一种遗传粒子群算法, 求解了5颗对地观测卫星成像任务调度问题, 取得了显著优于传统粒子群算法的调度结果.汤绍勋等[132]针对7星4轨预警卫星侦察任务调度问题, 设计了一种离散粒子群算法, 采用基于优先级的粒子群初始化机制, 有效提高了算法对可行解空间的搜索效率, 取得了良好的调度效果. Zhu等[100]针对变轨多星多目标成像任务调度问题, 混合使用了粒子群算法和差分进化算法(Differential evolution, DE), 算法表现出显著优于单一算法的优化性能.

      在数传任务方面, 常飞等[133]设计了一种自适应规模的粒子群算法(Adaptive scale particle swarm optimization, ASPSO), 根据种群多样性的变化对算法粒子自动增减, 并与传统的先到先服务算法进行了对比, 结果表明自适应机制显著提升了算法求解速度和优化质量. Chen等[105]提出了一种基于量子行为的粒子群算法(Quantum discrete particle swarm optimization, QDPSO), 并引入变异算子有效避免算法陷入局部最优, 算法在多星实时数传任务调度中表现出良好的寻优能力和收敛速度.针对分布式中继卫星系统的数传调度问题, 国晓博等[134]在粒子群算法中引入交叉、变异算子和方向回溯机制, 综合考虑了系统与中低轨卫星的时间窗、卫星剩余资源和数传任务属性等约束条件, 获得了良好的调度结果.

      此外, Zhang等[135]以最小化地面站参与度为目标, 采用烟火算法对动态卫星数传任务进行了有效调度.经飞等[136]建立了考虑时间窗调整的多星数传调度模型, 设计了一种吱呀轮优化算法(Squeaky-wheel optimization, SWO), 在大规模数传任务调度中表现出大邻域导向式搜索特点, 在时间性、优化度等方面取得满意效果.针对敏捷卫星前摄式多目标优化调度问题, 李志亮等[137]在差分进化算法的基础上引入了遗传策略和外部存档更新策略, 降低了任务调度时间, 取得了显著优于使用NSGA-Ⅱ算法的优化结果.

      可见, 智能优化算法在多星成像、数传及一体化任务调度中发挥着重要作用, 主要体现为: a)良好的全局寻优能力和问题求解效率, 适合于当前多星任务调度密集、大规模和强约束的问题特点; b)改进的智能优化算法在多星任务调度, 特别是动态任务调度中具有出色的可拓展性和鲁棒性; c)基于工程经验的启发式策略和基于约束推理的约束消解策略能够在有限时间内提升解的质量, 对引导算法寻优空间、提升求解速率起到重要帮助.同时, 智能优化算法在工程应用中也面临着鲁棒性与大规模场景优化能力欠佳等问题.由此, 结合调度任务工程背景, 有针对性地选择智能优化算法, 以及启发式、自适应、分布式和约束消解策略, 着力提升智能优化算法的鲁棒性, 对缩小多星任务调度问题求解空间、推动卫星管理系统的算法应用、提高大规模任务优化效率和任务调度的智能化水平起到十分重要的作用.

    • 以无人机和卫星为主的无人飞行器集群调度是复杂的NP难问题.通过本文对无人机群和多星任务调度问题特点、约束条件和智能优化算法的综述, 可见智能调度技术为无人飞行器集群任务带来了: a)更高的资源利用率、任务完成率和多目标的优化质量; b)更快的调度速率; c)更好的并行性、协同性和鲁棒性; d)更强的自主响应、动态响应和自适应能力等.由此, 智能调度技术对充分发挥无人飞行器集群优势、增强任务执行能力、提高任务执行率和资源利用率起到了举足轻重的作用.

      同时, 未来日益增长的环境复杂性、需求多样性和任务复杂性也不断对无人飞行器集群调度技术提出更高的要求.对此, 未来无人飞行器集群智能调度的研究可以向以下方向发展.

      1) 进一步提升调度技术智能化水平

      虽然智能调度技术在无人飞行器集群调度研究中已得到充分应用, 但与未来无人机和卫星的集群管控要求仍有一定差距.例如, 目前文献中无人机或卫星集群数量普遍小于10, 而现阶段蜂群调度和数十颗卫星联合调度的实际需求已不在少数.无人飞行器集群调度问题的NP难特性决定了其很难在短时间内通过精确算法求解, 而关于不确定环境下无人飞行器集群智能调度方法的鲁棒性、实时性研究还不足.

      针对上述现状, 无人飞行器集群调度的智能化水平还需进一步提升.无人飞行器集群智能化水平应包括集群任务的鲁棒性、自主性、自适应性、协同性和并行性等诸多方面.目前无人飞行器集群调度技术的鲁棒性问题是制约其工程应用与推广的关键因素.同时, 无人飞行器集群调度技术在大规模、长时效的任务调度中还大多保持着"人在回路"的调度模式, 特别是任务预处理和动态任务处理等方面尚不能完全离开人的决策.因此, 未来无人飞行器集群调度研究应进一步提升目标识别与预处理水平、分层调度和应急调度等方面的技术, 减少人为干涉程度, 提升人为决策的调度层级, 充分发挥低层级任务的智能调度水平, 进一步增强无人飞行器集群整体的智能化程度.

      2) 提升异构无人飞行器集群协同能力

      目前无人飞行器集群调度仍以同构飞行器调度或单一任务调度为主, 例如, 无人机察打一体化调度的文献中, 调度对象通常为具有侦察功能的侦察机、导弹攻击机和兼具侦察与打击功能的一体机等, 但真实情况下的空中指挥预警、电子对抗等关联任务调度通常被忽略, 涉及到的异构飞行器及其功能调度也被很大程度地简化.

      针对日益增长的多样化、复杂化任务需求, 在目前无人机群与多星任务调度技术的基础上, 应充分发挥二者的任务执行能力与优势, 拓展资源与协同空间, 推动异构无人飞行器集群协同调度技术发展.现有的无人飞行器集群较多地集中于同构协同的方式, 虽然同构协同具有问题描述简单统一、飞行器失效后其功能较容易及时补充等优势, 但个体成员一致的功能属性也限制了集群全局功能的发展.相反, 以预警机、侦察机、攻击机和加油机组成的无人机混合作战编队就能够实现单一机群无法完成的远距离侦察、打击和保障任务.因此, 发挥异构成员的独有优势、实现成员间优劣互补、发展多元化的无人飞行器集群调度问题具有非常重要的价值.未来, 对遥感卫星与导航卫星、侦察机与轰炸机、攻击梯队与保障梯队等异构协同无人飞行器集群调度将成为现实需求.

      3) 发展空天地一体化任务调度技术

      空天地一体化任务调度技术与异构无人飞行器集群协同能力是相辅相成的.在现有研究中, 无人飞行器集群调度的一体化水平仍需提高, 例如卫星天地一体化调度的文献中常采取以成像任务序列为基础, 再安排数传任务的一体化决策模式, 分段式调度的思维仍然存在.同时, 由于无人机与卫星信息侦察与数据传输的共性, 二者存在一体化调度的基础和应用价值, 但目前尚无文献开展关于二者的一体化调度研究.

      针对目前无人飞行器集群调度一体化水平不足、无人机与卫星协同应用较少等的现状, 全局考虑无人机侦察与打击任务、卫星成像与数传任务及相关不确定性的空天地一体化任务框架对提升集群任务的执行能力与可靠性具有重要意义.无人机群在执行任务的过程中, 数据信息也常通过卫星、地面站等途径进行传输, 故以无人机群构成的空域集群、由多星构成的天基集群, 与地面指挥控制集群具有联合运作的实际应用基础和发展前景.例如, 在未来信息化军事斗争中, 无人机群、卫星群、地面指挥与打击群必然是密切联动的, 对实时掌握战场态势、索取战场优先权和主动权起到十分重要的作用.由此, 综合考虑空域、天域、地域和时域的资源与约束条件, 降低各类约束中不确定性因素的影响, 发挥多装备、多平台耦合效应, 发展面向未来信息化工业与军事需求的空天地一体化智能调度技术势在必行.

      4) 开发通用式任务规划与调度管理系统

      通过本文对无人飞行器集群调度问题特点、约束条件和优化方法的综述, 各类无人飞行器集群调度模型与算法实际上具有很大的共性.但无人飞行器集群调度的工程应用背景促使了其调度模型与问题特征、邻域结构与算法改进措施紧耦合的现状, 在调度过程中缺乏统一的建模框架与模块化的系统设计思维.

      将具有共性特性的无人飞行器集群调度问题纳入统一的建模与求解方法, 开发通用式任务规划与调度管理系统, 是无人飞行器集群调度智能化水平、异构协同能力和空天地一体化发展的出发点和落脚点.通用式的任务规划与调度管理系统区分问题建模与算法求解两个重要模块, 前者通过合理的简化与预处理技术将问题抽象为经典、常用的形式化问题模型, 后者则有针对性地选择、混合各类智能优化算法对问题模型进行解算与优化.建模与算法的分离设计有利于降低两者之间的依赖程度、提升系统的集成性、适用性和可拓展性.此外, 任务规划与调度的综合管理和支持人机交互的系统模式也是未来无人飞行器集群任务管理发展的重要趋势.

参考文献 (137)

目录

    /

    返回文章
    返回