计算机应用   2017, Vol. 37 Issue (12): 3614-3619  DOI: 10.11772/j.issn.1001-9081.2017.12.3614
0

引用本文 

梁志刚, 顾军华, 董永峰. 基于头脑风暴优化算法的多机器人气味源定位[J]. 计算机应用, 2017, 37(12): 3614-3619.DOI: 10.11772/j.issn.1001-9081.2017.12.3614.
LIANG Zhigang, GU Junhua, DONG Yongfeng. Multi-robot odor source localization based on brain storm optimization algorithm[J]. Journal of Computer Applications, 2017, 37(12): 3614-3619. DOI: 10.11772/j.issn.1001-9081.2017.12.3614.

基金项目

天津市科技计划项目(14JCYBJC18500,14ZCDGSF00124)

通信作者

顾军华, E-mail:jhgu@hebut.edu.cn

作者简介

梁志刚(1982-), 男, 河北正定人, 讲师, 博士研究生, CCF会员, 主要研究方向:智能信息处理、计算机视觉;
顾军华(1966-), 男, 河北赵县人, 教授, 博士, CCF会员, 主要研究方向: 智能信息处理、计算机视觉;
董永峰(1977-), 男, 河北定州人, 教授, 博士, CCF会员, 主要研究方向:智能信息处理、移动机器人

文章历史

收稿日期:2017-06-05
修回日期:2017-08-16
基于头脑风暴优化算法的多机器人气味源定位
梁志刚1, 顾军华1,2, 董永峰2    
1. 河北工业大学 电气工程学院, 天津 300401;
2. 河北工业大学 计算机科学与软件学院, 天津 300401
摘要: 针对现有室内湍流环境下多机器人气味源搜索算法存在历史浓度信息利用率不高、缺少调节全局与局部搜索的机制等问题,提出头脑风暴优化(BSO)算法与逆风搜索结合的多机器人协同搜索算法。首先,将机器人已搜索位置初始化为个体,以机器人位置为中心聚类,有效利用了历史信息的指引作用;然后,将逆风搜索作为个体变异操作,动态调节选中一个类中个体或两个类中个体融合生成新个体的数量,有效调节了全局和局部搜索方式;最后,根据浓度和持久性两个指标对气味源进行确认。在有障碍和无障碍两个环境中将所提算法与三种群体智能多机器人气味源定位算法进行定位对比仿真实验,实验结果表明,所提算法的平均搜索时间减少33%以上,且定位准确率达到100%。该算法能够有效调节机器人全局和局部搜索关系,快速准确定位气味源。
关键词: 气味源定位    湍流环境    多机器人    头脑风暴优化算法    逆风搜索    
Multi-robot odor source localization based on brain storm optimization algorithm
LIANG Zhigang1, GU Junhua1,2, DONG Yongfeng2     
1. School of Electrical Engineering, Hebei University of Technology, Tianjin 300401, China;
2. School of Computer Science and Engineering, Hebei University of Technology, Tianjin 300401, China
Abstract: Aiming at the problems of the odor source localization algorithms by using multi-robot in indoor turbulent environment, such as the low utilization rate of historical concentration information and the lack of mechanism to adjust the global and local search, a multi-robot cooperative search algorithm combing Brain Storm Optimization (BSO) algorithm and upwind search was proposed. Firstly, the searched location of robot was initialized as an individual and the robot position was taken as the center for clustering, which effectively used the guiding role of historical information. Secondly, the upwind search was defined as an individual mutation operation to dynamically adjust the number of new individuals generated by the fusion of selected individuals in a class or two classes, which effectively adjusted the global and local search methods. Finally, the odor source was confirmed according to the two indexes of concentration and persistence. In the simulation experiments under two environments with and without obstacles, the proposed algorithm was compared with three kinds of swarm intelligent multi-robot odor source localization algorithms. The experimental results show that, the average search time of the proposed algorithm is reduced by more than 33% and the location accuracy is 100%. The proposed algorithm can effectively adjust the global and local search relations of robot, and locate the odor source quickly and accurately.
Key words: odor source localization    turbulent environment    multi-robot    Brain Storm Optimization (BSO) algorithm    upwind search    
0 引言

