三维空间的自适应气体源定位方法

崔益豪，王 巍,3+，王 彤，朱天宇，田立勤

(1.河北工程大学 信息与电气工程学院，河北 邯郸 056038；2.河北工程大学 河北省安防信息感知与处理重点实验室，河北 邯郸 056038；3.江南大学 物联网工程学院，江苏 无锡 214122； 4.华北科技学院 河北省物联网数据采集与处理工程技术研究中心，河北 廊坊 065201)

0 引 言

有害气体泄漏事故对人们的生命、财产以及自然环境等具有极大的威胁，近几年其发生的频率具有明显上升的趋势，如何定位有毒气体泄漏源问题成为了公共安全领域亟待解决的问题。受自然界中生物利用气味定位食物或求偶等行为的启发，自20世纪90年代以来，一些学者开始尝试利用机器人进行气体源定位研究，并取得了大量的研究成果，但这些研究大多是基于二维平面的研究，忽略了气体扩散的三维特性，并且均需切换不同的方法来完成定位过程中不同阶段的任务，影响了算法的整体搜索效率。随着无人机技术的迅速发展，其在多个领域得到了广泛的应用[1]，为三维空间气体源定位问题的研究提供了良好的平台支撑，使得基于无人机平台的三维空间气体源定位问题受到了国内外研究人员的关注，并取得了初步的研究成果[2-5]，其中大多数都是基础性的研究，这些研究确认了用无人机进行三维气体源定位方案的可行性，为之后的研究提供了重要参考。二维平面上的气体源定位研究经历了从基于简单趋化性和趋风性等算法的单机器人定位方法[6]到基于优化类等算法的多机器人定位方法[7,8]，为本文的研究提供了研究思路。同时已有的气体源定位方法存在着依赖于多模态传感器信息的问题，使得方法不能同时适应多种环境。因此，本文提出一种利用改进烟花算法来协调多无人机在三维空间自适应地进行气体源定位的方法，该方法只需要气体浓度信息就可以定位到气体泄漏源，为实际应用中快速准确定位气体泄漏源提供支撑。

1 三维空间自适应气体源定位方法

群体智能作为多机器人系统有效的协调控制方法，在针对二维的多机器人气体源定位研究中得到了很好的应用效果。本文提出的三维空间的自适应气体源定位方法，就是一种利用改进烟花算法协调多无人机进行三维空间气体源定位的策略，可以自适应的进行烟羽发现、烟羽跟踪、烟羽再发现以及气体源确认，无需通过切换不同的算法来完成不同阶段的任务，大大提高了算法的整体搜索效率。同时烟花算法的爆炸搜索机制，使得算法相比于其它群智能算法具有较强的局部搜索和一定的全局搜索能力，进而更容易搜索到目标环境中的气体浓度最大值位置。

1.1 三维气体扩散模型

在真实环境中的气体传播受到湍流的作用，使烟羽的分布呈现时变、间隔和多极值等复杂的特点[9]，很难通过构建精确的模型来描述，因此气体源定位研究大多采用相对简化的数值计算模型。目前在气体源定位领域采用的烟羽模型主要包括:基于烟丝的大气扩散烟羽模型、格构烟羽模型、基于CofinBox软件包的烟羽模型、GAUSS烟羽模型等[10]，这些烟羽模型除了GAUSS烟羽模型外大多是二维的烟羽模型，不适用于三维环境下的气体源定位方法的仿真实验。GAUSS烟羽模型是较早得到应用的三维烟羽模型，方法较为成熟，也是目前采用较多的气体泄漏模型，因此本文采用GAUSS烟羽模型对所提方法进行仿真研究，其浓度分布如式(1)所示

(1)

其中，c(x,y,z,H)为三维空间中点(x,y,z)处的气体浓度值，单位为mg/m3；H为气体泄漏源离地面的高度，单位为m；Q为源强，单位为mg/s；ky和kz分别为泄漏气体在y轴和z轴的扩散系数；μ为目标环境的平均风速，单位为m/s。

1.2 改进烟花算法

Ying T等在2010年受到烟花在空中爆炸产生火花的启发提出了烟花算法。本文将三维空间的气体源定位问题转化为最优解问题，烟花在三维空间的爆炸过程即对三维空间中气体浓度最大值位置的搜索过程，具体方法如下：

