復(fù)雜邊界田塊旋翼無(wú)人機(jī)自主作業(yè)路徑規(guī)劃

黃小毛 張 壘 TANG Lie 唐 燦 李小霞 賀小偉

(1.華中農(nóng)業(yè)大學(xué)工學(xué)院，武漢 430070；2.愛(ài)荷華州立大學(xué)農(nóng)業(yè)與生物系統(tǒng)工程系，埃姆斯 IA 50011；3.華中農(nóng)業(yè)大學(xué)信息學(xué)院，武漢 430070；4.塔里木大學(xué)現(xiàn)代農(nóng)業(yè)工程重點(diǎn)實(shí)驗(yàn)室，阿拉爾 843300)

0 引言

與地面機(jī)器相比，無(wú)人機(jī)空中作業(yè)具有通過(guò)性強(qiáng)、效率高、精度高等優(yōu)點(diǎn)，特別適合于植保、遙感、巡查和播撒等作業(yè)環(huán)節(jié)。作業(yè)路徑是無(wú)人機(jī)自主作業(yè)時(shí)機(jī)器軌跡控制的跟蹤目標(biāo)，在很大程度上決定機(jī)器作業(yè)過(guò)程的作業(yè)質(zhì)量、效率和總消耗。因此無(wú)人機(jī)作業(yè)路徑的規(guī)劃和優(yōu)化工作具有重要意義。

在目前農(nóng)機(jī)領(lǐng)域作業(yè)路徑的相關(guān)研究中，針對(duì)地面作業(yè)機(jī)器的居多[1-18]，針對(duì)農(nóng)用無(wú)人機(jī)作業(yè)路徑的研究不多。MOON等[12]針對(duì)噴粉無(wú)人直升機(jī)，提出基于田塊分區(qū)處理操作的路徑規(guī)劃方法。BARRIENTOS等[13]將待作業(yè)區(qū)域進(jìn)行網(wǎng)格化處理，提出一種基于任務(wù)協(xié)商機(jī)制的多架無(wú)人機(jī)協(xié)作圖像采集作業(yè)路徑規(guī)劃算法。VALENTE等[14]在此基礎(chǔ)上提出一種基于“和諧搜索”(Harmony search,HS)的啟發(fā)式搜索算法，求解遍歷網(wǎng)格的最優(yōu)次序。國(guó)內(nèi)相關(guān)的研究目前還處于起步階段，徐博等[15-16]對(duì)五邊形邊界單田塊的無(wú)人機(jī)作業(yè)路徑提出了具體的算法，并對(duì)多田塊路徑調(diào)度優(yōu)化進(jìn)行了研究。徐東甫等[17]、劉浩蓬等[18]分別將簡(jiǎn)單四邊形邊界的規(guī)劃路徑應(yīng)用到無(wú)人機(jī)赤眼蜂投放和噴霧試驗(yàn)中。王宇等[19]提出一種基于柵格模型的路徑規(guī)劃算法。彭孝東等[20]針對(duì)固定翼無(wú)人機(jī)作業(yè)過(guò)程中轉(zhuǎn)彎方式進(jìn)行了詳細(xì)的討論。以上研究的共同特點(diǎn)是作業(yè)田塊的邊界較為簡(jiǎn)單，均可簡(jiǎn)化為凸多邊形，而非實(shí)際應(yīng)用中遇到的復(fù)雜邊界田塊。

本文針對(duì)旋翼農(nóng)用無(wú)人機(jī)作業(yè)時(shí)可能遇到的各種復(fù)雜田塊邊界形狀的問(wèn)題，提出一種對(duì)田塊邊界形狀具有普適意義的旋翼無(wú)人機(jī)作業(yè)路徑規(guī)劃算法，以獲得凸多邊形、凹多邊形、帶孔洞多邊形或多個(gè)多邊形的復(fù)雜邊界田塊下的飛行作業(yè)軌跡。

