融合神經網絡及麻雀算法的機器人避障研究

朱金壇

(西安鐵路職業技術學院 電子信息學院，西安 710014)

0 引言

機器人自主運行的核心技術就是能避開障礙，具體來說是指機器人在無人干預的情況下，自主實現計劃中要求的各點間可行路徑的搜索與運行。規劃過程需要結合自身運行動力特性和環境約束，根據自身能耗和速度特征，考慮環境威脅等條件，自主規劃出最優路徑。其中，路徑的平滑度、行程長短、機器人能量消耗則是對該條路徑優劣的評估標準。從規劃環境尺度角度可分為全局避障和局部避障兩大類。局部路徑避障通過傳感器獲取環境數據，選擇一條當下節點至下一節點的子路徑，常用方法有滾動窗口法[1]、Dijkstra算法[2]、人工勢場法[3]等。全局避障指在掌握運動環境的前提下，利用算法自主生成優化路徑，如基于柵格圖對環境建模的方法[4]、利用可視圖法模擬實際環境的方式[5]以及基于open表的A*算法[6]等。

上述傳統算法雖然容易實現，但存在實時性差、適用范圍小、復雜環境計算量過大的問題。近年群智能算法的研究發展為解決機器人避障問題提供了更多解決方案。如：游達章[7]等人融合粒子群與灰狼算法，引入量子協同改善了算法在處理路徑規劃問題的精度；周晟[8]等人引入隨機分形自適應搜索策略優化了倉儲機器人多障礙多目標環境的的路徑規劃問題；潘紋[9]基于動態步長果蠅算法研究了自動導引車的路徑規劃問題。還有其他如天牛須算法[10]、鯨魚優化算法[11]等仿生群體算法也都開始用于路徑規劃與避障研究當中。2020年薛建凱等[12]首次提出麻雀搜索算法，算法主要以數學公式模擬麻雀群體覓食過程，具有速度快、精度高的特點。但由于收斂速度快也更容易提早收斂于局部極值點而無法跳出、初始種群分布不夠廣泛以及平衡能力差等缺點。該算法在CT圖檢測[13]、電池參數優化[14]、算法參數優化[15]和成像偏移預測[16]等實際問題。但SSA仍存在過度依賴初始種群，收斂前種群多樣性不足，易陷入局部極值且無法跳出等不足。

為解決以上問題，許多相關研究針對不同角度進行了優化改進。如G.Liu等人[17]引入混沌策略增加多樣性，使用權重和突變策略加快尋優。歐陽城添等人[18]融合折射學習，以此初始化種群，豐富多樣性，同時引入瘋狂算子使得算法尋優能力得以提升。這些算法雖也有一些算法上的提升，但并沒有從根本優化尋優機制，而是把結果交給不確定性較大的混沌隨機機制，也沒有考慮局部與全局的平衡，需要以時間復雜度為代價去優化算法性能。

因此針對算法提早收斂于局部、初始種群分布不夠廣泛和平衡能力差等問題，提出一種融合神經網絡的改進麻雀搜索算法。首先，通過神經網絡對規劃環境進行柵格化建模，其次引入低差異的Halton序列進行麻雀種群初始化，可使得初代種群分布廣泛且均勻，有很好的遍歷性；再次，采用布朗運動步長策略優化傳統SSA算法平衡能力差的缺陷，實現前期全局過程搜索范圍廣，中后期搜索精度高的平衡與切換，同時可通過布朗運動步長跳出局部收斂；最后，為了避免機器人實際運行過程出現急轉急停問題，引入clothoid曲線法進行最終的路徑平滑，避免了尖銳拐彎，減少實際運行時輪軸磨損和能耗。將綜合改進后的算法與原始算法進行時間復雜度對比，并使用6種函數對幾種常見算法進行橫向對比，最后將改進后算法與SSA算法和CSSA算法[19]進行不同尺度的環境規劃對比，綜合評價算法的機器人避障效果指標性能。

1 麻雀搜索算法

麻雀搜索算法(SSA)是一種啟發式算法，由麻雀搜索食物過程中的行為模式啟發而來，有算法穩定、尋優速度較快的特點。不僅優于傳統粒子群算法，對于新型的算法如灰狼算法、引力搜索算法也具有一定優勢。SSA真個種群共有3種角色，分別是發現者、尾隨者和警戒者，三者有不同的任務分工，發現者負責探索食物方位，并將食物位置共享給跟隨者，跟隨者的任務則是尾隨發現者，當收到發現者的位置更新后，則前往新位置準備覓食，同時，為了保證種群安全，種群中部分個體會在覓食前進行警戒，當收到危險信號時則會通知種群放棄覓食。

