摘要：為了尋找更優(yōu)的機器人移動路徑，將沙貓群優(yōu)化算法與三次樣條插值方法進行融合，對沙貓群優(yōu)化算法進行改進。在改進的沙貓群優(yōu)化算法中，利用混沌映射的均勻性初始化種群以提高種群多樣性；通過融合互利共生和萊維飛行策略減少局部最優(yōu)解的消極影響，提高算法的收斂速度和精度。通過兩種仿真實驗對比6種優(yōu)化算法的實驗數(shù)據(jù)，結(jié)果表明，改進的沙貓群優(yōu)化算法的最優(yōu)解、最差解和平均解都優(yōu)于對比算法，驗證了改進沙貓群優(yōu)化算法對于解決移動機器人路徑規(guī)劃問題的有效性和工程實用性。

關(guān)鍵詞：機器人路徑規(guī)劃；沙貓群優(yōu)化算法；三次樣條插值；混沌映射；互利共生；萊維飛行

中圖分類號：TP18

文獻標志碼：A 文章編號：1672-4348（2023）01-0072-06

Robot path planning based on improved sand cat swarm optimization algorithm

JIA Heming¹， LI Yongchao¹， YOU Jinhua¹， LI Zhengbang²， RAO Honghua¹， WEN Changsheng¹

（1. Department of Information Engineering，Sanming University， Sanming 365004， China;

2. School of Computer Science and Mathematics， Fujian University of Technology， Fuzhou 350118， China）

Abstract： In order to find a better robot moving path， the sand cat swarm optimization algorithm was combined with the cubic spline interpolation method to improve the sand cat swarm optimization algorithm. In the improved sand cat swarm optimization algorithm， the uniformity of chaotic mapping was used to initialize the population to improve the population diversity. Secondly， by integrating mutualism and introducing Levy flight strategy， the negative impact of local optimal solution was reduced and the convergence speed and accuracy of the algorithm were improved. In two simulation experiments， the experimental data of the six optimization algorithms were compared. Results show that the optimal solution， the worst solution and the average solution of the improved sand cat swarm optimization algorithm were all better than those of the comparison algorithm， which verifies the effectiveness and engineering practicability of the improved sand cat swarm optimization algorithm for solving the path planning problem of mobile robots.

Keywords： robot path planning; sand cat swarm optimization algorithm; cubic spline interpolation; chaotic mapping; mutual symbiosis; Levy flight

收稿日期：2022-12-06

基金項目：福建省自然科學(xué)基金面上項目（2021J011128）

第一作者簡介：賈鶴鳴（1983—），男，黑龍江哈爾濱人，教授，博士，研究方向：群體智能優(yōu)化算法及工程應(yīng)用。

路徑規(guī)劃是移動機器人研究的一大技術(shù)難題，優(yōu)秀的路徑規(guī)劃技術(shù)能夠減少移動機器人的成本、提高效率以及安全性能^[1]。國內(nèi)外就移動機器人的路徑規(guī)劃問題開展了諸多研究，提出了自由空間法^[2]、強化學(xué)習(xí)方法^[3]、深度學(xué)習(xí)方法^[4]和人工勢場法^[5]等方法。但是，當(dāng)空間里的障礙物數(shù)量過多時，自由空間法的復(fù)雜度也會過高；在計算復(fù)雜障礙空間時，強化學(xué)習(xí)方法無法在數(shù)據(jù)量較小的情況下進行高效的路徑規(guī)劃；人工勢場法會出現(xiàn)目標不可達的問題；障礙空間不完全可見或者不穩(wěn)定時，深度學(xué)習(xí)方法也不能很好地解決。群體智能算法在求解復(fù)雜空間時具有獨特的優(yōu)勢，如教與學(xué)優(yōu)化算法^[6]、蟻群優(yōu)化算法^[7]、人工蜂群優(yōu)化算法^[8]等。但是，未經(jīng)優(yōu)化改進的算法容易產(chǎn)生經(jīng)過障礙物的無效路徑，且容易陷入局部最優(yōu)等缺點。因此，尋找收斂速度更快、路線更好的改進群體智能算法是學(xué)者們共同的研究方向。

