基于无人小车嗅觉的混合型气体溯源定位算法

董文轩，陈建国，黄 宇，苏国锋

（1.清华大学工程物理系，北京100084；2.北京信息科技大学自动化学院，北京100192）

1 引 言

气体源定位是通过测量监测节点的气体浓度，结合定位算法估计气体泄漏源位置的技术［1］，主要应用于火灾早期监测和危险气体泄露预警，有助于应对城市管网老化、复杂化等现象带来的安防挑战。近年来，由于低成本、低功耗的传感器网络的普及，国内外出现了一系列方法多样的气体溯源定位研究。源定位算法是无人系统溯源技术的核心部分，其根据传感器测得的部分历史数据，计算出运载器当前的移动目标，并经过迭代最终预测泄露源位点。

当前，国内外研究人员主要采用机动式传感器（群），在无人运载器上构建机器主动嗅觉，结合动态路径规划算法，从而使无人系统经过迭代达到最优化位置。传统的嗅觉算法包括瞬时浓度梯度法、单纯形搜索法、半随机移动法、Z字型搜索法等［2-3］。此类算法一般认为气体分布具有平滑的浓度梯度，可供利用对烟羽进行跟踪定位；算法的搜索步长一般保持固定，系统逐步前进，移动速度慢，智能化程度较低。Hayes 提出的外螺旋（SS）算法，基于多风源的湍流环境进行设计，摆脱了对于局部浓度梯度的依赖，并且经过了实验验证［4］，但其在搜索路径效率和气体源确认上仍有不足。李飞将生物遗传和进化观点引入定位算法之后，国内相继出现大量群智能算法，如蚁群算法、粒子群算法等［5］，全局搜索能力和收敛精度持续提高。然而，此类算法对环境的已知信息量的要求普遍提高，需要在连续的栅格内采集数据，影响了算法在大型区域内的可用性。

受限于被动式传感器的气敏性能，无人小车用于采集浓度数据的时间不可忽略。低浓度传感器的响应时间参数和溯源路径上的检测节点数目，是制约目前算法溯源能力的首要因素。由于高昂的时间成本，现有算法主要面向室内搜寻场景，实验场地的典型尺度在10m 以下［6］，始终受限于较小场域空间和特定的扩散场模型，在很大程度上难以满足大型工业场地的使用需求。因此，现阶段气体源定位算法研究的主要矛盾，即是气体扩散行为的复杂性与安保时间紧迫性之间的矛盾。

如何在检测位点尽可能精简的前提下，控制合理的搜索范围，同时保证溯源定位的高精度和高成功率，是本文的研究目标。本文以搭载单个浓度传感器的智能小车为例，聚焦于准静态浓度场的平面搜寻场景，对三边定位法和单纯形算法两种传统算法加以改造和整合，提出一种不依赖于先验知识的混合型溯源定位遗传算法。

王巍等认为，目前气体源定位方法的普适性不强，针对湍流环境的气体源定位方法大部分具有风信息依赖性，而针对分子扩散环境和湍流主控微弱流体环境的方法，会因为失去连续的浓度梯度而无法对气体源进行定位［7］。本文算法弱化了对风信息和梯度信息的依赖，对于解决不同流场环境的普适性问题具有一定的启示意义。

2 问题描述

假设无人系统由n辆无人小车组成，在未知的平面环境中搜索，问题可以描述为：

（1）E=｛（i，j）|i=1，2，…，Lx，j=1，2，…，Ly｝为一个矩形待搜索区域，区域内存在一个气体源，坐标未知；

（2）每一个坐标网格对应一个气体浓度值c（i，j|t），在比较稳定的浓度场里，浓度c近似不随时间变化，假设气体源所在网格的浓度值最大；

（3）用x表示坐标位置，代替实数对（i，j）；用data或DATA表示一组坐标数据x和该位置处的浓度数据cx组成的结构体变量；

（4）无人小车n辆，配备了相同的传感器和通讯设备，当小车在某一位置静止时，可以测得此处的浓度值；

（5）通过算法对测量结果以及坐标数据进行计算，获得小车的运动路径，使之快速抵达泄露源点。

3 混合型平面溯源定位算法的设计