對于算法而言，發現者即執行的全局探測任務，跟隨者即對更新的位置信息進行局部尋優，當陷入局部極小值時，有警戒者負責釋放危險信號跳出局部，重新進行全局尋優。具有預警機制也是該算法優于其他算法的核心，使得SSA相較于其他算法更不易陷入局部最優解，更容易取得全局最優解。

SSA算法中的發現者、追隨者以及警戒者，分別按照各自規則進行位置更新，更新規則如式(1)～(3)所示：

(1)

(2)

(3)

2 改進的麻雀搜索算法

2.1 三層神經網絡建模

首先有三點假設前提：一是機器人運動范圍并非無限，而是在限定范圍內自主運行；二是以機器人最大尺度半徑膨脹障礙物，得到柵格環境；三是將機器人視為無尺度無邊界的質點處理。三層并聯神經網絡如圖1所示，數學表達如式(4)所示：

圖1 神經網絡的環境建模

(4)

其中：θim=(i=1，2，…，8)計算路徑如下：

(5)

式中，假設機器人的切線方向速度在[ti，ti+1]內不變。Vkx和Vky為速度分量。ti與ti+1之間的關系如下式：

(6)

式中，機器人在ti時速度為vrob，且在[ti，ti+1]速度不變。

(7)

式中，避碰檢測值Z為0時，代表可行路徑，取正值時則產生碰撞，路徑不可行。障礙物數目為PR，路徑等分點個數為Pe。此模型可同時計算出當前路徑與所有障礙物之間的碰撞結果。

2.2 低差異序列初始化

初代種群分布的廣泛性與均勻性直接影響算法收斂的速度。初代種群分布越廣，全局探索的速度越快，局部尋優的精度越高。標準SSA中初代麻雀種群位置過于隨機，均勻性過低、許多區域存在盲區，不夠遍歷。因此引入一種基于超均勻分布的均勻分布隨機數組Halton序列，以此代替隨機數進行種群初始化操作。

Halton序列主要有如下三步計算過程：

1)假定p≥2且為質數，對任意整數n，n∈(1，N)，可以p為基表達出如式(8)的形式：

bi∈{0，1，…，p-1}

(8)

2)已知bi與p，基本逆序函數如式(9)：

φp(n)=(0.b0b1…bm)p=b0p-1+

b1p-2+…+bmp-m-1

(9)

3)d維空間的Halton序列計算如式(10)：

H(n)=[φp1(n)，φp2(n)，…，φpd(n)]

(10)

在解空間上下限中生成一個取值范圍在0和1之間的隨機數Kn，初始位置Xn如式(11)所示：

Xn=Xmin+Kn·(Xmax-Xmin)

(11)

如圖2所示，可以清楚看出二維空間中Halton序列相對于偽隨機數法可將種群分布得更加均勻。

圖2 二維位置分布對比圖

由圖2可看出，Halton序列初始化種群相比偽隨機數序列得到分布更均勻、遍歷性更廣的初始化麻雀群體。

2.3 布朗運動步長策略

傳統SSA算法的迭代步長由一個符合均勻分布的隨機數作為步長因子，存在隨機性過大的問題，不能很好的平衡前期全局開發與中后期局部開發的過程切換。因此引入布朗運動步長策略，滿足前期全局過程搜索范圍足夠廣，中后期搜索精度足夠高的運行要求，當算法收斂于局部最優值，也可通過布朗運動策略跳出局部最優，脫離算法停滯。

布朗運動的步長服從均值為0方差為1的高斯分布，其本質是一個均勻可控的步長隨機過程，概率密度函數如式(12)所示：

(12)

麻雀位置更新公式為：

(13)

式(13)中，布朗運動步長以RB表示；P等于1/2；R為(0，1)間隨機數。

2.4 clothoid曲線法的路徑平滑

clothoid曲線廣泛運用于車輛行駛軌跡設計，路徑規劃等方向，是一種曲率半徑隨弧長線性變化的曲線，可以在直線段與曲線段平滑過渡。clothoid曲線的數學表達如式(14)所示：

(14)

式中，(x0，y0)為起點，θ0為切線角初始值，k為曲率，下標0代表初始值，c為曲率銳度參數，s為弧長。其中曲率k和切線角θ的計算如式(15)所示：

(15)

假設算法中關鍵點坐標為P(xi，yi)(i=1，2，…)上的離散點，那么對各點曲線擬合的過程，即保證曲率連續，求解k個離散點的各曲線段。圖3為一組離散點經擬合后的曲線段。

圖3 若干離散點擬合成clothoid曲線段

對于任意的第l段曲線，其端點坐標滿足如式(16)條件：

(16)

式中，第l段弧長為sl，(x1，y1)點的切線角為θ0l，曲率為k0l。為保證各點曲率連續且平滑，各參數滿足如式(17)的要求：

(17)

式中，前后兩段曲線交點處切線角、曲率均前后相等。即第l+1段曲線起點切線角等于第l段曲線的終點切線角，第l+1段曲線起點曲率等于第l段曲線的終點曲率。

