三維空間機器人主動嗅覺煙羽源自主定位策略

黃建新，袁 杰

新疆大學 電氣工程學院，烏魯木齊830047

1 引言

大氣中一些有害氣體通過煙羽擴散方式，對環境和健康造成危害。煙羽是指從煙羽源釋放的分子團被空氣流吹散后，像羽毛一樣在空氣介質中擴散，形成的軌跡[1]。若能定位到有害氣體煙羽源，便于及時預警和救援。煙羽源定位分為三個過程，即煙羽發現、煙羽追蹤、煙羽源定位。本文研究的是在已知煙羽發現的情況下，機器人如何自主追蹤煙羽，直至定位到煙羽源附近?；诜律袨榈臋C器人主動嗅覺在這方面有突出優勢，眾多學者對煙羽源定位問題進行了研究，提出了相應的方法。王儉等[2-4]采用變步長六邊形算法定位煙羽源。田宇等人[5]針對深海熱源探測、定位效率低下的問題，設計出了自主水下深海熱源定位仿真環境。魏傳鋒等人[6]針對三維密閉空間突發持續污染源定位問題，提出了一種基于位置多假設的污染源定位方法。余瀟瀟等人[7]針對傳統的設置固定監測站進行污染源監測問題，提出了一種基于移動車載傳感器網絡的空間污染源定位算法。王陽等[8]針對室內通風環境下煙羽源定位問題，提出了一種基于模擬退火算法的單機器人煙羽源定位方法。張建化等[9]針對機器人通信受限問題，提出了一種基于微粒群優化的有限通信多機器人煙羽源定位方法。張思齊等[10]針對湍流環境中機器人空間感知能力不足問題，提出一種多弱感知機器人煙羽源搜索算法。陳一村等人[11]，針對室內時變污染源定位問題，采用粒子群智能搜索算法定位室內時變污染源。宋程等[12]針對共享源概率地圖方法不足問題，提出了一種基于認知差異的多機器人協同信息趨向煙羽源搜索方法。Jatmiko等人[13]將粒子群優化算法用于群體機器人煙羽源定位。Ghods等[14]采用極值搜索方法定位煙羽源。

以上學者提出的方法雖然能夠定位到煙羽源，但根據作者掌握的國內外資料，目前鮮有人研究三維空間下煙羽源自主定位問題。因此，本文提出了布谷鳥搜索算法結合改進的模糊C均值聚類算法的自主定位策略。采用布谷鳥搜索算法生成機器人搜索的位置信息，避免搜索盲目性；將該位置信息及該位置處對應的煙羽濃度構成四維特征向量，采用改進的模糊C均值算法對該組特征向量和歷史特征向量構成的一組性的特征向量聚類分析，獲取濃度最大類對應的三維坐標，便于構建布谷鳥搜索算法的目標函數，為布谷鳥算法搜索提供了搜索范圍。

2 布谷鳥搜索算法

布谷鳥算法（Cuckoo Search，CS）是由英國學者Yang Xinshe和Suash Deb于2009年在群體智能技術的基礎上提出的一種新型基于自然元啟發式算法。對于布谷鳥搜索算法，理想情況下假設如下3條規則：

（1）每只布谷鳥每次隨機選擇一個其他鳥類的巢穴，并且每次只產一個蛋，放入選中的巢穴中。

（2）具有最高質量鳥蛋的巢穴會被保留至下一代。

（3）可用的寄主巢穴數量是固定的，并且寄主按概率pa∈(0,1)發現布谷鳥放的蛋。在這種情況下，寄主鳥類可以破壞該蛋或者放棄該巢穴，選擇重新建立新的巢穴。

該算法采用局部隨機游走和全局探索隨機游走，局部隨機游走滿足方程式（1）：

另一方面，全局隨機搜索采用Lévy飛行，滿足方程（2）：

方程（2）中的α＞0，是步長縮放因子，其中，L( s,λ)表達式為：

用Lévy飛行生成隨機數應包括兩個步驟：隨機方向的選擇和服從Lévy分布的步長生成。方向的隨機選擇應服從均勻分布，而Lévy分布的步長生成則采用Mantegna算法來實現。在Mantegna算法中，步長s可以通過使用兩個服從高斯分布的變量U和V計算，如方程（4）：

