多作業(yè)區(qū)域植保無人機航線規(guī)劃算法

徐 博 陳立平 徐 旻 譚 彧

(1.北京農(nóng)業(yè)智能裝備技術研究中心， 北京 100097； 2.中國農(nóng)業(yè)大學工學院， 北京 100083；3.北京市農(nóng)林科學院農(nóng)業(yè)智能裝備技術北京市重點實驗室， 北京 100097)

多作業(yè)區(qū)域植保無人機航線規(guī)劃算法

徐 博1,2陳立平1,3徐 旻1,3譚 彧2

(1.北京農(nóng)業(yè)智能裝備技術研究中心， 北京 100097； 2.中國農(nóng)業(yè)大學工學院， 北京 100083；3.北京市農(nóng)林科學院農(nóng)業(yè)智能裝備技術北京市重點實驗室， 北京 100097)

針對植保施藥多個作業(yè)區(qū)域的情況，研究了一種植保無人機全局航線規(guī)劃算法，將整個算法分為單個區(qū)域航線規(guī)劃、區(qū)域間作業(yè)順序和區(qū)域間調(diào)度航線規(guī)劃3部分。從作業(yè)路程、多余覆蓋和遺漏覆蓋的角度，分析了多種覆蓋作業(yè)方式的優(yōu)劣，確定了無人機在單區(qū)域內(nèi)的覆蓋方式?；谶z傳算法與TSP問題得到區(qū)域間的優(yōu)化作業(yè)順序，并基于改進的二進制編碼遺傳算法進行區(qū)域間調(diào)度航線的規(guī)劃，最終實現(xiàn)無人機多作業(yè)區(qū)域航線的全局規(guī)劃。仿真結果表明，規(guī)劃算法可以有效地實現(xiàn)全局航線的規(guī)劃，縮短了無人機的作業(yè)距離與區(qū)域間調(diào)度飛行的距離，達到了能耗與工作時間的優(yōu)化，節(jié)省了航線規(guī)劃所需的人力成本，使作業(yè)管理更加便利。

植保無人機; 航線規(guī)劃; 多區(qū)域作業(yè); 算法

引言

病蟲害是影響糧食安全的一個主要因素[1-2]，病蟲害的防治是糧食生產(chǎn)不可或缺的重要環(huán)節(jié)[3]，我國的種植地形多種多樣，既有平原的大面積種植區(qū)域，也有水田、丘陵等復雜地形[4-5]，對于后者，大型機械化防治很難實現(xiàn)，給病蟲害防治帶來了難題[6-7]。無人機具有作業(yè)靈活、起降無需跑道、地形適應性好、可懸停等特點[8]，可以適應丘陵、山區(qū)、坡地等復雜地形[9]，因此植保無人機已開始逐漸被運用在病蟲害防治中[10-11]。植保無人機以小型旋翼無人機作為載體，搭載農(nóng)藥噴霧設備進行作業(yè)[12]，目前植保無人機的作業(yè)主要是人為遙控為主，實際作業(yè)時對操作員依賴過大，文獻[13-14]指出了在遙控情況下，駕駛員操縱負荷較大，控制時間延遲，技術難點較多，并且人為即時規(guī)劃的航線與理論航線偏離嚴重、無人機的作業(yè)遺漏率和重復率往往偏高，因此對于具有自主作業(yè)功能的植保無人機研究是很有必要的。

