基于改進的五行環算法的移動機器人路徑規劃

黃敬堯，劉洪宇，武慧慧，王欽甜

（三峽大學 電氣與新能源學院，湖北 宜昌 443002）

0 引 言

路徑規劃是移動機器人的熱門研究之一，隨著科技的進步和社會的發展，移動機器人智能化和自動化的水平逐步提高，已經逐漸滲透到日常的生活中［1］。移動機器人需要規劃出從工作環境的起點位置到目標位置的路徑，并且滿足效能高、安全性高等要求，還必須能夠避開沿途的障礙物。移動機器人的路徑規劃具有重要的研究意義和價值，國內外學者已將其作為研究熱點。

作為智能搜索法的遺傳算法（genetic algorithm，GA）、蟻群算法、粒子群優化（particle swarm optimization，PSO）算法等算法，可以通過隨機的可行初始解出發以及迭代改進的策略，不斷地逼近最優路徑，從而求出最優解。楊洋等人針對多自動導引運輸車（automated guided vehicle，AGV）避障路徑優化問題，提出一種改進蟻群算法和彈性時間窗相結合的多AGV避障路徑優化策略［2］。不僅能在無人倉庫中實現多AGV快速規劃，同時還能找到最優的躲避障礙物的路徑。羅陽陽等人針對PSO算法能快速收斂，但容易陷入局部最優的問題，設計了一種突變算子來提高全局尋優能力［3］。雖然迭代次數會大幅增多，但其需要調節的參數較少，在更新機制中僅需要追蹤2 個“極值”來進行不斷的更新，也是很有可取之處的。

本文提出一種改進的五行環算法來解決機器人路徑規劃問題。在五行環模型的基礎上，采用PSO算法的更新機制來對元素進行更新。為了避免過早出現的較優解使得種群陷入局部最優解陷阱，采用變異的思想，設計了突變元子。為了避免種群快速趨同而降低元素的搜索效率，設計了散開元子。最后對路徑進行連接點刪除，刪除了不必要的連接點，使得路徑更優。通過仿真結果表明，采用改進的五行環算法能夠使移動機器人找到最優路徑的同時具有高度的穩定性，也證明了算法改進的可行性和有效性。

1 問題描述與環境建模

本文將環境映射為柵格地圖，即將環境轉化為由相同大小格子構成的一個柵格矩陣［4，5］。對每個柵格以實數進行編碼，將實際障礙物對應的柵格以0填充，在地圖中以黑色表示，對可行區域以1 填充，以白色表示。本文采用20 ×20和30 ×30的兩種柵格地圖，如圖1 所示。每個柵格的邊長為1，其中機器人的起始點與目標點都已標明。

圖1 環境模型

2 改進五行環算法的移動機器人路徑規劃

2.1 五行環模型

五行環模型［6］是建立在五行（金、水、木、土、火）相生相克原理的基礎上，通過計算各個體之間的相互作用關系如圖2，比較出個體適應值的優劣，然后來對解進行更新，從而找出系統的最優解。

圖2 五行元素相互關系

從圖2中可以看出，5種元素之間，由相生關系和相克關系建立了各個元素之間的關系，既相互促進又相互克制，形成了一個復雜的動態平衡［7］。為了將其應用到各種復雜的優化問題，文獻［8］提出了五行環算法，并且將它推廣到了一般形式，其一般表達式為

式中 mij（t）為第t 代中第j 個環中第i 個元素的質量，Fij（t）為元素的力。假設復雜系統中總共有h 個環（j ＝1，2，…，h），y個元素（i ＝1，2，…，y），則種群的規模為h×y。

在五行環模型中，每個環中的元素Fij（t）都由4 個部分的力組成：1）上輩元素的“生”力：若上輩元素的質量大于元素本身的質量，則此部分力為正值，反之力為負值。2）祖輩元素的“克”力：其力本身為負值，若元素本身的質量大于其祖輩元素的質量，則力變為正值。3）本元素對子元素的“生”力：這部分力會使自身能量產生損耗，因此為負值。4）本元素對祖輩元素的“克”力：同樣在施加力的過程中消耗了自身的能量，因此其力也為負值。式（1）中質量的表達采用的是logsig 函數，其用來表示在力的作用下質量的變化。其中，i ＝1 時，用y 替代i -1，用y -1 替代i-2；i ＝2時，用y替代i-2；i ＝y-1時，用1替代i ＋2；i ＝y時，用1替代i ＋1，用2替代i ＋2。

2.2 路徑規劃

2.2.1 PSO算法

在PSO算法中，群體中所有個體都被抽象為在d維空間中無重量和體積的粒子，并在搜索空間中以不同的速度飛行［9］。粒子在飛行時，通過追蹤2 個“極值”來不斷地更新自己的速度和位置，一個是全局極值，一個是個體極值［10］，其更新的速度和位置公式如下

2.2.2 突變元子［13］

具體突變方式是：先將實數編碼轉換為二進制編碼，再隨機生成一個整數（不能大于有效編碼的總長度的整數值）作為突變連接點的個數，然后在編碼區內隨機確定突變的連接點位置，在突變位置上對該連接點進行突變（將1→0，0→1），最后將其轉化為實數編碼。

2.2.3 散開元子