1 作業(yè)路徑規(guī)劃的基本原理

1.1 旋翼無(wú)人機(jī)特點(diǎn)及路徑規(guī)劃的基本要求

與大田地面作業(yè)機(jī)器及固定翼飛機(jī)相比，旋翼農(nóng)用無(wú)人機(jī)具有不與地面接觸、可懸停、可任意方向移動(dòng)等特點(diǎn)，因此其作業(yè)路徑規(guī)劃應(yīng)滿(mǎn)足以下基本要求：有效工作路徑(即作業(yè)航線)做到對(duì)待作業(yè)田塊所有區(qū)域的全覆蓋，重復(fù)作業(yè)及遺漏作業(yè)面積盡可能小；航線間跳轉(zhuǎn)轉(zhuǎn)移等非工作路徑總長(zhǎng)度盡可能小；無(wú)需考慮轉(zhuǎn)彎及碾壓?jiǎn)栴}；算法的時(shí)間消耗不能太長(zhǎng)；具體作業(yè)類(lèi)型及應(yīng)用場(chǎng)合的其他要求(如避障)。

1.2 數(shù)據(jù)定義及算法流程

圖1 田塊邊界及頂點(diǎn)存儲(chǔ)順序示意圖

本文只針對(duì)常見(jiàn)的二維田塊，用一組多邊形分別代表田塊的外邊界和內(nèi)邊界，且外邊界以逆時(shí)針?lè)较?、?nèi)邊界以順時(shí)針?lè)较蛞来未鎯?chǔ)各頂點(diǎn)(如圖1所示)。通過(guò)分析可知采用多邊形表征田塊區(qū)域時(shí)具有以下特點(diǎn)：每個(gè)田塊有且只有一個(gè)外邊界，而可能沒(méi)有也可能有多個(gè)相離的內(nèi)邊界，且內(nèi)邊界一定包含在外邊界內(nèi)部；每個(gè)邊界都是一個(gè)簡(jiǎn)單多邊形(除相鄰邊外，其他各邊之間互不相交)，可以是凸多邊形也可以是凹多邊形；每2個(gè)田塊之間的邊界均為相離關(guān)系(既不相交也不相互包含)。這些特點(diǎn)既是后續(xù)算法中導(dǎo)入的田塊邊界的合理性規(guī)定，也是計(jì)算機(jī)能夠?qū)Χ噙呅芜吔邕M(jìn)行分組進(jìn)而自動(dòng)識(shí)別田塊的依據(jù)[21]。

以多邊形邊界和作業(yè)基本參數(shù)為輸入條件，以獲得旋翼無(wú)人機(jī)飛行作業(yè)路徑為目標(biāo)，本文設(shè)計(jì)的算法基本流程如圖2所示。

圖2 算法流程圖

1.3 邊界合規(guī)性檢查及分組

田塊邊界一般通過(guò)人工手持GPS直接打點(diǎn)或在GIS系統(tǒng)中鼠標(biāo)打點(diǎn)獲得，打點(diǎn)、存儲(chǔ)的順序可能具有隨意性，不一定完全符合1.2節(jié)中的規(guī)定。因此經(jīng)緯度球面坐標(biāo)轉(zhuǎn)換成直角坐標(biāo)后，首先需要對(duì)表征邊界的多邊形進(jìn)行合規(guī)性檢查，對(duì)不合要求的地方進(jìn)行調(diào)整，以保證后續(xù)處理順利進(jìn)行。然后，通過(guò)分組算法[21]確定多邊形之間的關(guān)系，即從數(shù)據(jù)結(jié)構(gòu)上建立田塊的概念。如從圖3a中輸入的B0、B1、B23個(gè)邊界多邊形，通過(guò)分析它們之間的包含關(guān)系，分組后分別建立F0(圖1)和F1(圖3b)2個(gè)獨(dú)立的田塊區(qū)域。

圖3 邊界合規(guī)性檢查及分組

