結合混合粒子群算法的植保無人機航線設計方法

徐利鋒，楊中柱，黃祖勝，丁維龍

(浙江工業大學 計算機科學與技術學院，杭州 310023)

E-mail：lfxu@zjut.edu.cn

1 引 言

隨著通信技術、自動控制技術、傳感技術以及人工智能的發展，無人機的功能越來越完善，如何提高無人機的工作效率以及降低無人機的能耗成為了植保無人機領域的研究熱點[1，2].無人機航線規劃指的是在指定的約束條件下，根據工作目的來設計出一條無人機飛行路徑，飛行路徑的優劣程度根據具體的工作目的來確定.在軍事應用領域，軍用無人機能夠執行偵查預警、中繼通信、戰場搜救、跟蹤定位等多種任務，設計出更優的無人機飛行路徑能夠有效的躲避雷達偵測并提高任務成功率[3，4].在民事應用方面，無人機得到了非常廣泛的應用[5].例如在物流行業中用無人機來進行自主配送，能夠有效降低物流運輸的人工成本，根據配送點的位置信息設計出較好的無人機航線能夠有效的提高物流運輸效率.在農業領域，用植保無人機進行噴霧作業具有效率高、速度快等優點，并且無人機能夠在沒有跑道的小型區域內垂直起降，能夠很方便的在各種地形上進行噴灑作業[6-8].

目前大多數植保無人機需要工作人員用遙控來手動操作，這種方式過分依賴于操作人員的技術，在實際應用中并不能獲得很好的效果[9-11].通過遙控駕駛方式來控制無人機的移動會對操作人員產生較大的負荷，并且遙控駕駛方式對于時間延遲以及飛行控制等方面具有較高的要求[12].彭孝東等[13]基于GPS坐標采集無限傳輸系統，通過手動操作的方式進行了無人機噴灑試驗，結果表明人工操作的無人機飛行路徑與理論設計的無人機航線偏離嚴重，通過手動操作的方式無人機很難做到精準作業.隨著衛星定位技術的發展，以GPS(Global Positioning System，全球定位系統)導航為主并且能夠根據目標區域自動生成無人機作業航線的自主飛行作業模式成為了目前植保無人機的主要發展趨勢，對于無人機航線設計的研究顯得尤為必要.

植保無人機航線設計屬于全覆蓋路徑規劃的范疇，根據航線設計的時間點將全覆蓋航線規劃算法分為兩種[14]：1)根據已有的環境信息包括目標區域形狀、大小以及區域內部障礙物的分布情況等，在無人機起飛前設計出一條無人機飛行航線，讓無人機沿著設計出的航線飛行，這種方法稱為離線式航線規劃方法；2)另外一種是在無人機飛行過程中，通過傳感器來對目標區域實時掃描，根據掃描結果來實時計算無人機飛行路徑，這種方法稱為在線式航線規劃方法.徐博等[15,16]針對植保施藥多個作業區域的情況，提出了一種基于遺傳算法的植保無人機航線設計方法，將航線長度、多余覆蓋以及重復覆蓋作為評價無人機航線優劣的標準；另外其針對不規則區域提出了一種基于作業方向的不規則區域作業航線規劃算法，該算法可以根據指定的作業方向快速規劃出無人機作業航線.在植保無人機實際作業過程中，受到目標作業區域過大、無人機載藥量和續航時間有限等因素的影響，無人機需要多次返航才能完成對目標區域的噴灑作業，針對該實際情況，王宇等[17，18]提出了一種基于柵格法和引力搜索算法的植保無人機路徑規劃方法，將無人機作業所耗費的時間作為評價路徑優劣的標準，實現了對返航點數量及位置的尋優.Gabriely[19]提出了一種基于生成樹(Spanning Tree Coverage，STC)的在線式航線規劃算法Spiral-STC，通過傳感器獲取周邊環境信息并生成局部地圖，通過對局部地圖進行柵格劃分來獲得有效柵格以及障礙柵格.該方法能夠保證所有有效柵格均被覆蓋，并且不存在重復覆蓋的情況，但是由于設計出的航線轉彎次數過多而導致增大了能耗成本，另外由于柵格劃分的不精確導致出現了遺漏覆蓋的情況.Gonzalez[20]等提出了一種改進的Spiral-STC算法，在原始的Spiral-STC算法基礎上增加了外環航線，能夠有效地提高航線的覆蓋率，Choi[21]在此基礎上加入了新的地圖坐標分配方法，通過分析傳感器的歷史坐標數據進行分析進而重新分配坐標，能夠有效地降低航線的轉彎次數.