3.1 三边定位-单纯形算法

为了提高求解的科学性和保证逐代优化的趋势，保存一些节点的数据，并且使用遗传进化思想是有必要的。然而，根据前述精简测量节点的原则，并考虑到历史测量值的时效性，应优先选用信息量需求较小的算法。

针对平面溯源问题，现存两种简单的算法，即三边测量定位算法（Trilateration）和单纯形算法（Simplex Algorithm）［8］。两种传统算法均采用三组坐标位置的数据进行迭代计算，且具备良好的优势互补特征，在此基础上提出混合型算法，可以有效兼顾搜索效率和收敛稳定性。

3.1.1 启发式的三边定位求解

三边定位法的基本假设认为，平面内任意一点与源点的距离r，和该点的浓度值c呈负相关关系。由此，可以通过三点浓度的测量值来建立以下的平面距离关系：

以三个测量点为圆心，给定半径的比例关系画圆，当计算得到三个圆的共交点时，即作为预测源点位置的更新值。在本实验场景中，由于缺乏先验模型，使得方程组（1）不封闭，共交点的求解经常无法唯一确定（如图1），最多可能存在4个可行解。合适的半径取值需要用试值法得到。考虑到溯源起点通常位于浓度场边缘，实验认为，按照从大到小的方式试值，优先选用半径较大的解有利于提高搜寻效率。

图1 三边定位法多解示意图Fig.1 Trilateration method and possible multiple solution

具体的求解及筛选过程如下：

步骤一：定义三个圆Oi（i=1，2，3）的半径为ri，其中r3最大，在三个圆两两有交点的前提下，从大到小对半径进行试值；

步骤二：半径被赋值后，计算O1与O2的两个交点，选出距离O3的圆心较近的一个；

步骤三：计算该交点的坐标与半径r3是否匹配，即是否是三圆的共交点，若不匹配，本次试值失败，更改半径的赋值并重复以上过程。

三边定位算法在预测源点方向上具有启发式的意义，有助于弥补单纯形算法的不足。在长距离搜索过程中，初始化三角形远小于浓度场的几何尺度，单纯形算法易表现出搜索点分布特征单一、方向性差、自由度下降或退化为一维搜索、逐代移动步长非严格递减、易于陷入局部最优等特点（如图9）。而三边定位解在调整移动步长、跳出局部最优上具备优势，有效缓解了单纯形算法发生失效的概率，将搜索能力维持在较高水平。

3.1.2 改进的单纯形求解

单纯形求解与三边定位法使用相同的三个测量数据点，该算法认为，气体源的预测位置在三角形的一条中位线及其延长线上，这条射线经过浓度最低的顶点（如图2）。标准的三边定位法是不收敛和不可靠的，其解空间严重不完备。由于一般的浓度场与无风情况下的理想点源扩散模型差距较大，任取三点易陷入无解情况，或共交点位置超出场地范围，进而对算法的可用性造成损害。实验中以第一代初始化数据代入该算法，计算成功率仅达20%左右。

图2 基本的单纯形算法Fig.2 Basic simplex algorithm

本文算法利用此特点，辅助单纯形算法进行条件句判断，以代替其传统的判断方式［9］，减少路径规划中的冗余折返。判断逻辑见3.1.3 节的伪代码。假设三边定位计算成功，则定义该计算处于启发定向阶段；若失败，则定义处于保守的梯度步进阶段。以下分别介绍两种阶段下的单纯形求解步骤。

（1）启发定向阶段

如图2示，xL为最小值点坐标，xG、xH为另两个顶点的坐标，直接求解xext的坐标即为单纯形解。

（2）梯度步进阶段

此阶段中，三边定位法处于失效状态。单纯形算法宜取xmid和xext之间的点作为较保守的解，以确保算法运行的安全性。此外，为了缓解单纯形算法中搜索区域缩小的问题，在该步骤中加入了随机性因素，伪代码见3.1.3节。

3.1.3 两种算法的混合求解

本节以伪代码的形式，给出了三边定位-单纯形算法进行一次计算的完整步骤。其中，混合型算法在梯度步进阶段直接取单纯形解；启发定位阶段的最终解，取三边定位解与单纯形解的加权平均值，这样既充分发挥了三边定位的启发性作用，也可以过滤掉搜索步长相对过大的解［10］。实验选取加权参数k=0.35。