机器人气味源定位或化学烟羽追踪问题[1-3],又称为机器人主动嗅觉,是指利用配备了气味传感器的移动机器人跟踪气味分子扩散轨迹,最终定位并确认气味源所在位置的过程。许多问题都可以归结为气味源定位问题,例如有毒/有害气体泄露检测、污染源检测、火源探测、反恐排爆和灾后倒塌建筑物搜救等[4]。机器人与受过训练的人或动物相比,具有不易疲劳的特点,并且可以工作在剧毒、强腐蚀性等高危环境,因此机器人气味源定位技术具有广阔的应用前景。

机器人气味源定位算法的研究,集中在搜索过程中机器人运动策略的研究。气味源定位算法可以分为基于单机器人的生物启发算法、工程方法和基于多机器人的群体智能协同搜索算法。生物启发式算法模仿生物在觅食、寻找同伴时的化学趋向性和风趋向性特点,利用单个机器人实现气味源定位任务。张小俊等[5]利用配备气味和风速传感器的机器人模拟动物捕食行为,采用“Z”字形和神经网络算法融合的搜索策略实现了对于酒精气味源的准确定位。Li等[6]模仿飞蛾运动特性,实现了水下机器人在水中的定位任务。工程学方法利用机器人测量的浓度、风力信息,采用信息论、概率论和流体力学等方法动态估计气味源所在位置,实现气味源定位。Kowadlo等[7]应用贝叶斯理论构建多假设树进行气味源搜索,并在基于朴素物理学的封闭流场环境中验证了该算法的有效性。李吉功等[8]通过概率方法对气味包可能走过的路径进行计算,反向追踪路径源头实现了气味源定位。

有学者利用群体智能算法协调多个机器人运动,进行了多机器人气味源定位研究。相比单机器人定位算法,多机器人群体智能算法具有定位时间短、搜索效率高、鲁棒性好、可扩展等优点。Hayes等[9]首先对于多机器人气味源定位算法进行了研究,提出基于多机器人的外螺旋线搜索(Spiral Surge, SS)算法。Jatmiko等[10-11]研究了检测与响应粒子群优化(Detection and Response Partical Swarm Optimization, DRPSO)和带电电荷粒子群优化(Charged Partical Swarm Optimization, CPSO)算法,并应用Farrel建立的湍流烟羽仿真模型对算法性能进行了研究。孟庆浩等[12-13]研究自适应蚁群优化与逆风搜索相结合(Adapted Ant Clony Optimization combined with Upwind Surge, AACOUS)算法,分别在仿真和真实机器人平台验证了算法的有效性。张勇等[14]应用骨干微粒群进化的多机器人协作实现了对于噪声环境下气味源的定位。Wang等[15]等将改进布谷鸟算法结合逆风搜索,仿真实现了室内湍流环境下气味源定位。李飞等[16]建立基于贝叶斯和变论域模糊推理表达的适应度函数值,结合风速和气味浓度,实现了概率适应度函数粒子群优化算法气味源定位。上述算法存在以下两方面的问题:一是机器人搜索策略单一,算法缺少调节进行全局或局部搜索机器人数目的机制,搜索初期加强全局搜索,后期加强局部搜索可以显著缩短气味源的定位的时间。二是算法仅仅根据机器人当前位置气味浓度信息确定下一步运动方向,缺乏历史浓度信息对当前搜索行为的指引作用。

近年来,一种模仿人类解决复杂问题的群体智能算法——头脑风暴优化(Brain Storm Optimization, BSO)算法受到越来越多关注。BSO由Shi[17]于2011年提出,该算法是基于人们创造性解决问题的方法——头脑风暴过程(Brainstorming Process)启发演化而来。BSO算法能够较好平衡全局搜索和局部搜索能力,在很多优化问题上取得了成功,应用BSO算法对于经典测试函数进行仿真验证,实验结果表明了BSO算法在单模和多模优化问题中的有效性和效率。Duan等[18]提出捕食者-猎物BSO(Predator-Prey BSO, PPBSO)算法,在解决直流无刷电机优化问题上能够快速准确找到全局最优值。Sun等[19]提出了一种闭环BSO(Closed-Loop BSO, CLBSO)算法,成功解决了二冲量控制的多卫星编队再配置问题。Duan等[20]引入量子机制对BSO(Quantum-behaved BSO, QBSO)算法进行改进,解决了螺线管优化问题。杨玉婷等[21]将带差分步长的BSO(BSO with Differential Step, BSO-DS)算法应用于隐马尔可夫过程的训练,极大提高了运动视频识别的准确率。在这些领域的成功应用表明了BSO算法在解决优化问题时的优异效果。算法的分类机制和个体更新方式能够对于全局和局部搜索进行灵活调节,该机制显示了BSO算法在其他优化领域具有巨大的应用潜力。

