梁志剛，顧軍華,，董永峰

(1.河北工業(yè)大學(xué) 電氣工程學(xué)院，天津300401； 2.河北工業(yè)大學(xué) 計算機(jī)科學(xué)與軟件學(xué)院，天津 300401)

基于頭腦風(fēng)暴優(yōu)化算法的多機(jī)器人氣味源定位

梁志剛1，顧軍華1,2*，董永峰2

(1.河北工業(yè)大學(xué) 電氣工程學(xué)院，天津300401； 2.河北工業(yè)大學(xué) 計算機(jī)科學(xué)與軟件學(xué)院，天津 300401)

針對現(xiàn)有室內(nèi)湍流環(huán)境下多機(jī)器人氣味源搜索算法存在歷史濃度信息利用率不高、缺少調(diào)節(jié)全局與局部搜索的機(jī)制等問題，提出頭腦風(fēng)暴優(yōu)化(BSO)算法與逆風(fēng)搜索結(jié)合的多機(jī)器人協(xié)同搜索算法。首先，將機(jī)器人已搜索位置初始化為個體，以機(jī)器人位置為中心聚類，有效利用了歷史信息的指引作用；然后，將逆風(fēng)搜索作為個體變異操作，動態(tài)調(diào)節(jié)選中一個類中個體或兩個類中個體融合生成新個體的數(shù)量，有效調(diào)節(jié)了全局和局部搜索方式；最后，根據(jù)濃度和持久性兩個指標(biāo)對氣味源進(jìn)行確認(rèn)。在有障礙和無障礙兩個環(huán)境中將所提算法與三種群體智能多機(jī)器人氣味源定位算法進(jìn)行定位對比仿真實驗，實驗結(jié)果表明，所提算法的平均搜索時間減少33%以上，且定位準(zhǔn)確率達(dá)到100%。該算法能夠有效調(diào)節(jié)機(jī)器人全局和局部搜索關(guān)系，快速準(zhǔn)確定位氣味源。

氣味源定位;湍流環(huán)境;多機(jī)器人;頭腦風(fēng)暴優(yōu)化算法;逆風(fēng)搜索

0 引言

機(jī)器人氣味源定位或化學(xué)煙羽追蹤問題[1-3]，又稱為機(jī)器人主動嗅覺，是指利用配備了氣味傳感器的移動機(jī)器人跟蹤氣味分子擴(kuò)散軌跡，最終定位并確認(rèn)氣味源所在位置的過程。許多問題都可以歸結(jié)為氣味源定位問題，例如有毒/有害氣體泄露檢測、污染源檢測、火源探測、反恐排爆和災(zāi)后倒塌建筑物搜救等[4]。機(jī)器人與受過訓(xùn)練的人或動物相比，具有不易疲勞的特點，并且可以工作在劇毒、強(qiáng)腐蝕性等高危環(huán)境，因此機(jī)器人氣味源定位技術(shù)具有廣闊的應(yīng)用前景。

機(jī)器人氣味源定位算法的研究，集中在搜索過程中機(jī)器人運(yùn)動策略的研究。氣味源定位算法可以分為基于單機(jī)器人的生物啟發(fā)算法、工程方法和基于多機(jī)器人的群體智能協(xié)同搜索算法。生物啟發(fā)式算法模仿生物在覓食、尋找同伴時的化學(xué)趨向性和風(fēng)趨向性特點，利用單個機(jī)器人實現(xiàn)氣味源定位任務(wù)。張小俊等[5]利用配備氣味和風(fēng)速傳感器的機(jī)器人模擬動物捕食行為，采用“Z”字形和神經(jīng)網(wǎng)絡(luò)算法融合的搜索策略實現(xiàn)了對于酒精氣味源的準(zhǔn)確定位。Li等[6]模仿飛蛾運(yùn)動特性，實現(xiàn)了水下機(jī)器人在水中的定位任務(wù)。工程學(xué)方法利用機(jī)器人測量的濃度、風(fēng)力信息，采用信息論、概率論和流體力學(xué)等方法動態(tài)估計氣味源所在位置，實現(xiàn)氣味源定位。Kowadlo等[7]應(yīng)用貝葉斯理論構(gòu)建多假設(shè)樹進(jìn)行氣味源搜索，并在基于樸素物理學(xué)的封閉流場環(huán)境中驗證了該算法的有效性。李吉功等[8]通過概率方法對氣味包可能走過的路徑進(jìn)行計算，反向追蹤路徑源頭實現(xiàn)了氣味源定位。

