基于改進(jìn)蟻群算法的植保無人機(jī)路徑規(guī)劃方法

王 宇 王文浩 徐 凡 王涇涵 陳海濤

(東北農(nóng)業(yè)大學(xué)工程學(xué)院， 哈爾濱 150030)

0 引言

植保無人機(jī)近年來發(fā)展迅速，相比于有人駕駛飛機(jī)，植保無人機(jī)飛行高度較低、藥液飄移較少、具有更強(qiáng)的地形適應(yīng)能力，并且遙控作業(yè)保證了操作人員的安全，其在小面積農(nóng)田或作物多樣化的種植區(qū)已經(jīng)體現(xiàn)出顯著優(yōu)勢。日、韓等國已經(jīng)普遍采用無人機(jī)進(jìn)行植保作業(yè)。我國既有集中的大塊農(nóng)田，也有數(shù)量眾多較為分散的或地形特殊的小塊農(nóng)田，發(fā)展植保無人機(jī)具有廣闊的市場需求[1-5]。目前，部分植保無人機(jī)產(chǎn)品已具有對簡單多邊形作業(yè)區(qū)域進(jìn)行路徑規(guī)劃的功能，但實(shí)際作業(yè)環(huán)境有時(shí)較為復(fù)雜，如多個(gè)具有高低起伏的作業(yè)區(qū)域。面對較為復(fù)雜的作業(yè)環(huán)境，如何規(guī)劃出更加合理的作業(yè)路徑，以進(jìn)一步提高植保無人機(jī)的作業(yè)效率，成為亟待解決的問題。

植保無人機(jī)的作業(yè)路徑采用往復(fù)回轉(zhuǎn)式路徑，并要求對作業(yè)區(qū)域?qū)崿F(xiàn)全覆蓋[6-8]。文獻(xiàn)[9]基于掃描線方法提出了一種無人機(jī)全覆蓋路徑規(guī)劃方法，該方法將復(fù)雜多邊形區(qū)域合理劃分，可進(jìn)一步提高無人機(jī)作業(yè)效率。文獻(xiàn)[10-11]基于改進(jìn)的遺傳算法提出了一種植保無人機(jī)全局航線規(guī)劃算法，實(shí)現(xiàn)了多塊農(nóng)田的路徑規(guī)劃。文獻(xiàn)[12]基于改進(jìn)的退火算法提出了一種適用于內(nèi)含障礙物農(nóng)田的植保無人機(jī)路徑規(guī)劃方法，可實(shí)現(xiàn)航向角的優(yōu)化。上述研究中均未考慮三維地形的影響，植保無人機(jī)作業(yè)時(shí)仿地形飛行，以保證無人機(jī)與作物保持一定距離，若路徑規(guī)劃時(shí)不考慮三維地形的影響，則會(huì)使規(guī)劃結(jié)果與實(shí)際距離不一致，導(dǎo)致諸多計(jì)算結(jié)果失去對實(shí)際作業(yè)路徑的指導(dǎo)意義[13]。文獻(xiàn)[14]基于Morse分解方法提出了一種多架次無人機(jī)全覆蓋路徑規(guī)劃方法，能夠在內(nèi)含障礙物的三維作業(yè)區(qū)域中進(jìn)行路徑規(guī)劃。文獻(xiàn)[15-16]提出了基于引力搜索算法的路徑規(guī)劃方法，該方法能夠針對具有不規(guī)則邊界的三維地區(qū)進(jìn)行路徑規(guī)劃。但研究中未對作業(yè)路徑的航向角進(jìn)行規(guī)劃，且作業(yè)路徑的排序采用貪婪算法，導(dǎo)致計(jì)算結(jié)果避開較優(yōu)解的概率增大。

針對上述問題，本文提出一種適用于多個(gè)具有復(fù)雜多邊形邊界與內(nèi)部障礙物的三維作業(yè)區(qū)域的植保無人機(jī)路徑規(guī)劃方法。在掃描生成水平面內(nèi)的作業(yè)路徑基礎(chǔ)上，經(jīng)過離散化與插值等處理，獲得三維作業(yè)路徑；對蟻群算法(Ant colony optimization, ACO)進(jìn)行適用性改進(jìn)，以實(shí)現(xiàn)對三維作業(yè)路徑的排序優(yōu)化。

1 基于改進(jìn)蟻群算法的路徑規(guī)劃方法

基于改進(jìn)蟻群算法的路徑規(guī)劃方法主體包含作業(yè)路徑生成算法與改進(jìn)的蟻群算法，兩種算法各自的輸入輸出如表1所示。

表1 兩種算法的輸入與輸出Tab.1 Input and output of each algorithm

表1中，作業(yè)路徑是指進(jìn)行噴施作業(yè)的路徑；距離矩陣是指作業(yè)路徑端點(diǎn)之間的距離組成的矩陣；轉(zhuǎn)移路徑是指在作業(yè)路徑端點(diǎn)之間移動(dòng)的非噴施作業(yè)路徑。算法針對多個(gè)作業(yè)區(qū)域進(jìn)行路徑規(guī)劃的基本流程如圖1所示，圖中Pk與Dk分別為作業(yè)區(qū)域k(k=1,2,…,n)內(nèi)的路徑集與距離矩陣。