本文将BSO算法应用于室内湍流环境下多机器人气味源定位问题,提出了一种改进的BSO(Modified BSO, MBSO)算法,与逆风搜索相结合协调机器人的运动实现气味源定位任务。MBSO算法将机器人搜索轨迹上坐标点作为算法个体,该位置测得的气味浓度作为适应度值,极大保留了历史浓度信息,通过调节类内和类间生成新个体的数量动态调节全局和局部搜索关系。为了验证算法的有效性,应用Fluent建立了室内动态无障碍/有障碍两种计算机仿真模型,进行了气味源定位仿真实验。仿真结果表明,本文算法可以实现动态烟羽环境下气味源的快速、准确定位。

1 室内湍流环境烟羽模型建立

室内湍流环境下气味的浓度场受到湍动气流支配,浓度是关于位置、时间等因素的多元函数。机器人气味源定位时,气味传感器在同一水平高度上,浓度场可以简化为二维平面内的二元函数,浓度值C数学描述如下:

$C=f(\mathit{\boldsymbol{X}},t)$ (1)

其中:X=(x, y)为机器人坐标;t为测量浓度的时间。障碍物的存在和风速的变化使得湍流主控环境下浓度场更加复杂多变,流场的烟羽具有时变和间歇的特性,容易在局部聚集形成浓度极值点。这就造成浓度梯度在时间和空间上不连续的特性,某个区域内梯度方向通常指向局部极值点而不是气味源。

本文通过计算流体力学(Computational Fluid Dynamics, CFD)软件Fluent建立计算仿真模型,模拟室内具有湍流特性的动态烟羽扩散模型。仿真模型假设室内气体满足理想气体状态方程,考虑窗口和门的对流作用,忽略能量方程中由于黏性作用产生的能量损耗。空气的流动遵循N-S(Navier-Stokes)方程组,选用SIMPLE算法对时均方程进行求解,模拟环境为标准的k-ε模型。气体扩散源选用酒精进行模拟,扩散强度恒定。

仿真环境模拟了二维无障碍物流场Case-1和有3个障碍物流场Case-2两种实验环境,两个环境具有相同基本参数:流场尺寸为10 m×10 m,有2个宽度为2 m的进风口和1个宽2 m的出风口。进风口Inlet-1和Inlet-2位于流场左侧,坐标分别为(x=0,y=[1, 3])和(x=0,y=[7, 9]),出风口Outlet在流场右侧,坐标为(x=10,y=[2, 4])。酒精挥发源坐标为(2,7),挥发速度为200 ppm。两个环境中进风口的风速、风向是关于时间t的函数,随着风速、风向的变化,烟羽的分布也相应发生变化。图 1显示某个瞬间两个环境风速、风向和酒精浓度分布:图 1(a)中两个进风口速度均为1 m/s,方向与x轴平行; 图 1(b)中两个进风口的风速均为0.8 m/s,Inlet-1风向与x轴呈45°夹角,Inlet-2风向与x轴平行,图中三个黑色物体为障碍物。以酒精挥发源为中心的封闭曲线是浓度等高线,浓度值越大的区域对应等高线灰度越深。

图 1 动态湍流烟羽环境瞬时分布 Figure 1 Instantaneous distribution of dynamic turbulent plume environment
2 改进的头脑风暴优化算法

头脑风暴过程是人们创造性解决问题的一种方法,该方法通过聚集不同专业背景的人进行发散思维、思想碰撞、观点融合,以找到问题的最优解决方案。BSO算法是对于头脑风暴过程进行抽象得到的优化算法。

2.1 BSO算法

BSO算法中每个个体代表优化问题的可行解,算法将头脑风暴过程的不同阶段抽象为聚类、变异、生成新个体、选择四种操作,通过四种操作实现对个体更新,最终找到问题的最优解。BSO算法在解的可行域中随机选择n个个体Xi(i=1, 2, …, n)作为优化问题的初始解。确定最大迭代次数Imax,设定算法终止条件。

1) 聚类。

K-means聚类算法将n个个体分成m个类,计算每个个体的适应度函数值,适应度值最好的个体记为该类的中心个体。

2) 变异。