1.2.1 改进的爆炸算子

在气体源定位过程中，主要是依靠历次迭代中的最优烟花来对烟羽进行跟踪，但根据基本烟花算法的烟花爆炸半径公式可知历次迭代中最优烟花的爆炸半径为不变的固定值，使得算法的收敛性主要依靠全局搜索，导致了算法稳定性较差和定位效率较低。针对此问题，本文参考文献[11]，在气体源定位过程中引入自适应爆炸半径机制，实现最优烟花爆炸半径的动态调整，加快算法的收敛速度和稳定性，其计算公式为

(2)

(3)

(4)

其中，k表示当前迭代次数，R(k)表示当前最优烟花的爆炸半径，R*(k+1)为某个特殊个体(这个个体的选择依赖于式(3))与本次适应度值最好的个体(下一代最优烟花)的距离，si为满足f(si)

其它烟花爆炸半径和所有烟花火花数目的计算，如式(5)、式(6)所示

(5)

(6)

式中：Ri是第i个烟花的爆炸半径，r为常数，用来调整爆炸半径的大小，ymax是当前最大适应度。Ni是第i个烟花产生的火花数目，η为常数，用来调整每个烟花产生的火花数，ymin是最小适应度，为极小值，避免除零错误，m为烟花个数。算法还通过设置烟花产生火花数目的上下限避免适应度较高的烟花产生过多的火花。

1.2.2 变异操作

烟花算法通过高斯变异，增加爆炸火花种群的多样性，避免算法陷入局部最优，如式(7)所示

xi=xi·g

(7)

式中：xi表示第i个烟花位置，g服从均值为0，方差为1的高斯分布，xi·g表示对第i个烟花进行高斯变异操作。

1.2.3 映射规则

对于在烟花爆炸过程中出现火花位置越界的情况，烟花算法通过式(8)将其映射到目标空间范围之内

xi=xl+|xi|%(xu-xl)

(8)

式中：xi表示第i个烟花位置，xl为可行解下限，xu是可行解上限。

1.2.4 改进的选择策略

相比于其它群智能算法，烟花算法的最大优势是其爆炸搜索机制，多个烟花同时在其爆炸范围内随机产生大量火花，烟花爆炸的并行和产生火花的随机性，可能导致火花位置重复或相互之间距离太近的情况，使得算法在实际应用中重复检测某个点或一个极小区域，从而影响算法的整体搜索效率，因此根据式(9)、式(10)对火花进行调整

(9)

(10)

其中，xd为待舍弃的花火位置，xi(i=1,2,…,n-1,n)表示当前个体位置，xj(j≠i,i=1,2,…,n-1,n)表示其它个体位置，dt表示个体间最小距离阈值。采用精英保留策略，保留适应度值最大的个体，作为最优烟花，其余烟花根据式(11)、式(12)来选择

(11)

(12)

式中：R(xi)表示第i个个体到其它所有个体的欧式距离之和，n为所有个体总数。

1.3 气体源定位三阶段自适应策略

Hayes等将气体源定位问题分为烟羽发现、烟羽跟踪和气体源确认3个阶段。本文利用改进烟花算法协调多无人机，将烟花看作无人机，对应的火花作为其采样点，自适应地进行烟羽发现、烟羽跟踪、烟羽再发现以及气体源确认，进而完成气体源定位任务。

1.3.1 烟羽发现

