无人机集群任务规划方法研究综述

 电话：010-82030532 手机：18501361766

微信：tech99999 邮箱：yw@techxcope.com

来源：无人机

作者：贾高伟, 王建峰

任务规划是指在任务执行过程中对个体工作状态及使用方法或步骤的规划及安排,遍布于社会生活诸多领域,几乎所有社会系统的运作都必须明确什么样的任务该由什么样的成员来完成。任务规划理论是多类领域特殊任务规划问题求解发展的结果。鉴于任务规划之于群体运行的重要意义,长时间的研究使得该方面成果丰富。理论上讲,任务规划是一类多约束条件下的优化问题,从任务规划理论的发展历程看,20世纪60年代以前,主要的理论模型包括线性规划问题及单纯形方法[1]、指派问题[2]及匈牙利法[3]、整数规划问题[4]及分支定界方法[5]等经典的任务分配理论。随后受分布式系统发展的影响,任务规划理论得到快速的发展,随之而来的关键成果包括典型的0-1规划模型[6]、图论模型[7]、负载平衡模型[8]。20世纪80年代后,分布式智能任务规划方法开始出现,该类算法对数学模型的依赖很小,借鉴生物习性,逐步形成一类优化方法。

无人机具有低成本、无人员伤亡、操作方便简单、灵活可靠等优点,近年来发展迅速,各式各样的无人机层出不穷。结合日益发展的网络信息技术,促使了无人机集群的出现和高速发展。无人机集群技术已经演化为航空工业的核心技术之一,表现出巨大的应用潜力,尤其在军事应用领域。类似于其他社会系统,无人机集群的任务规划为无人机集群应用的核心技术,是指根据无人机集群的数量、要完成的任务及任务载荷情况的不同,对无人机集群所需完成的具体任务进行预先设定与统筹管理,决定着无人机集群的应用效能。因此,相关研究在全世界范围内得到了广泛持续的关注。从复杂程度上讲,无人机集群是由多无人机进一步提升发展而来,无人机集群是多无人机的高阶形式,二者的区别可以由表1来概括。

表1 无人机集群与多无人机的对比

Table 1 Comparison between unmanned aerial vehicle swarms and multiple unmanned aerial vehicle

无人机集群的灵活组织与运用,离不开科学的体系架构设计,不同的架构设计又牵引着不同的技术路线和方向,影响着无人机集群的任务规划、协同决策与实际效益。概括来讲,适合于无人机集群的控制架构包括集中式、分布式、集散式等多类[9]。

(1) 集中式:该体系的确立源自“单无人机-多无人机-无人机集群”的发展思路,是当前最直接、最成熟的集群架构模式,无人机集群接受单个或多个中心控制。该体系架构对无人机数据链带宽、速率、功率以及可靠性提出了很高要求。

(2) 分布式:该体系类似于自然界生物集群,无人机之间地位平等,通过彼此信息交互,协同完成任务。该体系是一种朝“完全自主”方向发展的任务构型,对无人机机间协同能力要求很高。分布式体系下各无人机单元之间的通信信息量较大.

(3) 集散式:该体系结合了集中式和分布式的优点,利用分布式自治与集中式协作相结合的方式,来解决全局控制问题。该体系符合现阶段集群技术发展现状,在可预见的今后一段时间,可能成为常态的实用化体系架构。

鉴于任务规划理论的多样性以及无人机任务样式的复杂性,截止目前,关于多无人机任务规划技术的研究成果丰富[10],而无人机集群是多无人机的高阶形式,对应的任务规划技术将呈现更为复杂的技术特征,本文拟针对近几年无人机集群的研究现状,从两个角度归纳无人机集群任务规划技术的发展特点和关键方向。

基于人类知识所建立起来的逻辑与规则,是实现多无人机任务规划的重要渠道,沿袭了分层递阶的思想[10],从顶层规划到分层逐步实施,降低了问题的复杂性。该思路符合人类社会管理的一般规律,易于理解,成果丰富。典型的任务规划方法也秉承了这一思想。

概括地讲,多无人机任务规划的内涵十分宽泛,可以包括但不限于任务目标分配、航迹规划、任务载荷规划、数据链路规划、应急处置规划等等。一般地,任务载荷规划、数据链路规划以及应急处置规划等功能相对独立,对无人机集群属性的依赖度不够强,比如有专用的传感器使用规划、链路配置规划系统等。常见的做法是在无人机集群的任务分配与航迹规划中将任务载荷、链路设置、安全飞行等因素作为规划的约束条件。

因此,本文对多无人机(乃至无人机集群)任务规划技术的介绍,主要从任务分配和航迹规划两个层次展开。任务分配与航迹规划是无人机集群任务规划中的关键环节,决定了无人机集群执行任务的时序关系,多无人机与多目标之间的映射关系,单架无人机的可执行航线等,确保无人机能够安全适时地抵达任务区域并最大效能地完成任务。任务分配和航迹规划共同奠定了无人机集群执行任务的基本能力基础。