2022年Amir Seyyedabbasi提出一種模擬沙貓捕食的群體智能算法——沙貓群優(yōu)化算法^[11]（sand cat swarm optimization，SCSO）。SCSO作為最近提出的群體智能優(yōu)化算法，有著優(yōu)于傳統(tǒng)算法的優(yōu)化性能 ，但是容易被局部最優(yōu)點干擾，導(dǎo)致算法易陷入局部最優(yōu)，無法找到全局最優(yōu)解。當(dāng)遇到的障礙物較為復(fù)雜時，使用圓弧^[9]或直線^[10]進行分段式產(chǎn)生的移動路線折點較多，在平滑性和連續(xù)性上效果一般。而使用三次樣條插值擬合出的動態(tài)路徑更加平滑，可以保證機器人具有更好的應(yīng)急機動性能。

本研究將沙貓群優(yōu)化算法進行改進，并與三次樣條插值方法進行融合，提高算法的收斂速度和精度，更加有效解決機器人路徑規(guī)劃問題。

1 沙貓群智能優(yōu)化算法

沙貓群智能優(yōu)化算法的靈感來源于沙貓對于低頻噪聲的檢測能力，沙貓無論在地面上還是在地面下，都能憑借它獨特的能力來找到獵物。

1.1 搜索獵物

控制探索與開發(fā)階段過渡的最終參數(shù)和主要參數(shù)是R→，當(dāng)Rgt;1時，沙貓對進行獵物搜索。沙貓對獵物的搜索依賴于低頻噪聲的釋放，假設(shè)沙貓的靈敏度范圍r_G從0到2 kHz。s_M值的靈感來自沙貓的聽覺特征，假設(shè)其值為2。iter_c為當(dāng)前迭代，iter_max為最大迭代，r顯示了每只貓的敏感范圍。r用于勘探或開發(fā)階段的操作，rand（0，1）表示0到1的隨機數(shù)。

每只沙貓根據(jù)最佳候選位置（Pos_bc）和當(dāng)前位置（Pos_c）及其靈敏度范圍（r）更新自己的位置。因此，沙貓能夠找到其他可能的最佳獵物位置。

1.2 攻擊獵物

當(dāng)R≤1時，沙貓進行攻擊獵物。首先，利用最佳位置Pos_bc與當(dāng)前位置Pos_c來生成一個隨機位置Pos_rnd。假設(shè)沙貓的靈敏度范圍是一個圓，利用輪盤賭法給每只沙貓隨機選擇一個角度θ，最后通過公式（6）實現(xiàn)攻擊獵物。其中，隨機位置能夠保證沙貓向獵物靠近，隨機角度有助于算法跳出局部最優(yōu)。

2 改良的沙貓群智能優(yōu)化算法

沙貓群優(yōu)化算法在計算過程中也存在著探索和開發(fā)之間的矛盾。種群在初始化時候的分布情況決定了算法的收斂精度與速度。為了使沙貓種群在搜索空間均勻分布，本研究引入了混沌映射來提高種群初始化的分布多樣性，引入互利共生策略和萊維飛行策略，加強個體與最優(yōu)個體之間的信息交流，擴大開采的周密性，提高算法的尋優(yōu)精度和速度。

2.1 混沌映射初始化

混沌映射^[12]具有良好的隨機性、規(guī)律性和遍歷性，不但能使得種群具有良好的多樣性，也能使得算法在全局搜索能力、收斂速度、收斂精度上都有所提高。改進公式如下：

式中，a一般取0.4；Pos_id表示第i只沙貓的第d維的位置；ub和lb表示種群的搜索范圍；C_id表示由式（7）產(chǎn)生的混沌序列。

2.2 引入互利共生策略

沙貓群優(yōu)化算法在攻擊獵物時，會通過輪盤賭法隨機選擇角度來靠近獵物進行攻擊。但這樣的攻擊方式隨機性較大，也易于陷入局部最優(yōu)，互利共生策略^[12]通過加強個體與最優(yōu)個體的信息交流，可以消除沙貓攻擊獵物時的消極影響，提高沙貓的尋優(yōu)精度和收斂速度。改進公式如下：

式中，Pos_new為更新后的位置；Pos_bc為最優(yōu)個體的位置；Pos_rnd為隨機個體的位置；bf表示利益因子，隨機選擇1或2，表示可能部分受益或全部受益；R_MV表示最優(yōu)個體與隨機個體的信息交流。