以一定的概率随机选中某个类的中心个体,加上一个随机扰动后替换原中心个体。

3) 生成新个体。

首先产生[0, 1]内的随机数p11,与预先设定的概率参数p1进行比较,根据结果选择以下两种方式产生候选个体Xs :

a)若p11>p1,则随机选中一个类,随机选择类中一个个体,作为产生新个体的候选个体Xs

b)若p11p1,则随机选中两个类,产生一个[0, 1]之间的随机数p12,与预先设定的概率参数p2进行比较,若p12>p2则选择两个类中心个体,否则随机选择两个非中心个体,作为候选个体Xs1Xs2。根据式(2) 融合得到候选个体Xs

${{\mathit{\boldsymbol{X}}}_{s}}=\omega \times {{\mathit{\boldsymbol{X}}}_{s1}}+\left( 1-\omega \right)\times {{\mathit{\boldsymbol{X}}}_{s2}}$ (2)

其中0 < ω < 1,由Xs生成新个体Y如式(3) 所示:

$\mathit{\boldsymbol{Y}}={{\mathit{\boldsymbol{X}}}_{s}}+\xi \times N(\mu ,\sigma )$ (3)

其中:N(μ, σ)是中心在μ、方差为σ的高斯随机函数;ξ为对数S变换函数,如式(4) 所示。

$\xi =\text{logsig}\left( \left( 0.5\times {{I}_{\max }}-{{I}_{c}} \right)/k \right)\times rand(0,1)$ (4)

其中:logsig()为一个对数S变换函数,Imax是算法最大迭代次数;Ic为当前迭代次数;k控制logsig()的坡度;rand()产生一个0到1之间的随机数。

在下文中,选中一个类中个体生成新个体的方法称为a方式生成新个体,两类中个体融合生成新个体的方法称为b方式生成新个体。

4) 选择。

新个体Y生成后,计算Y的适应度函数值,与候选个体Xs适应度函数值进行比较,适应度好的个体进入下一代。重复生成新个体操作,当有n个新个体生成后,进入下一轮迭代过程。当新个体满足最优解条件或达到预先设定的迭代次数时,算法结束。

2.2 MBSO气味源定位算法

MBSO算法中,气味浓度值作为个体适应度函数值。个体初始化方法如下:给定发现阈值C1m个机器人由同一位置沿不同方向进行随机搜索,当气味传感器测量值大于C1时,机器人位置坐标记为问题初始个体。当个体数量大于n-m时,取n-m个适应度值最大的个体加上机器人当前位置坐标组成初始种群,采用MBSO算法协调机器人之间的运动,执行气味源搜索任务。

1) 以机器人为中心的分类过程。

在气味源定位问题中,m个机器人是新个体的发现者,运动至新的位置并检测该点的气味浓度。每轮迭代中,由于每个类至多生成一个新个体,为了提高机器人利用率,最优分类方法是将当前代个体分成m个类,机器人平均分布在m个类中,这样m个机器人同时向各自目标位置运动,生成m个新个体。BSO算法中聚类操作采用K-means算法,算法计算复杂度高,耗费时间长,并且不能保证机器人平均分布于m个类中。MBSO算法采用以机器人为中心的简单聚类算法,流程如下:

① 记第j个机器人为当前坐标为Rj=(rxj, ryj)(1≤jm),分别计算当前代中个体Xi=(xi, yi)(i=1, 2, …, n)与Rj之间的距离:

${{d}_{ij}}=\sqrt{{{\left( {{x}_{i}}-r{{x}_{j}} \right)}^{2}}+{{\left( {{y}_{i}}-r{{y}_{j}} \right)}^{2}}}$ (5)

② 比较个体Xim个机器人之间的距离,将Xi划分至与之最近的机器人类中。

③ 重复以上两个步骤直至所有个体分类完成。

分类完成后将个体坐标气味浓度值记为个体适应度函数值,并确定每个类中心个体。

2) 逆风搜索。

动物在寻找食物过程中,在发现目标气味时采取逆风而上的运动策略。这一策略的逻辑是气味烟羽总是由源头挥发出来,沿着一段时间内气流运动的平均方向传播,风向的反方向大概率是气味源的方向。因此,在MBSO算法中加入逆风搜索,使得算法搜索具有方向性,客观上加快了搜索速度,又可以避免搜索过早收敛到局部极值点。