在之前的研究中，針對規(guī)則區(qū)域的多架次植保無人機航線規(guī)劃法，合理地分配了各架次的噴藥量和返航點，降低了無人機在非作業(yè)情況下無效消耗能量，使無人機的工作總能耗得到優(yōu)化[15]；而對于不規(guī)則區(qū)域，研究了基于作業(yè)航向的植保無人機作業(yè)航線規(guī)劃算法，可根據(jù)指定的作業(yè)方向，快速規(guī)劃出較優(yōu)的作業(yè)航線，有效地減少了飛行總距離和多余覆蓋面積，通過分析作業(yè)航向與距離的關系，在未指定作業(yè)航向的情況下，給出某一推薦的作業(yè)航向與對應航線，使整個作業(yè)過程能耗和藥耗最優(yōu)[16]。但以上研究均是針對單區(qū)域進行的，而我國的地形較為復雜，既有較為集中的大塊田地，也有田塊較為分散的小面積農(nóng)田，因此在包含多個較小區(qū)域的植保作業(yè)中，對于全局航線規(guī)劃的研究也顯得尤為必要。多區(qū)域的作業(yè)規(guī)劃，不僅包含各區(qū)域內(nèi)作業(yè)航線，還包括區(qū)域間作業(yè)順序的安排和區(qū)域間調(diào)度航線規(guī)劃。本文首先進行無人機作業(yè)行走方式的選擇，并利用改進的遺傳算法實現(xiàn)對區(qū)域間作業(yè)順序的優(yōu)化和調(diào)度航線的規(guī)劃。

1 覆蓋區(qū)域作業(yè)方式的選擇

環(huán)境已知情況下，覆蓋機械的行走方式主要有牛耕往復法和內(nèi)外螺旋法，衡量行走方式優(yōu)劣的標準主要有時間、能耗、路程、覆蓋重復率與遺漏率，其中影響時間和多余能耗的主要因素為轉彎次數(shù)，轉彎次數(shù)越多，費時越多、多余能耗越大[17]。因此對兩種行走方式進行分析，確定較優(yōu)的無人機覆蓋方式(圖1)。

圖1 兩種作業(yè)行走方式示意圖Fig.1 Schematic diagrams of two operation modes

如圖1a所示，在一塊矩形作業(yè)區(qū)域中，采用往復行走作業(yè)方式，沿縱向(長邊)作業(yè)與沿橫向(短邊)相比，路程SBou和轉彎次數(shù)TBou較優(yōu)，分別為

(1)

(2)

當作業(yè)方向相垂直的區(qū)域長度(本文為橫向長度M)不為幅寬d的整數(shù)倍時，采用向右取整的方式，確保整個區(qū)域均被覆蓋。

如圖1b所示，沿縱向(長邊)開始的內(nèi)螺旋行走方式，與沿橫向(短邊)開始行走相比，路程SSpi和轉彎次數(shù)TSpi較優(yōu)，分別為

(3)

(4)

圖2 螺旋法重復與遺漏覆蓋示意圖Fig.2 Sketch of repeated and missing coverage of spiral method

2 區(qū)域間作業(yè)順序規(guī)劃

各區(qū)域的作業(yè)優(yōu)化航線可利用之前研究的基于作業(yè)方向的航線規(guī)劃算法(簡稱作業(yè)航線規(guī)劃算法)求得[16]，其規(guī)劃方式也是基于牛耕往復式實現(xiàn)的。當各區(qū)域作業(yè)航線規(guī)劃完成后，全局規(guī)劃算法主要集中在分配各區(qū)域作業(yè)順序與區(qū)域間調(diào)度航線規(guī)劃。

2.1 區(qū)域節(jié)點的獲取

區(qū)域間的調(diào)度航線即為上一個作業(yè)區(qū)域的終止點與下一個作業(yè)區(qū)域的起始點間的連線，如圖3所示，當某區(qū)域H1H2H3…Hm的作業(yè)航線確定后，作業(yè)起始點與終止點的位置可相互對調(diào)，即當點A1為作業(yè)起始點時，點A2便為作業(yè)終止點，反之當點A2為作業(yè)起始點，點A1即為此塊區(qū)域的作業(yè)終止點。由于區(qū)域間調(diào)度航線為某區(qū)域終止點與其他區(qū)域起始點或某區(qū)域起始點與其他區(qū)域終止點的連線，且某區(qū)域的作業(yè)起始點與終止點并不固定(可相互對調(diào))，因此設點A1與A2的中點A3為此區(qū)域的節(jié)點，通過規(guī)劃出各區(qū)域節(jié)點間的最短連通距離，可獲得整體調(diào)度航線較優(yōu)的作業(yè)區(qū)域順序。

圖3 區(qū)域節(jié)點的獲取Fig.3 Node acquisition of one operation area

