徐 博 陳立平 徐 旻 譚 彧

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

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

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

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

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

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

引言

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

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

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

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

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

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

(1)

(2)

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

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

(3)

(4)

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

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

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

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

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

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

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

(5)

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

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

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

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

2.2 遺傳算法設(shè)計(jì)

2.2.1 編碼與初始化

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

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

2.2.2 適應(yīng)度函數(shù)與個(gè)體選擇

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

(6)

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

2.2.3 交叉與變異

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

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

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

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

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

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

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

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

如圖6所示，針對(duì)所選5個(gè)作業(yè)區(qū)域A、B、C、D、E，假設(shè)利用所選算法得到的優(yōu)化作業(yè)順序?yàn)锳→B→C→D→E，通過基于作業(yè)方向的航線規(guī)劃算法分別得到各作業(yè)區(qū)域的作業(yè)起始點(diǎn)和終止點(diǎn)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 二進(jìn)制編碼示意圖Fig.7 Schematic diagrams of binary coding

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

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

(7)

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

4 仿真

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

表1 各區(qū)域邊界點(diǎn)坐標(biāo)Tab.1 Boundary point coordinates of areas

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

1 王玲，蘭玉彬，HOFFMANN W C,等. 微型無人機(jī)低空變量噴藥系統(tǒng)設(shè)計(jì)與霧滴沉積規(guī)律研究[J/OL].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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 李鑫星，李輝，馬云飛，等.面向蔬菜病蟲害視頻移動(dòng)獲取的網(wǎng)絡(luò)互通網(wǎng)關(guān)設(shè)計(jì)[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，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 張東彥，蘭玉彬，陳立平，等. 中國(guó)農(nóng)業(yè)航空施藥技術(shù)研究進(jìn)展與展望[J/OL].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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 薛新宇，梁建，傅錫敏.我國(guó)航空植保技術(shù)的發(fā)展前景[J].中國(guó)農(nóng)機(jī)化，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 李成智，徐治立. 中國(guó)農(nóng)業(yè)航空技術(shù)發(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 薛新宇，蘭玉彬.美國(guó)農(nóng)業(yè)航空技術(shù)現(xiàn)狀和發(fā)展趨勢(shì)分析[J/OL].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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 茹煜，金蘭，賈志成，等.無人機(jī)靜電噴霧系統(tǒng)設(shè)計(jì)及試驗(yàn)[J].農(nóng)業(yè)工程學(xué)報(bào)，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 李冰，劉镕源，劉素紅，等．基于低空無人機(jī)遙感的冬小麥覆蓋度變化監(jiān)測(cè)[J]．農(nóng)業(yè)工程學(xué)報(bào)，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 茹煜，賈志成，范慶妮，等.無人直升機(jī)遠(yuǎn)程控制噴霧系統(tǒng)[J/OL].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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 秦維彩，薛新宇，周立新，等. 無人直升機(jī)噴霧參數(shù)對(duì)玉米冠層霧滴沉積分布的影響[J].農(nóng)業(yè)工程學(xué)報(bào)，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 丁團(tuán)結(jié)，方威，王鋒.無人機(jī)遙控駕駛關(guān)鍵技術(shù)研究與飛行品質(zhì)分析[J].飛行力學(xué)，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 彭孝東，張鐵民，李繼宇，等.基于目視遙控的無人機(jī)直線飛行與航線作業(yè)試驗(yàn)[J/OL]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，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è)植保無人機(jī)最小能耗航跡規(guī)劃算法研究[J/OL].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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 徐博，陳立平，譚彧，等.基于無人機(jī)航向的不規(guī)則區(qū)域作業(yè)航線規(guī)劃算法與驗(yàn)證[J/OL].農(nóng)業(yè)工程學(xué)報(bào)，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)化分割的機(jī)器人全覆蓋路徑規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用，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ī)模對(duì)遺傳算法性能影響的研究[D].保定：華北電力大學(xué)，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

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

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

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

TP18

A

1000-1298(2017)02-0075-07