第15卷第2期 智能系统学报 Vol.15 No.2 2020年3月 CAAI Transactions on Intelligent Systems Mar.2020 D0:10.11992/tis.201811018 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20190409.0932.010.html 多约束下多无人机的任务规划研究综述 齐小刚，李博，范英盛，刘立芳2 (1.西安电子科技大学数学与统计学院，陕西西安710071；2.西安电子科技大学计算机学院，陕西西安 710071,3.西安电子科技大学宁波信息技术研究院，浙江宁波315200) 摘要：高度信息化的发展使得无人机作战优势凸显。准确的无人机任务规划技术是完成给定任务的重要保 障。任务分配、路径规划是构成无人机任务规划技术的两个核心部分。基于该技术，首先讨论了无人机任务规 划的发展状况、分类标准、体系结构。其次，分别详细介绍了影响任务分配、路径规划的重要指标，如分类标 准、约束指标、相应模型、代表算法、评价指标等，然后，分别分析对比求解任务分配的启发式算法、数学规划 方法、随机智能优化算法的优缺点和求解路径规划的数学规划方法、人工势场法、基于图形学法、智能优化算 法的优缺点：最后，总结了无人机任务规划存在的开放性问题、未来发展方向和研究重点。 关键词：无人机；任务规划：任务分配：路径规划；启发式算法；智能优化算法；平滑处理；可飞性 中图分类号：TP393文献标志码：A文章编号：1673-4785(2020)02-0204-14 中文引用格式：齐小刚，李博，范英盛，等.多约束下多无人机的任务规划研究综述.智能系统学报，2020,15(2)：204-217. 英文引用格式：QI Xiaogang,LIBo,FAN Yingsheng,etal.A survey of mission planning on UAVs systems based on multiple con straintsJCAAI transactions on intelligent systems,2020,15(2):204-217. A survey of mission planning on UAVs systems based on multiple constraints QI Xiaogang,LI Bo',FAN Yingsheng',LIU Lifang23 (1.School of Mathematics and Statistics,Xidian University,Xi'an 710071,China;2.School of Computer Science and Technology, Xidian University,Xi'an 710071,China;3.Xidian-Ningbo Information Technology Institute,Ningbo 315200,China) Abstract:Depending on the highly developed information technology,unmanned aerial vehicles(UAVs)have shown unprecedented advantages in combat.Accurate mission planning technique for UAVs provides an important guarantee for completing a given mission.Task assignment and path planning are the two core components of the mission plan- ning technology for UAVs.Based on this technology,first,the development status,classification standards,and archi- tecture of the mission planning for UAVs are discussed.Second,the important indicators,which affect task assignment and path planning are described in detail;they include classification criteria,constraint indicator,corresponding model, representative algorithm,and evaluation indicator.Then,the strength and weakness of the algorithms for solving tasks are compared,such as heuristic algorithm,mathematical programming method,and stochastic intelligent optimization algorithm.Similarly,for the path planning problem,the advantages and disadvantages of its algorithms,which include mathematical programming method,artificial potential field method,graphic-based method,and intelligent optimization algorithm,are also analyzed.Finally,open problems,the future work,and the research focus in UAVs mission planning are summarized. Keywords:unmanned aerial vehicle;mission planning;task assignment;path planning;heuristic algorithm;intelligence optimization algorithm;smoothing;flyable 近年来，随着科学技术的不断发展，信息技术 收稿日期：2018-11-24.网络出版日期：2019-04-11 的日新月异，战争的智能化、信息化和一体化，使 基金项目：国家自然科学基金项目(61877067,61572435)：教 育部-中国移动联合基金项目(MCM20170I03):西安 得任务规划成为高技术战争的重要支撑。自1917 市科技创新项目(201805029YD7CG13-6):宁波市自 然科学基金项目(2016A610035,2017A610119) 年美国研制出第一架无人机以来，无人机先后经 通信作者：李博.E-mail:libo202017@163.com. 历了靶机、侦察机和诱饵机几个发展阶段。无人
DOI: 10.11992/tis.201811018 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20190409.0932.010.html 多约束下多无人机的任务规划研究综述 齐小刚1,3，李博1 ，范英盛1 ，刘立芳2,3 （1. 西安电子科技大学 数学与统计学院，陕西 西安 710071; 2. 西安电子科技大学 计算机学院，陕西 西安 710071; 3. 西安电子科技大学 宁波信息技术研究院，浙江 宁波 315200） 摘 要：高度信息化的发展使得无人机作战优势凸显。准确的无人机任务规划技术是完成给定任务的重要保 障。任务分配、路径规划是构成无人机任务规划技术的两个核心部分。基于该技术，首先讨论了无人机任务规 划的发展状况、分类标准、体系结构。其次，分别详细介绍了影响任务分配、路径规划的重要指标，如分类标 准、约束指标、相应模型、代表算法、评价指标等，然后，分别分析对比求解任务分配的启发式算法、数学规划 方法、随机智能优化算法的优缺点和求解路径规划的数学规划方法、人工势场法、基于图形学法、智能优化算 法的优缺点；最后，总结了无人机任务规划存在的开放性问题、未来发展方向和研究重点。 关键词：无人机；任务规划；任务分配；路径规划；启发式算法；智能优化算法；平滑处理；可飞性 中图分类号：TP393 文献标志码：A 文章编号：1673−4785(2020)02−0204−14 中文引用格式：齐小刚, 李博, 范英盛, 等. 多约束下多无人机的任务规划研究综述 [J]. 智能系统学报, 2020, 15(2): 204–217. 英文引用格式：QI Xiaogang, LI Bo, FAN Yingsheng, et al. A survey of mission planning on UAVs systems based on multiple constraints[J]. CAAI transactions on intelligent systems, 2020, 15(2): 204–217. A survey of mission planning on UAVs systems based on multiple constraints QI Xiaogang1,3 ，LI Bo1 ，FAN Yingsheng1 ，LIU Lifang2,3 (1. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China; 2. School of Computer Science and Technology, Xidian University, Xi’an 710071, China; 3. Xidian-Ningbo Information Technology Institute, Ningbo 315200, China) Abstract: Depending on the highly developed information technology, unmanned aerial vehicles (UAVs) have shown unprecedented advantages in combat. Accurate mission planning technique for UAVs provides an important guarantee for completing a given mission. Task assignment and path planning are the two core components of the mission planning technology for UAVs. Based on this technology, first, the development status, classification standards, and architecture of the mission planning for UAVs are discussed. Second, the important indicators, which affect task assignment and path planning are described in detail; they include classification criteria, constraint indicator, corresponding model, representative algorithm, and evaluation indicator. Then, the strength and weakness of the algorithms for solving tasks are compared, such as heuristic algorithm, mathematical programming method, and stochastic intelligent optimization algorithm. Similarly, for the path planning problem, the advantages and disadvantages of its algorithms, which include mathematical programming method, artificial potential field method, graphic-based method, and intelligent optimization algorithm, are also analyzed. Finally, open problems, the future work, and the research focus in UAVs mission planning are summarized. Keywords: unmanned aerial vehicle; mission planning; task assignment; path planning; heuristic algorithm; intelligence optimization algorithm; smoothing; flyable 近年来，随着科学技术的不断发展，信息技术 的日新月异，战争的智能化、信息化和一体化，使 得任务规划成为高技术战争的重要支撑。自 1917 年美国研制出第一架无人机以来，无人机先后经 历了靶机、侦察机和诱饵机几个发展阶段。无人 收稿日期：2018−11−24. 网络出版日期：2019−04−11. 基金项目：国家自然科学基金项目 (61877067，61572435)；教 育部−中国移动联合基金项目 (MCM20170103)；西安 市科技创新项目 (201805029YD7CG13-6)；宁波市自 然科学基金项目 (2016A610035，2017A610119). 通信作者：李博. E-mail：libo202017@163.com. 第 15 卷第 2 期 智 能 系 统 学 报 Vol.15 No.2 2020 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2020
第2期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·205· 机作为一种可重复使用的飞行器，以其结构简 燃料限制等约束，规划出一条可飞、可行和安全 单、续航时间长、造价低、隐蔽性强和安全性高等 的航迹。任务规划按时间划分有离线任务规划和 优势，广泛地应用在信息化战争中执行监视、侦 实时在线任务规划：按规划的对象划分有单无人 察、攻击、战场评估、精确打击、充当诱饵等任 机任务规划和集群无人机系统任务规划。按实现 务，极大地提高了部队的指挥控制和多兵种协作 方式划分有手动任务规划和自动任务规划。手 作战的能力。早在越南战争、中东战争、科索沃 动任务规划是指规划人员按照已有的信息和任务 战争、海湾战争及阿富汗战争中，无人机以其出 要求，辅助计算机来确定无人机的路径、目标要 色的表现受到世界各国的广泛关注。 求和载荷配置。自动任务规划指完全由规划系统 美国是无人机任务规划起步最早、发展最快、 自动生成。从空间角度划分有全局任务规划和局 技术最先进的国家，在国外无人机技术发展的同 部任务规划。全局任务规划多用于目标静止或障 时，中国也先后开启了无人机任务规划的研究。 碍物已知的战场环境；局部任务规划多用于复杂 其中，北京航空航天大学、南京航空航天大学、西 动态环境下。 北工业大学和哈尔滨工业大学等高校先后成立了 本文在全面收集、阅读现有文献基础上，论 无人机相关研究机构，并取得了可喜的研究成 述了3种求解无人机任务分配的方法；4种求解 果。自2000年以来一些民用无人机投入研制，无 路径规划的方法；分析对比了相应典型算法的基 人机任务规划系统也从最初的单平台向多平台交 本原理和优缺点；综合考虑了可飞性、时限性、任 互发展，目前有国防科技大学的多无人机协同任 务均衡、威胁规避和优先级等约束指标，同时，也 务资源分配与编队轨迹优化研究)，哈尔滨工业大 对初步规划出的路径的平滑处理方法进行了探 学的多无人机系统的协同目标分配和航迹规划方 讨；最后，指出无人机任务规划研究存在的不足 法研究、西北工业大学的无人机航路规划方法研 和亟待进一步解决的问题。 究和北京航空航天大学的无人机路径规划技术 研究等。此外，2015年我国在纪念抗战70周年 1任务规划 阅兵式上，首次展示了作战无人机，这表明了我国 无人机系统相较于单架无人机具有更好的容 无人机的发展已经走向高新技术的前沿。 错性和鲁棒性，可以通过各无人机之间的信息交 随着全球格局的不断演变、军事科技的飞速 流，提高完成任务的效率：在多变的战场环境中， 发展，武器装备由机械化发展为信息化，战争方 各无人机可以实时调整路线，规避障碍和威胁， 式较以前有了翻天覆地的变化。单无人机执行任 提高作战效能，增强规划路径的可靠性。。 务的局限性，使得多机协同作战成为当下研究的 无人机系统作为一种典型的多智能体系统， 热点。多机协同执行高危任务，一方面可有效地 可以在无人员参与下自主控制和执行任务，其 降低毁伤概率，另一方面可提高战斗力。在多机 飞行路径与有人机相比，无人机更加依赖预先规 协同执行任务中，当整个无人机系统达到最优 划的路径和实时路径规划，对所规划的路径要求 时，并不能保证每架无人机均能达到最优。本文 更高，故不能简单照搬有人机的路径规划方案。 是在现有文献综述)基础上，对无人机任务规 任务规划的影响要素众多且相互耦合，约束条件 划技术做详细论述。 的非线性、作战过程的复杂性、战场环境的不可 任务规划(mission planning,MP)2-1是指根 测性和规划过程的马尔可夫性等，增加了无人 据作战任务要求、战场环境、敌我双方的作战配 机在作战过程中的难度。为了保证无人机能够在 置和任务载荷等约束条件，规划出作战过程、任 指定时间完成指定作战任务，必须综合考虑战场 务分配和行动路线等。任务规划是各类飞行器， 环境威胁和任务要求等因素，为无人机制定出在 尤其军用飞行器执行任务的重要保证。任务分配 何时何地执行何种任务的可行路线。 和路径规划是任务规划的两个核心组成部分。无 无人机路径规划是物理可飞性、路径安全性 人机任务分配问题46是在满足环境要素和任务 战术可行性、规划实时性、任务可靠性的统一。 需求条件下，为多无人机分配一个或一组有序的 在规划的内容上，任务规划四已经超越了对作战 任务，在最大程度完成任务的基础上，最优化无 的定性指导和定量计算，主要表现在对作战环 人机系统的整体效率和资源配比。无人机路径规 境、作战资源和具体作战样式的精确化、数字化 划4]实质上是一个多约束、多目标的组合优化 描述。任务规划是作战的灵魂，在使用方式上， 问题，根据任务要求、威胁分布、实时机动性能、 规范化指导作战人员的操作行为，并将规划结果
机 [1,2] 作为一种可重复使用的飞行器，以其结构简 单、续航时间长、造价低、隐蔽性强和安全性高等 优势，广泛地应用在信息化战争中执行监视、侦 察、攻击、战场评估、精确打击、充当诱饵等任 务，极大地提高了部队的指挥控制和多兵种协作 作战的能力。早在越南战争、中东战争、科索沃 战争、海湾战争及阿富汗战争中，无人机以其出 色的表现受到世界各国的广泛关注。 美国是无人机任务规划起步最早、发展最快、 技术最先进的国家，在国外无人机技术发展的同 时，中国也先后开启了无人机任务规划的研究。 其中，北京航空航天大学、南京航空航天大学、西 北工业大学和哈尔滨工业大学等高校先后成立了 无人机相关研究机构，并取得了可喜的研究成 果。自 2000 年以来一些民用无人机投入研制，无 人机任务规划系统也从最初的单平台向多平台交 互发展，目前有国防科技大学的多无人机协同任 务资源分配与编队轨迹优化研究[3] ，哈尔滨工业大 学的多无人机系统的协同目标分配和航迹规划方 法研究[4] 、西北工业大学的无人机航路规划方法研 究 [5] 和北京航空航天大学的无人机路径规划技术 研究[6] 等。此外，2015 年我国在纪念抗战 70 周年 阅兵式上，首次展示了作战无人机，这表明了我国 无人机的发展已经走向高新技术的前沿。 随着全球格局的不断演变、军事科技的飞速 发展，武器装备由机械化发展为信息化，战争方 式较以前有了翻天覆地的变化。单无人机执行任 务的局限性，使得多机协同作战成为当下研究的 热点。多机协同执行高危任务，一方面可有效地 降低毁伤概率，另一方面可提高战斗力。在多机 协同执行任务中，当整个无人机系统达到最优 时，并不能保证每架无人机均能达到最优。本文 是在现有文献综述[7-11] 基础上，对无人机任务规 划技术做详细论述。 任务规划 (mission planning，MP)[12-13] 是指根 据作战任务要求、战场环境、敌我双方的作战配 置和任务载荷等约束条件，规划出作战过程、任 务分配和行动路线等。任务规划是各类飞行器， 尤其军用飞行器执行任务的重要保证。任务分配 和路径规划是任务规划的两个核心组成部分。无 人机任务分配问题[14-16] 是在满足环境要素和任务 需求条件下，为多无人机分配一个或一组有序的 任务，在最大程度完成任务的基础上，最优化无 人机系统的整体效率和资源配比。无人机路径规 划 [14-18] 实质上是一个多约束、多目标的组合优化 问题，根据任务要求、威胁分布、实时机动性能、 燃料限制等约束，规划出一条可飞、可行和安全 的航迹。任务规划按时间划分有离线任务规划和 实时在线任务规划；按规划的对象划分有单无人 机任务规划和集群无人机系统任务规划。按实现 方式划分有手动任务规划和自动任务规划[12]。手 动任务规划是指规划人员按照已有的信息和任务 要求，辅助计算机来确定无人机的路径、目标要 求和载荷配置。自动任务规划指完全由规划系统 自动生成。从空间角度划分有全局任务规划和局 部任务规划。全局任务规划多用于目标静止或障 碍物已知的战场环境；局部任务规划多用于复杂 动态环境下。 本文在全面收集、阅读现有文献基础上，论 述了 3 种求解无人机任务分配的方法；4 种求解 路径规划的方法；分析对比了相应典型算法的基 本原理和优缺点；综合考虑了可飞性、时限性、任 务均衡、威胁规避和优先级等约束指标，同时，也 对初步规划出的路径的平滑处理方法进行了探 讨；最后，指出无人机任务规划研究存在的不足 和亟待进一步解决的问题。 1 任务规划 无人机系统相较于单架无人机具有更好的容 错性和鲁棒性，可以通过各无人机之间的信息交 流，提高完成任务的效率；在多变的战场环境中， 各无人机可以实时调整路线，规避障碍和威胁， 提高作战效能，增强规划路径的可靠性。。 无人机系统作为一种典型的多智能体系统， 可以在无人员参与下自主控制和执行任务[19] ，其 飞行路径与有人机相比，无人机更加依赖预先规 划的路径和实时路径规划，对所规划的路径要求 更高，故不能简单照搬有人机的路径规划方案。 任务规划的影响要素众多且相互耦合，约束条件 的非线性、作战过程的复杂性、战场环境的不可 测性和规划过程的马尔可夫性[20] 等，增加了无人 机在作战过程中的难度。为了保证无人机能够在 指定时间完成指定作战任务，必须综合考虑战场 环境威胁和任务要求等因素，为无人机制定出在 何时何地执行何种任务的可行路线。 无人机路径规划是物理可飞性、路径安全性、 战术可行性、规划实时性、任务可靠性的统一[14]。 在规划的内容上，任务规划[21] 已经超越了对作战 的定性指导和定量计算，主要表现在对作战环 境、作战资源和具体作战样式的精确化、数字化 描述。任务规划是作战的灵魂，在使用方式上， 规范化指导作战人员的操作行为，并将规划结果 第 2 期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·205·
·206· 智能系统学报 第15卷 直接加载给无人机设备。 类和数量前提下，充分考虑战场环境、任务要求 任务分配和路径规划是无人机任务规划的两 和载荷能力约束，研究如何将合适的任务在合适 个重要环节，这两个过程是紧密相连的。在规划 的时间分配给合适的无人机，从而为每架无人机 过程中既要考虑燃料消耗、战场环境威胁、飞行 分配一个或一组有序的任务，使得无人机整体作 时间和转弯半径、爬升率等显性约束，也要考虑 战效率达到最优。多无人机本质上是单无人机通 威胁碰撞、任务均衡、攻击序列和目标价值等隐 过信息交互进行协同合作，其中协同川是指在任 性约束。图1是无人机任务规划流程图。 务分配基础上确定各个平台要执行的任务和执行 任务的先后顺序。典型的任务分配模型有基于旅 接收和输入任务 行商(travelling salesman problem,TSP)模型，混合 整数线性规划(mixed-integer linear programming, 数据准备 MLP)模型、车辆路由问题(VRP)模型P)、指派问 题模型及运输问题模型。其中，混合整数线性规 目标分析 划模型具有较强的可扩展性，在任务规划问题中 得到广泛应用。指派问题模型实质上是0-1规划 综合威胁评估 问题的一种特例。 1.1.1任务分配约束指标及问题建模 无人机任务分配的约束指标主要有任务均 战术选择 衡、毁伤代价、飞行距离、消耗成本与规划目标收 益等。其中，任务均衡其目的是实现无人机的负 任务初分配 载均衡，从而降低无人机在执行任务时的损伤 率。任务均衡可分为多个并行任务的均衡和各子 载荷规划 路径规划 链路规划 任务重规划 问题的均衡。图2为无人机任务分配结构图。 无人机N 调整链路、航 无人机2 任务预演评估 路、载荷等 无人机1 N 是否满足任务要求 任务规划输出 攻击任务制 图1无人机任务规划流程 Fig.1 The framework of UAV mission planning 无人机任务规划技术是通过接收和输入任务 追踪任务】 模块接收来自上级的作战任务信息；其次，通过 搜索任务M 信息采集和管理模块进行相关数据准备、分析， 并结合实时情报或数据库中的气象、威胁和目标 图2无人机任务分配图 等，建立约束条件，给出战术及初步任务分配结 Fig.2 Task assignment of UAV 果；然后，由环境建模，对载荷、航路和链路进行 假设有M项任务、N架无人机，每架无人机 规划分配，通过对任务进行预演，评估所规划任 可执行多项任务、但每项任务只能够分配给一架 务的安全性、效能及完成的程度，确定优劣，对不 无人机。任务分配的目标是最优化全局目标函数四。 满足规划要求的进行重规划循环处理，直到所规 划路径达到最佳，最后，按照标准格式输出规划 的结果，并加载到无人机终端平台。 1 无人机分配到任务j 否则 1.1多无人机的任务分配问题 任务分配2-2是运筹学中基本的组合优化问 (1) 题。多无人机任务分配)是指在给定无人机种 式中：∑列≤1保证每项任务最多被执行一次；R
直接加载给无人机设备。 任务分配和路径规划是无人机任务规划的两 个重要环节，这两个过程是紧密相连的。在规划 过程中既要考虑燃料消耗、战场环境威胁、飞行 时间和转弯半径、爬升率等显性约束，也要考虑 威胁碰撞、任务均衡、攻击序列和目标价值等隐 性约束。图 1 是无人机任务规划流程图。 接收和输入任务 数据准备 目标分析 综合威胁评估 战术选择 任务初分配 任务预演评估 是否满足任务要求 任务规划输出 载荷规划 路径规划 链路规划 调整链路、航 路、载荷等 Y 任务重规划 N 图 1 无人机任务规划流程 Fig. 1 The framework of UAV mission planning 无人机任务规划技术是通过接收和输入任务 模块接收来自上级的作战任务信息；其次，通过 信息采集和管理模块进行相关数据准备、分析， 并结合实时情报或数据库中的气象、威胁和目标 等，建立约束条件，给出战术及初步任务分配结 果；然后，由环境建模，对载荷、航路和链路进行 规划分配，通过对任务进行预演，评估所规划任 务的安全性、效能及完成的程度，确定优劣，对不 满足规划要求的进行重规划循环处理，直到所规 划路径达到最佳，最后，按照标准格式输出规划 的结果，并加载到无人机终端平台。 1.1 多无人机的任务分配问题 任务分配[21-22] 是运筹学中基本的组合优化问 题。多无人机任务分配[14] 是指在给定无人机种 类和数量前提下，充分考虑战场环境、任务要求 和载荷能力约束，研究如何将合适的任务在合适 的时间分配给合适的无人机，从而为每架无人机 分配一个或一组有序的任务，使得无人机整体作 战效率达到最优。多无人机本质上是单无人机通 过信息交互进行协同合作，其中协同[21] 是指在任 务分配基础上确定各个平台要执行的任务和执行 任务的先后顺序。典型的任务分配模型有基于旅 行商 (travelling salesman problem，TSP) 模型，混合 整数线性规划 (mixed-integer linear programming， MILP) 模型、车辆路由问题 (VRP) 模型[23] 、指派问 题模型及运输问题模型。其中，混合整数线性规 划模型具有较强的可扩展性，在任务规划问题中 得到广泛应用。指派问题模型实质上是 0-1 规划 问题的一种特例。 1.1.1 任务分配约束指标及问题建模 无人机任务分配的约束指标主要有任务均 衡、毁伤代价、飞行距离、消耗成本与规划目标收 益等。其中，任务均衡其目的是实现无人机的负 载均衡，从而降低无人机在执行任务时的损伤 率。任务均衡可分为多个并行任务的均衡和各子 问题的均衡。图 2 为无人机任务分配结构图。 攻击任务j 无人机N 无人机1 无人机2 . . . . . . . . . 追踪任务1 救援任务2 搜索任务M 图 2 无人机任务分配图 Fig. 2 Task assignment of UAV 假设有 M 项任务、 N 架无人机，每架无人机 可执行多项任务、但每项任务只能够分配给一架 无人机。任务分配的目标是最优化全局目标函数[24]。 min∑N i=1 ∑M j=1 Ri j ·si j s.t. ∑N i=1 si j ⩽ 1,∀ j ∈ J,si j = { 1, 无人机i分配到任务j 0, 否则 (1) ∑N i=1 式中： si j ⩽ 1 保证每项任务最多被执行一次； Ri j ·206· 智 能 系 统 学 报 第 15 卷
第2期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·207· 是第i架无人机，执行第j项任务时的代价。 然后，对新个体进行适应度估计，挑选出最优个 1.1.2多无人机任务分配分类标准 体进行下一轮循环。遗传算法具有较强的全局搜 任务分配从任务角度，可以分为单任务分配 索能力、搜索效率高和鲁棒性强等优点。但是， 和多任务分配。单任务分配指每架无人机最多被 该算法实时性较差，收敛速度较慢，运算时间较 分配一项任务，且能够顺利完成。多任务分配指 长，效率低，易出现早熟现象，进而使算法陷入局 每架无人机被分配的任务不止一项，且被分配的 部最优。图3是遗传算法在无人机任务分配中的 任务具有一定的耦合性。从目标状态划分可以分 结构流程。 为静态任务分配、动态任务分配2,2和综合任务 分配。静态任务分配指多无人机系统攻击或侦查 任务点结合开始 多个位置坐标已知的静态目标。动态任务分配指 无人机侦查或攻击状态位置随战场环境而变化的 任务编码成串形式 目标：按照无人机执行任务的方式和任务之间的 关联性分为相关性任务分配和独立性任务分配。 变量初始化 11.3典型的多无人机任务分配模型和代表算法 设置交叉变异 单无人机的多任务时序分配可以简单地抽象 e 为旅行商问题模型：多无人机多任务的目标分配 群体1 可简化为指派问题模型。旅行商问题(travelling salesman problem,TSP)2-28模型原理是一个商人 计算每项任务上的适应值 要遍历n个城市，需要从多条路径中选择一条最 短路径，且这条路径将所有城市遍历一遍后，能 选择、交叉、变异 群体1=群体2，则修改交 够回到起点。TSP问题是一个NP问题，目前没 叉变异概率 有较好的精确算法得到最优解，多使用智能优化 群体1的代数+1 算法得到次优解。指派问题(assignment problem, AP)模型原理是将n个人和n项任务一一对应， 群体2的代数+1 实现最佳完成任务的目的。指派问题可用匈牙利 算法来求解。 N 求解任务分配问题的方法有启发式算法、数 满足条件 学规划方法和随机性智能优化算法。 y 1)启发式算法。启发式算法是指在不能直接 选择最优任务分配方式 求解问题最优解下，折中得到满足计算时间和分 配目的的次优解。其代表性的算法有禁忌搜索 图3遗传算法在任务分配中的流程图 (tabu search,.TS)、模拟退火(simulated annealing, Fig.3 The framework of GA in task assignment SA)、遗传算法(genetic algorithm,GA)与聚类算 聚类算法中常用的有K-means算法。K- 法。启发式算法简单易行、计算速度快、兼容性 means刃算法其思想是在n个数据中，任意选择m 强。然而，计算量较大、对初始参数要求较高、且 个作为初始聚类中心，然后将每个任务作为簇， 不能保证得到最优解。 进行聚类。该方法是以平均值作为聚类中心的分 禁忌搜索算法29-是Glover于1977年提出， 割聚类法，多用于连续性空间。算法的时间复杂 通过引入的存储结构和相应的禁忌准则以避免迂 度、空间复杂度低。 回搜索，由藐视准则赦免一些被禁忌的优良状 2)数学规划方法。数学规划方法主要有枚举 态，以达到全局优化。禁忌搜索算法具有独特的 法(enumeration algorithm)、动态规划(dynamic)。 记忆功能、爬山搜索能力强及收敛速度快等优 动态规划是20世纪50年代初，美国数学家 势，然而搜索邻域、禁忌表及初始解选取对其影 R.E.Bellman等在研究多阶段决策优化问题时提 响较大。 出的，其思想是将多阶段决策问题转化为单阶段 遗传算法0,3是通过模拟达尔文提出的生物 优化问题，以降低决策问题的难度。动态是指 进化论的自然选择和遗传学机理，达到搜索最优 在问题的多阶段决策中，当决策顺序和步骤有所 解的目的。在遗传算法中，通过种群个体的变 变化时，将引起状态的变化和转移。动态规划的 异、交叉和遗传等操作模拟染色体的进化行为， 实现效率较高，但是易出现维数灾难。该算法不
是第 i 架无人机，执行第 j 项任务时的代价。 1.1.2 多无人机任务分配分类标准 任务分配从任务角度，可以分为单任务分配 和多任务分配。单任务分配指每架无人机最多被 分配一项任务，且能够顺利完成。多任务分配指 每架无人机被分配的任务不止一项，且被分配的 任务具有一定的耦合性。从目标状态划分可以分 为静态任务分配、动态任务分配[22,25] 和综合任务 分配。静态任务分配指多无人机系统攻击或侦查 多个位置坐标已知的静态目标。动态任务分配指 无人机侦查或攻击状态位置随战场环境而变化的 目标；按照无人机执行任务的方式和任务之间的 关联性分为相关性任务分配和独立性任务分配。 1.1.3 典型的多无人机任务分配模型和代表算法 n n n 单无人机的多任务时序分配可以简单地抽象 为旅行商问题模型；多无人机多任务的目标分配 可简化为指派问题模型。旅行商问题 (travelling salesman problem，TSP)[26-28] 模型原理是一个商人 要遍历 个城市，需要从多条路径中选择一条最 短路径，且这条路径将所有城市遍历一遍后，能 够回到起点。TSP 问题是一个 NP 问题，目前没 有较好的精确算法得到最优解，多使用智能优化 算法得到次优解。指派问题 (assignment problem， AP) 模型原理是将 个人和 项任务一一对应， 实现最佳完成任务的目的。指派问题可用匈牙利 算法来求解。 求解任务分配问题的方法有启发式算法、数 学规划方法和随机性智能优化算法。 1) 启发式算法。启发式算法是指在不能直接 求解问题最优解下，折中得到满足计算时间和分 配目的的次优解。其代表性的算法有禁忌搜索 (tabu search，TS)、模拟退火 (simulated annealing， SA)、遗传算法 (genetic algorithm，GA) 与聚类算 法。启发式算法简单易行、计算速度快、兼容性 强。然而，计算量较大、对初始参数要求较高、且 不能保证得到最优解。 禁忌搜索算法[29-32] 是 Glover 于 1977 年提出， 通过引入的存储结构和相应的禁忌准则以避免迂 回搜索，由藐视准则赦免一些被禁忌的优良状 态，以达到全局优化。禁忌搜索算法具有独特的 记忆功能、爬山搜索能力强及收敛速度快等优 势，然而搜索邻域、禁忌表及初始解选取对其影 响较大。 遗传算法[30-36] 是通过模拟达尔文提出的生物 进化论的自然选择和遗传学机理，达到搜索最优 解的目的。在遗传算法中，通过种群个体的变 异、交叉和遗传等操作模拟染色体的进化行为， 然后，对新个体进行适应度估计，挑选出最优个 体进行下一轮循环。遗传算法具有较强的全局搜 索能力、搜索效率高和鲁棒性强等优点。但是， 该算法实时性较差，收敛速度较慢，运算时间较 长，效率低，易出现早熟现象，进而使算法陷入局 部最优。图 3 是遗传算法在无人机任务分配中的 结构流程。 群体1 计算每项任务上的适应值 选择、交叉、变异 群体1的代数+1 任务编码成串形式 变量初始化、 设置交叉变异 群体2的代数+1 满足条件 群体1=群体2，则修改交 叉变异概率 选择最优任务分配方式 任务点结合开始 Y N 图 3 遗传算法在任务分配中的流程图 Fig. 3 The framework of GA in task assignment n m 聚类算法中常用的有 K-means 算法。Kmeans [37] 算法其思想是在 个数据中，任意选择 个作为初始聚类中心，然后将每个任务作为簇， 进行聚类。该方法是以平均值作为聚类中心的分 割聚类法，多用于连续性空间。算法的时间复杂 度、空间复杂度低。 2) 数学规划方法。数学规划方法主要有枚举 法 (enumeration algorithm)、动态规划 (dynamic)。 动态规划是 20 世纪 50 年代初，美国数学家 R. E. Bellman 等在研究多阶段决策优化问题时提 出的，其思想是将多阶段决策问题转化为单阶段 优化问题，以降低决策问题的难度。动态[14] 是指 在问题的多阶段决策中，当决策顺序和步骤有所 变化时，将引起状态的变化和转移。动态规划的 实现效率较高，但是易出现维数灾难。该算法不 第 2 期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·207·
·208· 智能系统学报 第15卷 像其他算法那样有明确的步骤，需要结合动态规 Dorigo等在蚁群算法基础上进一步发展的一种通 划的思想设计相应的优化算法。 用的优化技术s0。其流程图见图4。 分支定界法B是一种求解整数规划B问题 常用的广度优先算法，它把全部可行解空间反复 开始 的分割成越来越小的子集，即分支；然后，对每 个子集内的解集，计算下一个目标的上下界，即 初始化参数，m只蚂蚁位于起始 点等待出发 定界；每次分支之后，凡是不满足界限要求的可 行解目标值直接删除，即剪枝；最后，将剩下的 日 子集加入到可行集中，如此循环重复，直至找到 每只蚂蚁根据状态转移概率选择下 一个到达点，实现任务分配 问题的可行解；分支定界算法多用于求解约束条 件和变量数目较少的约束问题的一个解或在求 计算蚂蚁分配目标函数.保存最 解的一组解中找到满足某一约束条件的极值，该 优分配解 算法灵活且便于求解，但计算量较大，且求解效 率低。 根据目标函数，调整信息 3)随机性智能优化算法。随机性智能优化 算法)是受自然现象或社会行为启发而发展 的一种随机搜索方法，最早于20世纪70年代被 是否满足迭代信息 提出，该算法在求解大规模优化问题时，可获得 较好的解。进化算法、群智能算法、人工免疫算 y 法、禁忌搜索算法、模拟退火算法是典型的智能 输出最优分配方案 优化算法。 结束 群智能优化算法于1989年由Gerardo B提 出，是将代表候选解的多个个体组成一个群体， 图4蚊群优化算法求解任务分配 通过部分或全体之间的信息交互，达到寻优的目 Fig.4 The framework of ACO in task allocation 的。代表性的算法有粒子群优化算法、蚁群优化 由上可知随机智能算法易实现、搜索能力 算和鱼群算法。 强、鲁棒性好、计算复杂度低且性能优越，在大规 进化算法(evolutionary computation)241是以 模并行计算中优势凸显。典型的智能优化算法： 达尔文的进化论为基础，是自然界与遗传机制的 蚁群算法、遗传算法和模拟退火算法均具有较强 自组织、自适应搜索过程，主要由选择、重组和变 的鲁棒性，且扩展性强，能与其他算法混合使 异3个环节组成。代表性的算法有遗传算法、差 用。遗传算法可适用于大规模、非线性问题，通 分进化算法等。 用性强。蚁群算法和模拟退火算法易求得全局最 粒子群优化算法46是模拟鸟群寻找食物的 优解，而粒子群优化算法求得的解多为局部最 一种方法，1995年粒子群算法由Kennedy和Eber- 优。粒子群算法相较于其他智能算法的显著区别 hart首次提出，其原理是通过更新惯性系数、社会 在于算法中需要调整的参数少。在一些典型的优 系数和认知系数，由适应度函数评估局部最优和 化问题中，粒子群算法比遗传算法获得更好的优 全局最优等操作，实现集群最优搜索。粒子群算 化结果倒。 法计算简单、鲁棒性好、搜索能力强且收敛速度 综上所述，无人机任务分配的目的即是寻找 快，然而该算法易出现早熟收敛和停滞倾向。 最优匹配方案，任务分配和路径规划是两个密不 蚁群算法974是一种启发式算法，依据蚂蚁 可分的环节，在最优分配的基础上，才能规划出 在行动中留下的信息素，其他蚂蚁通过协同感知 可行、安全的飞行路径。本节在给出任务分配的 信息素浓度，倾向于向信息素浓度高的位置移 相关概念基础上，就任务分配的几个约束指标给 动，最终以一种有效的方式找到蚁穴到食物之间 出常用模型及分类标准，由2种典型的任务分配 的最短路径。ACO算法关键在于信息素更新、状 模型引出启发式算法、数学规划方法和随机性智 态转移和启发式函数的构建。该算法搜索较优解 能优化算法3种求解任务分配的方法，并给出相 的能力强，扩充性好，但是易陷入对某一区域的 应算法的优缺点。表1是任务分配算法的对比 过度搜索，且求解速度较慢。蚁群优化算法是M 结果
像其他算法那样有明确的步骤，需要结合动态规 划的思想设计相应的优化算法。 分支定界法[38] 是一种求解整数规划[39] 问题 常用的广度优先算法，它把全部可行解空间反复 的分割成越来越小的子集，即分支；然后，对每 个子集内的解集，计算下一个目标的上下界，即 定界；每次分支之后，凡是不满足界限要求的可 行解目标值直接删除，即剪枝；最后，将剩下的 子集加入到可行集中，如此循环重复，直至找到 问题的可行解；分支定界算法多用于求解约束条 件和变量数目较少的约束问题的一个解或在求 解的一组解中找到满足某一约束条件的极值，该 算法灵活且便于求解，但计算量较大，且求解效 率低。 3) 随机性智能优化算法。随机性智能优化 算法[40-41] 是受自然现象或社会行为启发而发展 的一种随机搜索方法，最早于 20 世纪 70 年代被 提出，该算法在求解大规模优化问题时，可获得 较好的解。进化算法、群智能算法、人工免疫算 法、禁忌搜索算法、模拟退火算法是典型的智能 优化算法。 群智能优化算法于 1989 年由 Gerardo B 提 出，是将代表候选解的多个个体组成一个群体， 通过部分或全体之间的信息交互，达到寻优的目 的。代表性的算法有粒子群优化算法、蚁群优化 算和鱼群算法。 进化算法 (evolutionary computation)[42-43] 是以 达尔文的进化论为基础，是自然界与遗传机制的 自组织、自适应搜索过程，主要由选择、重组和变 异 3 个环节组成。代表性的算法有遗传算法、差 分进化算法等。 粒子群优化算法[44-46] 是模拟鸟群寻找食物的 一种方法，1995 年粒子群算法由 Kennedy 和 Eberhart 首次提出，其原理是通过更新惯性系数、社会 系数和认知系数，由适应度函数评估局部最优和 全局最优等操作，实现集群最优搜索。粒子群算 法计算简单、鲁棒性好、搜索能力强且收敛速度 快，然而该算法易出现早熟收敛和停滞倾向。 蚁群算法[19,47-48] 是一种启发式算法，依据蚂蚁 在行动中留下的信息素，其他蚂蚁通过协同感知 信息素浓度，倾向于向信息素浓度高的位置移 动，最终以一种有效的方式找到蚁穴到食物之间 的最短路径。ACO 算法关键在于信息素更新、状 态转移和启发式函数的构建。该算法搜索较优解 的能力强，扩充性好，但是易陷入对某一区域的 过度搜索，且求解速度较慢。蚁群优化算法是 M. Dorigo 等在蚁群算法基础上进一步发展的一种通 用的优化技术[48-50]。其流程图见图 4。 开始 初始化参数，m只蚂蚁位于起始 点等待出发 计算蚂蚁分配目标函数，保存最 优分配解 每只蚂蚁根据状态转移概率选择下 一个到达点，实现任务分配 根据目标函数，调整信息 是否满足迭代信息 输出最优分配方案 结束 Y N 图 4 蚁群优化算法求解任务分配 Fig. 4 The framework of ACO in task allocation 由上可知随机智能算法易实现、搜索能力 强、鲁棒性好、计算复杂度低且性能优越，在大规 模并行计算中优势凸显。典型的智能优化算法： 蚁群算法、遗传算法和模拟退火算法均具有较强 的鲁棒性，且扩展性强，能与其他算法混合使 用。遗传算法可适用于大规模、非线性问题，通 用性强。蚁群算法和模拟退火算法易求得全局最 优解，而粒子群优化算法求得的解多为局部最 优。粒子群算法相较于其他智能算法的显著区别 在于算法中需要调整的参数少。在一些典型的优 化问题中，粒子群算法比遗传算法获得更好的优 化结果[51]。 综上所述，无人机任务分配的目的即是寻找 最优匹配方案，任务分配和路径规划是两个密不 可分的环节，在最优分配的基础上，才能规划出 可行、安全的飞行路径。本节在给出任务分配的 相关概念基础上，就任务分配的几个约束指标给 出常用模型及分类标准，由 2 种典型的任务分配 模型引出启发式算法、数学规划方法和随机性智 能优化算法 3 种求解任务分配的方法，并给出相 应算法的优缺点。表 1 是任务分配算法的对比 结果。 ·208· 智 能 系 统 学 报 第 15 卷