圖1 基于改進(jìn)蟻群算法的路徑規(guī)劃方法流程圖Fig.1 Flowchart of path planning approach based on ACO

2 作業(yè)路徑生成算法

作業(yè)路徑生成算法的基本思路：①根據(jù)作業(yè)區(qū)域邊界生成具有一定方向的水平面內(nèi)的作業(yè)路徑。②根據(jù)三維地形，將水平面內(nèi)的作業(yè)路徑轉(zhuǎn)變?yōu)槿S作業(yè)路徑。

2.1 水平面內(nèi)的作業(yè)路徑生成方法

設(shè)植保無人機(jī)作業(yè)路徑與坐標(biāo)系X軸正向的夾角為航向角θ、作業(yè)幅寬為w。水平面內(nèi)的作業(yè)路徑生成方法的步驟為：①輸入作業(yè)區(qū)域邊界頂點(diǎn)坐標(biāo)。②以-θ為轉(zhuǎn)角旋轉(zhuǎn)作業(yè)區(qū)域邊界。③以w為間距建立一組與坐標(biāo)系X軸平行的、能夠覆蓋作業(yè)區(qū)域的掃描線。④求第i條掃描線與邊界的交點(diǎn)集。⑤以x坐標(biāo)值遞增將交點(diǎn)集排序。⑥從前至后依次將交點(diǎn)集內(nèi)的交點(diǎn)兩兩配對，每對交點(diǎn)之間的連線即作業(yè)路徑，執(zhí)行完該步后i=i+1。⑦重復(fù)步驟④直至求出所有掃描線與邊界形成的作業(yè)路徑。

針對圖2所示的內(nèi)部包含障礙物的凹多邊形作業(yè)區(qū)域進(jìn)行具體執(zhí)行過程說明，藍(lán)色直線為掃描線中的一條，分別與作業(yè)區(qū)域邊界交于A1～A4點(diǎn)，按照x坐標(biāo)值遞增排序后，依次兩兩配對并連線后得到線段A1A2、A3A4，即作業(yè)路徑。

圖2 掃描線與邊界的交點(diǎn)Fig.2 Intersections of scan lines and boundary

在執(zhí)行步驟④至⑥時(shí)，可能會(huì)出現(xiàn)如圖2所示的紅色掃描線與邊界的頂點(diǎn)相交的特殊情況。在交點(diǎn)A5處，掃描線分別與2條邊界的頂點(diǎn)相交，可視為2個(gè)交點(diǎn)重疊。同理，圖2中除點(diǎn)A11以外的所有交點(diǎn)，均為相互重疊的2個(gè)交點(diǎn)。處理這種情況時(shí)，若將重疊的2個(gè)交點(diǎn)合并成1個(gè)交點(diǎn)，再前后依次兩兩配對后，則會(huì)得到線段A5A6、A7A8、A9A10、A11A12，其中，線段A5A6、A9A10均位于作業(yè)區(qū)域外，而正確的作業(yè)路徑A6A7、A8A9卻未計(jì)入作業(yè)路徑，這顯然不合理。

針對上述情況，認(rèn)為掃描線與邊界的交點(diǎn)總是在掃描線的一側(cè)，求出交點(diǎn)集后，再剔除交點(diǎn)集中重疊的交點(diǎn)。此處設(shè)交點(diǎn)總是在掃描線的上側(cè)，對圖2中紅色掃描線與邊界的交點(diǎn)進(jìn)行處理：交點(diǎn)A5與邊界K1、K2均在掃描線上側(cè)，所以交點(diǎn)A5在邊界K1、K2上，此處是2個(gè)重疊的交點(diǎn)；交點(diǎn)A6與邊界K3在掃描線上側(cè)，邊界K4在掃描線下側(cè)，所以交點(diǎn)A6在邊界K3上，認(rèn)為此處只有1個(gè)交點(diǎn)；點(diǎn)A7在邊界線上側(cè)，邊界K5、K6在掃面線下側(cè)，認(rèn)為此處沒有交點(diǎn)；其他交點(diǎn)處理方式類似于這3種情況。將重疊的交點(diǎn)從經(jīng)過處理的交點(diǎn)集中剔除，剩余交點(diǎn)A6、A9、A11、A12，按步驟⑥可得作業(yè)路徑A6A9、A11A12，包括且僅包括所有的位于作業(yè)區(qū)域內(nèi)的作業(yè)路徑。另外，認(rèn)為重合的線彼此之間沒有交點(diǎn)。

2.2 三維作業(yè)路徑生成方法