无人机任务分配用于建立无人机与任务之间的关联和映射关系,是多约束条件下的离散空间组合优化问题,其实施的关键是建立可数学表达的目标函数并有效地处理各项约束。本节从集中式任务分配和分布式任务分配两个方面简要地归纳相应的典型方法。

1.1.1 集中式任务分配典型方法

适合于多无人机集中式任务分配的数学模型主要包括:多旅行商问题(multiple traveling salesman problem, MTSP)[11],车辆路径问题(vehicle routing problem, VRP)[12],多选择背包问题(multiple choice knapsack problem, MCKP)[13],混合整数线性规划(mixed integer linear programming, MILP)问题[14], 动态网络流优化(dynamic network flow optimization, DNFO)模型[15],多处理器资源分配(multiple processors resource allocation, CMTAP)模型[16]等。这些模型一般可以推广应用于无人机集群,但随着无人机数量和任务类型增多,分配问题的描述将变得愈加复杂。

集中式任务分配求解方法又可以分为最优化方法和启发式方法。其中,典型的最优化方法如图1所示。整数规划(integer programming, IP)法通过建立目标函数和约束条件的方法进行求解,矩阵作业法[17]、单纯型法、匈牙利法、分支定界法等是常见的IP法,这一方法也演变出一类混合整数线性规划算法[13]。约束规划(constraint programming, CP)法由变量集和约束集两者组成,变量集内的所有变量都有自己对应的值域,是求解组合优化问题的常用方法。图论法通过图示的方法把目标和接收任务的对象特征表征出来[7],利用图论法在任务和系统成员之间建立匹配,网络流模型和偶图匹配模型是经典的图论任务分配模型。一般而言,最优化算法具有描述简洁、直接等特点,可以灵活调整约束条件来求解实际问题,具有理论最优解,但规模不宜过大,一般可用于无人机集群离线式任务分配。

启发式方法的基本思想是在算法时间和求解结果之间进行调节,在能够接受的时间内求得局部最优解或满意解,具体分类如图2所示。

Fig.2 Classification of heuristic methods

在启发式方法中,列表算法基于优先权函数对任务处理次序进行排列,随后分发给各成员[18];聚类算法将任务作为一个簇进行聚类,通过满足任务簇与系统成员数达到一致[19]实现分配,两者都有一定应用。智能类算法的应用相对比较普遍,尤其以遗传算法、粒子群优化(particle swarm optimization, PSO)算法、蚁群算法为多。这几类算法通常具有较强的稳定性,适合分布式计算机制、也能够与多类其他算法结合,但缺乏严谨的数学基础,没有对应的深刻的、具有普遍意义的理论分析,对其机理的数学解释薄弱,也缺乏规范化的、针对算法优化性能的评价准则。尽管如此,这些方法及其改进算法依然广泛应用于无人机任务分配。

1.1.2 分布式任务分配典型方法

分布式任务分配的典型模型主要包括多智能体决策理论、类市场机制(合同/竞拍)、分布式马尔可夫、分布式约束等。多Agent理论[20]广泛应用于机器人领域,其中一致性问题是多智能体协同控制的根本问题。随着应用样式的多样化,多Agent理论衍生了很多分支,并取得了诸多成果,具体如图3所示。

Fig.3 Decentralized task assignment models and methods

针对智能体与不确定因素之间的矛盾,已有的常用算法包括博弈论方法[21]、分布式马尔可夫法[22]、分布式贝叶斯方法[23]等。分布式约束可以形式化为一个约束网,网中变量有各自离散值域,且各自约束相互联系,求解过程即是求出变量的某个组合使得所有约束值相加获得极值[24]。分布式约束也可以看作是多Agent理论的分支应用。

类市场机制的方法是多无人机任务分配中应用广泛的一种分布式方法,其核心处理是防止冲突,对每个问题的求解采用通信协商的方式解决。合同网方法[25]由发布者和竞标者两个角色,由“招标-投标-中标-确认”4个交互阶段组成。而拍卖法[26]则是将要拍卖的物品用公开竞价的方式转卖给应价最高者。一个拍卖主要由参与方、拍卖品、收益函数和应价策略等要素组成。拍卖算法的演化算法也逐渐引起广泛重视,如一致性包算法(consensus-based bundle algorithm, CBBA)[27]。

1.2.1 单机航迹规划方法

航迹规划的作用在于为每架无人机执行所分配的任务建立可执行的航迹安排,其本质上是连续空间的路径寻优问题,是任务规划分层递阶策略的底层实现。从航迹规划的发展历程看,已有的典型规划方法可以分为基于路标图形的航迹规划和基于格栅的航迹规划等,此处进行简要概括,具体如图4所示。

