基于改進烏燕鷗算法的移動機器人路徑規(guī)劃

李月英

(鄭州科技學(xué)院電子與電氣工程學(xué)院，河南鄭州 450064)

0 前言

路徑規(guī)劃是移動機器人研究的關(guān)鍵問題之一，常簡化為在復(fù)雜的地圖環(huán)境中，復(fù)雜約束條件下獲取最優(yōu)路徑規(guī)劃線路的優(yōu)化問題。為更好地求解這類問題，傳統(tǒng)路徑規(guī)劃方法可以實現(xiàn)移動機器人的最優(yōu)路徑尋優(yōu)，如柵格法、人工勢場、連接圖法等[1-2]。但這些方法的求解效率較低，精度不足。為克服傳統(tǒng)路徑規(guī)劃方法存在的缺點，元啟發(fā)式智能算法引入隨機算子，具有快速、收斂精度高、易實現(xiàn)等優(yōu)點，被廣泛地應(yīng)用于求解各類復(fù)雜的移動機器人路徑規(guī)劃問題，如傳統(tǒng)的遺傳算法(Genetic Algorithm，GA)[3]，粒子群(Particle Swarm Optimization，PSO)算法[4]，人工蜂群(Artificial Bee Colony，ABC)算法[5]等。雖然傳統(tǒng)的元啟發(fā)式算法可以有效地解決移動機器人路徑規(guī)劃，但是仍存在易陷入局部最優(yōu)的問題。為此，研究學(xué)者著重于提高元啟發(fā)式算法的尋優(yōu)性能，采用多種改進策略提出眾多算法如：改進粒子群優(yōu)化算法[6], 改進灰狼優(yōu)化算法[7]，改進蟻群算法[8-10]，動態(tài)分組蟻群算法[11]，煙花混合蟻群算法[12]，粒子群-蟻群算法[13]，量子風(fēng)驅(qū)動優(yōu)化算法[14]，改進ACO[15]等。相比傳統(tǒng)元啟發(fā)式算法，這些改進算法可提升算法的全局尋優(yōu)精度和效率，應(yīng)用于求解移動機器人路徑規(guī)劃問題時，可使機器人有效地躲避障礙物，以較快的速度獲取較短的路徑規(guī)劃長度。

烏燕鷗算法(Sooty Tern Optimization Algorithm， STOA)是一種模擬烏燕鷗群體生活行為(遷徙和撲食)的高效智能算法，與其他元啟發(fā)式算法相比，尋優(yōu)性能較好。針對高維復(fù)雜的優(yōu)化問題，和其他算法一樣仍存在一定程度上的停滯現(xiàn)象，造成算法尋優(yōu)精度和效率低等[16]。

鑒于此，為提高STOA算法的性能，提出一種改進的烏燕鷗算法(Improved Sooty Tern Optimization Algorithm，ISTOA)，并應(yīng)用于求解復(fù)雜環(huán)境下移動機器人的路徑規(guī)劃問題。算法的具體改進方法為：在STOA算法初始化階段嵌入Circle混沌映射，保證種群的初始質(zhì)量；在遷徙階段混合正余弦非碰撞控制因子和自適應(yīng)Lévy飛行策略，協(xié)調(diào)算法全局搜索與局部探索；提出一種新穎的旋轉(zhuǎn)式翻筋斗策略并嵌入到撲食階段，提升算法的局部搜索能力。所提出算法的有效性通過不同的移動路徑規(guī)劃問題得以評估。

1 STOA算法

STOA算法是一種通過模擬烏燕鷗群體生活行為的智能算法，通過一些定義它被抽象為可循環(huán)迭代計算的數(shù)學(xué)模型。具體定義如下[15]：

定義1 遷徙位置更新。主要包含3種行為，避免碰撞見公式(1)和(2)，向最優(yōu)方向遷徙見公式(3)和(4)，靠近最優(yōu)位置見公式(5)。

C(k)=φ×P(k)

(1)

φ=2-[k×(2/kmax)]

(2)

式中：C(k)為烏燕鷗當(dāng)前未發(fā)生碰撞的遷移位置；P(k)為烏燕鷗個體當(dāng)前位置；φ為避免發(fā)生碰撞因子；k為當(dāng)前迭代次數(shù)；kmax為最大迭代次數(shù)。

