基于改進粒子群算法的機器人路徑規劃*

王志中

(重慶建筑工程職業學院，重慶 400072)

機器人可以幫助人類完成危險性高、重復性高、條件艱苦的工作，將人類從高風險、高體力勞動的工作中解放出來，而且機器人的使用是國家經濟發展的巨大推力。移動機器人是機器人中智能性較高的一類，移動機器人導航包括位置定位、任務規劃和路徑規劃，其中路徑規劃是機器人導航的基礎性工作[1]。一條好的規劃路徑可以節省行走時間、減少能耗和磨損，達到提高工作效率、節約資源、減少能耗和成本等目的，因此機器人路徑規劃技術的研究具有重要的理論和現實意義。

機器人路徑規劃方法的研究可以分為兩個階段，前期的路徑規劃方法又稱為傳統方法，包括可視圖法[2]、柵格法[3]、人工勢場法[4]；當前路徑規劃方法主要為智能路徑規劃方法，就是使用智能算法搜索規劃出最優路徑，包括神經網絡[5]、遺傳算法[6]、蟻群算法[7]、模糊控制[8]以及它們的改進算法等。傳統方法不具有智能性，面對復雜、隨機、多約束的路徑規劃問題，其規劃結果和普適性較差；智能算法在路徑規劃中會遇到不匹配或不理想的情況，因此出現了各種改進方法用于路徑規劃。

本文對環境障礙物膨化處理，并對環境坐標進行坐標變換，簡化了環境模型；分析了粒子群算法的缺陷并融入了跳出機制和牽引操作，從而提出改進粒子群算法。將此方法應用于路徑規劃中，規劃出的路徑在長度、平滑性、規劃時間上表現更優。

1 問題描述與適應度函數建立

1.1 障礙物處理

本文研究的是靜態環境下機器人路徑規劃問題，使用智能算法對機器人路徑進行規劃，首先要進行環境建模，就是將機器人實際工作區域轉化為數學模型，以便機器人進行識別。

在二維空間中，對各種形狀的障礙物進行“膨化處理”，如圖1所示，就是使用能夠包含該障礙物的最小圓表示，障礙物大小用圓的面積衡量。

1.2 問題描述與簡化

靜態環境下機器人路徑規劃就是在障礙物分布已知的環境中，尋找某種意義下最優從起點至終點的無碰路徑。以圖2為例，圖中在機器人工作區域建立了坐標系OXY，黑色實心物體為未膨化處理的障礙物，記起點坐標為S(xs,ys)，終點坐標為G(xg,yg)，由起點至終點的無碰路徑為Path={S,P1,P2,…,Pj,…,PN,G}，式中j=1,2,…,N，Pj=(xj,yj)為一個位置坐標，若位置點Pj之間的連線不穿過障礙物則此路徑為有效路徑。

為了將上述問題進行簡化，將二維優化問題轉化為一維優化問題 ，本文使用了坐標變換的思想。就是以出發點S為坐標原點，X軸為出發點S與目標點G連線，正向為出發點指向目標點，根據右手定則確定Y軸，這樣就建立了新坐標系O′X′Y′，記新舊坐標系之間的夾角為α，則兩坐標系之間的轉換公式為

(1)

1.3 適應度函數建立

在機器人路徑規劃中，規劃路徑的優劣程度使用適應度函數來評價。在路徑優化中，可以考慮的因素很多，包括路徑長度、平滑性、能耗等諸多方面，考慮到路徑長度與能耗具有很強的相關性，本文對路徑評價時考慮路徑長度、路徑平滑性兩個方面。

(1)路徑長度評價函數fit1的建立。本文使用歐氏距離構建路徑長度評價函數，即:

(2)

式中：d=((xg-xs)/(N+1))2是一個定值。

(2)路徑平滑度適應度函數fit2的建立。眾所周知，兩條路徑的夾角越大則機器人的轉彎壓力越小；相反地，路徑夾角越小則機器人轉彎壓力越大。所以本文使用路徑之間的夾角作為評價路徑平滑度的標準，即：

(3)

式中：β(lj,lj+1)表示路徑lj與路徑lj+1之間的夾角；N為路徑中夾角的個數。分析式(3)可知，fit2值越大則路徑平滑性越好，機器人轉彎壓力越小。

結合以上分析，給出機器人路徑規劃的適應度函數fit為：

