基于混合人工魚群算法的機(jī)器人路徑規(guī)劃研究

張 軍 于士坤

（1.安徽理工大學(xué)人工智能學(xué)院；2.安徽理工大學(xué)機(jī)械工程學(xué)院 安徽淮南 232001）

移動(dòng)機(jī)器人的路徑規(guī)劃是指在一個(gè)工作空間中，依據(jù)特定的優(yōu)化準(zhǔn)則（如行走成本最小、行走路徑長度最短、耗費(fèi)時(shí)間最少等），找到一條從起始位置到目標(biāo)位置的最優(yōu)路徑,并且不能碰撞任何障礙物[[1]。目前，國內(nèi)外學(xué)者針對(duì)路徑規(guī)劃問題進(jìn)行了廣泛探索并提出了諸多有效算法，如人工勢(shì)場(chǎng)法[2]、遺傳算法[3]、蟻群算法[4]、粒子群算法[5]、快速隨機(jī)樹算法[6]、人工魚群算法[7]等。這些算法均能解決一定環(huán)境下的機(jī)器人尋路問題，但規(guī)劃結(jié)果往往不是最優(yōu)，需進(jìn)一步研究改進(jìn)。

文獻(xiàn)[8]在傳統(tǒng)蟻群算法中加入偽隨機(jī)因子，減少了迭代次數(shù)、加快了收斂速度，有效提高了蟻群算法尋找路徑尋優(yōu)的效率。文獻(xiàn)[9]在JPS算法基礎(chǔ)上，提出以2個(gè)優(yōu)化目標(biāo)對(duì)路徑點(diǎn)序列進(jìn)行平滑處理的方法，并利用多段高階多項(xiàng)式對(duì)所得軌跡進(jìn)行優(yōu)化，使路徑長度得到減少，并明顯提高了路徑平滑性。文獻(xiàn)[[10]針對(duì)A＊算法的水下重力匹配導(dǎo)航路徑規(guī)劃問題，通過前后向?qū)Ρ确治鰧?duì)單個(gè)路徑節(jié)點(diǎn)逐個(gè)進(jìn)行篩選過濾，有效減少了冗余航向調(diào)整，提高了算法效率和路徑的平滑度。文獻(xiàn)[11]使用神經(jīng)網(wǎng)絡(luò)改進(jìn)了粒子群算法，改進(jìn)后的算法在動(dòng)態(tài)和靜態(tài)障礙物環(huán)境中均可以高效規(guī)劃出理想路徑。文獻(xiàn)[12]提出了無碰撞檢測(cè)RRT算法，去除了RRT算法中的碰撞檢測(cè)，在代價(jià)函數(shù)中引入風(fēng)險(xiǎn)評(píng)估函數(shù)，使改進(jìn)后的算法大幅度提高了收斂速度，且具有良好適應(yīng)性。文獻(xiàn)[13]在無人機(jī)的路徑規(guī)劃問題中對(duì)遺傳算法的選擇、交叉和變異算子進(jìn)行了改進(jìn)，顯著提高了算法的性能。文獻(xiàn)[14]針對(duì)船舶航跡規(guī)劃問題，在傳統(tǒng)蟻群算法基礎(chǔ)上提出了領(lǐng)頭頂點(diǎn)蟻群算法，通過保證蟻群的領(lǐng)頭并利用頂點(diǎn)法對(duì)路徑進(jìn)行優(yōu)化，使算法耗費(fèi)時(shí)間和路徑航路點(diǎn)數(shù)量都得到減少。

人工魚群算法是由李曉磊博士等人提出的一種群智能優(yōu)化算法，通過模仿魚群的聚群、追尾、覓食等行為尋找最優(yōu)解，在機(jī)器人路徑規(guī)劃中取得了較好效果。但是，傳統(tǒng)人工魚群算法存在收斂速度較慢、尋優(yōu)精度較低、規(guī)劃出的路徑折點(diǎn)多等不足[15]，通過將人工魚與天牛須算法進(jìn)行融合，利用動(dòng)態(tài)人工魚視野和動(dòng)態(tài)擁擠度因子來平衡兼顧算法的全局收斂和局部搜索能力，以提高混合算法的尋優(yōu)精度。將混合算法在不同規(guī)模的柵格地圖中進(jìn)行仿真驗(yàn)證，結(jié)果表明規(guī)劃出的路徑在長度和折點(diǎn)數(shù)發(fā)面均有明顯改善。

