基于Grid-GSA算法的植保無人機路徑規劃方法

王 宇 陳海濤 李 煜 李海川

(東北農業大學工程學院，哈爾濱150030)

基于Grid-GSA算法的植保無人機路徑規劃方法

王 宇 陳海濤 李 煜 李海川

(東北農業大學工程學院，哈爾濱150030)

為了提高植保無人機的作業效率，研究了一種路徑規劃方法。運用柵格法構建環境模型，根據實際的作業區域規模、形狀等環境信息和無人機航向，為相應柵格賦予概率，無人機優先選擇概率高的柵格行進。基于上述機制實現了在形狀不規則的作業區域內進行往復回轉式全覆蓋路徑規劃;以每次植保作業距離為變量，根據仿真算法得出返航點數量與位置來確定尋優模型中的變量維數范圍，以往返飛行、電池更換與藥劑裝填等非植保作業耗費時間最短為目標函數，通過采用引力搜索算法，實現對返航點數量與位置的尋優;為無人機設置必要的路徑糾偏與光順機制，使無人機能夠按既定路線與速度飛行。對提出的路徑規劃方法進行了實例檢驗，結果顯示，相比于簡單規劃與未規劃的情況，運用Grid-GSA規劃方法得出的結果中往返飛行距離總和分別減少了14%與68%，非植保作業時間分別減少了21%與36%，其它各項指標也均有不同程度的提高。在驗證測試試驗中，實際的往返距離總和減少了322m，實際路徑與規劃路徑存在較小偏差。驗證了路徑規劃方法具有合理性、可行性以及一定的實用性。

植保無人機;路徑規劃;柵格法;返航點;引力搜索算法

引言

無人機(Unmanned aerial vehicle，UAV)憑借其尺寸小、機動性好、對起降跑道要求低或無要求、造價相對低廉以及無人化等優勢，已經在軍事與民用領域得到了廣泛使用［1－2］。植保無人機以無人機為載體，搭載農藥噴霧設備，用于植保作業，其具有作業高度低、漂移少、對環境的污染較低，受作業區域電線桿、防護林等限制條件的影響較小，且旋翼產生的氣流場有助于增加霧流對作物的穿透性，可獲得良好的噴施效果等優點，隨著相關技術的逐步成熟，植保無人機越來越受到關注，其使用也更加普及［3－4］。但目前植保無人機作業以遙控方式為主，操作難度較大，操縱人員往往需要經過專業培訓［5］;而且人為遙控時，難免產生偏離最佳路徑的現象，導致藥劑重施、漏施等問題［6］。因此，為了降低操縱人員的技術要求與工作壓力，同時使植保作業更加精準、高效與節能，針對植保無人機作業過程，編制合理的路徑規劃算法，并配套定位技術，使無人機能夠穩定的按照規劃路徑進行植保作業，已經成為當前植保無人機相關研究中需要解決的一個重要問題。另外，植保無人機的作業區域形狀較為規則，一般開闊無障礙，作業環境相對優越，這也為植保無人機朝著自動化與智能化方向發展提供了條件。

無人機路徑規劃方法主要包括目標區域偵察監測及定點、移動目標跟蹤打擊、誘敵飛行等，其中涉及到尋求最優路徑的優化方法，躲避火力威脅、地形障礙與雷達偵測等不利因素的避障方法以及相關定位、傳感方法等［7－8］。植保無人機路徑規劃屬于全覆蓋路徑規劃的范疇，大多數技術與研究均能夠實現該種路徑的規劃［9－10］。但路徑規劃還應該與實際的農藝要求相結合，如CONESA-MUOZ等［11］針對多輛拖拉機田間協同作業路徑規劃問題，以消耗最小為目標建立了數學模型，對模擬退火算法進行了改進并用于路徑尋優計算。在植保無人機路徑規劃方面也已經開展了一些研究，徐博等［12－13］針對形狀規則的作業區域內無人機返航點的規劃問題，提出了一種多架次作業植保無人機航跡規劃算法，該算法以無人機的工作總耗能最小為目標;其還針對不規則區域提出了一種植保作業航跡規劃算法，算法可根據指定作業方向規劃出與作業區域相應的路徑。

