Maklink環(huán)境下機(jī)器人導(dǎo)航路徑的蛙跳多種群粒子群優(yōu)化

李 碩，蘇 鳴，趙 燕

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

1 引言

機(jī)器人路徑規(guī)劃是機(jī)器人導(dǎo)航的基礎(chǔ)性研究工作，對(duì)機(jī)器人安全性、穩(wěn)定性及工作效率具有極大影響，合理的行駛路徑在避開障礙物的同時(shí)能夠快速到達(dá)目標(biāo)點(diǎn)完成設(shè)定任務(wù)[1]，因此研究機(jī)器人路徑規(guī)劃問題具有明顯意義。

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

研究了靜態(tài)環(huán)境下機(jī)器人路徑規(guī)劃問題，提出了蛙跳多種群粒子群算法和Maklink圖接合的規(guī)劃方法。在粒子群算法基礎(chǔ)上，引入蛙跳算法深度搜索的方法，提出了蛙跳多種群粒子群算法，達(dá)到了減少機(jī)器人工作路徑長(zhǎng)度同時(shí)減少運(yùn)行時(shí)間的目的。

2 環(huán)境建模與問題建模

2.1 環(huán)境建模

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

式中：O i—第i個(gè)障礙物；W SB—工作區(qū)域邊界。

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

圖1 Maklink模型Fig.1 Maklink Model

2.2 問題建模

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

式中：p i1、p i2—p i所對(duì)應(yīng)鏈接線的兩個(gè)端點(diǎn)；t i∈[ 0，1]—滑動(dòng)系數(shù)。

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

3.1 蛙跳算法

蛙跳算法概念簡(jiǎn)單、參數(shù)較少，具有極強(qiáng)的全局搜索能力。記青蛙的搜索空間維度為D，第i個(gè)青蛙位置記為將青蛙按照適應(yīng)度值進(jìn)行降序排列，然后根據(jù)適應(yīng)度排序?qū)⑵浞譃閙個(gè)子群，具體分配方法為：將第一只青蛙分配給第1組，第二只青蛙分配給第2組，以此類推，以m為周期直至將所有青蛙分配完畢。

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

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

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

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

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

主群和副群采用不同的速度和位置更新方法。主群主要用于算法收斂，提高算法的收斂精度，速度和位置更新方法使用傳統(tǒng)粒子群算法的更新方法。副群主要負(fù)責(zé)全局深度搜索，參考蛙跳算法的速度和位置更新方法進(jìn)行更新，即：

式中：w—慣性權(quán)重；c1、c2—學(xué)習(xí)因子；r1、r2—（0，1）間的隨機(jī)數(shù)；p i—粒子i為歷史最優(yōu)位置；p s—此副群的最優(yōu)位置。若使用式（5）所示更新方法無(wú)法提高粒子適應(yīng)度，則使用式（6）進(jìn)行更新：

式中：p g—整個(gè)種群的最優(yōu)位置。

若按照式（6）給出的速度和位置更新方法依然無(wú)法提高粒子的適應(yīng)度，則隨機(jī)生成一個(gè)粒子并替代當(dāng)前粒子。設(shè)置深度搜索次數(shù)為t cyc，若到達(dá)深度搜索次數(shù)則算法結(jié)束，否則重復(fù)進(jìn)行式（5）或式（6）的更新過程。

3.3 多種群算法的合作機(jī)制

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

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

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

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

3.4 多種群算法流程

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

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

（2）隨機(jī)產(chǎn)生各粒子位置；

（3）計(jì)算各粒子適應(yīng)度值，將所有粒子按照適應(yīng)度降序排列；

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

（5）副群深度搜索。副群深度搜索時(shí)，反復(fù)執(zhí)行以下3個(gè)步驟，直至到達(dá)t cy c進(jìn)入（6）；

①計(jì)算粒子適應(yīng)度，挑選出每個(gè)副群的最優(yōu)解P i和全局最優(yōu)解P g；

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

③計(jì)算每個(gè)副群最優(yōu)解P i，若副群最優(yōu)解優(yōu)于全局最優(yōu)解，則使用P i替代主群中最差解；