有學(xué)者利用群體智能算法協(xié)調(diào)多個機(jī)器人運(yùn)動，進(jìn)行了多機(jī)器人氣味源定位研究。相比單機(jī)器人定位算法，多機(jī)器人群體智能算法具有定位時間短、搜索效率高、魯棒性好、可擴(kuò)展等優(yōu)點。Hayes等[9]首先對于多機(jī)器人氣味源定位算法進(jìn)行了研究，提出基于多機(jī)器人的外螺旋線搜索(Spiral Surge, SS)算法。Jatmiko等[10-11]研究了檢測與響應(yīng)粒子群優(yōu)化(Detection and Response Partical Swarm Optimization, DRPSO)和帶電電荷粒子群優(yōu)化(Charged Partical Swarm Optimization, CPSO)算法，并應(yīng)用Farrel建立的湍流煙羽仿真模型對算法性能進(jìn)行了研究。孟慶浩等[12-13]研究自適應(yīng)蟻群優(yōu)化與逆風(fēng)搜索相結(jié)合(Adapted Ant Clony Optimization combined with Upwind Surge, AACOUS)算法，分別在仿真和真實機(jī)器人平臺驗證了算法的有效性。張勇等[14]應(yīng)用骨干微粒群進(jìn)化的多機(jī)器人協(xié)作實現(xiàn)了對于噪聲環(huán)境下氣味源的定位。Wang等[15]等將改進(jìn)布谷鳥算法結(jié)合逆風(fēng)搜索，仿真實現(xiàn)了室內(nèi)湍流環(huán)境下氣味源定位。李飛等[16]建立基于貝葉斯和變論域模糊推理表達(dá)的適應(yīng)度函數(shù)值，結(jié)合風(fēng)速和氣味濃度，實現(xiàn)了概率適應(yīng)度函數(shù)粒子群優(yōu)化算法氣味源定位。上述算法存在以下兩方面的問題：一是機(jī)器人搜索策略單一，算法缺少調(diào)節(jié)進(jìn)行全局或局部搜索機(jī)器人數(shù)目的機(jī)制，搜索初期加強(qiáng)全局搜索，后期加強(qiáng)局部搜索可以顯著縮短氣味源的定位的時間。二是算法僅僅根據(jù)機(jī)器人當(dāng)前位置氣味濃度信息確定下一步運(yùn)動方向，缺乏歷史濃度信息對當(dāng)前搜索行為的指引作用。

近年來，一種模仿人類解決復(fù)雜問題的群體智能算法——頭腦風(fēng)暴優(yōu)化(Brain Storm Optimization, BSO)算法受到越來越多關(guān)注。BSO由Shi[17]于2011年提出，該算法是基于人們創(chuàng)造性解決問題的方法——頭腦風(fēng)暴過程(Brainstorming Process)啟發(fā)演化而來。BSO算法能夠較好平衡全局搜索和局部搜索能力，在很多優(yōu)化問題上取得了成功，應(yīng)用BSO算法對于經(jīng)典測試函數(shù)進(jìn)行仿真驗證，實驗結(jié)果表明了BSO算法在單模和多模優(yōu)化問題中的有效性和效率。 Duan等[18]提出捕食者-獵物BSO(Predator-Prey BSO, PPBSO)算法，在解決直流無刷電機(jī)優(yōu)化問題上能夠快速準(zhǔn)確找到全局最優(yōu)值。Sun等[19]提出了一種閉環(huán)BSO(Closed-Loop BSO, CLBSO)算法，成功解決了二沖量控制的多衛(wèi)星編隊再配置問題。Duan等[20]引入量子機(jī)制對BSO(Quantum-behaved BSO, QBSO)算法進(jìn)行改進(jìn)，解決了螺線管優(yōu)化問題。楊玉婷等[21]將帶差分步長的BSO(BSO with Differential Step, BSO-DS)算法應(yīng)用于隱馬爾可夫過程的訓(xùn)練，極大提高了運(yùn)動視頻識別的準(zhǔn)確率。在這些領(lǐng)域的成功應(yīng)用表明了BSO算法在解決優(yōu)化問題時的優(yōu)異效果。算法的分類機(jī)制和個體更新方式能夠?qū)τ谌趾途植克阉鬟M(jìn)行靈活調(diào)節(jié)，該機(jī)制顯示了BSO算法在其他優(yōu)化領(lǐng)域具有巨大的應(yīng)用潛力。

本文將BSO算法應(yīng)用于室內(nèi)湍流環(huán)境下多機(jī)器人氣味源定位問題， 提出了一種改進(jìn)的BSO(Modified BSO, MBSO)算法，與逆風(fēng)搜索相結(jié)合協(xié)調(diào)機(jī)器人的運(yùn)動實現(xiàn)氣味源定位任務(wù)。MBSO算法將機(jī)器人搜索軌跡上坐標(biāo)點作為算法個體，該位置測得的氣味濃度作為適應(yīng)度值，極大保留了歷史濃度信息，通過調(diào)節(jié)類內(nèi)和類間生成新個體的數(shù)量動態(tài)調(diào)節(jié)全局和局部搜索關(guān)系。為了驗證算法的有效性，應(yīng)用Fluent建立了室內(nèi)動態(tài)無障礙/有障礙兩種計算機(jī)仿真模型，進(jìn)行了氣味源定位仿真實驗。仿真結(jié)果表明，本文算法可以實現(xiàn)動態(tài)煙羽環(huán)境下氣味源的快速、準(zhǔn)確定位。