在植保無人機實際作業過程中，隨著藥劑或電量耗盡，無人機需要返航至保障點進行藥劑裝填或電池更換，其中返航點的數量與位置不僅受到載藥量、續航時間、飛行速度、作業幅寬等無人機固有屬性的影響，還與作業方向、作業區域尺寸和形狀等環境有關。以往的植保無人機路徑規劃方法中，返航點往往位于無人機起始點所在的作業區域邊界上，且在作業區域規模較大的情況下，返航點數量會多于未規劃時的情況，由于返航點數量增多，隨著往返次數增加，不僅會使往返距離總和變大，還會增加保障作業次數，從而導致非植保作業時間變長。針對這種情況，本文以縮短往返飛行、電池更換與藥劑裝填等非植保作業消耗的時間為目標，開展植保無人機路徑規劃方法研究。

1 植保無人機路徑規劃的基本思路

當作業區域面積較小時，植保無人機無需中途裝填藥劑或更換電池即可完成植保作業。但當作業區域較大，植保無人機單次植保作業無法滿足作業要求時，就需要中途多次飛至保障點進行保障作業。無人機在工作區域與保障點之間進行往返時，屬于非作業狀態，所以路徑規劃應盡量減少返航點與保障點之間的距離總和。表1首先對本文涉及的名詞進行定義。

設保障點位于坐標系原點，植保無人機續航時間為25min，飛行速度為6m/s，最長植保作業時間為15min，作業速度為3m/s，作業幅寬為2m。圖1中未規劃與簡單規劃情況下各返航點與保障點之間的往返距離總和分別為1 479m與629m，返航點數量均為5，此時圖1中的簡單規劃情況即可認為是最優路徑，出現此種最優情況的條件可表示為

表1 相關名詞定義Tab．1 Terms and definitions

圖1 300m×100m作業區域路徑規劃Fig．1 Path planning for 300m×100m working area

當無法滿足式(1)時，若仍要各返航點均位于起始點所在的作業區域邊界上，則必須增加返航點的數量。

圖2為相同型號植保無人機在400 m×100 m作業區域內未規劃與簡單規劃的返航點對比情況，返航點數量分別為7和8，而且這種返航點數量之間的差距還會隨著作業區域尺寸的改變而發生變化，如表2與表3所示。

圖2 400m×100m作業區域路徑規劃Fig．2 Path planning for 400m×100m working area

表2 返航點數量隨作業區域長度變化情況Tab．2 Number of return points varying w ith length of working area

表3 返航點數量隨作業區域寬度變化情況Tab．3 Number of return point varying w ith w idth of working area

定義植保無人機作業方向為作業區域長度方向，表2中，作業區域寬度為200 m，表3中，作業區域長度為400m，表2與表3中括號外數值為選取規則矩形作業區域時的測算結果。從表2、3中可知，當保持長度不變時，隨著寬度的增加，未規劃與簡單規劃的返航點數量之差將逐漸變大;當保持寬度不變時，隨著長度的增加，未規劃與簡單規劃的返航點數量之差未呈現單調變化趨勢，該差值主要與植保無人機載藥量所允許的最遠作業距離Dmax和作業區域長度L有關，Dmax/L越接近偶數，未規劃與簡單規劃的返航點數量之差就越小。除上述影響因素外，返航點數量還會受到作業區域不規則邊界的影響，表中括號內數字即為在不規則邊界的作業區域內未規劃與簡單規劃的返航點的數量情況，如圖2所示，不規則邊界由矩形區域去掉左上角三角形區域形成，表中的作業區域為去掉邊長40m的等腰直角三角形后的區域。