2.3 引入萊維飛行策略

沙貓群優(yōu)化算法在搜索獵物和攻擊獵物時，都是通過隨機角度進行的，導(dǎo)致算法會遺漏部分較優(yōu)的解，降低收斂精度。為了增強搜索的周密性，消除局部最優(yōu)解的消極影響，本算法引入萊維飛行策略^[13]，既加強了算法的局部搜索能力，又能保證算法在全局搜索時具有良好的周密性。改進公式如下：

式中，Pos_new為更新后的個體位置；Pos_bc表示最優(yōu)個體的位置；Pos_Levy表示萊維飛行位置；l是（0，1）的隨機數(shù)；Pos_rnd表示隨機個體的位置；μ是服從μ～N（0，σ²_μ）的隨機數(shù)，其中Γ為伽馬函數(shù)，β為（0，2）的隨機數(shù)。

3 基于三次樣條插值的路徑規(guī)劃

采用三次樣條插值的方法可以保證機器人在面臨緊急情況時具有更好的動力學(xué)特性，優(yōu)越于用直線與圓弧擬合機器人路徑。

3.1 三次樣條插值

在區(qū)間[a，b]上取n+1個結(jié)點，并假設(shè)a=x₁lt;x₂lt;…lt;x_n=b，假如s（x）滿足：s（x）∈C²[a，b]；s（x_i）=f_i（i=1，2，…，n）；[x_i，x_i+1]代表一個三次多項式。

三次樣條插值函數(shù)是一個分段式的三次多項式，在所有的區(qū)間[x_i，x_i+1]上都可以寫成：s（x）=a_ix³+b_ix²+c_ix+d_i（i=1，2，…，n-1），其中a_i，b_i，c_i，d_i為待定系數(shù)，因此s（x）共有4n個需要確定的系數(shù)。為了求得s（x），需要有對應(yīng)的4n個條件。由s（x_i）=f_i（i=1，2，…，n）可得n+1個插值條件。由s（x）∈C²[a，b]可知，s（x）在區(qū)間[a，b]上是二階連續(xù)可導(dǎo)，那么s_-''（x_i）=s₊''（x_i），i=1，2，…，n-1，這里可以得到n-1個條件。進一步的，s（x）在區(qū)間[a，b]上也是一階連續(xù)可導(dǎo)且連續(xù)的，那么：

s_-'（x_i）=s₊'（x_i），i=1，2，…，n-1

s_-（x_i）=s₊（x_i），i=1，2，…，n-1。

因此有2（n-1）個條件。另外再加上兩個邊界條件就得到4n個條件，即可確定s（x）。

3.2 編碼

在三次樣條插值方法中每兩段間的交接點稱為路徑節(jié)點，路徑節(jié)點代表路徑的轉(zhuǎn)向次數(shù)。以一條路徑上的結(jié)點代表一只沙貓，即沙貓的位置為節(jié)點的位置。假設(shè)m個路徑結(jié)點的坐標為（x_m1，y_m1），（x_m2，y_m2），…，（x_mm，y_mm），起點坐標（x_s，y_s）和終點坐標（x_t，y_t）。那么，在區(qū)間（x_s，x_m1，x_m2，…，x_mm，x_t）和（y_s，y_m1，y_m2，…，y_mm，y_t）上，利用三次樣條插值方法可以得到n個插值點的橫坐標（x₁，x₂，…，x_n）和縱坐標（y₁，y₂，…，y_n），由此可以得到了n個插值點。最終由路徑結(jié)點、起點、終點以及插值點擬合的連線就是我們要求的機器人路徑。

3.3 構(gòu)建適應(yīng)度函數(shù)

路徑問題要符合以下兩個約束條件：路徑不能經(jīng)過障礙物；路徑長度要盡可能短。本研究以無碰撞路線的長度來構(gòu)造如下的適應(yīng)度函數(shù)：

其中，beta是個比較大的數(shù)，用于懲罰通過障礙物區(qū)域的路徑，取100；L為路徑長度；第i個插值點的位置為（x_i，y_i）；Violation是表示路線碰撞到障礙物的一個變量，其初始值為0，計算過程為：

