第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 卷
第2期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·209· 表1任务分配算法对比 Table 1 Comparison of task allocation algorithms 任务分配 求解算法 容错性鲁棒性动态性协同性精确性规模大小计算速度 启发式算法 聚类算法 较强 差 强 强 低 大 快 枚举法 强 强 弱 强 高 小 慢 动态规划法 弱 较强 强 强 高 大 快 数学规划方法 分支定界方法 强 强 弱 弱 高 大 快 混合整数线性规划法 较强 强 强 高 大 较快 匈牙利算法 弱 强 弱 强 高 大 慢 禁忌搜索算法 强 较强 强 强 较高 小 快 模拟退火算法 强 较强 较强 强 较高 小 快 遗传算法 强 强 较强 强 较高 大 慢 随机性智能优化算法 粒子群优化算法 较强 较强 强 弱 较高 大 快 蚁群优化算法 强 强 强 强 较高 大 快 进化算法 强 强 强 强 较高 大 快 1.2多无人机的路径规划 5)输出规划的路径结果。 随着军事需求的不断增加，多无人机协同路 1.2.1多无人机路径规划的约束指标 径规划问题2、未知环境中动态规划问题逐渐成 多无人机路径规划的约束条件20，s3s1有地形 为当前研究多无人机路径规划的重点。相较于单 环境约束、平台自身约束、任务约束、可飞性约 无人机路径规划问题，多无人机协同路径规划在 束、威胁约束、时限性约束、优先级约束和能量约 求解方式和计算量上有一定的难度。 束等。 路径规划是任务规划的核心环节，无人机路 1)平台自身约束。最大、最小飞行高度将直 径规划4，s是指在给定的规划空间中，找出无人 接影响无人机在飞行中遇到威胁时能否安全行 机从起始位置到目标位置，且满足约束条件和性 驶，并顺利完成任务。最大飞行高度通常比无人 能指标的最优飞行路径。路径规划是有约束的非 机的实际升限稍低些，最小飞行高度通常是用地 线性规划问题，可用式(2)表示： 面的相对高度表示，若飞行过低，将增加与地面 了minf(x) 相撞的概率。 s.t.x∈Q (2) 最大、最小飞行速度保证了无人机在某段飞 这里f(x)是目标函数，x=(,x2,…,x)∈R为决 行路段内，其飞行速度保持在某一有限区间内。 策变量，2cR"是约束集。 无人机的动力系统和环境因素是影响速度的主要 为了保证规划路径的可实现性、安全性和最 因素。 优性，必须综合考虑平台机动性能等约束。多无 最大转向角决定着每架无人机的转弯半径和 人机路径规划研究的重点是建立描述具体任务的 飞行速率，它影响无人机从某段航路飞到另一段 数学模型，设定约束条件和优化求解的方法。当 航路时能否避免频繁的转弯。 战场态势发生改变或作战任务发生变更时，原规 最小转弯半径受空气速度和无人机的机动性 划路径不再满足当前需求，需要重新按照飞行器 能影响，无人机在飞行过程中，其转弯半径不得 的飞行状态、油耗量、威胁程度和时间最小原则 小于最小转弯半径。 重新规划新的航线。下面是无人机路径规划的步骤。 最大爬升角、下滑角控制着无人机机身的垂 1)根据起始点、任务区域、环境地形条件及 直姿态，将保证规划路径的高度方向、下滑角度 空中威胁，确定路径规划的规划空间； 在某一区间内。 2)根据任务约束、飞行器的性能限制，确定 2)任务约束。时间约束指无人机完成规划任 路径规划的约束条件和数学模型： 务所需的总时间长度。 3)选择合适的搜索算法，在规划空间中寻找 路径约束中的重要约束是最大路径长度值， 满足约束条件的最优可行路径； 若是所规划的路径超出这一有效值，则规划出的 4)对搜索到的路径进行平滑和评估处理； 路径是无效的。最大路径长度取决于无人机自身
表 1 任务分配算法对比 Table 1 Comparison of task allocation algorithms 任务分配 求解算法 容错性 鲁棒性 动态性 协同性 精确性 规模大小 计算速度 启发式算法 聚类算法 较强 差 强 强 低 大 快 数学规划方法 枚举法 强 强 弱 强 高 小 慢 动态规划法 弱 较强 强 强 高 大 快 分支定界方法 强 强 弱 弱 高 大 快 混合整数线性规划法 弱 较强 强 强 高 大 较快 匈牙利算法 弱 强 弱 强 高 大 慢 随机性智能优化算法 禁忌搜索算法 强 较强 强 强 较高 小 快 模拟退火算法 强 较强 较强 强 较高 小 快 遗传算法 强 强 较强 强 较高 大 慢 粒子群优化算法 较强 较强 强 弱 较高 大 快 蚁群优化算法 强 强 强 强 较高 大 快 进化算法 强 强 强 强 较高 大 快 1.2 多无人机的路径规划 随着军事需求的不断增加，多无人机协同路 径规划问题[21] 、未知环境中动态规划问题逐渐成 为当前研究多无人机路径规划的重点。相较于单 无人机路径规划问题，多无人机协同路径规划在 求解方式和计算量上有一定的难度。 路径规划是任务规划的核心环节，无人机路 径规划[14,52] 是指在给定的规划空间中，找出无人 机从起始位置到目标位置，且满足约束条件和性 能指标的最优飞行路径。路径规划是有约束的非 线性规划问题，可用式 (2) 表示： { min f (x) s.t. x ∈ Ω (2) f (x) x = (x1, x2,··· , xn) T ∈ R Ω ⊂ R n 这里 是目标函数， 为决 策变量， 是约束集。 为了保证规划路径的可实现性、安全性和最 优性，必须综合考虑平台机动性能等约束。多无 人机路径规划研究的重点是建立描述具体任务的 数学模型，设定约束条件和优化求解的方法。当 战场态势发生改变或作战任务发生变更时，原规 划路径不再满足当前需求，需要重新按照飞行器 的飞行状态、油耗量、威胁程度和时间最小原则 重新规划新的航线。下面是无人机路径规划的步骤。 1) 根据起始点、任务区域、环境地形条件及 空中威胁，确定路径规划的规划空间； 2) 根据任务约束、飞行器的性能限制，确定 路径规划的约束条件和数学模型； 3) 选择合适的搜索算法，在规划空间中寻找 满足约束条件的最优可行路径； 4) 对搜索到的路径进行平滑和评估处理； 5) 输出规划的路径结果。 1.2.1 多无人机路径规划的约束指标 多无人机路径规划的约束条件[20,53-55] 有地形 环境约束、平台自身约束、任务约束、可飞性约 束、威胁约束、时限性约束、优先级约束和能量约 束等。 1) 平台自身约束。最大、最小飞行高度将直 接影响无人机在飞行中遇到威胁时能否安全行 驶，并顺利完成任务。最大飞行高度通常比无人 机的实际升限稍低些，最小飞行高度通常是用地 面的相对高度表示，若飞行过低，将增加与地面 相撞的概率。 最大、最小飞行速度保证了无人机在某段飞 行路段内，其飞行速度保持在某一有限区间内。 无人机的动力系统和环境因素是影响速度的主要 因素。 最大转向角决定着每架无人机的转弯半径和 飞行速率，它影响无人机从某段航路飞到另一段 航路时能否避免频繁的转弯。 最小转弯半径受空气速度和无人机的机动性 能影响，无人机在飞行过程中，其转弯半径不得 小于最小转弯半径。 最大爬升角、下滑角控制着无人机机身的垂 直姿态，将保证规划路径的高度方向、下滑角度 在某一区间内。 2) 任务约束。时间约束指无人机完成规划任 务所需的总时间长度。 路径约束中的重要约束是最大路径长度值， 若是所规划的路径超出这一有效值，则规划出的 路径是无效的。最大路径长度取决于无人机自身 第 2 期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·209·
·210· 智能系统学报 第15卷 携带的燃料、无人机所允许的飞行速度和飞行时间。 少无人机在执行任务阶段因链路中断，导致规划 3)可飞性约束。现有算法规划出的路径多是 失败。 由直线组成，而在实际的飞行中直线交叉位置很 1.2.2多无人机路径规划的分类标准 难保证路径的可行性。Dubinsts6-s8)路径、二维 根据规划空间的特性可分为二维路径规划和 Clothoid、PH曲线S9-6o和Metropolisriterion可 三维路径规划；根据规划的时间特性分为预先静 用于平滑处理无人机的飞行路径。在用Dubins 态路径规划和实时动态路径规划：根据规划对象 曲线平滑处理路径时，由于Dubin曲率的不变性， 的数量分为单机路径规划和多机协同路径规划。 可将Dubins曲线结合Clothoid或PH曲线来优化 预先静态路径规划是指无人机起飞前，已知威胁 路径。 和目标位置等信息，所规划出的路径精度高，但 4)威胁约束。无人机路径规划面临的威胁主 实时性差。实时动态路径规划，重在“实时性” 要有地形威胁、环境威胁和敌方威胁，根据威胁 在规划中遇到威胁时，无人机能够实时调整路 的强度和覆盖范围将其分为点威胁和区域威胁。 线，重新规划出满足新的约束条件的路径。 点威胁指无人机仅受某单一威胁源影响。区域威 1.2.3多无人机路径规划的基本方法 胁指由多个威胁源组成的扇状威胁域。威胁的大 近年来关于无人机路径规划的研究已有很 小和强度将直接影响规划中无人机的路径选择、 多，这里将求解路径规划的方法分为数学规划方 载荷约束和武器的使用。 法、人工势场法6、基于图形学的方法和智能优 5)时限性约束。无人机路径规划的时限性主 化算法4种。 要指无人机系统的时间约束、空间约束和顺序约 1)数学规划方法。数学规划方法有动态规划 束。时间约束是指在执行飞行任务时，根据执行 算法和非线性规划算法。其中，非线性规划方法 任务的优先级和无人机自身机动性能约束，规划 于1939年首次被提出后，主要用于求解非线性目 出无人机飞行时间的先后顺序；空间约束保证了 标函数或约束条件中含有非线性约束的问题。非 每架无人机的飞行路径无交叉碰撞。顺序约束是 线性规划问题又可分为有约束的非线性规划问题 指规划出无人机飞行的先后顺序。时间约束、空 和无约束的非线性规划问题。 间约束和顺序约束是密不可分的，可通过时间调 2)人工势场法。美国斯坦福大学教授Ous 配避开空间规划和顺序规划的冲突，也可以通过 sama Khatib于20世纪80年代首次提出了人工势 空间调配避免时间规划和顺序规划上的冲突等。 场法26，该算法主要是在无人机任务规划空间 6)优先级约束。无人机任务规划中，为了便 中虚拟出指向目标的引力和远离障碍物的斥力 于任务分配和避免无人机在飞行中发生碰撞等， 从而组成人工力场。人工势场法多用于求解局部 由不同的规划系统和平台，给出机上编号、任务 最优问题，其模型简单、计算量小、实时性好、效 的重要度、目标的重要度和规划路径的长短等优 率高、导向性强且易实现。 先级评价指标，现给出以下约定。 3)基于图形学的方法。基于图形学的路径规 ①在任务规划中任务急迫解决的程度越高， 划方法有拓扑法6、Dijkstra路径搜索算法、模拟 优先级越高； 退火算法、栅格法I66、A'算法、Voronoi图法和随 ②在任务规划中任务的重要程度越高，优先 机路标图PRM)法等。 级就越高； Dijkstra路径搜索算法6)于1959年由荷兰科 ③在任务规划中，当遇到地形、环境威胁和 学家Dijkstra提出，用于扫描搜索从初始位置到 碰撞威胁时，优先解决使目标函数最优的无人机 目标位置的最短路径。该算法简单易行，多用于 路线和相应的任务分配 规模较小的网络。 能量约束。考虑到无人机在执行任务阶段 栅格法s8-69于1968年由W.E.Howden首次 可能出现因能量不足而导致规划失败的问题，规 提出，并应用在路径规划中。为了便于计算机处 划中安排携带能量少的无人机执行路径较短、级 理，将连续空间离散化为网格单元，然后采用启 别较轻的任务，携带能量较多的无人机执行级别 发式算法在网格单元中搜索最优路径。栅格化的 较高、路径较长的任务。 网格大小将直接影响算法的性能。在路径规划 8)载荷和链路约束。为每架无人机实现“量 中，蚁群算法、遗传算法6刀和神经网络算法都会 力而行”，即根据不同无人机执行任务的类型和功 对任务区域做栅格化处理。 能不同，为不同无人机分配适宜的任务载荷，减 模拟退火算法(simulated annealing,.SA)受启
携带的燃料、无人机所允许的飞行速度和飞行时间。 3) 可飞性约束。现有算法规划出的路径多是 由直线组成，而在实际的飞行中直线交叉位置很 难保证路径的可行性。Dubins[56-58] 路径、二维 Clothoid、PH 曲线 [59-60] 和 Metropolis criterion[46] 可 用于平滑处理无人机的飞行路径。在用 Dubins 曲线平滑处理路径时，由于 Dubin 曲率的不变性， 可将 Dubins 曲线结合 Clothoid 或 PH 曲线来优化 路径[4]。 4) 威胁约束。无人机路径规划面临的威胁主 要有地形威胁、环境威胁和敌方威胁，根据威胁 的强度和覆盖范围将其分为点威胁和区域威胁。 点威胁指无人机仅受某单一威胁源影响。区域威 胁指由多个威胁源组成的扇状威胁域。威胁的大 小和强度将直接影响规划中无人机的路径选择、 载荷约束和武器的使用。 5) 时限性约束。无人机路径规划的时限性主 要指无人机系统的时间约束、空间约束和顺序约 束。时间约束是指在执行飞行任务时，根据执行 任务的优先级和无人机自身机动性能约束，规划 出无人机飞行时间的先后顺序；空间约束保证了 每架无人机的飞行路径无交叉碰撞。顺序约束是 指规划出无人机飞行的先后顺序。时间约束、空 间约束和顺序约束是密不可分的，可通过时间调 配避开空间规划和顺序规划的冲突，也可以通过 空间调配避免时间规划和顺序规划上的冲突等。 6) 优先级约束。无人机任务规划中，为了便 于任务分配和避免无人机在飞行中发生碰撞等， 由不同的规划系统和平台，给出机上编号、任务 的重要度、目标的重要度和规划路径的长短等优 先级评价指标，现给出以下约定。 ①在任务规划中任务急迫解决的程度越高， 优先级越高； ②在任务规划中任务的重要程度越高，优先 级就越高； ③在任务规划中，当遇到地形、环境威胁和 碰撞威胁时，优先解决使目标函数最优的无人机 路线和相应的任务分配 7) 能量约束。考虑到无人机在执行任务阶段 可能出现因能量不足而导致规划失败的问题，规 划中安排携带能量少的无人机执行路径较短、级 别较轻的任务，携带能量较多的无人机执行级别 较高、路径较长的任务。 8) 载荷和链路约束。为每架无人机实现“量 力而行”，即根据不同无人机执行任务的类型和功 能不同，为不同无人机分配适宜的任务载荷，减 少无人机在执行任务阶段因链路中断，导致规划 失败。 1.2.2 多无人机路径规划的分类标准 根据规划空间的特性可分为二维路径规划和 三维路径规划；根据规划的时间特性分为预先静 态路径规划和实时动态路径规划；根据规划对象 的数量分为单机路径规划和多机协同路径规划。 预先静态路径规划是指无人机起飞前，已知威胁 和目标位置等信息，所规划出的路径精度高，但 实时性差。实时动态路径规划，重在“实时性”， 在规划中遇到威胁时，无人机能够实时调整路 线，重新规划出满足新的约束条件的路径。 1.2.3 多无人机路径规划的基本方法 近年来关于无人机路径规划的研究已有很 多，这里将求解路径规划的方法分为数学规划方 法、人工势场法[61] 、基于图形学的方法和智能优 化算法 4 种。 1) 数学规划方法。数学规划方法有动态规划 算法和非线性规划算法。其中，非线性规划方法 于 1939 年首次被提出后，主要用于求解非线性目 标函数或约束条件中含有非线性约束的问题。非 线性规划问题又可分为有约束的非线性规划问题 和无约束的非线性规划问题。 2) 人工势场法。美国斯坦福大学教授 Oussama Khatib 于 20 世纪 80 年代首次提出了人工势 场法[62-64] ，该算法主要是在无人机任务规划空间 中虚拟出指向目标的引力和远离障碍物的斥力， 从而组成人工力场。人工势场法多用于求解局部 最优问题，其模型简单、计算量小、实时性好、效 率高、导向性强且易实现。 3) 基于图形学的方法。基于图形学的路径规 划方法有拓扑法[65] 、Dijkstra 路径搜索算法、模拟 退火算法、栅格法 [66] 、A *算法、Voronoi 图法和随 机路标图 (PRM)法等。 Dijkstra 路径搜索算法[67] 于 1959 年由荷兰科 学家 Dijkstra 提出，用于扫描搜索从初始位置到 目标位置的最短路径。该算法简单易行，多用于 规模较小的网络。 栅格法[68-69] 于 1968 年由 W. E. Howden 首次 提出，并应用在路径规划中。为了便于计算机处 理，将连续空间离散化为网格单元，然后采用启 发式算法在网格单元中搜索最优路径。栅格化的 网格大小将直接影响算法的性能。在路径规划 中，蚁群算法、遗传算法[67] 和神经网络算法都会 对任务区域做栅格化处理。 模拟退火算法 (simulated annealing，SA) 受启 ·210· 智 能 系 统 学 报 第 15 卷
第2期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·211· 发于固体退火。它是基于Monte-Carlo迭代求解 4)智能优化算法。主要由群类优化算法和仿 策略的一种随机寻优方法，算法在搜索中加入随 生学算法组成。智能优化算法多以牺牲最优性换 机因素，使规划的结果跳出局部最优，然后，以一 取算法的计算速度。仿生学算法主要是通过模拟 定的概率迭代更新得到全局最优。 动物行为，规划路径的实现效果较佳。 Voronoi图法o是根据已知威胁的分布情况， 1.24多无人机路径规划数学表达式和问题建模 然后搜索图中的可行路段以构造最优路径。Voronoi 规划的路径可表示成空间位置点序列模 图法计算速度快，但规划中，未考虑威胁的类型 式，P:(x,y,,a,)表示无人机的初始位置状态， 和差别，而将其简单的处理为点目标，使得规划 P,(xy,二，a,β)表示无人机的终点位置状态，这里 的路径需要再进行优化处理。Voronoi图法多是 :=(,y)表示第i架无人机的初始点位置， 与其他算法结合使用。 表示第i架无人机的航偏角，B,是第i架无人机的 随机路标图(PRM)法，川于1992年由Over 航迹方位角，r(q)表示产生的路径，q为路径约束 mars首先提出，此方法是把需要规划的目标，随 参数，既可表示一条航程限制的直线路径长度， 机采样生成路标图，然后在生成的路标图中搜索 也可表示满足转弯角度限制路径的曲率，由上， 最优路径。PRM法规划路径的时间长度直接影 第j架无人机从起点p到终点P,的路径规划 响规划的路径质量，时间越长，路径质量越高。 r(q可用数学表达式(4)表示： 但是，该算法实时性较差。 A'算法2是一种启发式算法，在将规划空 PrP,)p.xy.-waE,）. 间中靠近初始点的节点用Dijkstra算法处理，靠 j=1,2,…,N (4) 上述环境约束、平台自身约束、任务约束等 近目标点的节点用BFS算法处理。A算法表示 均记为山m:(q),则路径规划数学表达式(4)可表 式(3)所示： 示为 f (n)=g(n)+h(n) (3) 式中：f(m)是当前节点n总的代价估计函数；g(n) P(nnaB)lg9p（pB, 是搜索空间中从起始点到当前节点n之间的距离 j=1,2,…,N (5) 代价函数值；h(m)是从当前节点n到目标节点的 三维空间中，规划路径的可飞性由曲率1和 启发式评估代价值。启发式函数h(m)是算法求 挠率τ共同决定。任务总约束条件记为山：(q), 解的核心。A算法虽然克服了盲目搜索，但是， 可以表示为 内存大、计算复杂，多用于静态环境中，图5为 k,2≤max A算法流程图。 片 r,T≤Tma (6) lafe,TmOTn=O,m≠n 开始 这里山ae表示无人机的安全性。 上述数学规划方法、人工势场法、基于图形 初始化open和close表 学的方法和智能优化算法在规划路径时，很多未 考虑运动学约束。由于无人机飞行是一个复杂过 将起点放入open表 程，受各种因素的影响。现假设无人机质量恒为 作为当前节点 常数、忽略地球的曲率且重力加速度不随飞行高 度的变化而变化。无人机动力学方程如下： open表是否空 dx(i) cosa(i)cosB(i) di N dy(i) 搜索周围所有可能的节 sina(i)cosB(i) 将代价最小的节点A从 di 点，将有效节点加人ope open表转移到close表 表，无效节点删除 d(i) =sinB(i) di (7) da(i) 点A是否为终点 =y1 di dB(i) di =y2 成功并结束 失败并退出 这里p:=(x(⑤，y(,z()是初始点位置，航偏角， 图5A算法流程图 B,是航迹方位角，a:和B,是控制输入变量，Bmn≤ Fig.5 The framework of A algorithm B(s)≤Bar。曲率半径为
发于固体退火。它是基于 Monte-Carlo 迭代求解 策略的一种随机寻优方法，算法在搜索中加入随 机因素，使规划的结果跳出局部最优，然后，以一 定的概率迭代更新得到全局最优。 Voronoi 图法[70] 是根据已知威胁的分布情况， 然后搜索图中的可行路段以构造最优路径。Voronoi 图法计算速度快，但规划中，未考虑威胁的类型 和差别，而将其简单的处理为点目标，使得规划 的路径需要再进行优化处理。Voronoi 图法多是 与其他算法结合使用。 随机路标图 (PRM) 法 [7,71] 于 1992 年由 Overmars 首先提出，此方法是把需要规划的目标，随 机采样生成路标图，然后在生成的路标图中搜索 最优路径。PRM 法规划路径的时间长度直接影 响规划的路径质量，时间越长，路径质量越高。 但是，该算法实时性较差。 A *算法[72-74] 是一种启发式算法，在将规划空 间中靠近初始点的节点用 Dijkstra 算法处理，靠 近目标点的节点用 BFS 算法处理。A *算法表示 式 (3) 所示： f (n) = g(n)+h(n) (3) f (n) n g(n) n h(n) n h(n) 式中： 是当前节点 总的代价估计函数； 是搜索空间中从起始点到当前节点 之间的距离 代价函数值； 是从当前节点 到目标节点的 启发式评估代价值。启发式函数 是算法求 解的核心。A *算法虽然克服了盲目搜索，但是， 内存大、计算复杂，多用于静态环境中，图 5 为 A *算法流程图。 开始 初始化open和close表 将起点放入open表 作为当前节点 open表是否空 将代价最小的节点A从 open表转移到close表 点A是否为终点 成功并结束 搜索周围所有可能的节 点，将有效节点加入open 表，无效节点删除 失败并退出 Y N N Y 图 5 A *算法流程图 Fig. 5 The framework of A algorithm 4) 智能优化算法。主要由群类优化算法和仿 生学算法组成。智能优化算法多以牺牲最优性换 取算法的计算速度。仿生学算法主要是通过模拟 动物行为，规划路径的实现效果较佳。 1.2.4 多无人机路径规划数学表达式和问题建模 Pi(x, y,z,α, β) Pt (x, y,z,α, β) pi = (xi , yi ,zi) i αi i βi i r(q) q j pi j pt j rj(q) 规划的路径可表示成空间位置点序列模 式 ， 表示无人机的初始位置状态， 表示无人机的终点位置状态，这里 表示第 架无人机的初始点位置， 表示第 架无人机的航偏角， 是第 架无人机的 航迹方位角， 表示产生的路径， 为路径约束 参数，既可表示一条航程限制的直线路径长度， 也可表示满足转弯角度限制路径的曲率，由上， 第 架无人机从起点 到终点 的路径规划 可用数学表达式 (4) 表示： pi j( xi j, yi j,zi j,αi j, βi j) ri(q) → pt j( xt j, yt j,zt j,αt j, βt j) , j = 1,2,··· ,N (4) ∏allri(q) 上述环境约束、平台自身约束、任务约束等 均记为 ，则路径规划数学表达式 (4) 可表 示为 pi j( xi j, yi j,zi j,αi j, βi j) ∏allri(q) → pt j( xt j, yt j,zt j,αt j, βt j) , j = 1,2,··· ,N (5) λ τ ∏allri(q) 三维空间中，规划路径的可飞性由曲率 和 挠率 共同决定。任务总约束条件记为 ， 可以表示为 ∏= ∏λ , λ ⩽ λmax ∏τ ,τ ⩽ τmax ∏sa f e,rm ∩rn = Ø,m , n (6) 这里 ∏safe 表示无人机的安全性。 上述数学规划方法、人工势场法、基于图形 学的方法和智能优化算法在规划路径时，很多未 考虑运动学约束。由于无人机飞行是一个复杂过 程，受各种因素的影响。现假设无人机质量恒为 常数、忽略地球的曲率且重力加速度不随飞行高 度的变化而变化。无人机动力学方程如下： dx (i) di = cosα(i) cosβ(i) dy (i) di = sinα(i) cosβ(i) dz(i) di = sinβ(i) dα(i) di = γ1 dβ(i) di = γ2 (7) pi = (x (i), y (i),z(i)) αi βi αi βi βmin ⩽ β(s) ⩽ βmax 这里 是初始点位置， 航偏角， 是航迹方位角， 和 是控制输入变量， 。曲率半径为 第 2 期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·211·
·212· 智能系统学报 第15卷 R(s)= (8) 长度，飞行时间受飞机的机动性能、障碍物、地 vi (s)cos2B(s)+(s) 形、环境威胁等因素影响，无人机规划路径的总 其中Ra≤R(S)≤Rmxxo 时间要小于规定的总时间。 最优控制问题可以转化为最短路径问题 min "ds,这里s,表示所规划路径的长度，即三维 多无人机路径规 划指标 空间的路径规划问题可转化为求解目标函数的最 优化问题。 规避威胁 飞行时间 路径距离 路径规划的 1.2.5路径规划的平滑处理 的能力 可靠性 路径平滑处理是无人机能否沿着所规划路径 安全、顺利飞行的保证。在空间约减的基础上， 与障碍物 被发现和击伤 碰撞风险 击毁的风险 受机动性能限制，上述算法规划的路径多是以直 线相连，会产生较多的拐点，为适应无人机的飞 图6路径规划的评价指标 行要求，需对规划路径优化处理。路径优化处理 Fig.6 Indicators on path planning 的目的是在规划的基础上，进一步验证路径的可 路径距离的长度是无人机从起始点到目标点 飞性。常见的优化路径的方法有曲线拟合、二次 的空间距离，规划的路径长度需满足小于允许的 B样条插值法、三次B样条插值法、RTS平滑和 最大长度。 圆弧拟合法，2，。B样条&-m最早由Isaac Jac- 规避威胁的能力指无人机避开各种障碍物， ob Schoenberg于1946年提出，其曲率变化均匀， 如山地、丘陵、房屋建筑等障碍物的能力。规避 曲线高阶导数连续，局部控制能力较强。n+1个 风险能力越强，规划路径可飞性就越高。 控制节点(oo2o),(M),…,(xya二)的n次B样 规划路径的可靠性是指在一定的时间、空间 条可以表示为 约束下，无人机在规划的路径上安全飞行的概率 1. 大小。 B1()= note i≤t<note i+l 0 其他 (9) 航迹评价的量化表达式可表示为 B(t)= (t-note_i)Bix-(t)(note_i+k-1)B:--1(1) J=arg maxw1+wJ2+03J3+wJ4 (12) note i+k-1-note_i note_i+k-note i+1 其中，w1+2+w+w=1,这里J表示评价函数， (10) 这里note_i=0,i<k,note_i=i-k+l,k≤i<n,note_i= 1、2、J3和J4分别表示飞行时间、路径距离、规 n-k+2,n<i。则坐标可以表示为 避威胁的能力和规划路径可靠性的无量纲值，山、 2、和w4分别是其对应的权重系数。针对特 r)=∑-Bu0 定问题，确定单项指标在综合指标中的权重系 数，最后，得到表征整体航迹性能优越的无量纲值。 P0=∑B0 (11) 现对评价指标做如下约定：所规划路径的飞 行时间越短，无人机燃耗能量越少，则规划的航 0-B 迹性能越优；在满足约束条件下，规划的路径越 =0 短，则无人机消耗的燃量越少，遇到威胁的概率 这里0≤t≤1，Bk()表示曲线的混合函数。 越低，则规划的航迹性能越优；规避威胁的能力 1.2.6多无人机路径规划的评价指标 越强，则规划的路径健壮性越高，重规划的成本 评估路径的优劣是任务规划系统整体效能评 就越低，航迹性能越优。规划路径的可靠性越 估的一个重要组成部分，规划的路径受规划模 高，遇到威胁时被损坏的概率就越低，航迹性能 型、所用算法影响，需要综合考虑各项因素，并对 越优。 各项评价指标进行量化处理，从而确定影响路径 在分析完成无人机路径规划步骤的基础上， 规划各指标的权重，便于计算综合约束指标，实 就路径规划的8个约束条件，给出数学规划方 现对规划路径的选优。现将多无人机路径规划的 法、人工势场法、基于图形学的方法和智能优化 评价指标列为飞行时间、路径距离、规避威胁的 算法4种规划方法的应用环境和优缺点，概述了 能力和规划路径的可靠性4种。图6是无人机路 路径规划的问题建模和平滑处理方法，最后，讨 径规划的评价指标结构图。 论分析了无人机路径规划的4个评价指标及其量 飞行时间指无人机从初始点到目标点的时间 化方法。表2是路径规划相应算法的对比结果
R(s)= 1 √ γ 2 1 (s) cos2β(s)+γ 2 2 (s) (8) 其中 Rmin ⩽ R(s) ⩽ Rmax。 min∫ st 0 ds st 最优控制问题可以转化为最短路径问题 ，这里 表示所规划路径的长度，即三维 空间的路径规划问题可转化为求解目标函数的最 优化问题。 1.2.5 路径规划的平滑处理 n+1 (x0,y0,z0),(x1,y1,z1),··· ,(xn,yn,zn) n 路径平滑处理是无人机能否沿着所规划路径 安全、顺利飞行的保证。在空间约减的基础上， 受机动性能限制，上述算法规划的路径多是以直 线相连，会产生较多的拐点，为适应无人机的飞 行要求，需对规划路径优化处理。路径优化处理 的目的是在规划的基础上，进一步验证路径的可 飞性。常见的优化路径的方法有曲线拟合、二次 B 样条插值法、三次 B 样条插值法、RTS 平滑和 圆弧拟合法[4,12,75]。B 样条[18,76-77] 最早由 Isaac Jacob Schoenberg 于 1946 年提出，其曲率变化均匀， 曲线高阶导数连续，局部控制能力较强。 个 控制节点 的 次 B 样 条可以表示为 Bi,1 (t) = { 1, note_i ⩽ t < note_i+1 0, 其他 (9) Bi,k (t) = ( t−note_i ) Bi,k−1 (t) note_i+k−1−note_i + ( note_i+k−t ) Bi−1,k−1 (t) note_i+k−note_i+1 (10) note_i=0 i<k note_i=i−k+1 k ⩽ i<n note_i= n−k+2 n<i 这 里 ， ， ， ， ， 。则坐标可以表示为 x (t) = ∑n i=0 xi · Bi,k (t) y (t) = ∑n i=0 yi · Bi,k (t) z(t) = ∑n i=0 zi · Bi,k (t) (11) 这里 0 ⩽ t ⩽ 1，Bi,k (t) 表示曲线的混合函数。 1.2.6 多无人机路径规划的评价指标 评估路径的优劣是任务规划系统整体效能评 估的一个重要组成部分，规划的路径受规划模 型、所用算法影响，需要综合考虑各项因素，并对 各项评价指标进行量化处理，从而确定影响路径 规划各指标的权重，便于计算综合约束指标，实 现对规划路径的选优。现将多无人机路径规划的 评价指标列为飞行时间、路径距离、规避威胁的 能力和规划路径的可靠性 4 种。图 6 是无人机路 径规划的评价指标结构图。 飞行时间指无人机从初始点到目标点的时间 长度，飞行时间受飞机的机动性能、障碍物、地 形、环境威胁等因素影响，无人机规划路径的总 时间要小于规定的总时间。 多无人机路径规 划指标 飞行时间 路径距离 规避威胁 的能力 路径规划的 可靠性 与障碍物 碰撞风险 被发现和击伤 击毁的风险 图 6 路径规划的评价指标 Fig. 6 Indicators on path planning 路径距离的长度是无人机从起始点到目标点 的空间距离，规划的路径长度需满足小于允许的 最大长度。 规避威胁的能力指无人机避开各种障碍物， 如山地、丘陵、房屋建筑等障碍物的能力。规避 风险能力越强，规划路径可飞性就越高。 规划路径的可靠性是指在一定的时间、空间 约束下，无人机在规划的路径上安全飞行的概率 大小。 航迹评价的量化表达式可表示为 J = argmaxω1 J1 +ω2 J2 +ω3 J3 +ω4 J4 (12) ω1 +ω2 +ω3 +ω4=1 J J1 J2 J3 J4 ω1 ω2 ω3 ω4 其中， ，这里 表示评价函数， 、 、 和 分别表示飞行时间、路径距离、规 避威胁的能力和规划路径可靠性的无量纲值， 、 、 和 分别是其对应的权重系数。针对特 定问题，确定单项指标在综合指标中的权重系 数，最后，得到表征整体航迹性能优越的无量纲值。 现对评价指标做如下约定：所规划路径的飞 行时间越短，无人机燃耗能量越少，则规划的航 迹性能越优；在满足约束条件下，规划的路径越 短，则无人机消耗的燃量越少，遇到威胁的概率 越低，则规划的航迹性能越优；规避威胁的能力 越强，则规划的路径健壮性越高，重规划的成本 就越低，航迹性能越优。规划路径的可靠性越 高，遇到威胁时被损坏的概率就越低，航迹性能 越优。 在分析完成无人机路径规划步骤的基础上， 就路径规划的 8 个约束条件，给出数学规划方 法、人工势场法、基于图形学的方法和智能优化 算法 4 种规划方法的应用环境和优缺点，概述了 路径规划的问题建模和平滑处理方法，最后，讨 论分析了无人机路径规划的 4 个评价指标及其量 化方法。表 2 是路径规划相应算法的对比结果。 ·212· 智 能 系 统 学 报 第 15 卷
第2期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·213· 表2路径规划算法对比 Table 2 Comparison of path planning algorithms 算法 对比分析 用于研究可分为多个决策阶段的组合优化问题。 动态规划法 数学规划 该方法精确度高、鲁棒性强、规划速度快：但是复杂度高。 方法 使用范围有一定的局限性。 非线性规划算法 该算法的精确性高，鲁棒性强：但是计算时间较长，规划速度较慢、复杂度高。 用于无人机的静态和动态路径规划。 人工势场法 该算法简单易实现、计算时间短，规划出的路径较平滑、实时性较好：但是易陷入局部最优 且障碍物附近目标不可达。 该算法属于典型的随机算法，计算时间越长，优化结果越好、可快速收敛到全局最优：但时空 模拟退火算法 复杂度较高。 该方法主要用于环境建模，栅格的大小，将直接影响规划能力和规划精度。 栅格法 该方法简单易实现、精确度较高、但是计算复杂度大。 该算法是用于全局路径规划最好的算法之一。 基于图形学的 A'算法 A算法结构直观、易实现、搜索效率高、收敛性强，并且在静态环境下一定能找到最优路径： 方法 当问题规模较大时，时空复杂度很高，该算法只能生成一条路径。 用于解决无人机航迹规划。 Voronoil图法 该方法规划出的路径安全性高，威胁代价和计算量低，计算效率高；但是实时性较差。 该方法用于完全随机的采样策略中。 随机路标图 该方法精确度较高、规划速度快：但是鲁棒性差、其路径规划的计算量及实时性受空间采样 (PRM)法 点影响大。 主要用于解决工程问题，可定性分析，但不能定量证明。 群类优化算法 该算法自组织性强、鲁棒性强、可扩展性强；但是计算量大、收敛速度慢、收敛精度低、易出 智能优化算法 现早熟、空间复杂度高。 该算法简单易实现，时空复杂度低、自适应性和自学习性能力较强、鲁棒性强：但是搜索过程 仿生学算法 中具有很多不确定性、使用范围有限，延展性（性能与规模矛盾）低。 2开放性问题和未来发展方向 的有效性和求解的复杂性是当下无人机任务规划 急需解决的问题。 2.1 目前存在的问题 2)多无人机任务分配模型中，应恰当约束载 相较于单架无人机任务规划而言，多无人机 荷分配，以减少执行任务的无人机与目标之间的 执行任务规划问题面临更多的困难。主要困难有 不适组合问题；多无人机任务分配问题相较于单 多无人机协同目标分配模型的统一、协同约束条 无人机任务分配问题，约束条件更多，计算更加 件的选取和计算、多无人机间协同路径规划与平 复杂。在任务分配阶段，既要考虑单架无人机的 滑处理，及遇到突发威胁时多无人机路径重规划 自主性，也需要考虑该无人机与其同时执行任务 问题。国内外对无人机任务规划问题已经有了大 的其他无人机间的协调配合问题；在编队飞行 量的研究，但是依旧存在以下问题需要解决： 中，提高各无人机间的信息融合，将有助于增加 1)建模方面，由于各无人机的飞行性能、飞 任务分配的鲁棒性和精确性；现有任务分配模型 行距离、飞行速度、执行任务的自身性能和目标 多假设目标状态和位置已知，然而，实际作战环 的类型和属性不同，导致多无人机在执行任务阶 境的高动态性、复杂性和不确定性，使得无人机 段执行效果差，飞行航线交叉等问题；另外，现有 任务分配容错性低、自适应性差。故有效地动态 的无人机任务规划方法、算法不统一，导致任务 任务分配算法，将提高无人机应对动态环境的自 分配和路径规划存在效率低下、重规划等问题， 适应和自组织能力。 并且现有文献多是将无人机任务规划抽象为过于 3)路径规划在燃耗量、转向角、无人机飞行 理想、便于求解的某种现有模型，所以，实现建模 高度、无人机飞行时间等单机约束和时空约束条
表 2 路径规划算法对比 Table 2 Comparison of path planning algorithms 算法 对比分析 数学规划 方法 动态规划法 用于研究可分为多个决策阶段的组合优化问题。 该方法精确度高、鲁棒性强、规划速度快；但是复杂度高。 非线性规划算法 使用范围有一定的局限性。 该算法的精确性高，鲁棒性强；但是计算时间较长，规划速度较慢、复杂度高。 人工势场法 用于无人机的静态和动态路径规划。 该算法简单易实现、计算时间短，规划出的路径较平滑、实时性较好；但是易陷入局部最优， 且障碍物附近目标不可达。 基于图形学的 方法 模拟退火算法 该算法属于典型的随机算法，计算时间越长，优化结果越好、可快速收敛到全局最优；但时空 复杂度较高。 栅格法 该方法主要用于环境建模，栅格的大小，将直接影响规划能力和规划精度。 该方法简单易实现、精确度较高、但是计算复杂度大。 A *算法 该算法是用于全局路径规划最好的算法之一。 A *算法结构直观、易实现、搜索效率高、收敛性强，并且在静态环境下一定能找到最优路径； 当问题规模较大时，时空复杂度很高，该算法只能生成一条路径。 Voronoi图法 用于解决无人机航迹规划。 该方法规划出的路径安全性高，威胁代价和计算量低，计算效率高；但是实时性较差。 随机路标图 (PRM)法 该方法用于完全随机的采样策略中。 该方法精确度较高、规划速度快；但是鲁棒性差、其路径规划的计算量及实时性受空间采样 点影响大。 智能优化算法 群类优化算法 主要用于解决工程问题，可定性分析，但不能定量证明。 该算法自组织性强、鲁棒性强、可扩展性强；但是计算量大、收敛速度慢、收敛精度低、易出 现早熟、空间复杂度高。 仿生学算法 该算法简单易实现，时空复杂度低、自适应性和自学习性能力较强、鲁棒性强；但是搜索过程 中具有很多不确定性、使用范围有限，延展性(性能与规模矛盾)低。 2 开放性问题和未来发展方向 2.1 目前存在的问题 相较于单架无人机任务规划而言，多无人机 执行任务规划问题面临更多的困难。主要困难有 多无人机协同目标分配模型的统一、协同约束条 件的选取和计算、多无人机间协同路径规划与平 滑处理，及遇到突发威胁时多无人机路径重规划 问题。国内外对无人机任务规划问题已经有了大 量的研究，但是依旧存在以下问题需要解决： 1) 建模方面，由于各无人机的飞行性能、飞 行距离、飞行速度、执行任务的自身性能和目标 的类型和属性不同，导致多无人机在执行任务阶 段执行效果差，飞行航线交叉等问题；另外，现有 的无人机任务规划方法、算法不统一，导致任务 分配和路径规划存在效率低下、重规划等问题， 并且现有文献多是将无人机任务规划抽象为过于 理想、便于求解的某种现有模型，所以，实现建模 的有效性和求解的复杂性是当下无人机任务规划 急需解决的问题。 2) 多无人机任务分配模型中，应恰当约束载 荷分配，以减少执行任务的无人机与目标之间的 不适组合问题；多无人机任务分配问题相较于单 无人机任务分配问题，约束条件更多，计算更加 复杂。在任务分配阶段，既要考虑单架无人机的 自主性，也需要考虑该无人机与其同时执行任务 的其他无人机间的协调配合问题；在编队飞行 中，提高各无人机间的信息融合，将有助于增加 任务分配的鲁棒性和精确性；现有任务分配模型 多假设目标状态和位置已知，然而，实际作战环 境的高动态性、复杂性和不确定性，使得无人机 任务分配容错性低、自适应性差。故有效地动态 任务分配算法，将提高无人机应对动态环境的自 适应和自组织能力。 3) 路径规划在燃耗量、转向角、无人机飞行 高度、无人机飞行时间等单机约束和时空约束条 第 2 期 齐小刚，等：多约束下多无人机的任务规划研究综述 ·213·