基于混合人工魚群算法的機器人路徑規劃研究

張 軍 于士坤

（1.安徽理工大學人工智能學院；2.安徽理工大學機械工程學院 安徽淮南 232001）

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

文獻[8]在傳統蟻群算法中加入偽隨機因子，減少了迭代次數、加快了收斂速度，有效提高了蟻群算法尋找路徑尋優的效率。文獻[9]在JPS算法基礎上，提出以2個優化目標對路徑點序列進行平滑處理的方法，并利用多段高階多項式對所得軌跡進行優化，使路徑長度得到減少，并明顯提高了路徑平滑性。文獻[[10]針對A＊算法的水下重力匹配導航路徑規劃問題，通過前后向對比分析對單個路徑節點逐個進行篩選過濾，有效減少了冗余航向調整，提高了算法效率和路徑的平滑度。文獻[11]使用神經網絡改進了粒子群算法，改進后的算法在動態和靜態障礙物環境中均可以高效規劃出理想路徑。文獻[12]提出了無碰撞檢測RRT算法，去除了RRT算法中的碰撞檢測，在代價函數中引入風險評估函數，使改進后的算法大幅度提高了收斂速度，且具有良好適應性。文獻[13]在無人機的路徑規劃問題中對遺傳算法的選擇、交叉和變異算子進行了改進，顯著提高了算法的性能。文獻[14]針對船舶航跡規劃問題，在傳統蟻群算法基礎上提出了領頭頂點蟻群算法，通過保證蟻群的領頭并利用頂點法對路徑進行優化，使算法耗費時間和路徑航路點數量都得到減少。

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

一、基本人工魚群算法

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

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

（一）覓食行為。覓食行為表示人工魚趨向高食物濃度方向的行為，狀態為Xi的人工魚個體在其視野范圍內隨機選擇一個狀態Xj，其適應分別計算適應度值并進行比較，若Yj優于Yi，則Xi向Xj方向移動一步，Xj更新為移動之后的新狀態，否則重新覓食。

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

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

擁擠度因子δ用來表示魚群的擁擠程度，通多調整δ可以限制人工魚的聚群規模，防止局部最優。

（三）追尾行為。追尾行為表示當某條魚發現食物后，魚群向其所在位置靠攏的行為。狀態為Xi的人工魚個體從當前位置視野內搜索伙伴數目Nf和狀態最優個體Xj，Nf適應度值為Yj，若Yj/Nf優于δYi，表明Xj位置狀態較優且不太擁擠，則Xi向Xj位置方向移動一步。否則執行覓食行為。

（四）隨機行為。隨機行為是覓食行為的一個缺省行為。當反復進行一定次數的覓食嘗試后仍未滿足移動條件時，人工魚便會在視野范圍內隨機移動一步。隨機行為能在一定程度上防止局部最優。

（五）公告板。公告板用來記錄人工魚的最優位置。人工魚將每次行動所得位置與公告板中的位置進行比較，若新獲得的位置狀態更優秀，則將共告板中的位置進行更新，反之則不做處理。

二、天牛須算法

天牛須算法[16]是受到天牛覓食原理啟發而開發的算法。與其他依靠種群智能的仿生算法不同，天牛須算法只需要一個天牛個體便可以完成尋優過程。天牛在覓食時會根據兩側觸角來檢測食物氣味的強弱，從而選擇前進方向。如果其中一側檢測到的狀態較優，則向該側方向前進一步，否則轉向另一側前進。當到達下一個狀態位置時，天牛的轉向是隨機的，將重新根據兩側觸角檢測結果來決定前進方向。通過迭代前進，逐步接近目標點。天牛須算法的具體步驟為：

（1）為模擬搜索行為，隨機生成天牛搜索的方向向量，并進行標準化

其中，n是待優化參數的維度。

（2）計算兩側觸角的坐標

其中，xt為t時刻天牛質心的坐標，dt是t時刻質心到觸角的距離，xl和xr分別為t時刻左右兩側觸角坐標。

（3）根據兩觸角對應的適應度函數值，決定下一時刻的移動方向，并計算要到達的位置

其中，δt為t時刻的移動步長，f為適應度函數。

（4）參數更新

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

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

（一）混合人工魚群算法。融合人工魚群算法和天牛須算法的優點，利用天牛須算法對人工魚群算法進行優化。傳統人工魚群算法存在較多隨機性，在避免陷入局部最優的同時也會降低算法的收斂性，考慮天牛須算法全局收斂性強的優點，在聚群或追尾行為與后續的覓食和隨機行為之間，加入一次人工魚個體利用天牛須算法尋優的過程，以提高算法的全局收斂性。提出動態視野范圍和擁擠度因子，使算法兼顧全局和局部收斂性。構想流程圖如圖1。

圖1 混合算法流程圖

每條人工魚在尋優過程中分別從兩個方向嘗試，第一方向為：聚群行為、追尾行為、天牛尋優行為、覓食行為和隨機行為；第二方向為：追尾行為、天牛尋優行為、覓食行為和隨機行為。其間，每個方向的任一行為成功，則結束本方向流程，并在公告板更新結果；然后流程轉到另一方向嘗試。兩個方向流程的嘗試結束后，當前人工魚移動到公告板所記錄的位置，得到當前人工魚本次尋優所得的最優位置。算法以第一條人魚為尋優基準，當第一條人工魚到達目標點時結束算法，否則，下一條人工魚繼續執行尋優過程。

（二）動態調整人工魚視野和擁擠度因子。

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

通過柯西-洛倫茲函數調節視野參數，有

其中，dig表示當前點與目標點之間的距離，dsg表示起始點與目標點之間的距離。

圖2 柯西-洛倫茲分布

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

（三）在基本人工魚群算法中引入天牛須算法。基本人工魚群算法的尋優過程存在一定的隨機性，為提高算法的全局收斂性，在尋優過程中引入天牛須算法。在人工魚聚群或追尾失敗后，先進行一次天牛尋優行為進行位置搜索，嘗試利用天牛須尋優的方法進行一次移動，即

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

圖3 天牛須算法流程圖

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

（四）適應柵格地圖的混合算法。

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

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

圖4 柵格地圖環境

2.鄰接矩陣。鄰接矩陣是表示頂點之間相鄰關系的矩陣。通過建立一個二維數組來存儲柵格地圖的信息，矩陣的規模為n2×n2，n為地圖每一維的長度，n2表示地圖中的柵格總數。每個柵格都有唯一對應的序列號，圖5展示了柵格在地圖中的標號排序方式。鄰接矩陣的每一行存儲了對應序列柵格與所有柵格的通行關系，障礙物柵格與所有柵格的關系值都為0；非障礙物柵格與鄰接可行走柵格的關系值為1或，與非鄰接柵格的關系值為0；所有柵格與本身的關系值為0。在柵格地圖中，人工魚的下一移動位置只會在與當前柵格關系值不為0的柵格中產生。以圖1為例建立的鄰接矩陣如公式（17）。

圖5 柵格標識方法(xi,yi)

人工魚在柵格地圖中移動時，只可以在相鄰的非障礙物柵格移動。設定每次移動的步長固定為1，在MATLAB仿真中，利用取整函數使人工魚每次移動后的位置坐標為柵格左上角的點（用該點代表相應柵格）。人工魚的可行域為與當前柵格在鄰接矩陣中的關系值不為0的柵格。

通過適應度函數可以評價人工魚位置的好壞，設人工魚當前位置柵格坐標為（xi,yi），目標點位置為（xg,yg），則目適應度函數為：

（五）混合算法的具體實現步驟。如圖1所示，改進算法實現的具體步驟為：

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

2.記第一條人工魚為x1，設置其為位置為Pstart，隨機設置其他人工魚位置，記錄每條人工魚的位置及其適應度值。

3.當前人工魚進行位置移動。每條人工魚在當前位置分別進行兩種選項的嘗試。選項一：①執行聚群行為，若成功則更新公告板并跳出此選項，否則繼續執行下一環節；②執行天牛尋優行為，若成功則更新公告板并跳出此選項，否則繼續執行下一環節；③執行覓食和隨機行為，更新公告板。選項二：與選項一相比除將環節①中的聚群行為變為追尾行為外，其余環節與選項一相同。

4.若當前人工魚為x1，則將x1的位置加入路徑path，判斷人工魚x1的位置是否為目標點位置，若是則結束算法并輸出所得路徑，否則按順序更換人工魚執行步驟3。

四、仿真實驗

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

圖6 30＊30地圖路徑規劃結果

在50*50地圖環境中的試驗結果如圖7所示。在30*30、50*50和100*100地圖環境中均對兩種算法進行20次隨機試驗。統計三種地圖環境中基本算法和混合算法的路徑信息，包括最長路徑、最短路徑、最大折點數、最小折點數、平均路徑長度和平均折點數，得到三種地圖環境的數據如表1-3所示。

圖7 50＊50地圖路徑規劃結果

表1 30＊30柵格地圖仿真結果

表2 50＊50柵格地圖仿真結果

表3 100＊100柵格地圖仿真結果

對比不同地圖環境中的試驗結果可見，混合算法規劃出的路徑明顯優于基本人工魚群算法，前者路徑更短且折點數量更少。對于機器人而言，路徑更短表示可以減少能量耗費、節約時間成本，折點數更少則表示可以減少機器人設備的磨損和消耗，延長使用壽命。

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

考慮到仿真實驗的隨機性因素，平均路徑長度和平均折點數更能代表算法的性能。根據表1-3，利用對應的優化率數據制成折線圖，如圖8所示。

圖8 混合算法對路徑的優化程度

從圖8可以看出，在不同地圖中，相對于基本算法，利用混合算法規劃出的路徑平均路徑長度和平均折點數都有明顯改善，并且隨著地圖規模的增大，混合算法的優勢也隨之擴大。

五、結語

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

仿真實驗的結果表明，在相同地圖環境下混合算法規劃出的路徑更短，折點數更少，且隨著地圖的增大，優化效果逐漸提高。可以預見，在更大規模的地圖環境中，混合算法將更具優勢。