无人机集群任务分配技术研究综述

毕文豪, 张梦琦, 高 飞, 杨 咪, 张 安

(1. 西北工业大学航空学院, 陕西 西安 710072; 2. 山东交通学院航空学院, 山东 济南 250357)

0 引 言

随着无人机相关技术的突破创新和快速发展,无人机类型越来越多样化,任务领域范围不断拓展,已经逐步实现从安全空域下执行侦察监视等简单任务向对抗空域下突防打击等复杂作战任务的跨越式发展。与此同时,网络化、信息化、体系化的战场环境呈现出高动态、强对抗、巨复杂等特点,单架无人机有限的载荷能力很难独立执行大区域监视、多目标攻击等复杂任务,因此无人机的作战样式正在朝着集群化和智能化方向发展,无人机集群协同作战是未来无人机作战方式的重要发展趋势。

在无人机集群作战中,低成本、大规模的异构无人机平台搭载不同的载荷,通过自组织协同形成规模优势,具有资源配置灵活、战场适应能力强等特点,可满足巨复杂、高动态、强对抗的战场环境下大区域协同侦察监视、协同多目标饱和攻击等任务需求,达到集群对抗的效果,提高无人机集群的作战效能。

无人机集群作战带来的巨大规模优势和作战效能引起了以美国为代表的世界各军事强国对无人机集群作战技术的热切关注,其中无人机集群任务分配技术作为无人机集群作战的关键技术之一,是实现无人机集群化和智能化的重要技术支撑,已成为国防工业部门和各科研机构、研究学者的研究热点。

1 无人机集群任务分配技术研究现状

目前,无人机集群任务分配技术在顶层设计、理论研究、项目论证、关键技术攻关等方面都取得了一定的进展。

1.1 无人机集群协同任务分配理论研究现状

美国国防高级研究计划局、海军研究办公室、麻省理工学院、宾夕法尼亚大学“格拉斯帕”实验室和诺斯罗普·格鲁门公司等研究单位在多无人机任务分配技术的研究方向上开展了大量的研究和论证工作,取得了很多理论成果,并且启动了多个无人机集群项目。2016年5月,美国空军发布的小型无人机系统发展路线图——《2016-2036年小型无人机系统飞行规划》[1]指出:为确保战争的制胜能力与强军事对抗环境下的非对称优势,应重点研究更具成本效益和作战威力的集群式无人机作战样式。同时,详细阐述了“无人机蜂群”的概念,并计划在2036年建成横跨航空、太空、网空三大作战领域的无人机集群作战系统。2018年8月,美国国防部发布的《无人系统综合路线图2017-2042》[2]指出了19项近、远期需要重点发展的面向军事作战需求、能大幅提升无人机集群作战效能的关键技术,包括开放式体系架构、机器学习、人工智能等。美国海军研究生院[3-4]提出了一种面向无人集群作战体系设计的一体化框架,该框架针对未来无人机集群作战的去中心化、自组网、扁平化结构等特点,构建了无人机集群“使命-战术-行动-算法-数据”五层任务框架,并以无人机集群执行情报、监视、侦察和空战任务为例分析了无人机集群在每层中的具体任务,给出了具体的军事概念模型。

2017年7月发布的《新一代人工智能发展规划》中多次提及“群体感知、协同与演化”“群体集成智能”“自主无人系统”等概念,同时明确指出应将人工智能与无人机集群紧密融合,借助人工智能重点突破无人系统相关核心技术,实现无人机集群相关技术的跨越式发展[5]。文献[6]针对无人飞行器集群访问、打击、察打一体化等多样化任务类型的特点和需求,结合无人机集群任务资源调度问题的约束条件与收益函数,分析论述了无人机集群任务调度技术进展和常用的智能优化算法。文献[7]介绍了无人机集群的研究动机和研究方法,分析了无人机集群的蜂群作战、忠诚僚机、组队协作、狼群作战等典型作战模式,并提出了面向复杂作战任务的调度与管理技术、分布式协同控制技术等亟需解决的共性关键技术。文献[8]首先从任务分配和航迹规划两方面对多无人机任务规划技术方法、新的技术难点进行了全面的总结,然后结合群集智能分析了无人机集群任务规划技术的若干发展方向。文献[9]强调协作任务分配是多无人机自主控制的关键技术,分析了多无人机协同任务分配在表征场景和获得高质量解决方案方面的重要性和难点,提出了无人机群中的协作任务分配发展方向。文献[10]通过分析复杂环境下无人集群任务场景及能力需求,论述了复杂环境下无人集群OODA(observation, orentation, decision, action)任务面临的挑战,梳理了无人集群自组织任务规划、无人集群协同控制等关键技术及发展方向。

1.2 无人机集群任务分配问题建模研究现状

国内外研究人员一般利用经典的组合优化问题模型来描述无人机集群协同作战任务分配问题。经典模型主要有:旅行商问题(traveling salesman problem, TSP)模型[11]、网络流优化(network flow optimization, NFO)模型[12]、车辆路由问题(vehicle routing problem, VRP)模型[13]、协同多任务分配问题(cooperative multi-tasks assignment problem, CMTAP)模型[14]、混合整数线性规划(mixed integer linear programming, MILP)模型[15]、基于马尔可夫决策过程(Markov decision process, MDP)模型[16]等。