1.4 填充線求解

多邊形填充是計(jì)算機(jī)圖形學(xué)中的經(jīng)典問(wèn)題[22]，在計(jì)算機(jī)動(dòng)畫(huà)、數(shù)控型腔銑削、3D打印和機(jī)器人等領(lǐng)域均有應(yīng)用[21]。利用掃描線及多邊形邊線的連貫性原理，采用有序邊表法進(jìn)行快速求交解算，可避免傳統(tǒng)做法中對(duì)每一組線段進(jìn)行逐一相交性測(cè)試，從而大大提高了求解效率和速度。

對(duì)于給定的任意形狀的單一多邊形，用一組水平或垂直的掃描線進(jìn)行掃描，對(duì)于每一掃描線而言均可求出與多邊形邊的交點(diǎn)，且交點(diǎn)成對(duì)出現(xiàn)，位于多邊形內(nèi)部的交點(diǎn)線段即為填充線。對(duì)于孔洞多邊形而言，分別求取外邊界多邊形B0、內(nèi)邊界多邊形B1～Bn的填充線，得到填充線段集合{L0}～{Ln}，再通過(guò)減法布爾運(yùn)算，即可得到孔洞多邊形區(qū)域的填充線集合，即航線集合{Pi}。對(duì)于孔洞多邊形田塊Fi而言，航向角θ條件下的作業(yè)航線Pi(θ)計(jì)算式為

(1)

以田塊F0為例，外邊界多邊形B0與內(nèi)邊界多邊形B1的填充線分別如圖4b淺藍(lán)色線條和圖4c紅色虛線條所示，二者作減法布爾運(yùn)算后的結(jié)果即為田塊F0在航向角為0條件下的作業(yè)航線，如圖4a淺藍(lán)色線條所示。

圖4 孔洞多邊形填充線的求解過(guò)程

1.5 活性邊表法

單個(gè)多邊形的填充線求解時(shí)，掃描線與多邊形邊的交點(diǎn)具有一定規(guī)律性，因此求解時(shí)不需要將每一條掃描線與每一條邊進(jìn)行求交測(cè)試并逐一解算交點(diǎn)，而是運(yùn)用活性邊表法快速求解。實(shí)施過(guò)程中用邊表(Edge table，ET)來(lái)確定哪些邊是下一條掃描線求交計(jì)算時(shí)應(yīng)及時(shí)加入運(yùn)算的邊，將與當(dāng)前掃描線相交的邊稱(chēng)為活化邊(Active edge list，AEL)，其個(gè)數(shù)可能不唯一且可動(dòng)態(tài)變化。由活化邊組成的表稱(chēng)為活性邊表(Active edge table，AET)，基于活性邊表的多邊形填充線求解算法稱(chēng)之為活性邊表法或有序邊表法。

作為存儲(chǔ)多邊形各邊的一種數(shù)據(jù)結(jié)構(gòu)，邊表用來(lái)表示對(duì)于某條掃描線而言第1次出現(xiàn)的邊的信息。以水平掃描線(即航向角為0)為例，每個(gè)節(jié)點(diǎn)的信息為(Ymax，dX，XYmin，next)，其中Ymax為對(duì)應(yīng)邊的最大Y值，dX為沿該邊從當(dāng)前掃描線到下一條掃描線之間的X方向增量(當(dāng)掃描線間距為1時(shí)為該邊斜率的倒數(shù))，XYmin為該邊的下端點(diǎn)的X坐標(biāo)，next為指向下一條邊的指針。建立邊表時(shí)，先按下端點(diǎn)的縱坐標(biāo)(Y值)對(duì)所有邊作分類(lèi)和排序，再將同一組中的邊按下端點(diǎn)X坐標(biāo)遞增的順序進(jìn)行排序，X坐標(biāo)還相同的按dX遞增的順序進(jìn)行排序。圖4b中多邊形的邊表如表1第2列所示(表中“→”表示指針next)。