1 室內(nèi)湍流環(huán)境煙羽模型建立

室內(nèi)湍流環(huán)境下氣味的濃度場受到湍動氣流支配，濃度是關(guān)于位置、時間等因素的多元函數(shù)。機(jī)器人氣味源定位時，氣味傳感器在同一水平高度上，濃度場可以簡化為二維平面內(nèi)的二元函數(shù)，濃度值C數(shù)學(xué)描述如下:

C=f(X,t)

(1)

其中：X=(x,y)為機(jī)器人坐標(biāo)；t為測量濃度的時間。障礙物的存在和風(fēng)速的變化使得湍流主控環(huán)境下濃度場更加復(fù)雜多變，流場的煙羽具有時變和間歇的特性，容易在局部聚集形成濃度極值點。這就造成濃度梯度在時間和空間上不連續(xù)的特性，某個區(qū)域內(nèi)梯度方向通常指向局部極值點而不是氣味源。

本文通過計算流體力學(xué)(Computational Fluid Dynamics, CFD)軟件Fluent建立計算仿真模型，模擬室內(nèi)具有湍流特性的動態(tài)煙羽擴(kuò)散模型。仿真模型假設(shè)室內(nèi)氣體滿足理想氣體狀態(tài)方程， 考慮窗口和門的對流作用，忽略能量方程中由于黏性作用產(chǎn)生的能量損耗?？諝獾牧鲃幼裱璑-S(Navier-Stokes)方程組，選用SIMPLE算法對時均方程進(jìn)行求解，模擬環(huán)境為標(biāo)準(zhǔn)的k-ε模型。氣體擴(kuò)散源選用酒精進(jìn)行模擬，擴(kuò)散強(qiáng)度恒定。

仿真環(huán)境模擬了二維無障礙物流場Case-1和有3個障礙物流場Case-2兩種實驗環(huán)境，兩個環(huán)境具有相同基本參數(shù):流場尺寸為10 m×10 m，有2個寬度為2 m的進(jìn)風(fēng)口和1個寬2 m的出風(fēng)口。進(jìn)風(fēng)口Inlet-1和Inlet-2位于流場左側(cè)，坐標(biāo)分別為(x=0，y=[1，3])和 (x=0，y=[7，9])， 出風(fēng)口Outlet在流場右側(cè)，坐標(biāo)為(x=10，y=[2，4])。酒精揮發(fā)源坐標(biāo)為(2，7)，揮發(fā)速度為200 ppm。兩個環(huán)境中進(jìn)風(fēng)口的風(fēng)速、風(fēng)向是關(guān)于時間t的函數(shù)，隨著風(fēng)速、風(fēng)向的變化，煙羽的分布也相應(yīng)發(fā)生變化。圖1顯示某個瞬間兩個環(huán)境風(fēng)速、風(fēng)向和酒精濃度分布:圖1(a)中兩個進(jìn)風(fēng)口速度均為1 m/s，方向與x軸平行;圖1(b)中兩個進(jìn)風(fēng)口的風(fēng)速均為0.8 m/s，Inlet-1風(fēng)向與x軸呈45°夾角，Inlet-2風(fēng)向與x軸平行，圖中三個黑色物體為障礙物。以酒精揮發(fā)源為中心的封閉曲線是濃度等高線，濃度值越大的區(qū)域?qū)?yīng)等高線灰度越深。

圖1 動態(tài)湍流煙羽環(huán)境瞬時分布Fig. 1 Instantaneous distribution of dynamic turbulent plume environment

2 改進(jìn)的頭腦風(fēng)暴優(yōu)化算法

頭腦風(fēng)暴過程是人們創(chuàng)造性解決問題的一種方法，該方法通過聚集不同專業(yè)背景的人進(jìn)行發(fā)散思維、思想碰撞、觀點融合，以找到問題的最優(yōu)解決方案。BSO算法是對于頭腦風(fēng)暴過程進(jìn)行抽象得到的優(yōu)化算法。

2.1 BSO算法

BSO算法中每個個體代表優(yōu)化問題的可行解，算法將頭腦風(fēng)暴過程的不同階段抽象為聚類、變異、生成新個體、選擇四種操作，通過四種操作實現(xiàn)對個體更新，最終找到問題的最優(yōu)解。BSO算法在解的可行域中隨機(jī)選擇n個個體Xi(i=1,2,…,n)作為優(yōu)化問題的初始解。確定最大迭代次數(shù)Imax，設(shè)定算法終止條件。

