基于改進蝙蝠算法的移動機器人路徑規劃方法研究

倪昌浩，鄒 海

（安徽大學 計算機科學與技術學院，合肥 230601）

0 引言

路徑規劃是移動機器人導航的重要步驟之一，其目的是尋找出一條滿足評價標準的無碰撞路徑。當前的路徑規劃方法主要是運用智能優化算法尋找最優路徑，如遺傳算法[1]、蟻群算法[2]、粒子群算法[3]等，這些算法計算量小，結構簡單，但依然存在收斂速度慢、搜索路徑時間長等問題。

針對上述問題，學者們也提出了相應的改進策略。文獻[4]對粒子群算法慣性權重因子和加速因子進行修改，同時融合雞群算法對停滯粒子進行擾動，提高路徑規劃的收斂精度和穩定性。文獻[5]將蟻群算法和人工勢場法兩種方法進行融合，提出一種結合人工勢場和蟻群算法的移動機器人路徑規劃，提高了算法全局搜索能力，加快了收斂速度。文獻[6]通過引入萊維飛行，克服粒子群算法的早熟問題，增加了種群多樣性，并將改進粒子群算法成功應用于焊接機器人的路徑規劃問題中。

蝙蝠算法[7]是一種新型的智能優化算法，已經在很多領域得到應用[8,9]。本文為了更好解決移動機器人路徑規劃問題，提出一種結合黃金正弦和蝙蝠算法的路徑規劃算法（Golden-Sine Bat Algorithm，GSBA），提升了算法的收斂速度和尋優能力，具有較強的魯棒性。

1 環境建模

本文研究的是靜態環境下移動機器人的路徑規劃問題，為了讓機器人能夠識別周圍環境，采用導航點模型[10]構建環境模型，如圖1所示，圖中黑色部分為障礙物，白色部分為可行區域，這種方法可以讓移動機器人更好的規避障礙物。障礙物的數學表達式為：

圖1 環境建模

其中：（a，b）為障礙物圓心坐標，R為圓的半徑。

其中：R（k）為障礙物半徑，l（k）為避障約束懲罰函數，D為問題維度，K為障礙物個數，c為安全因子，這里設置c=100。

2 蝙蝠算法

蝙蝠算法是通過研究蝙蝠的一些超聲波特征得出的，每個蝙蝠都代表著解空間中的一個可行解，根據適應度函數可以求得每個個體的適應度，記錄當前適應度最優蝙蝠，并使用更新公式對個體速度和位置進行調整，同時對最優蝙蝠位置進行局部搜索，通過不斷迭代進化，最終收斂至最優解。算法中每只蝙蝠的聲波頻率fi、速度以及位置更新公式如下：

其中：fi為蝙蝠發出的脈沖頻率，頻率的最大最小值分別為fmax和fmin，β是[0，1]之間的均勻分布隨機數，和分別表示蝙蝠個體i在第t代時的位置和飛行速度，x*代表全局最優位置。

當蝙蝠滿足局部搜索的條件時，需對最優個體附近進行隨機游走，位置更新公式為：

其中：xold為當前最優個體位置，ε為[-1，1]之間的均勻分布隨機數，At為蝙蝠在第t代的平均響度。

在上述位置更新過程中，蝙蝠發現獵物時會減小響度，同時增大脈沖頻率，以便更加準確掌握獵物的位置，其更新公式為：

文獻[1-2]在處理旋轉車輪對輪軌力的響應時，用輪軌力的旋轉來代替車輪的旋轉。換句話說，作者只是計算了相對地面不旋轉的車輪在一個沿車輪滾動圓移動的荷載作用下的響應。由于車輪不旋轉，因此車輪的響應可以用車輪的振動模態來疊加，而車輪的振動模態由普通的有限元程序計算出來。這種處理方法考慮了荷載的移動效應，但完全排除了車輪旋轉時的離心效應和陀螺效應。

3 融合黃金正弦的蝙蝠算法

3.1 黃金正弦算法

黃金正弦算法（Golden Sine Algorithm，Golden-SA）于2017年提出的新型智能算法[12]，該算法迭代尋優時，依靠正弦函數和單位圓的關系對尋優區域全面搜索，同時引入黃金分割數控制遍歷空間，可快速引導個體趨近于最優值，具有收斂速度快、易實現的優點。

Golden-SA算法中個體位置更新公式可表示為：

3.2 種群平均位置

基本蝙蝠算法單純依靠種群最優個體的引導尋優，如果全局最優值離種群最優值較遠，其他蝙蝠個體會受其影響，最終導致算法過早收斂或早熟。本文引入種群平均位置對部分個體進行引導，大大降低算法陷入局部最優的可能性，即速度更新公式為：

其中：mt-1為種群在第t-1代的種群平均位置。

3.3 分階段局部搜索

基本蝙蝠算法中局部搜索階段是執行全維搜索策略，這種搜索方式有很強的局部搜索能力，但沒有考慮到單個維度值對適應度的影響。單維搜索策略每次只選擇一個維度進行更新，可以盡可能廣泛地探索，但是搜索效率較低。