首先，设置一个气体浓度检测阈值ot，假设无人机检测范围为三维空间中的球形区域，其半径为r，当所有无人机检测到气体浓度均小于ot时，则所有无人机自适应地进行烟羽发现。此时，由于没有气体信息而无法设定主无人机，因此，随机选择一个无人机作为主无人机，其采样范围根据待检测空间大小设置，其它无人机作为辅助无人机，其采样范围根据式(5)计算得到Ri=r，所有无人机的采样点数量根据式(6)计算得到Ni=η，此时η大于最大采样点数ηu，所以每个无人机都拥有整个搜索过程中最大的采样范围r和最多的采样点数ηu，然后在其采样范围内随机产生对应的采样点。改进烟花算法基于分布的选择策略使得越分散的个体(即距离其它个体越远的个体)越可能被选择为下一代无人机的位置，所有无人机都基于式(11)、式(12)选择下一代的目标位置，以当前无人机的位置到下一代的目标位置的距离为依据，依次以就近原则通过打擂台的方式来确定其目标位置。改进烟花算法这种特殊的进化机制使得该方法能快速对目标空间进行覆盖式搜索，进而快速完成烟羽发现的任务。图1为烟羽发现的二维示意图，其为单个无人机在烟羽发现阶段，四次迭代的搜索过程，分别用空心的“圆”、“菱形”、“正方形”和“直角三角形”依次表示四次迭代中无人机的位置，设置无人机的最大采样点数ηu=4，采样点分别用对应的实心图形来表示，在烟羽发现过程中无人机的搜索范围不变，采样点数也不变，烟花算法基于分布的选择策略，使得每次迭代中距离其它采样点较远的个体位置被选定为下次迭代中无人机位置的概率最大，此处直接将其作为无人机的位置，依次迭代，对目标空间进行覆盖式搜索，直到某个无人机检测到气体浓度大于ot为止，算法自适应进入烟羽跟踪阶段。

图1 烟羽发现的二维示意图

1.3.2 烟羽跟踪

本文所提方法主要依靠主无人机对烟羽进行跟踪，其采样范围根据式(2)～式(4)进行更新，辅助无人机的采样范围根据式(5)进行更新，所有无人机在其采样范围内产生由式(6)计算得到的采样点数对目标空间进行搜索。在烟羽跟踪阶段，每次迭代计算出下一次迭代无人机的位置后，主无人机通过移动到其中的最优适应度值的位置来进行烟羽跟踪，而辅助无人机则以就近原则通过打擂台的方式选择其下一次迭代的位置，进而辅助主无人机定位到整个目标空间中的气体浓度最大值的位置。由于主无人机采用自适应采样范围调整策略，同时又拥有所有无人机中最多的采样点数，使得主无人机在气体源跟踪过程中表现出较强的局部搜索能力，能够有效的对烟羽进行跟踪。方法通过式(7)产生高斯变异采样点增加采样点的多样性，同时辅助无人机的位置根据式(11)、式(12)进行更新，均提高了系统的全局搜索能力，使算法在烟羽跟踪过程可以较好地平衡局部和全局搜索能力，进而快速准确地定位目标环境中气体浓度最大的位置。

1.3.3 气体源确认

气体源定位过程中，若满足条件(13)，则算法终止，将主无人机的位置作为气体源位置输出

(13)

其中，Imax表示最大迭代次数，当迭代次数I大于最大迭代次数Imax时，算法终止，输出定位结果；Ot为气体源浓度阈值，主无人机所在的位置的适应度值大于Ot时，则该位置为待定气体源；Tt为判定周期，当主无人机所在位置的适应度大于Ot时，再经过Tt次迭代，如果主无人机的位移距离均小于距离阈值dt时，则将该位置确定为气体源，算法终止，输出定位结果。

1.3.4 算法步骤

本文提出的三维空间自适应气体源定位方法的主要步骤如图2所示。

图2 三维空间的自适应气体源定位方法流程

2 实验及分析

2.1 三维气体扩散模型仿真

现有方法大多是在GAUSS烟羽模型基础上将其降维到二维平面进行研究，本文针对三维环境下的气体源定位问题对GAUSS烟羽模型进行三维仿真分析。其中，设泄漏气体为CO，气体泄漏源离地面的高度H为0.5 m，源强Q为56.667 mg/m3，平均风速μ为2 m/s；模拟环境的长、宽、高分别设置为30 m、20 m、10 m。其GAUSS烟羽模型在三维空间中的气体分布如图3所示。

图3 基于GAUSS模型的三维空间气体浓度分布

图3为气体浓度值为0.3 mg/m3以上部分的气体浓度分布图，之所以设置阈值是为了消除气体传感器噪声对气体源定位过程的影响。图中右侧的颜色栏中从深到浅再到深表示气体浓度逐渐变大。从图中可以看出：气体浓度最大值位置近似于气体源位置；随着高度的增加，气体浓度也随着快速下降；随着下风向(x轴正向)距离的增加，气体浓度也快速下降，并在y轴方向上向两边扩散。所以图中浓度大的区域被浓度小的部分所包围，不容易看出来，但总体的趋势是比较明显的。

