李 靖，楊 帆

（河北工業(yè)大學(xué) 電子信息工程學(xué)院，天津 300401）

隨著智慧農(nóng)業(yè)的發(fā)展，計算機(jī)視覺已經(jīng)在農(nóng)業(yè)領(lǐng)域取得了良好的成績。如KOUNALAKIS等[1]在闊葉雜草的奶牛場中實(shí)現(xiàn)了雜草自動識別系統(tǒng)。張芳等[2]提出一種用于黃瓜葉部病蟲害的識別系統(tǒng)。李少軒[3]開發(fā)了人機(jī)交互式干旱事件應(yīng)急應(yīng)對服務(wù)系統(tǒng)。此外，深度學(xué)習(xí)(deep learning，DL)技術(shù)的日益成熟，它在我國農(nóng)業(yè)領(lǐng)域有了廣大的發(fā)展應(yīng)用[4]，且隨著樣本數(shù)量的增加，DL技術(shù)的農(nóng)作物、病蟲害等分類識別更加廣泛及精準(zhǔn)。但在識別后如何自動化處理的途徑研究相對較少。無人機(jī)漸漸的從軍用走向民用領(lǐng)域，可以將無人機(jī)作業(yè)策略引入農(nóng)業(yè)領(lǐng)域。無人機(jī)航跡規(guī)劃是無人機(jī)作業(yè)領(lǐng)域研究的基礎(chǔ)，為其作業(yè)效果提供基礎(chǔ)保障。OUYANG等[5]提出了一種面向任務(wù)的無人機(jī)航跡規(guī)劃，根據(jù)作戰(zhàn)任務(wù)將無人機(jī)航路分為固定航路和突防航路，在軍事領(lǐng)域根據(jù)其作戰(zhàn)任務(wù)能取得良好效果。ZHENG等[6]針對應(yīng)急管理領(lǐng)域提出了一種用于快速圖像拼接的無人機(jī)航跡規(guī)劃數(shù)學(xué)模型，給定的模型考慮了3種不同的方法，覆蓋了大部分無人機(jī)飛行任務(wù)的情況。LI等[7]以飛行時間和飛行安全因素為基礎(chǔ)，建立目標(biāo)函數(shù)，利用模糊技術(shù)對威脅等級進(jìn)行評估，運(yùn)用粒子群優(yōu)化算法(partile swarm optimization，PSO)搜索策略進(jìn)行無人機(jī)航跡規(guī)劃。劉文兵等[8]對多任務(wù)目標(biāo)聚類，在類內(nèi)運(yùn)用了2-opt算子改進(jìn)遺傳算法進(jìn)行無人機(jī)航跡路徑規(guī)劃。目前，群智能優(yōu)化算法[9]在無人機(jī)航跡規(guī)劃領(lǐng)域較為流行，但群智能優(yōu)化算法易陷入局部最優(yōu)解的情況未能從根本上解決，且已有二維空間無人機(jī)航跡規(guī)劃算法較少的考慮了障礙物空間對航跡的影響。針對上述問題，在農(nóng)田噴灑作業(yè)領(lǐng)域提出了一種改進(jìn)灰狼優(yōu)化算法 （improve grey wolf optimizer，IGWO）與A*算法相結(jié)合的無人機(jī)航跡規(guī)劃算法。IGWO算法引入K-Means聚類算法初始化種群以加強(qiáng)種群多樣性，引入非線性收斂因子以平衡全局搜索與局部開發(fā)能力，引入PSO算法位置更新調(diào)整以避免陷入局部最優(yōu)問題。通過IGWO算法對標(biāo)記的多噴灑任務(wù)點(diǎn)進(jìn)行無障礙遍歷航跡規(guī)劃，隨后運(yùn)用A*算法對障礙物路線航跡局部避障調(diào)整。

1 理論依據(jù)

1.1 灰狼優(yōu)化算法