為了提高計算難度以貼近實際場景，將障礙物設(shè)置為15邊形表示，n_obs表示障礙物個數(shù)，xx和yy表示全部插值點的坐標。（x_obs（i），y_obs（i））是第i個障礙的中心位置，r_obs（i）表示第i個障礙的中心到頂點的距離，基于式（16）可求得路徑上所有插值點與i個障礙中心間的距離d。通過式（17）判斷路徑是否經(jīng)過第i個障礙，若集合v中的數(shù)都是0，則表示路徑與障礙物無碰撞。式（18）中mean（v）表示集合v的平均數(shù)，Violation是n_obs個mean（v）的累加值，假如路徑有通過障礙物區(qū)域，則Violation是一個大于0的數(shù)，反之，Violation=0。

3.4 算法流程

ISCSO算法流程如圖1所示。

4 仿真實驗及其分析

在確保公正客觀的前提下，將改良的沙貓群優(yōu)化算法ISCSO與標準的沙貓群優(yōu)化算法SCSO、教與學(xué)優(yōu)化算法TLBO^[14]、多元宇宙優(yōu)化算法MVO^[15]、龍格-庫塔優(yōu)化算法RUN^[16]、算數(shù)優(yōu)化算法AOA^[17]進行仿真對比，同時對比改進的PTRBA^[1]和IPSO-GOP^[18]算法，驗證ISCSO的尋優(yōu)性能。

4.1 實驗參數(shù)設(shè)定

為了確保算法對比的公正，對ISCSO算法、SCSO算法、TLBO算法、MVO算法、RUN算法、AOA、PTRBA、IPSO-GOP都是在相同的設(shè)備進行實驗，運行環(huán)境是windows 11，編程環(huán)境為MATLAB R2020b。實驗中，6種算法的種群個數(shù)為20，最大迭代次數(shù)為500，以及相同的障礙物、起點、終點。算法參數(shù)設(shè)定如表1。

4.2 簡單障礙環(huán)境下的路徑規(guī)劃及其算法分析

在簡單環(huán)境下，設(shè)置9個障礙物，6個結(jié)點，100個插值點，起點為（-30，-30），終點為（30，30），進行30次實驗。實驗結(jié)果如圖2、圖3、表2所示。

從圖2、圖3可見，在簡單障礙環(huán)境下，原算法SCSO并不比AOA優(yōu)越，效果更是差于針對機器人路徑規(guī)劃而改進的PTRAB，但經(jīng)過改良后的沙貓優(yōu)化算法ISCSO遠遠優(yōu)越于其他算法。表2是將實驗獨立進行30次求得的路徑長度情況，從實驗數(shù)據(jù)上看，ISCSO不論是最差解、最優(yōu)解還是平均值都優(yōu)越于其他算法，并且所求的結(jié)果非常穩(wěn)定。由此可以證明，3種策略的綜合引入能夠有效提高原算法的尋優(yōu)能力。

4.3 復(fù)雜障礙環(huán)境下的路徑規(guī)劃及其算法分析

在復(fù)雜環(huán)境下，設(shè)置12個障礙物，6個結(jié)點，100個插值點，起點為（-30，-25），終點為（30，25），進行30次實驗。實驗結(jié)果如圖4、圖5、表3所示。

從圖4的路徑圖能夠看出，ISCSO路徑明顯較優(yōu)。從圖5的迭代曲線圖可以看出，當(dāng)障礙環(huán)境變得更為復(fù)雜時，雖然原算法SCSO與RUN相差不大，但經(jīng)過改良后的沙貓優(yōu)化算法ISCSO明顯優(yōu)于其他算法。從表3的30次實驗數(shù)據(jù)可以看出，雖然ISCSO算法的最差解僅次于RUN，但是ISCSO算法的最優(yōu)解以及平均值均優(yōu)越于其他算法，體現(xiàn)了ISCSO算法在復(fù)雜障礙環(huán)境下的有效性與穩(wěn)定性。由此可以證明，經(jīng)過3種策略進行改良，有效提高了沙貓群優(yōu)化算法的優(yōu)化能力。

4 結(jié)語