一、基本人工魚群算法

人工魚群算法是通過觀察模擬魚群行為得出的優(yōu)化算法。在某片水域里，魚群往往集中在食物最豐富的地方，通過模仿魚群的一些列行為便可以實(shí)現(xiàn)尋找最優(yōu)解的目的。在魚群中，每條魚都具有覓食、聚群、追尾和隨機(jī)四種行為，魚類通過按照一定規(guī)則迭次進(jìn)行這四種行為可以逐步趨向食物最優(yōu)處（最優(yōu)解）。

假設(shè)魚群由S條人工魚組成，向量X=（x1,x2,x3,…,xs）表示每條人工魚個(gè)體的狀態(tài),其中i=1,2,3,…,S；Yi=f（Xi）表示人工魚當(dāng)前位置食物濃度，f（）為目標(biāo)函數(shù)；人工魚個(gè)體間距為dij=||xi-xj||；visual表示人工魚的視野范圍；δ表示擁擠度因子；step表示人工魚的移動(dòng)步長；try_number表示人工魚進(jìn)行覓食活動(dòng)的最大嘗試次數(shù)；rand為0到1之間的隨機(jī)數(shù)。

（一）覓食行為。覓食行為表示人工魚趨向高食物濃度方向的行為，狀態(tài)為Xi的人工魚個(gè)體在其視野范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，其適應(yīng)分別計(jì)算適應(yīng)度值并進(jìn)行比較，若Yj優(yōu)于Yi，則Xi向Xj方向移動(dòng)一步，Xj更新為移動(dòng)之后的新狀態(tài)，否則重新覓食。

若嘗試try_number次后仍未滿足覓食前進(jìn)的條件，則進(jìn)行隨機(jī)行為。

（二）聚群行為人工魚魚為保證自身生存和躲避危害會(huì)自然地聚集成群，聚群行為能夠加強(qiáng)算法的全局收斂性。狀態(tài)為Xi的人工魚個(gè)體從當(dāng)前當(dāng)前位置視野內(nèi)搜索到伙伴數(shù)目為Nf，并獲取視獲伙伴的中心位置Xc，若Yc/Nf優(yōu)于δYi，表明中心位置狀態(tài)較優(yōu)且不太擁擠，則Xi向Xc位置方向移動(dòng)一步，否則執(zhí)行覓食行為。

擁擠度因子δ用來表示魚群的擁擠程度，通多調(diào)整δ可以限制人工魚的聚群規(guī)模，防止局部最優(yōu)。

（三）追尾行為。追尾行為表示當(dāng)某條魚發(fā)現(xiàn)食物后，魚群向其所在位置靠攏的行為。狀態(tài)為Xi的人工魚個(gè)體從當(dāng)前位置視野內(nèi)搜索伙伴數(shù)目Nf和狀態(tài)最優(yōu)個(gè)體Xj，Nf適應(yīng)度值為Yj，若Yj/Nf優(yōu)于δYi，表明Xj位置狀態(tài)較優(yōu)且不太擁擠，則Xi向Xj位置方向移動(dòng)一步。否則執(zhí)行覓食行為。

（四）隨機(jī)行為。隨機(jī)行為是覓食行為的一個(gè)缺省行為。當(dāng)反復(fù)進(jìn)行一定次數(shù)的覓食嘗試后仍未滿足移動(dòng)條件時(shí)，人工魚便會(huì)在視野范圍內(nèi)隨機(jī)移動(dòng)一步。隨機(jī)行為能在一定程度上防止局部最優(yōu)。

（五）公告板。公告板用來記錄人工魚的最優(yōu)位置。人工魚將每次行動(dòng)所得位置與公告板中的位置進(jìn)行比較，若新獲得的位置狀態(tài)更優(yōu)秀，則將共告板中的位置進(jìn)行更新，反之則不做處理。

