基于改進(jìn)麻雀搜索算法的農(nóng)業(yè)機(jī)器人路徑規(guī)劃

摘" 要： 針對(duì)農(nóng)業(yè)機(jī)器人在進(jìn)行路徑規(guī)劃時(shí)存在尋優(yōu)結(jié)果差和搜索穩(wěn)定性低的問(wèn)題，提出一種改進(jìn)的麻雀搜索算法SSAPSO。首先利用Cubic混沌映射初始化種群來(lái)增強(qiáng)麻雀種群位置的多樣性。然后通過(guò)螢火蟲擾動(dòng)策略，增加算法的靈活性和搜索范圍。最后引入粒子群技術(shù)以提高算法的尋優(yōu)精度和穩(wěn)定性。實(shí)驗(yàn)結(jié)果表明，在不同障礙物覆蓋率的柵格地圖環(huán)境下，SSAPSO能高效且穩(wěn)定地求解農(nóng)業(yè)機(jī)器人最優(yōu)路徑，從而提高農(nóng)業(yè)機(jī)器人的工作效率。

關(guān)鍵詞： 麻雀搜索算法； 粒子群算法； 農(nóng)業(yè)機(jī)器人； 路徑規(guī)劃

中圖分類號(hào)：TP3" " " " " 文獻(xiàn)標(biāo)識(shí)碼：A" " "文章編號(hào)：1006-8228（2023）12-115-05

Path planning for agricultural robots based on improved sparrow search algorithm

Mao Shuang， Dai Yongqiang， Liu Huan

（College of Information Science amp; Technology， Gansu Agricultural University， Lanzhou， Gansu 730070， China）

Abstract： An improved sparrow search algorithm， SSAPSO， is proposed to address the problems of poor search results and low search stability in path planning for agricultural robots. Firstly， Cubic chaotic mapping is used to initialize the population to enhance the diversity of sparrow population locations. Then， a firefly perturbation strategy is used to increase the flexibility and search range of the algorithm. Finally， particle swarm techniques are introduced to improve the search accuracy and stability. The experimental results show that SSAPSO can solve the optimal path of agricultural robots efficiently and stably in a raster map environment with different obstacle coverage， thus improving the efficiency of agricultural robots.

Key words： sparrow search algorithm （SSA）; particle swarm optimization （PSO） algorithm; agricultural robot; path planning

0 引言

隨著人工智能技術(shù)的快速發(fā)展，農(nóng)業(yè)生產(chǎn)領(lǐng)域的各個(gè)環(huán)節(jié)得到了重塑，將機(jī)器人技術(shù)與智能算法相融合，應(yīng)用于現(xiàn)代農(nóng)業(yè)中，不僅具有廣泛的研究前景和巨大的應(yīng)用價(jià)值，同時(shí)也是機(jī)器人在農(nóng)業(yè)應(yīng)用領(lǐng)域中備受關(guān)注的難點(diǎn)技術(shù)之一，尤其是路徑規(guī)劃。

當(dāng)前遺傳算法、蟻群算法以及粒子群算法等智能仿生算法[1]，在機(jī)器人路徑規(guī)劃的實(shí)際問(wèn)題中得到了廣泛的應(yīng)用。潘忠英等[2]提出一種A*-ISSA算法策略，通過(guò)自適應(yīng)多普勒策略和量子行為來(lái)提高麻雀算法的收斂精度，并將A*與ISSA算法相結(jié)合，提高了農(nóng)業(yè)機(jī)器人的作業(yè)效率。雷超帆等[3]提出一種融合粒子群與蟻群算法的策略，利用粒子群算法優(yōu)化蟻群算法參數(shù)來(lái)實(shí)現(xiàn)路徑規(guī)劃，提高蟻群算法的綜合性能及機(jī)器人路徑規(guī)劃能力。梁景泉等[4]提出一種粒子群優(yōu)化算法與灰狼算法相結(jié)合的策略，通過(guò)粒子群算法來(lái)解決灰狼算法容易早熟收斂、局部最優(yōu)以及收斂速度慢等問(wèn)題。提高了機(jī)器人路徑規(guī)劃效率。劉燁[5]等提出一種基于遺傳機(jī)制的改進(jìn)蟻群算法策略，該策略改進(jìn)信息素分配方式，增加刪除算子，提高了機(jī)器人的路徑尋優(yōu)能力。馬凱凱等[6]提出一種粒子群算法與引力算法相結(jié)合的混合算法，將粒子群算法的全局搜索能力和引力算法的局部挖掘能力相結(jié)合，從而提高了機(jī)器人搜索速度。以上幾種融合算法策略，均能夠解決機(jī)器人路徑規(guī)劃中所遇到的一些基本問(wèn)題，但是存在求解效率較低、優(yōu)化精度不高等問(wèn)題。