Fig.4 Partial typical methods of unmanned aerial vehicle trajectory planning

最优控制法[28-29]是将航迹规划问题看作非线性、带有状态约束和控制约束的控制问题,进而求解得到符合实际飞行要求的规划路径。又可分为间接法和直接法,后者的应用更广,其利用数值化将最优控制问题转化为非线性规划问题,典型代表有伪谱法[30]。

路标图形法本质上是对规划环境的采样,是对规划空间的一种压缩处理[31-32];可以结合目标与规划空间的威胁等因素构建多类型图形,如Voronoi图,概率路标图(probabilistic road map, PRM)[33],可视图和快速扩展随机树(rapidly exploring random tree, RERT)等[32],最后通过搜索算法得到合理路径[34]。

栅格处理同样是对连续规划空间的离散化,由于现代数字地图都是栅格化处理得到,因此基于栅格的航迹规划方法发展迅速。A*算法是启发式搜索算法,将搜索空间表示为网络的形式,以网络的中心点或顶点作为航迹点,搜索邻域内代价函数值最小的航迹点,从起始点逐步搜索至目标点,最后逆向回溯当前节点的父节点完成航迹生成[35]。

利用优化求解方法获得航迹规划方面,人工势场法算法简明、实时性好、规划速度快,在局部规划和实时规划领域应用广泛[36],但主要问题是在复杂环境中容易产生局部极小值,在障碍物附近抖动或频繁摆动。智能类优化法的优点是算法求解对初始解状态依赖较小,能够渐近收敛于全局最优解[37]。

在实际应用中,上述多类算法也可互相借鉴与融合应用,解决航迹规划速度问题、动态性问题、航迹与载荷使用耦合问题等[38],例如Haider等人针对多无人机搜索与营救任务,采用Dijkstra算法和人工势场算法结合的方法,完成静态和动态规划[39]。

1.2.2 多无人机协同航迹规划

多无人机航迹规划协同性的体现,大多针对特定的目标或者具体任务。例如,庞强伟[40]围绕多无人机对多目标的协同侦察,依据K-means聚类算法完成目标集合的聚类,求解侦察序列,由侦察序列对应生成各无人机的任务航迹。胡超芳[41]针对多无人机协同追踪地面移动目标的问题,基于分布式预测控制架构,引入多无人机之间避碰约束,求解有限时域内每架无人机的局部航迹。周德云[42]针对多无人机区域内协同打击任务,强调“同时抵达”的时间和空间强约束环境,建立了基于多目标优化的航迹规划方法。王道波等人[43]针对地面移动目标,考虑了传感器安装姿态及有效观测模型约束,建立了基于化学反应优化理论框架的启发式多无人机航迹优化策略,得到了具有更长的目标检测时间的规划方案。Shah[44]考虑无人机间观测区域必须重叠、所有无人机同时抵达、无人机间满足通信条件等约束,基于Pythagorean曲线完成了有障碍环境内的多无人机航迹规划。Ema[45]针对市区环境内协同避障,通过无人机间的信息交互为其他无人机在线提供障碍信息,得到了一种基于人工势场和全局规划策略结合的多无人机航迹规划策略。概括来看,多无人机航迹协同是由于所执行任务之间的耦合性牵引多机之间的时空协同。

随着无人机集群数量和任务样式的增多以及协同性要求的提高,第1节阐述的多无人机任务分配典型方法适用性受限。无人机集群相对于多无人机,在任务分配上面临的新的重要挑战包括:模型的合理性与应用适应性需进一步拓展、任务分配的求解速度与动态可塑性要求进一步提升、亟需适应信息的不完整与不确定性。上述3个主要挑战对应的科学问题如下。

2.1.1 分配模型的完善与复杂度之间的均衡

无人机集群数量规模的增大,要求求解算法的效率大为提升,这是分配模型需要完善的重要驱动力。进化类算法对数学模型依赖小,因而得到了持续研究和发展,对智能类算法的初始化、粒子编码的改进是常见的应对思想。王婷[46]通过设计新的遗传算子,对适应度值进行标定,避免了传统遗传算法在最优解附近摆动的现象。沈林成[47]根据PSO算法离散化映射方式,将离散PSO(discrete PSO, DPSO)分为基于连续空间的DPSO和基于离散空间的DPSO两类模型,能够用于求解集群高维复杂离散优化问题。朱德法[48]设计新的粒子群位置和速度更新过程。国博[49]对粒子分群处理与合并优化。Hoang[50]对无人机航向角进行粒子编码等策略,都促使粒子群算法分配模型针对性优化以能够适应大规模集群,加速了粒子收敛速度。此外,Vincent[51]和Ugur[52]结合硬件设备特点,实现了遗传算法、PSO算法以及蚁群算法的并行化处理,也提升了进化速度。