TSP和VRP模型主要用于求解单一任务的分配问题,而对多任务情况适用性较差;NFO模型较早运用于弹药较少的广域搜索弹药任务分配问题上;MILP模型描述简洁,很容易表示涉及到数值的全局约束,将任务规划问题描述为一个组合优化问题,实用性较强,但计算成本会随问题规模增大而呈指数型增长;而基于NFO和MILP模型提出的CMTAP模型考虑多无人机编队完成探测识别、打击、毁伤评估等一系列时序任务,通过优化完成任务的总时间或者飞行的总距离来实现任务分配,更适用于复杂任务分配问题建模,但可扩展性低;在考虑系统存在不确定因素和多智能体协同系统时,可分别通过部分可观测的MDP(partially observable MDP, POMDP)及多智能体的MDP(multi-agent MDP, MMDP)对协同任务分配问题进行建模,但上述模型均存在通用性较差的缺点。

1.3 无人机集群任务预分配算法研究现状

任务预分配是指在无人机执行作战任务之前,任务规划平台通过雷达探测或卫星探测等手段提前获得战场中目标点的位置与任务类型等信息,依据任务预分配算法计算得到各无人机的任务分配决策信息。针对无人机集群任务预分配问题的特点,要求任务预分配算法能够全面考虑无人机自身约束、环境约束、任务约束等,根据不完全战场信息得到无冲突的完备解与最优解,以最大化执行任务所获得的收益。由于任务预分配算法静态结构的特点,求解相对简单,因此得到了大量研究成果,主要分为集中式求解算法和分布式求解算法两种。

1.3.1 多无人机任务预分配集中式求解算法研究现状

集中式求解算法可以分为最优化方法和启发式方法两类[17]。

最优化方法在问题有解的前提条件下,能够基于简化的假设求解得到问题的最优解,代表性算法包括穷举法、分支定界、整数规划、动态规划等。但随着无人机数量的增加,最优化方法求解任务分配问题的难度、计算时间都急剧增加,而且无法准确描述复杂环境下的大规模任务分配问题,不能模拟出战场环境的随机性和动态性,因此近年来采用最优化方法求解无人机集群任务分配问题的研究逐渐减少。

而启发式方法面对多无人机任务分配非确定性多项式(nondeterministic polynomially, NP)难问题时,并不盲目地寻求最优解,而是通过权衡求解质量和求解时间,在可接受的计算时间内求得近似最优解、次优解或满意解,因此其具有计算复杂度低、性能优越、易于实现等特点,被广泛地应用到任务预分配问题。典型的启发式算法有:遗传算法、禁忌搜索算法、粒子群优化算法、模拟退火算法等。

遗传算法由于使用多点并行搜索,不易陷入全局最优,且能够以编码的方式工作而不对参数本身操作,因此得到了大量研究成果。文献[15]通过添加一个混洗列表来修改交叉运算符,同时引入两个新的运算符,提高了遗传算法求解多无人机集群任务预分配问题时的求解质量。文献[18]为解决多无人机侦察多类型目标时的任务预分配问题,讨论了一种基于对位的双染色体编码遗传算法,引入基于对位的学习和多重变异算子对遗传算法进行改进,得到了较好的求解质量。文献[19]通过建立执行任务的收益、执行任务的时间以及任务负载因素下的任务分配整体效能模型,提出了基于分布估计思想的量子遗传算法,实现了多基地情形下无人机任务初始分配和突发威胁下动态分配。文献[20]提出了一种基于改进遗传算法的元启发式算法,解决了具有复杂无人机运动学约束、资源约束与时间约束的多无人机任务预分配问题。针对多无人机执行具有时序约束的任务预分配问题时可能出现的死锁问题,文献[21]对遗传算法进行了改进,首先通过考虑目标标识符和任务优先级约束生成无死锁个体,并设计特定的交叉和变异算法保证了后代个体的可行性。文献[22]为有效求解时间窗约束下异构多无人机协同打击敌雷达阵地的任务分配问题,提出了一种融合并行计算的多层编码遗传算法,有效提高了求解效率。

粒子群优化算法简单易实现,参数少,并且求解速度较快,在多无人机任务分配领域得到了广泛的应用。文献[23]针对执行攻击任务的多无人机协同任务预分配问题,通过位置饱和策略构造粒子的搜索空间,提出了基于自适应惯性权重的改进粒子群优化算法。文献[24]开发了具有维度级与个体级两个任务分配模块的双级任务分配粒子群变体结构,以平衡探索和开发搜索过程,具有更高的搜索精度,在求解多无人机任务预分配问题时表现出了优异的性能。文献[25]考虑无人机任务预分配问题中的通信和任务性能因素,采用粒子群优化算法在无人机数量有限的情况下得到了满意的预分配解。文献[26]通过建立不同类型的救援模型,提出了基于遗传学习策略的自适应粒子群算法,实现大规模救援场景下多无人机协同救援任务分配。文献[27]针对异构多无人机协同观测侦察、火力打击、毁伤评估任务分配问题,建立了复杂约束条件下的CMTAP模型,提出了基于拐点的多目标粒子群协同任务分配算法。