其中，U～N( 0,σ2),V～N( 0,1)，這里的U～N( 0,σ2)意味著樣本服從均值為0，方差為σ2的高斯正態分布，方差σ2滿足方程（5）：

布谷鳥搜索算法步驟如下：

步驟1設置巢穴個數為n，搜索空間維度為d，初始化巢穴位置，將P0代入目標函數，求出最優巢穴的位置

步驟2循環體

巢穴位置更新：保留上代最優巢穴位置xt-1b，t為整數，并且利用公式（2）對其他巢穴位置進行更新，得到一組新的巢穴位置解，將這組新解代入目標函數，與上代巢穴位置得到的適應度值進行對比，用適應度值較好的巢穴位置替換適應度值較差的巢穴位置，從而能夠得到一組優于上代的巢穴位置

存安去險：用服從均勻分布的隨機數ε∈[0,1]作為巢穴主人發現外來鳥蛋的可能性，并且與設定值pa進行比較，通過方程（1）得到一組新巢穴位置Kt=，計算新巢穴位置對應的適應度值，與得到的適應度值進行比較，用適應度值較好的巢穴位置替換適應度值較差的巢穴位置，從而能夠得到一組優于上代的巢穴位置

步驟3判斷是否滿足迭代終止條件若達到迭代條件終止條件，若滿足輸出最優一組巢穴Pt，反之，返回步驟2循環體繼續進行迭代更新。

布谷鳥搜索算法流程圖如圖1所示。

圖1 布谷鳥搜索算法流程圖

3 模糊C均值聚類算法

Bezdek[15]提出了模糊C均值（Fuzzy C-Means）算法，簡稱FCM算法。該算法通過計算每個樣本屬于所有類的隸屬度，比較每個樣本屬于各個類的隸屬度大小，確定每個樣本所屬類別。

設樣本X={x1,x2,…,xn-1,xn}，其中每個樣本xk均有d個特征，其特征矩陣為：

將樣本X分成c類(2≤c≤n)，設c個聚類中心向量為：

設uij∈[0,1]表示第j個樣本屬于第i類的隸屬度，且滿足：

模糊劃分的隸屬度矩陣U為：

FCM算法目標函數J為：

約束條件為：

利用拉格朗日乘子法將約束問題轉化成無約束問題，即目標函數J轉化為：

將式（13）中所有元素求和，計算目標函數J，分別對其中uij、ci求導，令導數為零，計算目標函數J的極小值，求出uij、ci如下：

FCM算法步驟：

步驟1確定FCM算法聚類數目Cluster，加權指數m。

步驟2初始化隸屬度矩陣U。

步驟3根據式（15）計算聚類中心C。

步驟4根據式（12）計算目標函數J。

步驟5根據步驟3求得的C和式（14）計算U。

步驟6判斷是否滿足迭代次數，若不滿足，返回步驟3，否則，算法終止，返回聚類結果。

4 改進的模糊C均值聚類算法

因傳統的模糊C均值聚類算法中n個聚類樣本X={x1,x2,…,xn-1,xn}的聚類中心點初始值是隨機選取的，聚類中心初始值的選取嚴重影響聚類效果，在本論文中，通過構造密度指標函數對該算法改進，確定聚類中心的初始值。構造的密度指標函數如方程（16）：

其中，ra是定義的樣本的鄰域半徑，半徑以外的樣本點對該樣本點的影響甚小，為了較好確定聚類中心初始值，不至于跨度太大，設定ra=0.5。

具體實現步驟如下：

步驟1根據方程（16）計算樣本X中每個樣本點的密度指標值，密度指標值越大，則該樣本點周圍的點越多，以密度指標值最大的樣本點作為聚類中心點的一個初始值。

步驟2設xck為第k次計算的聚類中心初始值，相應的密度指標為Dck，對于其他每個樣本點xk(xk≠xck)的密度指標按方程（17）進行修正。