在作業區域中，由于地形、輸電設備以及其余人為因素的限制，形成了障礙區域.單元分解法[22]是含障礙區域航線設計方法中的一種常用方法，其基本思想是對含障礙區域進行分解，將其分解為多個不含障礙的子區域，然后設計出合理的子區域連接順序，每個子區域內部用牛耕法[23]來完成.梯形分解法[24]是一種典型的單元分解法，其基本思想如下：用一條虛擬的掃描線對工作區域進行掃描，掃描線與工作區域內部的障礙物存在著相離、相切、相交三種狀態，根據掃描線以及障礙物的邊界，將工作區域分解為多個子區域，并且每個子區域都是梯形.在梯形分解法中將工作區域分解為子區域時，是用一條掃描線對工作區域進行掃描，掃描線的方向沒有改變，因此該算法具有一定的局限性.Huang等[25]針對該問題提出了一種能夠讓掃描線的方向進行變化的線掃分割法(Line-sweep Decomposition)，在掃描工作區域時對每個子區域使用不同方向的掃描線，最后通過最小高度和(MSA，Minimal Sum of Altitudes)來將掃描后的子區域合并，減少子區域數量.基于上述方法所設計出的無人機航線，往往存在著轉彎次數過多的問題，不僅增加了無人機作業的能耗，而且降低了無人機作業的效率.

本文以減少無人機航線轉彎次數、提高無人機作業效率為目的，針對含障礙工作區域進行了無人機航線規劃方法研究，提出了一種新的植保無人機航線規劃算法.基于柵格法來對目標區域進行路徑點采樣，用路徑點來表示目標區域的特征信息，并結合混合粒子群算法來對路徑點進行排序，用路徑點的排列來表示無人機飛行路徑，設計出一條能夠有效規避障礙物并對工作區域完成全覆蓋的航線.

2 路徑點采樣

柵格法[26]是一種常用的描述環境信息的方法，柵格法將目標區域用多個正方形網格單元來表示，每個網格單元具有一個屬性值來表示該網格單元內是否包含障礙物，不包含障礙物的網格稱為有效網格，包含障礙物的網格稱為無效網格.在對環境地圖進行網格化時，若網格單元過大，那么可能出現某個網格內只存在一小塊障礙區域而導致該網格被標記為無效網格，劃分后的網格對環境信息描述的準確度較低.對于在線式航線規劃方法，柵格劃分精度過低會將非障礙區域標記為障礙區域，而柵格劃分精度過高會增大計算量，由于在線式航線規劃方法對于實時性的要求較高，因此柵格劃分精度不能過高.而在離線式航線規劃方法中主要是在環境信息已知的條件下對有效網格進行排序，并且在無人機工作前進行航線設計，通過計算機進行處理計算能夠有效的解決因柵格法劃分精度過高所帶來的計算成本增加的問題.本文對于無人機航線規劃研究屬于離線式，在離線式航線規劃方法中柵格劃分精度越高越好，若柵格單元的邊長小于無人機噴幅寬度，那么無人機按照設計出的航線進行噴霧作業時會出現重復覆蓋的情況，因此在本次研究中我們將網格單元的邊長設置為無人機的噴幅寬度.