目前,基于遗传算法和粒子群优化算法解决多无人机任务预分配问题依旧是当前的研究热点,通过改变具体的编码方式或层级结构来提高自身求解性能,具有大量的研究成果,但大部分算法是针对特定的应用背景及约束条件进行改进,无法全面考虑实际多无人机集群任务预分配问题时存在的复杂耦合约束,算法的鲁棒性与可扩展性较低。

除上述典型算法的应用扩展外,为满足任务预分配问题的最优性、不确定性等约束,一些新的算法也被引入到任务分配问题中。如文献[28]针对多无人机对地面目标进行察打时任务时长、时敏目标的不确定性问题,提出了基于多策略优化的灰狼算法。文献[29]面向复杂场景下的任务分配和覆盖搜索问题,提出了融合改进匈牙利算法和Theta*算法的仿生狼群无人机群任务分配方法。文献[30]提出了一种基于蚁群系统的启发式算法,以最小化任务的时间消耗为导向,在协同搜索任务中寻求近似最优解。

1.3.2 多无人机任务预分配分布式求解算法研究现状

随着无人机自主能力的不断提升和无人机集群通信组网技术的快速发展,具有优越的可扩展性和鲁棒性的分布式求解算法逐渐成为任务分配算法研究方向的热点。

分布式求解算法可以进一步分为自顶向下和自下而上两类。其中,自顶向下的分布式求解方法利用分层递阶求解的思路,将复杂任务协同分配问题逐层分解为若干个更简单的子任务分配问题,各无人机通过协商与合作实现问题求解。其代表性方法包括:分布式MDP(decentralized MDP, Dec-MDP)方法、基于市场机制的方法、动态分布式约束优化问题(dynamic distributed constraint optimization problem, DDCOP)方法等。与之相反,自下而上的分布式求解方法通过研究无人机个体的局部感知和动态反应,设计基于反应和行为的协同优化策略,实现多无人机整体自组织任务分配。其中,典型算法有基于群智能的自组织算法(self-organized algorithm, SOA)、阈值响应法、蚁群优化(ant colony optimization, ACO)算法等。

作为典型的自顶向下分布式求解算法,基于市场机制的方法通过激励机制来鼓励各无人机参与任务分配买卖过程,能在较短时间得到任务问题的满意解。文献[31]针对异构多无人机协同打击不同类型目标的协同任务分配问题,提出了基于分布式通信拓扑的拍卖算法,实现了异构多无人机协同任务预分配问题的快速求解。文献[32]考虑异构无人机能力、类型分组等约束,在对偶分解任务分配问题的基础上,提出了融合最大一致性算法的分布式拍卖算法,得到了较高的求解质量。文献[33]首先将任务分解成不相交的子任务组,然后利用分布式拍卖分配算法使每个机器人通过逐步迭代最大化自己的目标函数,从而解决具有任务约束条件的多机器人任务预分配问题。文献[34]在分布式拍卖算法的基础上设计了广播、应用、审查与提供报表、任务分配四个阶段,解决了带有时序约束的无人机集群任务预分配问题。文献[35]在机器人寿命约束的条件下,针对任务持续时间相同与不同两种约束情况,对分布式拍卖的任务分配算法进行扩展,使得多机器人任务预分配解的质量最优。文献[36]基于一致性包算法(consensus-based bundle algorithm, CBBA)按优先级将目标任务归入不同层级,只将分配过高阶段任务的目标添加至相应的任务包和序列中,保证了无人机任务预分配问题的时序约束。针对多无人机作战环境中存在的参数不确定性,文献[37]提出用高斯回归过程模型对任务回报值进行预测,然后采用CBBA进行任务分配,有效解决了不确定环境下的协同无人机任务预分配问题。文献[38]针对侦察型和攻击型异构无人机多智能体系统协同任务分配问题,考虑无人机载荷资源、子任务时序关系等耦合约束,通过改进CBBA的冲突消解规则,提出了基于改进冲突消解的一致性联盟算法,同时保证了求解质量和求解速度,但是未考虑到动态不确定环境约束下的应用。

自下而上的分布式求解算法中,群智能算法能够基于每个同构个体的行动决定总体趋势,具有天然的分布性特点,对问题规模的变化不敏感,因此在协同任务预分配问题上也得到了广泛研究。文献[39]采用分布式搜索攻击任务自组织算法(search attack self organized algorithm, SAMSOA)将多无人机分布式搜索任务预分配全局优化问题分解为可以利用蚁群优化算法快速求解的局部优化问题,然后通过无人机之间的信息交换得到全局最优解。文献[40]针对多无人机协同搜索攻击任务预分配问题,提出一种基于改进分布式蚁群优化算法的智能自组织算法,具有较高的求解质量。文献[41]针对集群机器人任务预分配中通信负载较小、任务复杂耦合的问题,通过合理选取阈值和激励值,提出了具有较高求解质量的阈值响应法。文献[42]提出了基于阈值的分布式多无人机任务预分配方法,分别在充分利用无人机资源、选择更合适的任务和负载平衡3个方面进行了扩展,具有较高的任务预分配求解质量。文献[43]考虑环境中的自然不确定性,提出了概率决策机制下基于响应阈值模型的分布式方法,有效实现了异构机器人在有限资源下的任务预分配。文献[44]针对无人机集群任务分配过程中的连续性和动态性,将灰狼交互机制和合作捕食行为映射到无人机集群任务分配,提出了仿灰狼合作捕食行为任务分配算法。

