多无人机协同任务规划研究

杨晨 张少卿 孟光磊

无人机作战相比于有人机具有:体积小、重量轻、续航时间长、载荷能力强、生存能力强、费用低廉、自主控制能力强、无人员伤亡、可在高风险空域飞行等优势,且在第四次中东战争、海湾战争、科索沃战争中和后来的伊拉克战争中无人机完成了中低空侦察、长时间战场监视、电子对抗、战况评估、目标定位和收集气象资料等任务[1−2].由于军事战场收益是面向全局,单架无人机所能发挥的作用效能十分有限,由此提出多机协同作战,同时完成不同任务,压制敌军,赢得战斗.

2016年,美国针对无人机不同功能、尺寸及作战需求,研究与无人机相关的各种协同作战方式,在以“忠诚僚机”为代表的有/无人协同和小精灵项目为代表的集群协同作战方面进行了大量探索[3].2018∼2022年,美国计划继续致力于研究无人机作为“忠诚的僚机”的有/无人机混编协同作战系统的研究,且计划将无人机编队分配给前线F-35、F-22和最新轰炸机“B-21”[4].可见,无人机集群协同作战必将是无人机未来发展的必然趋势.文献[5]分析了现阶段智能无人机集群发展的四大关键技术:环境感知与认识、多机协同任务规划、信息交互与自主控制、人机智能融合与自适应学习技术.在集群技术中,多机协同任务规划技术尤为重要,既要使机群的安全指数最大化,同时要求在最短的时间内完成情报、监视、侦察以及多目标攻击等任务.合理、高效的协同任务规划方案能极大提高任务执行成功率和效率、降低风险和成本是任务执行的基础[6].

目前,各国研究者们对多无人机协同任务规划技术还在大力研究中,部分问题已得到有效的解决方法.如解决多目标优化问题的传统数学规划法、基于市场机制的方法、基于图论的方法、和现代智能优化算法如蚁群算法、遗传算法、禁忌搜索算法等;但现阶段多数算法在时间上、全局最优上、在大规模复杂的优化组合问题上,仍未达到令人满意的效果.以及飞行过程中威胁源突现,单机需具备在线航迹重规划的自治能力或在线多机航迹重规划的协调能力依旧是我们的难点问题.

1 多无人机任务规划系统

1.1 任务规划的内容、目的及原则

1.1.1 内容与目的

对多无人机协同任务规划的研究是基于对单无人机的发展而来,所以依旧具备单无人机任务的规划特性:1)明确任务,包括任务类型、任务区域、完成时间等;2)战场状态分析,包括环境威胁、目标威胁、效能评估、态势预测;3)任务规划;根据既定任务设定约束条件并结合评估数据,计算无人机团队以最小的代价完成最大收益的分配方案和飞行路线.此外,多无人机本质上不同于单机在于具有协同、协调能力[7],规划时需考虑时间上的“协同”、空间上的“协调”,为无人机团队建立“互帮互助”的关系,所以规划上的复杂度和计算量都大大增加[8−9].

1.1.2 规划原则

1)基本原则

多机任务规划的原则不仅要考虑各单机的物理性能和任务需求,还需考虑机群间协同关系和协调关系.从功能上任务规划由任务分配和航迹规划两部分组成,在任务分配方面需具备以下3个基本原则[10−12]:委派与无人机性能相适合的目标;多无人机共同执行任务时,在时间上协调;不同任务要求下,规划全局最优的多目标分配方案.航迹规划也具备3个基本原则[11−14]:避开航路威胁,气象威胁、地形威胁、编队碰撞、威胁源(雷达探测威胁、电磁干扰威胁、防空火炮威胁等);满足飞行约束条件,最小航迹段长度、最大爬升/俯冲角、最大转弯角、最大航迹长度、最低飞行高度等自身特性;飞行路径最优化,路径最优化的选择不但是选择出飞行的路径最短,更得满足所规划出的航路必须能够经过侦查区域或打击目标所在区域,且尽可能以较低概率被敌方雷达发现,最好结果是不被发现,这对规划航路的质量有较高的要求.

2)优先级

多无人机任务规划过程中会出现多任务多目标情况,军事指挥员基于不同环境、不同作战方式下达不同的作战要求,这不仅需要任务规划的结果是飞行的航路无威胁、满足飞机性能约束以及飞行路径最优等各类基本条件,还需任务规划系统能够以任务的优先级进行选取达到上层下达的作战要求[12,15−16].由此任务规划应具备这4种原则:

①优先选择价值高的目标;

②优先选择距离近的目标;

③优先执行任务时间最短;

④选取无人机数量最少;

这4种任务规划原则的优先级不等.在空对空、空对地等许多情况下,目标价值常常是作为任务规划的关键参考因素,建立选取价值高的目标为最高优先级的原则,保证了无人机的安全且得到的收益最大.但在完成一些特殊任务时,目标价值对规划要求来说优先级并不是最高的(指不是最重要的)如在完成侦察、监视、探测类任务时,由于无人机数量越多越容易暴露,针对这一类任务应当考虑用最少数量的无人机协同完成最多、最复杂的任务,由此选取最少无人机数量原则的优先级最高.

1.2 任务规划系统的功能模块