在此基礎(chǔ)上，本文提出一種改進(jìn)麻雀搜索算法的農(nóng)業(yè)機(jī)器人路徑規(guī)劃策略。麻雀搜索算法（Sparrow Search Algorithm， SSA）[7]是近幾年較新的群體智能算法。本文采用Cubic混沌映射對(duì)麻雀種群進(jìn)行初始化以增加麻雀種群的多樣性，并通過(guò)螢火蟲擾動(dòng)策略使得算法靈活性增強(qiáng)，搜索范圍擴(kuò)大，收斂速度加快。最后，考慮到原有算法易陷入局部最優(yōu)和穩(wěn)定性差等特點(diǎn)，在改進(jìn)麻雀搜索算法中引入粒子群技術(shù)來(lái)增強(qiáng)搜索能力和穩(wěn)定性。實(shí)驗(yàn)證明，本文提出的路徑規(guī)劃策略，在障礙物覆蓋率不一致的柵格地圖環(huán)境下能高效且穩(wěn)定地解決農(nóng)業(yè)機(jī)器人路徑規(guī)劃問(wèn)題。

1 算法簡(jiǎn)介

1.1 SSA算法

麻雀搜索算法是一種仿生優(yōu)化算法，其靈感來(lái)自麻雀種群的覓食行為。該麻雀群體可分為發(fā)現(xiàn)者、加入者和偵察者。發(fā)現(xiàn)者主要負(fù)責(zé)尋找食物和帶領(lǐng)其他麻雀尋找食物源，其他麻雀則依靠這些發(fā)現(xiàn)者尋找食物。偵察者觀察麻雀群體內(nèi)部的環(huán)境有無(wú)危險(xiǎn)，提醒全麻雀群體安全。

發(fā)現(xiàn)者的位置更新公式如下：

[Xt+1i，j=Xti，j?exp-iα?itermax，" R2lt;STXti，j+Q?L，" " " " " " " " " R2≥ST]" ⑴

其中，[itermax]表示最大迭代次數(shù)，[Xt+1i，j]表示第[i]個(gè)麻雀在第[j]維的位置，[α∈（0，1）]是一個(gè)隨機(jī)數(shù)，[R2?[0，1]]為預(yù)警值，[ST∈[0.5，1]]為安全值，[Q]是服從正態(tài)分布的隨機(jī)數(shù)，[L]為[1×d]且元素值全為1的矩陣。

加入者的位置更新公式如下：

[Xt+1i，j=Q?expXworst-Xti，ji2，" " " " " " " " "igt;N2Xt+1p+Xti，j-Xt+1p?A+?L，" " "i≤N2]" ⑵

其中，[Xworst]表示第[t]次迭代全局最差位置，[Xt+1p]表示[t+1]次迭代發(fā)現(xiàn)者最優(yōu)位置，[A]為多維矩陣，元素賦值為1或-1，且[A+=AT（AAT）-1]。

偵察者位置更新公式如下：