灰狼優(yōu)化算法（grey wolf optimizer，GWO）[10]是模擬灰狼群體捕獵行為的群智能優(yōu)化算法?；依菗碛袊?yán)格的金字塔層級結(jié)構(gòu)，從頂層到底層包含四種狼，分別是 alpha(α)狼、beta(β)狼、delta(δ)狼和 omega(ω)狼。 α 狼是首領(lǐng)狼，β狼服從α狼領(lǐng)導(dǎo)，δ狼服從α狼和β狼，其余狼稱為ω狼處于最底層。GWO算法數(shù)學(xué)建模中，每只灰狼代表種群中1個候選解，將最優(yōu)解視為α狼，第二和第三最佳候選解視為β狼和δ狼，其余的候選解視為ω狼。灰狼圍捕獵物的數(shù)學(xué)模型描述為：

式中：t為當(dāng)前迭代次數(shù)；tmax為最大迭代次數(shù)；A和C為系數(shù)向量；Xp為獵物的位置向量；X為灰狼的位置向量；r1和r2的大小為[0，1]之間的隨機(jī)數(shù)，a為收斂因子隨著迭代次數(shù)的增加從2線性減小到0。

灰狼追蹤獵物位置的數(shù)學(xué)模型描述為：

式中：C1、C2與 C3為隨機(jī)向量；Xα、Xβ和 Xδ為 α狼、β狼和 δ狼的位置；X 為當(dāng)前狼的位置。

1.2 改進(jìn)的灰狼優(yōu)化算法

1.2.1 K-Means聚類初始化種群 K-Means聚類算法[11]是通過距離度量數(shù)據(jù)相似性，數(shù)據(jù)間距離越小相似性越高，則可以歸為同類。大量隨機(jī)生成樣本點(diǎn)后運(yùn)用K-Means算法挑選k個精英個體（k個聚類中心）初始化種群。 假設(shè)隨機(jī)生成 n 個樣本點(diǎn)為 P={P1，P2，…，Pn}，需要聚類分成 k 類 C={C1，C2，…Ck}，聚類中心為 μ={μ1，μ2，…μk}，則可以計算樣本點(diǎn)與各聚類中心的距離dist(Pi，uj)，將該樣本點(diǎn)劃分到距離最近的類（Pi∈μnearst），再根據(jù)類中樣本點(diǎn)重新計算聚類中心，重復(fù)上述操作，直到滿足迭代次數(shù)或最小化損失函數(shù)為止，將生成的各聚類中心（精英個體）用于初始化種群。其中，聚類中心更新公式為：

圖1中隨機(jī)生成500個樣本點(diǎn)，設(shè)置種群數(shù)量k為30，運(yùn)用K-Means聚類將500個樣本點(diǎn)聚類分成30類，通過公式（7）計算出每類的聚類中心，將30個聚類中心用于初始化種群。由圖1b可知500個樣本點(diǎn)生成的30個種群精英個體，具有空間分布相對均勻的效果，增強(qiáng)了種群的多樣性，避免算法開始時就陷入局部最優(yōu)。

圖1 K-Means算法聚類種群初始化（種群數(shù)量30）Figure 1 Population initialization of K-Means algorithm clustering(the number of population is 30)

1.2.2 非線性收斂因子 HEIDARI等[12-13]指出A和C是兩個隨機(jī)自適應(yīng)向量以輔助GWO算法全局搜索和局部開發(fā)。由式（3）可知向量C是隨機(jī)的，因此向量A與全局搜索與局部開發(fā)能力息息相關(guān)。|A|＞1時灰狼種群增大搜索范圍尋找獵物，實(shí)現(xiàn)全局搜索；|A|＜1時收縮搜索范圍攻擊獵物，實(shí)現(xiàn)局部開發(fā)。由式（2）可知A的取值范圍為[-a，a]，A隨a變化，且隨著迭代次數(shù)的增加a線性的從2衰減到0。而算法的收斂并不是線性的過程，在全局搜索階段需要搜索慢些利于尋找獵物，而找到獵物后收斂快些易于迅速攻擊，因此式（4）中a的線性衰減不能滿足實(shí)際情況，從而引入非線性收斂的余弦收斂因子，即：