2.5 改進算法描述

改進后的算法流程圖大致可分為初始化階段、網絡建模階段、判斷階段和位置更新階段，具體如圖4所示。

圖4 改進算法流程圖

首先通過式(8)～(11)以三層神經網絡對規劃環境進行柵格化建模，生成膨脹后的柵格圖，再對各參數初始化；用公式(4)～(6)對種群進行低差異序列初始化，形成分布均勻的種群；分別以式(1)、(3)、(7)更新尾隨麻雀、警戒麻雀和發現者的位置，若果算法陷入局部最優則以布朗運動步長通過式(13)跳出局部最優，若存在個體位置超過解空間上下界，也通過式(13)進行位置初始化；最后當滿足設定迭代次數時，結束算法，再對路徑進行平滑，同時輸出平滑前后的路徑，得到對應收斂曲線。

2.6 算法復雜度分析

時間復雜度反映了算法面對復雜問題的求解能力。若在D維解空間存在規模為N的初代種群，求解該問題需要消耗f(D)的時間。則時間復雜度可表示為：

T=O(D+f(D))

(18)

在一系列的改進后，初始化參數用時記為η0，各隨機因子生成時間記為η1，任意一維種群產生耗時為η2，越界重置位置時間記為η3，此時的時間復雜度可表示為如下公式：

T1=O(η0+Nf(D)+D(η1+η2+η3))=

O(D+f(D))

(19)

種群存在不同類型個體。發現者有r1N個，r1即發現者在種群所有個體中的占比，任意一維位置更新耗時η4，隨機因子生成需消耗時長η5，則發現者執行階段時間復雜度可表示為：

T2=O(r1N(η4+η5+η5)D)=O(D)

(20)

追隨者有r2N，同樣的r2為其在個體總量的占比，任意一維位置更新耗時η6，隨機因子消耗時長η7，則追隨者執行階段時間復雜度可表示為：

T3=O(r2N(η6+η7)D)=O(D)

(21)

除去發現者與追隨者，剩余的均為警戒者，數量則為(1-r1-r2)N，任一維位置更新耗時η8，隨機因子消耗時長為η9，則警戒者執行階段時間復雜度可表示為：

T4=O((1-r1-r2)N(η8+η9+η9)D)=O(D)

(22)

在布朗運動階段，按式(13)更新麻雀最優個體所需的時間為η10，生成隨機步長R所需的時間分別為η11，則此階段的時間復雜度為：

T5=O(N(η10+η11+η12)D)=O(D)

(23)

最大迭代次數為itermax，改進算法的時間復雜度為：

T′=T1+itermax(T2+T3+T4+T5)=

O(D+f(D))

(24)

通過對比可知，算法改進前后的時間復雜度在同一水平尺度，優化改進得到的性能優化沒有導致時間復雜度的額外增加。

3 仿真及分析

3.1 算法性能測試

選取2個單峰，3個復雜多峰，1個定維函數來測試算法尋優性能，具體函數如表1所示。同時將標準SSA，GWO和粒子群算法也加入一起作為橫向對比，將文獻[20]中的ISSA與文獻[21]中的CSSA進行縱向對比，以此突出本文改進算法的新穎性與優越性。對比算法種群數量統一為100，迭代次數為500，粒子群算法中的獨有參數c1=c2=2，w=0.728。統計各算法的平均值指標，并將各算法最終指標進行排序，根據排序先后衡量算法的尋優能力的強弱。表2中可以發現，改進算法對各函數均表現出較強的尋優能力，特別是在F3～F6中，改進算法的尋優效果顯著。為避免均值指標的片面性，引入Wilcoxon秩檢驗，在5%的顯著水平下進行試驗，當P≤0.05時，則存在顯著性差異。反之當P>0.05時，則表示差異不顯著，用N/A表示，具體結果如表1所示。由表1中看出，改進算法與其他各算法存在顯著差異，改進算法更具有快速處理復雜問題的優勢。

表1 測試函數表

表2 算法尋優結果排序

表3 Wilconxon秩和檢驗P值

3.2 地圖環境生成

用本文改進算法與傳統麻雀算法、文獻[19]中的CSSA算法作仿真結果對比。仿真計算機配置采用intel i7-11800H型號的CPU，GeForce RTX 3070顯卡，32 GB運行內存。

本文以膨脹法將環境進行柵格化建立環境模型。每個柵格代表一個節點，每次可移動一個單元格，因此有8個移動方向，如圖5所示。

圖5 運動方向

通過建立兩種圖5所示的不同柵格環境，驗證算法在不同尺度環境下的移動機器人的實際規劃效果。柵格地圖中，黑色部分即障礙，白色部分為可規劃區域。坐標(0.5，0.5)為規劃起點，坐標(19.5，19.5)和(39.5，39.5)為規劃終點，在圖6以灰色柵格表示，在仿真過程中黑色用1表示，白色和灰色用0表示。