如圖3所示，對于同一塊正方形的作業(yè)區(qū)域，若不考慮三維地形，則作業(yè)路徑無論沿著方向1還是方向2進(jìn)行規(guī)劃，其總距離應(yīng)該是相同的；但考慮三維地形時(shí)，顯然沿著方向1規(guī)劃，作業(yè)路徑總長度更短。所以，進(jìn)行作業(yè)路徑規(guī)劃時(shí)，有必要考慮三維地形的影響。

圖3 正方形作業(yè)區(qū)域三維作業(yè)路徑Fig.3 3D path in square farmland

三維作業(yè)路徑生成步驟為：①以一定的間距a建立一組與水平面內(nèi)的作業(yè)路徑垂直的、能夠覆蓋作業(yè)區(qū)域的直線。②求取直線與水平面內(nèi)的作業(yè)路徑的交點(diǎn)，從而將作業(yè)路徑離散成被交點(diǎn)分隔的線段。③運(yùn)用交點(diǎn)與作業(yè)路徑端點(diǎn)坐標(biāo)在已知三維地形曲面上插值得各點(diǎn)相應(yīng)的高度。④連接同屬一條作業(yè)路徑上的各點(diǎn)即得三維作業(yè)路徑。⑤以θ為轉(zhuǎn)角旋轉(zhuǎn)三維作業(yè)路徑。

其中，離散直線間距a越小，精度越高、計(jì)算量越大，若地形起伏較平緩，a可取較大值；若地形變化較劇烈，則a須取較小值。

通過上述方法，能夠?qū)崿F(xiàn)在一定航向角θ條件下的三維作業(yè)路徑總長度與數(shù)量的計(jì)算，作業(yè)路徑生成算法以航向角θ為變量，0≤θ<π，由于變量少，變化范圍小，所以采取以π/180為步長遍歷的方式對θ進(jìn)行尋優(yōu)，優(yōu)化目標(biāo)為作業(yè)路徑總長度盡量短、路徑之間轉(zhuǎn)移次數(shù)盡量少，由于每條作業(yè)路徑只經(jīng)過一次，所以作業(yè)路徑之間的轉(zhuǎn)移次數(shù)可視為作業(yè)路徑數(shù)量，目標(biāo)函數(shù)E為

(1)

其中

式中ωN——作業(yè)路徑之間轉(zhuǎn)移次數(shù)權(quán)重

N——作業(yè)路徑數(shù)量

Nmax、Nmin——作業(yè)路徑數(shù)量最大值、最小值

ωL——作業(yè)路徑長度權(quán)重

Lmax、Lmin——作業(yè)路徑總長度最大值、最小值

L——作業(yè)路徑總長度

Li——第i條作業(yè)路徑的長度

3 改進(jìn)的蟻群算法

得出三維作業(yè)路徑之后，還須按照一定順序?qū)⑵溥M(jìn)行連接。對于如圖3所示的簡單多邊形作業(yè)區(qū)域，將作業(yè)路徑順次連接即可。但是對于較為復(fù)雜的情況，例如圖4所示的4個(gè)作業(yè)區(qū)域，對其內(nèi)的作業(yè)路徑進(jìn)行排序時(shí)須按照一定的策略，才能使轉(zhuǎn)移路徑總長度較短。

圖4 算例作業(yè)區(qū)域Fig.4 Example farmland

作業(yè)路徑的排序問題，類似于旅行商問題，將作業(yè)路徑視為節(jié)點(diǎn)，對于所有的節(jié)點(diǎn)，既要求遍歷，又不能重復(fù)。在此前提下求節(jié)點(diǎn)的排序，以使節(jié)點(diǎn)之間的轉(zhuǎn)移路徑總長度最短，若采用遍歷方式求該類問題的最優(yōu)解，遍歷次數(shù)為節(jié)點(diǎn)數(shù)量的階乘，隨著節(jié)點(diǎn)增多，計(jì)算量增大[17-18]。

作業(yè)路徑的排序問題更為復(fù)雜，旅行商問題中2個(gè)節(jié)點(diǎn)之間的距離固定，而作業(yè)路徑排序問題中每條作業(yè)路徑均具有2個(gè)端點(diǎn)，植保無人機(jī)須從其中一端點(diǎn)進(jìn)入，從另一端點(diǎn)離開，使得任意2條作業(yè)路徑之間的距離具有4種可能。

蟻群算法是一種啟發(fā)式智能優(yōu)化算法，適用于處理旅行商問題，能夠以轉(zhuǎn)移路徑最短為目標(biāo)，得出較優(yōu)的節(jié)點(diǎn)排序。其基本思路為：蟻群分批次出發(fā)，每只螞蟻選擇一條遍歷各節(jié)點(diǎn)的路線，并在路線上留下信息素，總長度較短的路線上信息素較多，下一批次螞蟻選擇路線時(shí)，會(huì)受到信息素的引導(dǎo)，隨著批次增多，總長度較短的路線上信息素不斷積累，最終，蟻群會(huì)集中到信息素最多的路線上[19-22]。

