三维多无人机系统协同任务规划关键问题综述

赵明　李涛　苏小红　赵玲玲　张彦航

摘 要：随着无人机技术的迅猛发展，人们对无人机技术的需求越来越广泛，已从单机简单任务向多机协同执行多个复杂任务、且自主协调、无人干预、群体合作的方向发展。而多无人机系统的协同任务规划技术，是无人机自主导航飞行和无人机之间自主协调配合共同完成任务的关键。这一任务规划决定了无人机各类资源的协调和执行目标的合理分配，无人机协调可飞飞行航迹的规划，以及在飞行过程中，取代人为干预，实时协调化解多机飞行时可能产生的各种冲突和问题。因此，对多无人机系统协同任务规划的关键问题，如目标分配、航迹规划、在线重规划等深入研究，是提高多机系统执行任务能力的重要环节。近年来，该领域的研究日益广泛，但还存在诸多问题需要解决，尤其迫切需要研究在三维战场环境下的多机协同任务规划方法。

关键词：多无人机系统；任务规划；三维战场；多机协同

中图分类号：TP391 文献标识码：A 文章编号：2095-2163（2015）06-

Abstract： With the rapid development of UAV technology， peoples demand for the UAV is becoming more and more extensive. The trend of UAV research has been developed from a single UAV and simple task to the multiple UAVs performing complex tasks with autonomous coordination， no intervention， and group cooperation. The cooperative task planning of multi-UAV system is not only the key to the autonomous navigation of UAVs， but also the focus on coordination and cooperation with the UAVs to complete tasks. It determines the optimal tasks of UAV and the reasonable allocation of resources， the path planning of UAVs cooperative flight， and replacing human intervention to resolve various conflicts and problems in real time. So， the key issues of cooperative task planning for UAVs， such as target assignment， path planning， and on-line re-planning， are all important parts of improving the ability of UAVs system. In spite of the wide range of research in this field recently， there are still many problems need to be solved. In particular， it is urgent to research on multi-UAVs cooperative task planning methods in three dimensional battlefield environments.

Keywords： Multi-UAVs System； Task Planning； target assignment； Path Planning； Re-planning.

0引 言

与有飞行员驾驶的载人飞行器相比，无人机（Unmanned Aerial Vehicle， UAV）具有众多明显以及潜在的特点优势，如自主飞行的无人机在燃油充足的情况下不需要休息，可以组织更长时间的空中巡航。无人机不需要提供飞行员必须的生命支持系统，这不仅减少了飞行成本，还为部署传感器和其他设备提供了更多空间[1]。此外，无人机不必考虑机载人员的生理限制，因此可以支持超越极限的更灵活的自由度完成各种复杂飞行任务，并可探索人类无法接近的危险区域[2]。现代战争中，无人机的广泛使用，极大程度上降低了人员伤亡的代价，提高了作战系统平台的安全性和自适应性。因此“无人化”势将逐渐改变现代战争的面貌，成为未来信息化战争的新方向。在民用和科研领域，无人机的作用也日益凸显，成为辅助人类探索自然、增进社会安全、参与救灾抢险等重大任务必不可少的技术支撑[3]。

近年来随着无人技术的广泛推广，无人系统在各领域获得普遍关注，除了无人飞行器系统（Unmanned Aircraft System， UAS）被概念化以外，无人地面系统（Unmanned Ground System， UGS）和无人海洋系统（Unmanned Maritime System， UMS）也相继成为瞩目热点。可以预期的是，无人技术发展的未来趋势，必然是陆地、天空、海洋以及外太空多种无人系统一体化的综合应用[2]。无人系统技术的全面推广，将以更为纵深立体的方式影响未来高新科技格局。图1显示了UAS预期的自主级别发展规划[4]，从其中可以看出，分布式控制、群协同和在线重规划等自主需求都作为预期的目标要加以研究实现，而完全群体自主的UAVs系统则是未来发展的最终目标。