如圖1所示，用柵格法來表示環境信息時，繪制出目標區域邊界的最小外接矩形，并將矩形的長和寬調整為柵格邊長的整數倍.包含作業區域同時不包含障礙區域的柵格稱為有效柵格，不包含作業區域也不包含障礙區域的柵格稱為無效柵格，包含障礙區域的柵格稱為障礙柵格，其中障礙柵格也屬于無效柵格.在設計無人機航線時按照一定的順序連接所有有效柵格，讓航線避開無效柵格，完成對整個工作區域的覆蓋.

圖1 柵格化示意圖Fig.1 Schematic illustration of gridding

用柵格法來表示環境信息時，部分柵格中同時包含工作區域以及障礙區域，或者同時包含了工作區域以及工作區域邊界外部區域，在柵格法中將這些柵格全部設置為無效柵格，進行航線規劃時無人機航線并不經過這些柵格，降低了無人機航線的覆蓋率.

圖2 路徑點采樣示意圖Fig.2 Schematic illustration of path point sampling

如圖2所示，本文用路徑點來代替柵格，對工作區域進行柵格化后，在每個柵格單元的中心點設置一個路徑點，并將包含在障礙物邊界內部的路徑點以及工作區域邊界外部的路徑點設置為無效路徑點，包含在工作區域邊界內部以及障礙物邊界外部的路徑點設置為有效路徑點.無人機飛行路徑可以用路徑點的排列順序來表示，將無人機航線規劃轉化為對路徑點的排序.

3 基于混合粒子群算法的路徑點自動排序算法

組合優化問題[27](Combinatorial Optimization Problem，COP)指的是在給定的約束條件下，根據預期目的從目標問題的可行解集中尋找最優解的問題，路徑點的排列問題也是一種組合優化問題.在目標問題的規模較小時可以用窮舉法來獲取目標問題的最優解，但是隨著問題規模的擴大，算法運行所消耗的時間也在不斷增加，出現了組合爆炸問題.啟發式優化算法的出現為解決組合優化問題提供了一種新的思路，能夠有效解決組合爆炸問題.

3.1 混合粒子群算法

粒子群優化算法(Particle Swarm Optimization，PSO)是一種仿生智能優化算法，PSO模擬了自然界中鳥群的覓食過程[28].在鳥群尋找食物的過程中存在著分散搜尋以及群體搜尋兩種情況，分散搜尋指的是鳥群中的單個個體沿著不同的方向去尋找食物，當某個個體尋找到食物的位置時會向整個群體中的其余個體傳遞食物位置信息，然后整個群體會朝向食物位置移動.研究表明在自然界生物的覓食過程中，個體之間互相學習的種群能夠比個體之間相互競爭的種群更加快速地尋找到食物[29].在粒子群優化算法中，種群中的每個粒子表示優化問題的可行解，而食物位置代表著該優化問題的最優解.整個種群為了找到食物位置而不斷在解空間中進行探索，在探索過程中所有個體通過自身的尋找經驗以及種群中其余個體的尋找經驗來不斷移動.在算法優化過程中，單個粒子通過自身的歷史最優值(pbest)以及種群歷史最優值(gbest)來調整粒子的位置以及速度，根據實際的優化問題來確定適應度函數并且通過適應度函數來判定最優值.粒子的更新公式如下：

xi(t+1)=xi(t)+vi(t+1)

(1)

vi(t+1)=ωvi(t)+c1r1(pbesti(t)-xi(t))+
c2r2(gbest(t)-xi(t))

(2)

r1和r2是隨機數，其取值范圍為[0，1].c1和c2為學習因子，c1表示該個體向其自身歷史最優值的學習能力，c2表示該個體向種群歷史最優值的學習能力，c1和c2的取值范圍為[0，2].這里ω為慣性權重因子，慣性權重表示粒子的速度受到粒子慣性的影響程度.