二、天牛須算法

天牛須算法[16]是受到天牛覓食原理啟發(fā)而開發(fā)的算法。與其他依靠種群智能的仿生算法不同，天牛須算法只需要一個(gè)天牛個(gè)體便可以完成尋優(yōu)過程。天牛在覓食時(shí)會(huì)根據(jù)兩側(cè)觸角來檢測(cè)食物氣味的強(qiáng)弱，從而選擇前進(jìn)方向。如果其中一側(cè)檢測(cè)到的狀態(tài)較優(yōu)，則向該側(cè)方向前進(jìn)一步，否則轉(zhuǎn)向另一側(cè)前進(jìn)。當(dāng)?shù)竭_(dá)下一個(gè)狀態(tài)位置時(shí)，天牛的轉(zhuǎn)向是隨機(jī)的，將重新根據(jù)兩側(cè)觸角檢測(cè)結(jié)果來決定前進(jìn)方向。通過迭代前進(jìn)，逐步接近目標(biāo)點(diǎn)。天牛須算法的具體步驟為：

（1）為模擬搜索行為，隨機(jī)生成天牛搜索的方向向量，并進(jìn)行標(biāo)準(zhǔn)化

其中，n是待優(yōu)化參數(shù)的維度。

（2）計(jì)算兩側(cè)觸角的坐標(biāo)

其中，xt為t時(shí)刻天牛質(zhì)心的坐標(biāo)，dt是t時(shí)刻質(zhì)心到觸角的距離，xl和xr分別為t時(shí)刻左右兩側(cè)觸角坐標(biāo)。

（3）根據(jù)兩觸角對(duì)應(yīng)的適應(yīng)度函數(shù)值，決定下一時(shí)刻的移動(dòng)方向，并計(jì)算要到達(dá)的位置

其中，δt為t時(shí)刻的移動(dòng)步長，f為適應(yīng)度函數(shù)。

（4）參數(shù)更新

其中，dt和δt分別是搜索距離和步長的更新衰減系數(shù)。

三、混合人工魚群算法與柵格法

（一）混合人工魚群算法。融合人工魚群算法和天牛須算法的優(yōu)點(diǎn)，利用天牛須算法對(duì)人工魚群算法進(jìn)行優(yōu)化。傳統(tǒng)人工魚群算法存在較多隨機(jī)性，在避免陷入局部最優(yōu)的同時(shí)也會(huì)降低算法的收斂性，考慮天牛須算法全局收斂性強(qiáng)的優(yōu)點(diǎn)，在聚群或追尾行為與后續(xù)的覓食和隨機(jī)行為之間，加入一次人工魚個(gè)體利用天牛須算法尋優(yōu)的過程，以提高算法的全局收斂性。提出動(dòng)態(tài)視野范圍和擁擠度因子，使算法兼顧全局和局部收斂性。構(gòu)想流程圖如圖1。

圖1 混合算法流程圖

每條人工魚在尋優(yōu)過程中分別從兩個(gè)方向嘗試，第一方向?yàn)椋壕廴盒袨?、追尾行為、天牛尋?yōu)行為、覓食行為和隨機(jī)行為；第二方向?yàn)椋鹤肺残袨?、天牛尋?yōu)行為、覓食行為和隨機(jī)行為。其間，每個(gè)方向的任一行為成功，則結(jié)束本方向流程，并在公告板更新結(jié)果；然后流程轉(zhuǎn)到另一方向嘗試。兩個(gè)方向流程的嘗試結(jié)束后，當(dāng)前人工魚移動(dòng)到公告板所記錄的位置，得到當(dāng)前人工魚本次尋優(yōu)所得的最優(yōu)位置。算法以第一條人魚為尋優(yōu)基準(zhǔn)，當(dāng)?shù)谝粭l人工魚到達(dá)目標(biāo)點(diǎn)時(shí)結(jié)束算法，否則，下一條人工魚繼續(xù)執(zhí)行尋優(yōu)過程。