為了解決作業(yè)路徑排序問題，本文將蟻群算法改進(jìn)，使其對作業(yè)路徑排序的同時(shí)，考慮每條作業(yè)路徑的進(jìn)入點(diǎn)，建立的優(yōu)化模型如下：

(1)作業(yè)路徑與進(jìn)入點(diǎn)排序

將每條作業(yè)路徑順次編號i(i=1,2,…,N)，第i條作業(yè)路徑的2個(gè)端點(diǎn)分別為Ai與Bi，每只螞蟻選擇一條遍歷所有作業(yè)路徑的路線，其中，第m只螞蟻選擇的路線為

(2)

t——當(dāng)前螞蟻批次

由于每條作業(yè)路徑均有2個(gè)端點(diǎn)，螞蟻選擇不同的端點(diǎn)進(jìn)入時(shí)，轉(zhuǎn)移路徑的長度不同，所以還須為蟻群算法附加記錄每條作業(yè)路徑的進(jìn)入點(diǎn)的功能

(3)

式(2)、(3)中，當(dāng)n=1時(shí)，是螞蟻的起點(diǎn)，處理方式有兩種：①人為選定起點(diǎn)，對應(yīng)人為選定植保無人機(jī)作業(yè)起點(diǎn)的情況。②算法隨機(jī)選擇一條作業(yè)路徑與其上一端點(diǎn)作為起點(diǎn)，此時(shí)植保無人機(jī)的作業(yè)起點(diǎn)由算法優(yōu)化得出。

對于確定起點(diǎn)之后作業(yè)路徑與相應(yīng)進(jìn)入點(diǎn)的選擇，須按照一定的概率依次進(jìn)行。設(shè)第m只螞蟻現(xiàn)位于作業(yè)路徑i上，選擇作業(yè)路徑j(luò)，此時(shí)分為兩種情況，分別為選擇端點(diǎn)Aj與端點(diǎn)Bj作為進(jìn)入點(diǎn)，選擇兩端點(diǎn)的概率各為

(4)

(5)

式中α——信息素對選擇概率的重要程度

β——啟發(fā)因子對選擇概率的重要程度

τij(k)(t)——作業(yè)路徑i與作業(yè)路徑j(luò)(k)之間的信息素，初始值為1

ηiAj(k)、ηiBj(k)——從作業(yè)路徑i到達(dá)端點(diǎn)Aj(k)、Bj(k)的啟發(fā)因子

Vm——當(dāng)前第m只螞蟻可選擇的作業(yè)路徑集合

(2)啟發(fā)因子

啟發(fā)因子與作業(yè)路徑之間的距離矩陣有關(guān)，距離矩陣計(jì)算式為

(6)

(7)

(8)

dist(Ai,Aj)——端點(diǎn)Ai與Aj的歐氏距離

AiAj——端點(diǎn)Ai與Aj間線段

S——作業(yè)區(qū)域

h——設(shè)定的安全高度

H——升降飛行距離

若線段AiAj不包含于作業(yè)區(qū)域S，則轉(zhuǎn)移時(shí)還須按照設(shè)定的安全高度h進(jìn)行升降，采用如下策略判斷線段AiAj是否包含于作業(yè)區(qū)域S：①判斷線段AiAj是否與作業(yè)區(qū)域S的邊界內(nèi)交，若內(nèi)交，則不包含于；若只在端點(diǎn)處相交，則由策略②判斷。②采用射線法判斷相鄰兩交點(diǎn)的中點(diǎn)是否位于作業(yè)區(qū)域S內(nèi)，只要存在不位于作業(yè)區(qū)域S內(nèi)的中點(diǎn)，則不包含于；若均位于作業(yè)區(qū)域S內(nèi)，則包含于。

同理還可求

(9)

(10)

啟發(fā)因子計(jì)算式為

(11)

(12)

(3)信息素

批次之間信息素的更新策略為

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(13)

其中

式中ρ——信息素?fù)]發(fā)系數(shù)

Δτij(t)——第t批次與t+1批次之間的信息素變化量

Q——信息素增加強(qiáng)度系數(shù)

lm(t)——第t批次第m只螞蟻?zhàn)哌^的轉(zhuǎn)移路徑總長度

4 算例檢驗(yàn)

4.1 作業(yè)路徑生成算法檢驗(yàn)

相關(guān)參數(shù)設(shè)置如下：w=5 m，a=10 m，ωN=0.5，ωL=0.5。對如圖4所示的4個(gè)作業(yè)區(qū)域生成作業(yè)路徑，其中區(qū)域S1與區(qū)域S4內(nèi)部具有障礙物。圖5為4個(gè)作業(yè)區(qū)域所處的三維地形，構(gòu)成曲面的點(diǎn)陣中，各坐標(biāo)點(diǎn)在水平面內(nèi)彼此之間相距10 m。對航向角θ遍歷尋優(yōu)后生成的作業(yè)路徑如圖6所示。

圖5 作業(yè)區(qū)域三維地形Fig.5 3D terrain of farmland

圖6 作業(yè)路徑Fig.6 Spray path