M(k)=λ×[Pb(k)-P(k)]

(3)

λ=0.5×β

(4)

其中：M(k)為烏燕鷗當(dāng)前遷移位置;Pb(k)為當(dāng)前烏燕鷗最優(yōu)解位置；λ為全局可調(diào)因子；β為[0,1]范圍內(nèi)的隨機數(shù)。

D(k)=C(k)+M(k)

(5)

式中：D為烏燕鷗最終遷移位置。

定義2 撲食位置更新。在遷移過程中，烏燕鷗采用螺旋式撲食方法[見公式(6)]，在局部范圍內(nèi)進行獵物的搜索。因此，烏燕鷗的位置更新見式(7):

(6)

式中：R為螺旋線半徑；θ為[0,2π]范圍內(nèi)的隨意u和v表示螺旋形狀的超參數(shù)。

P(k)=[D×(x′×y′×z′)]×Pb(k)

(7)

2 改進烏燕鷗算法(ISTOA)

2.1 改進STOA算法(ISTOA)簡介

(1)種群混沌初始化

對STOA算法的種群初始化方式進行混沌化，可以增強種群的初始均勻分布，提高算法的初始收斂速度和精度，因此采用Circle映射對其種群進行初始化，見式(8)

(8)

(2)正弦控制非碰撞因子

由圖1可知：在STOA中，參數(shù)φ受迭代次數(shù)的影響逐漸線性遞減。線性下降方式制約著算法的全局搜索和局部搜索，影響算法尋優(yōu)性能。

圖1 非碰撞因子對比Fig.1 Comparison of non-collision factors

當(dāng)φ越大全局搜索能力越強，反之，局部搜索能力越強。為增強STOA算法的局部搜索能力，將φ修改為正弦控制方式的非線性遞減因子，見(9)。由圖1可知：采用正弦控制方式，可增強非碰撞因子φ的自我動態(tài)調(diào)整能力，在迭代前期φ變化較快，迭代后期φ變化較慢。這樣可實現(xiàn)STOA算法的迭代前期快速全局搜索，迭代后期最大化地進行局部搜索。

(9)

(3)旋轉(zhuǎn)式翻筋斗撲食策略

由于烏燕鷗算法無限逼近全局最優(yōu)解時，難以跳出最優(yōu)解的鄰域，導(dǎo)致陷入局部最優(yōu)。標(biāo)準(zhǔn)的翻筋斗策略可提高算法跳出局部的能力[17]。烏燕鷗翻斗撲食如圖2所示,在不同區(qū)域(即A、B、C等)以獵物為空翻支撐點，每次撲食過程中，當(dāng)前烏燕鷗會更新至獵物的對稱位置處。這種撲食的數(shù)學(xué)模型可式(10)：

(10)

圖2 標(biāo)準(zhǔn)的翻筋斗撲食策略Fig.2 A standard somersault strategy

由圖2可知，第i只烏燕鷗只能以固定的空翻步長F分別隨機空翻在對應(yīng)的有限搜索區(qū)域A、B、C內(nèi)，但有限的區(qū)域會使烏燕鷗種群的多樣性減弱，不利于算法逃離局部最優(yōu)。為此，引入空翻旋轉(zhuǎn)角度β(0≤β≤2π)(見圖3)，顯而易見，隨著空翻旋轉(zhuǎn)角度β不斷地變化，可以有效地豐富烏燕鷗個體空翻空間，保持迭代后期種群的多樣性，進一步提高算法的局部尋優(yōu)能力。采用這種旋轉(zhuǎn)式翻斗撲食策略見圖4，一方面可以增加空翻的空間，擴大種群搜索空間，另一方面也可以保持種群的分布均勻性和多樣性，提升算法的尋優(yōu)性能。因此，對公式(10)中空翻旋轉(zhuǎn)角度β，改進為旋轉(zhuǎn)式翻筋斗撲食位置更新方式見式(11)，即對STOA算法的烏燕鷗個體的撲食位置更新方式修改為旋轉(zhuǎn)式翻筋斗撲食位置模式見式(11)。