綜上所述，植保無人機路徑規劃主要是對作業過程中返航點數量與位置的規劃，其主要受到無人機固有屬性與作業區域環境的影響，而且通過表2中數據可知，簡單規劃的返航點數量比未規劃情況最多高出96%，隨著往返次數增多，往返距離與作業時間也隨之增大，需要對路徑進一步優化。針對上述問題，本文將柵格法(Grid method)［14］與引力搜索算法(Gravitational search algorithm，GSA)［15－16］相結合，運用柵格法建立作業區域環境，通過為柵格附加移動權值，使植保無人機路徑規劃方法能夠適應形狀不規則的作業區域，以非植保作業時間最小為目標，運用引力搜索算法進行尋優，從而獲得返航點數量與位置最優解。

2 基于Grid-GSA算法的路徑規劃方法

2.1 柵格化環境

植保無人機的路徑規劃可以視為已知環境下的路徑規劃問題，且由于植保作業的各條路徑相互平行或垂直，相鄰平行路徑之間的距離為作業幅寬。一般情況下，作業區域形狀較為規則，因此適宜應用柵格法表示環境情況。構造初始柵格時，以無人機的作業幅寬為邊長，根據實際環境信息對相應位置上的柵格賦予移動權值，位于作業區域邊界或障礙物處的柵格權值ω0=0，位于待作業區域中的柵格權值ωe=1。

2.2 作業路徑仿真

為能夠識別邊界，在作業區域內規劃出如圖1所示的往復回轉式作業路徑，首先計算無人機前進的概率為

式中 Pf——無人機前進的概率

ωf——無人機前進的權值

ωl、ωr、ωb——無人機左側、右側與后方柵格的權值，ωb=0表示無人機飛過區域均被視為邊界

其余方向的移動概率計算與式(2)同理。無人機前進方向的權值添加獎勵機制表示為

式中 S——直行獎勵系數，S＞1

Gf——無人機前方柵格

B——邊界柵格

利用式(2)與式(3)計算各個方向的移動概率，使無人機優先選擇概率大的移動方向，即可實現直行作業，且遇到作業區域邊界或障礙物時進行轉彎，但此時無人機作業路徑呈螺旋形，并不適用于植保作業。為使無人機在作業區域邊界處進行回轉，對無人機左后方或右后方柵格的權值進行獎勵

式中 U——回轉獎勵系數，U＞S

ωlb——無人機左后方柵格權值

Glb——無人機左后方柵格

如圖3所示，在t1時刻，無人機飛行至作業區域邊界，ωf=ω0=0，且通過式(4)所示的獎勵機制，柵格2權值ω2=ωe+U，設無人機右側為已作業區域，則此時無人機左轉概率最大;在t2時刻，無人機進入柵格1，此時ωf=ωe+S，而ωl=ω2=ωe+U，又因為U＞S，使得此時無人機左轉概率依然最大。通過上述方法，即可實現無人機的往復回轉式作業路徑規劃，再為無人機附加載藥量屬性，記錄每次植保作業時藥量耗盡的返航點位置，就能夠通過仿真得到未規劃狀態的返航點數量與位置。

2.3 引力搜索算法尋優

圖3 植保無人機周圍權值分布Fig．3 Weight distribution around plant protection UAV

遺傳算法、粒子群算法、模擬退火算法等智能優化算法已經被用于路徑規劃問題，在最短路徑規劃中表現出較好的性能［17－19］。引力搜索算法也屬于啟發式算法，對于本文研究的路徑規劃問題，變量為每次植保作業的飛行距離，目標為返航點與保障點之間往返距離總和最短，變量與目標函數之間不存在明顯的線性關系，且該函數關系還會受到無人機固有屬性與作業區域環境的影響，屬于較為典型的NP-Hard問題，適于智能優化算法求解［20］。引力搜索算法的迭代規則為:一個粒子在下一時刻的速度等于該時刻的速度加上加速度，在下一時刻的位置等于該時刻的位置加上下一時刻的速度，即