逆风搜索的方法如下:每轮迭代中,首先找到当前代适应度值最大的中心个体所在的类,属于该类的机器人沿逆风方向运动一个步长的距离vr,生成新个体Xnewvr为机器人最大运动速度。

3) 新个体生成。

BSO算法中:a方式产生的个体大概率出现在所在类附近,适合局部细致搜索;b方式产生的个体大概率出现在两类中间,更适合全局搜索。分析气味源定位问题的搜索过程,可以发现:初期需要加强全局搜索,以b方式产生新个体为主;后期需要在局部进行细致搜索以确定气味源位置,以a方式产生新个体为主.

MBSO产生新个体方式如下:每轮迭代中,将m-1个类划分为两部分,首先确定b方式生成新个体的类,剩余类采用a方式产生新个体。每次迭代采用b方式更新的类设为一个单调递减函数,数量记为Cex,如式(6) 所示:

${{C}_{\text{ex}}}=2\times floor\left( \frac{\left( {{I}_{\max }}-{{I}_{c}} \right)\times \left( m-1 \right)}{{{I}_{\max }}\times 2} \right)$ (6)

其中:Imax是算法最大迭代次数;Ic为当前迭代次数;floor为对有理数向下取整函数。按照式(3) 生成目标个体Y后,m-1个机器人运动模式如下:

① b方式中随机选中一个类,类中机器人向目标个体Y方向移动距离d;

② b方式中未被选中机器人向当前代中适应度值最大的个体运动一个步长的距离vr;

③ a方式生成新个体的类中,机器人向目标个体Y方向移动距离d

综合考虑真实机器人的运动特性,机器人运动距离d如式(7) 所示:

$d=\min \left( {{v}_{r}},{{d}_{i}} \right)$ (7)

其中:vr为机器人最大运动速度;di为机器人与目标个体Y之间的距离。机器人分别按照以上三种模式运动至新的坐标,生成新个体Xnew

4) 选择。

机器人运动至新位置Xnew后,舍弃当前类中适应度值最差的个体,将Xnew作为新个体加入到类中。这种方式选择的新个体Xnew一定概率上会保留适应度值较差的个体,但在不断迭代过程中,适应度值最差的个体不断被舍弃。种群中始终保存适应度值最好的n-m个个体,群体适应度值向最优方向逼近,直至实现对气味源定位。

当机器人气味传感器读数大于预先设定的阈值TH2时,则认为已经找到疑似气味源,机器人通过浓度和持久性两个指标,排除疑似气味源或对气味源进行确认。MBSO算法流程如图 2所示。

图 2 MBSO算法流程 Figure 2 Flow chart of MBSO algorithm
3 实验结果与分析

仿真实验将Fluent模拟动态烟羽环境结果以ASCII文件输出,导入Matlab 2010a科学计算软件,进行MBSO算法气味源定位仿真实验。

3.1 仿真实验结果

实验中对机器人作如下假设:

1) 机器人配备红外距离传感器、定位装置和通信设备,共享位置坐标、风力和气味浓度信息;

2) 机器人具有全自由度运动性能,实时向目标点运动,最大运动速度vr设定为0.5 m/s;

3) 机器人尺寸很小,可以忽略不计;

4) 气味和风速传感器实时测量浓度、风力风速数据,忽略响应和恢复时间。

图 3为无障碍环境Case-1中使用6个机器人在种群规模为30时的气味源定位过程,图中机器人用○、☆、◇、△、□、※表示。在t=0 s时刻, 机器人随机运动发现烟羽,初始化MBSO种群个体,当机器人探测酒精浓度大于阈值的个体数量大于种群规模时,机器人由随机搜索转换为MBSO算法搜索。t=10 s时, 机器人已经开始按照MBSO算法搜索,t=25 s时刻两个机器人传感器读数大于阈值TH2,此区域存在疑似气味源,其他机器人迅速靠拢,通过浓度和持久性两个指标结合进行判断,最终在t=36 s时对气味源进行了确认。

图 3 无障碍环境机器人搜索过程 Figure 3 Search process of robot in the environment without obstacles

图 4为有障碍物环境Case-2中使用6个机器人在种群规模为30时的气味源定位过程。障碍物的存在影响了酒精烟羽的传播和分布,对机器人的搜索增加了困难。在MBSO搜索算法中加入避障算法,当机器人探测到前方有障碍物存在时,沿顺时针旋转45°,直到前方检测不到障碍物,继续向前搜索,从而绕过障碍物实现对于气味源的定位。由图 4中可知,t=15 s开始MBSO算法搜索过程,t=30 s时刻机器人成功绕过了障碍物并跳出了局部极值点,向气味源运动,并在t=48 s对于气味源进行了确认。

