基于布谷鸟搜索算法的多智能体自动避障方法

安文广

（河北金融学院，保定 071051）

0 引言

随着科技、智能化水平的不断提升,智能体在众多领域的应用性普遍提高,特别是在灾害救援、空中侦察、有毒有害物质管控方面均有较好的表现[1]。多智能体自动避障即是在动态变化的障碍环境中,规划出合适且安全的运动路线,使其能够躲避全部障碍物实现目标的跟踪,并且在环境条件允许的条件下,能以某种编队队形执行任务[2,3]。通过对多智能体进行避障控制,不仅能够缩减任务成本花销、也能加快任务执行效率。因此,在利用多智能体进行目标搜寻、跟踪时,采用何种避障算法是确保多智能体安全、顺利、无碰撞地完成任务的关键,具有很重要的现实意义。

众多学者对多智能体避障问题进行了相关研究,张玮等人针对利用烟花算法对避障路径进行确定时的缺陷问题,通过引入“镜面映射”规则及先锋火花等对其进行优化,以此确定最短避障路线,再利用蚁群算法对其进行优化处理实现智能移动体的避障路径规划,但该方法容易陷入局部最优困局,无法获得最合适避障路线[4]；党霞针对包装机器人的避障问题,提出通过基于引力势场的避障方法,首先对机器人的运动轨迹模型进行构建,对其运动性能进行分析,根据机器人间的引力势场对其避障状态方程进行设计,以此实现包装机器人的自动避障,但该方法中引力增益系数设定存在不足,导致随机性强、动态变化的障碍环境下的避障效果大打折扣[5]。因此,本文提出基于布谷鸟搜索算法的多智能体自动避障方法,在多智能体目标追踪过程中,利用人工势场法对其运动路线进行规划,并通过改进布谷鸟搜索算法对其增益系数进行优化,提高多智能体的避障效果。

1 多智能体自动避障

1.1 人工势场法原理

人工势场法的基本原理是所有智能体处于混合势场的动态环境下,其与障碍物间存在斥力场,又与目标之间存在引力场,在两种势力场的共同作用下,通过势函数实现其避障方向的确定,从而获得安全、无碰撞的避障路线[6,7]。人工势场法原理的实际应用方法是在多智能体运动的动态环境中,U为构建的势场,由两部分过程,其一为目标对多智能体的引力场,其方向是从多智能体到目标位置,其二为障碍物对多智能体的斥力场,其方向是障碍物到多智能体。U为引力、斥力势能之和,多智能体在U状态下,通过不断躲避运动区域障碍物抵达目标位置。

1.1.1 引力函数

在人工势场法中,引力势场函数与距离相关,对于多智能体、目标而言,二者间的距离是势力函数的影响因素,多智能体受到的势能大小与距离的远近成正比[8],当势能不断降低,说明多智能体与目标间距离越小,直到多智能体抵达目标处时,其势能降低为0。引力势场函数可通过式(1)进行描述：

式(1)中：对于当下智能体z,与目标位置的相对距离表示为zg,引力增益系数表示为katt,其引力Fatt(z)可通过Uatt(z)的负梯度进行描述,如式(2)所示：

1.1.2 斥力函数

对于动态环境下的障碍物,其周围产生的势场与多智能体具有相斥性,且与二者间距离成反比关系[9],即二者相距距离越短,排斥性越大。斥力势场函数可通过式(3)进行描述：

式(3)中：对于多智能体,与障碍物间的距离表示为z-z0,斥力增益参数表示为krep,对于障碍物,其斥力可作用的距离表示为ρ0,其斥力可通过Urep(z)的负梯度进行描述,如式(4)所示：

总势能的公式可定义如式(5)所示：

对于多智能体,其合力公式的描述如式(6)所示：

1.2 改进布谷鸟搜索算法原理

1.2.1 布谷鸟搜索算法（CS）

CS搜索算法是基于布谷鸟巢寄生、育雏行为以及莱维飞行机制的智能化搜索策略[10],与其余算法的差别即是其独特的搜索方式,即莱维飞行机制,方向及步长是该机制的主要内容,前者通过均匀分布进行确定,后者满足Levy分布,且具有随机性,可通过Mantegn法则实现。CS算法实现一般需满足以下条件：

1）各布谷鸟对鸟巢的选取依据随机性,且各鸟巢仅有1个鸟蛋。