圖6 環境柵格圖

柵格圖中原點位于左下角，終點在右上角第j行k列，代號為G的柵格中心坐標為：

(25)

式中，橫、縱坐標即x和y，mod為取余運算，int為求整公式。

3.3 算法參數

通過Matlab軟件得到20*20與40*40柵格圖，通過比較測試SSA算法、CSSA算法、本文改進算法在柵格地圖上規劃出的最短路徑來對比改進算法的優越性。其主要參數設置如表4所示。

表4 基本參數設置

3.4 仿真分析

在環境大小為20×20的柵格地圖中對3種算法進行仿真，得到的最優路徑對比和收斂迭代曲線對比如圖7所示。

圖7 20×20地圖仿真路徑與收斂曲線對比圖

圖7中，左圖為改進算法、原始算法同對比算法規劃出的路徑，改進算法因為引入了平滑改進，所以相對于其他兩種算法沒有尖銳轉彎點，而原始算法則有7個尖銳轉彎點，對比算法也有相應優化，只有5個尖銳轉彎點。右圖為3種算法的收斂曲線，原始算法迭代60次后趨于收斂，對比算法迭代52次后收斂穩定，改進算法最優，46代即收斂于最優路徑。

在環境大小為40×40的柵格地圖中對3種算法進行仿真，得到的最優路徑對比和收斂迭代曲線對比如圖8所示。

圖8 40×40地圖仿真路徑與收斂曲線對比圖

圖8中，左圖為改進算法、原始算法同對比算法規劃出的路徑，改進算法因為引入了平滑改進，所以相對于其他兩種算法沒有尖銳轉彎點，由于地圖尺度增加，環境障礙更加復雜，原始算法有8個尖銳轉彎點，對比算法只有7個尖銳轉彎點。右圖為3種算法的收斂曲線，原始算法迭代175次后趨于收斂，對比算法迭代158次后收斂穩定，改進算法最優，139代即收斂于最優路徑。

在20×20地圖和40×40地圖中，對比傳統SSA、改進SSA和CSSA三種算法規劃出的路徑，傳統SSA算法和CSSA算法由于沒有路徑平滑過程，均有較多的尖銳拐點，且收斂速度相對改進SSA算法更慢，其中傳統SSA算法路徑相對較長，加大了機器人不必要的能量消耗。改進SSA算法在路徑長度上最短，收斂速度最快，且無尖銳拐點。具體指標對比如表5所示。

表5 指標對比

結果顯示，在20×20地圖環境下，改進SSA相對傳統SSA算法最短路徑縮短了6.07 m，降低了17.66%，收斂迭代次數減少14次約23.33%；改進SSA相對CSSA算法最短路徑縮短了2.36 m，降低了7.69%，收斂迭代次數減少6次約11.54%。在40×40地圖環境下，改進SSA相對傳統SSA算法最短路徑縮短了10.18 m，降低了15.43%，收斂迭代次數減少36次約20.57%；改進SSA相對CSSA算法最短路徑縮短了4.03 m，降低了6.74%，收斂迭代次數減少19次約12.03%。

綜合來看，改進SSA算法在不同尺度環境解決機器人避障問題表現均很突出，其各項性能指標均優于CSSA算法和傳統SSA算法，可以以最快的速度收斂于最短平滑路徑。

4 結束語

針對傳統SSA算法易收斂在局部極值，平衡能力差、精度相對較低的缺陷，通過提出一種融合神經網絡的改進麻雀搜索算法得出以下結論。

1)通過三層神經網絡對規劃環境進行柵格化建模；引入低差異序列中的Halton序列，使得初代麻雀種群分布廣泛且均勻，有很好的遍歷性，改善了初始麻雀種群隨機性過大，位置分布不均勻導致取得局部極值的問題；

2)采用布朗運動步長策略，實現前期全局過程搜索范圍廣，中后期搜索精度高的平衡與切換，當算法收斂于局部最優值，也可通過布朗運動策略跳出局部最優，更快脫離算法停滯；

3)引入clothoid曲線法進行最終的路徑平滑，避免了尖銳拐彎，運行時急轉急停，減少了機器人運行時機械磨損和降低了能耗。

4)經6個標準函數驗證和Wilcoxon檢驗P值對比可知，改進后的算法相較于SSA和CSSA算法各項指標得到明顯優化，且具有和SSA同一水平的時間復雜度。

仿真結果進一步顯示，改進后的SSA算法在求解機器人避障問題時，不同地圖環境的避障結果均好于傳統SSA算法和CSSA算法，改進算法收斂速度快，規劃路徑短，拐點少且平滑，更滿足機器人實際工作的運行需求。