改進后的沙貓群優(yōu)化算法引入混沌映射提高種群初始化的多樣性；引入互利共生策略和萊維飛行策略，規(guī)避算法跳過最優(yōu)解，消除局部最優(yōu)解的消極影響。通過仿真實驗表明，不論是在簡單障礙環(huán)境還是在復(fù)雜障礙環(huán)境下，改進后的沙貓群優(yōu)化算法在路徑問題的求解性能都更為高效。下一步將對沙貓群優(yōu)化算法繼續(xù)進行改進，同時也考慮將新的啟發(fā)式算法應(yīng)用于路徑問題，探索出性能更優(yōu)的啟發(fā)式智能算法，更加有效的解決機器人路徑問題。

參考文獻：

[1]劉景森，吉宏遠，李煜. 基于改進蝙蝠算法和三次樣條插值的機器人路徑規(guī)劃[J]. 自動化學(xué)報，2021，47（7）：1710-1719.

[2]CONN R A，KAM M. Robot motion planning on N-dimensional star worlds among moving obstacles[J]. IEEE Transactions on Robotics and Automation，1998，14（2）：320-325.

[3]閆皎潔，張鍥石，胡希平. 基于強化學(xué)習(xí)的路徑規(guī)劃技術(shù)綜述[J]. 計算機工程，2021，47（10）：16-25.

[4]成怡，郝密密. 改進深度強化學(xué)習(xí)的室內(nèi)移動機器人路徑規(guī)劃[J]. 計算機工程與應(yīng)用，2021，57（21）：256-262.

[5]裴以建，楊超杰，楊亮亮. 基于改進RRT*的移動機器人路徑規(guī)劃算法[J]. 計算機工程，2019，45（5）：285-290，297.

[6]高怡杰，何湘竹，石英，等. 求解煙草配送路徑規(guī)劃問題的新型智能優(yōu)化算法[J]. 中南民族大學(xué)學(xué)報（自然科學(xué)版），2022，41（1）：87-93.

[7]任春明，張建勛. 基于優(yōu)化蟻群算法的機器人路徑規(guī)劃[J]. 計算機工程，2008，34（15）：1-3，35.

[8]李艷生，萬勇，張毅，等. 基于人工蜂群-自適應(yīng)遺傳算法的倉儲機器人路徑規(guī)劃[J]. 儀器儀表學(xué)報，2022，43（4）：282-290.

[9]王洪斌，尹鵬衡，鄭維，等. 基于改進的A*算法與動態(tài)窗口法的移動機器人路徑規(guī)劃[J]. 機器人，2020，42（3）：346-353.

[10]劉宇. 煤礦井下履帶式機器人路徑規(guī)劃方法研究[D]. 徐州：中國礦業(yè)大學(xué)，2021.

[11]SEYYEDABBASI A，KIANI F. Sand cat swarm optimization：a nature-inspired algorithm to solve global optimization problems[J]. Engineering With Computers，2022：1-25.

[12]陳功，曾國輝，黃勃，等. 融合互利共生和透鏡成像學(xué)習(xí)的HHO算法[J]. 計算機工程與應(yīng)用，2022，58（10）：76-86.

[13]柴巖，任生. 多策略協(xié)同優(yōu)化的改進HHO算法[J]. 計算機應(yīng)用研究，2022，39（12）：3658-3666，3677.

[14]RAO R V，SAVSANI V J，VAKHARIA D P. Teaching-learning-based optimization：a novel method for constrained mechanical design optimization problems[J]. Computer-Aided Design，2011，43（3）：303-315.

[15]MIRJALILI S，MIRJALILI S M，HATAMLOU A. Multi-verse optimizer：a nature-inspired algorithm for global optimization[J]. Neural Computing and Applications，2016，27（2）：495-513.

[16]AHMADIANFAR I，HEIDARI AA，GANDOMI A H，et al. RUN beyond the metaphor：an efficient optimization algorithm based on Runge Kutta method[J]. Expert Systems With Applications，2021，181：115079.

[17]ABUALIGAH L，DIABAT A，MIRJALILI S，et al. The arithmetic optimization algorithm[J]. Computer Methods in Applied Mechanics and Engineering，2021，376：113609.

[18]熊昕霞，何利力. 基于混合粒子群算法的移動機器人路徑規(guī)劃[J]. 計算機系統(tǒng)應(yīng)用，2021，30（4）：153-159.

（責(zé)任編輯：方素華）