Maklink環境下機器人導航路徑的蛙跳多種群粒子群優化

李 碩，蘇 鳴，趙 燕

（1.武昌首義學院，湖北 武漢 430064；2.武漢科技大學，湖北 武漢 430080）

1 引言

機器人路徑規劃是機器人導航的基礎性研究工作，對機器人安全性、穩定性及工作效率具有極大影響，合理的行駛路徑在避開障礙物的同時能夠快速到達目標點完成設定任務[1]，因此研究機器人路徑規劃問題具有明顯意義。

機器人路徑規劃是按照某一或某些準則，在工作空間中找到由起始點到目標點的最優或次優路徑。路徑規劃主要兩個方面的研究：（1）建立環境模型，將機器不可識別的現實環境轉化為可識別的環境模型；（2）設計優化算法，達到目標函數最優。當前存在的環境模型包括可視圖法、柵格圖法和鏈接圖法等，其中可視圖法隨障礙物增多其運算復雜度也大大增加，不適用于復雜環境中[2]；柵格法原理簡單，但是信息存儲量大、抗干擾能力弱、決策效率低下[3]；鏈接圖法占用存儲空間小、搜索復雜性低[4]，本文使用鏈接圖法建立環境模型。在優化算法方面，使用較多的包括快速擴展隨機樹[5]、人工勢場法[6]、粒子群算法[7]、遺傳算法[8]、魚群算法[9]等。通過路徑建模與問題轉化，將機器人路徑規劃問題轉化為優化問題，并使用群智能算法進行尋優求解成為了當前的研究熱點。

研究了靜態環境下機器人路徑規劃問題，提出了蛙跳多種群粒子群算法和Maklink圖接合的規劃方法。在粒子群算法基礎上，引入蛙跳算法深度搜索的方法，提出了蛙跳多種群粒子群算法，達到了減少機器人工作路徑長度同時減少運行時間的目的。

2 環境建模與問題建模

2.1 環境建模

鑒于鏈接圖法占用存儲空間小、搜索復雜性低的優點，使用鏈接圖法建立環境模型。首先給出兩個假設：（1）根據障礙物和機器人的三維分布，將三維工作空間投影為二維空間。（2）將障礙物半徑進行膨脹，膨脹尺寸為機器人半徑，從而可以將機器人視為一個質點。使用鏈接圖法進行建模，則所有障礙物用頂點進行表示，記第i個障礙物O i具有n i個頂點，那么工作環境的鏈接圖模型為：

式中：O i—第i個障礙物；W SB—工作區域邊界。

機器人工作的自由空間是由鏈接線圍成的凸區域組成，如圖1所示。圖中：S點—路徑起點；T點—終點，深色實體多邊形—障礙物區域，實線—鏈接線，虛線—由鏈接線上的點連接而成的路徑。鏈接線需滿足四個條件：（1）連接線的端點為障礙物頂點或環境邊沿；（2）每條鏈接線均是兩個自由區域的邊界線；（3）鏈接線不允許穿過障礙物；（4）每個自由區域具有兩條以上邊界線。

圖1 Maklink模型Fig.1 Maklink Model

2.2 問題建模

首先使用MS算法[10]規劃出從起點至目標點的路徑，選擇長度較短的前C條路徑作為待優化對象，而后使用第3節中的蛙跳多種群粒子群算法對路徑進行二次優化。記由MS算法得到的路徑為，二次優化就是使用蛙跳多種群粒子群算法對p1，p2，…，p D的位置進行優化，從而減少路徑長度。具體方法是使p1，p2，…，p D在自身鏈接線上滑動，通過確定p i，i=1，2，…，D在鏈接線上的具體位置而確定最優路徑。p i，i=1，2，…，D在自身鏈接線上的滑動方法為：

式中：p i1、p i2—p i所對應鏈接線的兩個端點；t i∈[ 0，1]—滑動系數。

3 基于蛙跳算法的多種群粒子群算法

3.1 蛙跳算法

蛙跳算法概念簡單、參數較少，具有極強的全局搜索能力。記青蛙的搜索空間維度為D，第i個青蛙位置記為將青蛙按照適應度值進行降序排列，然后根據適應度排序將其分為m個子群，具體分配方法為：將第一只青蛙分配給第1組，第二只青蛙分配給第2組，以此類推，以m為周期直至將所有青蛙分配完畢。

每個子群各自進行深度搜索。記某個子群第t次迭代后適應度最差粒子為X w，適應度最佳粒子為X b，則算法的速度和位置更新方法為：