2.2 气体源定位仿真

本文的仿真实验是在windows7操作系统上利用Matlab-R2014a科学计算软件进行的。实验采用基于GAUSS烟羽模型的三维仿真环境，相关参数如2.1节所示。实验中设无人机的数量m=3，随机投放在：28 m≤x≤30 m，8 m≤y≤10 m，8 m≤z≤10 m范围内，由图3可知该区域没有烟羽信息，以便于验证算法的烟羽发现能力。具体仿真参数见表1。

表1 仿真参数

三维空间的自适应气体源定位方法的目标是协调多无人机在三维空间中以少量迭代次数定位到气体泄漏源的位置。图4为在相同参数设置下，基于基本烟花算法和改进烟花算法的气体源定位过程对比，由于定位过程中产生的采样点数较多，这里分别选取其中四次迭代的主无人机和其采样点位置进行对比分析，k1代表第一次迭代。

图4 基本烟花算法和改进烟花算法定位过程

图4(a)、图4(b)可以看出，两种方法的前两次迭代均处于烟羽发现阶段，主无人机k1:MasterUAV和k2:MasterUAV都在其最大采样范围r内随机产生对应的采样点k1:Sample dot1～4和k2:Sample dot1～4，对目标空间进行覆盖式搜索，进而进行烟羽发现。从图4(a)可以发现基于基本烟花算法的气体源定位过程中的第8次和第13次迭代，主无人机没有产生对应的采样点，是因为此时为烟羽跟踪阶段，主机器人的采样范围根据式(5)计算近似为0，所以无法产生有效的采样点对烟羽进行跟踪。而从图4(b)可以看出，在基于改进烟花算法的气体源定位过程的第7次和第10次迭代中，主无人机在一个相对较小的爆炸半径内产生了采样点数上限的采样点，可以有效地对烟羽进行跟踪。为了展现基本烟花算法和改进烟花算法的三维空间自适应气体源定位方法的搜索效率和稳定性，本文进行了50次实验，对比结果如图5所示。

图5 两种方法搜索效率和稳定性对比

图6 气体源搜索路径和浓度分布

图6(a)所示三维空间自适应气体源定位方法的主无人机的路径，显示了主无人机以较快的速度趋向于气体泄漏源，体现了算法具有较快的定位效率。图6(b)所示两个辅助无人机UAV1和UAV2在气体源定位过程中的路径，显示了辅助无人机在每次迭代中都针对当前迭代中未搜索的区域进行探索，以辅助主无人机找到整个目标空间的浓度最大值位置。从图6(c)中所有无人机在定位气体源过程中的气体浓度变化趋势可以看出，前几次迭代中由于没有气体信息，所有无人机以覆盖式搜索的方式进行烟羽发现，一旦有无人机检测到气体则所有无人机自适应的进行烟羽跟踪，在这个阶段，主无人机一直向气体浓度高的梯度方向前进，与前文中基于GAUSS模型的三维空间气体浓度分布仿真图相吻合，直到主无人机的浓度值大于等于气体源阈值Ot=100mg/m3时，所有无人机自适应的进入气体源确认阶段，经过Tt=4次迭代判断，主无人机的位置均小于dt=0.2m，算法终止，输出主无人机的位置。实验结果表明了该方法可以在三维空间中自适应地进行烟羽发现、烟羽跟踪以及气体源确认，进而定位到气体源，其中两个辅助无人机的移动过程并不依赖于气体浓度，只依赖于种群中个体的分布，从而在整个空间进行随机搜索，避免整个无人机系统陷入局部浓度最大值位置。

2.3 定位方法中参数的影响

2.3.1 无人机初始位置对定位效率的影响

无人机的初始位置往往会对算法的定位效率产生一定的影响，本文针对这一影响进行讨论。表2为设置的无人机的5个不同的初始位置范围L1～L5。

表2 无人机初始位置

使用3个无人机，以L1～L5为初始位置范围，在基于GAUSS模型的三维仿真环境中，分别进行50次气体源定位仿真实验，取其定位到气体源需要的迭代次数的平均值如图7所示。

