王志中

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

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

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

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

1 問題描述與適應度函數(shù)建立

1.1 障礙物處理

本文研究的是靜態(tài)環(huán)境下機器人路徑規(guī)劃問題，使用智能算法對機器人路徑進行規(guī)劃，首先要進行環(huán)境建模，就是將機器人實際工作區(qū)域轉(zhuǎn)化為數(shù)學模型，以便機器人進行識別。

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

1.2 問題描述與簡化

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

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

(1)

1.3 適應度函數(shù)建立

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

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

(2)

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

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

(3)

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

結(jié)合以上分析，給出機器人路徑規(guī)劃的適應度函數(shù)fit為：

(4)

式中:w1、w2分別為路徑長度、路徑平滑性的調(diào)節(jié)參數(shù)，此參數(shù)的設立，一是為了調(diào)節(jié)不同優(yōu)化目標在適應度函數(shù)中的重要性，二是使不同性能指標實現(xiàn)量級上的統(tǒng)一。分析適應度函數(shù)fit可知，此函數(shù)值越大說明路徑質(zhì)量越高。

2 粒子群算法及改進

2.1 粒子群算法

(5)

2.2 改進粒子群算法

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

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

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

(6)

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

(7)

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

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

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

(8)

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

(9)

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

3 基于改進粒子群算法的路徑規(guī)劃

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

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

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

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

Step7：更新個體歷史最優(yōu)值和種群最優(yōu)值；

Step8：若搜索結(jié)果滿足精度要求或算法迭代次數(shù)達到上限，則算法結(jié)束；否則轉(zhuǎn)至Step5繼續(xù)迭代。

4 仿真實驗驗證

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

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

表1 環(huán)境一下兩算法適應度值

算法最大值平均值最小值平均時間/s傳統(tǒng)算法154141111945改進算法199179138653

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

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

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

5 結(jié)語

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

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

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

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

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

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

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

[7] 金飛虎, 高會軍, 鐘嘯劍. 自適應蟻群算法在空間機器人路徑規(guī)劃中的應用[J]. 哈爾濱工業(yè)大學學報, 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混沌粒子群算法及其在結(jié)構(gòu)優(yōu)化決策中的應用[J]. 控制與決策, 2008, 23(8):857-862.