2）布谷鸟子代选择优质鸟巢,以确保CS算法具有最佳解。

3）n为备选鸟巢个数,其值为定值,可搜索到的鸟蛋概率表示为pa,且pa∈[0,1]。

上述条件具有理想化特点,通过CS算法可获得局部最佳位置、全局最佳位置,前者可通过式(7)进行调节：

其中：对于鸟巢i,其第t代的结果为该结果经全局调整获得的最新结果表示为。点对点乘法表示为⊕,步长控制因子、步长分别表示为γ、λ,Levy(λ)需满足Levy分布函数,其如式(8)所示：

通过式(9)可生成Levy的随机数,如式(9)所示：

其中：Levy的分布μ、压缩因子v满足标准正态分布。系数φ的表达式如式(10)所示：

仅利用莱维飞行机制的全局搜索无法满足高准确度要求,需结合局部搜寻方法完成位置的调整,局部最佳位置可通过式(11)进行调整：

其中：满足均匀分布的任意数为r,且r∈(0,1),迭代t次后,任意两个位置表示为

1.2.2 改进布谷鸟搜索算法

其中：在迭代t次时,群体的最佳位置表示为惯性系数表示为的更新公式描述如式(13)、式(14)所示：

式(13)、式(14)中：wmax、wmin表示权重的最大、最小值；搜索范围的界线分别为a、b,且b＞a。

改进布谷鸟搜索算法实施过程为：

1）对布谷鸟个体所在位置的优劣进行判断,并按从优到差顺序排列。

2）将布谷鸟种群分成两组,其中位置较好的一组通过式(11)确定局部最佳解,可有效扩大其搜索区域。另一组则通过式(12)获取局部最佳解,虽然此组个体不具备较好的初始位置,但通过逐步获取最佳位置,可有效提升个体搜索的准确度。改进后的布谷鸟搜索算法具备突出局部搜索性能的同时,可提升其全局搜索能力。

1.3 基于人工势场法与改进布谷鸟搜索算法的多智能体自动避障

在动态环境下,多智能体存在对环境具有较低适应性,编队需要花费较长时间的缺点,本文采用人工势场法实现多智能体的自动避障,通过改进布谷鸟搜索算法对增益系数进行优化。

1.3.1 基于改进布谷鸟搜索算法的增益系数优化

在动态环境中,障碍物的分布呈现任意性特点,而人工势场法生成的增益系数存在不变性,故采用改进布谷鸟搜索算法对其进行优化,获取合适增益系数,为多智能体规划出准确避障路径,提高避障精度[12,13]。利用式(8)对引力增益系数、斥力增益系数进行优化,由于多智能体是沿着目标点引力方向进行编队飞行,即式(9)的Levy分布集合,此时,引力增益系数可通过(15)式进行描述：

斥力增益系数的描述公式如式(16)所示。

其中：基于莱维飞行机制,获得的增益系数为β,满足任意性原则。

将式(15)代入到引力势场函数中对其进行改进,改进后公式如式(17)所示：

将式(16)代入到斥力势场函数中对其进行改进,改进后公式描述如式(18)所示：

由此可确定引力、斥力表达式,分别用式(19)、式(20)描述：

1.3.2 效率函数

多智能体飞行队形是否适合于当下动态环境可通过环境适应度函数进行描述[14],若其编队队形与动态环境具有较好的适应性,则具有较低适应度函数值,该函数可通过式(21)进行表达：

式(21)中：对于多智能体编队队形,其失真度表示为Kfdd,能量损失率表示为Kect,形式转换中的收敛时间比表示为Kcct。

多智能体所处的动态环境下,障碍物呈任意性分布,为分析多智能体对环境的适应度,本文通过方差指标进行评估,视其为效率函数对多智能体的自动避障路径进行判断[15],如式(22)所示：

其中：对于多智能体,在其自动避障时,其时间方差表示为Kδ,其值决定了多智能体自动避障过程对环境的适应度,该值越低,说明多智能体避障路径与环境的适合度高。

1.3.3 多智能体自动避障

在实施多智能体自动避障前,需先对其编队队形知识库进行构建,再对避障线路进行判断,当只有1条避障路线时,根据队形伸缩因子选择最佳队形,实现多智能体的自动避障；当避障路径较多时,采用改进布谷鸟搜索算法优化后的人工势场法实现多智能体避障,并依据领航跟随法对避障队形进行有效维护。多智能体自动避障过程如图1所示。