最早的无人机任务规划系统[15],是由控制站完成任务规划,再将任务命令下达给无人机,无人机只需完成对航迹的规划,如:文献[17]基于侦察机接受侦察战场状况的任务命令,建立了单无人机任务规划系统,系统只生成具体的飞行轨迹引导飞机到达预定目标完成任务,却没考虑在载荷等条件满足的情况下,单机任务规划系统需建立对目标的时序排列;文献[18]单机任务规划系统中建立比较全面、基本的系统模块包括任务分配、航迹规划、控制模块、数据管理模块等,但系统的组成还是过于简单;文献[19]的规划系统中除具有任务分配模块外,添加了系统保障模块,当航路战术决策装订好后发送到指挥系统内,在指挥系统接收到的航路战术决策的同时航路战术决策上传到保障系统,确保无人机出现意外指挥系统失控时,保障系统作为指挥系统继续完成任务,且保障系统还存入其他重要信息如:无人机所经过地形地貌的地图信息.单机任务规划系统是不能满足多机协同、协调的能力.基于协同能力的要求,多无人机任务规划系统需具备[15]:协同通信系统、协同控制系统以及协同任务调配系统等,使各无人机可以相互配合,减少威胁,一起行动,提高效率.文献[20−21]提出将系统从功能上进行层次结构的划分:决策层和执行层;决策层由多机任务分配、多机航迹规划、信息协调组成,执行层则是单机路径规划,由此完成了从多机到单机、从任务分配到航迹规划整个多无人机的任务规划.多无人机协同对控制技术、系统设置以及通信技术等都有很高的要求,研究者们就提出有人机控制无人机的方式完成协同作战;文献[22]在有/无人机协同作战下,提出采用语音控制法,完成协同控制下包括人机交互接口、链路通信接口、任务管理和调度以及实时路径决策和航路规划模块的任务规划系统;文献[23]在文献[19]的基础上设置了评估模块、目标分析模块,同时还将航迹规划分为了预规划和航路规划,实现了在飞行过程中对目标实时分析、判定威胁,无人机自主进行在线航迹规划,并具有评估能力,遇危自治,基本完成多无人机下的单机任务规划系统[23](图1(a));文献[24]基于对多UAV协同侦察任务决策问题继续深入,采用从局部到总体的研究思路建立如图1(b)的多无人机任务规划系统[24].

由此分析,多无人机任务规划系统需具备以下基本模块,其组成的基本架构如图2所示.

1)检测管理模块:跟踪各模块实时状态、调度各模块信息、控制各模块发生冲突;

2)态势/威胁评估模块:感知环境、目标等态势信息,建立综合评估指标体系图;

3)任务分配模块:根据任务要求,确定任务目的,完成任务(目标)分配.但由于不同机型的任务分配系统需要完成的规划不一样,侦察机就只需根据任务要求,完成支配各个传感器对目标、环境等信息的搜集;对于“侦察–打击”为一体的无人机,不但需要完成侦察任务还需要对目标评估,将目标进行合理安排保证目标收益最大化,最后完成目标打击.

4)航迹规划模块:根据目标位置,确定起飞点、作战点、作战区域,完成从起飞点到作战点的路线规划,选取最优路线,并做平滑处理满足飞机性能约束;

5)方案效能评估模块:对规划方案进行收益和代价评估,供决策者参考;

6)协调模块:解除预规划路径与新障物、与各UAVS的冲突;

7)内部数据管理模块:无人机的知识库、数据库,接收、存储、发送有关任务规划的所有信息与数据,更新任务规划的中间结果,接受任务规划的最终结果.

1.3 任务规划系统的控制方式

1.3.1 集中式控制系统

集中式控制系统[20,25−27](图3(a))由一个中央处理器控制全局,可以是由长机或者地面控制中心,这样的好处在于使全局收益最高.但是,计算量大、计算时间长且对服务器性能要求也高,更重要的是无人机在突发状况下不具备自治能力,就大大降低了无人机的安全系数.

1.3.2 完全分布式控制系统

完全分布式控制系统[17,23,25−26,28](图3(b))与集中式完全相反,各无人机地位平等,以相互协商、相互协调的方式完成任务分配.每架无人机从自身利益出发,容易陷入局部最优,且当无人机对任务都同时具有相同收益时,便无法抉择,相互之间产生竞争.

1.3.3 部分分布式控制系统

部分分布式控制系统即集散式控制系统[17,28−31](图3(c)),也称分层次式.结合集中式和分布式的优缺点,由长机或者地面控制站将任务分解成小任务包,分配给无人机,无人机对小包任务进行规划并相互协调,规划完成后将自己的收益、损失等数据反馈给长机或者地面控制站,从全局收益出发对各机下达任务命令.集散式控制方式既消除了集中式计算量大的问题,又大大提高了作战效率,满足全局利益最大化且无人机还具备自治能力.

1.3.4 基于多智能体分布式控制系统

多智能体系统(Multi-agent system,MAS)是指由不同的单个智能体(Agent)为完成某一特定任务组合而成的多智能体系统[32−33].在多无人机任务规划系统由规划Agent,分配Agent和协调Agent等组成(图3(d)).