表1 活性邊表法實(shí)施過(guò)程示例

對(duì)應(yīng)的，活性邊表AET中每個(gè)節(jié)點(diǎn)的信息也由4部分組成，即(Ymax，dX，XYmin，next)，其中Ymax、dX、next指針的含義同邊表。當(dāng)作業(yè)幅寬w不等于1時(shí)，dX=ΔX/w，式中ΔX為對(duì)應(yīng)邊在兩掃描線間的X方向增量。與邊表ET節(jié)點(diǎn)信息的主要差別在于第3個(gè)信息，XYmin為邊與當(dāng)前掃描線交點(diǎn)的X坐標(biāo)而不是當(dāng)前邊的下端點(diǎn)X坐標(biāo)。活性邊表的生成是基于邊表的，而由活性邊表生成成對(duì)的交點(diǎn)即為填充線段的端點(diǎn)。圖4b中多邊形的活性邊表及交點(diǎn)如表1第3、4列所示。

活性邊表法求解多邊形填充線段的流程如圖5所示。對(duì)于每一條掃描線而言，對(duì)應(yīng)的處理步驟如下[23]：

(1)對(duì)于掃描線Y=y，若對(duì)應(yīng)的ET中非空，則將其所有的邊從ET中取出并且插入到邊的活性邊表AET中，并對(duì)AET中各邊按XYmin及dX或ΔX遞增排序。

(2)若相對(duì)于當(dāng)前掃描線的AET非空，則將AET中的邊兩兩依次配對(duì)，即第1、2邊為一對(duì)，第3、4邊為一對(duì)，依此類(lèi)推，每一對(duì)邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，即為對(duì)應(yīng)的填充線。

(3)將當(dāng)前掃描線的縱坐標(biāo)Y累加w，即Y=Y+w。

(4)將AET中滿(mǎn)足Y=Ymax的邊刪去。

(5)將AET中剩下的每一條邊的X域累加dXw，即X=X+dXw。

(6)重復(fù)執(zhí)行步驟(1)，直至AET中邊全部刪除。

圖5 活性邊表法求解多邊形填充線段算法流程圖

1.6 航線排序優(yōu)化

上文中每一填充線即為飛行器作業(yè)時(shí)的具體航線，由于填充線段的長(zhǎng)度、位置各不相同，因此航線間存儲(chǔ)順序?qū)Q定遍歷時(shí)航線跳轉(zhuǎn)距離和遍歷過(guò)程的總軌跡長(zhǎng)度。若將每一條航線視為一個(gè)城市，這將是一個(gè)典型的旅行商問(wèn)題(TSP)，屬于NP-hard。本文主要采取文獻(xiàn)[5]中的貪婪算法進(jìn)行求解，該算法屬于組合優(yōu)化問(wèn)題的常規(guī)求解算法，雖然所得結(jié)果不一定為最優(yōu)，但算法穩(wěn)定可靠，具有實(shí)用性。具體實(shí)現(xiàn)過(guò)程見(jiàn)相關(guān)文獻(xiàn)，此處不再贅述。

航線間轉(zhuǎn)移時(shí)，轉(zhuǎn)移路線與田塊邊界之間存在兩種情況：一種是包含關(guān)系，即轉(zhuǎn)移線段全部包含在某一田塊的內(nèi)部(包括邊界上)，也就是無(wú)人機(jī)轉(zhuǎn)移過(guò)程中始終處于邊界內(nèi)部；另一種是非包含關(guān)系，即轉(zhuǎn)移線段上，除端點(diǎn)外，還有第3點(diǎn)處于邊界外部，也就是說(shuō)無(wú)人機(jī)轉(zhuǎn)移過(guò)程中會(huì)跳到田塊邊界的外部。因田塊邊界外部可能存在高于作業(yè)高度的障礙物(尤其在田塊間轉(zhuǎn)移時(shí))，為確保安全，有必要找出第2種情形下的線段并進(jìn)行必要處理。

