倪昌浩，鄒 海

（安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601）

0 引言

路徑規(guī)劃是移動機(jī)器人導(dǎo)航的重要步驟之一，其目的是尋找出一條滿足評價(jià)標(biāo)準(zhǔn)的無碰撞路徑。當(dāng)前的路徑規(guī)劃方法主要是運(yùn)用智能優(yōu)化算法尋找最優(yōu)路徑，如遺傳算法[1]、蟻群算法[2]、粒子群算法[3]等，這些算法計(jì)算量小，結(jié)構(gòu)簡單，但依然存在收斂速度慢、搜索路徑時(shí)間長等問題。

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

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

1 環(huán)境建模

本文研究的是靜態(tài)環(huán)境下移動機(jī)器人的路徑規(guī)劃問題，為了讓機(jī)器人能夠識別周圍環(huán)境，采用導(dǎo)航點(diǎn)模型[10]構(gòu)建環(huán)境模型，如圖1所示，圖中黑色部分為障礙物，白色部分為可行區(qū)域，這種方法可以讓移動機(jī)器人更好的規(guī)避障礙物。障礙物的數(shù)學(xué)表達(dá)式為：

圖1 環(huán)境建模

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

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

2 蝙蝠算法

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

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

當(dāng)蝙蝠滿足局部搜索的條件時(shí)，需對最優(yōu)個(gè)體附近進(jìn)行隨機(jī)游走，位置更新公式為：

其中：xold為當(dāng)前最優(yōu)個(gè)體位置，ε為[-1，1]之間的均勻分布隨機(jī)數(shù)，At為蝙蝠在第t代的平均響度。

在上述位置更新過程中，蝙蝠發(fā)現(xiàn)獵物時(shí)會減小響度，同時(shí)增大脈沖頻率，以便更加準(zhǔn)確掌握獵物的位置，其更新公式為：

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

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

3.1 黃金正弦算法

黃金正弦算法（Golden Sine Algorithm，Golden-SA）于2017年提出的新型智能算法[12]，該算法迭代尋優(yōu)時(shí)，依靠正弦函數(shù)和單位圓的關(guān)系對尋優(yōu)區(qū)域全面搜索，同時(shí)引入黃金分割數(shù)控制遍歷空間，可快速引導(dǎo)個(gè)體趨近于最優(yōu)值，具有收斂速度快、易實(shí)現(xiàn)的優(yōu)點(diǎn)。

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

3.2 種群平均位置

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

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

3.3 分階段局部搜索

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

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

其中：T為總迭代次數(shù)，d為[1，D]間的隨機(jī)整數(shù)。

3.4 刪除操作

為了減少路徑的冗余節(jié)點(diǎn)本文還增加了刪除操作，如圖2所示。

圖2 刪除操作

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

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

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

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

其中：x*為全局最優(yōu)位置。

在蝙蝠算法局部搜索階段，分階段使用單維和全維操作對最優(yōu)蝙蝠局部區(qū)域進(jìn)行搜索，實(shí)現(xiàn)單維和全維操作優(yōu)勢互補(bǔ)。最后刪除最優(yōu)解的冗余節(jié)點(diǎn)，使路徑更為簡潔。

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

圖3 算法流程圖

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

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

迭代次數(shù)t=t+1，計(jì)算位置更新后各路徑的適應(yīng)度值，并更新全局最優(yōu)路徑x*，若t達(dá)到最大迭代次數(shù)，對最優(yōu)路徑進(jìn)行刪除操作，輸出結(jié)果，否則跳轉(zhuǎn)到步驟3）。

4 仿真分析

為了驗(yàn)證改進(jìn)算法的性能，利用MATLAB軟件進(jìn)行路徑規(guī)劃仿真實(shí)驗(yàn)，對本文改進(jìn)算法、原始蝙蝠算法、傳統(tǒng)粒子群算法和黃金正弦算法在同樣的環(huán)境下進(jìn)行路徑規(guī)劃，共進(jìn)行兩組實(shí)驗(yàn)。實(shí)驗(yàn)中，機(jī)器人起點(diǎn)為S（0，0），終點(diǎn)為E（100，100），具體參數(shù)選取如下：種群規(guī)模N=100，問題維度D=30，迭代次數(shù)T=100，最大脈沖頻率fmax=2.0，最小脈沖頻率fmin=0.0，初始脈沖發(fā)射率r0=0.5，響度最大值A(chǔ)0=0.9，響度、脈沖的調(diào)節(jié)參數(shù)α=γ=0.9，PSO算法中學(xué)習(xí)因子c1=c2=2.0。

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

圖4 地圖一下路徑規(guī)劃結(jié)果

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

圖5 地圖二下路徑規(guī)劃結(jié)果

5 結(jié)語

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