由于Agent不但具有能迅速对环境进行认识、学习的能力,对问题进行判断、推理、求解的能力,且还具备很好的协调能力、协作能力,解决与其他Agent的矛盾和冲突,规划自身行为,并做出最终决策.而多Agent除了具有单Agent的自主性、交互性、主动性、社会性等基本特性外,由于其动态复杂,还具有以下特点:群体性,多Agent系统是由多个Agent为了实现各自的或群体的整体目标,通过扮演群体中的角色,并以角色关系相互连接而构成的.一个Agent可以承担多个角色,也可能由多个Agent组成的组来共同承担某一个角色;协作与协调,具有不同目标的各个Agent必须相互工作、协作、协商来完成问题的求解,从而实现整体任务.

通过MAS技术对多无人机任务规划系统的控制功能进行子功能划分,实现了智能体间、系统模块间共同参与、相互协商的作用,包括:集中式、分布式、分散式和混合式的多Agent系统架构.但目前国际上研究的热点问题主要在基于MAS技术的分布式控制系统,不同的是完全分布式任务规划系统[17,32,34]是将各智能体之间的交互关系平级化,而基于分层的部分分布式任务规划系统[33,35]是以集中式控制区和分布式控制区建立集散式控制方式明确各智能体之间的交互关系.

1.4 任务规划的基本流程

图4为多无人机任务规划的基本流程,由此流程图我们将任务规划过程分为离线预规划和在线实时规划.为了更好地展现出任务规划的流程,图4中将态势与威胁评估、航迹规划的工作过程分步分开表示.

1.4.1 离线预规划

离线预规划:起飞前,根据任务指令在完成态势评估系统同时完成:任务分析,建立任务优先级和对已知信息的态势分析与态势估计,建立目标的威胁评估并结合我机情况完成目标代价收益评估.然后,根据各类评估数据基于任务要求建立的优先级原则,完成目标的分配、路径规划和航迹修正,预规划完成.

1.4.2 在线实时规划

在线实时规划:执飞后,当在飞行过程中出现不明物或者与其他飞机交汇的问题,由机载传感器提供数据信息进行分析、评估,分步判断目标对无人机是否有威胁、对任务的执行是否有影响:是,协调修改;否,则执行原计划.由此确定是否具有更改预规划的必要性,使无人机在动态环境下缩短任务执行的时间并提高了自身的自治能力.

1.5 小结

本节由分析多无人机任务规划的规划内容、目的以及原则,讨论了无人机任务规划的体系结构,系统至少包含7个模块,具备任务分配、航迹规划、协调处理等功能,分析了多无人机控制系统的结构,将无人机任务规划分为集中式任务规划、部分分布式任务规划和完全分布式任务规划和基于多智能体的分布式控制系统.最后阐述了任务规划的基本流程,理论上实现了任务规划过程中的离线预规划和在线实时规划.

2 任务分配

2.1 工作任务分配

任务分配包含了工作任务分配和工作目标分配.工作任务分配是指对侦察监视、目标指示、电子干扰、火力打击、效果评估等任务,在一定的场景、战况、任务下完全自主的智能式完成作战任务步骤的分配,工作任务分配与工作目标分配两者求解的问题模型以及解决问题方法大同小异,分配本质是一样的,都是一个优化组合NP问题,有关工作任务分配问题可见文献[26,36]对多机协同作战,完成了侦察、评估、打击3种任务的分配,建立了侦察—评估—打击—评估的任务执行顺序.国内外对工作任务分配研究相对较少,本章以工作目标分配问题(目标分配)为阐述对象.

2.2 编队级目标分配

在高动态实时战场下,无人机面对的目标数量众多且相对分散,为提高求解速度,研究者们将聚类思想用于目标分配— 目标群划分技术,由目标聚类分析建立目标簇,将此目标群分给某组无人机编队[28,31,37−38].文献[39]提出两阶段目标分配,第一阶段对分散的多目标聚类求解得若干目标簇,再将目标簇分配给不同的无人机编队,建立编队级目标分配,如图5所示[39].最后编队内的各无人机进行队内目标分配,完成编队内目标分配,如图6所示[39].

2.2.1 聚类分析

聚类分析是指使用数学的方法研究和处理对给定对象分类.可划分为:系统聚类法、有序样品聚类法、动态聚类法、模糊聚法、图论聚类法、聚类预报法等.聚类分析的算法可以分为:1)划分法(如:K-means算法、K-medoids算法、CLARANS算法等)在给定一个有N个元组或者记录的数据集,通过反复迭代的方法改变分组,使得每一次改进之后的分组方案都较前一次好,分裂法将构造K个分组,每一个分组就代表一个聚类,其中K

2.2.2 K均值算法

近10年,K均值算法(也称K-means算法)是无人机目标聚类分析使用最多、最常用的一种动态聚类、一种基于划分的迭代算法.通过反复修改分类来达到最满意的聚类结果.其基本思想:先以一些初始点为聚类中心,对样本集进行初始分类,判定分类结果是否能使一个确定的准则函数取得极值:能,聚类算法结束;不能,改变聚类中心,重新进行分类,并重复判定所使用的准则.设有k个分类,每个分类域中心为m,(j=l,2,···,k),常用的准则函数是使得每个类中的各样本到该类中心的距离的平方和取得极小值,即:

K均值聚类算法的运算步骤[40]:

1)确定初始聚点,根据聚点全部对象划分为两组,完成初始划分;

2)然后计算每组的中心,修改聚点,确定各组新聚点;

2)最后由新的中心将对象重新划分.

通过这样确定中心点建立目标簇完成编队级目标分配,就可将最近的目标簇分配给该无人机编队,可简化了多无人机—多目标分配问题,从整体上提高了目标分配求解效率.但是,传统K均值聚类算法由于产生类的大小相差不会很大,且对脏数据很敏感.许多研究者以改变初始聚点或修改聚点等对传统K均值聚类算法进行改进,如:K-means改进的K-medoids算法[39],K-means是以当前Cluster中所有数据点的平均值为中心点,而K-medoids以当前Cluster内满足到其他所有点的距离之和最小为中心点;此外文献[40]是以所有数据成员到聚类中心的距离与聚类的半径阈值对比判定中心点的办法改进传统K均值方法,当出现距离大于设定的聚类的半径阈值时,该点为新的中心点.再依次检测所有数据成员到聚类中心的距离是否小于等于聚类的半径阈值,若都小于等于则该点为聚类中心.以60个目标仿真后得到改进后K均值方法在求解预攻击目标聚类问题优于传统K均值方法,但是这样计算量增大且计算的时间相对变长.

聚类分析法还可用于航迹规划,文献[41]作者发现用遗传算法完成路径规划后常常会产生多条可行航路,这些航路在空间中的分布有些相对分散而有些相对集中.由此提出是否可将聚类分析使用到空间中较为分散的航路,计算航路的相对方向,对航路进行聚类.作者在文中还分析到由于不同的航路其节点数一般不同,因此,不能用航路节点作为特征对航路进行聚类,选择航路个体的适应度值和相对方向作为聚类的数据对象,将K均值聚类算法与基于遗传算法的航路规划方法结合起来,通过将航路个体进行聚类,生成K个子种群的航迹规划算法,这样就可提高规划航路的时间,更快生成可飞行路径.

2.3 编队内目标分配

多目标分配(图6)根据环境知识、任务需求、目标威胁强度及自身攻击能力等信息下,既考虑到飞行器的数量、是否异构、任务的类别和权重、飞行的环境等因素,又考虑可行的航程代价、合理的分配算法、各种协同约束条件等[10],使完成最大数量任务的同时也满足多机系统整体效率和资源配比达到最优的分配问题,是求解组合优化的NP问题[42].下面接介绍有关NP问题的几种常见模型以及解决NP问题的常见算法,并类比了这些算法在目标分配问题的上的适应性.

2.3.1 常见的问题模型

1)多旅行商问题模型

旅行商问题(TSP)是NP类问题的经典模型,问题是指有N个城市,要求旅行商到达每个城市各一次且仅一次,并回到起点且要求旅行路线最短.多旅行商问题(MTSP)是指多个旅行商从同一个城市或不同城市出发,分别走一条旅行路线,使得每个城市有且仅有一个旅行商经过(出发城市除外),且总路程最短等有关问题的研究.国内对TSP和MTSP问题求解进行尝试并改进各种算法使计算范围更大、结果更优化.文献[43]采用蚁群算法解决了无人机滞留防御方雷达探测范围内时间总和最小的航线优化问题;文献[44−45]提出改进的蚁群算法对多目标情况下的航路规划问题求解;文献[46]基于多目标多旅行商问题模型,将旅行商的个数和多旅行商的最长访问路径作为优化目标,采用改进的多目标模拟退火算法和多目标遗传算法分别对30个城市的旅行商问题进行了测试,发现改进的多目标模拟退火算法比多目标遗传算法计算复杂度低、能有较好的最优解且算法性能更优,此外文献[20]发现受时序优先级约束的协同多任务规划过程中会出现不可避免的死锁问题,基于图论提出了一整套方法进行处理,指出在多无人机路径协调过程中,沿着解的拓扑序列,顺序协调飞行路径,可获得最佳的协调效果.

2)车辆路径问题模型

多车辆路径问题(MDVRP)是车辆路径问题的一种扩展.根据车辆的型号是否相同,可将车辆路径问题分为单车型问题(VRP)和多车型题(HVRP).单车型问题假定车辆的型号相同,即具有相同的最大载重量、最大行驶距离、固定成本与变动成本,而多车型问题则不同,通常各车型的最大载重、使用成本等都各不同.目前国内对多车场车辆问题研究注重结合实际运行情况,从传统的启发式算法的应用到现在集中于现代启发式算法的应用,并对多车场问题进行扩充.而MDVRP,在多车辆路径问题上增加了多停车场情况,符合车辆的调度问题.国内2011年王征等人,对多车场带时间窗车辆路径问题的变邻域搜索算法进行了研究[47];2017年颜瑞等人,考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[48].多车场、多车型车辆路径问题(MDMTVRP),是对基本车辆路径问题的扩展,更是对多车场车辆路径问题和多车型车辆路径问题的组合,它的求解必然更加复杂.目前国内外还没有一个相对成熟的解决办法,这也是目前研究的热点问题和难点问题.国内学者对此问题已开始进行初步的研究探索,马建华等[49]以最快完成为目的求解MDMTVRP,对给定的顾客顺序划分车辆和指派车场,把该问题转化为寻找最优顾客顺序问题进行求解.然而,这种方法划分了路线,对每条路线取最优,达到了局部最优,但对于全局而言并不一定是收益最大的,即:不一定是全局最优解;2018年陈呈频等[50],对多车场与多车型车辆路径问题的多染色体遗传算法的研究,虽然全局上得到了最优解,但是计算量很大、且是集中计算,对服务器要求很高,花费时间很长.

