中国指挥与控制学会会刊 
无人机在速度、机动性和隐蔽性方面有优势,目前已经被广泛应用于区域侦察、环境监测等领域。随着任务环境的日趋复杂,单无人机由于所携带载荷单一导致作业能力有限,已不能满足用户需求。无人机集群由于相互协作提高了整体的系统效能,系统整体涌现出的能力远超内部单体的能力之和,因此无人机集群的研究逐渐受到关注。无人机研究从单机研究过渡到集群研究,集群任务范畴也从单一任务向多任务协同发展[1⇓⇓⇓-5]。
目前,无人机集群协同搜索领域的研究方法分为2类:第一类基于传统的不可生成规则的搜索方法,其中包括传统的基于精确数学建模方法和基于启发式算法的搜索方法;第二类是可生成新规则的搜索方法,主要包括基于演化学习的搜索方法和强化学习的搜索方法。传统的集群协同搜索方法中基于精确数学建模的方法主要以回字形或者并行扫略的方法进行搜索,如何进行合理的区域划分是研究重点。基于启发式算法的集群协同搜索通过对无人机参数、目标搜索概率图等进行建模和更新并将无人机类比于启发式算法中粒子和基因以探索更多解空间来找到更适合的搜索方案,该类型搜索算法是当前研究热点。这种搜索方法需依附于启发式算法架构本身才能表现出足够的智能性且不能生成新的搜索规则。基于演化理论以及强化学习的集群协同搜索方法能够在与环境以及自身的不断交互中产生最优规则,属于可生成规则的协同搜索算法。基于演化理论的协同搜索算法设计思想是通过设计集群单体间局部行为规则而后通过行为演化而产生群体行为,通过这个过程可以产生多种搜索行为,行为的智能度更高。基于强化学习的集群协同搜索方法中,集群通过个体不断和其他个体以及环境进行交互,达到最佳回报值或者设定目标,具备良好的自学习和在线学习能力,可以快速而准确地获取环境信息从而降低环境的不确定度,较好地适应未知复杂环境。
本文将对集群协同搜索方法中不可生成新规则的传统搜索算法以及可生成规则的基于演化理论以及强化学习的协同搜索算法研究现状和进展进行分析并对其优缺点进行对比,同时提出无人机集群协同搜索算法未来发展方向。作者将集群协同搜索方案发展分为三个阶段:第一阶段,区域划分式搜索阶段;第二阶段,生物启发式搜索阶段;第三阶段,涌现式搜索阶段,如图1 所示。
1 基于任务区域划分的集群协同搜索
传统集群协同搜索方法,合理的区域划分是研究重点,该方法考虑单无人机的飞行能力、区域轮廓凸凹性等因素对任务区域进行合理划分来满足无人机在各自区域的任务分配要求,以此来实现任务区域的搜索。
目前使用比较多的区域划分方法是栅格均分法和基于Voronoi图划分法,如图2 和图3 所示。
文献[6]针对一个凸多边形任务区域,设计将任务区域包含在最小边界矩形内,根据无人机的飞行时长和速度等信息对矩形进行了等面积栅格划分作为单无人机的任务分配。文献[7]中作者设计了对有界区域构造Voronoi图的区域划分算法,将多无人机对任务区域的协同搜索问题转换为单无人机在给定区域下搜索航迹规划问题,降低了问题难度。针对任务区域的不规则外形,文献[8]提出通过包络、划分、补全等方法进行规整化,降低了区域划分难度,同时文中针对不同类型的目标设计了相应的协同搜索方式,提高了协同搜索的效率。文献[9]假设多无人机对任务区域搜索从任务区域单侧边进入并设计了等面积单侧区域分割方法,解决了多无人机的搜索区域分配问题。为防止机器人集群在大范围区域搜索中迷失,文献[10]提出了模拟群居生物觅食行为的协同搜索算法,该算法首先将整个搜索区域划分为若干子区域进行分别搜索,利用信号强度-距离关系同时借鉴蝗蜂群阈值响应模型建立了区域效用函数,确定了子区域的搜索顺序,实现了多无人机搜索区域划分和搜索次序分配。考虑到现实中地形起伏对集群传感器成像质量的影响,文献[11]基于无人机飞行高度和采集数据质量间的关系,提出一个基于最小和最大检测宽度作为目标函数的数字地图模型并结合无人机初始位置和飞行时长对任务区域进行分割,实现了任务区域的有效划分。针对凹多边形任务区域难以划分的问题,文献[12]利用凹点凸分解的方法将其转换为凸多边形,并提出了根据无人机来向进行均衡区域划分的方法。
传统协同搜索方法中,对任务区域进行划分后无人机按子区域逐一分配搜索的方法相对比较简单,但这种方法存在无人机协同不足的问题。为改善这一问题,研究人员在对任务区域进行区域划分后对每个子区域的目标存在概率和搜索信息素地图进行建模,利用无人机运动过程中信息的滚动更新决策达到协同区域搜索的目的。文献[13-14]将未知领域侦察和目标搜索任务转换为区域划分问题和搜索分配问题,并建立了基于中心Voronoi图的多无人机区域覆盖模型解决了多无人机任务分配问题,同时考虑到无人机携带传感器探测能力以及通信范围有限,提出了基于概率地图信息更新融合机制的多无人机协同搜索策略。为最短时间内降低环境的不确定性,文献[15]提出基于Voronoi图质心的集群协同搜索方法,该算法建立了离散联合区域划分和搜索策略,不断更新环境信息来驱动Voronoi图划分和无人机的运动,从而提升搜索效率,该算法能够保证协同区域搜索鲁棒性并尽快降低任务区域的不确定性。文献[16]提出基于分布式模型预测的滚动更新决策方法,建立了无人机模型、搜索信息地图模型,在无人机集群协同搜索过程中环境和目标的状态随着搜索进程而改变,在此基础之上滚动更新决策方法从而实现协同目标搜索。文献[17]提出以信息素为决策机制的无人机集群协同搜索方法,将协同搜索分为搜索和决策两阶段,搜索阶段无人机各自移动并实现本机环境信息素更新,并通过相互通信进行信息素融合,利用信息素地图进行决策引导无人机位置更新,该算法效率高、抗毁性强。
上述方法主要是基于区域几何划分的方法进行无人机集群的搜索任务分配或者将任务区域栅格化后利用无人机运动和环境与目标的信息交互进行滚动更新达到协同搜索的目的,这类方法优点是计算任务量小,但集群中无人机智能化有限且搜索方式相对固定,不太适合复杂任务环境。因此,研究人员需要研究更能适应实际复杂环境和任务需求的高智能化的协同搜索方法,使得无人机集群在搜索过程中可以根据实际情况自主进行信息交流和协同操作,以便更灵活、更安全高效地执行协同搜索任务。
2 基于生物启发式算法的集群协同搜索
启发式算法是基于自然界中生物群体通过单体间交互合作而达到“群愚生智”的结果而提出,一经出现便成为研究热点。由于生物群体智能行为有着去中心化、交互合作和整体自组织的特点,与无人机集群协同搜索的局部性、分布式和鲁棒性等要求有很高的契合度。因此,基于启发式算法的无人机集群协同搜索成为当前多智能体领域研究热点[18]。
2.1 构造多粒子的集群协同搜索
基于构造多粒子的集群协同搜索算法是将协同搜索过程类比粒子群等启发式算法的群交互过程,无人机类比于群生物启发式算法中的粒子,并进一步考虑粒子间相对位置、局部通信、避障等约束条件,同时结合无人机等多智能体自身的运动特性实现速度和位置的更新,达到协同搜索的目的[19],如图4 所示。
无人机承载能力有限,只能实现有限感知、局部通信及有限计算能力,对此文献[20]提出基于扩展粒子群优化的协同搜索算法,该算法将无人机集群协同搜索类比粒子群算法的多粒子交叉变异而后根据环境适应度择优过程,并综合考虑有限感知、有限视野和局部通信等限制条件,从而实现协同细化搜索。考虑到无人机集群协同搜索存在的最大飞行距离、最小安全避障距离以及最小侦察时间等约束,文献[21]将集群协同搜索问题转化为对侦察收益、能量消耗以及飞行距离的多目标优化问题,并提出了基于非支配排序遗传算法Ⅱ改进型(Improved Non-dominated sorted genetic algorithm-Ⅱ, INSGA-Ⅱ)启发式协同搜索算法开展对任务区域的协同搜索,该算法相比较于传统的基于NSGA-Ⅱ的集群协同区域搜索方法具有更高的侦察收益和更低能耗。文献[22]提出了一种将全局侦察收益作为目标函数的协同和声集群协同区域搜索算法,该算法将无人机比作算法中的基因片段,并通过交叉、变异操作对基因片段进行更新,提高了算法的自适应性,实验结果表明所提算法相比于传统集群协同搜索算法搜索效率更高。针对无人机集群电量、航程等可用资源有限问题,文献[23]提出了基于改进的前推插入启发式集群协同搜索算法,实现了在满足所有环境约束条件下的最大效费比协同搜索。文献[24]构建了集群自组织搜索策略,首先建立了环境模型以及无人机动力学模型,其次构建了任务区域目标存在概率模型、信息不确定度模型及其更新机制,采用基于改进遗传算法的滚动优化方法决策无人机的运动方向,该算法相比于随机搜索不仅满足了区域搜索协同性的需求也同时降低了计算难度。
针对无先验信息的未知环境协同搜索问题,文献[25]提出了集群分布式预测控制模型,并将预测周期内最大覆盖率设为奖励函数,采用差分进化算法进行求解,并将最优解作为下一步行动的输入对区域进行覆盖搜索,覆盖结果优于平行搜索方法。针对任务区域固定目标的搜索问题,考虑到侦察和通信限制,文献[26]提出将最小化搜索时间作为目标,并基于合作-竞争粒子群算法提出了基于协作无人机子群构成的分布式实时控制模型用于目标搜索,该算法相比于传统的区域搜索算法在无人机数量增多的情况下仍具备足够的时间效益和容错度。针对完全未知任务区域搜索问题,文献[27]提出了基于改进型机器种子优化方法(Improved Robot Bean Optimization Algorithm, IRBOA)的无人机集群协同搜索方法,该算法整合多阶段搜索机制和调度控制策略,仿真结果表明该算法相对于基于自适应机器粒子群优化算法(Adaptive robotic particle swarm optimization, A-RPSO)的区域搜索方法在复杂和未知环境下的搜索能力更强。为降低多无人机协同搜索未知环境过程中存在的重复搜索、低搜索效率以及对动态目标搜索能力差的问题,文献[28]提出蜂窝状环境模型来降低重复搜索度并利用马尔可夫链对动态目标位置变化进行建模,而后基于改进的鸽群优化算法进行全局寻优,从而实现了目标搜索。考虑到区域搜索效费比,文献[29]将不确定性环境下的任务区域侦察问题,转化为解决侦察路径最优化规划问题,采用离散布谷鸟搜索算法进行寻优,使得全任务区域遍历侦察航路最短。
2.2 基于多子群启发式算法的集群协同搜索
协同进化算法是通过构造两个或者多个种群,建立内部竞争或合作关系,多个种群通过相互作用提高各自性能,适应复杂动态变化环境,达到种群优化目标,如图5 所示。针对复杂环境的不确定性,文献[30]提出搜索概率图描述环境不确定性并使用贝叶斯准则进行更新,利用协同进化算法构造多个子群进行多子群中最优个体寻优并在线生成多UAV协同搜索方向和路径从而实现多UAV协同区域搜索。
蚁群在觅食过程中通过个体间信息素交换信息并协作搜索,从而找到一条从蚁巢到食物源的最短路径。多蚁群算法是假设图空间中有多个种类的蚁群,每个种群的优化过程作为求解优化问题子问题的过程。蚂蚁个体同时受到同种群个体吸引和异种群个体的排斥,因此多蚁群算法具有协作性和并行性、正负反馈机制,从而受到研究者的广泛关注。文献[31⇓-33]将多蚁群算法中多个蚂蚁子种群类比为多架无人机,每个蚂蚁种群负责一架无人机的路径搜索,在同种群内多无人机之间通过信息素进行相互引导,而异种群间通过信息素进行相互排斥,这样多目标搜索过程中无人机既可以通过群体内信息素引导趋向最优路径,同时也因受到其他无人机群排斥而避免重复无效搜索,提高了搜索效能。
基于启发式算法的集群协同搜索通过将协同搜索过程转化为优化问题,求得最优解,不断进行滚动更新集群的方向、位置等参数达到集群协同搜索的目的。这种方法会随着目标数量或者无人机数量的增多而导致计算量大幅增加,对于大规模集群协同搜索的实现是一个挑战。因此,研究人员还需要研究更加智能和计算量适中的智能集群协同搜索算法。
3 基于涌现控制的集群协同搜索
无论是传统的搜索方法还是基于生物启发式算法的协同搜索方法生成的集群协同搜索行为相对固定,这类算法依赖于数学建模并不能生成新的搜索规则,随着环境和任务复杂度增加很可能因集群行为环境适应能力减弱而导致行为失能,最终导致任务失败。因此,具备自学习能力的基于涌现的集群协同搜索算法因可生成新的集群行为规则而具有现实意义。基于演化理论和基于强化学习的集群协同搜索算法是主要的两种群体行为涌现控制算法。
3.1 基于演化理论的集群协同搜索
传统的协同搜索方法采用自上而下的设计方法,集群搜索行为模式非常确定,而搜索任务以及环境非常复杂,这种方法存在灵活度不足以及环境适应性差等问题。集群顶层的行为设计和底层的行为之间存在着非常复杂的非线性关系,仅仅利用精确的数学建模的方式进行集群协同搜索算法设计已不现实。基于演化理论的集群协同搜索方法不再具体考虑集群局部行为与顶层行为设计之间的复杂的关系,而是采用一种“优胜劣汰”的机制搜索理解空间来产生集群单体行为规则,从而可以涌现出有效的群体搜索行为。无人机集群单体体积相对较小,所携带的传感器等载荷能力相对有限,该理论能在硬件资源受限条件下尽可能地探索由传感器到动作的端到端映射关系来满足复杂任务的需要[34]。集群协同搜索行为演化基本原理如图6 所示。
演化理论通过不断探索机器人自身和环境之间的交互行为理解空间,从而获得更多优质的多样性集群行为,目前该理论已经逐步在单体以及多智能体控制领域开始使用。文献[35]针对微型扑翼在进行室内窗口位置搜索以及穿窗任务中存在特定场景失能的问题,应用演化理论对所设计行为树进行演化得到了鲁棒性更高的任务行为树结构,演化出适合该特定复杂场景的行为,而且通过演化获得的行为控制器,在从仿真到实物迁移过程中控制结构更容易理解和调整。文献[36]针对集群机器人觅食任务设计了一个以行为树为框架的集群行为演化控制器,在仿真和实物实验中皆实现了集群机器人的搜索和觅食行为。在无人机集群协同搜索领域,文献[37-38]通过设计基于最近邻三个单体间方向和距离以及最少访问的栅格方向作为四个局部行为规则并利用MAP-Elites算法演化生成了多种类型的群体区域搜索行为,而后进行了集群任务区域全覆盖搜索和通信稳定性保持研究,解决了手动设计集群控制器所难以解决的顶层和底层行为之间的复杂耦合关系。文献[39]针对多功能集群须同时解决多任务多场景的问题,同样采用了基于单体间局部行为规则演化集群行为的方式,将单体和最近邻的6个单体间方向和距离、最少访问次数的近邻任务区域的方向以及平均预测发射点位置等规则作为集群行为演化的局部规则,利用MAP-Elites算法演化生成一批具有不同特征的集群协同搜索行为控制器,通过手动选择不同特征的控制器,可以解决集群在协同搜索过程中区域全覆盖侦察、通信网络保持以及射频发射器定位的问题。目前国内基于演化理论集群智能行为演化研究逐步开展,如文献[40]利用遗传规划算法来实现机器人避障行为的演化。
国内在集群协同搜索领域,主要运用如蚁群算法、粒子群算法、遗传算法等生物启发式算法来对集群单体进行组织和互操作实现群体智能行为生成,完成区域侦察和目标搜索。文献[41]提出集群机器人行为演化过程是可诱导的,利用物联网协同感知技术构建基于传感器网络特征的诱导信息,从而诱导和控制集群行为演化方向。基于单体间局部规则的集群协同搜索行为演化方面目前尚处于空白,是后续重点拓展的方向。
集群智能行为演化算法研究重点在于集群内部个体局部控制规则的设计以及适应度函数的选择,局部行为规则的设计是行为演化的基础,而合适的适应度函数是群体行为成型的保证。这种方法的不足之处在于群体行为和集群模型参数之间的关系未知,集群行为对参数的取值比较敏感,需要大量仿真实验确认合适的参数值。此外,适应度函数设计主要依赖于设计者对集群行为主要因素的定位能力,当任务复杂时对设计者是一个挑战。
3.2 基于强化学习的集群协同搜索
强化学习是一种智能体通过和环境之间不断地交互和学习来实现环境最大回报或者达到某个设定目标的机器学习方法。强化学习一般以马尔科夫决策过程为理论基础,通过不断的尝试来寻求马尔科夫决策过程的最优策略。强化学习基本原理模型如图7 所示。
强化学习机理决定了它与人类经验学习和决策思维方式的高相似性,可有效地解决样本数据获取难等问题[42]。多智能体系统是当前强化学习领域的应用研究热点,主要通过研究多个单体间交互作用来解决复杂实时动态多智能体环境下任务调度、资源分配和行为协调以及冲突消解等问题。多智能体强化学习可分为集中式和分布式强化学习两种。集中式强化学习汇总各个智能体观测值,进行集中计算,并将结果返回给各个多智能体。在这种方式中,多智能体仅扮演感知和任务执行的角色。在分布式强化学习中,每个智能体都可以进行学习,在感知环境后可以做出局部的决策并进行局部信息共享,再进一步调整策略。集中式和分布式强化学习在无人机集群领域应用越来越多,目前在集群遂行协同搜索任务过程中也逐步开展。
3.2.1 基于集中式强化学习算法的集群协同搜索
1)基于Q学习网络的协同搜索算法
Q学习网络是由一系列的状态、动作和奖励组成,智能体的最终目标是最大限度地提高任务总体的回报[43],其算法步骤如图8 所示。
为实现对未知环境中多个动态目标的实时搜索,文献[43]设计了以搜索效率作为奖惩函数的Q学习网络实时生成多无人机协同搜索路径来实现协同目标搜索。首先利用无人机状态和动作信息设计Q值表,Q值表中横坐标代表无人机状态信息,纵坐标代表无人机的动作,而后确定奖惩函数。奖惩函数为最优目标函数,包括三部分元素:寻找到目标的收益、搜索环境的收益、执行任务对时间和油量消耗以及碰撞的代价。最后设计Q值表更新过程,并依据更新过程进行滚动迭代收敛,从而找到最优决策。
2)基于深度Q网络的协同搜索算法
深度Q网络[44]是深度卷积神经网络和强化学习中的Q学习方法相结合而成的深度强化学习算法,该算法利用深度卷积神经网络强大的信息特征提取能力来感知环境信息,随后提取部分环境信息特征利用Q-Learning通过马尔科夫决策模型做出决策,完成状态到动作的映射,并获取反馈奖励,后续又将这些信息转化为训练数据提供给深度卷积学习网络进行学习和特征提取,从而持续优化神经网络的权重矩阵,最终获得最优网络结构。深度Q网络机理如图9 所示。
文献[44]利用深度Q网络进行了无人机集群协同区域侦察路径规划,解决了多无人机对任务区域覆盖问题。文中将无人机载雷达侦察覆盖率作为奖励函数,以无人机的位置坐标和飞行方向为状态,以无人机速度方向和转弯半径所确定的圆弧均匀采点作为无人机可采取的动作,而后利用深度Q神经网络为每个无人机训练一个深度神经网络,使得无人机集群可根据当前状态推断出相应的无人机动作,通过不断学习无人机集群不断产生趋向更大侦察覆盖量的动作,进行更大范围的侦察覆盖,直到任务结束。针对多静态目标搜索问题,考虑到无人机感知能力和通信能力有限,文献[45]提出了利用深度Q神经网络(Deep Q-learning Network, DQN)来对多无人机搜索路径进行训练,文中考虑到局部概率地图以及相邻单体分布,设计了将目标搜索收益、时间成本以及引导性奖励作为标准的奖励函数指导无人机的行为探索和学习,为保证训练过程的稳定性,单体决策在训练阶段中进行周期性发布和共享,该算法相比于传统区域覆盖方法和随机搜索策略效果更好。
3)基于QMIX网络的协同搜索算法
基于额外状态信息的联合行动-价值函数学习是集中式学习的一个有效的途径,但是这个方法并不适用于分布式决策。QMIX是一种具有应用前景的典型集中式训练—分布式执行的强化学习算法框架,它能够以一个集中的端到端训练方式得到每个智能体的分布式决策。算法基本思想是将局部节点观测值进行非线性联合计算并作为每个单体单调动作—价值函数。这种方法本质上还是通过训练集群中单体局部控制网络来达到解耦集群复杂交互关系的目的。QMIX将一个估计联合动作—价值映射关系的网络用于每个单体值的非线性整合,这些单体的值依赖于单体的局部观测,其中联合动作—价值函数是单调的,这一机理使得学习中的联合动作—价值函数易于最大化,确保了集中和离散决策的连贯性[46]。QMIX原理包含3个部分:单体网络、混合网络和超网络。单体网络用于计算各个单体在环境中的动作—价值函数,混合网络是一个前向神经网络,能够非线性联合各个单体值函数从而产生联合值函数,在QMIX网络中起到了信息整合的作用。超网络则负责生成网络中每个部分的权重和补偿。QMIX全网络结构如图10 所示。
针对无人机集群在协同搜索任务中应用传统预前规划方法难以适应动态环境的问题,文献[47]提出了基于强化学习的多无人机自主决策模型并设计了状态空间、动作空间和奖惩空间,利用QMIX来对集群进行训练,从而达到了满意的区域覆盖率和重复率。
3.2.2 基于分布式强化学习算法的集群协同搜索
分布式强化学习具备响应快、灵活度高且系统鲁棒性强的特点,是当前集群智能控制领域的研究重点[48]。
当前,强化学习运用于集群协同搜索主要以集中式训练-分布式执行为主,分布式也逐步展开,由于分布式强化学习算法存在样本数据量大、训练时间较长且奖励函数设计困难的问题,算法整体延展性较差。对于多智能体复杂任务研究及应用仍是一个挑战。
4 结束语
传统集群协同搜索方法主要对无人机航路进行规划,算法对数学模型依赖多且搜索行为相对固定,不适应复杂环境和任务的需求。启发式算法可以扩大算法的搜索空间寻求最优解,但随着集群中无人机数量的增加会导致计算时间变长。这类算法依赖于既有的启发式算法框架,对环境的适应能力有限。基于演化理论和强化学习的集群协同搜索算法则在智能性、灵活性和适应性方面具有优势。在基于局部规则演化的协同搜索行为涌现控制算法中,由于MAP-Elites算法所具备的质量和多样性兼顾的特性,使得集群可依据局部行为规则演化出多样的优质群体行为,使得多无人机在协同搜索过程中不仅可以实现区域覆盖搜索同时也可以满足通信约束等任务需求。该算法可以根据不同环境和适应度函数的需求演化而生成新的行为规则,可适应于多种复杂任务和环境。强化学习作为当前人工智能研究热门在集群协同搜索领域应用研究也逐步展开,其独特的状态到动作端到端映射和奖惩反馈机制使得集群协同搜索行为更智能,对环境的适应性也更强,但该算法多是离线训练且随着任务的复杂度增加需要训练时间也大幅增加。
随着无人机技术的发展和任务需求的不断增加,无人机集群协同搜索将会面临更加复杂的任务环境和更多约束条件,更智能化的集群协同搜索算法是未来发展趋势,其特点具体可以归纳为以下几个方面:
1)实时高效。未来集群作业须要快速响应,对集群的实时行为生成要求提高,更高的硬件计算能力以及更简洁有效的算法程序是其保证。
2)自主智能。任务环境动态复杂,如何在无人机单体带载能力有限以及通信受限情况下,集群顺利完成协同搜索是一个不小的挑战。基于演化理论和强化学习的集群协同搜索方法是比较有前景的发展方向。前者基于集群单体间局部行为规则衍生出多种群体行为,通过适当的约束和引导就可以演化出满足任务需求的集群行为,后者集群通过不断与环境交互学习建立一套状态到动作的映射关系,使得集群具有很强环境适应性。这两种方法都可以通过各自算法机制生成新的集群行为规则,对环境的适应能力更强。
3)安全容错。集群协同作业只有在保证无人机足够数量的情况下才能顺利进行,而集群飞行中故障在所难免,如何做到容错是提升集群生存力和任务高质量完成的重要保证。