由圖6可知，在區(qū)域S3與S4中，所得作業(yè)路徑方向不同，且三維地形使原本為直線的作業(yè)路徑變?yōu)榫哂懈叨茸兓那圩鳂I(yè)路徑，使作業(yè)路徑變長，具體計(jì)算結(jié)果如表2所示。

作業(yè)區(qū)域S1與S2中，三維作業(yè)路徑與水平面內(nèi)的作業(yè)路徑的航向角相同，由于三維作業(yè)路徑具有高度變化，所以總長度均較長。作業(yè)區(qū)域S3與S4中，三維作業(yè)路徑與水平面內(nèi)的作業(yè)路徑的航向角差異明顯，如作業(yè)區(qū)域S4中，水平面內(nèi)的作業(yè)路徑航向角為92°，基本與三維作業(yè)路徑航向角垂直。采用作業(yè)區(qū)域S3水平面內(nèi)的航向角9°，通過式(1)計(jì)算三維作業(yè)路徑的目標(biāo)函數(shù)E=0.29，大于0.14；同理，計(jì)算作業(yè)區(qū)域S4水平面內(nèi)的航向角92°對應(yīng)的三維作業(yè)路徑的目標(biāo)函數(shù)E=0.14，大于0.12，計(jì)算結(jié)果直接表明了生成作業(yè)路徑過程中若不考慮三維地形的影響，會(huì)導(dǎo)致航向角優(yōu)化結(jié)果出現(xiàn)偏差。

表2 作業(yè)路徑計(jì)算結(jié)果Tab.2 Results related to spray path

4.1.1離散直線的間距a

保持其他參數(shù)不變，改變離散直線的間距a，計(jì)算結(jié)果如表3所示。

表3 不同間距a的作業(yè)路徑計(jì)算結(jié)果Tab.3 Results related to spray path for different values of a

表3中，當(dāng)間距a=10 m時(shí)，相關(guān)計(jì)算結(jié)果見表2中的三維作業(yè)路徑的計(jì)算結(jié)果。由表3可知，間距a越小，計(jì)算時(shí)間越長。這主要是因?yàn)殚g距a縮小后，離散直線與每一條作業(yè)路徑的交點(diǎn)增多，而每個(gè)交點(diǎn)都需要在三維地形曲面上進(jìn)行插值計(jì)算。

在作業(yè)區(qū)域S1與S3中，間距a越小，作業(yè)路徑總長度越長，這是由于交點(diǎn)數(shù)量增多后會(huì)使作業(yè)路徑更好地與地面仿形。如圖7所示，對于一條作業(yè)路徑，間距a較小時(shí)，為藍(lán)色線，間距a較大時(shí)，為紅色線。顯然藍(lán)色線的總長度更長，也更接近地形曲面。以不同的間距a得出的作業(yè)路徑總長度雖有差距，但相差不大，這主要是因?yàn)樽鳂I(yè)區(qū)域內(nèi)地形的坡度較小，且在優(yōu)化后的航向上，地形起伏較少。如圖6所示，作業(yè)區(qū)域S1中的每一條作業(yè)路徑，均近似于與水平面具有一定傾斜角度的線段。而對于一條傾斜的線段，只要兩端點(diǎn)的位置確定，則總長度即確定，不管將其分為多少個(gè)離散線段進(jìn)行計(jì)算，總長度均不受影響。

圖7 作業(yè)路徑的生成Fig.7 Generation of spray path

當(dāng)間距a=15 m時(shí)，作業(yè)區(qū)域S4中，優(yōu)化所得的航向角為92°，與不考慮三維地形時(shí)優(yōu)化所得的航向角相同，說明此時(shí)間距a取值過大，使得三維作業(yè)路徑上的交點(diǎn)過少，無法通過插值得到足夠的地形信息，如圖7綠色線所示，由于缺少了中間3個(gè)交點(diǎn)，導(dǎo)致路徑包含的地形信息缺失。

由于構(gòu)成三維地形曲面的點(diǎn)陣中各點(diǎn)在水平面內(nèi)的間距為10 m，當(dāng)間距a=5 m時(shí)，已經(jīng)超過地形信息的精度，較難使作業(yè)路徑相關(guān)計(jì)算結(jié)果精度進(jìn)一步提高，而且還會(huì)導(dǎo)致計(jì)算時(shí)間變長?？杉僭O(shè)圖7中紅色線連接的點(diǎn)為地形曲面點(diǎn)陣中的點(diǎn)，精度為10 m，若采用間距a=5 m在其上進(jìn)行插值，則會(huì)出現(xiàn)空心交點(diǎn)所示的情況，此時(shí)，作業(yè)路徑長度計(jì)算結(jié)果與間距a=10 m時(shí)相同，但卻需要對多余的點(diǎn)進(jìn)行計(jì)算。所以，針對該算例，間距a選取10 m較為合適。