1)聚類。

用K-means聚類算法將n個個體分成m個類，計算每個個體的適應(yīng)度函數(shù)值，適應(yīng)度值最好的個體記為該類的中心個體。

2)變異。

以一定的概率隨機(jī)選中某個類的中心個體，加上一個隨機(jī)擾動后替換原中心個體。

3)生成新個體。

首先產(chǎn)生[0，1]內(nèi)的隨機(jī)數(shù)p11，與預(yù)先設(shè)定的概率參數(shù)p1進(jìn)行比較，根據(jù)結(jié)果選擇以下兩種方式產(chǎn)生候選個體Xs:

a)若p11>p1，則隨機(jī)選中一個類，隨機(jī)選擇類中一個個體，作為產(chǎn)生新個體的候選個體Xs。

b)若p11≤p1，則隨機(jī)選中兩個類，產(chǎn)生一個[0，1]之間的隨機(jī)數(shù)p12，與預(yù)先設(shè)定的概率參數(shù)p2進(jìn)行比較，若p12>p2則選擇兩個類中心個體，否則隨機(jī)選擇兩個非中心個體，作為候選個體Xs1和Xs2。根據(jù)式(2)融合得到候選個體Xs：

Xs=ω×Xs1+(1-ω)×Xs2

(2)

其中0<ω<1，由Xs生成新個體Y如式(3)所示：

Y=Xs+ξ×N(μ,σ)

(3)

其中：N(μ,σ)是中心在μ、方差為σ的高斯隨機(jī)函數(shù)；ξ為對數(shù)S變換函數(shù)，如式(4)所示。

ξ=logsig((0.5×Imax-Ic)/k)×rand(0,1)

(4)

其中：logsig()為一個對數(shù)S變換函數(shù)，Imax是算法最大迭代次數(shù)；Ic為當(dāng)前迭代次數(shù)；k控制logsig()的坡度；rand() 產(chǎn)生一個0到1之間的隨機(jī)數(shù)。

在下文中，選中一個類中個體生成新個體的方法稱為a方式生成新個體，兩類中個體融合生成新個體的方法稱為b方式生成新個體。

4)選擇。

新個體Y生成后，計算Y的適應(yīng)度函數(shù)值，與候選個體Xs適應(yīng)度函數(shù)值進(jìn)行比較，適應(yīng)度好的個體進(jìn)入下一代。重復(fù)生成新個體操作，當(dāng)有n個新個體生成后，進(jìn)入下一輪迭代過程。當(dāng)新個體滿足最優(yōu)解條件或達(dá)到預(yù)先設(shè)定的迭代次數(shù)時，算法結(jié)束。

2.2 MBSO氣味源定位算法

MBSO算法中，氣味濃度值作為個體適應(yīng)度函數(shù)值。個體初始化方法如下:給定發(fā)現(xiàn)閾值C1，m個機(jī)器人由同一位置沿不同方向進(jìn)行隨機(jī)搜索，當(dāng)氣味傳感器測量值大于C1時，機(jī)器人位置坐標(biāo)記為問題初始個體。當(dāng)個體數(shù)量大于n-m時，取n-m個適應(yīng)度值最大的個體加上機(jī)器人當(dāng)前位置坐標(biāo)組成初始種群，采用MBSO算法協(xié)調(diào)機(jī)器人之間的運(yùn)動，執(zhí)行氣味源搜索任務(wù)。

1)以機(jī)器人為中心的分類過程。

在氣味源定位問題中，m個機(jī)器人是新個體的發(fā)現(xiàn)者，運(yùn)動至新的位置并檢測該點的氣味濃度。每輪迭代中， 由于每個類至多生成一個新個體，為了提高機(jī)器人利用率，最優(yōu)分類方法是將當(dāng)前代個體分成m個類，機(jī)器人平均分布在m個類中，這樣m個機(jī)器人同時向各自目標(biāo)位置運(yùn)動，生成m個新個體。 BSO算法中聚類操作采用K-means算法，算法計算復(fù)雜度高，耗費時間長，并且不能保證機(jī)器人平均分布于m個類中。MBSO算法采用以機(jī)器人為中心的簡單聚類算法，流程如下:

①記第j個機(jī)器人為當(dāng)前坐標(biāo)為Rj=(rxj,ryj)(1≤j≤m)，分別計算當(dāng)前代中個體Xi=(xi,yi)(i=1,2,…,n)與Rj之間的距離:

(5)

②比較個體Xi與m個機(jī)器人之間的距離，將Xi劃分至與之最近的機(jī)器人類中。

③重復(fù)以上兩個步驟直至所有個體分類完成。