（二）動(dòng)態(tài)調(diào)整人工魚視野和擁擠度因子。

1.動(dòng)態(tài)視野。視野范圍的大小直接影響到人工魚的搜索能力。人工魚在進(jìn)行聚群、追尾、覓食和隨機(jī)行為時(shí)，都需要在一定的視野范圍內(nèi)搜尋位置?；救斯~群算法中，視野參數(shù)被設(shè)為固定值。視野范圍較大時(shí)，人工魚的全局尋優(yōu)能力強(qiáng)，但在接近目標(biāo)點(diǎn)時(shí)的收斂能力弱；視野范圍較小時(shí)，人工魚后期收斂能力強(qiáng)，但全局尋優(yōu)能力弱，且易陷入局部最優(yōu)[17]。在混合算法中，通過引入下降函數(shù)來動(dòng)態(tài)調(diào)整視野參數(shù)，使人工魚的視野隨著趨近目標(biāo)值而逐漸下降，讓算法兼顧全局搜索和在目標(biāo)點(diǎn)附近的收斂能力。使用柯西-洛倫茲函數(shù)作為下降函數(shù)[18]，函數(shù)曲線如圖4所示，當(dāng)x0=0、γ=2時(shí)函數(shù)曲線下降較為平緩且下降幅度較小，適合用來調(diào)整人工魚視野。柯西-洛倫茲函數(shù)的具體形式為：

通過柯西-洛倫茲函數(shù)調(diào)節(jié)視野參數(shù)，有

其中，dig表示當(dāng)前點(diǎn)與目標(biāo)點(diǎn)之間的距離，dsg表示起始點(diǎn)與目標(biāo)點(diǎn)之間的距離。

圖2 柯西-洛倫茲分布

2.動(dòng)態(tài)擁擠度因子。擁擠度因子δ表示一定范圍內(nèi)魚群的擁擠程度，人工魚在進(jìn)行聚群、追尾和覓食行為時(shí)，都需要對(duì)搜尋所得點(diǎn)附近的擁擠程度進(jìn)行判斷。在路徑規(guī)劃問題中，δ越大表示允許的擁擠程度越大，有利于全局搜索但精度較差，反之則有利于提高收斂性局部搜索但易陷入局部最優(yōu)。在混合算法中，引入放大系數(shù)Eδ使擁擠度因子δ隨迭代次數(shù)增加而逐步增大，有

（三）在基本人工魚群算法中引入天牛須算法?；救斯~群算法的尋優(yōu)過程存在一定的隨機(jī)性，為提高算法的全局收斂性，在尋優(yōu)過程中引入天牛須算法。在人工魚聚群或追尾失敗后，先進(jìn)行一次天牛尋優(yōu)行為進(jìn)行位置搜索，嘗試?yán)锰炫ｍ殞?yōu)的方法進(jìn)行一次移動(dòng)，即

其中k表示天牛須搜索的迭代次數(shù)，xl和xr表示天牛左右須的位置。天牛尋優(yōu)的流程圖如圖3。

圖3 天牛須算法流程圖

若搜索成功則將所得位置更新到公告板，否則執(zhí)行覓食和隨機(jī)行為。

（四）適應(yīng)柵格地圖的混合算法。

1.柵格地圖。采用柵格法建立地圖模型，將移動(dòng)機(jī)器人的行走環(huán)境空間由三維轉(zhuǎn)換為二維并進(jìn)行單元分割，將其用大小相等的方塊表示出來。黑色方格表示障礙物，白色方格表示允許通行，如圖4（a）所示。機(jī)器人只能在可行走柵格中通行，不能通過障礙物柵格。

對(duì)于每個(gè)柵格來說，其鄰接的8個(gè)柵格為可行走柵格。相鄰柵格的距離用中點(diǎn)的歐式距離表示，距離值為1或，如圖4（b）所示。

圖4 柵格地圖環(huán)境