无人机集群任务样式的多样性和特殊性,要求分配模型进行针对性与适应性拓展,结合任务属性增加模型约束条件并维持求解复杂度是常见的处理思想。张耀中[53]针对不同侦察能力的无人机集群多任务区协同侦察,将达到时间作为强约束,结合分布式拓展一致性束算法,在多项式时间复杂度的层面实现了遍历侦察任务规划。林君灿[54]针对侦察/控制/打击/评估一体化无人机集群作战应用,在分配模型中增加时间窗约束,并利用混合整数线性规划算法实现了集群离线式任务分配。严飞[55]针对多无人机协同搜索和同时攻击的任务约束,引入协同粒子群、协同函数、协同变量,并结合合同网模型实现任务分配。罗德林[56]针对大规模无人机集群对抗任务,引入了规避不利目标、支援处于劣势友机的功能约束,结合分布式博弈决策模型,实现了群对群对抗中的目标分配。Khaled[57]针对森林着火点监视与探测,引入无人机间冲突规避约束,以及无人机控制参量化、时间离散化等建模策略,丰富对无人机单机控制模型的描述,实现着火点目标的分配。

2.1.2 求解空间剧增条件下的快速收敛优化

满足多目标条件下的共同优化是应对协同等级提高的新需求,无人机集群多目标任务分配使得求解空间大幅扩增。以智能类优化算法为例,加速进化进程和结构化减小解空间是常见的快速收敛优化思想。Farid[58]针对无人机群对群对抗,在减少视场区域和满足规避动作的约束下,对比了多目标PSO算法、改进非劣分层多目标遗传算法(non-dominated sorting genetic algorithm version 2, NSGA2)[59]、强度Pareto算法(strength pareto evolutionary algorithm version 2， SPEA2)、多目标进化算法(multi-objective evolutionary algorithm, MOEA)等的任务规划性能。施展[60]基于量子粒子群算法,通过将粒子高斯变异改为混沌变异,增加粒子群的遍历性和随机性,提升了多目标分配收敛速度。王建峰[61]在量子粒子群算法中设计了多层编码策略和约束调度方法,通过非支配解评估引导算法进化,兼顾了收敛性和分布性。韩博文[62]基于量子粒子群算法,通过佳点集构造产生初值解,基于量子变异和混沌因子拓展遍历解空间,设置动态惯性引导前期全局搜索、后期局部精细搜索,最终实现在保证遍历性的基础上加速进化搜索。

实战或者对抗背景下无人机集群的动态调整导致求解空间增加,并迫切需要分配算法的快速收敛性。集群任务分配算法应对动态调整的直接思路是在原有任务方案基础上对局部任务进行重分配调整,当前主要的处理思想是约束动态重置对任务分配解空间产生非线性剧增。具体算法方面,Carlos[63]提出了一种通用的包括全局任务规划和单智能体任务规划的动态分配架构,以全局规划-局部调整的策略支持实时在线的任务调整。史豪斌[64]提出了基于迭代自组织数据分析技术算法(iterative self-organizing data analysis techniques algorithm, ISODATA)约束聚类的多无人机动态任务分配方法,ISODATA是无监督分类机器学习方法的一种,克服了K-means聚类方法需要人为设定K数值的不足,能够动态地进行类的合并与分裂,最后得到满足动态性要求的任务方案。一致性竞拍算法(consensus-based auction algorithm, CBAA)和CBBA是基于市场竞拍策略的分布式任务分配算法[65],Noam[66]针对分布式时间敏感任务,将CBBA与部分重规划策略结合,通过改变任务重规划过程中重置任务数,在收敛速度和协调规模之间折衷,针对性重置最少的竞拍任务,使得任务分配解空间同重置任务数和集群规模保持线性复杂度关系,在满足任务约束的情况下大幅降低了运算量。

2.1.3 信息不完整条件下的模糊度量和优化分配

无人机集群的实战对抗要求任务分配算法能够在不确定因素(如态势不明确、信息被阻滞、欺骗和干扰)存在的情况下完成高效的方案规划。而集群数量规模的增大以及协同等级的提升,也放大了不确定因素的影响。该问题的关键处理思想是不确定度的建模与量化。陈侠[67]以目标价值收益、毁伤代价以及航程代价的不确定信息为依据,采用主观赋值与客观赋值相结合的方法确定指标综合权重,利用区间数表示不确定因素,建立了不确定多因素下多属性任务分配模型,将离散粒子群算法与区间数排序方法相结合,适应了不确定环境下的任务分配问题。任佳[68]提出了一种基于变结构离散动态贝叶斯网络的决策模型,利用贝叶斯推理量化不确定度,得到当前时刻的任务决策。Le[69]将无人机集群动态环境下的非线性任务规划问题转换为差分凸函数规划问题,并利用差分凸函数算法进行求解。Alqahtani[70]针对多无人机侦察任务,利用四叉树表述不确定性,建立基于四叉树和K部图结合的分配架构,能够在通信受限情况下完成任务分配。