針對全維操作的不足，本文使用單維和全維互補的方式對最優蝙蝠進行搜索，即在前迭代中執行單維更新策略，后迭代中執行全維搜索，如式(15)所示：

其中：T為總迭代次數，d為[1，D]間的隨機整數。

3.4 刪除操作

為了減少路徑的冗余節點本文還增加了刪除操作，如圖2所示。

圖2 刪除操作

圖2(a)中，機器人的路徑為1→2→3，連接路徑節點1和3，若1→3為無碰撞的安全路徑，可刪除路徑節點2。

從起始節點開始依次對后面的路徑節點進行連接，如果存在無碰撞路徑，則將中間節點刪除，如果不存在則對下一個節點依次搜索，直到到達終點，操作結束后重新計算路徑的適應度。這種方法有效減少了路徑的冗余度，也會讓路徑在平滑性上有較好的表現。

3.5 融合黃金正弦的蝙蝠算法

針對蝙蝠算法易陷入局部最優、多樣性差等問題，本文提出了融合黃金正弦的蝙蝠算法（Golden-Sine Bat Algorithm，GSBA）。該算法按照不同的適應度把蝙蝠分為兩個子種群，對于適應度較優的精英蝙蝠使用黃金正弦更新位置，使個體可以充分吸收最優個體的信息，達到快速收斂的目的，同時使用種群平均位置對另外的蝙蝠個體引導，以保證種群的多樣性，防止搜索路徑陷入局部最優。這里黃金正弦的位置更新方式可以用下式表示：

其中：x*為全局最優位置。

在蝙蝠算法局部搜索階段，分階段使用單維和全維操作對最優蝙蝠局部區域進行搜索，實現單維和全維操作優勢互補。最后刪除最優解的冗余節點，使路徑更為簡潔。

圖3為算法流程圖，移動機器人路徑規劃步驟如下：

圖3 算法流程圖

1）對工作環境進行建模，參數初始化，設置機器人起始點S和目的點E，根據環境確定路徑數量N、問題維度D、最大迭代次數T，同時初始化蝙蝠位置xi、速度vi、聲波響度、初始脈沖發射率；

2）計算每只蝙蝠所搜索路徑的適應度，記錄全局最優路徑x*，根據式(14)計算種群平均位置；

迭代次數t=t+1，計算位置更新后各路徑的適應度值，并更新全局最優路徑x*，若t達到最大迭代次數，對最優路徑進行刪除操作，輸出結果，否則跳轉到步驟3）。

4 仿真分析

為了驗證改進算法的性能，利用MATLAB軟件進行路徑規劃仿真實驗，對本文改進算法、原始蝙蝠算法、傳統粒子群算法和黃金正弦算法在同樣的環境下進行路徑規劃，共進行兩組實驗。實驗中，機器人起點為S（0，0），終點為E（100，100），具體參數選取如下：種群規模N=100，問題維度D=30，迭代次數T=100，最大脈沖頻率fmax=2.0，最小脈沖頻率fmin=0.0，初始脈沖發射率r0=0.5，響度最大值A0=0.9，響度、脈沖的調節參數α=γ=0.9，PSO算法中學習因子c1=c2=2.0。

圖4為各個算法在地圖一下規劃結果，從圖4(a)中可以看出四種算法都可以規劃出一條有效路徑，但是本文算法的路徑平滑度明顯優于其他算法。PSO、BA、Golden-SA和GSBA在地圖一中得到的路徑最短長度分別為158.89、150.98、165.76和143.75，結合圖4(b)可以看出，改進算法的規劃路徑明顯短于對比算法，且有很好的執行效率，改進算法迭代次數到達26次時路徑長度趨于穩定，同時在尋優后期依然可以使路徑質量有所提升，而BA和PSO算法分別在42和30次迭代后，規劃路徑長度開始平穩減小，Golden-SA算法在68次迭代后，結果才趨于穩定。

圖4 地圖一下路徑規劃結果

地圖二規劃結果如圖5所示，相對于地圖一，地圖二環境略微復雜，從圖5(a)、圖5(b)中可以看出GSBA算法依然可以尋找到一條較優路徑，而其他對比算法規劃的路徑存在較高冗余度，PSO、BA、Golden-SA和GSBA在地圖二中得到的路徑最短長度分別為164.09、160.98、211.19和146.64，GSBA算法的規劃路徑長度依然有明顯的優勢。綜上可得：本文改進算法提高了尋優收斂速度的同時，也使該算法規劃路徑的質量得到很大提高，驗證了改進算法在路徑規劃中的有效性。

圖5 地圖二下路徑規劃結果

5 結語

為了解決傳統算法在進行機器人路徑規劃時出現的搜索精度低、易陷入局部最優等問題，本文研究了蝙蝠算法在機器人路徑規劃中的應用，同時提出了一種改進的路徑規劃算法，通過引入黃金正弦算法和種群平均位置，優化個體位置更新方式，保持種群多樣性的同時提高了算法的收斂速度，利用單維和全維相結合的局部搜索，使最優位置的局部區域得到充分探索，再對節點進行刪除操作，進一步簡化了路徑。仿真結果表明：本文提出的算法具有較高的搜索效率和精度，能使移動機器人快速找到最優路徑，有效解決了此類路徑規劃問題。