先利用航線規(guī)劃算法得到各區(qū)域的作業(yè)航線，通過作業(yè)起始點和終止點求得各區(qū)域的節(jié)點坐標，如圖4所示，5個作業(yè)區(qū)域A、B、C、D、E，對應的節(jié)點分別為A3、B3、C3、D3、E3。區(qū)域間節(jié)點的連通屬于TSP旅行商問題，即尋找一條最短的遍歷各個節(jié)點的路徑，或者表述為搜索自然子集X={1, 2, …,n}(X的元素表示對n個節(jié)點的編號)的某個排列P(X)={V0,V1,V2, …,Vn}，使Td取值最小。

(5)

式中d(Vi,Vi+1)——節(jié)點Vi到節(jié)點Vi+1的距離Td——遍歷所有節(jié)點的總距離

圖4 多區(qū)域節(jié)點示意圖Fig.4 Schematic of multi-area nodes

采用遺傳算法對區(qū)域的作業(yè)順序進行規(guī)劃。遺傳算法是一種進化算法，其基本原理是仿效生物界中的“物競天擇、適者生存”的演化法則。圖5為遺傳算法流程圖，遺傳算法是把問題參數(shù)編碼為染色體，再利用迭代的方式進行選擇、交叉以及變異等運算來交換種群中染色體的信息，最終生成符合優(yōu)化目標的染色體。

圖5 遺傳算法求解流程圖Fig.5 Flow chart of genetic algorithm

2.2 遺傳算法設計

2.2.1 編碼與初始化

在遺傳算法運算之前，需要針對問題設計染色體，包括基因字串的長度以及基因代表的含義，也就是對要搜索空間的可行解以編碼的形式呈現(xiàn)。一般的編碼方式采用二進制編碼，此外也有整數(shù)、實數(shù)、文字等編碼方式。本研究采用整數(shù)排列編碼方法，對于n個節(jié)點的TSP問題，染色體分為n段，其中每一段對應區(qū)域節(jié)點的編號，如對10個區(qū)域節(jié)點的TSP問題{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}，則|10|1|6|5|2|4|8|7|9|3|就是一個合法的染色體。在生成染色體時需要進行染色體合法性檢查環(huán)節(jié)，即染色體恰好是n個區(qū)域節(jié)點編碼的一個排列，不能有重復的節(jié)點代碼出現(xiàn)。

在完成染色體編碼以后，必須產(chǎn)生一個初始種群(染色體集合)作為起始解，初始化結果的好壞，一定程度上決定了遺傳算法收斂所用的時間。首先，需要決定初始化種群的數(shù)目，一般情況下，初始化種群的數(shù)目根據(jù)經(jīng)驗得到，如果初始化數(shù)目太大，可能會消耗過多的計算時間，但如果數(shù)目太小可能難以達到預期效果并導致過早收斂。初始化種群采用隨機方式產(chǎn)生，初始化種群的數(shù)目往往根據(jù)作業(yè)區(qū)域(節(jié)點)數(shù)量而定，其取值一般在4n～6n之間[18]。

2.2.2 適應度函數(shù)與個體選擇

適應度是用來評價個體對“環(huán)境”的適應能力，適應度越高，說明適應能力越強。設|V1|V2|…|Vi|…|Vn|為一個采用整數(shù)編碼的染色體，其適應度函數(shù)為

(6)

適應度f1為恰好走遍n個節(jié)點，再回到出發(fā)節(jié)點的距離的倒數(shù)，適應度函數(shù)值越大的染色體越優(yōu)，反之越劣。個體的選擇即從舊群體中以一定概率選擇個體到新的群體中，個體被選中的概率跟適應度值有關，個體的適應度越大，被選中的概率越大。

2.2.3 交叉與變異