集中式算法和分布式算法对比分析如表1所示。

表1 集中式算法和分布式算法对比分析Table 1 Comparative analysis of centralized algorithm and distributed algorithm

除上述典型算法的应用扩展外,为满足任务预分配问题的最优性要求和复杂约束条件,一些新的算法也被引入到任务分配问题中。如文献[45]针对多种复杂约束,引入自适应搜索策略、重置Harmonic平均距离循环策略和全局最优引导邻域搜索策略等策略改进多目标自适应快速人工蜂群算法,并通过定义自主决策准则引导多目标任务分配的方案选取。文献[46]面向异构多无人机执行防空压制任务中的任务分配问题,通过图论建立了基于路径约束的协同任务分配模型,并采用分布式遗传算法进行求解,具有较好的求解速度。文献[47]给出了一种基于交叉熵(cross entropy, CE)的任务预分配方法,解决了具有资源类型约束与任务类型约束的多类型无人机任务预分配问题。文献[48]针对环境不确定性条件下异构无人机的任务分配问题,通过优先经验回放和神经网络近似,提出了基于强化Q学习的快速任务分配算法。文献[49]通过设计多无人机智能体高回报获取、利益分配、联盟稳定性保证和搜索加速的历史任务机制,提出了一种用于多无人机协同任务分配的稳定性量子粒子群优化算法。文献[50]针对无人机在灾难应急处置中执行的搜索、紧急医疗运送、救援运送和通信中继4种任务分配问题,提出了一种近似两阶段方法。文献[51]将纳什均衡的概念应用于任务分配问题,使用贪婪策略搜索有效的纳什均衡解,提出了具有预算约束的任务分配问题的博弈算法。

上述算法在针对小规模多无人机任务预分配问题时可以获得较好的求解质量,并已有许多学者针对特定约束对算法进行扩展,但随着异构无人机类型的逐渐增加,无人机集群规模不断扩大,约束条件复杂耦合,上述算法的求解效率较低,求解质量也直线下降。

1.4 无人机集群任务重分配算法研究现状

随着战场对抗不断升级,无人机集群在任务执行过程中遇到突发事件时,任务重分配算法需要通过各无人机平台之间的信息交互对战场态势和动态任务快速做出反应,在有限时间内完成任务的重构与优化,并达成无冲突的任务重分配方案[52]。

基于市场机制的任务重分配算法具有简单易实现、灵活性较好、可扩展性强的优点,因此被广泛应用到无人机集群任务重分配,并且结合具体的无人机集群任务重分配场景,对求解性能、约束满足、冲突消解等方面进行扩展,提出了众多改进算法。文献[53]提出了一种基于分布式拍卖算法的博弈理论非协调决策框架,并证明其在异步网络环境下求解大规模无人机任务重分配问题时具有较好的收敛性。文献[54]中每架无人机在执行任务时估计所有其他无人机的位置,并在此基础上用简单的分布式拍卖方案实现了无冲突的任务重分配,得到了较满意的解。文献[55]为更好地利用有限资源,采用基于分布式拍卖的方法解决了多机器人动态任务重分配问题。文献[56]讨论了一种满足任务执行时长约束与机器人寿命约束的分布式拍卖算法,解决了具有任务执行时间约束的多机器人动态任务重分配问题。为处理战场环境中的通信约束,文献[57]针对有限通信距离的场景,提出了一种基于改进市场机制的分布式任务重分配算法。文献[58]在其基础上针对时变网络拓扑的情况进行了改进,提高了任务重分配算法的实用性。

上述基于市场机制的分布式任务重分配算法都面向于多个无人机协同执行任务的情况,适用规模较小,在求解大规模无人机集群协同作战时求解性能不足,因此有学者延续市场机制的思想,提出了联盟组任务重分配算法。文献[59]针对突发任务的实时分配问题,提出了基于时间窗的两阶段任务联盟组任务重分配算法,提升了大规模无人机集群任务重分配的实时性。文献[60]针对大规模无人机集群通信链路部分可靠下的任务重分配问题,提出了不确定条件下部分信息可靠的无人机任务重分配一致协调算法,使算法收敛于确定性的目标函数。文献[61]为同时将多个任务均衡地分给各异构无人机团队,提出基于市场机制的多紧耦合多无人机任务联盟重分配算法,得到较好的求解质量。文献[62]将CBBA扩展以处理具有附加需求和任务依赖性的多无人机复杂动态任务重分配问题,并通过新的数据结构降低了各无人机之间的通信成本,使算法收敛到一个无冲突的可行解。文献[63]利用贝叶斯理论定量化描述任务空间的不确定量,并采用CBBA算法实现不确定环境下多无人机的协同多任务快速重分配。文献[64]提出了改进的CBBA,并建立了基于一致性协调理论的冲突消解规则,利用在线协同策略在有限时间内得到多异构无人机任务重分配问题的较优解。