在空间立体化复杂战场态势下，参与作战的飞行器种类不断增加，性能迅速提高，形成了技术密集、结构复杂的特征。因此单架无人机有限的飞行能力和载弹负荷将很难独自完成复杂战场态势中的信息收集、区域监视、多目标攻击等显示高端任务。而多无人机协同作战则可以处理各种复杂的问题，提高任务完成的效率和成功率，具有比单机更灵活、执行任务时间更短、信息传递更迅速等优点。同时，多无人机系统中部分无人机的毁伤和失效也不致影响完成任务的最终效果[5]。因此多机系统已经逐渐取代单机，成为执行各种复杂任务的开放目标指向中的重点关键技术。

但是，多机协同作战增加了问题求解的规模，问题的复杂程度随无人机和任务数量的增加呈几何级数增长。在协同过程中，不但要处理无人机自身的约束条件，更要考虑相互协同的约束；此外，还要避免多机间冲突导致的系统退化、共享资源竞争等关键问题的影响。在控制方面，传统的基于中央控制的方法越来越难行，尤其是多架次无人机协同作战，需要更多的通信带宽、更完备的信息共享和更高的自主决策能力支持；多无人机系统面临着复杂的挑战。因此，近年来多无人机协同任务规划系统成为无人机研究领域的新热点，赢得了来自多方的重视和关注。

多无人机协同任务规划系统从功能和实施阶段上，可以分为协同目标分配、协同航迹规划和协同任务执行三个部分。其中多机协同目标分配 （Multi-UAVs Cooperative Multi-Targets Assignment， MUCMTA）是基于一定的环境知识和任务需求，为多机系统中的每架UAV分配一个或一组有序目标，以便在完成最大可能数量任务的同时保证执行目标总代价最小和总效益最大的问题，该问题是一个多模型、多约束、计算难度大、复杂度呈几何级数增长的最优化NP难题；多机协同航迹规划（Multi-UAVs Cooperative Path Planning）是在给定已知、部分已知或未知信息的环境中，规划出从起始点到达目标点，可以绕过威胁区和障碍物、安全可靠无碰撞，且同时满足各种约束条件和协同关系的多条可行飞行航迹，该问题是一个多目标优化问题；在任务执行阶段，环境的动态改变可能导致全局规划结果的部分失效，因此需要对环境的改变做出响应，对失效的航迹段进行在线协同重规划（Online Cooperative Path Planning），以保证任务执行过程中UAVs飞行的安全可靠、且高效。

1国内外研究现状及分析

1.1无人机和无人机任务规划系统概况

近年来，无人机的研究和应用在多数发达国家呈几何级数急增，这些国家投入了大量的人力和财力组织研发，涌现出一批性能优良的新型无人机系统[6]，如Global Hawk、WASP 3、Raven、Scan Eagle、MQ-18、RQ-4 Blk、X47-B 和 RQ-170、以及我国自主产权的“翼龙（GJ-1）”，“海鹰（WJ-600）”等。随着无人机性能不断深入发展，针对无人机系统性的研究也日趋普遍具体。近年来，国际民用航空组织（ICAO）、美国联邦航空管理局（FAA）、美国国防部（DoD）、欧洲航空安全局（EASA）一致通过如下决议：采用Unmanned Aircraft System（UAS）取代即将过时的术语“UAV”[2]，将系统性的研究提到了新的高度。

针对UAS概念的提出和发展，在任务需求复杂度不断提高的情况下，多机协同任务规划系统的研究也日益广泛，并逐渐成为未来无人机应用的主要研究方向。例如，美国国防部建立了无人机联合开发局（JPO），致力于从大尺度多机系统转型为研发小型、低空、低成本、一次性的多无人机群系统。2013年，美国国防部在无人系统未来25年发展规划中，提出联合地面、空中和海上的多种无人机协同工作将成为未来无人机发展的挑战[2]。此外，欧盟很早就进行了异构多无人机实时协同和控制（COMETS）项目的研究。近年来，多机系统不断向着群体人工智能和分布式网络控制技术方向发展，例如，欧盟联合开发的Neuron作战无人机单元阵列项目、美国海军研究所的LOCUST项目（低代价无人机群集）都是利用群智能的典范。