3)混合整数线性规划模型

混合整数线性规划(MILP)的研究己有相当长的历史.1974年,G.Dantzig提出了线性规划单纯形间算法,并在应用中取得了很大的成功.但现实生活中机器台数、工作人数这类变化要求必须是整数,如果在线性规划的模型中添加一些整数约束,那么该模型将有更广阔的应用空间,由此产成了MILP.目前求解MILP的方法主要有分支定界法和巧平面法.用混合整数规划技术求解规划问题具有一些优点[51]:模型描述简洁、直接,很容易表示涉及到数值的全局约束,有助于提高无人机任务执行效率和生存能力,达到了任务分配的目的和初衷,且当无法求得最优解时,可以较快求出次优解.文献[52]采用混合整数线性规划技术对无人机最优搜索任务方法的研究,仿真结果表明如果有可能降低优化问题的复杂度,则可以减少计算时间.但是模型规模不能过大,问题规模过大将导致计算量指数型增长,任务分配的实时性得不到保证.

4)网络流模型

网络流模型(NFM)网络流是一种类比水流的解决问题方法,与线性规划密切相关.其优化特性是对于已知攻击目标、行为的数据集进行学习,以及对人为选定的攻击组合特征进行优化,使之更能反映该攻击行为的特点.网络流量分配模型是基于网络流量特征向量分层划分的思想,具备基本特征和优化特性两个特点.文献[53]中将网络流量分配划分为:平衡配流[54]和非平衡配流.在一定供给和需求水平条件下,如何确定网络中具体弧段上的流量,用于模拟当前整个运输网络的状态,评估其性能从而为决策者制定政策及网络发展规划提供依据.文献[55]介绍了网络流量分配模型的基本概念和移动云计算环境下可以有效解决发展中遇到的移动设备差异化和网络环境复杂带来的资源浪费、网络开销大等问题,使移动端和云端各尽其能,大大提高程序运行的效率.

2.3.2 常见的求解算法

1)打击式目标分配

2.3.1节中几种NP问题模型现已有许多解决算法:传统的匈牙利算法,用于分布式系统的合同网法以及目前正蓬勃发展的智能优化算法.经过对这些算法学习、研究,通过它们各自的特性、适用性等不同,建立如表1所示的目标分配算法的类比.虽然这些算法能解决一些约束少、优化目标少、规模小的目标分配问题,而为能解决在现实环境中的复杂问题,研者们尝试对已有的算法进行改进与优化,并得到不错的效果.国内学者,文献[56]基于同构多机协同空对地,建立了目标分配模型,根据战术任务和战术目标提出相关约束,减小搜索范围提高攻击效率.同时引入满意决策理论,根据攻击满意集来搜索目标分配最优解,大大提升了搜索效率;文献[29]对3个有人作战智能体控制的不同数量的异构无人作战智能体进行多目标分配,分别采用集中式遗传算法、传统合同网算法和扩展后的合同网算法(CNP)的分布式分配法,发现在集中式遗传算法可得到优于全局的分配方案,但通信量和计算时间上都高于其余两种,若目标新增则需重新求解;而采用分布式扩展后的CNP具有更好的寻优质量,通信量小于传统的合同网,但由于扩展后CNP在招标、投标和中标策略比传统CNP的复杂度大,在计算时间上,需要更多的计算时间,以牺牲少量计算时间为代价得到了较高质量的解和较少的通信量;文献[57]采用模拟退火遗传算法进行目标攻击分配方案的寻优,对算法中的非常规编码、变异以及模拟退火平衡条件和冻结条件进行了设计,结合最优导弹目标攻击分配方案,得出相应的最佳协同多目标攻击决策解.

2)对抗式目标分配

目前大多数研究都是单次(一次性)静/动态打击式目标分配,但由于未来无人机自主作战过程中不可能是单次目标分配,而是敌我双方动态(多阶段多次)对抗式目标分配,国内学者哈尔滨工业大学教授韩松臣1996年提出[58]可基于马尔可夫动态系统通过随机服务系统输入过程的最优控制建立目标分配决策模型的方法,考虑实战中不同类型目标(如核武器、重型轰炸机、诱饵弹等)的威胁程度相差很大利用这种方法得到的决策结果能有效地减少重点目标突防的概率,得到攻防对抗式目标分配决策.北京航空航天研究者姜欢、陈万春2007年[59]对动静态结合的武器目标分配方法求取最大化的拦截效能其基本依据马尔可夫决策过程和随机服务系统输入过程最优化问题.采用马尔可夫决策用于目标分配通过策略迭代算法得到最优分配策略从而实现系统效益的最大化.2012年黄长强等[60]研究了基于博弈论建立在纳什平衡(在双方都为最优策略)下的对抗策略,并仿真完成了动态下的多次武器目标分配.但不足之处是当打破这一平衡,整个过程便不会具有动态特性.