[Xt+1i，j=Xtbest+β?Xti，j-Xtbest，" " " "figt;fgXti，j+K?Xti，j-Xtworstf1-fw+ε，" " "fi=fg]" ⑶

其中，[Xtbest]為當(dāng)前全局最優(yōu)位置，[β]為步長(zhǎng)控制參數(shù)。[k∈[-1，1]]用于控制麻雀的活動(dòng)方向，[fi]表示個(gè)體適應(yīng)度值，[fg]為最佳適應(yīng)度值，[fw]為最差適應(yīng)度值，[ε]為防止分母為零，記為最小常數(shù)。

1.2 PSO算法

粒子群算法（Particle Swarm Optimization， PSO）[8]其主要通過(guò)更新粒子的速度、位置等信息尋找最優(yōu)解。假設(shè)種群有N個(gè)粒子在D維空間搜索，初始粒子群算法更新表示為：

[vd+1ij=ωvdij+c1r1pdij-xdij+c2r2pdgj-xdij]

[vd+1ij=vdij+vd+1ij] ⑷

其中，[d]為迭代次數(shù)，[vij]表示第[i]個(gè)粒子[j]維的速度，[xij]表示第[i]個(gè)粒子[j]維的位置。[ω]表示慣性權(quán)重，[c1、c2]表示學(xué)習(xí)因子，[r1、r2]表示范圍在[0，1]之間的隨機(jī)數(shù)。

2 改進(jìn)的SSA算法（CFSSA）

2.1 Cubic混沌映射初始化麻雀種群

Cubic混沌映射[9]具有隨機(jī)性、均勻性、有序性，以及不重復(fù)全部狀態(tài)的特性。

在初始化階段，麻雀?jìng)€(gè)體之間呈非均勻分布，造成其初始位置相對(duì)聚集，不利于尋找全局最佳位置。為此，本文利用Cubic混沌因子初始化種群，克服盲目性，同時(shí)也使得個(gè)體初始位置更均勻分布于搜索空間，增加了麻雀種群多樣性，也為麻雀搜索算法后期優(yōu)化奠定基礎(chǔ)。

Cubic表達(dá)式如下：

[xn+1=ρxn1-x2n]" ⑸

其中，[xn?（0，1）]，[ρ]為控制參數(shù)。[xn]的初值為（0，1），取[xn=0.3]，[ρ=2.595]。

2.2 螢火蟲擾動(dòng)策略

麻雀搜索算法采用螢火蟲算法擾動(dòng)麻雀位置[10]，每代麻雀?jìng)€(gè)體位置更新后，利用螢火蟲算法擾動(dòng)并更新個(gè)體位置，以使得個(gè)體麻雀有足夠能力跳出局部最優(yōu)。當(dāng)擾動(dòng)結(jié)束時(shí)，將擾動(dòng)前后個(gè)體麻雀適應(yīng)度函數(shù)進(jìn)行對(duì)比，若擾動(dòng)后個(gè)體麻雀表現(xiàn)更優(yōu)，則更新位置，公式如下：

[xi=xi+β?xj-xi+α?rand*-12]" ⑹

其中，[xi]和[xj]為麻雀[i]和[j]的空間位置，[α]為步長(zhǎng)因子，[rand*∈0，1]區(qū)間服從均勻分布的隨機(jī)數(shù)。

2.3 混合算法設(shè)計(jì)（SSAPSO）

混合麻雀算法與粒子群算法的核心思想是：將改進(jìn)后的麻雀算法的相關(guān)參數(shù)作為粒子群算法的位置信息，使用粒子群的位置信息來(lái)運(yùn)行麻雀算法，最終進(jìn)行路徑規(guī)劃（如圖1所示）。

混合算法的運(yùn)行步驟如下：

步驟1 系數(shù)初始化。設(shè)置麻雀、粒子群種群數(shù)量、迭代次數(shù)相關(guān)參數(shù)等，使用公式（5）進(jìn)行麻雀種群位置的初始化，增加搜索范圍的多樣性。