2.鄰接矩陣。鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。通過建立一個(gè)二維數(shù)組來存儲(chǔ)柵格地圖的信息，矩陣的規(guī)模為n2×n2，n為地圖每一維的長度，n2表示地圖中的柵格總數(shù)。每個(gè)柵格都有唯一對(duì)應(yīng)的序列號(hào)，圖5展示了柵格在地圖中的標(biāo)號(hào)排序方式。鄰接矩陣的每一行存儲(chǔ)了對(duì)應(yīng)序列柵格與所有柵格的通行關(guān)系，障礙物柵格與所有柵格的關(guān)系值都為0；非障礙物柵格與鄰接可行走柵格的關(guān)系值為1或，與非鄰接?xùn)鸥竦年P(guān)系值為0；所有柵格與本身的關(guān)系值為0。在柵格地圖中，人工魚的下一移動(dòng)位置只會(huì)在與當(dāng)前柵格關(guān)系值不為0的柵格中產(chǎn)生。以圖1為例建立的鄰接矩陣如公式（17）。

圖5 柵格標(biāo)識(shí)方法(xi,yi)

人工魚在柵格地圖中移動(dòng)時(shí)，只可以在相鄰的非障礙物柵格移動(dòng)。設(shè)定每次移動(dòng)的步長固定為1，在MATLAB仿真中，利用取整函數(shù)使人工魚每次移動(dòng)后的位置坐標(biāo)為柵格左上角的點(diǎn)（用該點(diǎn)代表相應(yīng)柵格）。人工魚的可行域?yàn)榕c當(dāng)前柵格在鄰接矩陣中的關(guān)系值不為0的柵格。

通過適應(yīng)度函數(shù)可以評(píng)價(jià)人工魚位置的好壞，設(shè)人工魚當(dāng)前位置柵格坐標(biāo)為（xi,yi），目標(biāo)點(diǎn)位置為（xg,yg），則目適應(yīng)度函數(shù)為：

（五）混合算法的具體實(shí)現(xiàn)步驟。如圖1所示，改進(jìn)算法實(shí)現(xiàn)的具體步驟為：

1.初始化參數(shù)，包括魚群規(guī)模S，人工魚視野Visual，擁擠度因子δ，擁擠度因子放大系數(shù)Eδ，人工魚移動(dòng)步長step，覓食最大嘗試次數(shù)try_number，天牛法迭代次數(shù)bas_n，天牛步長bas_step，起點(diǎn)Xstart和終點(diǎn)Xgoal。

2.記第一條人工魚為x1，設(shè)置其為位置為Pstart，隨機(jī)設(shè)置其他人工魚位置，記錄每條人工魚的位置及其適應(yīng)度值。

3.當(dāng)前人工魚進(jìn)行位置移動(dòng)。每條人工魚在當(dāng)前位置分別進(jìn)行兩種選項(xiàng)的嘗試。選項(xiàng)一：①執(zhí)行聚群行為，若成功則更新公告板并跳出此選項(xiàng)，否則繼續(xù)執(zhí)行下一環(huán)節(jié)；②執(zhí)行天牛尋優(yōu)行為，若成功則更新公告板并跳出此選項(xiàng)，否則繼續(xù)執(zhí)行下一環(huán)節(jié)；③執(zhí)行覓食和隨機(jī)行為，更新公告板。選項(xiàng)二：與選項(xiàng)一相比除將環(huán)節(jié)①中的聚群行為變?yōu)樽肺残袨橥?，其余環(huán)節(jié)與選項(xiàng)一相同。

4.若當(dāng)前人工魚為x1，則將x1的位置加入路徑path，判斷人工魚x1的位置是否為目標(biāo)點(diǎn)位置，若是則結(jié)束算法并輸出所得路徑，否則按順序更換人工魚執(zhí)行步驟3。

四、仿真實(shí)驗(yàn)

