結(jié)合混合粒子群算法的植保無人機(jī)航線設(shè)計方法

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

(浙江工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)

E-mail：lfxu@zjut.edu.cn

1 引 言

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

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

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

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

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

2 路徑點采樣

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

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

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

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

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

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

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

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

3.1 混合粒子群算法

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

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是隨機(jī)數(shù)，其取值范圍為[0，1].c1和c2為學(xué)習(xí)因子，c1表示該個體向其自身歷史最優(yōu)值的學(xué)習(xí)能力，c2表示該個體向種群歷史最優(yōu)值的學(xué)習(xí)能力，c1和c2的取值范圍為[0，2].這里ω為慣性權(quán)重因子，慣性權(quán)重表示粒子的速度受到粒子慣性的影響程度.

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

3.2 變異操作和交叉操作

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

1)在路徑C1={P1，…，Pi-1，Pi，Pi+1，…，Pj-1，Pj，Pj+1，…，Pn}中隨機(jī)選擇兩個路徑點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}中隨機(jī)選擇一段子路徑C0={ Pi，Pi+1，…，Pj-1，Pj}，將C0反轉(zhuǎn)并插入原有位置，得到的新路徑即為C2={P1，…，Pi-1，Pj，Pj-1，…，Pi+1，Pi，Pj+1，…，Pn}.

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

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

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

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

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

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

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

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

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

3.3 路徑點排序優(yōu)化算法

在文獻(xiàn)[25]中提出了無人機(jī)在轉(zhuǎn)彎時會經(jīng)歷“減速-轉(zhuǎn)彎-加速”過程，與直線飛行相比，轉(zhuǎn)彎過程會帶來更大的能量消耗，因此無人機(jī)航線的轉(zhuǎn)彎次數(shù)越少越好，本文將無人機(jī)航線轉(zhuǎn)彎次數(shù)作為評價無人機(jī)航線優(yōu)劣的標(biāo)準(zhǔn).算法的適應(yīng)度函數(shù)如下：

(3)

C表示任意一條路徑，T為該路徑的轉(zhuǎn)彎次數(shù).

算法具體步驟如下：

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

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

6)終止.若算法未達(dá)到最大迭代次數(shù)，那么返回第3步繼續(xù)運(yùn)行.若算法達(dá)到最大迭代次數(shù)，那么算法停止，輸出最優(yōu)路徑Cpbest.

4 仿真實驗

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

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

4.1 單障礙工作區(qū)域航線設(shè)計

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

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

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

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

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

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

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

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

4.2 多障礙工作區(qū)域航線設(shè)計

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

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

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

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

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

在本次仿真實驗中，設(shè)計了多種不同的工作區(qū)域，包括含單個障礙物的工作區(qū)域以及包含多個障礙物的工作區(qū)域，每個工作區(qū)域內(nèi)部障礙物的大小、形狀以及位置均不相同.應(yīng)用本文所提出的植保無人機(jī)航線設(shè)計算法，在多種不同的工作區(qū)域內(nèi)均能設(shè)計出一條對目標(biāo)區(qū)域完成全覆蓋的無人機(jī)航線.對比以上所有實驗結(jié)果，可以發(fā)現(xiàn)與文獻(xiàn)[31]提出的含障礙區(qū)域無人機(jī)航線規(guī)劃方法相比，本文所提出的方法設(shè)計出的無人機(jī)航線的轉(zhuǎn)彎次數(shù)大幅降低，實驗結(jié)果表明對于含障礙物的工作區(qū)域本文所提出的方法能夠設(shè)計出更優(yōu)的無人機(jī)航線.

5 結(jié)論與展望

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

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