胡馨丹，楊盛毅，朱 力，宋云云

(1.貴州民族大學(xué)數(shù)據(jù)科學(xué)與信息工程學(xué)院，貴州 貴陽 550025；2.貴州省模式識別與智能系統(tǒng)重點實驗室，貴州 貴陽 550025；3.貴州民族大學(xué)機械電子工程學(xué)院，貴州 貴陽 550025)

0 引言

針對無人機(unmanned aerial vehicle ，UAV)具有操作簡便、體積小和機動性高[1]等特點，基于無人機的農(nóng)業(yè)噴藥必將成為一項重要的新技術(shù)，為作物防護產(chǎn)品提供高效、有效的應(yīng)用[2]。無人機技術(shù)已被廣泛用于不同的精準農(nóng)業(yè)(PA)領(lǐng)域，如噴灑[3]、遙感監(jiān)測[4]和作物生長檢測[5]等。在農(nóng)村農(nóng)業(yè)的發(fā)展中，無人機技術(shù)更多的是應(yīng)用于植保作業(yè)方面。對于農(nóng)民來說，在農(nóng)業(yè)生產(chǎn)經(jīng)營中，需要考慮成本收益最大化。也即是在農(nóng)田噴灑作業(yè)時，需要盡量減少漏噴、多噴，以及噴灑不均勻的問題。對于區(qū)域中含有不規(guī)則的障礙物的覆蓋路徑規(guī)劃，文獻[6]提出一種基于A*的覆蓋路徑規(guī)劃算法，但重復(fù)率較高，轉(zhuǎn)彎次數(shù)比較多。因此，本文提出一種基于障礙物分區(qū)的A*覆蓋路徑規(guī)劃方法。

1 覆蓋路徑規(guī)劃方法設(shè)計

為確保農(nóng)用無人機能夠在避開障礙物的同時，還能完成區(qū)域的藥物噴灑。首先以農(nóng)田環(huán)境信息為輸入，以作業(yè)路徑長度、轉(zhuǎn)彎次數(shù)和重復(fù)點數(shù)為輸出，整體的算法流程如圖1所示。

圖1 含障礙區(qū)域全覆蓋路徑規(guī)劃流程

根據(jù)實際的作業(yè)環(huán)境，人工手持GPS打點，獲得作業(yè)區(qū)域頂點坐標，以及障礙物頂點坐標，然后用黑色填充障礙物，白色填充無障礙區(qū)域。對于障礙物所占單元格不足一半的，視為無障礙單元，所占單元格超過一半的，視為障礙單元，從而得到作業(yè)環(huán)境柵格地圖。在柵格地圖中，用0表示無障礙單元，1表示障礙單元。對于存在有障礙物的作業(yè)區(qū)域，本文將進行區(qū)域分解。比較常用的方法有單元分解[7]、矩形分解[8]和聚類分解[9]。本文選用聚類分解進行區(qū)域劃分。

2 柵格區(qū)域劃分算法

對于柵格地圖，為了便于遍歷整個單元，且能避開障礙物，最有效的方法就是沿著障礙物邊界進行劃分，從而將整個地圖劃分為多個子區(qū)域。區(qū)域劃分流程如圖2所示。

2.1 模糊C均值聚類算法

模糊C均值(fuzzyC-means，F(xiàn)CM)是根據(jù)隸屬度原則最大，從而判定每個數(shù)據(jù)點歸屬于某個聚類中心的一種聚類算法[10]。本文利用FCM聚類算法將柵格障礙物進行分類，然后找到每類障礙物x軸和y軸的最大值xmax、ymax和最小值xmin、ymin。

2.2 Bresenham算法

Bresenham算法是計算機圖形學(xué)領(lǐng)域使用最廣泛的直線掃描轉(zhuǎn)換算法[11]。本文利用Bresenham算法得到分割線，如果障礙物中有多個最小值xmin的點，則找出其對應(yīng)點的最小值ymin。如果障礙物中有多個最大值xmax的點，則找出其對應(yīng)點的最大值ymax。從而得到柵格區(qū)域劃分結(jié)果，如圖3a所示，其中黑色虛線表示分割線。

根據(jù)圖3a的分解結(jié)果，將區(qū)域分為9個子區(qū)域。然后按照從上到下，從左到右的順序，將區(qū)域進行編號，為了后續(xù)處理節(jié)點間的訪問順序，以子區(qū)域中心點為該區(qū)域節(jié)點。

根據(jù)每個區(qū)域的最小和最大的橫縱坐標值，求取每個區(qū)域的中心點Mi(xmi,ymi)，計算式為

(1)

xmaxi、xmini分別為第i個區(qū)域橫坐標的最大值和最小值；ymaxi、ymini分別為第i個區(qū)域縱坐標的最大值和最小值；n為區(qū)域的個數(shù)。得到每個子區(qū)域中心點分布如圖3a所示(黑色實心序號部分)。

圖3 柵格分區(qū)

2.3 子區(qū)域合并

考慮子區(qū)域間存在一定的相似性，為了減少尋找各區(qū)域起始點的過程，使其能夠進行區(qū)域間的連續(xù)噴灑作業(yè)，首先從左到右將相鄰子區(qū)域?qū)挾认嗤膮^(qū)域合并在一起，對于圖3a，可以將2、3、4、5和6這5個區(qū)域合并為新的區(qū)域，區(qū)域?qū)挾炔煌模瑒t各為單獨的區(qū)域。對于剩余單獨區(qū)域，則按照子區(qū)域間的中心節(jié)點距離，滿足小于某一閾值ε，再進行合并，本文設(shè)置ε=8，從而最終將區(qū)域分為3個子區(qū)域如圖3b所示。本文將起始區(qū)域的起始點位于區(qū)域的左上角。