图 4 有障碍环境机器人搜索过程 Figure 4 Search process of robot in the environment with obstacles
3.2 机器人数目和类平均个体数目对搜索结果的影响

仿真实验表明,机器人数目和种群中个体的数目均对MBSO算法搜索速度有影响。机器人数目等于每轮迭代中类的数目,对搜索速度影响显著。个体数目变化远小于类数目时,对于搜索速度影响不明显,但变化量等于或大于类数目时,对搜索速度影响变化显著。因此本文把机器人数目和每类中平均个体数目结合起来,分析两者对搜索速度的影响。

在无障碍物环境Case-1中,分别对于不同数目机器人和类平均个体数目进行交叉组合,分别进行实验。每种组合独立运行MBSO算法100次,计算每种情况下平均搜索时间,实验结果如图 5所示,图中曲面每个点表示该种组合下平均搜索时间。由图 5可知,随着机器人数量增加,算法平均定位时间越短,但也呈现一定波动性,机器人数目小于6个时,算法搜索速度变化剧烈,在个数大于6个时变化幅度趋于平稳。

图 5 机器人平均数目和类平均数目对搜索速度的影响 Figure 5 Influence of average number of robots and classes on search speed

随着类中平均个体数目的增加,算法平均搜索时间呈现先减小后增大的规律。综合来看,算法在机器人数目为10、类中个体平均数目为6的情况下达到最优状态。出现这一现象的原因是个体保存了环境中气味的历史浓度信息,随着类内平均个体数量的增加,可供利用的信息越多,平均搜索时间越短。但是由于气流对于气味分子的输运作用,较早生成的个体浓度信息逐步发生了变化,已经不能代表当前浓度分布情况,这些个体的存在反而会增加算法的平均搜索时间。

3.3 对比实验及分析

选取自适应蚁群优化与逆风搜索相结合(AACOUS)算法[13]、带电粒子群与结合风向(Charged PSO with Wind Utilization, WU-CPSO)算法[10]和基于概率适应度函数的粒子群优化(Probability-fitness-function based PSO, P-PSO)算法[16],测试所提算法的效率和搜索速度。AACOUS算法将蚁群算法与逆风搜索结合定位气味源。WU-CPSO算法将机器人视为带电粒子以避免陷入局部最优,结合风向实现对于气味源定位。P-PSO算法应用贝叶斯推理和变论域推理的适应值的微粒群算法实现气味源定位。三种算法均没有调节全局与局部搜索关系的机制。WU-CPSO和P-PSO没有利用历史信息的指引作用,AACOUS仅利用了少量历史浓度信息进行定位,但结果不明显。

采用三个指标对于算法性能进行评价:一是算法的平均搜索时间,这一指标直接反映了算法的收敛速度; 二是机器人出发点和气味源之间距离与机器人平均运动长度的比值,称为距离长度比,这一指标反映了算法的运动效率; 三是算法成功定位气味源的次数与总实验次数的比值,也就是算法的成功率。实验中采用10个机器人分别对Case-1和Case-2环境进行气味源定位。三种对比算法分别与参考文献中保持一致。MBSO算法如下:种群规模n取为70,最大迭代代数Imax为200,预设概率p1p2都设为0.5,高斯函数参数μ设为1,σ为0。

1) 无障碍环境Case-1。

对于无障碍物环境Case-1,运用上述四种算法进行气味源定位,每种算法分别独立运行100次,相应的平均搜索时间、距离长度比和成功率如表 1所示。由表 1中可以看出,MBSO算法获得最短平均搜索时间、次优的距离长度比和最高的成功率; AACOUS算法获得了最好的距离长度比值和次优的成功率,平均搜索时间要长于MBSO算法和P-PSO算法; WU-PSO算法获得了第3的成功率,但平均搜索时间最长,机器人走过距离也最长; P-PSO算法获得了排名第2的平均搜索时间,但距离长度比较小且成功率最低。综合来看,在Case-1环境气味源定位中,相比算法AACOUS、WU-PSO、P-PSO,MBSO算法定位成功率分别提高了5个百分点、10个百分点、15个百分点,其定位时间分别缩短了33.91%、38.16%、32.30%,定位效果明显优于其他三种算法。

