混沌狼群圍捕算法的車間機(jī)器人導(dǎo)航路徑規(guī)劃

周 璟

（無錫工藝職業(yè)技術(shù)學(xué)院電子信息系，江蘇 宜興 214200）

1 引言

隨著社會的進(jìn)步和生產(chǎn)力發(fā)展，人類對機(jī)器人的活動范圍和工作效率提出了更高要求。機(jī)器人精確導(dǎo)航是機(jī)器人從事一切生產(chǎn)活動的基礎(chǔ)，路徑規(guī)劃是導(dǎo)航的首要工作[1]。研究機(jī)器人導(dǎo)航規(guī)劃問題，對提高機(jī)器人工作效率具有明顯意義。

機(jī)器人導(dǎo)航包括機(jī)器人定位、工作地圖創(chuàng)建、路徑規(guī)劃等三個方面，主要研究機(jī)器人導(dǎo)航路徑規(guī)劃方法。機(jī)器人導(dǎo)航規(guī)劃的研究熱點集中在群智能算法方面，包括粒子群算法、蟻群算法、魚群算法、蜂群算法、狼群圍捕算法等，文獻(xiàn)[2]將差分進(jìn)化算法用于提高粒子群算法多樣性，降低了導(dǎo)航路徑長度；文獻(xiàn)[3]對蟻群算法信息素提出了多種改進(jìn)方法，規(guī)劃出的路徑更短、更平滑；文獻(xiàn)[4]在魚群算法中引入方向算子和免疫記憶操作，使路徑規(guī)劃時間更短、穩(wěn)定性更好；文獻(xiàn)[5]提出了自適應(yīng)搜索因子改進(jìn)人工蜂群算法，兼顧算法搜索與收斂，應(yīng)用于多機(jī)器人協(xié)同規(guī)劃用時較少。相比于其他群智能算法，狼的個體智力更高，狼群捕食行為更能夠體現(xiàn)強(qiáng)強(qiáng)聯(lián)合，群智能算法更加高效。但是基本狼群圍捕算法也存在初始化不合理、易陷入局部極值等問題。

研究了車間移動機(jī)器人導(dǎo)航規(guī)劃問題，建立了機(jī)器人導(dǎo)航規(guī)劃模型，使用狼群圍捕算法進(jìn)行求解。針對狼群圍捕算法易陷入局部極值和初始化不合理問題，改進(jìn)了算法初始化方法、狼群圍捕步長、種群進(jìn)化方法等方面，算法性能得到了改進(jìn)，路徑規(guī)劃結(jié)果得到了提高。

2 狼群圍捕算法

狼群圍捕算法是模擬狼群獵食行為提出的算法，獵食行為被區(qū)分為“游走”“召喚”“圍攻”等行為，按照“強(qiáng)者多得食”的分配方式進(jìn)行優(yōu)勝劣汰[6-7]。

2.1 狼群圍捕算法原理

記搜索空間為d維空間，第i只狼的位置信息為Pi=（pi1，pi2，L，pid），狼群規(guī)模為SN，對于求解最小值問題，記目標(biāo)函數(shù)為f（P），則獵物濃度（適應(yīng)度函數(shù)）為Y=1/f（P）。第i只狼的獵物濃度記為Yi，頭領(lǐng)狼獵物濃度為Ylead。則狼群圍捕算法由以下行為完成：

（1）狼群初始化與競做頭領(lǐng)狼。使用式（1）進(jìn)行狼群位置初始化。

式中：pij—第 i只狼第 j維初始化位置；rand—（0，1）間的隨機(jī)數(shù)；puj、plj—分別為第j維位置的上下限。計算所有狼的適應(yīng)度函數(shù)，適應(yīng)度最大的狼為頭領(lǐng)狼，指揮狼群的圍捕行為。

（2）搜尋行為。為了提高食物搜尋效率，狼向四面八方h個方向前進(jìn)一步，并計算各方向的適應(yīng)度值Yik（k=1，2，L，h），當(dāng)存在Yik大于當(dāng)前位置適應(yīng)度時，選擇最大的Yik作為前進(jìn)方向，則：

（3）奔走行為。在頭領(lǐng)狼號召下，圍攻狼向頭領(lǐng)狼奔走，奔走過程中，若某一位置適應(yīng)度值大于頭領(lǐng)狼，則立馬替代頭領(lǐng)狼指揮狼群。奔走方式為：

（4）圍攻行為。在圍攻狼向頭領(lǐng)狼奔走過程中，當(dāng)其與頭領(lǐng)狼的距離小于某一閾值Slimit時，奔走行為轉(zhuǎn)換為圍攻行為。距離閾值計算方法為：