采用“安全邊界相交性測(cè)試法”來(lái)判別某條候選轉(zhuǎn)移路徑線段Ji與田塊邊界多邊形組{Bi}是否屬于非包含關(guān)系。具體做法如下：根據(jù)障礙物情況，人為設(shè)立安全距離參數(shù)d和安全高度參數(shù)h；將田塊邊界多邊形組{Bi}向外偏置d(外邊界擴(kuò)大、內(nèi)邊界縮小)，得到偏置后多邊形組{B′i}；判斷轉(zhuǎn)移線段Ji與多邊形組{B′i}的相交性，若相交，則視為“危險(xiǎn)轉(zhuǎn)移過(guò)程”。

如圖6所示，對(duì)于田塊F0的某條候選轉(zhuǎn)移路徑Ji(對(duì)應(yīng)線段KiKj)來(lái)說(shuō)，因?yàn)榫€段KiKj與外邊界B0偏置后多邊形B′0存在交點(diǎn)C1和C2，故該轉(zhuǎn)移過(guò)程被視為危險(xiǎn)轉(zhuǎn)移過(guò)程。對(duì)于此類(lèi)轉(zhuǎn)移過(guò)程，實(shí)際操作時(shí)，飛機(jī)先從Ki點(diǎn)從作業(yè)高度h0拉升至安全高度h，轉(zhuǎn)移至Kj點(diǎn)后再下降至作業(yè)高度繼續(xù)作業(yè)。計(jì)算轉(zhuǎn)移路線長(zhǎng)度時(shí)在原計(jì)算值上加上2(h-h0)。上述過(guò)程中涉及到多邊形偏置算法、多邊形與線段間求交算法，也是計(jì)算機(jī)圖形學(xué)中經(jīng)典問(wèn)題[21]，限于篇幅問(wèn)題，不再贅述。

圖6 安全邊界相交性測(cè)試

1.7 航向優(yōu)化

作業(yè)飛行的總線路長(zhǎng)度和時(shí)間，除了與航線間調(diào)度次序有關(guān)，還與航線的方向有關(guān)。這里采用最小跨度法和步進(jìn)旋轉(zhuǎn)法進(jìn)行綜合優(yōu)化，前者可精確確定單一凸多邊形邊界田塊的最佳航向，后者則用于近似確定其他類(lèi)型(凹多邊形及孔洞多邊形)田塊的最佳航向。

區(qū)域跨度是指某一平面區(qū)域Q能夠剛好被某一對(duì)方向?yàn)棣鹊钠叫芯€夾住時(shí)平行線間的間距D。此時(shí)，平行線稱(chēng)之為支撐平行線，θ稱(chēng)之為跨度方向角，D稱(chēng)之為區(qū)域Q在θ方向上的跨度。分析可知，凸多邊形在任意方向上都有一對(duì)支撐平行線，且跨度值隨方向角變化而變化，按照最小跨度對(duì)應(yīng)方向布置填充線時(shí)數(shù)量最少，因此航線間轉(zhuǎn)移距離將最短[24]。對(duì)于凸多邊形而言，其跨度有3種形式，分別是點(diǎn)對(duì)式、點(diǎn)邊式和邊對(duì)式(圖7)。文獻(xiàn)[24]已證明凸多邊形區(qū)域的最小跨度方向一定出現(xiàn)在點(diǎn)邊式中。因此找出最小跨度方向角即為凸多邊形田塊的最優(yōu)航向角。

圖7 凸多邊形跨度的3種形式

對(duì)非單一凸多邊形田塊而言，可采用“步進(jìn)旋轉(zhuǎn)法”進(jìn)行近似求解。其本質(zhì)上是一種窮舉法，計(jì)算時(shí)，從0開(kāi)始、以dθ為步距，計(jì)算所有可能航向下的航線，比較線路總長(zhǎng)度，取最小值對(duì)應(yīng)的航向θ為最優(yōu)航向。