（6）判斷是否執(zhí)行粒子遷移。當(dāng)滿足粒子遷移條件時(shí)，將所有粒子打亂，按照適應(yīng)度值進(jìn)行重新分群；

（7）算法終止。判斷算法是否達(dá)到最大迭代次數(shù)，若是則算法結(jié)束，同時(shí)輸出全局最優(yōu)粒子位置，否則轉(zhuǎn)至（3）。

4 仿真分析

4.1 蛙跳多種群粒子群算法性能測(cè)試

將蛙跳多種群粒子群算法應(yīng)用于機(jī)器人路徑二次優(yōu)化之前，先對(duì)算法的搜索性能進(jìn)行測(cè)試。選擇兩種類型的測(cè)試函數(shù)，分別為：

式中：D—測(cè)試函數(shù)的維度。

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

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

為了形成對(duì)比，同時(shí)使用標(biāo)準(zhǔn)粒子群算法（PSO）、文獻(xiàn)[11]MSCPSO算法和這里蛙跳多種群算法（Leapfrog Multi-group PSO，LMGPSO）搜索10維度測(cè)試函數(shù)的最小值結(jié)果，如圖3所示。

圖3 測(cè)試函數(shù)的迭代過程Fig.3 Iteration Process of Test Function

使用三種粒子群算法對(duì)兩個(gè)測(cè)試函數(shù)的搜索最優(yōu)結(jié)果，如表1所示。

表1 測(cè)試函數(shù)搜索最優(yōu)值Tab.1 Searching Optimal Value of Test Function

由圖3和表1可知，不管是單峰函數(shù)f1(x)還是多峰函數(shù)f2(x)，提出的蛙跳多種群粒子群算法均具有最高的搜索精度，而PSO算法和MSCPSO算法都不同程度地陷入局部最優(yōu)而無(wú)法跳出，導(dǎo)致搜索到的最小值精度較差。這是因?yàn)楸疚乃惴ㄖ懈比菏褂蒙疃人阉鞑呗?，提高了算法的搜索精度和速度；同時(shí)算法的粒子遷移策略使子群每隔一定周期就進(jìn)行重組，使算法具備了跳出局部極值的能力。

4.2 結(jié)論分析

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

圖4 待優(yōu)化路徑Fig.4 Path to Optimize

以此三條路徑為基礎(chǔ)，按照2.2節(jié)給出的二次優(yōu)化方法，分別使用PSO算法、MSCPSO算法、LMGPSO算法對(duì)此三條路徑進(jìn)行二次優(yōu)化并選出最佳路徑，算法的參數(shù)設(shè)置與4.1節(jié)一致，迭代過程，如圖5所示。

圖5 二次優(yōu)化迭代過程Fig.5 Iteration Process of the Secondary Optimization

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

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

統(tǒng)計(jì)三種粒子群算法對(duì)路徑進(jìn)行二次優(yōu)化時(shí)的迭代次數(shù)、運(yùn)行時(shí)間及最短路徑結(jié)果，如表2所示。

表2 結(jié)果對(duì)比Tab.2 Comparison of Result

從圖6和表2可以看出，蛙跳多種群粒子群算法具有最佳的優(yōu)化效果，最短路徑長(zhǎng)度比MSCPSO算法減少了3.82%，比PSO算法減少了5.46%。另外，蛙跳多種群粒子群算法與MSCPSO算法的迭代次數(shù)幾乎一樣，但是運(yùn)行時(shí)間卻減少了25.53%，這是因?yàn)橥芴喾N群粒子群算法一個(gè)迭代周期的耗時(shí)較少。綜上所述，就優(yōu)化精度和耗時(shí)來(lái)講，蛙跳多種群粒子群算法優(yōu)于另外兩種算法，這是因?yàn)楦比河糜趨^(qū)域的深度搜索，能夠提高算法的優(yōu)化精度；另外，粒子遷移方法通過粒子混合重組方式可以跳出局部極值，從而具有最佳的搜索性能。

5 結(jié)論

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