(1)算法尋優變量為每次植保作業的飛行距離，表示為

(2)由于固定的作業區域面積使得植保作業飛行時間一定，若要縮短總的作業時間，就應盡量降低往返飛行、電池更換與藥劑裝填等非植保作業的時間消耗，以非植保作業時間最短為目標建立目標函數

其中 Pn=(xn，yn) P0=(x0，y0)

式中 Ten——第n次保障作業時更換電池時間

Tpn——第n次保障作業時裝填藥劑時間

voff——非植保作業狀態下的飛行速度

Pn——第n個返航點的位置坐標

P0——保障點的位置坐標

xn、yn分別與Dn存在函數關系，可分別表示為

圖4 f與函數曲線Fig．4 Function graph of f and

式(7)表示電池更換與藥劑裝填兩項保障工作可同時進行，且取其中消耗時間較長者作為保障作業時間。

(3)以式(1)為每次尋優的約束條件。基于Grid-GSA算法的路徑規劃方法步驟為:①柵格化作業區域，為柵格設置初始權值。②運用仿真方法得出未規劃與簡單規劃的返航點數量與位置。③根據未規劃與簡單規劃的返航點數量之差確定搜索空間。④生成初始搜索群體。⑤計算個體目標函數值。⑥計算個體不同維度上的加速度和速度。⑦更新個體位置。⑧重復步驟⑤～⑦，直至達到終止條件。⑨輸出規劃結果并結束。

2.4 路徑糾偏與光順

從規劃好的路徑中選取關鍵點，并將其位置信息輸入無人機控制器，再配合無人機自身糾偏算法、定位系統、電動機、螺旋槳等硬件，即可使無人機按照既定路徑與速度自主飛行。本文方法所需的主要糾偏機制如圖5所示。

圖5 糾偏機制Fig．5 Machanism of deviation rectification

無人機通過機載定位系統反饋得到實際位置F，通過與輸入的關鍵點R1與R2形成直線進行比較，得出偏航距離d，以此為依據調整飛行速度。另外，無人機還需具備如圖5所示的光順路徑的能力。

3 實例檢驗

3.1 算例檢驗

設植保無人機續航時間為25 min，最長植保作業時間為15min，飛行速度voff為6m/s，作業速度von為3 m/s，計算得出載藥量所允許的最遠作業距離Dmax=2 700m，作業幅寬為2m，電池更換時間Te與最大藥劑裝填時間Tpmax均為1min，由于藥劑裝填時間與每次植保作業的載藥量有關，計算藥劑裝填時間Tpn為

式中 tb——藥劑裝填時間基數，本文取20 s

選取作業區域長700 m、寬100 m，邊界形狀不規則，如圖6所示，不規則邊界由矩形區域去掉左上角三角形區域形成，該三角形區域為直角邊長40 m的等腰直角三角形。圖6中坐標系為非等比坐標系，保障點位于坐標系原點處，根據植保無人機作業幅寬對作業區域柵格化，柵格邊長為2 m。運用仿真方法得出的未規劃與簡單規劃的返航點數量與位置如圖6所示，返航點數量分別為12與22，往返距離總和分別為6 440m和2 413m，非植保作業時間分別為29.9min和24.2min。

圖6 700m×100m作業區域路徑規劃Fig．6 Path planning for 700m×100m working area

運用Grid-GSA算法規劃返航點情況如圖7所示，植保無人機需要進行15次返航保障，返航點與保障點之間往返距離總和為2 073m，由于終點位置固定，所以該距離總和未考慮終點到保障點的距離，非植保作業時間19min，具體的規劃結果見表4。

圖7 基于Grid-GSA算法的路徑規劃返航點情況Fig．7 Planned path by Grid-GSA

表4 基于Grid-GSA算法的路徑規劃結果Tab．4 Results of path planning based on Grid-GSA