结合第1.2.2节多无人机航迹协同技术现状的论述可知,在充分的协同任务分配基础上,任务规划对于无人机集群航迹层面的逻辑协同要求降低。无人机集群任务对航迹规划的核心要求体现为:精确的时间协同与空间冲突消解。精确的时间协同是任务协同分配方案得以实施的关键保障,而冲突消解则是无人机集群安全可靠应用的基础。需要说明的是,高精度的时间协同和空间冲突消解的应用范围不仅限于无人机集群,因此下文的阐述,着重于对两类技术的现状总结。

2.2.1 航迹的高精度时间协同

高精度时间协同条件下的航迹规划演变为有时间约束的路径规划,即4D路径优化问题。相关研究分为离散4D航迹规划和连续4D航迹规划。前者是以一系列离散的航路点来控制航迹形状并为航路点设置到达时间,后者以位置和时间为变量,并采用连续数学表达式表述4D航迹时空关系。

离散4D航迹规划方面,Chaimatanan[71]将航迹规划转换为混合元启发式优化问题,优化航线和设定出发时间,实现了4D航迹设计。Antonio[72]通过对航路点设置时间属性,基于调整飞机速度策略满足时间要求。丁强[73]在Tau-H运动策略基础上,利用PSO算法形成全局航迹预测,随后利用采样间隔与冲突判断双驱动的滚动优化方法,实现航迹不断更新。周青[74]将到达时间偏差引入到A*算法中的估价函数中,不断扩展偏差最小的节点,同时加入速度调整策略进一步缩小时间误差,满足了到达时间要求。整体而言,离散4D航迹规划方法具有直接、简便、规划效率高的优点,但是忽略了航迹点之间速度变化的过渡过程,通常会导致航路规划的灵活性及航线精度降低。

连续4D航迹规划方面,Goerzen[75]运用勾股速端曲线(pythagorean hodograph,PH)进行航迹规划,基于可变参数的矢量场中参数的调整,实现向终点的收敛以达到期望的4D协同。Antonio[76]和Bousson[77]基于3次至5次样条曲线近似的方法,提出了搜索两个连续航点之间最短轨迹的算法,在区域监视的框架下实现了无人机的4D航迹规划。概括地讲,连续4D航迹规划保证了时域的可微性和连续性,能够提供更为光滑的航迹,且提供连续的速度和加速度,但通常航迹的表达式参数较多、形式复杂。

2.2.2 空间冲突消解

无人机集群飞行面临空间冲突,尽管空间冲突的规避不完全由航迹规划克服(控制层面也可发挥重要作用),但全面、有预案的无人机集群航迹规划能够大幅减小空间冲突概率。

在传统的多机航迹规划中,通常采用以安全飞行距离为半径的“管道”来包围航迹,保证多UAV之间不发生碰撞。这一处理思路同样可以应用到空间位置较为松散的无人机集群。无人机间冲突消解流程一般包括冲突的预判/检测和基于规则的规避。在预判/检测方面,可以分为基于几何形状的确定性方法和基于预测的概率性方法两类,判决标准分别对应于有其他物体进入无人机安全保护区或者飞行器间冲突概率超过一定阈值[78-79]。冲突消解的典型策略可以分为基于航线、基于势场、和模型转化等3类,如图5所示。

Fig.5 Partial typical methods of collision avoidance

航线法冲突消解简单、直接,一般可以在时间维度消解,即调整无人机到达冲突位置时间;但在飞行器数量多、航线密集条件下应用受限[80]。势场法中定义无人机目标为引力、空间冲突物为斥力,两者合力作为无人机安全飞行方向,具有含义清晰、易于处理的特点,但应避免陷入局部极值。模型转化类方法较为灵活、应用广泛,将冲突消解问题转化为在线预测控制问题或博弈问题。魏瑞轩[81]提出了基于差分进化(differential evolution,DE)算法和分布式模型预测控制(distributed model dictive control, DMPC)相结合的防碰撞控制策略,将编队问题转化为滚动在线优化问题,将碰撞约束纳入代价函数。Kurik[82]将冲突消解转化为基于一致性编队控制问题。茹常剑[83]提出将无人机碰撞规避问题转化为两方博弈问题,建立了无人机间运动学模型,实现了基于认知博弈制导的防碰撞方法[84]。Senthil[85]在无人机集群协同侦察应用方面,将冲突消解转化为速度空间的速度障碍问题,在保证侦察覆盖范围的条件下实现了无人机间动态避障,其前提是假定无人机能够在很大的范围内安全调整速度。

2.2.3 无人机集群航迹规划的难点