式中：Ωi(t+1)—第t+1次迭代的青蛙速度；rand—（0，1）間的隨機數。

若fi t(X w(t+1))≤fit(X w(t))，即位置更新后X w的適應度沒有得到提高，則隨機生成一個粒子替代X w。當所有子群的深度搜索結束后，所有粒子混合并重新分組，直至算法結束。

3.2 多種群算法的分群與更新策略

多種群粒子群算法是粒子群算法改進的一個重要方向，它相比于單子群粒子群算法具有更優的搜索性能。在多種群算法中，將整個粒子群劃分為S個子群，每個子群均在整個搜索空間內獨立搜索。粒子的分群方法與蛙跳算法一致，按照粒子適應度進行降序排列，而后以S為周期進行分群，直至將粒子分配完畢。其中最優粒子所在子群稱為主群，其余S-1個子群稱為副群。

主群和副群采用不同的速度和位置更新方法。主群主要用于算法收斂，提高算法的收斂精度，速度和位置更新方法使用傳統粒子群算法的更新方法。副群主要負責全局深度搜索，參考蛙跳算法的速度和位置更新方法進行更新，即：

式中：w—慣性權重；c1、c2—學習因子；r1、r2—（0，1）間的隨機數；p i—粒子i為歷史最優位置；p s—此副群的最優位置。若使用式（5）所示更新方法無法提高粒子適應度，則使用式（6）進行更新：

式中：p g—整個種群的最優位置。

若按照式（6）給出的速度和位置更新方法依然無法提高粒子的適應度，則隨機生成一個粒子并替代當前粒子。設置深度搜索次數為t cyc，若到達深度搜索次數則算法結束，否則重復進行式（5）或式（6）的更新過程。

3.3 多種群算法的合作機制

多種群算法的合作機制主要包括兩個方面：（1）子群的遷移時機，也即子群重組時機；（2）主群與副群間的信息交流機制。

（1）子群遷移時機。由前文可知，副群負責在全局的深度搜索，那么子群的遷移時機影響算法的搜索精度和收斂速度。當子群遷移頻率快時，算法沒有進行足夠的深度搜索，則算法的搜索精度會降低，但是子群遷移產生的信息交流可以加快算法收斂；同樣的，當子群遷移頻率慢時，算法能夠進行充分的深度搜索，此時算法的搜索精度會提高，但是各自獨立的工作會降低算法收斂速度。因此，這里采用折中的遷移周期，當算法迭代一定次數后，子群進行遷移，即將所有粒子重新按照適應度排序并重新分組。

（2）子群間信息交流方法。若信息在各子群間共享，則失去了分群的意義，算法極易在種群最優的引導下陷入局部最優；但是若各子群間不進行信息交流，則失去了子群間協作的意義。因此本文設定各副群間不進行信息交流，信息交流只在各副群與主群間進行。信息交流方式為：當某個副群的最優粒子位置優于主群時，則將最優位置共享給主群，同時將主群內最差粒子去除，從而保持主群的粒子規模。當主群同時接到多個副群的最優粒子時，則主群選擇其中最優的粒子進行替換。主群與副群之間信息共享的示意圖，如圖2所示。

圖2 信息共享方法Fig.2 Information Share Method

3.4 多種群算法流程

根據設置的多種群粒子群算法的分群方法、更新策略和合作機制，制定蛙跳多種群粒子群算法的步驟為：

（1）初始化算法參數，包括種群規模N、粒子維度D、子群數量S、深度搜索次數t c yc、算法最大迭代次數tmax；

（2）隨機產生各粒子位置；

（3）計算各粒子適應度值，將所有粒子按照適應度降序排列；

（4）分群。將所有粒子按照前文所述方法分為S個子群，含有最佳粒子的子群為主群，其余S-1個子群為副群；

（5）副群深度搜索。副群深度搜索時，反復執行以下3個步驟，直至到達t cy c進入（6）；

①計算粒子適應度，挑選出每個副群的最優解P i和全局最優解P g；

②副群執行深度搜索，即根據式（5）更新速度和位置，若粒子適應度未提高，則使用式（6）更新速度和位置，若粒子適應度仍未提高，則重新初始化粒子位置；

③計算每個副群最優解P i，若副群最優解優于全局最優解，則使用P i替代主群中最差解；

（6）判斷是否執行粒子遷移。當滿足粒子遷移條件時，將所有粒子打亂，按照適應度值進行重新分群；