分類完成后將個體坐標(biāo)氣味濃度值記為個體適應(yīng)度函數(shù)值，并確定每個類中心個體。

2)逆風(fēng)搜索。

動物在尋找食物過程中，在發(fā)現(xiàn)目標(biāo)氣味時采取逆風(fēng)而上的運(yùn)動策略。這一策略的邏輯是氣味煙羽總是由源頭揮發(fā)出來，沿著一段時間內(nèi)氣流運(yùn)動的平均方向傳播，風(fēng)向的反方向大概率是氣味源的方向。因此，在MBSO算法中加入逆風(fēng)搜索，使得算法搜索具有方向性，客觀上加快了搜索速度，又可以避免搜索過早收斂到局部極值點。

逆風(fēng)搜索的方法如下:每輪迭代中，首先找到當(dāng)前代適應(yīng)度值最大的中心個體所在的類，屬于該類的機(jī)器人沿逆風(fēng)方向運(yùn)動一個步長的距離vr，生成新個體Xnew，vr為機(jī)器人最大運(yùn)動速度。

3)新個體生成。

BSO算法中：a方式產(chǎn)生的個體大概率出現(xiàn)在所在類附近，適合局部細(xì)致搜索；b方式產(chǎn)生的個體大概率出現(xiàn)在兩類中間，更適合全局搜索。分析氣味源定位問題的搜索過程，可以發(fā)現(xiàn)：初期需要加強(qiáng)全局搜索，以b方式產(chǎn)生新個體為主；后期需要在局部進(jìn)行細(xì)致搜索以確定氣味源位置，以a方式產(chǎn)生新個體為主.

MBSO產(chǎn)生新個體方式如下:每輪迭代中，將m-1個類劃分為兩部分，首先確定b方式生成新個體的類，剩余類采用a方式產(chǎn)生新個體。每次迭代采用b方式更新的類設(shè)為一個單調(diào)遞減函數(shù)，數(shù)量記為Cex，如式(6)所示：

(6)

其中：Imax是算法最大迭代次數(shù)；Ic為當(dāng)前迭代次數(shù)；floor為對有理數(shù)向下取整函數(shù)。按照式(3)生成目標(biāo)個體Y后，m-1個機(jī)器人運(yùn)動模式如下:

①b方式中隨機(jī)選中一個類，類中機(jī)器人向目標(biāo)個體Y方向移動距離d;

②b方式中未被選中機(jī)器人向當(dāng)前代中適應(yīng)度值最大的個體運(yùn)動一個步長的距離vr;

③a方式生成新個體的類中，機(jī)器人向目標(biāo)個體Y方向移動距離d。

綜合考慮真實機(jī)器人的運(yùn)動特性，機(jī)器人運(yùn)動距離d如式(7)所示:

d=min(vr,di)

(7)

其中：vr為機(jī)器人最大運(yùn)動速度；di為機(jī)器人與目標(biāo)個體Y之間的距離。 機(jī)器人分別按照以上三種模式運(yùn)動至新的坐標(biāo)，生成新個體Xnew。

4)選擇。

機(jī)器人運(yùn)動至新位置Xnew后，舍棄當(dāng)前類中適應(yīng)度值最差的個體，將Xnew作為新個體加入到類中。這種方式選擇的新個體Xnew一定概率上會保留適應(yīng)度值較差的個體，但在不斷迭代過程中，適應(yīng)度值最差的個體不斷被舍棄。種群中始終保存適應(yīng)度值最好的n-m個個體，群體適應(yīng)度值向最優(yōu)方向逼近，直至實現(xiàn)對氣味源定位。

當(dāng)機(jī)器人氣味傳感器讀數(shù)大于預(yù)先設(shè)定的閾值TH2時，則認(rèn)為已經(jīng)找到疑似氣味源，機(jī)器人通過濃度和持久性兩個指標(biāo)，排除疑似氣味源或?qū)馕对催M(jìn)行確認(rèn)。MBSO算法流程如圖2所示。

圖2 MBSO算法流程Fig. 2 Flow chart of MBSO algorithm

3 實驗結(jié)果與分析

仿真實驗將Fluent模擬動態(tài)煙羽環(huán)境結(jié)果以ASCII文件輸出，導(dǎo)入Matlab 2010a科學(xué)計算軟件，進(jìn)行MBSO算法氣味源定位仿真實驗。

3.1 仿真實驗結(jié)果

實驗中對機(jī)器人作如下假設(shè):

1)機(jī)器人配備紅外距離傳感器、定位裝置和通信設(shè)備，共享位置坐標(biāo)、風(fēng)力和氣味濃度信息;

2)機(jī)器人具有全自由度運(yùn)動性能，實時向目標(biāo)點運(yùn)動，最大運(yùn)動速度vr設(shè)定為0.5 m/s;

3)機(jī)器人尺寸很小，可以忽略不計;