式中：Tmax為最大迭代次數(shù)；t為當(dāng)前迭代次數(shù)。圖2顯示了收斂因素a的先慢后快的非線性收斂變化。

圖2 收斂因子對比效果Figure 2 Comparison effect of convergence factor

1.2.3 位置更新調(diào)整策略 GWO算法的位置更新方程如式（6），其考慮了個體與種群的位置交流信息，但忽略了自身個體經(jīng)驗(yàn)信息的交流[14]，而PSO算法對個體自身歷史最優(yōu)解具有記憶的能力[15]，因此在IGWO算中引入PSO算法中個體速度更新及位置更新策略，使得灰狼種群個體能夠保存自身最優(yōu)位置信息，則灰狼追蹤獵物位置的數(shù)學(xué)模型可修改描述為：

式中：ω 為慣性系數(shù)；c1，c2，c3為學(xué)習(xí)因子；r1，r2，r3為[0，1]之間的隨機(jī)數(shù)。

1.3 A*路徑規(guī)劃算法

A*算法[16-17]是一種啟發(fā)式搜索算法，路徑規(guī)劃時對每個搜索位置進(jìn)行估價，即：

式中：G(n)為起點(diǎn)到第n節(jié)點(diǎn)的實(shí)際代價，H(n)為第n節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑的估計代價。搜索過程是通過OPEN表和CLOSED表標(biāo)識的，OPEN表記錄了待搜索節(jié)點(diǎn)，CLOSED表記錄了已搜索過節(jié)點(diǎn)，不斷的根據(jù)估價函數(shù)重排OPEN表尋找最優(yōu)節(jié)點(diǎn)實(shí)現(xiàn)搜索過程。

2 無人機(jī)農(nóng)田噴灑航跡規(guī)劃

無人機(jī)農(nóng)田噴灑航跡規(guī)劃主要有兩個階段，一是運(yùn)用改進(jìn)灰狼優(yōu)化算法進(jìn)行多噴灑點(diǎn)的無障礙空間遍歷路徑求解，以解決多噴灑點(diǎn)先后順序及噴灑路徑，二是運(yùn)用A*算法對噴灑路徑進(jìn)行修正以避免障礙物碰撞。

2.1 IGWO算法求解無障礙空間航跡路徑

假設(shè)區(qū)域工作環(huán)境地圖已知，要求無人機(jī)能夠遍歷全部n個噴灑點(diǎn)形成遍歷航跡路徑，則路徑長度為：

式中：||TjTj+1||表示第j到j(luò)+1個噴灑點(diǎn)的距離。||TnT1||表示第n噴灑點(diǎn)到起始噴灑點(diǎn)之間的距離。要求出遍歷任務(wù)點(diǎn)順序 T={T1，T2，…，Tn}，使路徑長度最短 min（L）。 以式（12）作為目標(biāo)函數(shù)，運(yùn)用IGWO算法求解最優(yōu)解得出無障礙物空間多噴灑點(diǎn)一次航跡路徑，其流程如圖3。

2.2 A*算法求解障礙物空間航跡路徑

A*算法以圖的輸入形式進(jìn)行連接編碼矩陣區(qū)域搜索，尋找出一條從起點(diǎn)到已搜索區(qū)域中所有節(jié)點(diǎn)的最短路徑。為了降低計算復(fù)雜度，A*算法首先將高分辨率地圖降低為適用的低分率地圖，將降低分辨率地圖的每個像素作為節(jié)點(diǎn)，每個節(jié)點(diǎn)都有許多無障礙物連接線作為邊，形成編碼矩陣，圖4為常用的3種連接編碼矩陣（搜索模板），所有可能的移動用1表示，所有不可以的移動用0表示，R代表無人機(jī)當(dāng)前位置。搜索方向越多，搜索路徑可能性就越多，搜索精度越高，但計算耗時會越大。圖6a為分辨率500×500降低到100×100的地圖上進(jìn)行模板b的路徑擴(kuò)張搜索區(qū)域（灰色區(qū)域），圖6b為避障后從噴灑點(diǎn)(50，50)到噴灑點(diǎn)(400，400)規(guī)劃出的航跡路線，路徑長度為 553．5534m。