表 1 无障碍物环境不同算法对比结果 Table 1 Comparison results of different algorithms in the environment without obstacles

2) 有障碍环境Case-2。

对于存在三个障碍物的环境Case-2,运用上述四种算法进行气味源定位,每种算法分别独立运行100次,相应的平均搜索时间、距离长度比和成功率如表 2所示。Case-2中障碍物的存在使得气流方向和强度发生了改变,在障碍物附近烟羽容易聚集形成局部浓度极值点,加大了气味源的定位难度。由表 2可以看出,三种对比算法距离长度比相差不大,AACOUS算法获得了第2的定位成功率和第3的平均搜索时间; WU-PSO算法平均搜索时间最长,定位成功率也最低; P-PSO算法获得了第2的平均搜索时间和第3的成功率。MBSO算法以最短的平均搜索时间,最大的距离长度比,获得了最高的定位成功率。综合来看,在Case-2环境气味源定位中,相比算法AACOUS、WU-PSO、P-PSO,MBSO算法定位成功率分别提高了15个百分点、28个百分点、25个百分点,其定位时间分别缩短了41.73%、52.26%、40.00%,表明MBSO算法在复杂环境中具有更高效的定位能力。

表 2 有障碍物环境不同算法对比结果 Table 2 Comparison results of different algorithms in the environment with obstacles

通过比较可以发现,本文算法可以有效调节机器人全局搜索和局部搜索行为,大大降低了机器人陷入局部最优的概率。在两个环境中气味源定位中,该算法平均搜索时间和成功率两个指标均优于其他三种算法,能够实现气味源快速、准确定位。

4 结语

本文研究了湍流环境下多机器人协同气味源定位问题,提出基于头脑风暴优化算法的多机器人气味源定位算法——MBSO。根据气味源定位问题特点,重新定义了BSO算法个体生成方式,将逆风搜索融合到算法中,使得每轮迭代中机器人都向目标点运动,通过调节类内和类间生成新个体的数量动态调节全局和局部搜索关系,同时BSO算法的多个体机制充分利用了历史信息的导向作用,极大缩短了多机器人气味源定位的时间,提升了定位准确率。利用Fluent软件模拟了有无障碍两个动态烟羽环境,将所提算法在仿真环境中与三种已有群体智能多机器人气味源定位算法进行比较。实验结果表明,MBSO算法能快速、高效、准确定位气味源。本文中应用Fluent模拟了室内湍流环境下烟羽分布,与实际环境还是有所区别,把算法移植到实际机器人平台进行验证将是进一步要研究的方向。