交叉操作采用局部映射雜交，確定交叉操作的父代個體，假定節(jié)點個數(shù)即染色體長度為n，在[1,n]區(qū)間內(nèi)產(chǎn)生隨機整數(shù)r1和r2，確定兩個位置，對父代染色體在這兩位置的中間數(shù)據(jù)進行交叉，形成兩個新的個體，如果新的個體中存在重復的節(jié)點編號，將不重復的數(shù)字保留，對于有沖突的數(shù)字，采用部分映射的方法消除沖突，即利用中間段的對應關系進行映射。交叉行為的發(fā)生有一定的概率，發(fā)生交叉行為的個體占種群個體總數(shù)的比例稱為交叉率，記為Pc。遺傳算法的變異操作指的是對染色體上某位置的信息進行變動，如交換路線上任意2個不同城市的位置。與交叉操作一樣，變異操作同樣有變異率的約束，是指發(fā)生變異的個體占種群中個體總數(shù)的比例，記為Pm。代溝是用于控制每代中種群被替換的比例，記為g，即在種群C中每代有C(1-g)個父代個體被選中進入下一代種群。

2.3 作業(yè)區(qū)域順序規(guī)劃算法的基本步驟

(1)對作業(yè)區(qū)域節(jié)點進行編碼，確定初始化種群數(shù)量，隨機生成初始種群。

(2)設置遺傳算法的選擇率、交叉率與變異率，并確定適應度函數(shù)。

(3)利用選擇、交叉與變異操作，形成下一代種群。

(4)驗證進化的代數(shù)是否滿足終止條件，即是否得到滿意的優(yōu)化解，若不滿足，返回步驟(2)繼續(xù)運行。

(5)解碼并輸出優(yōu)化的區(qū)域作業(yè)順序解。

3 區(qū)域間調(diào)度航線的規(guī)劃

如圖6所示，針對所選5個作業(yè)區(qū)域A、B、C、D、E，假設利用所選算法得到的優(yōu)化作業(yè)順序為A→B→C→D→E，通過基于作業(yè)方向的航線規(guī)劃算法分別得到各作業(yè)區(qū)域的作業(yè)起始點和終止點A1和A2、B1和B2、C1和C2、D1和D2、E1和E2，連接A2B1、B2C1、C2D1、D2E1、E2A1，形成了一組區(qū)域間調(diào)度航線l1、l2、l3、l4、l5。

圖6 區(qū)域間調(diào)度航線示意圖Fig.6 Schematic of dispatching routes among areas

圖7 二進制編碼示意圖Fig.7 Schematic diagrams of binary coding

如圖7a所示，可將多區(qū)域的作業(yè)順序和區(qū)域間的調(diào)度航線安排通過排列的方式表現(xiàn)出來，當各區(qū)域的作業(yè)順序保持不變時，如圖7b所示，各區(qū)域的作業(yè)起始點和終止點均可進行調(diào)整，而每個區(qū)域作業(yè)起始點與終止點的選擇均有2種情況。以區(qū)域A為例。作業(yè)起始點與終止點可分別為A1與A2或A2與A1，這兩種狀態(tài)可分別用0與1來表示，因此如圖7c所示，|A1A2|B2B1|C1C2|D1D2|E2E1|排列情況可通過二進制編碼01001表示，二進制編碼的位數(shù)與作業(yè)區(qū)域數(shù)相同。

同樣，區(qū)域間調(diào)度航線規(guī)劃也可利用遺傳算法進行求解，設作業(yè)區(qū)域數(shù)為m，對應的適應度函數(shù)為

(7)

適應度f2為m條調(diào)度航線總長度的倒數(shù)。按照遺傳算法的步驟進行調(diào)度航線規(guī)劃。

4 仿真

仿真時，選用5塊區(qū)域，區(qū)域A、B、C、D、E的各邊界點坐標如表1所示。

表1 各區(qū)域邊界點坐標Tab.1 Boundary point coordinates of areas

利用作業(yè)航線規(guī)劃算法得到各區(qū)域的作業(yè)起始點與終止點，并求出各區(qū)域對應的節(jié)點，結果如表2所示。

表2 各區(qū)域起始點、終止點和節(jié)點坐標Tab.2 Coordinates of starting points, ending points and nodes

利用遺傳算法計算遍歷各區(qū)域節(jié)點的最短路徑，設交叉率Pc=0.9，變異率Pm=0.2，種群大小C=20，代溝g=0.9。如圖8所示，當進化第3代時，得到遍歷各節(jié)點的路徑距離最優(yōu)值為Dmin=1 368.95 m，對應的作業(yè)順序為A→B→D→C→E。