此外，有且仅有一种情况三边定位法与单纯形算法同时失效，即三组亲代数据点位于同一坐标方格中。算法特别定义，在此状态下，输出的子代坐标点于该方格附近一定距离处随机跳动，从而实现跳出局部最优解，继续在周围保持一定范围的游走。游走距离可以根据实际流场条件进行规定，在本实验中设置为5m。

3.2 遗传进化结构

为测试以上算法的可行性，首先进行了一次预实验。实验使用混合型平面溯源定位算法，输入任意一张浓度场分布图，初始化三个数据点进行遗传迭代。结果表明，如果只使用三组数据点，路径节点会迅速形成共线，陷入一维的局部搜索，溯源效果与单纯形算法基本无异。图3（a）中显示了预实验前50代的搜索目标点，坐标单位为0.4m，可见其分布过于紧密。图3（b）为搜索路径的局部放大图，算法初步具备了步长调节和跳出共线的能力，但很快又陷入共线状态。

由此可见，三边定位-单纯形算法的求解质量并不高，而低质量的迭代会使算法向基础的单纯形算法退化，收敛速度极慢，甚至定位失败。如果在遗传过程中适当扩大备选子代的规模，杀死一些低质量的种群，则能够有效维护算法的有效性，提高算法鲁棒性。

为解决上述问题，算法引入了排列组合策略，使用五组数据点进行遗传迭代。图4左侧表示亲代数据集，其中2～5号数据点按照浓度大小降序排列。图5所示为遗传进化算法的流程图。

图3 预实验前50代搜寻点分布图Fig.3 Distribution of search points of 50 generations in pre-experiment

图4 引入排列组合策略的数据遗传结构Fig.4 Data genetic structure introducing combination strategy

混合型算法进行一次运算需要使用三组数据，第一组数据固定选取图4中的DATA1，余下两组从2～5 号数据点中任选，可以取出总计C（4，2）= 6 种组合形式，即得到六组不同的子代（如图4右侧data1～6）。无人小车抵达六个目标点进行探测，选取其中浓度值最大的点，用来更新亲代数据集。

亲代数据集的更新方法为，先用DATA1 替代浓度较低的DATA5，然后以最优子代作为DATA1的更新值，最后对DATA2～5 重新定序。这种更新策略有效地维护了数据的优化趋势，DATA2～4 三组数据分别随迭代次数非严格递增，该特征可以作为判断溯源结束的标志；而锁定DATA1 的组合方式，保证了逐代计算中，至少有一组数据点始终保持更新，子代之间几乎不产生重复计算，这有助于维护亲代数据集的更新能力，从而加快收敛速度。

4 建模及参数设置

4.1 点源泄露气体扩散模型

本文采用经典的高斯扩散方程对气体扩散过程进行模拟，适用于大多数气体探测场景的需求［11］。同时，为了体现浓度场分布的一般性特点，尽量减少场的先验形状对算法的影响，在计算中引入了时变因素，模拟了在二维平面（z=0）内0～750min的扩散过程。

实验假设，气体源由1500 个位置相同、相互独立的点源，在时间维度上相继连续触发所形成，任一时刻浓度场视为1500个点源浓度场的代数叠加。每个源在初始化位置上泄露30s，形成稳定的高斯烟团；泄露时间结束以后，在设定的风力作用下，烟团中心在平面内以一定速度和方向漂移。依此过程，最终形成时间颗粒度为30s 的变源强、变风向、变风速的开阔区域气体扩散模型。如图6所示，气体源高度0.25m，坐标位置（5m，50m），中心区域气体浓度达到10-4kg/m3量级。

仿真实验条件为准静态场，不考虑小车在溯源过程中引起的浓度变化，故只选取任一时间切片的浓度场分布数据作为静态索引对象。

4.2 小车及运动场地模型

仿真实验场地设置为100m×200m 的开阔平地区域；坐标网格以0.4m为单位刻度，将场地划分成250×500 个方格，所有实验采用同样的地图作算法的验证。