整体来看,当前有时间约束的路径规划以及多机间冲突消解方法的技术现状尚不完全适应于无人机集群。其一,无人机集群数量大、编队密集等约束对连续4D航迹规划的精确度和实时性提出了挑战。其二,无人机集群数量大,以安全距离(区域)为约束的分割会限制集群的密集程度,基于概率的冲突检测处理也面临巨大计算压力。其三,从时间维度看,无人机集群航迹可以存在交叠,当任务类型或协同要求更复杂时,基于局部调整的冲突消解容易引入新的冲突。满足无人机集群应用的航迹规划问题仍需要持续关注和深入研究。

与秉承“自上而下”的思路研究集群技术相对应,“自下而上”思路研究集群技术也逐渐引起研究学者的广泛兴趣,该类技术的突出特点是对无人机集群的数量不敏感,而这一优势是“自上而下”式集群技术所缺乏的。

从生物、数学、计算机、控制、机器人等领域看,集群的出现和研究已经历时很久,对集群的关注重点包括自然界中的鸽群、鱼群、蜂群、狼群等群居动物[86],并不断探索集群现象产生的原因及其衍生的工程应用[87-88]。研究发现,动物集群一般具有临近交互性、群体稳定性、环境适应性。动物行为学表明可以通过个体间简单行为规则的合作产生复杂有序的集体行为。无人机集群技术的另一重要研究思路,即是基于生物集群行为的模仿,逐步向群体决策和认知理论发展,最终实现飞行的智能、决策的智能,以及集群的智能。无人机飞行的智能化是实现无人机决策智能和集群智能的基础,而集群协同智能化的终极目标是无人机集群的完全自主[89]。

Boid模型[90]、Vicsek模型[91-92]以及Couzin模型[93]是描述集群行为最为常见的3种模型。Boid模型于1986年由美国科学家Reynolds提出,基于靠近、对齐和避碰3条规则,假设每只鸟只能观察到其周围固定范围内的个体,就可以在计算机中复现出自然界中鸟类等动物的集群现象、模拟其群体运动。Vicsek模型于1995年由匈牙利物理学家Vicsek及其合作者从统计力学的角度提出,通过改变群体密度以及噪声强度,对集群行为进行定量分析。Conzin模型将个体的感知区域由内而外分为排斥区域、对齐区域和吸引区域,3个区域互不重叠,分别对应群体中分离、速度一致和聚集规则。这3类模型构成了现有集群行为理论研究的重要基石,为后续集群研究提供必要的理论架构、分析工具和方法支撑。近年来Jadbabaie[94], Tanner[95], Olfati-Saber[96]以及Levine[97]也提出了新的群集模型。

共识主动性是生物群体中的一个核心概念:代表生物个体自治的信息协调机制,个体之间间接协调,无需任何集中规划以及直接通信即能完成复杂智能活动。典型的例子是:蚂蚁的大脑或基因中并没有巢穴建造的计划、组织和控制机制,个体间也没有直接的交流,但是蚂蚁个体通过识别其他蚂蚁留下的信息素,达成共识,共同完成了复杂和精致的蚁巢建造[98]。

在集群行为模拟与验证方面,Mataric[99]研制的The Nerd Herd系统被应用在多机器人学习、群体行为、协调与协作等方面。James[100]基于“在多机器人上进行并行算法运算的复杂性度量项目”研制的多移动机器人系统,能够开展大量多机器人行为协调算法设计以及性能预测研究。此外,典型系统还包括Kube[101]研制的 Collective Robotics系统以及Dorigo[102]开发的SWARM-BOTS系统。

实际的无人机集群系统方面,近年来引起广泛关注的包括美国国防部高级研究计划局(Defense Advanced Research Projects Agency, DARPA)支持的“小精灵”项目、美国海军支持的“郊狼(LOCUST)”计划、美国海军参与研制的“山鹑”项目等[103],但这些项目的技术体制和方案细节并未公布。所见报道的其他无人机集群系统包括:匈牙利罗兰大学Vicsek团队于2014年实现10架四旋翼飞机在室外的自主集群飞行[104-105],该项目在任务决策层利用了生物集群行为机制,四旋翼飞机与临近个体之间进行信息交互,实现了在全球定位系统(global positioning system, GPS)噪声、通信延迟环境下的自主决策和稳定飞行,包括区域内碰撞规避、聚集、队形保持和集群目标跟踪。Chung团队在2015年实现了一人控制50架固定翼飞机的集群飞行,无人机按照主从模式飞行,其工作重点是无人机操控权的转移以及无人机自主飞行和决策[106]。