式中：Slimit—距離閾值；maxj、minj—第 j維最大值與最小值；ω—距

離控制因子。圍攻行為的移動方式為：

式中：Stepc—圍攻步長，λ∈［-1，1］—一個隨機(jī)數(shù)。在圍攻過程中，若某一位置適應(yīng)度值高于頭領(lǐng)狼，則代替頭領(lǐng)狼指揮狼群圍捕獵物。

（5）狼群更新。狼群更新模擬自然選擇過程中，使用“強(qiáng)者生存”法則，選擇適應(yīng)度最差的m只狼淘汰，而后使用隨機(jī)生成方式產(chǎn)生m只狼補(bǔ)充。

2.2 狼群圍捕算法流程

根據(jù)上節(jié)介紹，給出基本狼群圍捕算法流程，如圖1所示。

圖1 基本狼群圍捕算法流程Fig.1 Flow of Basic Wolf Pack Besieging Algorithm

3 混沌狼群圍捕算法的提出

在基本狼群圍捕算法基礎(chǔ)上，從三個方面對狼群圍捕算法進(jìn)行改進(jìn)，分別為種群初始化方法、圍捕步長和種群進(jìn)化方法。

3.1 基于混沌映射的種群初始化

在基本狼群圍捕算法中，狼群初始化使用隨機(jī)函數(shù)實現(xiàn)，這可能導(dǎo)致種群初始分布不均勻，影響算法的尋優(yōu)能力。混沌映射具有遍歷性和類隨機(jī)性[8]，因此提出改進(jìn)混沌映射方法初始化狼群位置。Tent映射結(jié)構(gòu)簡單，分布較均勻，遍歷性好。表達(dá)式為：

式中：a∈（0，1），當(dāng) x1∈（0，1）時系統(tǒng)處于混沌狀態(tài)。

設(shè)置參數(shù)a=0.5、x1=0.32，將Tent映射迭代200次得數(shù)據(jù)序列，如圖2所示。

圖2 Tent映射數(shù)據(jù)Fig.2 Tent Mapping Data

由圖2可以看出，數(shù)據(jù)在（0，1）間的遍歷性很好，但是數(shù)據(jù)主要集中在（0.2～0.8）之間，兩端部分?jǐn)?shù)據(jù)取值較少，鑒于這一問題，引入隨機(jī)方程對Tent映射進(jìn)行擾動，為：

設(shè)置參數(shù)a=0.5、x1=0.32，將改進(jìn)Tent映射迭代200次得數(shù)據(jù)序列，如圖3所示。

圖3 改進(jìn)Tent映射數(shù)據(jù)Fig.3 Improved Tent Mapping Data

對比圖2和圖3可知，改進(jìn)Tent映射既保持了良好的遍歷性，同時相比于Tent映射的分布更加均勻，因此使用隨機(jī)方程擾動的Tent映射初始化狼群位置，使狼群在搜索空間中分布均勻，有利于算法初期對整個區(qū)域的完全搜索。

3.2 Levy飛行改進(jìn)圍攻步長

Levy飛行特點是長時間短距離的來回搜索和偶爾的長距離搜索相互穿插[9]，對于大范圍的搜索空間和有限的搜索個體，levy飛行這一特點既能滿足小范圍的細(xì)致搜索，防止遺失目標(biāo)，也能夠使用偶爾的長距離跳出局部極值。

Levy飛行步長，如圖4所示。從圖中可以看出，levy飛行穿插進(jìn)行了長時間小步長搜索和偶爾大步長搜索。

圖4 Levy飛行步長Fig.4 Levy Fighting Step-length

將levy飛行應(yīng)用于狼群圍攻行為，得：

式中：s—levy飛行步長。Levy飛行長時間小距離來回搜索有利于算法長期進(jìn)行細(xì)致搜索，防止遺失目標(biāo)；偶爾的長距離搜索可以使算法跳出局部極值。

3.3 基于遺傳思想的種群進(jìn)化方法

在基本狼群圍捕算法中，使用“強(qiáng)者生存，弱者淘汰”的生存法則，對于被淘汰個體，使用隨機(jī)生成的方式進(jìn)行補(bǔ)充。這種個體補(bǔ)充方式使種群進(jìn)化效率較低，借鑒遺傳思想提出了種群進(jìn)化方法[10]，可以引導(dǎo)算法朝著收斂的方向進(jìn)化。