圖8 作業(yè)順序遺傳算法進化過程圖Fig.8 Process of genetic algorithm in operating sequence

確定了作業(yè)順序后，對|A1A2|B1B2|D1D2|C1C2|F1F2|排列進行5位二進制隨機編碼，再次進行遺傳算法運算，適應度計算公式如式(7)所示，設種群大小C=10，交叉率Pc=0.9，變異率Pm=0.2，代溝g=0.9。如圖9所示，同樣在進化到第3代時，得到調(diào)度航線的距離最優(yōu)解Lmin=1 055.18 m，編碼序列為10011，即|A2A1|B1B2|D1D2|C2C1|F2F1|。

圖9 調(diào)度航線遺傳算法進化過程圖Fig.9 Process diagram of genetic algorithm in dispatching routes

航線規(guī)劃仿真結果如圖10所示，其中藍線為無人機在區(qū)域中作業(yè)航線，紅線為區(qū)域間調(diào)度航線，箭頭為調(diào)度方向，仿真結果驗證了本算法的可行性，可對無人機多區(qū)域作業(yè)進行全局航線規(guī)劃。

圖10 全局航線規(guī)劃仿真結果Fig.10 Overall route planning simulation results

5 結論

(1)從作業(yè)路程、多余覆蓋和遺漏覆蓋的角度，分析了多種覆蓋作業(yè)方式的優(yōu)劣，確定了牛耕往復法作為無人機在單區(qū)域內(nèi)的作業(yè)方式。

(2)將全局航線規(guī)劃算法劃分為單區(qū)域航線規(guī)劃、區(qū)域間作業(yè)順序規(guī)劃和區(qū)域間調(diào)度航線規(guī)劃3部分。將區(qū)域間作業(yè)順序規(guī)劃轉化為節(jié)點間的TSP旅行商問題，基于遺傳算法得到作業(yè)順序優(yōu)化解。之后利用改進的遺傳算法，對區(qū)域間調(diào)度航線進行二進制編碼，得到了區(qū)域間調(diào)度的最短航線，使得整個作業(yè)過程的能耗和工作時間得到了優(yōu)化。

(3)仿真得到了多區(qū)域作業(yè)的優(yōu)化順序與區(qū)域間調(diào)度航線的最短距離，驗證了算法的可行性，在無人機作業(yè)前可對整個作業(yè)過程的飛行航線進行規(guī)劃，節(jié)省了人力，使作業(yè)管理更加方便，同時降低了人為即時規(guī)劃的不準確性，使無人機植保系統(tǒng)更加智能化，規(guī)劃算法有效地減少了無人機飛行距離，因此既節(jié)省了能耗成本，又提高了無人機作業(yè)效率，有助于推動農(nóng)業(yè)植保朝著更加智能、高效、節(jié)能和無人化的方向發(fā)展。

