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

(1.華中農(nóng)業(yè)大學(xué)工學(xué)院，武漢 430070；2.愛荷華州立大學(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ī)器相比，無人機(jī)空中作業(yè)具有通過性強(qiáng)、效率高、精度高等優(yōu)點(diǎn)，特別適合于植保、遙感、巡查和播撒等作業(yè)環(huán)節(jié)。作業(yè)路徑是無人機(jī)自主作業(yè)時(shí)機(jī)器軌跡控制的跟蹤目標(biāo)，在很大程度上決定機(jī)器作業(yè)過程的作業(yè)質(zhì)量、效率和總消耗。因此無人機(jī)作業(yè)路徑的規(guī)劃和優(yōu)化工作具有重要意義。

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

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

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

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

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

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

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

本文只針對(duì)常見的二維田塊，用一組多邊形分別代表田塊的外邊界和內(nèi)邊界，且外邊界以逆時(shí)針方向、內(nèi)邊界以順時(shí)針方向依次存儲(chǔ)各頂點(diǎn)(如圖1所示)。通過分析可知采用多邊形表征田塊區(qū)域時(shí)具有以下特點(diǎn)：每個(gè)田塊有且只有一個(gè)外邊界，而可能沒有也可能有多個(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ù)為輸入條件，以獲得旋翼無人機(jī)飛行作業(yè)路徑為目標(biāo)，本文設(shè)計(jì)的算法基本流程如圖2所示。

圖2 算法流程圖

1.3 邊界合規(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)行。然后，通過分組算法[21]確定多邊形之間的關(guān)系，即從數(shù)據(jù)結(jié)構(gòu)上建立田塊的概念。如從圖3a中輸入的B0、B1、B23個(gè)邊界多邊形，通過分析它們之間的包含關(guān)系，分組后分別建立F0(圖1)和F1(圖3b)2個(gè)獨(dú)立的田塊區(qū)域。

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

1.4 填充線求解

多邊形填充是計(jì)算機(jī)圖形學(xué)中的經(jīng)典問題[22]，在計(jì)算機(jī)動(dòng)畫、數(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}，再通過減法布爾運(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 孔洞多邊形填充線的求解過程

1.5 活性邊表法

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

作為存儲(chǔ)多邊形各邊的一種數(shù)據(jù)結(jié)構(gòu)，邊表用來表示對(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ì)所有邊作分類和排序，再將同一組中的邊按下端點(diǎn)X坐標(biāo)遞增的順序進(jìn)行排序，X坐標(biāo)還相同的按dX遞增的順序進(jìn)行排序。圖4b中多邊形的邊表如表1第2列所示(表中“→”表示指針next)。

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

對(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ì)，依此類推，每一對(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中滿足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)距離和遍歷過程的總軌跡長(zhǎng)度。若將每一條航線視為一個(gè)城市，這將是一個(gè)典型的旅行商問題(TSP)，屬于NP-hard。本文主要采取文獻(xiàn)[5]中的貪婪算法進(jìn)行求解，該算法屬于組合優(yōu)化問題的常規(guī)求解算法，雖然所得結(jié)果不一定為最優(yōu)，但算法穩(wěn)定可靠，具有實(shí)用性。具體實(shí)現(xiàn)過程見相關(guān)文獻(xiàn)，此處不再贅述。

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

采用“安全邊界相交性測(cè)試法”來判別某條候選轉(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)移過程”。

如圖6所示，對(duì)于田塊F0的某條候選轉(zhuǎn)移路徑Ji(對(duì)應(yīng)線段KiKj)來說，因?yàn)榫€段KiKj與外邊界B0偏置后多邊形B′0存在交點(diǎn)C1和C2，故該轉(zhuǎn)移過程被視為危險(xiǎn)轉(zhuǎn)移過程。對(duì)于此類轉(zhuǎn)移過程，實(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)。上述過程中涉及到多邊形偏置算法、多邊形與線段間求交算法，也是計(jì)算機(jī)圖形學(xué)中經(jīng)典問題[21]，限于篇幅問題，不再贅述。

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

1.7 航向優(yōu)化

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

區(qū)域跨度是指某一平面區(qū)域Q能夠剛好被某一對(duì)方向?yàn)棣鹊钠叫芯€夾住時(shí)平行線間的間距D。此時(shí)，平行線稱之為支撐平行線，θ稱之為跨度方向角，D稱之為區(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開始、以dθ為步距，計(jì)算所有可能航向下的航線，比較線路總長(zhǎng)度，取最小值對(duì)應(yīng)的航向θ為最優(yōu)航向。

當(dāng)θ≠0時(shí)，通過兩次坐標(biāo)變換可簡(jiǎn)化計(jì)算過程。先將多邊形頂點(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ì)算

前述全部算法過程在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邊界通過無人機(jī)開源軟件Mission Planner獲取并以其自定義的POLY格式導(dǎo)出，二者都經(jīng)過坐標(biāo)轉(zhuǎn)換，將地球經(jīng)緯度坐標(biāo)轉(zhuǎn)換成平面直角坐標(biāo)后再進(jìn)行計(jì)算測(cè)試[6]；假想田塊邊界利用CAD繪制并以DXF格式導(dǎo)入。計(jì)算過程中，算法對(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)移過程作高度方向上補(bǔ)償，轉(zhuǎn)移距離加上兩倍高度差(即安全高度與作業(yè)高度之差)。結(jié)果數(shù)據(jù)中路徑總長(zhǎng)度通過軌跡線段長(zhǎng)度求和得到，算法耗時(shí)通過GetTickCount()函數(shù)獲取算法運(yùn)行前后的系統(tǒng)時(shí)間后再求差得到，且測(cè)試時(shí)包括界面顯示更新相關(guān)操作。

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

聚焦田塊邊界多邊形的復(fù)雜性，不考慮邊界上障礙物的影響或障礙物高度低于作業(yè)高度而不影響轉(zhuǎn)移過程安全，測(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)移過程的安全性判斷及處理算法的測(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ù)雜邊界形狀類型的田塊，這些田塊的邊界形狀復(fù)雜程度明顯高于現(xiàn)有可查的相關(guān)文獻(xiàn)中的算法實(shí)例，同時(shí)對(duì)于作業(yè)方向的優(yōu)化是自動(dòng)完成的，有別于現(xiàn)有商用無人機(jī)自帶處理軟件(包括Mission Planner)需要用戶人工指定設(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ū)域面積，而無效工作路徑為航線間跳轉(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)化過程是作業(yè)前離線完成的，對(duì)實(shí)時(shí)性要求不高，因此本文算法的實(shí)時(shí)性特性完全能夠滿足無人機(jī)使用時(shí)對(duì)路徑規(guī)劃的及時(shí)性需求。

考慮障礙物影響時(shí)，對(duì)比表3及表2中計(jì)算結(jié)果，在同樣試驗(yàn)條件下，有效工作路徑總長(zhǎng)度幾乎沒有變化，而非有效作業(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)移過程進(jìn)行安全性判斷，極大增加了算法的工作量。好在算法的穩(wěn)定性很好，計(jì)算效率也基本滿足離線規(guī)劃的要求。

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

4 結(jié)論

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

(2)利用假想田塊、實(shí)際田塊的多組仿真測(cè)試試驗(yàn)表明，所設(shè)計(jì)的算法運(yùn)行穩(wěn)定可靠、效率高、優(yōu)化效果明顯，可滿足農(nóng)用無人機(jī)作業(yè)時(shí)對(duì)路徑規(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)。