粒子群算法使用粒子的個體信息、個體歷史最優值以及種群歷史最優值來對粒子的屬性進行更新.對于本文所描述的路徑點排列優化問題，粒子的位置表示一條路徑，而粒子的速度難以表示，因此本文使用混合粒子群算法[30]來對目標優化問題進行求解.式(2)中的ωvi(t)項視為遺傳算法中的變異操作，c1r1(pbesti(t)-xi(t))項視為當前個體與個體歷史最優值進行交叉操作，c2r2(gbest(t)-xi(t))視為當前個體與種群歷史最優值進行交叉操作.對當前個體進行變異操作以及交叉操作后，得到新個體的適應度值可能會低于原有個體的適應度值，若新個體優于原有個體，那么接受新個體，否則舍棄.

3.2 變異操作和交叉操作

假設有效路徑點總數為n，由路徑C1變異到路徑C2，常用的變異策略有以下幾種：

1)在路徑C1={P1，…，Pi-1，Pi，Pi+1，…，Pj-1，Pj，Pj+1，…，Pn}中隨機選擇兩個路徑點Pi和Pj，在路徑C1中交換Pi和Pj，得到的新路徑即為C2={P1，…，Pi-1，Pj，Pi+1，…，Pj-1，Pi，Pj+1，…，Pn}.

2)在路徑C1={ P1，…，Pi-1，Pi，Pi+1，…，Pj-1，Pj，Pj+1，…，Pn}中隨機選擇一段子路徑C0={ Pi，Pi+1，…，Pj-1，Pj}，將C0反轉并插入原有位置，得到的新路徑即為C2={P1，…，Pi-1，Pj，Pj-1，…，Pi+1，Pi，Pj+1，…，Pn}.

3)在路徑C1={P1，…，Pi-1，Pi，Pi+1，…，Pn}隨機選擇一個路徑點Pi，交換Pi和Pi+1，得到的新路徑即為C2={P1，…，Pi-1，Pi+1，Pi，…，Pn}.

在無人機航線規劃問題中，無人機航線需要覆蓋整個工作區域，并且需要盡量減少對工作區域的重復覆蓋.結合實際優化問題，本文提出了一種新的變異策略，具體步驟如下：

Step1.對于路徑C={P1，...，Pi-1，Pi，Pi+1，...，Pn}，隨機選擇一個路徑點Pi，若點Pi與點Pi+1在工作區域中為不相鄰的兩個路徑點，那么進入Step 2，否則重復Step 1；

Step2.在剩余路徑點集合C-{Pi}中隨機選擇一個點Pj，若點Pj與點Pj+1在工作區域中為不相鄰的兩個路徑點，那么進入Step 3，否則重復Step 2；

Step3.在路徑C中交換點Pi和點Pj，得到的新路徑即為變異后的路徑.

對于兩條路徑C1和C2，常用的交叉方法有以下幾種：

1)在C2中隨機選擇一條局部路徑C0，將C1中與C0相同的路徑點刪除，然后將C0添加到C1末尾，得到的新路徑即為交叉路徑.

2)在C2中隨機選擇一條局部路徑C0，將C0添加到C1中的對應位置并將C1中與C0重復的路徑點刪除，得到的新路徑即為交叉路徑.

3)在C2中隨機選擇一條局部路徑C0，將C0隨機添加到C1中的任意位置并將C1中與C0重復的路徑點刪除，得到的新路徑即為交叉路徑.

3.3 路徑點排序優化算法

在文獻[25]中提出了無人機在轉彎時會經歷“減速-轉彎-加速”過程，與直線飛行相比，轉彎過程會帶來更大的能量消耗，因此無人機航線的轉彎次數越少越好，本文將無人機航線轉彎次數作為評價無人機航線優劣的標準.算法的適應度函數如下：

(3)

C表示任意一條路徑，T為該路徑的轉彎次數.

算法具體步驟如下：

1)初始化.假設有效路徑點總數為n，那么初始路徑用1-n的隨機排列表示，粒子的位置代表一條路徑.根據指定的種群大小m初始化種群，獲得m條初始路徑(C1，C2，…，Cm).

2)計算種群最優值以及每個粒子的個體歷史最優值.根據適應度函數計算出所有粒子的適應度值，將適應度值最大的粒子所表示的路徑設置為種群最優值Cpbest，初始時刻第i個粒子的個體歷史最優值Cgbesti與其初始值Ci相同.