（1）父代的選擇。記每次淘汰的狼數(shù)為m，每一次迭代后對狼群依據(jù)適應(yīng)度排序，選擇適應(yīng)度最高的m頭狼作為一組父代Xi，另外一組父代Yi在其余狼中隨機(jī)選取，這樣既能遺傳高適應(yīng)度個體的優(yōu)勢，又能通過隨機(jī)選擇增加種群多樣性。

（2）染色體的構(gòu)造。使用十進(jìn)制方法構(gòu)造染色體，記其維數(shù)為 L，則 X=（x1，x2，…，xL）。

（3）染色體重組。有性生殖通過父代基因重組產(chǎn)生下一代，傳統(tǒng)的重組方法有離散重組、中間重組、混雜重組等，在中間重組基礎(chǔ)上改進(jìn)，提出了權(quán)值可調(diào)節(jié)重組法。記父代染色體分別為Xi與Xj，權(quán)值可調(diào)整重組法為：

式中：α、β—兩個父代的權(quán)重，權(quán)重可以根據(jù)問題特點和父代的適應(yīng)度進(jìn)行設(shè)置，使子代進(jìn)化具有針對性和方向性；權(quán)值也可以隨機(jī)設(shè)置，增強(qiáng)進(jìn)化的隨機(jī)性，增加物種多樣性。

將由式（10）產(chǎn)生的m個個體補(bǔ)充到狼群中，保持種群規(guī)模不變。由以上分析可以看出，通過遺傳方式維持種群規(guī)模并促進(jìn)種群進(jìn)化，既可以遺傳優(yōu)秀個體的優(yōu)勢，同時可以控制種群進(jìn)化方向，在算法收斂和搜索方面都優(yōu)于基本算法。

本節(jié)對算法的三點改進(jìn)，沒有改變算法的流程，因此改進(jìn)算法流程圖與基本算法一致，在此不再給出。

4 機(jī)器人導(dǎo)航問題建模

4.1 環(huán)境建模

依據(jù)機(jī)器人尺寸、障礙物尺寸及分布等情況，通過投影的方式將機(jī)器人工作的三維空間簡化為二維空間，使用矢量建模方法建立工作環(huán)境的二維模型。某一工作區(qū)域的環(huán)境模型，如圖5所示。

圖5 環(huán)境模型Fig.5 Environment Model

圖中多邊形與圓形表示障礙物區(qū)域，S表示出發(fā)點，T表示目標(biāo)點，pi點為中間點。

4.2 路徑表示與適應(yīng)度函數(shù)

正常情況下機(jī)器人路徑由一系列二維點組成，為了與這里的尋優(yōu)算法吻合且降低路徑規(guī)劃復(fù)雜度，將二維搜索問題降為一維，如圖5所示。在起始點與目標(biāo)點之間作n-1條Y軸的平行線，將ST分成n段，只要規(guī)劃出每條平行線的縱坐標(biāo)，就實現(xiàn)了路徑規(guī)劃。

將路徑長度作為路徑規(guī)劃目標(biāo)，路徑長度d（p）各段路徑的累加和，即：

式中：yi—機(jī)器人每一步的縱坐標(biāo)；駐=dST/n—平行線間的距離。

4.3 邊界約束與碰撞檢測

狼群在尋優(yōu)過程中，可能超出邊界，因此狼群每更新完一次就要進(jìn)行一次檢測，當(dāng)狼的位置超越邊界值時則將狼的位置定義為邊界值，否則不進(jìn)行干涉。

前文將障礙物建模為多邊形和圓形兩種情況，因此碰撞檢測也分這兩種情況分析。

（1）多邊形障礙物的碰撞檢測。狼群圍捕算法規(guī)劃出某段路徑后，首先判斷多邊形各頂點與路徑端點橫坐標(biāo)關(guān)系，若處于路徑端點之外則障礙物對此段路徑無影響；若多邊形各頂點在路徑端點內(nèi)，則判斷各頂點在路徑同側(cè)還是兩側(cè)，若處于路徑同側(cè)則不發(fā)生碰撞，若處于路徑兩側(cè)則發(fā)生碰撞。

（2）圓形障礙物的碰撞檢測。計算路徑上任意一點到圓心的距離，若距離大于圓半徑則路徑安全，否則路徑發(fā)生碰撞。

5 仿真驗證及分析