圖3 IGWO算法求解航跡規(guī)劃流程圖Figure 3 Flow chart of IGWO algorithm to solve the route planning

圖4 連接編碼矩陣Figure 4 Connection coding matrix

3 試驗(yàn)仿真結(jié)果與分析

3.1 IGWO算法無障礙物航跡規(guī)劃

圖5為GWO算法與IGWO算法在無障礙物空間中求解多個噴灑點(diǎn)的航跡規(guī)劃路徑對比效果，其中種群的數(shù)量設(shè)置為30，最大迭代次數(shù)為800次，當(dāng)待噴灑點(diǎn)較少時（圖5a和圖5b 5個噴灑點(diǎn)），GWO算法與IGWO算法航跡規(guī)劃路徑相同，均為2-3-4-5-1-2噴灑點(diǎn)遍歷航跡路徑，路徑長度2552．7062m。而當(dāng)待噴灑點(diǎn)較多時 （圖5c和5d 30個噴灑點(diǎn)），GWO算法與IGWO算法求解無障礙物空間航跡路徑分別為6357．799m和6092．4102m，路徑縮短265．3888m，路徑縮短4．17%。從圖6對30個任務(wù)點(diǎn)求解適應(yīng)度曲線的收斂情況可知，IGWO算法第248次迭代時便尋找到了最優(yōu)遍歷路徑，而GWO算法在784次迭代才尋找到最優(yōu)解路徑，IGWO算法尋優(yōu)迭代次數(shù)為GWO算法的1/3，效率提升2倍，且IGWO算法的收斂效果要優(yōu)于GWO算法，說明IGWO算法的模型求解能力更強(qiáng)。

圖5GWO算法與IGWO算法無障礙物空間航跡規(guī)劃對比Figure 5 Route planning for obstacle avoidance of A*algorithm

3.2 A*算法障礙物避障航跡規(guī)劃

圖7 為房屋障礙物田間地圖，通過交互式標(biāo)記出障礙物區(qū)域如圖7b白色區(qū)域，生成障礙物地圖掩模板，圖7c白色區(qū)域?yàn)檎系K物區(qū)域不可通行，黑色區(qū)域?yàn)樽杂煽臻g可通行。運(yùn)用A*算法通過2．2節(jié)3種連接編碼矩陣模板對障礙物進(jìn)行避障及航跡規(guī)劃，路徑起點(diǎn)坐標(biāo)為(250，50)，目標(biāo)點(diǎn)坐標(biāo)為(150，200)，其路徑規(guī)劃長度分別為 327．4000，296．6703，287．5984m， 路徑規(guī)劃效果如圖7d～f，可以看出連接編碼矩陣模板越簡單，路徑規(guī)劃效果越差但耗時相對減少，綜合考慮路徑長度及路徑平滑程度，可以得出模板b與模板c是可以被選擇的。

3.3 基于IGWO-A*算法的農(nóng)田噴灑無人機(jī)航跡規(guī)劃

圖8a白色實(shí)線段為農(nóng)田區(qū)域無障礙物時IGWO算法求解的遍歷多噴灑點(diǎn)的航跡規(guī)劃效果，其遍歷順序?yàn)?-8-2-5-4-3-7-6-1，此步為一次航跡規(guī)劃。當(dāng)發(fā)現(xiàn)規(guī)劃路徑中噴灑點(diǎn)6至噴灑點(diǎn)1的航跡中有障礙物阻礙，如圖8b白色方框?yàn)檎系K物區(qū)域，此時在此段航跡中運(yùn)用A*算法進(jìn)行噴灑點(diǎn)6坐標(biāo)為起點(diǎn)，噴灑點(diǎn)1坐標(biāo)為目標(biāo)點(diǎn)的避障二次航跡規(guī)劃，以修正此段航線。圖8c和圖8d的白色虛線段為A*算法運(yùn)用模板b和模板c搜索的避障二次修改效果路徑，從而形成了農(nóng)田多噴灑點(diǎn)無人機(jī)航跡規(guī)劃結(jié)果。