6)終止.若算法未達到最大迭代次數，那么返回第3步繼續運行.若算法達到最大迭代次數，那么算法停止，輸出最優路徑Cpbest.

4 仿真實驗

本次仿真實驗環境為Windows10操作系統，編程語言使用Java程序設計語言，硬件平臺為Intel(R) Core(TM) i7-6700HQ @ 2.60 GHz，內存為16 GB.

本次實驗在單障礙工作區域以及多障礙工作區域內進行了無人機航線設計，并與文獻[31]中提出的基于Reeb圖的歐拉回路航線設計方法進行了對比，文獻[31]基于牛耕單元分解法對含障礙工作區域進行了子區域劃分，用Reeb圖來表示子區域，將子區域銜接問題轉化為Reeb圖邊的遍歷問題，通過匈牙利0-1指派法實現了Reeb圖奇度節點的最小權匹配，并基于改進的Fleury歐拉回路算法來確定最佳的子區域銜接順序，最終實現對含障礙作業區域的無人機航線規劃.

4.1 單障礙工作區域航線設計

本研究在實驗中設計了三個不同位點(位點1、2、3)的單障礙，并運用前述算法進行工作區域航線設計.

圖3 單障礙(位點1)工作區域無人機航線設計結果Fig.3 Result of UAV route planning on target area with single barrier(position No.1)

如圖3所示，對于一塊80 m*80 m的工作區域，邊界頂點坐標分別為(0，0)，(80，0)，(80，80)，(0，80)，其內部存在一塊不規則的凹多邊形障礙物區域，障礙物邊界各個頂點坐標分別為(4.5，23)，(7，16.5)，(13，15.5)，(18，10)，(24.5，11.5)，(24，22.5)，(13.5，24.5)，設定無人機噴幅寬度為5 m，最終航線設計結果如圖3(a)所示.從圖中可以看出按照本文所提出的方法設計出的無人機航線避開了工作區域內部的障礙物，并且航線不存在交叉的情況，說明無人機按照該航線進行噴霧作業時沒有出現重復覆蓋的現象，航線轉彎次數為36次.在相同條件下采用文獻[31]中提出的方法所得到的無人機航線如圖3(b)所示，航線轉彎次數為60次，可以看出本文所提出的方法能夠設計出一條轉彎次數更少的無人機航線.

圖4 單障礙(位點2)工作區域無人機航線設計結果Fig.4 Result of UAV route planning on target area with single barrier(position No.2)

如圖4所示，工作區域大小為80m*80m，障礙物頂點坐標分別為(10，50)，(6，49)，(4.5，41.5)，(7，31.5)，(11，30)，(16.5，33)，(14.5，48)，無人機噴幅寬度為5m，航線規劃結果如圖4(a)所示，航線轉彎次數為34次.在相同條件下采用文獻[31]中提出的方法所得到的無人機航線如圖4(b)所示，航線轉彎次數為60次.

圖5 單障礙(位點3)工作區域無人機航線設計結果Fig.5 Result of UAV route planning on target area with single barrier(position No.3)

如圖5所示，工作區域大小為80m*80m，障礙物頂點坐標分別為(37，46)，(33.5，33.5)，(56，34)，(53，46)，無人機噴幅寬度為5m，航線規劃結果如圖5(a)所示，航線轉彎次數為27次.在相同條件下采用文獻[31]中提出的方法所得到的無人機航線如圖5(b)所示，航線轉彎次數為60次.

圖6 包含兩塊障礙物的工作區域航線設計結果Fig.6 Result of UAV route planning on target area with two barriers

4.2 多障礙工作區域航線設計