利用柵格法，在不同規(guī)模的地圖環(huán)境分別進(jìn)行基本人工魚群算法和混合人工魚群算法路徑規(guī)劃的仿真實(shí)驗(yàn)。建立30*30、50*50、100*100的柵格地圖環(huán)境，初始參數(shù)：S=n，Visual=0.6×n，δ=0.618,step=1,try_number=10,起點(diǎn)Xstart為（1,1），終點(diǎn)Xgoal為（n,n），改進(jìn)算法中，Eδ=1.019，天牛尋優(yōu)迭代次數(shù)bas_iteration=50,天牛步長bas_step=1.5以上n表示柵格地圖每一維的大小。在30*30地圖環(huán)境中的試驗(yàn)結(jié)果如圖6所示。

圖6 30＊30地圖路徑規(guī)劃結(jié)果

在50*50地圖環(huán)境中的試驗(yàn)結(jié)果如圖7所示。在30*30、50*50和100*100地圖環(huán)境中均對(duì)兩種算法進(jìn)行20次隨機(jī)試驗(yàn)。統(tǒng)計(jì)三種地圖環(huán)境中基本算法和混合算法的路徑信息，包括最長路徑、最短路徑、最大折點(diǎn)數(shù)、最小折點(diǎn)數(shù)、平均路徑長度和平均折點(diǎn)數(shù)，得到三種地圖環(huán)境的數(shù)據(jù)如表1-3所示。

圖7 50＊50地圖路徑規(guī)劃結(jié)果

表1 30＊30柵格地圖仿真結(jié)果

表2 50＊50柵格地圖仿真結(jié)果

表3 100＊100柵格地圖仿真結(jié)果

對(duì)比不同地圖環(huán)境中的試驗(yàn)結(jié)果可見，混合算法規(guī)劃出的路徑明顯優(yōu)于基本人工魚群算法，前者路徑更短且折點(diǎn)數(shù)量更少。對(duì)于機(jī)器人而言，路徑更短表示可以減少能量耗費(fèi)、節(jié)約時(shí)間成本，折點(diǎn)數(shù)更少則表示可以減少機(jī)器人設(shè)備的磨損和消耗，延長使用壽命。

以100*100地圖中的仿真結(jié)果表3為例，與基本人工魚群算法相比混合算法的最長路徑和最大折點(diǎn)數(shù)分別減少了29.90%和38.46%，最短路徑和最小折點(diǎn)數(shù)分別減少了6.02%和23.07%，平均路徑長度和平均折點(diǎn)數(shù)量分別減少了13.48%和19.74%。

考慮到仿真實(shí)驗(yàn)的隨機(jī)性因素，平均路徑長度和平均折點(diǎn)數(shù)更能代表算法的性能。根據(jù)表1-3，利用對(duì)應(yīng)的優(yōu)化率數(shù)據(jù)制成折線圖，如圖8所示。

圖8 混合算法對(duì)路徑的優(yōu)化程度

從圖8可以看出，在不同地圖中，相對(duì)于基本算法，利用混合算法規(guī)劃出的路徑平均路徑長度和平均折點(diǎn)數(shù)都有明顯改善，并且隨著地圖規(guī)模的增大，混合算法的優(yōu)勢(shì)也隨之?dāng)U大。

五、結(jié)語

提出了混合人工魚群算法，有效提高了人工魚群算法的全局尋優(yōu)能力，利用下降函數(shù)來逐步調(diào)整視野參數(shù)并提出動(dòng)態(tài)擁擠度因子，使算法兼顧了全局搜索和在目標(biāo)點(diǎn)附近的收斂能力。在30*30、50*50和100*100柵格地圖環(huán)境中分別進(jìn)行了20次隨機(jī)仿真實(shí)驗(yàn)，數(shù)據(jù)顯示混合算法規(guī)劃出的路徑與基本人工魚群算法相比，三種柵格地圖平均長度分別減少了10.37%、11.51%和13.48%，平均折點(diǎn)數(shù)量分別減少11.11%、14.60%和19.74%。

仿真實(shí)驗(yàn)的結(jié)果表明，在相同地圖環(huán)境下混合算法規(guī)劃出的路徑更短，折點(diǎn)數(shù)更少，且隨著地圖的增大，優(yōu)化效果逐漸提高。可以預(yù)見，在更大規(guī)模的地圖環(huán)境中，混合算法將更具優(yōu)勢(shì)。