朱金壇

(西安鐵路職業(yè)技術(shù)學(xué)院 電子信息學(xué)院，西安 710014)

0 引言

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

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

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

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

1 麻雀搜索算法

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

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

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

(1)

(2)

(3)

2 改進的麻雀搜索算法

2.1 三層神經(jīng)網(wǎng)絡(luò)建模

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

圖1 神經(jīng)網(wǎng)絡(luò)的環(huán)境建模

(4)

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

(5)

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

(6)

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

(7)

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

2.2 低差異序列初始化

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

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

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

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

(8)

2)已知bi與p，基本逆序函數(shù)如式(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之間的隨機數(shù)Kn，初始位置Xn如式(11)所示：

Xn=Xmin+Kn·(Xmax-Xmin)

(11)

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

圖2 二維位置分布對比圖

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

2.3 布朗運動步長策略

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

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

(12)

麻雀位置更新公式為：

(13)

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

2.4 clothoid曲線法的路徑平滑

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

(14)

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

(15)

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

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

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

(16)

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

(17)

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

2.5 改進算法描述

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

圖4 改進算法流程圖

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

2.6 算法復(fù)雜度分析

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

T=O(D+f(D))

(18)

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

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

O(D+f(D))

(19)

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

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

(20)

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

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

(21)

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

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

(22)

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

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

(23)

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

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

O(D+f(D))

(24)

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

3 仿真及分析

3.1 算法性能測試

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

表1 測試函數(shù)表

表2 算法尋優(yōu)結(jié)果排序

表3 Wilconxon秩和檢驗P值

3.2 地圖環(huán)境生成

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

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

圖5 運動方向

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

圖6 環(huán)境柵格圖

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

(25)

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

3.3 算法參數(shù)

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

表4 基本參數(shù)設(shè)置

3.4 仿真分析

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

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

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

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

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

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

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

表5 指標(biāo)對比

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

綜合來看，改進SSA算法在不同尺度環(huán)境解決機器人避障問題表現(xiàn)均很突出，其各項性能指標(biāo)均優(yōu)于CSSA算法和傳統(tǒng)SSA算法，可以以最快的速度收斂于最短平滑路徑。

4 結(jié)束語

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

1)通過三層神經(jīng)網(wǎng)絡(luò)對規(guī)劃環(huán)境進行柵格化建模；引入低差異序列中的Halton序列，使得初代麻雀種群分布廣泛且均勻，有很好的遍歷性，改善了初始麻雀種群隨機性過大，位置分布不均勻?qū)е氯〉镁植繕O值的問題；

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

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

4)經(jīng)6個標(biāo)準(zhǔn)函數(shù)驗證和Wilcoxon檢驗P值對比可知，改進后的算法相較于SSA和CSSA算法各項指標(biāo)得到明顯優(yōu)化，且具有和SSA同一水平的時間復(fù)雜度。

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