图7 不同初始位置对定位效率的影响

可以看出，本文所提方法对初始位置不太敏感。初始位置范围为L1时的定位效率最高，这是因为该位置范围就在烟羽中，算法没有进行烟羽发现，直接对烟羽进行跟踪定位，所以定位效率最高。从L2到L5，定位到气体源所需的迭代次数有稍微增加，这是因为其初始位置范围与烟羽和气体源的相对距离越来越远，之所以会缓慢增加，是因为算法的烟羽发现能力很强，而且距离梯度也不是很大，所以其定位效率不会随着初始位置范围与烟羽和气体源的相对距离增大有很明显的变化。

2.3.2 不同η取值下无人机数量对定位效率的影响

本文针对不同η取值下无人机数量对算法定位效率的影响，通过设置不同η取值下的不同数量的无人机，分别进行50次实验，统计算法定位到气体源所需迭代次数的平均值如图8所示。

图8 不同η取值下无人机数量对定位效率的影响

根据图8可以看出，当火花计算公式系数η取值不变时，随着无人机数量的增加，算法定位到气体源所需的迭代次数先减少后，又稍有增加进而趋于稳定。其中，迭代次数减少的原因是：当无人机数量较少时，虽然根据式(6)计算Ni相对较大，但为了避免好的无人机产生过多的烟花，造成对局部区域的重复搜索进而浪费资源，所以设定了采样点数的上限为ηu=4，因此也造成了当无人机数量较少时其定位效率很低。而当无人机数量增加到3架之后，在稍有增加后，进而趋于稳定，这是因为η是固定值，因此每次迭代的采样点数量是固定的，随着无人机数量的增加，每个无人机得到的采样点数目减少，同时目标环境的范围是确定的，无人机越多，其覆盖的范围就大，致使有部分采样点越界，此外无人机各自的采样区域重复的部分就越多，越界处理后的采样点以及个无人机重复的采样区使的采样点位置重复或相互间距离过近的概率增加，这些点被处理后，总的采样点数减少，从而降低了方法的定位效率，但当每个无人机所获得的采样点少到一定程度，这种概率就趋于平衡，所以方法的定位效率逐渐趋于稳定。从图中可以看出，在目标环境的长、宽、高分别为30 m、20 m和10 m条件下，当无人机的数量定为3架时，其定位效率最高。

此外，分析图8可知，在无人机的数量一定时，随着η的增加，算法定位到气体源所需迭代次数的总体趋势是先减少后趋于稳定，但是变化的幅度很小，这是因为每个无人机的采样点数是有上限的，所以在无人机数量一定的条件下，其只能在较小的范围内提高算法的有效采样点，致使算法的定位效率有较小幅度的提高后趋于稳定。

3 结束语

三维空间的气体源定位方法的研究，相对于二维平面的研究，更符合气体在实际环境中的传播特性，因而更有利于解决实际应用的需求。本文针对已有的气体源定位方法大多都忽略了气体在三维空间扩散的实际情况，而将其降为二维进行研究，并需要切换不同方法完成不同阶段的任务的问题，提出了利用改进烟花算法协调多无人机在三维空间自适应地进行气体源定位的方法。首先，针对基本烟花算法中主无人机无法对烟羽进行有效跟踪的问题，通过引入自适应爆炸半径机制，在气体源定位过程中动态的调整主无人机的采样范围，使其能够有效地对烟羽进行跟踪，并通过实验验证了改进后的方法具有良好的稳定性和较高的定位效率。然后，又通过仿真实验验证了所提方法不仅具有高效的烟羽发现和烟羽跟踪能力，而且能够根据气体浓度信息自适应进行烟羽发现、烟羽跟踪以及气体源确认，进而快速高效完成气体泄露源的定位。最后，分别针对无人机的初始位置以及不同η取值下无人机数量对算法定位效率的影响进行了实验分析，实验结果表明在目标环境的长、宽、高分别为30 m、20 m和10 m条件下，无人机为3架时，所提方法的定位效率最高。同时该方法只需要利用浓度信息即可完成气体源的定位，因而，无论是分子扩散主控的环境下以及无法测到有效风信息的湍流主控微弱流体环境下，还是湍流主控环境下，均可适用，具有很好的普适性。