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

李月英

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

0 前言

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

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

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

1 STOA算法

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

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

C(k)=φ×P(k)

(1)

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

(2)

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

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

(3)

λ=0.5×β

(4)

其中：M(k)為烏燕鷗當前遷移位置;Pb(k)為當前烏燕鷗最優解位置；λ為全局可調因子；β為[0,1]范圍內的隨機數。

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

(5)

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

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

(6)

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

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

(7)

2 改進烏燕鷗算法(ISTOA)

2.1 改進STOA算法(ISTOA)簡介

(1)種群混沌初始化

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

(8)

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

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

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

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

(9)

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

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

(10)

圖2 標準的翻筋斗撲食策略Fig.2 A standard somersault strategy

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

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

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

(11)

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

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

(12)

式中：wmax和wmin分別為初設的自適應因子的最大和最小值。

Lévy(β)≈α-β

(13)

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

(14)

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

(15)

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

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

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

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

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

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

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

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

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

(8)算法尋優結束，輸出最優結果。

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

3 路徑規劃實驗仿真與分析

3.1 實驗參數與地圖環境設置

為了驗證所提ISTOA算法在路徑規劃上的有效性，采用柵格法構建3種不同規格的地圖環境，如圖6—圖8所示。圖中黑色代表障礙物，白色代表可通行區域，并設置有始末點。為驗證ISTOA算法在移動機器人路徑規劃中的尋優性能，選用STOA[16]、SOA[18]、SCA[19]和ISTOA算法進行對比分析，實驗結果評價指標選取20次，各個算法獨立運行獲得最小路徑長度、平均路徑長度、成功率、路徑長度標準差和平均運行時間。各算法種群數量選擇為100，最大迭代次數為700。起始柵格為S=1,3種不同規格的路徑柵格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 實驗結果與分析

在20 m×20 m、40 m×40 m和50 m×50 m地圖環境下，4種算法的實驗統計結果見表1—表3，最優路徑和迭代收斂曲線對比見圖9—圖11。

表1 20 m×20 m地圖路徑規劃統計結果

表2 40 m×40 m地圖路徑規劃統計結果

表3 50 m×50 m地圖路徑規劃統計結果

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

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

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

由表1—表3統計結果可知：對于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地圖環境，ISTOA算法長于STOA算法但短于SOA和SCA算法。對于平均路徑長度和路徑長度標準差，ISTOA算法均優于其他算法。

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

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

綜上所述，在復雜環境中，ISTOA算法可以快速地實現移動機器人最優路徑規劃，且擁有較好的尋優能力。

4 結論

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

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

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