4)氣味和風(fēng)速傳感器實時測量濃度、風(fēng)力風(fēng)速數(shù)據(jù)，忽略響應(yīng)和恢復(fù)時間。

圖3為無障礙環(huán)境Case-1中使用6個機(jī)器人在種群規(guī)模為30時的氣味源定位過程，圖中機(jī)器人用○、☆、◇、△、□、※表示。在t=0 s時刻,機(jī)器人隨機(jī)運(yùn)動發(fā)現(xiàn)煙羽，初始化MBSO種群個體，當(dāng)機(jī)器人探測酒精濃度大于閾值的個體數(shù)量大于種群規(guī)模時，機(jī)器人由隨機(jī)搜索轉(zhuǎn)換為MBSO算法搜索。t=10 s時,機(jī)器人已經(jīng)開始按照MBSO算法搜索，t=25 s時刻兩個機(jī)器人傳感器讀數(shù)大于閾值TH2，此區(qū)域存在疑似氣味源，其他機(jī)器人迅速靠攏，通過濃度和持久性兩個指標(biāo)結(jié)合進(jìn)行判斷，最終在t=36 s時對氣味源進(jìn)行了確認(rèn)。

圖3 無障礙環(huán)境機(jī)器人搜索過程Fig. 3 Search process of robot in the environment without obstacles

圖4為有障礙物環(huán)境Case-2中使用6個機(jī)器人在種群規(guī)模為30時的氣味源定位過程。障礙物的存在影響了酒精煙羽的傳播和分布，對機(jī)器人的搜索增加了困難。在MBSO搜索算法中加入避障算法，當(dāng)機(jī)器人探測到前方有障礙物存在時，沿順時針旋轉(zhuǎn)45°，直到前方檢測不到障礙物，繼續(xù)向前搜索，從而繞過障礙物實現(xiàn)對于氣味源的定位。由圖4中可知，t=15 s開始MBSO算法搜索過程，t=30 s時刻機(jī)器人成功繞過了障礙物并跳出了局部極值點，向氣味源運(yùn)動，并在t=48 s對于氣味源進(jìn)行了確認(rèn)。

圖4 有障礙環(huán)境機(jī)器人搜索過程Fig. 4 Search process of robot in the environment with obstacles

3.2 機(jī)器人數(shù)目和類平均個體數(shù)目對搜索結(jié)果的影響

仿真實驗表明，機(jī)器人數(shù)目和種群中個體的數(shù)目均對MBSO算法搜索速度有影響。機(jī)器人數(shù)目等于每輪迭代中類的數(shù)目，對搜索速度影響顯著。個體數(shù)目變化遠(yuǎn)小于類數(shù)目時，對于搜索速度影響不明顯，但變化量等于或大于類數(shù)目時，對搜索速度影響變化顯著。因此本文把機(jī)器人數(shù)目和每類中平均個體數(shù)目結(jié)合起來，分析兩者對搜索速度的影響。

在無障礙物環(huán)境Case-1中，分別對于不同數(shù)目機(jī)器人和類平均個體數(shù)目進(jìn)行交叉組合，分別進(jìn)行實驗。每種組合獨立運(yùn)行MBSO算法100次，計算每種情況下平均搜索時間，實驗結(jié)果如圖5所示，圖中曲面每個點表示該種組合下平均搜索時間。由圖5可知，隨著機(jī)器人數(shù)量增加，算法平均定位時間越短，但也呈現(xiàn)一定波動性，機(jī)器人數(shù)目小于6個時，算法搜索速度變化劇烈，在個數(shù)大于6個時變化幅度趨于平穩(wěn)。

隨著類中平均個體數(shù)目的增加，算法平均搜索時間呈現(xiàn)先減小后增大的規(guī)律。綜合來看，算法在機(jī)器人數(shù)目為10、類中個體平均數(shù)目為6的情況下達(dá)到最優(yōu)狀態(tài)。出現(xiàn)這一現(xiàn)象的原因是個體保存了環(huán)境中氣味的歷史濃度信息，隨著類內(nèi)平均個體數(shù)量的增加，可供利用的信息越多，平均搜索時間越短。但是由于氣流對于氣味分子的輸運(yùn)作用，較早生成的個體濃度信息逐步發(fā)生了變化，已經(jīng)不能代表當(dāng)前濃度分布情況，這些個體的存在反而會增加算法的平均搜索時間。

圖5 機(jī)器人平均數(shù)目和類平均數(shù)目對搜索速度的影響Fig. 5 Influence of average number of robots and classes on search speed

3.3 對比實驗及分析