对抗式动态目标多次分配问题的研究仍然处于起步阶段,目前没有系统的理论能够解决这一问题.

2.4 小结

在第2节中我们以编队级、编队内目标分配这两阶段着手分析研究,介绍了编队级目标分配解决问题的一般步骤和K均值算法.例举了编队内目标分配的几种常见的分配模型,再将目标分配算法从作战方式上分为:打击式与对抗式,例举了打击式静、动态目标分配的算法并分析了其特性及适用性和研究者们对对抗式目标分配提出的一些可用方法.

3 航迹规划

3.1 路径规划

3.1.1 基于环境建模的方法

1)路标图法

路标图法包括可视图法、Voronoi图法和概率路图法.可视图法、Voronoi图法通过对环境空间的釆样处理,把环境空间转换为避开路径中(起点到终点)所有约束区由若干线段组成的二维网络.而不同之处在于,可视图法是将障碍物设置成一个多边形,其余空间为自由区,由各多边形上的顶点连接而成的可视直线,是最早的路径规划方法之一;Voronoi图法[16]是将地图规划成围绕障碍物的多个共边的多边形连接图,从这些多边形的节点经过公共边到下一个节点直到非完整性规划和运动动力学规划中,其优点根植于它不需要连接任何一对位姿点或状态点,完成从起点到终点的路线,是目前使用较多路径规划方法之一.文献[16]叶媛媛等人对想定的已知静态配置的威胁和突现威胁通过Voronoi图法对无人机任务规划建模,确定此方法作为初始可选航路可行.概率法是随机选取相邻点使其满足一定的优化准则,如最短距离,此时概率法称为随机概率路图法.在概率法基础之上,1996年Kavraki等以分隔单元内的搜索的方式研究得到概率路图法.1998年Lavalle,2001年Cheng等通过现有树中最近点相连得到下一步轨迹的方式研究得到快速扩展随机树法,文献[61]提出快速扩展随机树法优点在于无需启发式函数,以随机性作为最有力的参数;应用于航迹规划的随机数据结构,针对不确定环境下的航迹规划问题,并能直接应用于非完整性约束下的环境,而概率路标算法则需要上万个这样的连接.

表1 目标分配算法

2)单元分解

单元分解法是将环境划分为若干个正四边形或正六边形栅格,有障碍物、威胁、禁飞等区域视为不叠加的阴影区,其余为自由区,在空间区域内连通栅格构造(从起点到目标点)代价最小的航行路径,但即使这样,相比其他方法可选的空间环境变小,路径相对变长,且栅格的大小也对路径规划有很大的影响:当栅格较大时,其存储信息量小,航路质量低;当栅格较小时,存储信息量大,相比之下航路的质量高.

3)人工势场法

人工势场法[62−63]是将整个空间区域建势场模,基于“同性相吸、异性相斥”的原理,在目标吸引力场与障碍物排斥力场共同作用的势能场下,沿着势函数下降的方向运动,结合搜索算法选择最优路径.其优点在于与障碍物相排斥规划出的路径相对安全,实时性极强可用于在线避障且规划出的路径相对平滑.缺点在于势场对一些约束条件不好处理,且障碍物如“C”型易陷入局部极小的陷阱区域问题.此方法通过求合力控制移动飞行器的运动,当障碍物过密过多,在狭窄的路径中可能会造成斥力大等于引力,无人机无法飞往目标或者出现抖动问题[64].所以适用于障碍物数量不多的环境中,且仅用于单无人机.

3.1.2 路径的优化组合

路径优化问题是指在飞机性能、自然环境、任务要求等约束条件下,从全局出发,合理安排各无人机有序完成任务,达到路程最短、费用最少、耗时最少、毁伤程度最少等目标的调度技术[65].也可以看成复杂的优化组合NP问题,目前解决路径优化[45,66−67]的方法可分为:精确算法(分支定界法、动态规划法、网络流算法)、传统启发式算法(扫描法、数学规划法)、智能优化算法(禁忌搜索法、模拟退火法、蚁群算法、遗传算法[17]等),其特性及适用性分析见表2.和声搜索算法[68]是近几年新提出来的一种智能算法,一种启发式全局搜索算法,通过反复调整记忆库中的解变量,使函数值随着迭代次数的增加不断收敛,从而来完成优化.算法概念简单、可调参数少、容易实现.除此之外,董乔月、李洪双等[69]2016年在解决桁架结构优化设计和机翼翼盒结构优化问题时使用了增广拉格朗日子集模拟优化方法.增广拉格朗日子集模拟优化方法是一种基于增广拉朗日约束处理方法和子集模拟优化方法发展的优化设计方法.利用拉格朗日乘子法处理多重约束条件,再利用子集模拟优化方法对转化后的无约束优化问题进行求解;对罚函数因子的更新方法进行改进,以保证收敛过程的稳定性.作者将其与其他著名优化算法进行对比,发现相比于遗传算法、蚁群算法、粒子群优化算法更具有很好的寻优准确性,相比于和声搜索算法具有不超越最大约束限制.由此我们可对此方法继续深入研究是否能用于求解任务规划的优化组合问题.此外用于解决单机快速路径规划有A*算法、D*算法和Dijkstra算法.A*算法是一种经典的最优启发搜索算法,以栅格为基础,以栅格中心点为子节点进行扩展,可过滤掉不必要的节点(不同问题的具体约束结合)削减了搜索的空间.同时A*算法是智能搜索算法,搜索效率高,但最优程度取决于启发函数的表达式且当搜索空间很大时,计算量也大,主用于路径预规划.文献[70−72]研究了基于A*算法在路径规划和图搜索的工程应用,文献[73]对A*算法改进为稀疏A*算法,将节点带约束的选择性扩展,减少了搜索的空间.A*算法与Dijkstra算法只适用于静态环境,D*是动态的A*,D*算法是A*算法与Dijkstra算法的结合在动态环境中寻路非常有效,向目标点移动中,只检查最短路径上下一节点或临近节点的变化情况.其他的还有文献[41]利用元胞自动机算法解决航迹规划问题,将航迹规划问题分为多层次问题,对每一层的问题,分别提出了解决的方法,再将各层次问题综合得到最终的航迹优化结果.