其中，rb定了一個密度指標函數顯著減小的領域，領域中靠近第k個聚類中心初值樣本點的密度指標顯著減小，這些樣本點成為下一個聚類中心的可能小甚微。為了避免出現距離很近的聚類中心點，一般取rb=(1 .2～1.5) ra，本文取rb=0.6。

步驟3根據FCM算法確定的聚類數目，判斷計算的聚類中心初始值個數是否等于聚類數目，若滿足，則計算終止，否則，返回步驟2。

5 煙羽源定位策略實驗驗證及分析

5.1 污染源模擬與空間坐標系建立

為了采集煙羽濃度信息及濃度信息對應的空間坐標，把加入乙醇的加濕器模擬為污染源，在實驗室建立三維空間坐標系，見圖2。

圖2 實驗室模擬污染源及空間坐標系

圖2 中，以加滿乙醇的加濕器作為污染源，放在實驗室固定位置，距離污染源約4 m的地方建立了如圖所示的空間坐標系，圖中的O點即為x軸、y軸和z軸的交點。完成污染源模擬和坐標系建立后，采用Arduino控制器、兩個MQ-3濃度傳感器、筆記本電腦、Kobuki移動機器人、卷尺對實驗室空間煙羽濃度分布進行采集，直至采集到模擬的污染源附近為止，實驗平臺如圖3所示。

圖3 實驗平臺

采集的部分數據如表1所示。

表1 采集的部分數據

5.2 FCM算法參數確定

FCM算法中需要確定兩個參數，即聚類數目Cluster和加權指數m。采用兩種評價指標，即Xie-Beni評價指標和緊致性度量指標Com（Cluster），通過實驗確定聚類數目Cluster和加權指數m。Xie-Beni評價指標通過尋找類內緊湊度和類間分離度之間的平衡點，來衡量聚類效果，如方程（18）：

其中，c是聚類數目，n是樣本數目，m是FCM算法中加權指數參數。uij表示第j個樣本屬于第i類的隸屬度，ci是某一類聚類中心，ck也是某一類聚類中心，Xie-Beni指標越小，聚類效果越好。緊致性度量是評價類內的內聚程度，如式（19）所示：

其中，c是聚類數目，n是樣本數目，m是FCM算法加權指數參數，uij表示第j個樣本屬于第i類的隸屬度，ci是某一類聚類中心，ck也是某一類聚類中心，Com(c)值越小，聚類效果越好。

Bezdek[15]指出FCM算法中加權指數m理想范圍為[1.6，2.6]。故依次取加權指數m為1.6、1.8、2.0、2.2、2.4、2.6。在Matlab2017a軟件平臺上，針對m不同取值，分別將實驗室采集的380個由x、y、z坐標和有害氣體濃度構成的四維數據聚成2～16類，以此確定FCM算法聚類數目和加權指數。實驗效果如圖4～圖6。

圖4 Xie-Beni指標與聚類數目關系曲線

圖5 Com(Cluster)指標與聚類數目關系曲線

圖6 仿真時間與聚類數目關系曲線

圖4 是Xie-Beni評價指標與聚類數目關系曲線圖，圖中六條曲線分別是加權指數m取1.6、1.8、2.0、2.2、2.4、2.6時對應的曲線。由圖4知，隨著m取值及聚類數目的變化，Xie-Beni評價指標也隨著變化，且每條曲線在聚類數目為5時，都取得極小值，且所取得的極小值僅比聚類數目10和12時取得極小值稍大。圖5是Com(Cluster)評價指標與聚類數目關系曲線圖，圖中六條曲線分別是加權指數m取1.6、1.8、2.0、2.2、2.4、2.6時對應的曲線。對比圖5六條曲線可知，隨著加權指數m取值增加，Com(Cluster)評價指標逐漸減小，故m取值越大，Com(Cluster)評價指標越小。圖6是仿真時間與聚類數目關系曲線圖，圖中六條曲線分別是加權指數m取1.6、1.8、2.0、2.2、2.4、2.6時對應的曲線。由圖6知，不論m取值如何，隨著聚類數目增加，運行時間一直增加。對比圖4～圖6可知，圖4中，盡管聚類數目為10和12時取得極小值比聚類數目為5時取得的極小值稍小，但在圖5中對應的時間比聚類數目為5時所用時間長很多，故聚類數目取5時，較為合適。綜上分析，本論文聚類數目取5，加權指數m取2.6。