1 王玲，蘭玉彬，HOFFMANN W C,等. 微型無人機低空變量噴藥系統(tǒng)設計與霧滴沉積規(guī)律研究[J/OL].農(nóng)業(yè)機械學報，2016，47(1)：15-22. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20160103&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2016.01.003. WANG Ling, LAN Yubin, HOFFMANN W C, et al. Design of variable spraying system and influencing factors on droplets deposition of small UAV[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(1): 15-22. (in Chinese)

2 李鑫星，李輝，馬云飛，等.面向蔬菜病蟲害視頻移動獲取的網(wǎng)絡互通網(wǎng)關設計[J/OL]. 農(nóng)業(yè)機械學報，2015，46(11)：309-315. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20151142&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2015.11.042. LI Xinxing, LI Hui, MA Yunfei, et al. Network interworking gateway design for video of vegetables harmed by pets[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(11): 309-315. (in Chinese)

3 張東彥，蘭玉彬，陳立平，等. 中國農(nóng)業(yè)航空施藥技術研究進展與展望[J/OL].農(nóng)業(yè)機械學報，2014，45(10)：53-59. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20141009&journal_id=jcsam. 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-59. (in Chinese)

4 薛新宇，梁建，傅錫敏.我國航空植保技術的發(fā)展前景[J].中國農(nóng)機化，2008(5)：72-74． XUE Xinyu, LIANG Jian, FU Ximin. Prospect of aviation plant protection in China[J]. Chinese Agricultural Mechanization, 2008(5): 72-74. (in Chinese)

5 李成智，徐治立. 中國農(nóng)業(yè)航空技術發(fā)展分析與政策建議[J]. 自然辯證法研究，2012，28(11)：36-41. LI Chengzhi, XU Zhili. The analyses and suggestions of technology development of agricultural aviation in China[J]. Studies in Dialectics of Nature, 2012, 28(11): 36-41. (in Chinese)

6 薛新宇，蘭玉彬.美國農(nóng)業(yè)航空技術現(xiàn)狀和發(fā)展趨勢分析[J/OL].農(nóng)業(yè)機械學報，2013，44(5)：194-201．http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20130534&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2013.05.034. XUE Xinyu， LAN Yubin. Agricultural aviation applications in USA[J/OL]. Transactions of the Chinese Society for Agricultural Machinery，2013，44(5)：194-201. (in Chinese)

7 茹煜，金蘭，賈志成，等.無人機靜電噴霧系統(tǒng)設計及試驗[J].農(nóng)業(yè)工程學報，2015，31(8)：42-47. RU Yu, JIN Lan, JIA Zhicheng, et al. Design and experiment on electrostatic spraying system for unmanned aerial vehicle [J]. Transactions of the CSAE, 2015, 31(8): 42-47. (in Chinese)

8 李冰，劉镕源，劉素紅，等．基于低空無人機遙感的冬小麥覆蓋度變化監(jiān)測[J]．農(nóng)業(yè)工程學報，2012，28(13)：160-165． LI Bing, LIU Rongyuan, LIU Suhong, et al. Monitoring vegetation coverage variation of winter wheat by low-altitude UAV remote sensing system[J]. Transactions of the CSAE, 2012, 28(13): 160-165. (in Chinese)

9 HUANG Y, HOFFMANN W C, LAN Y, et al. Development of a spray system for an unmanned aerial vehicle platform [J]. Applied Engineering in Agriculture, 2009, 25(6): 803-809．

10 JACOPO P, SALVATORE FILIPPO D G, EDOARDO F, et al. A flexible unmanned aerial vehicle for precision agriculture[J]. Precision Agriculture, 2012, 13(4): 517-523.

11 茹煜，賈志成，范慶妮，等.無人直升機遠程控制噴霧系統(tǒng)[J/OL].農(nóng)業(yè)機械學報，2012，43(6)：47-52. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20120609&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2012.06.009. RU Yu, JIA Zhicheng, FAN Qingni, et al. Remote control spraying system based on unmanned helicopter[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2012, 43(6): 47-52. (in Chinese)

12 秦維彩，薛新宇，周立新，等. 無人直升機噴霧參數(shù)對玉米冠層霧滴沉積分布的影響[J].農(nóng)業(yè)工程學報，2014,30(5)：50-56. QIN Weicai, XUE Xinyu, ZHOU Lixin, et al. Effects of spraying parameters of unmanned aerial vehicle on droplets deposition distribution of maize canopies [J]. Transactions of the CSAE, 2014, 30(5): 50-56.(in Chinese)

13 丁團結，方威，王鋒.無人機遙控駕駛關鍵技術研究與飛行品質分析[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)

14 彭孝東，張鐵民，李繼宇，等.基于目視遙控的無人機直線飛行與航線作業(yè)試驗[J/OL]. 農(nóng)業(yè)機械學報，2014，45(11)：258-263. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20141140&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2014.11.040. PENG Xiaodong, ZHANG Tiemin, LI Jiyu, et al. Experiment of straight and airline flight operation for farmland based on UAV in visual remote mode[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(11): 258-263. (in Chinese)

15 徐博，陳立平，譚彧，等.多架次作業(yè)植保無人機最小能耗航跡規(guī)劃算法研究[J/OL].農(nóng)業(yè)機械學報，2015，46(11)：36-42. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20151106&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2015.11.006. XU Bo, CHEN Liping, TAN Yu, et al. Path planning based on minimum 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)

16 徐博，陳立平，譚彧，等.基于無人機航向的不規(guī)則區(qū)域作業(yè)航線規(guī)劃算法與驗證[J/OL].農(nóng)業(yè)工程學報，2015，31(23)：173-178. http:∥www.tcsae.org/nygcxb/ch/reader/view_abstract.aspx?file_no=20152323&flag=1. DOI：10.11975/j.issn.1002-6819.2015.23.023. XU Bo, CHEN Liping, TAN Yu, et al. Route planning algorithm and verification based on UAV operation path angle in irregular area[J/OL]. Transactions of the CSAE，2015，31(23)：173-178. (in Chinese)

17 王儉，趙鶴鳴，肖金球.基于區(qū)域優(yōu)化分割的機器人全覆蓋路徑規(guī)劃[J].計算機工程與應用，2006，42(22)：59-62. WANG Jian, ZHAO Heming, XIAO Jinqiu. Optimized region decomposition based complete coverage path planning for mobile robot[J]. Computer Engineering and Applications, 2006, 42(22):59-62.(in Chinese)

18 劉曉霞.種群規(guī)模對遺傳算法性能影響的研究[D].保定：華北電力大學，2010:1-37.

Path Planning Algorithm for Plant Protection UAVs in Multiple Operation Areas

XU Bo1,2CHEN Liping1,3XU Min1,3TAN Yu2

(1.BeijingResearchCenterofIntelligentEquipmentforAgriculture,Beijing100097,China2.CollegeofEngineering,ChinaAgriculturalUniversity,Beijing100083,China3.BeijingKeyLaboratoryofIntelligentEquipmentTechnologyforAgriculture,BeijingAcademyofAgricultureandForestry,Beijing100097,China)

According to multi-area operations, a kind of overall route planning algorithm for plant protection UAVs was developed in order to reduce flight distance in multi-area operations and operating sequence of each area was reasonable allocation to improve operational efficiency and reduce energy consumption of the UAVs. The algorithm was divided into three parts, namely, single area route planning, operating sequences of areas and dispatching route planning among areas. After analyzing a variety of covering operation modes in aspects of operation distance, extra coverage and missed coverage, the UAVs operation mode in single area was determined. Optimized operation sequences of areas were planned based on genetic algorithm and traveling salesman problem (TSP). Dispatching routes among areas were planned based on improved genetic algorithm with binary coding, finally the overall route planning algorithm was achieved. The simulation was performed in an operation of five different irregular areas, numbers of each area were set asA,B,C,DandE. Operation route of each area was planned by using the previously proposed algorithm of route planning algorithm based on operation path angle in irregular, achieving operation start point, end point and node point coordinates of each area. Operation sequences of areas were achieved based on genetic algorithm and TSP, dispatching routes among areas were planned based on the improved genetic algorithm, of which the code was a random five-digit binary sequence, each digit represented arrangement of start point and end point of each area. The simulation result proved feasibility of the multi-area route planning algorithm. Nowadays, unmanned operations becomes trend, this multi-area route planning algorithm not only saves manpower required by route planning, but also makes operation management easier, and it is suitable for autonomous unmanned aerial vehicles and can be widely used in the area of precision agriculture.

plant protection UAVs; path planning; multi-area operation; algorithm

10.6041/j.issn.1000-1298.2017.02.010

2016-10-11

2016-11-23

國家自然科學基金項目(31601228)、北京市農(nóng)林科學院青年科研基金項目(QNJJ201422、QNJJ201632)和北京市自然科學基金項目(6164032)

徐博(1988—)，男，博士生，主要從事機電一體化研究，E-mail： xubocau@163.com

陳立平(1973—)，女，研究員，博士，主要從事農(nóng)業(yè)信息技術和農(nóng)業(yè)智能裝備研究，E-mail： chenlp@nercita.org.cn

TP18

A

1000-1298(2017)02-0075-07