3.2 航迹修正

3.2.1 平滑处理

平滑处理是航迹规划技术中重要组成之一,是解决路径初规划后使路径满足无人机飞行性能约束的问题.路径初规划是由许多最短直线首尾连接而成的折线,具有一定的角度,而无人机受飞行性能约束,转角有限不能都达到.研究者们对此问题提出路径修正:轨迹曲线规化法即平滑处理,将不满足飞行性能约束的路径,计算修正为满足飞行约束的曲线,建立参数控制,使无人机沿满足飞行性能约束的曲线航迹飞到终点到目前为止,文献[61]在航迹平滑层中引入k航迹平滑算法奠定了基础.文献[67]航迹平滑过程基于B-spline方法,对平面移动和高度变化被分别考虑,算法通过对控制点的修整,使生成的航迹满足场景及UAV的约束;文献[74]采用CR样条曲线是Bezier曲线的一种改进形式,一种插值样条曲线,参数方简单,计算速度快,具有C1连续性(切线连续),且修改其中某一控制点只会修改相邻的曲线变化,不会影响距该点较远的曲线形状,当要对某些航迹段调整时,仅需要对部分航迹做出改变即可.文献[75]基于Clothoid螺旋曲线的复合路径,采用一种新的算法与基于微分几何的迭代算法相比能够在任意起止点位置和方向下得到更短的曲率连续的Clothoid复合路径且算法迭代简单.曲线规划法包含的种类众多,但它们适用性并不相同,表3简单介绍了几种常用的曲线,分析了各自的适用性.

表2 路径规划算法

3.2.2 安全距离

目前,国内外对曲线规划法的研究已不只在路径的平滑处理.多无人机协同攻击时存在两机或多机交汇问题,为避免无人机交汇碰撞将无人机建立轨道安全距离,如果不满足安全约束,需通过改变曲率或添加中间航路点等方法,通过K航迹平滑处理法、Dubins曲线、Clothoid螺旋曲线、PH螺旋曲线等对路径修正,如文献[76]仿真得到PH路径随切线向量长度k变化,如图7所示[76].文献[77]在城市环境和山区环境下提出使用PH曲线和和声搜索算法调整飞行路径以满足空间需求,满足无人机的运动和动态约束,保证任何两辆车之间都大于等于安全距离,不存在碰撞路线以及障碍物.此外有的研究者将躲避新障碍物问题也看做航迹安全距离问题.由于人工势场法常用于躲避障碍物,并可以得到较平滑的路径,但由于它只适用于障碍物数量不多的环境下,文献[64]指出传统的人工势场仅限于单个无人机轨迹规划,为了克服这一挑战,提出了一种利用距离因子和跳跃策略来解决不可达目标等常见问题的方法,并确保无人机不会碰到任何障碍物.此外,使用动态步长调整方法解决抖动问题.已在定量测试仿真模型中得到验证,并且在模拟城市环境中获得满意的结果.国内外研究者们对航迹修正(避障)还研究出其他可行方法:文献[67]采用启发式A*搜索算法和B样条曲线对1)无人机探测半径的航迹修正、2)不规则障碍物的航迹修正、3)突发情况的航迹修正、4)目标位置改变的航迹修正、5)目标变异的航迹修正,这5种情况下由于威胁的突发性对航迹在线修正,并得到了较好的实验结果.也有其他研究者用蚁群、遗传等智能搜索算法代替A*算法虽然可以满足多架无人机协同规划问题,但这样的搜索算法计算时间过长,对躲避动态障碍物在线实时路径修正的实用性不大.由此研究者们将曲线规划法直接用于避障技术上,将障碍物所处的路径位置看作不满足飞行约束的路径,对路径进行曲线修正避开障碍物.文献[78]一书中详细介绍了Dubins曲线、PH曲线、Clothoid曲线用于已知障碍物的路径修正问题和结合安全圆算法或中间航点算法解决未知障碍物的避障路径修正.国内杨秀霞、张毅、周皑皑等人2015年采用PH曲线用于航迹修正法、分布估计算法解决路径优化问题、速度障碍法在线勘测障碍物这3种算法完成了在线避障航迹规划,PH曲线在此可由不同初始条件和终止切向量长度,满足曲率约束的初始和终止偏航角[79];2016年对现有避障算法忽略重规划路径侵犯威胁障碍物安线路径规划为例,基于速度障碍圆弧法给出了速度障碍圆弧法,并在此基础全圆的问题上提出一种基于PH螺线修正避障重规划路径的方法[80];2017年结合PH曲线路径规划提出了一种动态不确定环境下UAV自主避障算法[81].