生物群体在去中心化、邻近个体信息交互、整体自组织等方面的特点与无人机集群追求目标一致,因此仿生研究是无人机集群任务规划决策的重要研究方向之一[107-108]。对应地,基于集群智能的无人机集群任务规划的内容包括但不限于威胁的判断、目标优先权的排序、任务的动态分配与调度、飞机航迹的规划与任务载荷的协调等[109],且需要重点考虑多机之间逻辑与行为冲突消解。基于集群智能涌现的无人机集群任务规划的一般过程可以表述为:无人机个体收集并处理外界信息进而更新个体知识以适应环境,再同集群内其他个体交互,完成经验交互和社会学习,实现共同进化,并执行复杂有序的集体行为[110]。而智能涌现在任务规划方面的表征体现在3个层面:单机、群集以及任务,分别对应于无人机单机对环境的学习与适应,无人机集群群集行为的形成,以及无人机集群对复杂多样化任务的完成。

具体进展方面,Su[111]提出一种具有多个变速度虚拟领导者的多智能体蜂拥控制算法,从理论上证明了该方法可以准确跟踪对应的虚拟领导者。周子为[112]分析研究了雁群长途迁徙过程中的编队飞行机制,并设计实现了一种仿雁群行为机制的多无人机紧密编队控制与编队变拓扑重构方法。段海滨[113]提出一种基于注意力机制的群集模型,能够通过刺激单一或者多个个体影响群体快速一致性反应。王训[21]提出基于合作博弈的智能自主聚集策略,以实现群体聚集为“合作目标”,以降低自身消耗为“竞争目标”开展博弈,最终引导群体系统出现聚集行为。段海滨团队[98,114]结合狼群的等级特性与社会组织,建立狼群合作狩猎运动模型,提出一种基于狼群行为机制的自主编队控制方法,设计了基于狼群层级行为机制的编队保持控制器。此外,该团队[115]针对鸟群运动中拓扑交互、策略切换等群集行为机制,映射建立了具有动态环境适应性的无人机集群协调决策控制模型。

除了模拟群体行为建立映射决策模型,研究学者的另一种思路是试图提出通用的自组织集群模型架构,例如美国空军试验室的Nowak面向战场环境中集群任务的动态性、部分可观性提出了基于集群行为激励的通用控制等级模型[116],如图6所示。

Antonio[117]针对分布式目标定位,提出了，群集激励进化(flocking, stigmergy, and evolution, FSE)算法,基于共识主动性用潜在目标吸引无人机,基于聚集特性保证成员间协调观测,基于进化特性来适应动态环境,如图7所示。其他应用场景方面,Wallar[118]基于集群行为建模,设计实现了无人机集群对某敏感危险区域的监视。Howden[119]基于聚集和共识主动性,在无人机局部通信的约束下,实现了无人机集群对森林火场的自主监视。

总的来看,受当前研究水平限制,基于生物集群行为学习与映射的集群任务规划决策更适合于组织较为松散的简单反应型任务,是否能够满足高端无人机在行为更为严格受限条件下的任务执行,还有待深入研究和验证。但这是一个充满挑战与希望的领域,有潜力产生涌现式的集群智能,发挥不可替代的作用,值得持续深入的研究。

3.3 与基于逻辑规则类任务规划的区别

上文分析了基于逻辑规则与集群智能涌现的两类不同的无人机集群任务规划方法,为便于对比,在表2中列出了二者的区别。

表2 两类方法特性对比

Table 2 Characteristic comparison of two different methods

从第2节和第3节的内容看,无人机集群任务规划的方式方法多样,集群任务规划技术的研究既有广泛化、理论化等优势方面,也存在重复化和低端化的不足。以无人机集群实际能力建设为牵引,围绕无人机集群系统的应用前景,梳理无人机集群任务规划技术的发展方向如下。

无人机集群任务规划需要考虑单个无人机的动力学和运动学约束、输入饱和及状态有界约束、模型非线性及不确定性约束,此外还需要满足多无人机到达目的地的时间和空间协同约束,以及数据链系统连通性方面的网络拓扑约束等。基于逻辑与规则的任务规划模型在集群数量剧增的情况下很难以较低的复杂度准确描述多约束条件以及协作机理,迫切需要研究多约束条件下基于集群智能涌现的系统建模和分布式协同控制机理。

在面临时变任务和突发威胁条件下,无人机集群的实时协同规划与决策在当前和未来一段时间内将是集群任务规划的难点。不确定、动态环境下的任务规划机理上依赖于推理判断与优化求解,鉴于深度学习方法在推理的其他应用方面展现出极大优势,将深度学习与分布式优化相结合,在提升无人机集群任务协同分配和航迹规划的实时性和最优性方面具有巨大潜力。

无人机集群航迹规划与调整要能够满足既定分配任务,又要能够自主防碰撞(由控制层面进行的规避技术不在本文阐述范围内),而分布式控制下的无人机集群个体仅同局部临近节点进行信息交换和反馈,要兼顾集群系统的任务使命和智能个体的多约束条件,迫切需要研究局部信息反馈条件下的自组织航迹协同技术,能够应对突发威胁并具备一定的容错和自愈能力。