3.2 驗證試驗

試驗主要測量在實際環境中，無人機分別按照未規劃返航點與運用Grid-GSA算法規劃返航點飛行得出往返距離總和，檢驗該測量數據與計算機輸出數據的偏差，分析產生偏差的主要影響因素，以此為依據判斷本文提出方法的可行性與實用性。根據試驗要求，需要無人機具有按照設定航點飛行的功能，試驗選取大疆精靈3無人機，具體參數為最大水平飛行速度16 m/s，飛行時間約25 min，采用GPS定位，信號最大有效距離1 000m。

試驗于2017年1月在東北農業大學進行，試驗區域開闊無障礙，形狀為矩形，尺寸為200m×60m。人為設置邊界，于作業區域一角去掉直角邊長40m的等腰直角三角形區域，以驗證Grid-GSA算法對不規則邊界的適用性，天氣良好，試驗環境如圖8所示。

圖8 試驗環境Fig．8 Experiment environment

運用本文提出方法，對試驗田地的作業區域進行返航點規劃，結果如表5所示。根據表5數據，在作業區域內進行無人機航點定位。

完成定位后，使無人機按照既定航點飛行，并打開攝像功能，通過后期處理攝像中標志點的位置信息，來記錄實際航跡與理想航跡的偏差，現場情況如圖9所示。

表5 計算機輸出的返航點坐標數據Tab．5 Data of return point outputted by com puter m

圖9 航點定位Fig．9 Flight points positioning

通過試驗測得無人機實際飛行路徑如圖10所示。

圖10 無人機實際飛行路徑Fig．10 Path of UAV from test

通過試驗測得未規劃和Grid-GSA算法規劃的返航點情況如表6所示。

表6 試驗測得的返航點坐標數據Tab．6 Measured data of return point m

4 結果分析

對基于Grid-GSA算法規劃、簡單規劃與未規劃3種情況的數據進行對比，如表7所示。

表7 路徑規劃結果數據對比Tab．7 Data of path planning results

表7中，情況1、2、3分別對應Grid-GSA算法規劃、簡單規劃、未規劃。情況1中的返航點數量少于情況2，多于情況3，且由圖7可知，大多數返航點沒有位于起始點所在的作業區域邊界。設情況1的返航點數量與位置均為未規劃情況，保持15個返航點數量不變，將其移至作業距離所允許的最近起始點所在作業區域邊界，即進行簡單規劃，計算得

由該結果可知，無法滿足式(1)要求，并通過進一步計算驗證，在返航點數量少于22時均無法滿足式(1)要求。說明針對本文實例，簡單規劃結果必然導致返航點數量激增。

情況1相比于情況2、3，往返距離總和分別縮短了14%與68%，非植保作業時間分別減少了21%與36%。取情況1所有的返航點與情況2前15個返航點計算往返距離總和分別為2 073 m與1 223m，情況2剩余返航點與保障點之間的往返距離總和為1 190m。由此可見，雖然情況1與情況2相對應的返航點中，均是情況1返航點距離保障點較遠，但由于情況2返航點數量的增多，導致了往返距離總和的變大。而且保持作業區域長度不變，隨著寬度不斷增大，這種差距還會更加明顯。

3種情況更換電池的次數分別為9、8和12，裝填藥劑的次數與返航次數相同，分別為15、22和12，即情況3每次保障作業均進行了電池更換與藥劑裝填。情況3的保障作業時間最短，但由于往返距離較遠，使得非植保作業時間最長。情況1與情況2相比較，往返飛行時間與保障作業時間均較短，兩種情況的藥劑裝填平均時間分別為51.5 s與41.5 s，雖然情況2優于情況1，但由于保障次數增多，使得總的藥劑裝填時間較長，而且還加大了人工作業密度。