圖3 旋轉(zhuǎn)式翻斗單一撲食行為Fig.3 Single feeding behavior by rotary somersault

圖4 旋轉(zhuǎn)式翻斗群體撲食行為Fig.4 Group feeding behavior by rotary somersault

(11)

(4)自適應(yīng)Lévy飛行策略

為增強STOA算法全局尋優(yōu)能力，引入自適應(yīng)因子w，見式(12)。在STOA遷徙位置中引入自適應(yīng)因子和Lévy飛行因子可以提高算法的種群多樣性和擴大探索空間，提高算法的收斂速度和收斂精度。Lévy飛行因子可由式(13)計算。因此，在STOA中，式(5)可修改為式(14)。

(12)

式中：wmax和wmin分別為初設(shè)的自適應(yīng)因子的最大和最小值。

Lévy(β)≈α-β

(13)

式中：α為隨機飛行搜索步長；β∈(1,3]。

(14)

同時，STOA算法搜索后期，烏燕鷗落入最優(yōu)位置附近，由于此時的種群多樣性較弱，無法保證烏燕鷗能夠無限逼近最優(yōu)解，所以，采用Lévy飛行因子對烏燕鷗最優(yōu)個體變異，見式(15)

(15)

2.2 基于ISTOA的移動機器人路徑規(guī)劃算法

綜合以上改進方法，文中提出的基于ISTOA移動機器人路徑規(guī)劃算法流程如圖5所示，步驟如下：

(1)初始化設(shè)置。搭建柵格地圖環(huán)境，設(shè)置機器人的起始與終止坐標(biāo)位置，設(shè)置ISTOA算法種群數(shù)量、最大迭代次數(shù)等；

(2)利用Circle映射對種群進行初始化即式(8)，并評估初始最佳路徑長度，確定初始最優(yōu)路徑信息；

(3)采用旋轉(zhuǎn)式翻斗進行撲食位置更新即式(11)和式(6)；

(4)采用自適應(yīng)Lévy飛行方式更新遷徙位置，即式(1)(3)(4)(9)(12)(13)；

(5)重新評估路徑適應(yīng)度值更新最佳路徑長度及路徑信息；

(6)用式(15)對其最優(yōu)路徑進行變異；

(7)判斷是否滿足最大迭代次數(shù)，若是，則輸出全局最佳路徑長度及最優(yōu)路徑信息，反之，返回步驟(3)繼續(xù)尋優(yōu)；

(8)算法尋優(yōu)結(jié)束，輸出最優(yōu)結(jié)果。

圖5 基于ISTOA的移動機器人路徑規(guī)劃算法

3 路徑規(guī)劃實驗仿真與分析

3.1 實驗參數(shù)與地圖環(huán)境設(shè)置

為了驗證所提ISTOA算法在路徑規(guī)劃上的有效性，采用柵格法構(gòu)建3種不同規(guī)格的地圖環(huán)境，如圖6—圖8所示。圖中黑色代表障礙物，白色代表可通行區(qū)域，并設(shè)置有始末點。為驗證ISTOA算法在移動機器人路徑規(guī)劃中的尋優(yōu)性能，選用STOA[16]、SOA[18]、SCA[19]和ISTOA算法進行對比分析，實驗結(jié)果評價指標(biāo)選取20次，各個算法獨立運行獲得最小路徑長度、平均路徑長度、成功率、路徑長度標(biāo)準(zhǔn)差和平均運行時間。各算法種群數(shù)量選擇為100，最大迭代次數(shù)為700。起始柵格為S=1,3種不同規(guī)格的路徑柵格G=200、1 600、2 500。

圖6 20 m×20 m柵格化地圖Fig.6 The 20 m×20 m rasterization map

圖7 40 m×40 m柵格化地圖Fig.7 The 40 m×40 m rasterization map

圖8 50 m×50 m柵格化地圖Fig.8 The 50 m×50 m rasterization map

3.2 實驗結(jié)果與分析

在20 m×20 m、40 m×40 m和50 m×50 m地圖環(huán)境下，4種算法的實驗統(tǒng)計結(jié)果見表1—表3，最優(yōu)路徑和迭代收斂曲線對比見圖9—圖11。