5.3 自主定位策略效果分析

5.3.1 自主定位策略

布谷鳥搜索算法結合改進的模糊C均值聚類算法的自主定位策略包括七個部分，即：模擬煙羽發現，采用改進的FCM聚類算法對四維特征向量聚類，構造目標函數，采用布谷鳥搜索算法迭代生成三維路徑點，計算三維路徑點對應的等效濃度，利用歷史四維特征向量數據和當前迭代的四維特征向量數據構造新的四維特征向量數據，以及反復交替采用布谷鳥搜索算法和改進的FCM聚類算法。

模擬煙羽發現：任取實際采集的由x、y、z和該位置處的煙羽濃度構成的380個四維特征向量中的50個作為初始點，這些初始點即作為煙羽發現的數據點。

采用改進的FCM聚類算法對四維特征向量聚類：采用改進的FCM聚類算法對四維特征向量數據聚類分析。

構造目標函數：根據改進的FCM聚類算法的聚類結果，獲取濃度最大類對應的三維坐標及其對應的濃度，如圖7中的“●”所示，分別求取濃度最大類中所有四維特征向量的三維坐標x、y、z的平均值，作為布谷鳥搜索算法的初始值，以“●”作為參照點，計算布谷鳥搜索算法生成的三維路徑點和該參照點的距離平方和，作為目標函數。根據目標函數，以“●”為參照點，采用布谷鳥搜索算法迭代生成四軸飛行器下一步要搜索的空間區域，如圖7中“×”所示。

圖7 聚類后濃度最大點和布谷鳥搜索算法迭代的路徑點

采用布谷鳥搜索算法迭代生成三維路徑點：根據構造的目標函數，采用布谷鳥搜索算法迭代生成三維路徑點。

計算三維路徑點對應的等效濃度：計算布谷鳥搜索算法迭代生成的每個路徑點與如圖8所示的實際采集的380個三維坐標數據點的距離，以最近的距離對應的實際采集的濃度作為布谷鳥搜索算法迭代生成的三維路徑點的等效濃度。

圖8 真實采集的三維數據及對應濃度散點圖

利用歷史四維特征向量數據和當前迭代的四維特征向量數據構造新的四維特征向量數據：利用歷史數據指的是將前幾次迭代和當前布谷鳥搜索算法迭代生成的三維路徑點和對應的等效濃度構成一組新的四維特征向量，為改進的FCM聚類算法提供了聚類數據。

反復交替采用布谷鳥搜索算法和改進的FCM聚類算法：再次采用改進的FCM聚類算法對采用歷史數據機制構成的新的一組四維特征向量聚類，再次根據濃度最大值，構造目標函數，采用布谷鳥搜索算法迭代生成新的路徑點。反復采用布谷鳥搜索算法結合改進的FCM聚類算法，直到定位到煙羽源附近為止，實現了定位的自主性，布谷鳥搜索算法結合改進的FCM聚類算法自主定位策略流程圖如圖9所示。

5.3.2 實驗效果分析

利用該方法在Matlab中的運行結果如圖10～圖16所示。

圖8是根據實驗室實際采集的380個三維坐標數據及對應濃度畫出的散點圖，右側的柱狀顏色條代表實際采集的濃度信息，隨著顏色的不同，濃度值也不同。因實驗室模擬的污染源實際對應的濃度范圍為：[0.41，3.825]，該范圍與柱狀條顏色一一對應。圖10是根據實際采集的380個數據點中前50個三維坐標數據及其對應的濃度，畫出的散點圖，從圖中可以看出，該50個數據點對應的濃度大致范圍在[0.5，1.2]。對比圖10～圖16可知，僅僅采用已知的50個實驗室采集的濃度數據作為煙羽發現，反復交替使用改進的模糊C均值算法及布谷鳥搜索算法，后一次迭代總能比前一次迭代獲取的煙羽濃度范圍大，通過6次迭代，最終能夠自主定位到煙羽源附近。圖16對應的煙羽濃度范圍為[2.2，3.8]，該范圍是圖8實驗室采集的煙羽濃范圍[0.41，3.825]的子集，且最大濃度很接近，驗證了該定位策略的有效性。為進一步驗證該策略的有效性，做了5次實驗，結果見圖17及表2。