無人機電池充電時間較長，所以每次植保作業需要配備多組電池以備更換。本文規劃方法可計算出每塊電池電量消耗情況如表8所示，配合表4中電池更換的次數與時機，可為電池配備提供參考。3種情況中，電池的利用率平均值分別為79%、88%與65%，電池用量分別為10、9、13塊。若對情況1中低利用率電池1與10進行合并，則利用率平均值變為88%，電池用量變為9塊，所以在該方面情況1也表現出較優的性能。

表8 電池使用情況Tab．8 Consumption of battery power %

根據表5、6中的返航點坐標，可計算各返航點至保障點之間的距離，從而得出未規劃與Grid-GSA算法規劃后的往返距離總和，如表9所示。

表9 往返距離總和Tab．9 Total distance of round trip m

由表9可知，對于同一作業區域，運用Grid-GSA算法規劃返航點能夠使往返距離總和減少，且試驗結果顯示，運用Grid-GSA算法得出的往返距離總和減少幅度更加明顯，說明Grid-GSA算法具有一定的實用性與可行性。仿真結果與試驗結果存在一定偏差，主要由無人機定位系統與實際位置偏差造成，在試驗中，通過無人機航拍獲得標志點位置出現了偏離中心位置的情況，這說明試驗中的無人機沒有完全按照設定航點與路線飛行。雖然無人機具有自主的糾偏算法，但由于定位系統精度低的問題，就會導致無人機認為已經通過糾偏回歸正確航線，但實際上仍存在偏差。若采用MG-1S型植保無人機，使用手持RTK導航系統，精度可達到厘米級，且實現高精度定位還有較多手段，本文路徑規劃方法可以進一步得到改進。

5 結論

(1)將柵格法與引力搜索算法相結合，提出了基于Grid-GSA算法的路徑規劃方法。通過將無人機固有屬性與作業區域環境相關參數輸入算法，即可自動輸出最優的作業路徑，其中包含了合理的返航點數量與位置，保證非植保作業時間最短，且該方法適用于具有不規則邊界的作業區域。將規劃出的路徑輸入植保無人機控制器，通過無人機的糾偏算法、定位系統以及控制器與各硬件之間的協調配合，來實現自主作業。

(2)運用實例對本文提出的路徑規劃方法進行了檢驗。采用本文提出的基于Grid-GSA算法的路徑規劃方法得出的結果，相比于簡單規劃與未規劃情況，往返距離總和分別縮短了14%與68%，非植保作業時間分別減少了21%與36%，耗費電池數量與電池利用率等指標均較好，從而驗證了該方法的合理性與可行性。在驗證試驗中，運用Grid-GSA算法規劃返航點比未規劃的實際往返距離總和少322m，說明方法具有一定的實用性與可行性。

1 HUANG L，QU H，JIP，et al．A novel coordinated path planningmethod using k-degree smoothing formulti-UAVs［J］．Applied Soft Computing，2016，48:182－192．

2 TISDALE J，KIM Z W，HEDRICK J K．Autonomous UAV path planning and estimation［J］．IEEE Robotics＆Automation Magazine，2009，16(2):35－42．

3 張東彥，蘭玉彬，陳立平，等．中國農業航空施藥技術研究進展與展望［J/OL］．農業機械學報，2014，45(10):53－59．http:∥www．j-csam．org/jcsam/ch/reader/view_abstract．aspx?file_no=20141009＆flag=1．DOI:10．6041/j．issn．1000-1298．2014．10．009．ZHANG Dongyan，LAN Yubin，CHEN Liping，et al．Current status and future trends of agricultural aerial spraying technology in China［J/OL］．Transactions of the Chinese Society for Agricultural Machinery，2014，45(10):53－39．(in Chinese)

4 周志艷，臧英，羅錫文，等．中國農業航空植保產業技術創新發展戰略［J］．農業工程學報，2013，29(24):1－10．ZHOU Zhiyan，ZANG Ying，LUO Xiwen，et al．Technology innovation development strategy on agricultural aviation industry for plant protection in China［J］．Transactions of the CSAE，2013，29(24):1－10．(in Chinese)