當(dāng)θ≠0時(shí)，通過(guò)兩次坐標(biāo)變換可簡(jiǎn)化計(jì)算過(guò)程。先將多邊形頂點(diǎn)繞其軸對(duì)齊包圍盒(Axis-aligned bounding box，AABB)中心點(diǎn)(xr0,yr0)順時(shí)針旋轉(zhuǎn)θ(正變換)得到旋轉(zhuǎn)后多邊形頂點(diǎn)，基于活性邊表法計(jì)算得到中間航線，再將航線端點(diǎn)(x0,y0)繞包圍盒中心逆時(shí)針旋轉(zhuǎn)θ(逆變換)即得到所需的真實(shí)航線的端點(diǎn)(x,y)。逆變換時(shí)計(jì)算公式為

(2)

而順時(shí)針變換時(shí)，只需將θ值取相反數(shù)即可。

2 實(shí)例仿真計(jì)算

前述全部算法過(guò)程在Visual C++ 6.0平臺(tái)上編碼實(shí)現(xiàn)，在Intel Corei7-3370 CPU、3.4 GHz主頻、8 GB內(nèi)存、Windows 7操作系統(tǒng)環(huán)境下，分別對(duì)4組典型復(fù)雜性的人工假想邊界和實(shí)際邊界在多組不同工作參數(shù)條件下進(jìn)行兩次試驗(yàn)，以測(cè)試算法穩(wěn)定性和計(jì)算效率。

實(shí)際田塊1的邊界利用Google Earth獲取并以KML文件格式導(dǎo)出，實(shí)際田塊2邊界通過(guò)無(wú)人機(jī)開(kāi)源軟件Mission Planner獲取并以其自定義的POLY格式導(dǎo)出，二者都經(jīng)過(guò)坐標(biāo)轉(zhuǎn)換，將地球經(jīng)緯度坐標(biāo)轉(zhuǎn)換成平面直角坐標(biāo)后再進(jìn)行計(jì)算測(cè)試[6]；假想田塊邊界利用CAD繪制并以DXF格式導(dǎo)入。計(jì)算過(guò)程中，算法對(duì)導(dǎo)入的邊界自動(dòng)進(jìn)行合規(guī)性檢查并進(jìn)行分組；對(duì)于單一邊界且為凸多邊形的田塊采用最小跨度法優(yōu)化航向，其他的情形則采用“步進(jìn)旋轉(zhuǎn)法”(步距取0.5°)優(yōu)化航向；采用貪婪算法進(jìn)行航線排序優(yōu)化，計(jì)算航線間轉(zhuǎn)移距離時(shí)，若不考慮障礙物則直接計(jì)算直線距離，如考慮障礙物影響，則對(duì)每一潛在轉(zhuǎn)移軌跡與安全邊界進(jìn)行安全檢查，對(duì)不安全轉(zhuǎn)移過(guò)程作高度方向上補(bǔ)償，轉(zhuǎn)移距離加上兩倍高度差(即安全高度與作業(yè)高度之差)。結(jié)果數(shù)據(jù)中路徑總長(zhǎng)度通過(guò)軌跡線段長(zhǎng)度求和得到，算法耗時(shí)通過(guò)GetTickCount()函數(shù)獲取算法運(yùn)行前后的系統(tǒng)時(shí)間后再求差得到，且測(cè)試時(shí)包括界面顯示更新相關(guān)操作。

2.1 不考慮邊界障礙物情況下的仿真試驗(yàn)