機(jī)器人導(dǎo)航路徑規(guī)劃驗證在在MATLAB仿真環(huán)境下進(jìn)行，設(shè)想機(jī)器人在車間內(nèi)工作或者為家庭服務(wù)機(jī)器人，按照此類機(jī)器人行駛能力和工作環(huán)境大小將機(jī)器人工作區(qū)域設(shè)置為（200×120）m，區(qū)域內(nèi)設(shè)置10個障礙物，障礙物位置及形狀隨機(jī)生成，起點S坐標(biāo)為（0，0），目標(biāo)點 T坐標(biāo)為（180，120）。狼群圍捕算法參數(shù)設(shè)置為：種群規(guī)模SN=30，算法最大迭代次數(shù)MaxCycle=250，搜尋步長Stepa=0.1，奔走步長Stepb=0.2，搜尋方向h=4。

分別使用基本狼群圍捕算法和混沌狼群圍捕算法搜索最優(yōu)路徑，分別運(yùn)行100次。在迭代過程中，兩種算法的最優(yōu)路徑長度隨迭代次數(shù)的變化情況，如圖6所示。

圖6 路徑長度隨迭代次數(shù)變化圖Fig.6 Variation Condition of Path Length with Iteration Time

由圖6可以看出，基本狼群圍捕算法迭代80次后路徑長度不再下降，算法陷入局部極值而無法跳出?；煦缋侨簢端惴ㄔ诘?5次時路徑長度不再下降，算法搜索到最優(yōu)路徑。這是因為混沌狼群圍捕算法中l(wèi)evy飛行具有偶爾長距離搜索的特點，使算法具有跳出局部極值的能力；且遺傳思想可以引導(dǎo)狼群進(jìn)化方向，朝算法收斂方向進(jìn)化，使混沌狼群圍捕算法收斂更快。

混沌狼群圍捕算法與基本狼群圍捕算法搜索的最優(yōu)路徑，如圖7所示。

圖7 基本狼群圍捕算法與混沌狼群圍捕算法規(guī)劃路徑Fig.7 Path Planned by Basic Wolf Pack Besieging Algorithm and Chaotic Wolf Pack Besieging Algorithm

由圖7可以看出，混沌狼群圍捕算法規(guī)劃出的路徑明顯短于基本狼群圍捕算法，這意味著混沌狼群圍捕算法的尋優(yōu)能力優(yōu)于基本狼群圍捕算法，這是因為混沌隱射的狼群初始化方法使狼群分布均勻，利于整個區(qū)域完全搜索；且levy飛行長時間短距離搜索特點，使算法能夠長時間細(xì)致搜索，防止丟失目標(biāo)，使算法尋優(yōu)精度更高。

統(tǒng)計基本狼群圍捕算法與混沌狼群圍捕算法100次搜索路徑的最短長度、最長長度、平均長度與搜索到最短路徑耗時，結(jié)果如表1所示。

表1 兩種算法的性能統(tǒng)計Tab.1 Property Statistics of the Two Algorithms

由表1可知，混沌狼群圍捕算法最短路徑比基本狼群圍捕算法最短路徑長度減少了16.7%，尋優(yōu)耗時減少了37.5%。結(jié)合表1、圖6與圖7的結(jié)果，充分驗證了混沌狼群算法在尋優(yōu)精度和尋優(yōu)耗時上的雙重優(yōu)勢，這是因為使用Tent映射初始化狼群，使狼群分布更加均勻，增加了對整個區(qū)域的搜索能力；其次levy飛行長時間短距離來回搜索與偶爾大步長搜索相互穿插，即實現(xiàn)了細(xì)致搜索，又可以以大步長跳出局部極值，以上兩種改進(jìn)都增加了算法尋優(yōu)能力和精度；再者，使用遺傳思想引導(dǎo)狼群進(jìn)化方向，使狼群算法朝著收斂方向進(jìn)化，增加了算法收斂速度。基于以上原因，與傳統(tǒng)狼群圍捕算法相比，混沌狼群算法在尋優(yōu)精度和收斂速度上均具有明顯優(yōu)勢。

5 結(jié)論

研究了移動機(jī)器人導(dǎo)航規(guī)劃問題，建立了機(jī)器人導(dǎo)航問題模型，使用混沌狼群圍捕算法進(jìn)行求解，經(jīng)仿真驗證得到了以下結(jié)論：（1）基于混沌映射的種群初始化方法可以使狼群分布均勻，利于算法對整個區(qū)域的完全搜索；（2）levy飛行長時間短距離來回搜索與偶爾大步長搜索相互穿插，既有利于算法進(jìn)行長時間細(xì)致搜索，又保持了跳出局部極值的能力；（3）混沌狼群圍捕算法規(guī)劃的路徑長度比傳統(tǒng)狼群算法減少了16.7%，耗時減少了37.5%，證明了混沌狼群算法在收斂速度和尋優(yōu)精度上的優(yōu)勢。