圖9 布谷鳥搜索算法結合FCM聚類算法自主定位策略流程圖

圖10 真實采集的數據點前50個數據對應的散點圖

圖11 第一次迭代產生的坐標及等效濃度散點圖

其中收斂精度是指在每次實驗中，最大等效濃度所對應的三維坐標與實驗室實際采集的煙羽最大濃度所對應的三維坐標的平方和，平方和越小，越能說明收斂到煙羽源附近；收斂時間是指每次實驗總共所用時間。

圖12 第二次迭代產生的坐標及等效濃度散點圖

圖13 第三次迭代產生的坐標及等效濃度散點圖

圖14 第四次迭代產生的坐標及等效濃度散點圖

圖15 第五次迭代產生的坐標及等效濃度散點圖

由表2及圖17知，每次實驗最大濃度所在位置都比較接近實際的煙羽最大濃度所在位置，進一步驗證了該策略的可行性及有效性。

圖16 第六次迭代產生的坐標及等效濃度散點圖

圖17 5次煙羽源定位實驗效果圖

表2 收斂精度及收斂時間

為了進一步驗證改進的模糊C均值聚類算法的效果，采用同樣步驟，交替反復采用布谷鳥搜索算法和未改進的模糊C均值聚類算法，同樣實驗5次，實驗結果見表3。由表3知，采用布谷鳥搜索算法結合改進的模糊C均值聚類算法在煙羽源定位精度、平均迭代次數等方面均優于未改進的模糊C均值聚類算法。

為了更進一步驗證本文所提出的布谷鳥搜索算法結合改進的模糊C均值聚類方法（CS-IFCM）的效果，將該方法與Yan等人[16]提出的改進保證收斂粒子群優化算法（MGC-PSO），Chen等人[17]提出的改進的螢火蟲優化算法（IGSO）及梁志剛等人[18]提出的改進的頭腦風暴優化算法（MBSO）進行對比，結果如表4所示。由表4可以看出，本文所提出的方法（CS-IFCM）平均運行時間最短，收斂精度最高，但平均迭代次數比MGC-PSO算法和IGSO算法的平均迭代次數高，但MGC-PSO算法和IGSO算法的運行時間和收斂精度沒有CS-IFCM方法優。綜合來看，相比算法MGC-PSO、IGSO、MBSO，本文所提出的方法（CS-IFCM）收斂精度分別提高了1.76%、3.0%、2.1%，平均時間分別縮短了28.42%、31.31%、26.86%，定位效果明顯優于其他三種算法。

表3 FCM聚類算法改進前后效果對比

表4 不同定位算法結果對比

6 結束語

針對三維空間鮮有人研究煙羽源自主定位的問題，引入利用歷史數據機制，提出了布谷鳥搜索算法結合改進的模糊C均值聚類算法的自主定位策略。采用評價指標，通過多組實驗確定了模糊C均值算法參數，為驗證所提出的策略獲取了合適的參數。通過布谷鳥搜索算法產生三維空間坐標數據，為煙羽源自主定位提供了位置信息，避免了自主定位的盲目性，實現了定位的自主性；通過引入密度指標函數對模糊C均值聚類算法進行改進，確定了聚類算法的初始聚類中心，采用改進的FCM算法對歷史四維特征向量及當前迭代生成的四維特征向量構成一組新的特征向量聚類分析，獲取三維空間煙羽濃度分布區域，為布谷鳥搜索算法向濃度大的方向搜索提供了支撐。通過5次實驗對所提策略進行驗證并和最近兩年的定位算法對比，結果表明：該方法能夠在已知煙羽發現情況下，通過反復交替使用布谷鳥搜索算法及改進的FCM聚類算法，在平均運行時間和收斂精度上均優于最近兩年的定位算法，且能夠以平均0.145 0 m的收斂精度自主定位到煙羽源附近，為煙羽源定位提供了方法支持。