步驟2 運(yùn)用適應(yīng)度值函數(shù)對(duì)麻雀進(jìn)行排序，以獲取其個(gè)體最優(yōu)和全局最優(yōu)適應(yīng)度值，并記錄其個(gè)體和全局最優(yōu)位置。

步驟3 使用公式⑴、公式⑵、公式⑶更新發(fā)現(xiàn)者、加入者、偵察者的位置。

步驟4 使用公式⑹對(duì)處于最優(yōu)位置的麻雀進(jìn)行螢火蟲隨機(jī)擾動(dòng)。

步驟5 計(jì)算適應(yīng)度值函數(shù)，保留麻雀?jìng)€(gè)體位置和全局最優(yōu)位置。

步驟6 判斷當(dāng)前的個(gè)體位置和全局最優(yōu)位置，是否優(yōu)于粒子群的個(gè)體最優(yōu)和全局最優(yōu)。如果所處位置優(yōu)于當(dāng)前，則進(jìn)入粒子群算法階段，否則返回步驟⑵。

步驟7 使用公式⑷更新各粒子群的位置和速度。

步驟8 更新粒子群個(gè)體最優(yōu)和全局最優(yōu)位置。

步驟9 判斷迭代次數(shù)是否滿足最大值，若滿足則輸出全局最佳位置，全局最佳位置所對(duì)應(yīng)的位置信息作為麻雀算法的重要參數(shù)，運(yùn)行麻雀算法進(jìn)行路徑規(guī)劃，否則返回步驟⑹。

3 SSAPSO算法性能測(cè)試

為驗(yàn)證SSAPSO算法的改進(jìn)效果，采用四個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，其中[f1]、[f2]、[f3]為單峰函數(shù)，[f4]為多峰函數(shù)，具體描述如表1所示。

將SSAPSO算法與麻雀搜索算法（Sparrow Search Algorithm， SSA）、粒子群算法（Particle Swarm Optimization， PSO）、改進(jìn)的麻雀搜索算法（CFSSA）在Matlab2021a中進(jìn)行對(duì)比實(shí)驗(yàn)。針對(duì)這四種算法，每個(gè)算法獨(dú)立運(yùn)行30次。其中，每運(yùn)行一次的算法迭代次數(shù)為1000，種群數(shù)量為30。

如表2給出了SSA、PSO、CFSSA、SSAPSO對(duì)于四種基準(zhǔn)函數(shù)的仿真實(shí)驗(yàn)結(jié)果。從表2可以看出，均值和標(biāo)準(zhǔn)差反映了SSA、PSO、CFSSA、SSAPSO對(duì)測(cè)試函數(shù)[f1]到[f4]所求解的質(zhì)量，可得出SSAPSO算法優(yōu)于其他算法。標(biāo)準(zhǔn)差反映出算法的魯棒性和穩(wěn)定性，對(duì)于函數(shù)[f1]到[f4]，SSAPSO有較明顯的優(yōu)勢(shì)。對(duì)于求解單峰函數(shù)[f1]、[f2]、[f3]，SSAPSO算法的尋優(yōu)性能明顯強(qiáng)于其他算法。在求解多峰函數(shù)[f4]時(shí)，SSAPSO的求解精度最高，說(shuō)明SSAPSO的穩(wěn)定性強(qiáng)于其他算法。

綜上所述，引入多種策略使得算法在尋優(yōu)效率上有明顯的提升，本文設(shè)計(jì)的SSAPSO算法在測(cè)試函數(shù)上表現(xiàn)出優(yōu)秀的優(yōu)化能力與搜索精度，進(jìn)一步驗(yàn)證了改進(jìn)算法是有效可行的。

4 路徑規(guī)劃仿真測(cè)試

4.1 環(huán)境建模