5 丁團結，方威，王鋒．無人機遙控駕駛關鍵技術研究與飛行品質分析［J］．飛行力學，2011，29(2):17－24．DING Tuanjie，FANG Wei，WANG Feng．Development of UAV remote-piloted key technology and flight qualities［J］．Flight Dynamics，2011，29(2):17－24．(in Chinese)

6 彭孝東，張鐵民，李繼宇，等．基于目視遙控的無人機直線飛行與航線作業試驗［J/OL］．農業機械學報，2014，45(11): 258－263．http:∥www．j-csam．org/jcsam/ch/reader/view_abstract．aspx?file_no=20141140＆flag=1．DOI:10．6041/j．issn．1000-1298．2014．11．040．PENG Xiaodong，ZHANG Tiemin，LIJiyu，et al．Experimentof straight and airline flight operation for farmland based on UAV in visual remotemode［J/OL］．Transactions of the Chinese Society for Agricultural Machinery，2014，45(11):258－263．(in Chinese)

7 YAO P，WANG H，SU Z．Cooperative path planning with applications to target tracking and obstacle avoidance for multi-UAVs［J］．Aerospace Science＆Technology，2016，54:10－22．

8 RAMANA M V，VARMA SA，KOTHARIM．Motion planning for a fixed-wing UAV in urban environments［J］．IFAC-Papers Online，2016，49(1):419－424．

9 POPESCU D，STOICAN F，ICHIM L．Control and optimization of UAV trajectory for aerial coverage in photogrammetry applications［J］．Advances in Electrical and Computer Engineering，2016，16(3):99－106．

10 TORRES M，PELTA D A，VERDEGAY J L，et al．Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction［J］．Expert Systems with Applications，2016，55(C):441－451．

11 CONESA-MUOZ J，PAJARESG，RIBEIRO A．Mix-opt:a new route operator for optimal coverage path planning for a fleet in an agricultural environment［J］．Expert Systemswith Applications，2016，54:364－378．

12 徐博，陳立平，譚彧，等．多架次作業植保無人機最小能耗航跡規劃算法研究［J/OL］．農業機械學報，2015，46(11): 36－42．http:∥www．j-csam．org/jcsam/ch/reader/view_abstract．aspx?file_no=20151106＆flag=1．DOI:10．6041/j．issn．1000-1298．2015．11．006．XU Bo，CHEN Liping，TAN Yu，et al．Path planning based onminimum energy consumption for plant protection UAVs in sorties［J/OL］．Transactions of the Chinese Society for Agricultural Machinery，2015，46(11):36－42．(in Chinese)

13 徐博，陳立平，譚彧，等．基于無人機航向的不規則區域作業航線規劃算法與驗證［J］．農業工程學報，2015，31(23): 173－178．XU Bo，CHEN Liping，TAN Yu，et al．Route planning algorithm and verification based on UAV operation path angle in irregular area［J］．Transactions of the CSAE，2015，31(23):173－178．(in Chinese)

14 GU J，CAO Q．Path planning formobile robot in a 2.5 dimensional grid based map［J］．Industrial Robot，2011，38(3):315－321．

15 王宇，黃勝，廖全蜜，等．基于引力搜索算法的船舶艙室布置方法［J］．上海交通大學學報，2016，50(1):131－139．WANG Yu，HUANG Sheng，LIAO Quanmi，et al．A method for ship compartment layout design based on gravitational search algorithm［J］．Journal of Shanghai Jiao Tong University，2016，50(1):131－139．(in Chinese)

16 王宇，黃勝，廖全蜜，等．基于引力搜索算法的艙室分布方案設計方法［J］．哈爾濱工程大學學報，2016，37(1):48－52．WANG Yu，HUANG Sheng，LIAO Quanmi，et al．Method for the layout design of ship cabins based on gravitational search algorithm［J］．Journal of Harbin Engineering University，2016，37(1):48－52．(in Chinese)