图1 多智能体自动避障过程

多智能体自动避障过程为：

第一步：确定多智能体编队的原始队形,并对动态障碍物环境进行检测,识别目标点坐标。

第二步：根据障碍物检测结果确定多智能体的避障路径,当只存在一条避障线路时,在对障碍物进行膨化处理的基础上,对队形的伸缩因子ρ进行确定,当满足ρ≥1条件时,则以原始队形通过障碍区域,否则,继续判断是否满足ρm≤ρ＜1条件,若条件满足,则仍采用原始队形进行避障,但需对队形进行压缩,缩减各智能体间的距离。反之,则需对fenvfit进行运算,根据其结果选择合适的编队队形进行避障。

第三步：当存在多条避障路线时,在对障碍物进行膨化处理的前提下,仍需对队形的伸缩因子ρ进行计算,当其值满足条件ρ＜ρm时,通过改进布谷鸟搜索算法优化后的人工势场法确定多智能体的避障方向,根据fenvfit计算结果确定多智能体的编队队形,以此多智能体完成一次自动避障。反之,返回到第二步。

第四步：判断多智能体是否抵达目标坐标,若任务未完成,则需继续进行飞行任务,并返回到步骤二,反之,飞行任务结束。

2 实验分析

以多智能体为研究对象,设定动态环境下障碍物数量为30,目标点数量为2,其坐标表示为（30,12）、（36,0）,智能体数量为5,各智能体标记为A-E,其坐标为（-20,-2.5）、（-25,4.5）、（-26,-2.5）、（-23,10）、（-23,-11）,且分别以0.3m/s、2m/s、1.5m/s、1m/s、0.8m/s速度向目标点移动,多智能体编队队形夹角40度,应用本文方法为多智能体提供避障规划,验证本文方法的避障能力。

采用本文方法对多智能体进行避障规划,使其顺利抵达目标点（30,12）,通过不同时刻各智能体的避障状态,分析本文方法的自动避障性能,避障过程中各智能体在不同时刻的运动状态如图2所示。

图2 多智能体避障过程

分析图2可知,采用本文方法对多智能体的运动路线进行避障规划,确定避障路线只有1条,在t=0时刻,各智能体处于杂乱运动状态,尚未形成编队队形,但运动方向均朝向目标点,经1.1s后完成初始编队,并以V型编队运动；当发现前方障碍物后,采取V形编队并对该队形进行压缩方式实现障碍物的自动避障,最终顺利抵达目标坐标。实验结果表明,本文方法可根据动态环境下障碍物的分布,判断实现多智能体的自动避障。

以（36,0）坐标作为目标点,采用本文方法对多智能体的运动路线进行自动避障,通过分析多智能体的避障过程验证本文方法的避障能力,实验结果如图3所示。

图3 多智能体避障能力分析

分析图3可知,各智能体能够在1.6s后迅速集结成编队队形对（36,0）位置的目标进行追踪,当遇到障碍物后,可快速规划出避障轨迹,采用沿障碍物两边绕行方式完成自动避障,并且能在躲避障碍物后恢复到原始V型队形,最终抵达目标坐标。由实验结果表明,本文方法可实现避障路线规划,并能够确定适合的避障队形,实现多智能体的自动避障。

在多智能体对目标（30,18）、（36,0）的追踪过程中,采用时间方差指标评估其避障性能的优劣,为验证本文方法的避障效果,障碍物选择遵循随机性原则,并通过10次避障实验获取方差均值实现避障性能的分析,实验结果如图4所示。

图4 多智能体避障性能分析

分析图4可知,在对各目标进行追踪过程中,时间方差指标均较低,其中（30,12）目标的方差均值低于0.1、（36,0）目标的方差均值低于0.15,说明采用本文避障方法后,多智能体对动态环境具有较高适应度,能够实现最优避障路线规划,取得突出避障效果。

3 结语

以多智能体为研究对象,采用本文方法对分布于动态环境下的不同目标点进行避障跟踪,通过分析多智能体对各目标的避障跟踪过程分析本文方法的自动避障性能,并通过时间方差指标验证本文方法的避障效果。实验结果表明：本文方法能够对动态环境下随机分布的障碍物进行自动避障,规划不同避障路线,且具有较低的方差均值、显著的避障效果。