在平面内运动的智能小车，理论上自由度为3。实验中为了适当降低路径规划的难度，将小车模型简化为自由运动质点，并且省略了运动场地中的障碍物。参考算法过程可以说明，作出该简化是合理的。给定小车的典型平均速度为2m/s。小车数量与迭代计算过程无关。

智能小车上搭载有浸入式的气体浓度传感器探头。以低浓度甲烷探测器为例，市场现有探测器每次测量的最短响应时间约5s［12］。在测量时间内，假设小车于测量点处静止。

5 仿真结果及分析

5.1 场外巡检与烟羽发现

本文数字仿真实验基于MATLAB 环境。单次实验中，随机设定任一时刻的气体浓度场，设定小车位置起始点在场地边缘（如图7右上角），风速、风向为已知条件。

图6 不同时刻下的点源气体扩散浓度场模型Fig.6 Point source gas diffusion concentration field model at different moments

图7 场外搜寻及烟羽发现路径模拟Fig.7 Off-site search path simulation

无人系统溯源过程，通常可以划分为烟羽发现、烟羽追溯、确认气体源三个阶段。在前溯源阶段，小车沿逆风向对全场进行Z字形排查搜索［13］，如图粉红色虚线为初次路径规划轨迹。重规划使用贝塞尔曲线，将小车的模拟运动轨迹处理成黑色光滑曲线，红色六角星表示小车位置，算法在此处达到浓度探测阈值（实验设置为10-6kg/m3），进入溯源定位阶段。

二阶贝塞尔曲线表达式为：

其中，p0、p2为各段局部路径的起点和终点，p1为控制点。

5.2 溯源定位算法仿真

小车模型进入浓度场之后，继续在同一准静态场中运动，使用本文混合型平面溯源定位算法执行迭代过程。本实验设定，当DATA2、DATA3、DATA4三组数据经过5 次迭代不再更新时，小车退出迭代算法，输出源点坐标及浓度［14］。图8为部分仿真结果，实心圆点表示溯源算法中所有子代的坐标数据，即小车搜索过的目标点，虚线代表小车运动经过的平均路径。实验表明，输出数据在源点所在方格处（浓度最高）精确收敛。

为保证实验的可重复性，研究选取150～500min内不同时间的浓度分布场共进行了100组实验。结果显示，在绝大多数场景下，本文算法精确溯源的成功率为100%，迭代次数稳定在20～45 代左右，预计溯源时间为750～1400s；平均路径与烟羽的飘散方向基本吻合，在不具备先验知识的情况下，较好地符合了烟羽的形状，满足了对提高搜寻效率的要求；小车搜索的目标点分布在平均路径附近，拐点处和终点处分布增多；退化成一维的共线状态偶有出现，该现象对溯源结果的精确性不造成影响，但会使迭代次数明显增加。

作为对照，本文还单独使用了两种传统算法进行了实验，该实验使用了完全相同的组合数遗传框架。三边定位法的计算失败概率过高，无法形成有效的搜索路径；单纯形算法的搜索路径不光滑，中后段明显退化成一维搜索（如图9），逐渐向传统的单纯形算法过渡，且迭代次数多，溯源成功率约50%。

图8 混合型平面溯源算法仿真路径图及迭代次数Fig.8 Simulation path of hybrid traceability algorithm(n for number of iterations)

图9 传统单纯形算法仿真路径图（60代）Fig.9 Simulation path diagram of traditional simplex algorithm

5.3 路径规划方案分析

无人车的规划路径以代际为单位，每一次迭代包含6个搜索目标点，无先后顺序，故整个溯源路径问题可以分解成为数十次连续的多目标路径规划问题。而路径确定之后，根据小车的运动速度和传感器测量时间，就可以估算得到完成一次溯源任务的时间成本。选择不同的路径规划方案与迭代计算结果无关。

由于运动场地模型中不存在障碍物，可以粗略地用两点连线的方式代表小车运动路径。对于任意一代目标点，共存在720种路径选取方式，容易选出长度最短的一条作为单个小车的规划路径（如图10）。这种路径规划方式存在一定的路径折返，增加了不必要的时间成本，使用一辆小车的无人系统基本无法避免此类问题。