除了经典的基于市场机制的分布式任务分配算法之外,相关学者也针对动态环境中任务重分配问题的特点提出了许多新的算法,并证明有较好的求解效率与求解质量。如文献[65]设计了新的动态环境激励、响应阈值和转移概率,提出了具有对动态环境实时响应能力的动态蚁群分工模型,有效提高了多无人机任务重分配问题的求解效率。文献[66]讨论了一种改进双组分狼群搜索算法与经典内点法结合的在线分层规划方法,解决了具有参数与时间敏感的不确定性的多无人机任务重分配问题。文献[67]提出了基于令牌协议的群体智能策略与广义分配方法,能够随着无人机数量的变化和新目标的出现实时完成动态任务重分配。文献[68]针对多智能体协同围捕问题,建立了追逃微分博弈模型,采用自适应动态规划方法,为各个智能体规划围捕目标及运动轨迹。文献[69]提出了一种基于资源福利的分布式任务分配方案,通过使无人机编队平衡资源消耗,以保留更多可用无人机来平稳地响应动态事件,提高多无人机对动态事件的响应能力。文献[70]为最大化提升无人机编队对多个时敏目标的作战效能,提出了时敏目标时间窗口约束下的多无人机动态任务重分配算法。文献[71]针对平台失效和新增任务两种突发事件下的任务重分配问题,考虑任务完成精度、任务顺序等约束条件,提出了基于可执行任务序列和贪婪策略的任务重分配算法。文献[72]提出了分布式深度压缩算法和分布式快速压缩算法两种多无人机在线任务分配算法,较好地解决了具有时间窗口约束的异构多无人机任务重分配问题。文献[73]设计了通信延迟、丢包等约束下带比较阈值的冲突任务预测与消解机制,提出了基于改进分布式转运指派算法的多无人机任务重分配方法。文献[74]采用了一种基于免疫多智能体网络框架的分布式免疫多无人机任务重分配算法,得到了较好的求解速度。文献[75]在随机、动态环境下,将任务分配问题表述为动态匹配问题,并提出了一种基于多等待列表的任务分配(multiple-waitlist based task assignment, MWTA)算法来寻找时间变化环境下的稳定匹配,证明了MWTA可以实现包含策略保护、效率和无嫉妒性的动态稳定性。文献[76]针对异构无人机集群执行区域察打任务过程发现新目标时的局部任务重分配问题,利用信息一致性算法设计了通信约束下异构多无人机联盟构建方法,提出了基于改进分布式合同网的多无人机任务重分配方法。文献[77]针对无人机辅助物联网中的动态任务分配,通过基于多种群的遗传算法以及结合动态规划和改进的K-means聚类的混合算法来解决联合任务分配和无人机轨迹优化问题。文献[78]针对无人机多智能体系统攻击任务场景中突发故障情况下的任务重分配问题,考虑任务时效性和同步性等约束,提出了基于势博弈理论的任务重分配算法。

1.5 无人机集群与其他无人系统联合应用下任务分配研究现状

随着智能自主技术、体系作战的快速发展,无人机、无人车、四足机器人、无人水面艇、无人水下航行器等无人系统逐步成为能改变未来战争形态和作战样式的关键性武器装备。无人系统的联合应用也向“协同、群智”的趋势发展,已受到广泛关注。

解放军报2019年10月发表《加速推进军事智能化》文章,将智能集群作战协同技术列为智能化战争的基石;“智领群蜂”国际无人蜂群技术大赛力求通过无人机、无人车联合协同,验证空中快速避障集结、协同搜索任务等群集智能多任务分配策略。文献[79]提出了基于异构强弱、规模大小的异构无人系统分类依据,介绍了异构无人系统协同的内涵和作战想定,论述了异构无人系统协同作战中涉及的协同架构、协同任务规划等关键技术。文献[80]面向由无人车和无人机组成的空地异构无人系统协同执行巡逻任务,提出了融合遗传算法的改进蚁群优化算法。文献[81]针对多无人机与无人车协同进行多目标、大区域范围的察打一体化任务分配问题,利用密度最大值聚类方法进行子任务区域划分,提出了基于混合遗传算法和粒子群优化算法的空地异构无人系统协同任务分配方法。文献[82]针对最后一英里配送中无人机与地面车辆联合作业任务分配问题,以最小化包括运输成本和等待惩罚在内的总运营成本为目标,提出了基于MILP和贪婪随机自适应搜索的联合配送任务分配算法。文献[83]面向多无人机与运输车联合进行“最后一公里”的货物配送任务分配问题,提出了区块链式拍卖算法。文献[84]以“多无人机-无人水面艇”联合进行海洋大数据收集为背景,提出了基于K-means聚类算法的分组任务分配方法。文献[85]针对多无人机-多无人车协同任务分配问题,建立了单任务智能体-多智能体任务下的双层任务分配模型,提出了基于图神经网络架构和MILP的多机器人静态任务分配方法。