在農(nóng)業(yè)機(jī)器人規(guī)劃一條路徑之前，需要對(duì)農(nóng)業(yè)機(jī)器人的工作環(huán)境進(jìn)行建模和預(yù)處理。柵格法[11]是農(nóng)業(yè)機(jī)器人路徑規(guī)劃工作環(huán)境建模的一種傳統(tǒng)方法。如圖2所示，設(shè)定黑色柵格為障礙物區(qū)域用“1”表示，農(nóng)業(yè)機(jī)器人不可以通過(guò)，白色柵格為空閑區(qū)域用“0”表示，農(nóng)業(yè)機(jī)器人可以通過(guò)，柵格的長(zhǎng)度為1m，柵格按從下至上、從左往右的順序編號(hào)。每個(gè)柵格都有惟一的序號(hào)和位置坐標(biāo)，轉(zhuǎn)換公式如下：

[xi=αmodi，MM-0.5yi=αNN+0.5-ceiliNN]" ⑺

其中，[xi]和[yi]為第[i]個(gè)柵格位置的坐標(biāo)；[α]表示小柵格的邊長(zhǎng)，通常取1；[MM]和[NN]分別為行方向和列方向的柵格數(shù)；[mod]為冗余運(yùn)算符；[ceil]為向上取整。

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

為了驗(yàn)證SSAPSO算法在路徑規(guī)劃中的尋優(yōu)性能，將其與SSA、PSO和CFSSA算法進(jìn)行對(duì)比分析。其中，20m×20m柵格地圖環(huán)境下的障礙物覆蓋率達(dá)到15.3%，40m×40m柵格地圖環(huán)境下的障礙物覆蓋率達(dá)到23.3%，50m×50m柵格地圖環(huán)境下的障礙物覆蓋率達(dá)到32.2%。實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)選取30次，各算法種群數(shù)量為30，最大迭代次數(shù)為200。

4.3 實(shí)驗(yàn)結(jié)果與分析

根據(jù)表3可知，在路徑最優(yōu)值方面，SSAPSO的最優(yōu)路徑長(zhǎng)度較CFSSA縮短5.7%，較SSA縮短14.4%，較PSO縮短12.3%。在平均路徑長(zhǎng)度方面，SSAPSO平均路徑長(zhǎng)度較CFSSA縮短4.5%，較SSA縮短12.5%，較PSO縮短26.6%。標(biāo)準(zhǔn)差反應(yīng)算法的穩(wěn)定性，在求解最優(yōu)值路徑的穩(wěn)定性方面，SSAPSO路徑穩(wěn)定性比CFSSA提高了50%，比SSA提高了78%，比PSO提高了93%。在運(yùn)行時(shí)間上，各算法運(yùn)行時(shí)間都隨地圖環(huán)境復(fù)雜性提高而增加。SSAPSO算法的運(yùn)行時(shí)間增加是由于采用多種改進(jìn)策略，增強(qiáng)了算法的種群多樣性，提高了尋優(yōu)精度。

根據(jù)圖3可知，PSO和SSA算法容易陷入局部最優(yōu)解，導(dǎo)致路徑不夠平滑。SSAPSO相較于其他算法，能最快獲得最優(yōu)路徑且路徑也更加平滑。根據(jù)圖4可知，PSO和SSA算法的路徑存在轉(zhuǎn)折點(diǎn)過(guò)多，路徑的平滑度低，不利于農(nóng)業(yè)機(jī)器人的平穩(wěn)移動(dòng)。相較于PSO和SSA，SSAPSO算法搜索到的路徑轉(zhuǎn)折點(diǎn)更少，規(guī)劃出的路徑質(zhì)量更高。根據(jù)圖5可知，隨著地圖維度的增大，SSAPSO、CFSSA、SSA和PSO這4種算法規(guī)劃出的路徑拐點(diǎn)數(shù)量也隨之增加。其中，SSAPSO算法所規(guī)劃的路徑拐點(diǎn)個(gè)數(shù)最少，收斂快。因此，SSAPSO算法的路徑規(guī)劃速度更快、穩(wěn)定性更好，路徑規(guī)劃求解質(zhì)量也明顯優(yōu)于其他算法。