（7）算法終止。判斷算法是否達到最大迭代次數，若是則算法結束，同時輸出全局最優粒子位置，否則轉至（3）。

4 仿真分析

4.1 蛙跳多種群粒子群算法性能測試

將蛙跳多種群粒子群算法應用于機器人路徑二次優化之前，先對算法的搜索性能進行測試。選擇兩種類型的測試函數，分別為：

式中：D—測試函數的維度。

測試函數f1(x)是球體函數，為單峰函數，最小值為f1min(0)=0；測試函數f2(x)為多峰函數，會使算法陷入局部極值，最小值為f2min(0)=0。

仿真在Matlab 2012a環境下進行，電腦配置為Intel Core（TM）i5-3210M CPU，內存4GB，硬盤1T。算法的參數設置為：種群規模N=100，子群數量S=5，深度搜索次數t cyc=50、算法最大迭代次數tmax=500，學習因子c1=c2=1.5。

為了形成對比，同時使用標準粒子群算法（PSO）、文獻[11]MSCPSO算法和這里蛙跳多種群算法（Leapfrog Multi-group PSO，LMGPSO）搜索10維度測試函數的最小值結果，如圖3所示。

圖3 測試函數的迭代過程Fig.3 Iteration Process of Test Function

使用三種粒子群算法對兩個測試函數的搜索最優結果，如表1所示。

表1 測試函數搜索最優值Tab.1 Searching Optimal Value of Test Function

由圖3和表1可知，不管是單峰函數f1(x)還是多峰函數f2(x)，提出的蛙跳多種群粒子群算法均具有最高的搜索精度，而PSO算法和MSCPSO算法都不同程度地陷入局部最優而無法跳出，導致搜索到的最小值精度較差。這是因為本文算法中副群使用深度搜索策略，提高了算法的搜索精度和速度；同時算法的粒子遷移策略使子群每隔一定周期就進行重組，使算法具備了跳出局部極值的能力。

4.2 結論分析

以圖1所示的機器人工作環境為規劃背景，首先使用MS算法規劃出最短的3條路徑，如圖4所示。

圖4 待優化路徑Fig.4 Path to Optimize

以此三條路徑為基礎，按照2.2節給出的二次優化方法，分別使用PSO算法、MSCPSO算法、LMGPSO算法對此三條路徑進行二次優化并選出最佳路徑，算法的參數設置與4.1節一致，迭代過程，如圖5所示。

圖5 二次優化迭代過程Fig.5 Iteration Process of the Secondary Optimization

從圖中可以看出，這里提出的蛙跳多種群粒子群算法對路徑的優化程度最高，得到的路徑長度為6.2147，其次為MSCPSO算法，路徑長度為6.4616，PSO算法最差，路徑長度為6.5737。蛙跳多種群粒子群算法搜索的最優粒子位置為p g={0.0735，0.0291，0.2811，0.9999，0.5146，0.4809}。三種粒子群算法搜索的最優路徑，如圖6所示。

圖6 三種粒子群算法的優化路徑Fig.6 Optimized Path by Three PSO

統計三種粒子群算法對路徑進行二次優化時的迭代次數、運行時間及最短路徑結果，如表2所示。

表2 結果對比Tab.2 Comparison of Result

從圖6和表2可以看出，蛙跳多種群粒子群算法具有最佳的優化效果，最短路徑長度比MSCPSO算法減少了3.82%，比PSO算法減少了5.46%。另外，蛙跳多種群粒子群算法與MSCPSO算法的迭代次數幾乎一樣，但是運行時間卻減少了25.53%，這是因為蛙跳多種群粒子群算法一個迭代周期的耗時較少。綜上所述，就優化精度和耗時來講，蛙跳多種群粒子群算法優于另外兩種算法，這是因為副群用于區域的深度搜索，能夠提高算法的優化精度；另外，粒子遷移方法通過粒子混合重組方式可以跳出局部極值，從而具有最佳的搜索性能。

5 結論

研究了移動機器人的路徑規劃問題，建立了工作環境的Maklink圖，首先使用MS算法規劃出若干條最短路徑，而后提出了蛙跳多種群粒子群算法對路徑進行二次優化。通過仿真驗證可以看出：（1）與PSO算法和MSCPSO算法相比，LMGPSO算法對單峰函數和多峰函數均具有最佳的搜索性能；（2）將蛙跳多種群粒子群算法應用于機器人路徑規劃，可以得到最短的規劃路徑，且算法運行時間較短。