為了減輕元素快速趨同帶來的不利影響，本文設計了散開元子［14］。對搜索空間中處于某一位置上的多個相同的元素僅保留一個，而對其余的元素進行突變使其離開原來的位置，突變方法和2.2.2節一致。如圖3 所示，在某一搜索空間中，如果同時聚集了3 個以上的元素，則元素A保持不變，其余元素被移至其他的位置；如果聚集了不到3個元素，則允許它們都保留在原位。

圖3 散開元子示意

2.2.4 改進的五行環算法

1）更新機制

通過對Fij（t）的計算，可以將結果分為Fij（t）＞0 和Fij（t）≤0兩類。若Fij（t）＞0，則采用式（2）的更新機制對元素群進行更新，并使用散開元子避免出現快速趨同的現象；若Fij（t）≤0，則xij（t）使用突變元子更新。

2）mij（t）變化規則

在使用五行環模型時，采用xij（t）表示第t代中第j個環的第i個元素的解，即xij（t）表示一條可行路徑，而S 表示搜索連接點的總個數。用（xd，yd）表示第d 個連接點的坐標，d ＝1，2，…，S，重新定義mij（t），mij（t）表示一條可行路徑的歐氏距離，其表達式為

式中 κ為縮小因素。

3）適應度函數

每個元素的適應度函數［15］表達式為

改進的五行環算法具體步驟為：1）初始化參數，隨機生成種群。2）通過式（1）計算mij（0）。3）通過式（1）計算Fij（t），根據結果采用不同的更新機制。4）計算各個元素群的適應度值，并通過式（3）計算mij（t ＋1）。5）如果沒達到最大迭代次數T，則令t ＝t ＋1，繼續返回進行步驟（3）；如果達到最大迭代次數T則結束整個流程。

2.2.5 連接點刪除［16］

圖4為連接點刪除的簡單示意，黑色虛線為連接點刪除之前的路徑，淺色實線為刪除連接點之后的路徑。

圖4 連接點刪除示意

3 仿真與分析

對比了五行環優化算法、PSO算法、GA和A*算法，并分別置于2種不同柵格環境的2種不同復雜度的地圖中進行路徑規劃，并進行仿真與比較分析。圖5 是柵格環境為20 ×20的簡單和復雜地圖（障礙物覆蓋率為30%）不同算法的路徑規劃。僅展示不同地圖的改進五行環算法、五行環優化算法和PSO算法3種算法的路徑規劃。

圖5 不同復雜度地圖的20 ×20 機器人路徑規劃路線

從圖5中可以明顯觀察到，當3 種算法不論是在簡單地圖還是在復雜地圖中規劃的最優路線中，五行環優化算法能用較短時間規劃出一條路徑，但其穩定性極差，局部搜索能力不強，規劃出來的路徑較長。PSO 算法在進行路徑規劃時極其容易陷入局部最優解的陷阱中，搜索時間較長，收斂效果較差。而本文改進的五行環算法規劃出的路徑軌跡最為平滑，拐點數目明顯少于其他算法，能在短時間內規劃處最短的無碰撞的路徑。

表1為各算法在20 ×20 柵格環境不同復雜度地圖的路徑規劃數據，設每個柵格邊長1 cm。

表1 5 種算法的數據比較（20 ×20 地圖）

從表1中數據可得，A*算法在路徑規劃中的路徑長度是最長的；GA和PSO算法總體上穩定性較高，但有少數波動情況，導致平均路徑大于最短路徑，拐點數目也較多；五行環優化算法的數據波動最大，穩定性低，導致最短路徑和平均路徑差距較大；改進五行環算法在穩定性上遠優于五行環優化算法，規劃出的路徑長度也比其他算法短，在簡單環境地圖中的最短路徑和平均路徑都能保持在26.307 1 cm，在復雜環境地圖中的最短路徑和平均路徑都能保持在28.4493 cm，在對其進行連接點刪除處理之后，甚至能達到26.129 cm和27.602 5 cm的最短路徑。

本文設計了柵格環境為30 ×30的簡單和復雜地圖（障礙物覆蓋率為30%），不同算法的路徑規劃如圖6。

圖6 不同復雜度地圖的30 ×30 機器人路徑規劃路線

從表2中可知，改進五行環算法在更大的柵格地圖中仍然能穩定地規劃出一條最優路徑，路徑長度和拐點數目都明顯優于其他算法。在對連接點進行刪除處理后，簡單地圖中的路徑長度可以縮短至25.284 6 cm，復雜地圖中的路徑長度可縮短至43.791 9 cm。

圖7為改進的五行環算法的收斂曲線?？梢悦黠@看出，在迭代次數為100次時，本文算法在第8代時就已經收斂并保持穩定狀態，而其他算法都達不到這么快的收斂速度。

圖7 收斂效果

4 結 論

本文結合五行環優化算法和粒子群算法的優點，提出了一種改進的五行環算法，用柵格法對環境進行建模，通過2種不同柵格環境、4 個不同復雜度的地圖、5 種不同算法來對機器人的行駛路徑進行規劃。而且路徑上的障礙物數量的不同、路徑規劃空間的不同，更體現了改進的五行環算法的優勢。通過更新機制、突變元子、散開元子和連接點刪除等一系列流程后，所得的路徑更優、長度更短。仿真結果表明：改進的五行環算法改進使得種群粒子能夠跳出局部最優解，提高了算法的性能，也就是說算法的收斂速度和算法的穩定性都得到了大幅提升。