3.2.3 多机协同优化

目前国内外对无人机在突发威胁后,采用曲线规划法对路径修正避开障碍物,可看作小范围的航迹重规划.此法不但简化了系统的复杂结构,更可缩短计算时间.采用曲线规划法优化飞行路径,使多机协同大致建立在两种思想上:1)使得平滑后的航迹与平滑之前的航迹长度相等,以满足多机协同规划时确定的预计到达时间不变;2)基于各无人机都能达到的约束条件下或性能相同的情况下,使多架无人机从起点到达终点修正后所产生的路径长度相等,也可满足来多无人机路径规划的协同性.文献[61]基于第1种思想提出一种分级分解的方法,将优化分解成3步,将协同航迹产生器分解为航迹生成层、航迹协同层和航迹平滑层.在航迹生成层中引入了快速扩展随机随算法,并通过对随机扩展函数进行改进以及采用Dijkstra算法对冗余节点进行处理,提高了算法的效率;在航迹协同层中以编队代价函数最小为约束,确定了各机的航迹以及同时到达时间(ETA)并确定了各自的速度;在航迹平滑层中引入k航迹平滑算法对航迹拐点处进行处理并通过对参数k的取值使得平滑后的航迹与平滑之前的航迹长度相等,以满足多机协同规划时确定的ETA不变.而国外研究者们基于第2种思想,设定多无人机为一组匀速飞行的无人机,将多无人机路径规划同时到达问题分为了3个阶段:产生可飞行路径、产生可行路径(采用Dubins曲线、Clothoid曲线、PH曲线用于二维和三维的可飞行路径规划建立无人机之间的安全距离)和产生等长度路径(改变曲率的方法调整路径的长度),成功应用在二维和三维空间内多机协同达到的Dubins路径和PH路径中[78].

表3 路径规划算法

3.3 小结

第3节主要叙述了航迹规划中基于环境建模的3种方法,常用于路径优化的算法其特性及适用性的分析,阐述了平滑处理中采用曲线规划法修正了不满足无人机自身特性的规划路径,分析了6种不同曲线其特性和适用范围.最后介绍了改变曲率或添加中间航路点的数目可处理两机之间的安全距离问题和多机协同的问题.

4 总结与展望

多无人机协同任务规划技术是一个综合性研究课题.本文围绕系统架构、目标分配、航迹规划等方面进行总结,并根据目前的研究现状,浅谈对多无人机任务规划技术的展望:

1)以分析多无人机任务规划的规划内容、目的以及原则,无人机任务规划的体系架构至少包含7个模块,具备任务分配、航迹规划、协调处理等功能,发现基于多智能体任务规划系统的控制架构,相比于其他控制架构,其鲁棒性好,具备良好的协同能力和自治能力,可减少无人机的反应时间,提高作战能力.但软件的程序上所涉及层次增多,设计更为复杂.基于离线预规划上并可在线实时规划完成方案重规划,虽然在理论上可实现,但是在实际应用中,系统计算程序的设定以及发现冲突后,对已有方案部分修改的判定以及如何修改还需要深入研究.

2)目标分配以编队级、编队内这两个阶段着手,目前这两个阶段的分配问题都有可行方法.但国内外在任务分配技术上的发展尚未成熟,目前对静态目标分配已形成了一套研究方法和步骤,对动态分配的分配技术也有不少研究者提出了解决的办法,但对于目标—武器的多阶段的综合性分配问题,虽已有采用博弈论的办法可解决,但需基于纳什平衡下才能完成分配,这一问题目前任然是我们无法突破的难题.此外工作任务分配技术与工作目标分配技术的结合问题,形成“OODA”一个完整的任务分配过程,这将是解决目标分配问题后的下一个关键点.

3)航迹规划中研究者们已从环境建模、路径优化、航迹修正这3个方面完成了无人机航迹规划的研究.并可通过改变曲率或添加中间航路点的数目来处理两机之间的安全距离问题和解决多机协同问题.但无人机飞行时飞行环境复杂、攀爬动力有限、转弯角度受限且要求工作效率高,不同的实时任务要求下,对选择适合的曲线路径、中间航路点数,控制适合的转弯曲率尤为重要.无人机航迹规划系统应为决策者(决策系统)分析、预测航迹的变化趋势,提供航迹在线代价评估,从航迹规划上提高作战效率.这也是亟待解决的问题之一.

通过对多无人机协同任务规划技术研究、分析,发现各类问题虽已有许多行之有效的解决方法,但任存在诸多不足.由于不同的无人机具有不同的特性、适应性,由此下一步我们将尝试在设定的场景下,对比各种模型及算法,选择适合无人机的工作特性方法,并基于某一理论找出最优办法进行优化,缩短计算的时间,提高工作效率,使之在任务规划问题内充分发挥自身优势.