图10 一辆无人小车溯源规划路径图（n=26）Fig.10 Trace route of one unmanned vehicle

一种优化方式是通过增加无人车的数量，以及建立多辆车之间的通信系统，合理分配运动目标点和测量时间，同时减少路径折返现象的发生。不同的车之间需要保持同步性，即当一代6 个目标点全部测量结束后，再开始次一代计算。实验中采取了两辆车的规划方案，每辆车在一次迭代中测量3 组坐标下的浓度数据。仿真路径如图11。

图11 两辆无人小车溯源规划路径图（n=35）Fig.11 Trace route of two unmanned vehicles

实验在8 组不同浓度场条件下，分别使用以上两种路径规划策略，对平均路径长度、时间成本进行了统计和对比（表1）。算法平均迭代39.89次，两车路径规划方案比一车规划的场内迭代时间节省了47.9%，完成全部溯源过程的时间成本平均下降了43.6%；和改进的蚁群算法比较，在同尺度场地、相同定位精度、同样使用两辆无人小车的条件下［5］，系统的溯源效率提高了约91.0%。

6 结 论

本文提出的混合型三点定位算法与传统算法相比，体现出诸多改良和创新性，在运行稳定性、结果可靠性和搜索效率上均有所突破，大大提高了两种算法的实用性。三边定位、单纯形算法和组合遗传策略，这三者对于各自的劣势形成了互相弥补的结构。三边定位法通过其定向能力、步长调节能力，改善了单纯形算法的搜索缓慢、单一化和路径折返问题；组合遗传策略，补偿了三边定位法中计算失败的概率，确保xtr解在逐级迭代中发挥持续的作用，也为单纯形算法提供了多样性的选择，避免搜寻轨迹过早地陷入共线状态；单纯形算法利用了一部分浓度梯度信息，保证了算法系统的运算安全性。

该算法的优势首先在于测量节点少，效率高，机动性强，使搜索步长具有了自我调适能力。在烟羽追溯阶段，搜索步长没有明显下降，维持了快速移动的能力；在算法趋于收敛的阶段，搜索步长逐渐下降，从而获得高精确性。本算法现阶段达到的效率和搜索场域大小，已经基本符合无人小车的移动特征和现实需求。而现有算法以改进的蚁群为例，小车在溯源路径上逐点探测，搜索步长小于定位精度，在现有的传感器条件下导致高昂的时间成本，可能花费数个小时才能完成一次定位。这一特点是本算法相较于蚁群等算法的主要优势，也是现有算法无法突破场地大小限制的核心原因。

其次，本算法具有收敛性。使用亲代数据的定序排列作为判断溯源结束的标志，保证了数据更新的优化趋势，避免了各种群智能算法和加权质心法中，迭代次数过多导致定位远离源点的情况。五代不更新的判敛条件是经验结果，为保证收敛的可靠性，需要避免算法陷入共线陷阱，防止发生过早收敛。

由于本算法在运算中利用的数据点较少，数据即时性较强，因而使系统的时间敏感性有所降低，提高了计算结果的可靠性。经遗传结构保存下来的亲代数据，基本上都是2～3min 以内的测量结果，在变化不太剧烈的浓度场中基本符合静态特征。

最后，由于该算法摆脱了对风信息的高度依赖，也没有形成对梯度信息的绝对依赖，故可以认为其对于非湍流环境、湍流主控微弱的环境和湍流环境都具有一定的兼容性和适应性。这一猜想仍有待实验验证。

本文在某些细节上仍然有待进一步改进，特别是有关维护溯源定位过程不进入共线状态的方法。当算法陷入共线状态时，容易失去三边定位能力，近似退化为单纯形算法，对算法的溯源能力形成一定的制约。与传统算法相比，本算法在克服共线问题上已经得到了大幅改善，但实验中，初始化亲代数据和参数的选取方式等可能都对结果造成一定的影响。亦可以引入禁忌表或斥力因素等，保持亲代坐标点的离散状态，使算法跳出共线陷阱。

表1 一辆小车与两辆小车路径规划的平均时间成本Table1 Average time cost of one-car path planning and two-car path planning