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

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

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

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

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

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

針對(duì)現(xiàn)有室內(nèi)湍流環(huán)境下多機(jī)器人氣味源搜索算法存在歷史濃度信息利用率不高、缺少調(diào)節(jié)全局與局部搜索的機(jī)制等問(wèn)題，提出頭腦風(fēng)暴優(yōu)化(BSO)算法與逆風(fēng)搜索結(jié)合的多機(jī)器人協(xié)同搜索算法。首先，將機(jī)器人已搜索位置初始化為個(gè)體，以機(jī)器人位置為中心聚類，有效利用了歷史信息的指引作用；然后，將逆風(fēng)搜索作為個(gè)體變異操作，動(dòng)態(tài)調(diào)節(jié)選中一個(gè)類中個(gè)體或兩個(gè)類中個(gè)體融合生成新個(gè)體的數(shù)量，有效調(diào)節(jié)了全局和局部搜索方式；最后，根據(jù)濃度和持久性兩個(gè)指標(biāo)對(duì)氣味源進(jìn)行確認(rèn)。在有障礙和無(wú)障礙兩個(gè)環(huán)境中將所提算法與三種群體智能多機(jī)器人氣味源定位算法進(jìn)行定位對(duì)比仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，所提算法的平均搜索時(shí)間減少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é)煙羽追蹤問(wèn)題[1-3]，又稱為機(jī)器人主動(dòng)嗅覺(jué)，是指利用配備了氣味傳感器的移動(dòng)機(jī)器人跟蹤氣味分子擴(kuò)散軌跡，最終定位并確認(rèn)氣味源所在位置的過(guò)程。許多問(wèn)題都可以歸結(jié)為氣味源定位問(wèn)題，例如有毒/有害氣體泄露檢測(cè)、污染源檢測(cè)、火源探測(cè)、反恐排爆和災(zāi)后倒塌建筑物搜救等[4]。機(jī)器人與受過(guò)訓(xùn)練的人或動(dòng)物相比，具有不易疲勞的特點(diǎn)，并且可以工作在劇毒、強(qiáng)腐蝕性等高危環(huán)境，因此機(jī)器人氣味源定位技術(shù)具有廣闊的應(yīng)用前景。

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

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

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

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

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

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

C=f(X,t)

(1)

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

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

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

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

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

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

2.1 BSO算法

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

1)聚類。

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

2)變異。

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

3)生成新個(gè)體。

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

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

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

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

(2)

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

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

(3)

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

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

(4)

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

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

4)選擇。

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

2.2 MBSO氣味源定位算法

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

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

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

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

(5)

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

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

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

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

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

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

3)新個(gè)體生成。

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

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

(6)

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

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

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

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

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

d=min(vr,di)

(7)

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

4)選擇。

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 仿真實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中對(duì)機(jī)器人作如下假設(shè):

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 對(duì)比實(shí)驗(yàn)及分析

選取自適應(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]，測(cè)試所提算法的效率和搜索速度。AACOUS算法將蟻群算法與逆風(fēng)搜索結(jié)合定位氣味源。WU-CPSO算法將機(jī)器人視為帶電粒子以避免陷入局部最優(yōu)，結(jié)合風(fēng)向?qū)崿F(xiàn)對(duì)于氣味源定位。P-PSO算法應(yīng)用貝葉斯推理和變論域推理的適應(yīng)值的微粒群算法實(shí)現(xiàn)氣味源定位。三種算法均沒(méi)有調(diào)節(jié)全局與局部搜索關(guān)系的機(jī)制。 WU-CPSO和P-PSO沒(méi)有利用歷史信息的指引作用，AACOUS僅利用了少量歷史濃度信息進(jìn)行定位，但結(jié)果不明顯。

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

References)

[1] 孟慶浩,李飛.主動(dòng)嗅覺(jué)研究現(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] 張小俊,張明路,孟慶浩,等.一種基于動(dòng)物捕食行為的機(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] 李吉功,孟慶浩,李飛,等.時(shí)變流場(chǎng)環(huán)境中機(jī)器人跟蹤氣味煙羽方法[J].自動(dòng)化學(xué)報(bào),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ī)器人主動(dòng)嗅覺(jué)實(shí)現(xiàn)方法研究[J].自動(dòng)化學(xué)報(bào),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é)報(bào),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].自動(dòng)化學(xué)報(bào), 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)動(dòng)識(shí)別[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。

天津市科技計(jì)劃項(xiàng)目(14JCYBJC18500，14ZCDGSF00124)。

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

1001- 9081(2017)12- 3614- 06

10.11772/j.issn.1001- 9081.2017.12.3614

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

TP242；TP391.9

A