2.4 子區(qū)域覆蓋路徑順序

子區(qū)域進行區(qū)域合并后，為了高效率實現(xiàn)農(nóng)用無人機對噴灑區(qū)域進行覆蓋，則每個子區(qū)域的覆蓋只能遍歷1次，因此將每個子區(qū)域視為1個節(jié)點，將節(jié)點連接成1條線，且只能經(jīng)過1個節(jié)點，而且相連的2個節(jié)點還必須是相鄰關(guān)系，由此將其轉(zhuǎn)化成求解旅行商問題，所求的最短路徑就是子區(qū)域間的遍歷順序。通過圖3b發(fā)現(xiàn)子區(qū)域間是相鄰的，因此可以直接對子區(qū)域進行自上而下的遍歷順序。

2.5 子區(qū)域間起點與終點的連接

以圖3b為例，針對這3個矩形區(qū)域，每個矩形區(qū)域都有4個柵格單元，記為Mij(i=1,…,c，j=1,2,3,4)，其中，c為子區(qū)域個數(shù)，4個柵格單元從左上角開始順時針排序得到4個單元的坐標點分別為Mi1(xmini1,ymini1)、Mi2(xmaxi2,ymini2)、Mi3(xmaxi3,ymaxi3)和Mi4(xmini4,ymaxi4)，如圖4所示。

圖4 矩形4個柵格單元示意圖

由子區(qū)域的訪問順序，以區(qū)域的左上角坐標為進入點，考慮到覆蓋路徑長度以及重復(fù)率，則根據(jù)掃描方向，則每個子區(qū)域的進入點與出口點可分為：

a.如果子區(qū)域無障礙物，則農(nóng)用無人機沿最長邊方向作業(yè)，根據(jù)式(2)可得4個坐標點的關(guān)系。

(2)

b.如果子區(qū)域內(nèi)部含有障礙物，則農(nóng)用無人機沿最短邊方向作業(yè)，根據(jù)式(3)可得4個坐標點的關(guān)系。

(3)

“?”的兩側(cè)為對應(yīng)關(guān)系。

如果子區(qū)域進入點為左上角Mi1，當(dāng)該子區(qū)域噴灑作業(yè)完成，出入點為Mi4，則下一個子區(qū)域的起點根據(jù)上面的2種情形可以直接得到為Mi+1,1。而子區(qū)域的連接有2種情況：

a.當(dāng)下一子區(qū)域的進入點與Mi4無障礙，則當(dāng)該子區(qū)域噴灑作業(yè)完成后，農(nóng)用無人機直接直線移動1格到下一區(qū)域的進入點有2種情況,如果長邊長度或短邊長度為偶數(shù)，則進入點為Mi+1,1；如果長邊長度或短邊長度為奇數(shù)，則進入點為Mi+1,3。

b.當(dāng)下一子區(qū)域的進入點與Mi4有障礙，即是農(nóng)用無人機進入死區(qū)如圖5所示。當(dāng)前子區(qū)域完成作業(yè)后，下一區(qū)域的進入點為Mi+1,2，則2點之間的最優(yōu)運動軌跡用A*算法求得。

圖5 農(nóng)用無人機進入死區(qū)

3 作業(yè)區(qū)域仿真實驗分析

在MATLAB平臺上，本文建立的柵格地圖尺寸為15×18，農(nóng)用無人機起始坐標為(1,1)，分別用本文方法、傳統(tǒng)的A*覆蓋算法和傳統(tǒng)的遺傳算法，進行仿真實驗，仿真結(jié)果如圖6所示。圖6中的灰色柵格表示重復(fù)噴灑節(jié)點，黑色加粗線條為無人機飛行覆蓋路徑。根據(jù)3種方法進行仿真實驗，得到的覆蓋效率統(tǒng)計如表1所示。

圖6 柵格環(huán)境3種方法覆蓋路徑比較

表1 覆蓋路徑規(guī)劃方法比較

從覆蓋路徑長度來看，本文方法所得的覆蓋路徑是最優(yōu)的，重復(fù)點數(shù)也是最少的，轉(zhuǎn)彎次數(shù)雖然不是最優(yōu)解，但也是次優(yōu)解；從程序運行時間來看，本文方法是運行時間最少的，其次是A*算法，傳統(tǒng)的遺傳算法運行時間比較長，且A*算法還存在漏噴的問題，無法實現(xiàn)完全的覆蓋。綜合來看，本文方法與傳統(tǒng)的A*覆蓋算法和遺傳覆蓋算法相比，覆蓋路徑長度分別減少13.97%和3.78%，重復(fù)率分別降低了94.44%和83.33%，轉(zhuǎn)彎次數(shù)分別減少16.00%和增加1.61%?？梢姳疚姆椒ㄓ休^優(yōu)的性能，能夠減少藥物的損失和縮短電池能量的消耗。

4 結(jié)束語

針對傳統(tǒng)的A*覆蓋算法出現(xiàn)重復(fù)率高轉(zhuǎn)彎次數(shù)多的問題，本文提出將FCM聚類算法與Bresenham算法相結(jié)合對含有多個障礙物的區(qū)域進行分區(qū)，然后按照從上到下的順序遍歷子區(qū)域。并分析子區(qū)域間出入點的連接問題，運用A*算法獲得最優(yōu)的連接路徑。設(shè)計仿真實驗，驗證了算法的可行性。