17 MAC T T，COPOT C，TRAN D T，et al．Heuristic approaches in robot path planning:a survey［J］．Robotics＆Autonomous Systems，2016，86:13－28．

18 DAS P K，BEHERA H S，DAS S，et al．A hybrid improved PSO-DV algorithm for multi-robot path planning in a clutter environment［J］．Neurocomputing，2016，207:735－753．

19 BEHNCK L P，DOERING D，PEREIRA C E，et al．A modified simulated annealing algorithm for SUAVs path planning［J］．IFAC-Papers Online，2015，48(10):63－68．

20 RASHEDIE，NEZAMABADI-POUR H，SARYAZDIS．GSA:a gravitational search algorithm［J］．Information Sciences，2009，179(13):2232－2248．

Path Planning Method Based on Grid-GSA for Plant Protection UAV

WANG Yu CHEN Haitao LIYu LIHaichuan
(College of Engineering，Northeast Agricultural University，Harbin 150030，China)

Due to the limited battery power and pesticide capacity，the plant protection UAV need return to the supply point frequently in the process of plant protection．With thework area increasing，more time would be spent on battery replacement，pesticide filling and round trips between each return pointand the supply point．So an appropriate path with the optimal return pointsmust be planned before starting the work，in order to minimize the total time and improve the efficiency of the plant protection．For the purpose，a research was conducted on the path planning method for the plant protection UAV．Firstly，aiming at building an environmentmodel which could describe the working area，the grid method was selected to divide the working area into small gridswith the initialized weights，which were depended on the working area’s size and shape．Secondly，the UAV was made to fly from the current grid to the adjacent one with the highest probability，which was calculated according to both the grids’initialized weights and the heading direction of the UAV．Incentive coefficients were added to the weights of the grids located in the front，left rear and right rear of the UAV so that the parallel routes were followed which moved from one extreme of the working area to the other alternately and turned at the boundary．Then the quantity and position of the return point could be outputted by controlling the distance in the sprayingmode．Thirdly，amathematicalmodelwas established．The quantities of the return times in the artificial planned path and the unplanned path were taken as the upper and lower limits of the search space respectively．The distance of each flight in the sprayingmode was chosen as the variable，and the dimensions ofwhich were depended on the search space．The objective was to obtain the optimal return points with the minimum time in the non-spraying mode．After that the gravitational search algorithm (GSA)was applied to solve themodel．Based on themethods and processes above，a new path planning method was proposed．Then themethod would output the planned path with return points automatically byinputting the data about the environment and the UAV such as the size of the working area，the direction of the crop row and the speed of the UAV．At last，for the test of the performance of the proposed path planningmethod，a 700m×100m working area with the irregular boundary was taken as an example for the path calculation．The path calculated by the proposed method was also compared with the artificial planned path and the unplanned path respectively，which showed the non-spraying distance of the proposed method was reduced by 14%and 68%，while the non-spraying time was reduced by 21%and 36%．Furthermore，a field experiment with the real UAV was used to test the proposed deviation rectification algorithm．Finally，the study indicated that the proposed method which could produce paths with lessworking timewas a reasonable，feasible and useful solution for the path planning problem of the plant protection UAV．

plant protection UAV;path planning;grid method;return point;gravitational search algorithm

TP301.6;V279+.2

A

1000-1298(2017)07-0029-09

2016-11-05

2017-02-04

公益性行業(農業)科研專項(201303011)和國家現代農業產業技術體系建設專項(CARS-04-PS22)

王宇(1989—)，男，講師，主要從事農業機械化工程研究，E-mail:wang_neau@163．com

陳海濤(1962—)，男，教授，博士生導師，主要從事農業機械化工程與生物質材料研究，E-mail:CHT_neau@163．com

10．6041/j．issn．1000-1298．2017．07．004