聚焦田塊邊界多邊形的復(fù)雜性，不考慮邊界上障礙物的影響或障礙物高度低于作業(yè)高度而不影響轉(zhuǎn)移過(guò)程安全，測(cè)試結(jié)果相關(guān)數(shù)據(jù)如表2所示。表中，優(yōu)化率ε為S2相對(duì)于S1的降低幅度，即ε=(S1-S2)/S1×100%，式中，S1為只進(jìn)行航線排序優(yōu)化而不進(jìn)行航向優(yōu)化(人工指定與邊界上某一邊的方向一致)時(shí)非工作路徑(即航線間跳轉(zhuǎn)路徑)的長(zhǎng)度，S2為同時(shí)進(jìn)行航向及航線排序優(yōu)化時(shí)非工作路徑的長(zhǎng)度。計(jì)算示例的部分結(jié)果截圖(因篇幅限制，只取其中部分典型結(jié)果)如圖8所示。

2.2 考慮邊界障礙物情況下的仿真試驗(yàn)

為進(jìn)一步擴(kuò)大算法的應(yīng)用范圍，假設(shè)上述4個(gè)田塊邊界上存在障礙物且高度大于作業(yè)高度，在前述同時(shí)進(jìn)行航向及航線排序優(yōu)化試驗(yàn)基礎(chǔ)上，繼續(xù)增加轉(zhuǎn)移過(guò)程的安全性判斷及處理算法的測(cè)試。設(shè)置作業(yè)高度為2 m，安全高度為6 m，安全距離為1 m，測(cè)試結(jié)果如表3及圖9所示。圖9較圖8增加了高度調(diào)整和安全邊界，分別采用黑色小圓圈和粉色多邊形表示。

3 討論

不考慮障礙物影響時(shí)，從表2中數(shù)據(jù)及圖8所示計(jì)算實(shí)例典型結(jié)果截圖可以看出，本文算法能夠處理各種復(fù)雜邊界形狀類(lèi)型的田塊，這些田塊的邊界形狀復(fù)雜程度明顯高于現(xiàn)有可查的相關(guān)文獻(xiàn)中的算法實(shí)例，同時(shí)對(duì)于作業(yè)方向的優(yōu)化是自動(dòng)完成的，有別于現(xiàn)有商用無(wú)人機(jī)自帶處理軟件(包括Mission Planner)需要用戶(hù)人工指定設(shè)置。

對(duì)比不進(jìn)行航向優(yōu)化而只進(jìn)行航線排序優(yōu)化的規(guī)劃結(jié)果，二者同時(shí)優(yōu)化時(shí)有效工作路徑(即航線)的總長(zhǎng)度基本不變，但對(duì)非工作路徑的優(yōu)化效果明顯，優(yōu)化幅度從23.04%到45.98%不等。這是因?yàn)橛行Чぷ髀窂揭采w作業(yè)區(qū)域，其總長(zhǎng)度與工作幅寬之積近似等于區(qū)域面積，而無(wú)效工作路徑為航線間跳轉(zhuǎn)軌跡，其總長(zhǎng)度與航向和航線間調(diào)度次序高度相關(guān)。進(jìn)一步，如不進(jìn)行航線排序優(yōu)化，則后果更加嚴(yán)重。如圖8g所示，同樣航向情況下，不排序情況下非工作路徑長(zhǎng)度為15 269.30 m，為表2中相同算例排序優(yōu)化結(jié)果(對(duì)應(yīng)圖8e)2 058.88 m的7.4倍，是有效工作路徑7 042.57 m的2.2倍。

表2 不考慮障礙物影響情況下的算法測(cè)試結(jié)果

圖8 不考慮障礙物影響情況下部分計(jì)算實(shí)例結(jié)果截圖

表3 考慮障礙物影響情況下的算法測(cè)試結(jié)果

圖9 考慮障礙物影響情況下部分優(yōu)化計(jì)算實(shí)例結(jié)果截圖