(4)

式中:w1、w2分別為路徑長度、路徑平滑性的調節參數，此參數的設立，一是為了調節不同優化目標在適應度函數中的重要性，二是使不同性能指標實現量級上的統一。分析適應度函數fit可知，此函數值越大說明路徑質量越高。

2 粒子群算法及改進

2.1 粒子群算法

(5)

2.2 改進粒子群算法

粒子群算法存在以下兩個缺陷：(1)算法迭代后期，粒子種群多樣性急劇下降，使算法陷入局部最優值而出現“早熟”現象；(2)當粒子被困于較差搜索區域而難以自動跳出時，就會導致搜索效率慢，算法收斂慢的問題。針對這兩個問題，本文分別提出了跳出機制和牽引操作，用于提高粒子群算法的搜索精度和收斂速度。

(1)跳出機制。在粒子群算法迭代的后期，種群多樣性減少，針對這種情況，當粒子多次迭代而適應度值相差不大時，認為此粒子搜索處于停滯狀態，此時對于停滯狀態的粒子，以一定概率p1執行跳出機制，使粒子擺脫停滯狀態，繼續執行搜索操作，從而保持種群的多樣性。

在給出粒子跳出機制前，首先要定義粒子的視覺范圍Visual和步長Step。粒子的視覺范圍是粒子所能感知或看到的范圍，粒子步長為粒子一步前進的最大幅度，且Visual>Step。則粒子的跳出機制定義為：

(6)

執行跳出機制時，首先在粒子i視覺范圍內選擇一個粒子j，若粒子j的適應度值大于粒子i，則粒子i向粒子j的方向前進一步；若粒子j的適應度值不大于粒子i，則在視覺范圍內重新尋找一粒子，重復上述過程；若反復尋找Ntry次后，依然沒有滿足條件的粒子，則粒子i向任意方向前進一步，即：

(7)

而后粒子繼續進行最優解的搜索。跳出機制能夠保持種群的多樣性，增強粒子群的全局搜索能力，避免粒子陷入局部最優。本文具體執行跳出機制時，規定連續T次出現本次和上次適應度值的差值在0.01之內時，認為粒子處于搜索停滯狀態而執行跳出機制。

(2)牽引操作。當粒子被困于較差區域而無法自動跳出時，粒子在較差區域的反復搜索是無效的，是對搜索資源的浪費，導致搜索效率低，算法收斂速度慢。為了解決這一問題，本文提出了牽引操作，就是以一定概率p2選擇陷入較差區域的粒子，對其執行牽引操作，使其盡快跳出較差區域而在其他可能包含最優解的區域搜索，實現搜索資源的有效分配。

以最小值優化問題為例，當粒子適應度值連續三次大于種群平均適應度值時，認為此粒子被困于較差區域而無法自動跳出，對于此類粒子以一定概率p2執行牽引操作，即：

(8)

式中:p0為牽引量，式(8)表示將被困粒子向個體最優和群體最優的中間位置牽引;c3為自適應牽引因子。其計算方法為：

(9)

式中：fit(i)為被困粒子i的適應度值；fitave、fitmin分別為種群中適應度平均值和最小值。分析式(9)可知，被困粒子i適應度值越大，說明此粒子被困區域越差，此時牽引因子越大，越能夠使被困粒子擺脫被困區域，所以牽引因子c3具有自適應性。

3 基于改進粒子群算法的路徑規劃

綜上所述，基于改進粒子群算法的機器人路徑規劃步驟為：

Step1：根據起點位置S和終點位置D建立新坐標系，并進行坐標變換，以下步驟均在新坐標系中進行，路徑規劃完畢后，再將規劃結果轉換到舊坐標系；

Step2：對所有障礙物進行處理，膨化為圓形；

Step5：需要執行牽引操作的粒子使用式(8)進行狀態更新，其他粒子使用式(5)進行粒子狀態更新；

Step7：更新個體歷史最優值和種群最優值；

Step8：若搜索結果滿足精度要求或算法迭代次數達到上限，則算法結束；否則轉至Step5繼續迭代。

4 仿真實驗驗證