我国无人机领域的研究起步比较晚，90年代以来，西北工业大学、北京航天航空大学和南京航天航空大学、清华大学、华中理工大学、哈尔滨工业大学等高校率先成立了无人机和无人机任务规划系统的专门研究机构，并已研发出几十个型号的无人机和多种无人机仿真平台。2000年以来，中航工业集团、航天科工集团、航天科技集团下属的一些院所也开始了军事或民用无人机的研制，虽然这些研发距离大批量生成和产业化发展还有一定的距离，但国内无人机市场化趋势已成为现实必然[7]。与此同时，与无人机体系紧密配套的无人机任务规划系统的研究，也已从初期研究的单平台航迹规划问题发展到包括异构多平台、多任务的规划问题。目前主要有国防科技大学多UAV任务协调技术的研究[8]，北京航空航天大学基于DTC的无人机任务规划研究[9]，华中科技大学的协同航迹规划研究[10]等，均获得了丰硕的研究成果。此外，尤其值得一提的是，2015年纪念抗战70周年阅兵式上，我国首次以无人机受阅方队的形式，向全世界展示了最新型的侦察打击一体无人机，从而说明我国无人机在军事领域已经进入了崭新的高度和飞速发展时期。

多无人机系统任务规划由协同目标分配、航迹规划和任务执行三个部分组成。下面详细介绍相关方面常用的技术手段和研究方法。

1.2多机协同的目标分配方法

解决多机协同目标分配问题，常采用集中式或分布式目标分配系统。具体地，集中式系统可以统一控制，但是扩展性较差；分布式系统计算灵活，但是对通信要求较高。目前常用的方法有：数学规划法、协商法和智能算法等。针对这几类常用方法，给出如下的论述与分析。

2.2.1 基于数学规划法的协同目标分配

数学规划（Mathematical Programming）法是集中式解决分配问题的经典方法，如匈牙利算法[11]在处理分配问题时具有较好的效果，但该方法要求已知所有信息、其容错能力也较差，针对模型不一致的多机多目标分配的普适性则欠佳；此外，目标分配问题是一个典型的整数规划问题，可利用整数规划的方法进行求解。Jonathan P.How等人基于混合整数线性规划（MILP）研究实现的协同任务分配[12]。此类方法简单灵活，求解速度较快，但是对复杂问题的抽象过于简单，环境表示不清晰，仅适合简单环境的问题求解；动态规划（Dynamic Programming）也是求解协同目标分配问题常用的一种数学规划方法[13]，该方法把多过程转化为一系列单阶段问题，虽然结构简单，但却过度简化了无人机之间的关系，从而降低了结果的可信度。

1.2.2 基于协商法的协同目标分配

分布式目标分配系统计算灵活，可以将协同和分配问题分布到各个节点上进行高速处理，适合解决大规模的目标分配问题。目前最常见的是基于合同网的协商方法，合同网将目标分配看作一个市场交易过程，通过“招标-投标-中标”的拍卖机制，实现任务的委派迁移[14]。UAV将执行任务过程中自己无法处理的任务对外拍卖，由其他UAV进行投标，系统通过协商将任务迁移给能够以最低代价执行的UAV。基于合同网的方法原理简单、易于实现，效率较高。但是对协同和约束的处理能力较差，在追求整体最优的目标下，通常会与个体利益冲突。尤其忽略了三维真实环境的动态特征，致使其实现效果受到影响。

1.2.3基于智能算法的协同目标分配

利用人工智能的方法处理目标分配问题，具有灵活、自适应、启发性、易于实现和计算复杂度低等优点，灵活的编码结构尤其适合三维问题的建模和求解。常见的方法有：进化规划、粒子群算法和蚁群算法等。

多目标遗传规划方法将原有的单目标优化进行了扩展，通过在协同目标分配中对多个相互冲突的目标实施优化，向适应度最优的个体方向实行搜索，可以有效收敛到最优的目标分配结果[15]。但是遗传规划存在迭代周期长、容易陷入局部最优解的不足，因此陆续出现了更多改进方法，如采用差分进化算法[16]、免疫进化算法[17]等。

粒子群算法是一种并行群进化技术，粒子在演化学习过程中，不但受整体社会精英的影响，还将受到其近邻关系的影响，因此粒子飞行的方向是社会和个体经验的集合，该算法反映了群体智能决策特有的简单和高效性[18]。与进化算法相比，粒子群算法摒弃了交叉和变异操作，具有比遗传算法更好的效率。但该算法的精细搜索能力不强，尤其是处理离散问题时易陷入局部最优，全局搜索能力差。