参考文献(References)
[1] 孟庆浩, 李飞. 主动嗅觉研究现状[J]. 机器人, 2006, 28(1): 89-96. (MENG Q H, LI F. Review of active olfaction[J]. Robot, 2006, 28(1): 89-96.)
[2] RUSSELL R A. Tracking chemical plumes in constrained environments[J]. Robotica, 2001, 19(4): 451-458.
[3] LYTRIDIS C, KADAR E E, VIRK G S. A systematic approach to the problem of odour source localization[J]. Autonomous Robots, 2006, 20(3): 261-276. DOI:10.1007/s10514-006-7414-3
[4] ISHIDA H, WADA Y, MATSUKURA H. Chemical sensing in robotic applications:a review[J]. IEEE Sensors Journal, 2012, 12(11): 3163-3173. DOI:10.1109/JSEN.2012.2208740
[5] 张小俊, 张明路, 孟庆浩, 等. 一种基于动物捕食行为的机器人气味源定位策略[J]. 机器人, 2008, 30(3): 268-272. (ZHANG X J, ZHANG M L, MENG Q H, et al. A gas/odor source localization strategy for mobile robot based on animal predatory behavior[J]. Robot, 2008, 30(3): 268-272.)
[6] LI W, FARRELL J A, PANG S, et al. Moth-inspired chemical plume tracing on an autonomous underwater vehicle[J]. IEEE Transactions on Robotics, 2006, 22(2): 292-307. DOI:10.1109/TRO.2006.870627
[7] KOWADLO G, RUSSELL R A. Improving the robustness of naive physics airflow mapping, using Bayesian reasoning on a multiple hypothesis tree[J]. Robotics and Autonomous Systems, 2009, 57(6/7): 723-737.
[8] 李吉功, 孟庆浩, 李飞, 等. 时变流场环境中机器人跟踪气味烟羽方法[J]. 自动化学报, 2009, 35(10): 1327-1333. (LI J G, MENG Q H, LI F, et al. Tracing odor plume by robot in time-variant flow-field environments[J]. Acta Automatica Sinica, 2009, 35(10): 1327-1333.)
[9] HAYES A T, MARTINOLI A, GOODMAN R M. Distributed odor source localization[J]. IEEE Sensors Journal, 2002, 2(3): 260-271. DOI:10.1109/JSEN.2002.800682
[10] JATMIKO W, SEKIYAMA K, FUKUDA T. A PSO based mobile robot for odor source localization in dynamic advection-diffusion with obstacles environment:theory, simulation and measurement[J]. IEEE Computational Intelligence Magazine, 2007, 2(2): 37-51. DOI:10.1109/MCI.2007.353419
[11] JATMIKO W, PAMBUKO W, MURSANTO P, et al. Localizing multiple odor sources in dynamic environment using ranged subgroup PSO with flow of wind based on open dynamic engine library[C]//MHS 2009:Proceedings of the 2009 International Symposium on Micro-Nano Mechatronics and Human Science. Piscataway, NJ:IEEE, 2009:602-607.
[12] 孟庆浩, 李飞, 张明路, 等. 湍流烟羽环境下多机器人主动嗅觉实现方法研究[J]. 自动化学报, 2008, 34(10): 1281-1290. (MENG Q H, LI F, ZHANG M L, et al. Study on realization method of multi-robot active olfaction in turbulent plume environments[J]. Acta Automatica Sinica, 2008, 34(10): 1281-1290.)
[13] MENG Q H, YANG W X, WANG Y, et al. Adapting an ant colony metaphor for multi-robot chemical plume tracing[J]. Sensors, 2012, 12(4): 4737-4763.
[14] 张勇, 巩敦卫, 胡滢, 等. 室内噪声环境下气味源的多机器人微粒群搜索方法[J]. 电子学报, 2014, 42(1): 70-76. (ZHANG Y, GONG D W, HU Y, et al. A PSO-based multi-robot search method for odor source in indoor environment with noise[J]. Acta Electronica Sinica, 2014, 42(1): 70-76.)
[15] WANG W J, CAO M L, MA S G, et al. Multi-robot odor source search based on curkoo search algorithm in ventilated indoor environment[C]//Proceedings of the 201612th World Congress on Intelligent Control and Automation. Piscataway, NJ:IEEE, 2016:1496-1501.
[16] 李飞, 孟庆浩, 李吉功, 等. 基于P-PSO算法的室内有障碍通风环境下的多机器人气味源搜索[J]. 自动化学报, 2009, 35(12): 1573-1579. (LI F, MENG Q H, LI J G, et al. P-PSO algorithm based multi-robot odor source search in ventilated indoor environment with obstacles[J]. Acta Automatica Sinica, 2009, 35(12): 1573-1579.)
[17] SHI Y H. Brain storm optimization algorithm[C]//Proceedings of the 2011 International Conference in Swarm Intelligence, LNCS 6728. Berlin:Springer, 2011:303-309.
[18] DUAN H B, LI S T, SHI Y H. Predator-prey brain storm optimization for DC brushless motor[J]. IEEE Transactions on Magnetics, 2013, 49(10): 5336-5340. DOI:10.1109/TMAG.2013.2262296
[19] SUN C H, DUAN H B, SHI Y H. Optimal satellite formation reconfiguration based on closed-loop brain storm optimization[J]. IEEE Computational Intelligence Magazine, 2013, 8(4): 39-51. DOI:10.1109/MCI.2013.2279560
[20] DUAN H B, LI C. Quantum-behaved brain btorm optimization approach to solving loney's solenoid problem[J]. IEEE transactions on Magnetics, 2015, 51(1): 1-7.
[21] 杨玉婷, 段丁娜, 张欢, 等. 基于改进头脑风暴优化算法的隐马尔可夫模型运动识别[J]. 航天医学与医学工程, 2015, 28(6): 403-407. (YANG Y T, DUAN D N, ZHANG H, et al. Motion recognition based on hidden Markov model with improved brain storm optimization[J]. Space Medicine & Medical Engineering, 2015, 28(6): 403-407.)