選取自適應(yīng)蟻群優(yōu)化與逆風(fēng)搜索相結(jié)合(AACOUS)算法[13]、帶電粒子群與結(jié)合風(fēng)向(Charged PSO with Wind Utilization, WU-CPSO)算法[10]和基于概率適應(yīng)度函數(shù)的粒子群優(yōu)化(Probability-fitness-function based PSO, P-PSO)算法[16]，測試所提算法的效率和搜索速度。AACOUS算法將蟻群算法與逆風(fēng)搜索結(jié)合定位氣味源。WU-CPSO算法將機(jī)器人視為帶電粒子以避免陷入局部最優(yōu)，結(jié)合風(fēng)向?qū)崿F(xiàn)對于氣味源定位。P-PSO算法應(yīng)用貝葉斯推理和變論域推理的適應(yīng)值的微粒群算法實現(xiàn)氣味源定位。三種算法均沒有調(diào)節(jié)全局與局部搜索關(guān)系的機(jī)制。 WU-CPSO和P-PSO沒有利用歷史信息的指引作用，AACOUS僅利用了少量歷史濃度信息進(jìn)行定位，但結(jié)果不明顯。

采用三個指標(biāo)對于算法性能進(jìn)行評價:一是算法的平均搜索時間，這一指標(biāo)直接反映了算法的收斂速度;二是機(jī)器人出發(fā)點和氣味源之間距離與機(jī)器人平均運(yùn)動長度的比值，稱為距離長度比，這一指標(biāo)反映了算法的運(yùn)動效率;三是算法成功定位氣味源的次數(shù)與總實驗次數(shù)的比值，也就是算法的成功率。實驗中采用10個機(jī)器人分別對Case-1和Case-2環(huán)境進(jìn)行氣味源定位。三種對比算法分別與參考文獻(xiàn)中保持一致。MBSO算法如下：種群規(guī)模n取為70，最大迭代代數(shù)Imax為200，預(yù)設(shè)概率p1和p2都設(shè)為0.5，高斯函數(shù)參數(shù)μ設(shè)為1，σ為0。

1)無障礙環(huán)境Case-1。

對于無障礙物環(huán)境Case-1，運(yùn)用上述四種算法進(jìn)行氣味源定位，每種算法分別獨立運(yùn)行100次，相應(yīng)的平均搜索時間、距離長度比和成功率如表1所示。由表1中可以看出，MBSO算法獲得最短平均搜索時間、次優(yōu)的距離長度比和最高的成功率;AACOUS算法獲得了最好的距離長度比值和次優(yōu)的成功率，平均搜索時間要長于MBSO算法和P-PSO算法;WU-PSO算法獲得了第3的成功率，但平均搜索時間最長，機(jī)器人走過距離也最長;P-PSO算法獲得了排名第2的平均搜索時間，但距離長度比較小且成功率最低。綜合來看，在Case-1環(huán)境氣味源定位中，相比算法AACOUS、WU-PSO、P-PSO，MBSO算法定位成功率分別提高了5個百分點、10個百分點、15個百分點，其定位時間分別縮短了33.91%、38.16%、32.30%，定位效果明顯優(yōu)于其他三種算法。

表1 無障礙物環(huán)境不同算法對比結(jié)果Tab. 1 Comparison results of different algorithms in the environment without obstacles

2)有障礙環(huán)境Case-2。

對于存在三個障礙物的環(huán)境Case-2，運(yùn)用上述四種算法進(jìn)行氣味源定位，每種算法分別獨立運(yùn)行100次，相應(yīng)的平均搜索時間、距離長度比和成功率如表2所示。Case-2中障礙物的存在使得氣流方向和強(qiáng)度發(fā)生了改變，在障礙物附近煙羽容易聚集形成局部濃度極值點，加大了氣味源的定位難度。由表2可以看出，三種對比算法距離長度比相差不大，AACOUS算法獲得了第2的定位成功率和第3的平均搜索時間;WU-PSO算法平均搜索時間最長，定位成功率也最低;P-PSO算法獲得了第2的平均搜索時間和第3的成功率。MBSO算法以最短的平均搜索時間，最大的距離長度比，獲得了最高的定位成功率。綜合來看，在Case-2環(huán)境氣味源定位中，相比算法AACOUS、WU-PSO、P-PSO，MBSO算法定位成功率分別提高了15個百分點、28個百分點、25個百分點，其定位時間分別縮短了41.73%、52.26%、40.00%，表明MBSO算法在復(fù)雜環(huán)境中具有更高效的定位能力。

通過比較可以發(fā)現(xiàn)，本文算法可以有效調(diào)節(jié)機(jī)器人全局搜索和局部搜索行為，大大降低了機(jī)器人陷入局部最優(yōu)的概率。在兩個環(huán)境中氣味源定位中，該算法平均搜索時間和成功率兩個指標(biāo)均優(yōu)于其他三種算法，能夠?qū)崿F(xiàn)氣味源快速、準(zhǔn)確定位。