因?yàn)樽鳂I(yè)區(qū)域S2的地形為平地，使得不同的間距a所得結(jié)果相同，此時(shí)縮小間距a僅會(huì)導(dǎo)致計(jì)算時(shí)間增加，所以對作業(yè)區(qū)域S2可不進(jìn)行離散處理。

4.1.2作業(yè)幅寬w

根據(jù)大疆T16型植保無人機(jī)設(shè)置作業(yè)幅寬w=6.5 m，其他參數(shù)設(shè)置保持不變，三維路徑相關(guān)計(jì)算結(jié)果見表4。

由表4可知，作業(yè)幅寬w增至6.5 m后，各項(xiàng)計(jì)算結(jié)果均會(huì)受到影響。相比于作業(yè)幅寬w=5 m時(shí)，作業(yè)路徑的總長度縮短2 440 m，總數(shù)量減少30，這主要是因?yàn)樽鳂I(yè)幅寬w增加后，使作業(yè)路徑之間的間距變大，從而用較少的作業(yè)路徑便可覆蓋作業(yè)區(qū)域；作業(yè)路徑數(shù)量減少，作業(yè)路徑總長度也就隨之縮短。作業(yè)路徑的數(shù)量的變化也導(dǎo)致了優(yōu)化后的航向角的變化，例如作業(yè)區(qū)域S4中，優(yōu)化后的航向角為90°，與作業(yè)幅寬w=5 m時(shí)得出的航向角相垂直，這主要是因?yàn)檠?0°航向角的單條作業(yè)路徑長度較長，當(dāng)該方向作業(yè)路徑數(shù)量減少時(shí)，作業(yè)路徑總長度縮短幅度較大。

表4 w=6.5 m時(shí)三維作業(yè)路徑計(jì)算結(jié)果Tab.4 Results related to 3D spray path with w=6.5 m

4.2 改進(jìn)的蟻群算法檢驗(yàn)

本例對4.1節(jié)中當(dāng)w=5 m時(shí)得出的三維作業(yè)路徑進(jìn)行排序，改進(jìn)的蟻群算法的相關(guān)參數(shù)設(shè)置如下：總批次T=100，蟻群規(guī)模M=50，α=1，β=5，h=3 m，Q=100，ρ=0.1。根據(jù)不同的作業(yè)需求，分別對選定與未選定作業(yè)起點(diǎn)的情況進(jìn)行計(jì)算。

4.2.1選定作業(yè)起點(diǎn)的作業(yè)路徑排序

選定作業(yè)起點(diǎn)為C1(0,0,0)，計(jì)算得出作業(yè)路徑排序，結(jié)果如圖8a所示，圖中藍(lán)色線段為作業(yè)路徑，紅色線段為轉(zhuǎn)移路徑，轉(zhuǎn)移路徑總長度見表5。

圖8 選定作業(yè)起點(diǎn)時(shí)的作業(yè)路徑排序Fig.8 Sequence of spray paths with selected starting point

貪婪算法是一種能夠快速求解最短路徑問題的算法，其基本思路為選擇下一條作業(yè)路徑時(shí)，總是選擇最近的那一條[23-25]。與貪婪算法的計(jì)算結(jié)果進(jìn)行對比，能夠一定程度上驗(yàn)證改進(jìn)的蟻群算法的尋優(yōu)性能。以C1為起點(diǎn)，采用貪婪算法進(jìn)行作業(yè)路徑排序，結(jié)果如圖8b所示，轉(zhuǎn)移路徑總長度見表5。

表5 轉(zhuǎn)移路徑總長度Tab.5 Total length of transfer paths m

表5中記錄了5個(gè)作業(yè)起點(diǎn)各自對應(yīng)的轉(zhuǎn)移路徑總長度，其中，C1與C2為作業(yè)區(qū)域邊界的頂點(diǎn)，C3為作業(yè)區(qū)域外的點(diǎn)，A71與A73為三維作業(yè)路徑的端點(diǎn)。由表5可知，針對選定的作業(yè)起點(diǎn)進(jìn)行作業(yè)路徑排序，基于改進(jìn)的蟻群算法得到的轉(zhuǎn)移路徑總長度均較短，比貪婪算法計(jì)算結(jié)果縮短3%～28%，相差最大值為694 m。

計(jì)算過程中發(fā)現(xiàn)，采用貪婪算法進(jìn)行作業(yè)路徑排序時(shí)，轉(zhuǎn)移路徑總長度只與作業(yè)起點(diǎn)有關(guān)，因?yàn)樨澙匪惴偸前凑兆罱瓌t選擇下一條作業(yè)路徑，當(dāng)作業(yè)起點(diǎn)與待排序的作業(yè)路徑一定時(shí)，轉(zhuǎn)移路徑即已經(jīng)被確定。采用貪婪算法針對每個(gè)作業(yè)路徑端點(diǎn)進(jìn)行作業(yè)路徑排序，其中最短與最長的轉(zhuǎn)移路徑對應(yīng)的作業(yè)起點(diǎn)分別為A71與A73，轉(zhuǎn)移路徑總長度見表5。