2 无人机集群任务分配技术面临的问题

随着无人机集群相关技术的迅猛发展,无人机集群在平台异构性上从单一的同构平台发展到复杂多任务下多异构平台,在成员规模上从传统多机编队的数架无人机扩展到几十架甚至是成百上千架的无人机集群。同时,伴随着无人机集群作战样式的转变,无人机集群的作战任务类型更加复杂,从仅可执行安全空域下侦察监视等简单任务拓展到执行对抗空域下突防打击等复杂作战任务,研究方向由简单任务的预分配技术转变为复杂多任务的预分配和动态环境下实时重分配,大规模无人机集群任务分配技术在模型建立、算法求解、任务分配实时性等研究方向的一些问题也暴露出来。

2.1 无人机集群任务分配建模的架构问题

在异构无人机集群任务分配模型的架构设计上,许多研究人员只是在经典多无人机协同任务分配模型的基础上面向特定的异构无人机任务需求与约束条件进行改进,没有提出无人机集群任务分配建模的架构理论,没有依据多任务适应性综合考虑真实战场环境中的各种约束及优化目标。如战场中的不确定性、平台异构性、通信约束、任务的时序约束、资源约束等,只面向某些特定约束条件与应用场景下的任务分配问题,建立模型不能够面向不同作战环境和作战任务,对无人机集群任务分配的规模扩展性不足。

因此,如何立足于动态多变、高度不确定性的真实战场环境,在考虑多种无人机类型、通信约束、不同任务需求目标、多种约束相互耦合的情况下“向实战聚焦”,探究更符合真实战场的异构无人机集群任务分配架构,是大规模异构无人机集群任务分配的一个严峻问题,也是异构无人机集群任务分配算法能否真正应用于实战的一大挑战。

2.2 面向多任务的无人机集群任务预分配算法最优解求解问题

当前的大部分无人机集群任务预分配算法求解都是面向中小型规模的同构无人机集群,无法对大规模异构无人机集群任务分配问题的多约束因素进行有效解耦,且不能高效处理有优先级差别的任务,求解复杂度随无人机集群的规模呈几何级数增长,甚至导致出现无法求解的情况。

随着无人机集群任务预分配的研究对象从小规模的同构无人机转向大规模的异构多平台无人机,研究方向由确定信息下的简单任务预分配转变为不完全信息下的复杂多任务预分配,任务预分配所涵盖的范围和规模不断扩大,主要表现为:约束条件繁多且耦合程度高,强对抗战场环境导致指标因素具有强不确定性,机载传感器、武器载荷等任务要素复杂,任务预分配结果需符合作战意图等。这些都对任务分配算法求解提出了新的挑战。

因此,如何对集群任务中的时间、资源、空间约束信息进行有效的表示和推理;为最大化提升异构无人机集群的作战效能,如何尽可能求解得到异构无人机集群任务预分配的最优解等都是需要深入考虑的问题。

2.3 有限时间下面向突发事件的无人机集群任务重分配算法寻优问题

与无人机集群任务预分配相比,无人机集群任务重分配既要克服战场态势信息的动态性所带来的负面影响,又需要在资源和时间都有限的条件下得到合理可行的分配结果。

目前,大多数无人机集群任务重分配只是将突发事件作为任务重分配问题的一种约束,不能合理区分不同突发事件对原有任务分配方案带来的不同影响,对突发事件的处理能力较低;而且随着问题复杂度的增加,求解效率直线下降,算法的收敛速度不能满足动态环境下的实时性要求。在实际作战中,由于任务环境的不确定性、情报信息的误差,以及高度对抗环境中不断变化的战场态势,要求异构无人机集群任务重分配方法能够面向突发事件克服信息的动态性和不确定性,在有限时间下快速给出较优解。

因此,面对动态对抗环境下的突发事件,如何对冲突任务进行消解与优化,以及如何利用高性能的重分配算法在局部最优和全局最优间进行合理有效的折中,以便在有限时间下获得无人机集群任务重分配的较优解,是无人机集群任务重分配研究中的关键问题。

2.4 路径规划紧耦合下面向大规模异构无人系统的协同任务分配问题

当前的大部分任务分配算法都将任务分配与路径规划分离,以松耦合的方式先求解任务分配,再对单平台进行路径规划,忽略实际路径对分配任务执行的影响。而多变任务类型和复杂动态环境下大规模异构无人集群协同任务分配不仅要在整体宏观层上进行异构无人集群内各智能体的任务分配,而且要在个体动力学层上为每个智能体设计路径轨迹,实现路径规划耦合下的任务分配,使得大规模异构无人集群作战效能近似最优。

与此同时,国内外在针对不同应用场景下的较小规模异构无人系统协同任务优化分配算法已取得较为扎实的研究成果。然而,面向大规模异构无人系统协同任务分配问题时,随着规模的迅速增长和异构性的增强,已有的方法大多适用性不足;其次,异构无人系统协同任务分配需要依靠集群通信组网获取信息,时延、拓扑时变、丢包、误码等通信约束大幅增加了大规模异构无人系统协同任务分配的难度。