通過(guò)仿真實(shí)驗(yàn)的對(duì)比和分析可知，在不同障礙物覆蓋率的地圖環(huán)境中，SSAPSO可以高效穩(wěn)定地求解農(nóng)業(yè)機(jī)器人路徑規(guī)劃問(wèn)題，能夠獲得較好的路徑求解結(jié)果。

5 結(jié)束語(yǔ)

本文針對(duì)農(nóng)業(yè)機(jī)器人在進(jìn)行路徑規(guī)劃時(shí)會(huì)存在尋優(yōu)結(jié)果差和搜索穩(wěn)定性低的問(wèn)題，提出一種改進(jìn)的麻雀搜索算法。首先，采用Cubic混沌映射改善初始種群不均的問(wèn)題。然后，利用螢火蟲擾動(dòng)策略，提高算法的探索能力和收斂精度。最后，為了避免在搜索過(guò)程中陷入局部極值的問(wèn)題，引入粒子群算法，該算法能夠更容易地跳出當(dāng)前狀態(tài)，從而避免陷入局部最優(yōu)，進(jìn)一步提升了算法的局部搜索能力。實(shí)驗(yàn)結(jié)果表明，SSAPSO優(yōu)化后的路徑最短、求解精度最高、穩(wěn)定性最好，很大程度上提高了農(nóng)業(yè)機(jī)器人的路徑尋優(yōu)能力，保證了農(nóng)業(yè)機(jī)器人的作業(yè)效率。

參考文獻(xiàn)（References）：

[1] 林韓熙，向丹，歐陽(yáng)劍，等.移動(dòng)機(jī)器人路徑規(guī)劃算法的研究

綜述[J].計(jì)算機(jī)工程與應(yīng)用，2021，57（18）：38-48.

[2] 潘忠英，尚猛.改進(jìn)麻雀算法和A～*算法的農(nóng)業(yè)機(jī)器人路徑

規(guī)劃[J]. 機(jī)械設(shè)計(jì)與研究，2022，38（1）：31-37.

[3] 雷超帆，趙華東，江南.融合粒子群與蟻群算法的機(jī)器人路徑

規(guī)劃[J].重慶理工大學(xué)學(xué)報(bào)（自然科學(xué)），2020，34（1）：235-241.

[4] 梁景泉，周子程，劉秀燕.粒子群算法改進(jìn)灰狼算法的機(jī)器人

路徑規(guī)劃[J].軟件導(dǎo)刊，2022，21（5）：96-100.

[5] 劉燁，杜艷平，張騰丹，等.基于遺傳機(jī)制改進(jìn)蟻群算法的室內(nèi)

移動(dòng)機(jī)器人路徑規(guī)劃研究[J].北京印刷學(xué)院學(xué)報(bào)，2022，30（2）：57-62.

[6] 馬凱凱，李翠明，吳新民.基于引力搜索和粒子群混合算法的

移動(dòng)機(jī)器人路徑規(guī)劃[J].機(jī)械設(shè)計(jì)與制造工程，2019，48（12）：43-46.

[7] 薛建凱.一種新型的群智能優(yōu)化技術(shù)的研究與應(yīng)用[D].

上海：東華大學(xué)，2020.

[8] 吳大飛，楊光永，樊康生，等.多策略融合的改進(jìn)粒子群優(yōu)化

算法[J].計(jì)算機(jī)應(yīng)用研究，2022，39（11）：3358-3364.

[9] Feng Junhong，ZhangJie，ZhuXiaoshu，etal.A novel chaos

optimization algorithm[J].Multimedia Tools and Applications，2017，76（16）：17405-17436.

[10] 劉睿，莫愿斌.一種改進(jìn)的麻雀搜索算法[J].計(jì)算機(jī)技術(shù)與

發(fā)展，2022，32（3）：21-26.

[11] 王影，梁凱，于攀，等.基于柵格模型與改進(jìn)蟻群算法的機(jī)器

人路徑規(guī)劃研究[J].內(nèi)蒙古科技大學(xué)學(xué)報(bào)，2019，38（4）：349-354.