而基于改進(jìn)的蟻群算法針對選定的作業(yè)起點(diǎn)進(jìn)行作業(yè)路徑排序時(shí)，多次求解的結(jié)果不唯一。以C1為作業(yè)起點(diǎn)，5次運(yùn)行改進(jìn)的蟻群算法所得的轉(zhuǎn)移路徑總長度分別為1 705、1 797、1 735、1 756、1 745 m。

這些數(shù)據(jù)顯示，生成的轉(zhuǎn)移路徑總長度上下浮動(dòng)，這是因?yàn)楦倪M(jìn)的蟻群算法是一個(gè)迭代計(jì)算過程，圖9表示第1次運(yùn)行時(shí)的迭代計(jì)算過程，轉(zhuǎn)移路徑總長度隨著迭代計(jì)算次數(shù)增加不斷縮短，由于總迭代計(jì)算次數(shù)較少，轉(zhuǎn)移路徑總長度仍有縮短趨勢，還未出現(xiàn)信息素具有絕對優(yōu)勢的轉(zhuǎn)移路徑，螞蟻仍會(huì)積極搜索可行的轉(zhuǎn)移路徑。

圖9 轉(zhuǎn)移路徑總長度在100次迭代計(jì)算中的變化趨勢Fig.9 Trend of total length of transfer paths with 100 iterations

在圖9所示第100次迭代計(jì)算結(jié)果的基礎(chǔ)上，再繼續(xù)進(jìn)行900次迭代計(jì)算，過程如圖10所示，優(yōu)化后的轉(zhuǎn)移路徑總長度為1 683 m，當(dāng)計(jì)算至第70次時(shí)，優(yōu)化結(jié)果已經(jīng)小于1 685 m，其后的830次迭代計(jì)算降低幅度小于2 m，而在圖9所示的前100次迭代計(jì)算中，優(yōu)化解結(jié)果降低幅度超過500 m，說明迭代計(jì)算趨于收斂。所以應(yīng)盡量使總的迭代計(jì)算次數(shù)超過200次，以獲得更加優(yōu)化的結(jié)果。

4.2.2未選定作業(yè)起點(diǎn)的作業(yè)路徑排序

該種情況下作業(yè)起點(diǎn)與轉(zhuǎn)移路徑由算法一并計(jì)算得出?；诟倪M(jìn)的蟻群算法得到的轉(zhuǎn)移路徑如圖11a所示，紅色線段與綠色線段均為轉(zhuǎn)移路徑，其中綠色線段連接本次作業(yè)的起點(diǎn)與終點(diǎn)，計(jì)算得到的作業(yè)起點(diǎn)為A92(360 m, 67.5 m, 1.5 m)，轉(zhuǎn)移路徑總長度為1 661 m，比貪婪算法計(jì)算得出的最短轉(zhuǎn)移路徑短102 m。以A92作為作業(yè)起點(diǎn)，采用貪婪算法計(jì)算得出的轉(zhuǎn)移路徑如圖11b所示，轉(zhuǎn)移路徑總長度為2 383 m，比基于改進(jìn)的蟻群算法所得的結(jié)果長722 m。

圖11 未選定作業(yè)起點(diǎn)時(shí)的作業(yè)路徑排序Fig.11 Sequence of spray paths without selected starting point

在選定與未選定作業(yè)起點(diǎn)的條件下，通過對改進(jìn)的蟻群算法與貪婪算法所得的轉(zhuǎn)移路徑進(jìn)行對比可知，相同作業(yè)起點(diǎn)時(shí)，總是改進(jìn)的蟻群算法所得的轉(zhuǎn)移路徑總長度更短，因?yàn)楦倪M(jìn)的蟻群算法中，通過啟發(fā)因子，體現(xiàn)了每一次轉(zhuǎn)移時(shí)的距離對作業(yè)路徑選擇的客觀影響，同時(shí)，還通過信息素，保證了轉(zhuǎn)移路徑總長度的全局主導(dǎo)地位。

5 實(shí)例檢驗(yàn)

選取東北農(nóng)業(yè)大學(xué)試驗(yàn)田進(jìn)行實(shí)際地形的路徑規(guī)劃，作業(yè)區(qū)域共5塊，如圖12所示，其中作業(yè)區(qū)域S4內(nèi)部圓形為一高3 m的凸臺(tái)，其上也須作業(yè)，其余作業(yè)區(qū)域均為平地，已知的地理信息中構(gòu)成三維地形曲面的點(diǎn)陣水平面內(nèi)的間隔為20 m，根據(jù)算例相關(guān)結(jié)論，設(shè)置作業(yè)區(qū)域S4離散直線的間距a=20 m，對其余作業(yè)區(qū)域不進(jìn)行離散處理。作業(yè)區(qū)域之外存在道路、樹木、棚屋，相比于作業(yè)區(qū)域最低處分別高0.5、15、2.5 m，安全高度須大于其中的最大值，因此設(shè)置h=18 m。植保無人機(jī)作業(yè)幅寬w=5 m，總批次T=200，其余參數(shù)與算例設(shè)置一致。