如何在路径规划紧耦合下考量异构耦合涌现效应,更高效、合理地实现异构无人系统的协同任务分配,是未来大规模异构无人系统协同任务分配的关键问题。

3 无人机集群任务分配技术的发展方向

3.1 基于模型的系统工程的无人机集群任务分配的通用化建模理论

近年来,基于模型的系统工程在复杂系统和航空航天领域各个领域的兴起[86-87],通过对模型的系统工程中元模型的研究可大大降低系统建模的复杂度,为复杂系统的建模提供一个公共和一致的标准。文献[88]为解决C4ISR(command,control,communication,computer,intelligence,surveillance,reconnaissance)系统中对武器装备体系认知的不确定性问题,提出统一采用元模型对环境、能力、用户、作战、资源、管理和公共7类数据进行描述,实现C4ISR系统的互联互通互操作性。文献[89]针对C4ISR系统中抽象层次高的能力需求建模复杂问题,构建了面向C4ISR系统建模的能力元模型,有力地支持了后续应用层模型的构建与开发。文献[90]为评估指挥与控制体系结构对动态变化环境的适应能力及完成任务的能力,建立了包含资源元模型、任务元模型和控制元模型的体系任务分解模型,为后续指挥与控制体系结构评估模型的构建提供了建模基础和标准。

无人机集群任务分配的数学描述模型可概括性地表述为:异构无人机平台(Who)在特定位置(Where)上,为完成某种集群任务而按照一定的约束条件/作战规则(Why)执行自身分配到的任务(How)并产生与消耗作战资源(What),即无人机集群任务分配“4W1H”关系,如图1所示。

图1 无人机集群任务分配“4W1H”关系图Fig.1 “4W1H” relational graph of unmanned aerial vechtle swarm task allocation

因此,在建模理论方向,迫切需要分析动态多变、高度不确定性的战场环境下无人机集群作战的使命任务、作战样式和作战流程,综合考虑平台异构性、通信约束、任务的时序约束、资源约束等约束条件,研究利用基于模型的系统工程方法建立不确定环境下无人机集群任务分配的单任务、任务需求、约束条件、能力和无人机平台等元模型,构建面向复杂多任务的、具有通用性和可扩展性的无人机集群任务分配建模理论。

3.2 不完全信息下面向多任务的基于生成对抗网络的无人机集群任务预分配技术

近几年来人工智能和深度学习理论迅速发展,引起各个领域的广泛关注[91-94],其在军事领域应用的研究如火如荼。尤其是深度学习中的生成对抗网络(generative adversarial networks, GANs),作为一种深度学习网络结构由Goodfellow提出后,满足了许多领域的研究和应用需求[95-97]。在网络结构方面,GANs采用的神经网络结构不限制生成数据的维度,大幅拓展了生成模型生成数据样本的能力范围;在建模能力方面,GANs能够逼近任意函数,应用范围广泛。GANs以其在处理复杂数据信息时的优越性,能为求解具有复杂约束关系的异构无人机集群任务预分配最优解的提供新的研究思路和解决途径。基于GANs的无人集群任务预分配网络框架如图2所示。

图2 基于GANs的无人集群任务预分配网络框架Fig.2 Task pre-allocation network framework of unmanned aerial vehcile swarm based on GANs

将深度学习理论与无人机集群任务预分配技术交叉融合,并在不完全信息下利用GANs针对不同任务需求高效地求解面向多任务的异构无人机集群任务预分配的最优解将是无人机集群任务分配研究中的热点方向。

3.3 有限时间下面向突发事件的基于性能影响算法的无人机集群任务重分配技术

启发式的性能影响算法在2016年被首次提出[98],该算法是一种源于CBBA的完全分布式启发式算法,其使用性能影响的新概念对任务包进行评分和组织,在可进行局部通信的无人机上并行迭代运行任务包含阶段、协商一致和任务删除阶段两个部分来系统地交换任务,使用特定的度量标准来度量所有任务,逐步构建和更新这些代理的任务。性能影响算法结构具有较高的可扩展性和鲁棒性,其采用的并行局部通信方式适合于未来高动态对抗、高通信约束的战场环境,已被证明其在求解具有时敏的任务动态重分配问题时具有较好的表现,而且目前对基本性能影响算法的改进也已经取得了较多的成果。文献[99]针对基本性能影响算法中可能存在的局部最优和不能处理突发任务的缺点,首先对算法进行了扩展,使其允许实时动态在线重规划,然后通过引入一个额外的soft-max操作来提高算法的探索性,并在文献[100]中提出利用性能影响Max Ass算法为未分配任务创造可行的时间段,实现任务分配数量的最大化。文献[101]为满足在线重规划时严格的时间窗约束和最大资源利用率的约束,在基本性能影响算法的基础上提出一种任务交换分配算法,为未分配的任务创建可行空间。文献[102]对任务纳入和冲突解决的标准进行了修改,以总效益最大化而不是最终分配方案的平均等待时间最小化作为全局目标,提出了带有关键任务的扩展性能影响算法(extended performance impact algorithm for critical tasks, EPIAC),并设计了一个新的任务列表调整阶段以分配关键任务。文献[103]针对分布式多无人机在动态环境中的任务重分配问题,建立了根据动态事件的类型确定处理策略的分布式框架,设计了子团队形成机制和部分释放机制,并基于此提出了部分重分配算法,能够以较少的数据交换和运行时间获得无冲突的任务重分配方案。