逻辑规则与集群智能涌现相结合的规划决策模式能够增强无人机集群在通信受限环境下的适应能力,在群间自组织通信正常情况下可采用基于逻辑/规则指派或动态调整任务规划方案,在电磁干扰导致通信受阻,可以结合集群个体间底层协调,保持稳定的队形及功能,增强集群鲁棒性。

作为“先进的任务规划技术能够更好地发挥无人机集群能力”的逆问题,设计满足一定功能的无人机集群系统具有重要现实意义,无论是基于逻辑与规则,还是基于集群智能涌现,均需建立个体能力与集群整体效能的关系模型,形成个体能力与集体状态之间的量化联系。并根据系统的性能指标要求,完成个体设计、结合(改善)个体间驱动与激励模式组织应用,形成实用的无人机集群系统。

对于基于逻辑与规则的无人机集群任务规划,目标函数是评价任务方案优良与否的基石,全面的目标函数能够度量任务方案的最优性,但目标函数复杂度的提升将大幅扩增优化解空间,影响求解效率,甚至无法求解。而基于集群智能涌现的任务规划决策是开放式的架构,缺乏量化的能力评价。迫切需要开展无人机集群任务规划方案的应用效能评估技术[120-121],在无人机集群执行任务前形成规划闭环。

基于逻辑与规则的集群任务规划技术的研究成果丰富,可以直接应用于现有无人机集群系统;对应的研究大多是多无人机系统任务规划技术针对无人机集群系统的拓展和适应性调整,尚不能满足在信息不完全、环境不确定、高动态调整等对抗环境下的集群任务规划要求,以无人机集群为对象的任务规划建模与理论方面缺乏足够创新。此外,基于集群智能涌现的任务规划决策受当前研究水平限制,尚不能灵活、机动、高效、可控地完成复杂性耦合性强的集群任务。无人机集群任务规划技术仍需要持续深入地研究与发展。

一网打尽系列文章，请回复以下关键词查看：
创新发展：习近平 | 创新中国 | 创新创业 | 科技体制改革 | 科技创新政策 | 协同创新 | 科研管理 | 成果转化 | 新科技革命 | 基础研究 | 产学研 | 供给侧
热点专题：军民融合 | 民参军 | 工业4.0 | 商业航天 | 智库 | 国家重点研发计划 | 基金 | 装备采办 | 博士 | 摩尔定律 | 诺贝尔奖 | 国家实验室 | 国防工业 | 十三五 | 创新教育 | 军工百强 | 试验鉴定 | 影响因子 | 双一流 | 净评估
预见未来：预见2016 |预见2020  | 预见2025 | 预见2030  | 预见2035 | 预见2045  | 预见2050
前沿科技：颠覆性技术 | 生物 | 仿生 | 脑科学 | 精准医学 | 基因 |  基因编辑 | 虚拟现实 | 增强现实 | 纳米 | 人工智能 | 机器人 | 3D打印 | 4D打印 | 太赫兹 | 云计算 | 物联网 | 互联网+ | 大数据 | 石墨烯 | 能源 | 电池 | 量子 | 超材料 | 超级计算机 | 卫星 | 北斗 | 智能制造 | 不依赖GPS导航 | 通信 | 5G | MIT技术评论 | 航空发动机 | 可穿戴 | 氮化镓 | 隐身 | 半导体 | 脑机接口 | 传感器
先进武器：中国武器 | 无人机 | 轰炸机 | 预警机 | 运输机 | 直升机 | 战斗机 | 六代机 | 网络武器 | 激光武器 | 电磁炮 | 高超声速武器 | 反无人机 | 防空反导 | 潜航器
未来战争：未来战争 | 抵消战略 | 水下战 | 网络空间战 | 分布式杀伤 | 无人机蜂群 | 太空战 | 反卫星
领先国家：美国 | 俄罗斯 | 英国 | 德国 | 法国 | 日本 | 以色列 | 印度
前沿机构：战略能力办公室 | DARPA | 快响小组 | Gartner | 硅谷 | 谷歌 | 华为 | 阿里 | 俄先期研究基金会 | 军工百强
前沿人物：钱学森 | 马斯克 | 凯文凯利 | 任正非 | 马云 | 奥巴马 | 特朗普
专家专栏：黄志澄 | 许得君 | 施一公 | 王喜文 | 贺飞 | 李萍 | 刘锋 | 王煜全 | 易本胜 | 李德毅 | 游光荣 | 刘亚威 | 赵文银 | 廖孟豪 | 谭铁牛 | 于川信 | 邬贺铨
全文收录：2017文章全收录 | 2016文章全收录 | 2015文章全收录 | 2014文章全收录
其他主题系列陆续整理中，敬请期待……