圖6 收斂性能對比Figure 6 Comparison of convergence performance

圖7 A*算法求解避障航跡路徑Figure 7 A*algorithm to solve the path of obstacle avoidance

圖8 基于IGWO-A*算法的農(nóng)田噴灑無人機(jī)航跡規(guī)劃結(jié)果Figure 8 Result of route planning of UAV for farmland spraying based on IGWO-A*algorithm

4 討論與結(jié)論

本研究結(jié)果表明，改進(jìn)灰狼優(yōu)化算法引入K-Means聚類算法，可以從500種群個體篩選出遍布全局的30個精英個體以初始化種群，可以加強(qiáng)種群的多樣性與優(yōu)越性；引入非線性收斂因子可以實(shí)現(xiàn)全局搜索慢些以廣泛的搜尋獵物，在找到獵物收斂快些以迅速攻擊獵物；引入PSO算法的對于個體自身歷史最優(yōu)信息的記憶能力，可以使得灰狼種群個體能夠保存自身最優(yōu)位置信息。通過上述對傳統(tǒng)灰狼優(yōu)化算法的改進(jìn)，使得對無人機(jī)噴灑作業(yè)遍歷航跡規(guī)劃模型求解的能力更強(qiáng)。在本試驗(yàn)?zāi)Ｐ铜h(huán)境中，IGWO算法需要248次迭代找到最優(yōu)解遍歷路徑，而GWO算法需要784次迭代才能找到最優(yōu)解路徑，效率提升2倍。而在航跡規(guī)劃長度上，本試驗(yàn)環(huán)境下對于5個任務(wù)點(diǎn)的遍歷航跡規(guī)劃GWO算法與IGWO算法的航跡規(guī)劃長度相同；而對于30個任務(wù)點(diǎn)遍歷航跡規(guī)劃IGWO算法比GWO算法規(guī)劃路徑縮短4．17%，可見，IGWO算法對于大任務(wù)量作業(yè)任務(wù)更具優(yōu)越性。除此之外，徐博等[18]在植保無人機(jī)航跡規(guī)劃中有深入研究，為了降低無人機(jī)總能耗，提出了一種多架次往復(fù)遍歷式植保無人機(jī)的作業(yè)路徑。又針對多作業(yè)區(qū)域運(yùn)用改進(jìn)二進(jìn)制編碼的遺傳算法與TSP模型結(jié)合進(jìn)行了多作業(yè)區(qū)域植保無人機(jī)航線全局規(guī)劃[19]，對無人機(jī)植保作業(yè)航跡規(guī)劃均有一定的成效，但并未考慮無人機(jī)低空作業(yè)的障礙物碰撞問題。本研究在無人機(jī)航跡規(guī)劃的同時，進(jìn)行低空障礙物避障路徑優(yōu)化，以更加適應(yīng)低空任務(wù)場景的需求。

綜上所述，IGWO算法與A*算法相結(jié)合的無人機(jī)農(nóng)田噴灑航跡規(guī)劃策略，不但可以增強(qiáng)模型的求解能力，縮短航跡規(guī)劃長度；而且充分考慮了低空作業(yè)時障礙物區(qū)域避障問題，可以二次航跡路徑修正以避免碰撞，有利于無人機(jī)農(nóng)田噴灑作業(yè)的實(shí)施。本研究并未考慮作業(yè)任務(wù)點(diǎn)是如何確定的，如若加入機(jī)器視覺與深度學(xué)習(xí)識別過程且樣本量足夠大時，可以實(shí)現(xiàn)噴灑點(diǎn)（如蟲害區(qū)域、雜草區(qū)域等）的自動提取與分類[20-21]，可以提升無人機(jī)農(nóng)田噴灑作業(yè)系統(tǒng)的自主性，促進(jìn)智慧農(nóng)業(yè)的發(fā)展。