使用仿真實驗對本文提出的改進粒子群算法進行驗證。機器人工作環境大小設置為200×200，算法最大迭代次數為2 000，種群大小m=100，粒子維數與平行直線數量一致N=30，學習因子c1=c2=2，粒子視覺范圍Visual=5，步長Step=2，嘗試次數Ntry=5，跳出機制的執行概率p1=0.2，牽引操作的執行概率p2=0.3，在初始坐標中起點坐標為S(0,0)，目標點坐標為G(70.7,-70.7)。

為了驗證改進粒子群算法在機器人路徑規劃中的有效性，分別使用傳統的粒子群算法與改進粒子群算法在同樣條件下進行路徑規劃，共進行兩組實驗，第二組實驗相較于第一組環境略微復雜，每組實驗均執行100次，圖4和圖5給出了不同環境下兩組算法的規劃結果，表1給出了在環境一下兩種算法的統計數據。

表1 環境一下兩算法適應度值

算法最大值平均值最小值平均時間/s傳統算法154141111945改進算法199179138653

由圖4和圖5中兩種算法的規劃結果可以看出，兩種算法都能夠規劃出一條無碰路徑。但是對比圖4中兩條路徑。可以看出改進算法的路徑平滑度明顯優于傳統算法；對比圖5中兩算法的規劃結果，改進算法的規劃路徑不僅在平滑度上明顯優于傳統算法，而且改進算法的規劃路徑明顯短于傳統算法，傳統算法規劃出的路徑存在繞彎路的情況。

由表1中數據可以看出，在100次實驗中，改進算法規劃路徑適應度的最大值、平均值、最小值均大于傳統算法。按照式(4)建立的適應度函數可知，改進算法規劃出的路徑在長度和平滑性上優于傳統算法；且改進算法的路徑規劃時間也短于傳統算法。

改進算法在路徑長度、路徑平滑度、規劃時間上的優勢，是因為改進算法中引入了跳出機制和牽引操作，跳出機制保持了種群多樣性，也就保證了算法的全局搜索能力，所以其相對于傳統算法能找到更優解；牽引操作能夠牽引被困粒子向全局最優和自身歷史最優運動，提高算法收斂速度，所以改進算法的規劃時間短于傳統算法。此仿真實驗充分說明了改進算法在路徑規劃中的有效性。

5 結語

通過以上分析可以得出以下結論：(1)通過坐標變換，可以將二維優化問題簡化為一維優化問題，簡化了問題的求解；(2)跳出機制可以保持種群多樣性，也就保持了算法的全局搜索能力；(3)牽引操作能夠使被困粒子跳出被困區域，向全局最優和自身歷史最優收斂，提高了算法收斂速度；(4)本文提出的改進算法規劃出的路徑在長度、平滑度和規劃時間上均具有優勢。

[1]李文學, 饒運清, 戚得眾,等. 全向輪機器人路徑規劃與導航系統設計[J]. 機械設計與制造,2014(12):18-22.

[2]陳超, 唐堅, 靳祖光,等. 一種基于可視圖法導盲機器人路徑規劃的研究[J]. 機械科學與技術, 2014, 33(4): 490-495.

[3]柴寅, 唐秋華, 鄧明星,等. 機器人路徑規劃的柵格模型構建與蟻群算法求解[J]. 機械設計與制造, 2016, 4(4): 178-181.

[4] 劉傳領. 基于勢場法和遺傳算法的機器人路徑規劃技術研究[D]. 南京：南京理工大學, 2012.

[5]呂戰永, 曹江濤. 自反饋生物激勵神經網絡機器人路徑規劃[J]. 計算機工程與應用, 2014, 50(16):255-258.

[6] 田欣. 基于改進遺傳算法的移動機器人路徑規劃研究[D]. 鄭州：鄭州大學, 2016.

[7] 金飛虎, 高會軍, 鐘嘯劍. 自適應蟻群算法在空間機器人路徑規劃中的應用[J]. 哈爾濱工業大學學報, 2010, 42(7):1014-1018.

[8]徐悅, 林志賢, 姚劍敏,等. 關于機器人導航目標點搜索路徑模糊控制[J]. 計算機仿真, 2016, 33(10):300-304.

[9] Singh G, Deep K. A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku[M]. Elsevier Science Publishers B. V. ，2016.

[10]張浩, 張鐵男, 沈繼紅,等. Tent混沌粒子群算法及其在結構優化決策中的應用[J]. 控制與決策, 2008, 23(8):857-862.