蚁群算法是一种利用隐式通信而获得信息共享，在未知环境中搜索目标和解的智能自组织方法。该方法通过传递信息素共享环境信息，引导搜索向信息密度高的方向递次进化[19]。该算法通过无智能或简单智能的聚集协同表现出全局智能行为特性，具有计算简单、鲁棒性好的优点。但是蚁群系统收敛速度很慢，易于出现停滞现象。

1.3多机协同的航迹规划方法

多机协同航迹规划是多机任务规划系统中的另一主要问题。已有研究方法有：从单机航迹规划方法发展来的多机规划方法；适合群体计算的群智能算法；以及基于路径优化的规划方法等。在此，对各类研究方法可分别作如下具体详述。

1.3.1 从单航迹规划发展来的多航迹规划

启发式A*算法是一种静态路网中求解最短路径卓具成效的启发式方法。A*算法和稀疏A*（SAS）算法[20]用来解决二维和三维环境下的单航迹规划问题，可以很好地处理各种复杂的约束条件。A*算法存在的问题是：对环境信息的依赖程度高，计算量大，并行能力差，因此不适合大规模三维多机协同航迹规划。

常用的概率图算法包括通视图法、轮廓图法、随机路线图法和Voronoi图法等[10]。其中的Voronoi图是由一组连接两邻点直线的垂直平分线组成的连续多边形网格图，可将环境中的威胁源和障碍物作为Voronoi图的特征元素，并通过对空间进行分解，就可以表示空间中距离威胁最远的通路。Voronoi图具有数量级低、构造时间快、距离威胁和障碍最远，因而航路最安全等优点[21]。但是由于三维空间没有确定的特征元素选择方法，因此很难构建其三维空间的相应表示，且最短路径也不一定就存在于其中。

人工势场是一种仿效作用力形成空间力场的规划方法，具体是将物体的运动看成是排斥力和吸引力相互作用下的结果，其中吸引力不断将运动物体拉向目标点，而排斥力则努力使运动物体远离威胁和障碍。算法原理是通过计算势函数对运动物体进行导航，其规划结果是沿势函数下降最快的方向搜索而得的航迹[22]。人工势场法的优点是规划速度快、躲避障碍和威胁的能力强等。缺点是存在静止点。

1.3.2 基于群智能的多航迹协同规划

与任务分配阶段相似，群智能算法也同样适合求解多机协同规划问题。这种算法具有规划速度快、并行性好、易于协同、可以收敛到全局最优等优点。其缺点则在于没有明确的基因表示定义、求得的最优解不唯一，且存在冲突和违背约束等问题。

当前，大量的航迹规划研究都围绕着改进的进化算法来实现展开，如平行进化算法[23]、量子遗传算法[24]等，这些方法证明了利用物种进化机制和并行寻优方法，可以较快搜索到解空间的最优位置。此外，人们更进一步地认识到，进化算法还特别适合处理三维空间中的规划问题，因此，该方法在实际航迹规划问题的求解上将有着独特优势。Roberge等则引领性地将平行进化算法与粒子群算法进行了比较[25]，强调了两者的区别和各自的优点，并将其混合方法应用于实际的航迹协同规划。此外，还有利用免疫应答、神经元网络[26]等多种智能航迹规划的方法。由此可见，基于群体智能和仿生学的航迹协同规划算法，必将在无人机发展的历程中收获更多优质丰富的科研成果。

1.3.3 基于路径优化的多机协同航迹规划

无人机特殊的飞行机动特性，要求规划时必须考虑结果的可飞性，因此规划时还需要对航迹段进行平滑，以获得一条平滑可飞的飞行航线。常用的曲线平滑方法有二次样条曲线、B样条曲线、Bezier曲线等。Jung D采用B样条控制点作为遗传基因，通过遗传算法优化B样条曲线，规划平滑可飞的飞行航迹[27]。该方法的缺点是分离了无人机性能和规划之间的具体联系。Antonlos则指出将规划和平滑分开的不合理性，并提出直接利用曲线对UAV的航迹进行规划的方法，基于无人机飞行最大转角条件下，利用Dubins曲线进行多机协同的航迹规划[28]。该方法的缺点是规划的曲线不是最优航迹，且多航迹协同规划时，优化规则也过于简单。