圖12 實(shí)際地形作業(yè)區(qū)域Fig.12 Actual farmland

采集作業(yè)區(qū)域頂點(diǎn)坐標(biāo)建立數(shù)字化作業(yè)區(qū)域邊界，頂點(diǎn)坐標(biāo)如表6所示。作業(yè)區(qū)域S4中的圓形凸臺(tái)區(qū)域的圓心坐標(biāo)為(426 m,-128 m)，半徑為35 m。

進(jìn)行三維作業(yè)路徑生成，得到各作業(yè)區(qū)域內(nèi)的作業(yè)路徑與航向角，如表7所示。

當(dāng)選定C1(0, 0, 0)為作業(yè)起點(diǎn)時(shí)，作業(yè)路徑排序結(jié)果如圖13所示，轉(zhuǎn)移路徑總長度見表8。

表6 作業(yè)區(qū)域頂點(diǎn)坐標(biāo)Tab.6 Coordinates of spray area boundary vertices m

表7 實(shí)際地形作業(yè)路徑計(jì)算結(jié)果Tab.7 Results related to spray path in actual farmland

圖13 實(shí)際地形作業(yè)路徑排序Fig.13 Sequence of spray paths in actual farmland

表8 實(shí)際地形轉(zhuǎn)移路徑總長度Tab.8 Total length of transfer paths in actual farmland m

表8中，記錄了3個(gè)不同的作業(yè)起點(diǎn)各自對應(yīng)的轉(zhuǎn)移路徑總長度，C1為作業(yè)區(qū)域邊界的頂點(diǎn)，A75與B58均為作業(yè)路徑的端點(diǎn)，A75為改進(jìn)的蟻群算法所得最短轉(zhuǎn)移路徑對應(yīng)的起點(diǎn)，B58為貪婪算法所得最短轉(zhuǎn)移路徑對應(yīng)的起點(diǎn)。表8中數(shù)據(jù)顯示，相同作業(yè)起點(diǎn)時(shí)，改進(jìn)的蟻群算法所得的轉(zhuǎn)移路徑均較短，相比貪婪算法所得轉(zhuǎn)移路徑縮短7%～13%，相差最大值為600 m；改進(jìn)的蟻群算法所得最小值為4 001 m，比貪婪算法所得最小值(4 368 m)縮短367 m，數(shù)據(jù)均表明改進(jìn)的蟻群算法可規(guī)劃出較為高效的路徑。

6 結(jié)論

(1)提出了基于改進(jìn)蟻群算法的植保無人機(jī)路徑規(guī)劃方法。該方法將掃描生成的水平面內(nèi)的作業(yè)路徑離散化，通過在三維地形曲面上插值求取三維作業(yè)路徑，使航向優(yōu)化過程能夠考慮三維地形影響；對蟻群算法進(jìn)行改進(jìn)，使其具有同時(shí)記錄作業(yè)路徑與相應(yīng)進(jìn)入點(diǎn)的機(jī)制，從而能夠?qū)ψ鳂I(yè)路徑合理排序。

(2)在算例檢驗(yàn)中，針對同一作業(yè)區(qū)域，規(guī)劃出的作業(yè)路徑航向角相差最大值為92°，這說明路徑規(guī)劃過程中考慮三維地形的必要性。算例中，針對一系列相同的作業(yè)起點(diǎn)，改進(jìn)蟻群算法所得的轉(zhuǎn)移路徑總長度比貪婪算法所得結(jié)果縮短3%～28%；在未選定作業(yè)起點(diǎn)情況下，改進(jìn)蟻群算法與貪婪算法求得的轉(zhuǎn)移路徑總長度最小值分別為1 661 m與1 763 m。實(shí)例檢驗(yàn)中，在相同作業(yè)起點(diǎn)情況下，改進(jìn)蟻群算法所得的轉(zhuǎn)移路徑總長度比貪婪算法所得結(jié)果縮短7%～13%；在未選定作業(yè)起點(diǎn)情況下，改進(jìn)蟻群算法與貪婪算法求得的轉(zhuǎn)移路徑總長度最小值分別為4 001 m與4 368 m。說明改進(jìn)蟻群算法具有良好的尋優(yōu)能力。另外，算例與實(shí)例中的作業(yè)區(qū)域具有復(fù)雜多邊形邊界、三維地形、內(nèi)含障礙物等特征，表明本文提出的路徑規(guī)劃方法具有一定實(shí)用性。

(3)提出的路徑規(guī)劃方法尚未考慮作業(yè)過程中的農(nóng)藥補(bǔ)充與電池更換。進(jìn)行農(nóng)藥補(bǔ)充與電池更換時(shí)，植保無人機(jī)須由當(dāng)前位置中斷，再返航至補(bǔ)給點(diǎn)，返航路徑必然會(huì)影響路徑的總長度，因此本文提出的路徑規(guī)劃方法更適用于較小面積的作業(yè)區(qū)域。