實驗中模擬了包含多個障礙物的工作區域，如圖6所示，工作區域大小為80m*80m，其內部存在兩塊不規則的凸多邊形障礙物區域，左下角障礙物頂點坐標分別為(10，30)，(5，28)，(7，12)，(14，8)，(16，13)，(12，20)，(14，28)，右上角障礙物頂點坐標分別為(54，66)，(58，54)，(73，56)，(76，64)，航線規劃結果如圖6(a)所示.當目標工作區域內部存在多塊障礙物時，本文提出的方法仍然能夠設計出一條規避所有障礙物的航線，并且保證了無人機按照指定航線進行作業時不會出現重復覆蓋現象，航線轉彎次數為39次.在相同條件下采用文獻[31]中提出的方法所得到的無人機航線如圖6(b)所示，航線轉彎次數為42次.

如圖7所示，圖中的目標區域中在圖6所示的工作區域的基礎上添加了一塊新的障礙物，圖中共有三塊障礙物，新加的障礙物頂點坐標分別為(54.5，21)，(57.5，15)，(53.5，9)，(66，11)，(64，18)，航線規劃結果如圖7(a)所示.圖7(a)中的航線繞開了新增加的障礙物，航線轉彎次數為46次.在相同條件下采用文獻[31]中提出的方法所得到的無人機航線如圖7(b)所示，航線轉彎次數為88次.

圖 7 包含三塊障礙物的工作區域航線設計結果Fig.7 Result of UAV route planning on target area with three barriers

如圖8所示，工作區域大小為80m*80m，其內部存在兩塊不規則的凸多邊形障礙物區域，左下角障礙物頂點坐標分別為(5，70)，(6，55)，(14，55)，(15，68)，上方障礙物頂點坐標分別為(64，46)，(66，31)，(74，31)，(75，45)，航線規劃結果如圖8(a)所示，轉彎次數為44次.在相同條件下采用文獻[31]中提出的方法所得到的無人機航線如圖8(b)所示，航線轉彎次數為90次.

圖8 包含兩塊障礙物的工作區域航線設計結果Fig.8 Result of UAV route planning on target area with two barriers

在本次仿真實驗中，設計了多種不同的工作區域，包括含單個障礙物的工作區域以及包含多個障礙物的工作區域，每個工作區域內部障礙物的大小、形狀以及位置均不相同.應用本文所提出的植保無人機航線設計算法，在多種不同的工作區域內均能設計出一條對目標區域完成全覆蓋的無人機航線.對比以上所有實驗結果，可以發現與文獻[31]提出的含障礙區域無人機航線規劃方法相比，本文所提出的方法設計出的無人機航線的轉彎次數大幅降低，實驗結果表明對于含障礙物的工作區域本文所提出的方法能夠設計出更優的無人機航線.

5 結論與展望

本文提出了一種針對含障礙工作區域的植保無人機航線設計方法，基于柵格法對目標工作區域進行路徑點采樣，獲得所有有效路徑點，并結合混合粒子群算法來對路徑點進行排序，設計出一條能夠有效規避障礙物并對工作區域完成全覆蓋的航線.實驗結果表明本文提出的無人機航線設計方法能夠應用在多種含障礙工作區域內，目標區域包含單個或者多個障礙物時均能獲得良好的效果，能夠有效減少無人機航線的轉彎次數，降低無人機飛行時的能耗.

本文提出的植保無人機航線設計方法適用于平原等地面高度變化較小的地區，設計無人機航線時在二維環境地圖中進行.在未來的研究工作中，考慮到部分地面高度變化較大的工作環境，需要在三維空間中進行無人機航線設計.在進行無人機航線設計時沒有考慮航線終點的問題，根據本文所提出的無人機航線規劃方法所設計出的無人機飛行路徑，其終點在工作區域中心部位，無人機在完成作業后需要返航，仍然會增加無人機的耗能，在未來的研究工作中需要考慮到航線起點和終點的問題，減少無人機停止作業后返航所來帶的能量消耗.考慮到無人機定位控制精度的問題以及自然環境中風的作用，無人機實際飛行路線與理論規劃路徑之間存在一定的偏移，影響了無人機作業結果，在后續的研究工作中需要對上述因素進行詳細分析，進一步完善無人機航線設計方法.