有限时间下基于改进性能影响算法的无人机集群任务重分配框架如图3所示。

图3 有限时间下基于改进性能影响算法的无人机 集群任务重分配框架Fig.3 Task reallocation framework of unmanned aerial vechile swarm based on improved performance impact algorithm in limited time

针对无人机集群任务重分配应对动态对抗环境下多种突发事件的实时性需求,研究如何对冲突任务进行消解与优化,为后续无人机集群任务重分配算法求解降低求解复杂度;如何基于改进性能影响算法在有限时间下获得无人机集群任务重分配的较优解,提高异构无人机集群战术灵活性,将成为解决日益复杂的无人机集群任务重分配问题的重要途径。

3.4 群集智能下大规模异构无人系统协同任务分配技术

(1) 大规模异构无人系统拓扑网络设计与优化

拓扑网络设计与优化是异构无人系统协同任务分配的关键支撑技术。虽然集中式、分层式、分布式拓扑网络已被提出,但相关研究未涉及大规模异构无人系统,也未与实际应用中“自组织性、异构性、对抗性”等特征相结合。

设计合理、高效、稳健、可重构的协同控制拓扑网络,使得异构无人系统可以在复杂对抗战场环境中保持通信链路稳定,实时感知态势信息和实时评估结果,并以此为基础动态调整任务分配方案,增强异构无人系统在通信受限环境下的适应能力,提升系统的鲁棒性。

(2) 精确时空协同下路径规划技术

由于无人平台异构,其移动速度、机动能力、载荷、可达区域等不尽相同,而且任务存在逻辑、时序以及时间窗约束,传统的任务分配方法难以满足现实需求。

为适应大规模异构无人系统任务分配问题的不断发展和变化,任务分配方法呈现多层次、强耦合的特点,各层通过相互耦合在不同的细节粒度上进行求解,高层主要面向任务分配共性问题的研究,底层与异构无人平台的性能特点及作战样式结合,强调多重威胁、多源干扰下的路径轨迹精确规划与控制,对异构无人平台协同路径规划提出新的要求——精确的时间协同与空间冲突消解。其中,精确的时间协同是可靠地实施任务分配方案的基础,空间冲突消解是大规模异构无人系统安全地执行任务分配方案的重要保障。

(3) 复杂环境下基于群集智能的大规模异构无人系统协同任务分配技术

相比于同构无人系统任务分配,大规模异构无人系统协同任务分配的任务规模大、类型多,协同关系复杂并存在组合约束,涌现性复杂,通信拓扑网络多变,任务分配呈现出不确定性、随机性、涌现性。传统的任务分配方法不再适用于大规模异构无人系统,因此亟需提出满足大规模协同任务分配需求的高效求解方法。

基于群集智能的大规模异构无人系统协同任务分配可以表述为:各个异构无人平台在复杂环境下动态感知外界态势信息,从而更新个体知识以适应复杂环境,再与系统内其他异构无人平台交互,完成自适应学习与进化,最终执行复杂有序的群集行为(即协同任务分配)。智能涌现在协同任务分配上的表征为单异构无人平台、异构无人系统和任务3个层面,分别对应于单异构无人平台对环境的学习、无异构无人系统群集智能行为的进化以及无人机集群对复杂多样化任务的分配。

利用深度学习构建异构无人系统分布式学习及训练环境,通过大数据挖掘提取协同任务分配训练样本数据特征,研究复杂环境下基于群集智能的大规模异构无人系统协同任务分配技术,使得大规模异构无人系统具备在线学习与自主决策能力,提升复杂环境下大规模异构无人系统协同任务分配的自主性与灵活性。

4 结 论

本文从无人机集群作战理论、无人机集群任务分配问题建模、无人机集群任务与分配算法和无人机集群任务重分配算法、异构无人系统联合应用下任务分配等方面对相关研究现状进行了总结,指出了无人机集群任务分配技术目前面临的无人机集群任务分配元模型的通用化建模理论、不完全信息下面向多任务的无人机集群任务预分配最优解求解、有限时间下面向突发事件的无人机集群任务重分配寻优、路径规划紧耦合下面向大规模异构无人系统的协同任务分配等关键问题。在此基础上,突破传统方法的不足和局限,探索无人机集群任务分配新理论和新技术发展方向,为增强无人机集群任务分配对不确定战场环境的适应性、提升无人机集群的任务预分配和重分配的求解质量和求解速度提供新的研究思路和解决途径,促进无人机集群任务分配技术由目前的先进“跟跑者”逐渐迈向国际领先水平的“领跑者”,具有重要的社会和国防意义。