表2 有障礙物環(huán)境不同算法對比結(jié)果Tab. 2 Comparison results of different algorithms in the environment with obstacles

4 結(jié)語

本文研究了湍流環(huán)境下多機(jī)器人協(xié)同氣味源定位問題，提出基于頭腦風(fēng)暴優(yōu)化算法的多機(jī)器人氣味源定位算法——MBSO。根據(jù)氣味源定位問題特點，重新定義了BSO算法個體生成方式，將逆風(fēng)搜索融合到算法中，使得每輪迭代中機(jī)器人都向目標(biāo)點運(yùn)動，通過調(diào)節(jié)類內(nèi)和類間生成新個體的數(shù)量動態(tài)調(diào)節(jié)全局和局部搜索關(guān)系，同時BSO算法的多個體機(jī)制充分利用了歷史信息的導(dǎo)向作用，極大縮短了多機(jī)器人氣味源定位的時間，提升了定位準(zhǔn)確率。利用Fluent軟件模擬了有無障礙兩個動態(tài)煙羽環(huán)境，將所提算法在仿真環(huán)境中與三種已有群體智能多機(jī)器人氣味源定位算法進(jìn)行比較。實驗結(jié)果表明，MBSO算法能快速、高效、準(zhǔn)確定位氣味源。 本文中應(yīng)用Fluent模擬了室內(nèi)湍流環(huán)境下煙羽分布，與實際環(huán)境還是有所區(qū)別，把算法移植到實際機(jī)器人平臺進(jìn)行驗證將是進(jìn)一步要研究的方向。

References)

[1] 孟慶浩,李飛.主動嗅覺研究現(xiàn)狀[J].機(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.

[4] ISHIDA H, WADA Y, MATSUKURA H. Chemical sensing in robotic applications: a review [J]. IEEE Sensors Journal, 2012, 12(11): 3163-3173.

[5] 張小俊,張明路,孟慶浩,等.一種基于動物捕食行為的機(jī)器人氣味源定位策略[J].機(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.

[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] 李吉功,孟慶浩,李飛,等.時變流場環(huán)境中機(jī)器人跟蹤氣味煙羽方法[J].自動化學(xué)報,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.

[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.

[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] 孟慶浩,李飛,張明路,等.湍流煙羽環(huán)境下多機(jī)器人主動嗅覺實現(xiàn)方法研究[J].自動化學(xué)報,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] 張勇,鞏敦衛(wèi),胡瀅,等.室內(nèi)噪聲環(huán)境下氣味源的多機(jī)器人微粒群搜索方法[J].電子學(xué)報,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 2016 12th World Congress on Intelligent Control and Automation. Piscataway, NJ: IEEE, 2016: 1496-1501.

[16] 李飛,孟慶浩,李吉功,等.基于P-PSO算法的室內(nèi)有障礙通風(fēng)環(huán)境下的多機(jī)器人氣味源搜索[J].自動化學(xué)報, 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.

[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.

[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ìn)頭腦風(fēng)暴優(yōu)化算法的隱馬爾可夫模型運(yùn)動識別[J].航天醫(yī)學(xué)與醫(yī)學(xué)工程,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.)

This work is partially supported by the Science and Technology Project of Tianjin (14JCYBJC18500,14ZCDGSF00124).

LIANGZhigang, born in 1982, Ph. D. candidate, lecturer. His research interests include intelligent information processing, computer vision.

GUJunhua, born in 1966, Ph. D., professor. His research interests include intelligent information processing, computer vision.

DONGYongfeng, born in 1977, Ph. D., professor. His research interests include intelligent information precessing, mobile robot.

Multi-robotodorsourcelocalizationbasedonbrainstormoptimizationalgorithm

LIANG Zhigang1, GU Junhua1,2*, DONG Yongfeng2

(1.SchoolofElectricalEngineering,HebeiUniversityofTechnology,Tianjin300401,China;2.SchoolofComputerScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,China)

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.

odor source localization; turbulent environment; multi-robot; Brain Storm Optimization (BSO) algorithm; upwind search

2017- 06- 05;

2017- 08- 16。

天津市科技計劃項目(14JCYBJC18500，14ZCDGSF00124)。

梁志剛(1982—)，男，河北正定人，講師，博士研究生， CCF會員,主要研究方向：智能信息處理、計算機(jī)視覺； 顧軍華(1966—)，男，河北趙縣人，教授，博士，CCF會員,主要研究方向：智能信息處理、計算機(jī)視覺； 董永峰(1977—)，男，河北定州人，教授，博士，CCF會員,主要研究方向：智能信息處理、移動機(jī)器人。

1001- 9081(2017)12- 3614- 06

10.11772/j.issn.1001- 9081.2017.12.3614

(*通信作者電子郵箱jhgu@hebut.edu.cn)

TP242；TP391.9

A