此外算法耗時(shí)隨著田塊數(shù)量和邊界頂點(diǎn)數(shù)目增加而增加，這是因?yàn)槌醪胶骄€計(jì)算和航向優(yōu)化都是以田塊為單元逐一進(jìn)行的，田塊數(shù)量的增加必然會(huì)增加優(yōu)化的工作量，而邊界頂點(diǎn)數(shù)目的增加則會(huì)增加邊界分組、多邊形凹凸性判斷及活性邊表法求交處理的工作量。同時(shí)算法耗時(shí)還會(huì)隨機(jī)器工作幅寬的減少和田塊面積的增加而增加，這是因?yàn)榉鶎捲叫?、田塊面積越大，航線的數(shù)量越多，需要求交的次數(shù)愈多、排序優(yōu)化TSP的規(guī)模越大。對(duì)于航向的優(yōu)化，基于最小跨度法的算法執(zhí)行效率明顯高于步進(jìn)旋轉(zhuǎn)法，但只適合于單一邊界且為凸多邊形的田塊(如假想田塊1)，通用性不如步進(jìn)旋轉(zhuǎn)法。算法總耗時(shí)從15 ms到19.2 s不等，考慮到計(jì)算優(yōu)化過(guò)程是作業(yè)前離線完成的，對(duì)實(shí)時(shí)性要求不高，因此本文算法的實(shí)時(shí)性特性完全能夠滿(mǎn)足無(wú)人機(jī)使用時(shí)對(duì)路徑規(guī)劃的及時(shí)性需求。

考慮障礙物影響時(shí)，對(duì)比表3及表2中計(jì)算結(jié)果，在同樣試驗(yàn)條件下，有效工作路徑總長(zhǎng)度幾乎沒(méi)有變化，而非有效作業(yè)路徑長(zhǎng)度普遍增加，主要原因是某些航線間轉(zhuǎn)移路徑中增加了高度調(diào)整的補(bǔ)償而且航線間排序可能因此而改變。此外，算法耗時(shí)的增加幅度較大，特別是在多邊形數(shù)目和頂點(diǎn)數(shù)較多且航線數(shù)量也較多時(shí)(如假想田塊2在工作幅寬2 m時(shí))，這是因?yàn)楹骄€排序時(shí)要對(duì)每一潛在航線間轉(zhuǎn)移過(guò)程進(jìn)行安全性判斷，極大增加了算法的工作量。好在算法的穩(wěn)定性很好，計(jì)算效率也基本滿(mǎn)足離線規(guī)劃的要求。

無(wú)人機(jī)實(shí)際作業(yè)過(guò)程中，還可能遇到因?yàn)槔m(xù)航和載重等原因?qū)е碌南钠钒葱柩a(bǔ)給、田塊間高度差和多機(jī)協(xié)同作業(yè)等問(wèn)題，這是路徑規(guī)劃工作中需要進(jìn)一步深入研究的內(nèi)容。

4 結(jié)論

(1)提出并實(shí)現(xiàn)一種對(duì)于田塊邊界形狀具有普適性意義的旋翼無(wú)人機(jī)作業(yè)路徑規(guī)劃算法，可以快速獲得凸多邊形、凹多邊形、帶孔洞多邊形或多個(gè)多邊形等各種復(fù)雜邊界田塊下的飛行作業(yè)軌跡。

(2)利用假想田塊、實(shí)際田塊的多組仿真測(cè)試試驗(yàn)表明，所設(shè)計(jì)的算法運(yùn)行穩(wěn)定可靠、效率高、優(yōu)化效果明顯，可滿(mǎn)足農(nóng)用無(wú)人機(jī)作業(yè)時(shí)對(duì)路徑規(guī)劃過(guò)程的準(zhǔn)確性、實(shí)時(shí)性和穩(wěn)定性等相關(guān)要求。在不考慮障礙物影響時(shí)算法耗時(shí)15 ms～19.2 s，相比于只進(jìn)行航線排序優(yōu)化的情況，同時(shí)進(jìn)行航向和航線排序優(yōu)化后，航線間轉(zhuǎn)移路徑總長(zhǎng)度下降了23.04%～45.98%，而考慮障礙物影響時(shí)的處理耗時(shí)也在離線應(yīng)用的可接受范圍內(nèi)。