表1 20 m×20 m地圖路徑規(guī)劃統(tǒng)計結(jié)果

表2 40 m×40 m地圖路徑規(guī)劃統(tǒng)計結(jié)果

表3 50 m×50 m地圖路徑規(guī)劃統(tǒng)計結(jié)果

圖9 20 m×20 m地圖最優(yōu)路徑(a)與迭代收斂曲線(b)

圖10 40 m×40 m地圖最優(yōu)路徑(a)與迭代收斂曲線(b)

圖11 50 m×50 m地圖最優(yōu)路徑(a)與迭代收斂曲線(b)

由表1—表3統(tǒng)計結(jié)果可知：對于20 m×20 m、40 m×40 m和50 m×50 m地圖，ISTOA算法可分別獲得最短路徑長度為30.500、60.036、73.439 m。與SOA、STOA和SCA算法相比，ISTOA的最短路徑長度均短于其他算法，除了40 m×40 m地圖環(huán)境，ISTOA算法長于STOA算法但短于SOA和SCA算法。對于平均路徑長度和路徑長度標(biāo)準(zhǔn)差，ISTOA算法均優(yōu)于其他算法。

從成功率來說，對于所有的地圖環(huán)境，ISTOA算法成功率達到了100%，高于或者等于其他算法，全部能夠成功實現(xiàn)移動機器人路徑最優(yōu)規(guī)劃。然而，其他算法成功率不穩(wěn)定。從平均耗時來看，對于所有的地圖環(huán)境，ISTOA算法耗時最長，SCA算法耗時較短，SOA算法和STOA算法耗時居中。隨著地圖環(huán)境復(fù)雜性的增加，所有算法的耗時均增加。ISTOA算法的耗時增加是由于采用多種改進策略，增強了算法種群的多樣性，提高了尋優(yōu)精度。

由圖9—圖10可知：對于不同規(guī)格的地圖環(huán)境，從最優(yōu)路徑來看，ISTOA算法路徑長度短，路徑中的轉(zhuǎn)折次數(shù)較少，路徑平滑度較好，總能夠獲得較為合理的移動機器人移動路徑；從迭代收斂曲線來看，ISTOA算法迭代收斂曲線均位于其他算法下方，可以快速地獲得最優(yōu)路徑，收斂速度和全局最優(yōu)解均優(yōu)于其他算法?？擅黠@地看出，STOA算法容易在局部停滯，不易跳出局部極值，且全局收斂精度低。與STOA算法相比，ISTOA算法改善了STOA算法易陷入局部最優(yōu)的現(xiàn)象且全局收斂精度更高。在迭代初期，ISTOA算法就能夠快速下降，這是由于采用了Circle混沌映射提高了迭代初期的收斂速度。在迭代中后期，ISTOA算法可以快速地跳出局部最優(yōu)，這是旋轉(zhuǎn)式翻筋斗搜索策略的獨特優(yōu)勢所在，同時采用自適應(yīng)正余弦因子和Lévy飛行策略平衡了算法全局與局部之間搜索能力。

綜上所述，在復(fù)雜環(huán)境中，ISTOA算法可以快速地實現(xiàn)移動機器人最優(yōu)路徑規(guī)劃，且擁有較好的尋優(yōu)能力。

4 結(jié)論

(1)為提高移動機器人路徑尋優(yōu)效率與精度，利用Circle映射提高算法初始種群質(zhì)量，自適應(yīng)正余弦非碰撞控制因子和Lévy飛行協(xié)同算法全局與局部搜索，旋轉(zhuǎn)式翻筋斗避免算法早熟，提出了改進烏燕鷗算法(ISTOA)。

(2)提出了一種新穎的旋轉(zhuǎn)式翻筋斗搜索策略，避免了算法在處理移動機器人路徑規(guī)劃時易陷入局部極值。

(3)路徑規(guī)劃仿真實驗表明：與SOA、STOA和SCA算法相比，ISTOA算法能實時地躲避障礙物，可提供較優(yōu)的路徑規(guī)劃尋優(yōu)結(jié)果，并且耗時較短、成功率高、穩(wěn)定性和魯棒性更強。