南風(fēng)，曹光喬，李亦白，陳聰，劉東

(農(nóng)業(yè)農(nóng)村部南京農(nóng)業(yè)機(jī)械化研究所，南京市，210014)

0 引言

農(nóng)機(jī)調(diào)度已經(jīng)在農(nóng)業(yè)領(lǐng)域中得到廣泛的使用，例如收割機(jī)跨區(qū)收獲、無人機(jī)植保作業(yè)、農(nóng)作物測繪、監(jiān)測以及收割機(jī)與運(yùn)糧車響應(yīng)等農(nóng)業(yè)作業(yè)環(huán)節(jié)[1]。農(nóng)業(yè)機(jī)械的作業(yè)路徑很大程度上決定作業(yè)過程的質(zhì)量、效率和成本消耗[2]，因此農(nóng)業(yè)設(shè)備作業(yè)路徑的規(guī)劃和優(yōu)化工作具有重要意義。隨著人工智能技術(shù)的不斷發(fā)展，國內(nèi)外農(nóng)業(yè)正在經(jīng)歷一個重要的轉(zhuǎn)折點(diǎn)：傳統(tǒng)農(nóng)業(yè)的耕作過程正在逐步轉(zhuǎn)變?yōu)橐环N全新智能視角下的作業(yè)方式[3]。其中國外相關(guān)研究內(nèi)容較多，但更多針對大型農(nóng)場與大型地塊的農(nóng)業(yè)機(jī)械調(diào)度問題，由于我國的“大國小農(nóng)”國情，因此在國內(nèi)現(xiàn)階段的推廣應(yīng)用較少且適用性較差[4-5]。目前全覆蓋路徑規(guī)劃問題在國內(nèi)農(nóng)業(yè)領(lǐng)域的相關(guān)研究處于起步階段：一方面集中在植保無人機(jī)的飛行航跡規(guī)劃上；另一方面關(guān)于地面農(nóng)機(jī)的路徑規(guī)劃問題集中在聯(lián)合收割機(jī)在多個區(qū)域的轉(zhuǎn)移路徑上[6-8]，并不屬于同一區(qū)域的全覆蓋作業(yè)問題。徐博等[9-11]對多邊形邊界單田塊的無人機(jī)作業(yè)路徑提出了具體的算法并對多區(qū)域路徑轉(zhuǎn)移進(jìn)行了研究。王宇等[12]對無人機(jī)作業(yè)提出了一種基于柵格模型的路徑規(guī)劃算法。黃小毛等[2]基于復(fù)雜邊界田塊對無人機(jī)自主作業(yè)路徑進(jìn)行了研究。總體來看，關(guān)于農(nóng)機(jī)作業(yè)區(qū)域全覆蓋路徑規(guī)劃相關(guān)文獻(xiàn)仍然較少，而且地面與空中農(nóng)業(yè)設(shè)備相比[13]，地面農(nóng)機(jī)的作業(yè)不具備無人機(jī)的速度、通過性強(qiáng)等特點(diǎn)，地面農(nóng)機(jī)全覆蓋作業(yè)要時刻受到作業(yè)環(huán)境、少重復(fù)及遺漏面積等條件的制約，因此植保無人機(jī)路徑規(guī)劃方法雖然可以借鑒，但仍然需要考慮適合眾多地面環(huán)境、設(shè)備本身參數(shù)及具體作業(yè)流程的影響。

對于重要的小麥?zhǔn)斋@作業(yè)環(huán)節(jié)，聯(lián)合收割機(jī)通常在規(guī)則農(nóng)田區(qū)域內(nèi)沿著邊界長邊方向進(jìn)行收獲作業(yè)[14]。小麥播種時，大面積的農(nóng)田通常采用機(jī)械直播(條播)方式，中小面積通常還是人工均勻播撒，分布較為集中且均勻，因此對于不規(guī)則形狀地塊或受環(huán)境因素制約的不規(guī)則地塊，可以采用優(yōu)化行駛方向使小麥?zhǔn)崭顧C(jī)轉(zhuǎn)彎次數(shù)最少。該場景下的收割機(jī)全覆蓋作業(yè)路徑優(yōu)化對于不規(guī)則農(nóng)田的小麥播種、水稻播種、全覆蓋深耕等全覆蓋作業(yè)路徑規(guī)劃問題都具有一定的借鑒和推廣價值。

本文擬針對小麥?zhǔn)斋@環(huán)節(jié)聯(lián)合收割機(jī)作業(yè)時可能遇到的復(fù)雜類型田塊問題，提出一種基于作業(yè)優(yōu)化方向的全覆蓋路徑規(guī)劃算法，以獲得凸邊形、凹邊形等多邊形邊界地塊的作業(yè)路徑軌跡，為實(shí)際環(huán)境下復(fù)雜邊界地塊的農(nóng)機(jī)全覆蓋路徑規(guī)劃提供借鑒和理論支持。

1 優(yōu)化轉(zhuǎn)彎次數(shù)的全覆蓋調(diào)度

小麥聯(lián)合收割機(jī)田間收獲作業(yè)路徑規(guī)劃應(yīng)該滿足以下要求：有效工作路徑中達(dá)到農(nóng)田所有區(qū)域的全覆蓋，重復(fù)作業(yè)及遺漏作業(yè)面積盡可能??；聯(lián)合收割機(jī)轉(zhuǎn)彎次數(shù)盡可能少。

傳統(tǒng)的收割機(jī)田內(nèi)覆蓋收獲作業(yè)方式較為適合標(biāo)準(zhǔn)、規(guī)整的矩形農(nóng)田區(qū)域，通常表現(xiàn)為沿固定方向往復(fù)行走，該行走方向平行于區(qū)域最長邊界，又被稱為牛耕往復(fù)法，能夠取得最少的轉(zhuǎn)彎次數(shù)。而對于不規(guī)則形狀的農(nóng)田區(qū)域(非平行四邊形)，行走路線無法與區(qū)域大多數(shù)邊界平行或垂直，總存在一定的角度，因此會出現(xiàn)收割機(jī)轉(zhuǎn)彎次數(shù)較多的現(xiàn)象。

對于一般小麥?zhǔn)斋@作業(yè)環(huán)節(jié)，聯(lián)合收割機(jī)在規(guī)則農(nóng)田區(qū)域內(nèi)，沿區(qū)域邊界的最長邊方向進(jìn)行作業(yè)。但對于不規(guī)則邊界地塊，當(dāng)收割機(jī)基于不同方向進(jìn)行作業(yè)時，由于割幅相同、作業(yè)面積固定，整體行走的有效路徑長度是一定的，但是各方向受場地形狀與邊界限制，轉(zhuǎn)彎次數(shù)發(fā)生改變，在田內(nèi)轉(zhuǎn)彎次數(shù)增多則會造成耕作面積遺漏的風(fēng)險(xiǎn)，收割效率降低。因此基于不規(guī)則多邊形農(nóng)田區(qū)域的調(diào)度模型，需要優(yōu)化不同收獲方向使收割機(jī)轉(zhuǎn)彎次數(shù)最少。同時由于國內(nèi)收割機(jī)通常轉(zhuǎn)彎在田塊內(nèi)部，不必考慮收割機(jī)在田外的重復(fù)和多余覆蓋面積，因此行走方向不同直接影響了收割機(jī)的轉(zhuǎn)彎次數(shù)，且轉(zhuǎn)彎過程總是伴隨著收割機(jī)的減速和加速過程，增加作業(yè)時間和油耗?？梢缘贸觯涸谑斋@環(huán)節(jié)收割機(jī)的行走方向能夠影響轉(zhuǎn)彎次數(shù)從而增加收獲作業(yè)的成本，因此需盡可能減少轉(zhuǎn)彎次數(shù)，對田間收獲作業(yè)過程中收割機(jī)行走方向進(jìn)行優(yōu)化。

該場景的收割機(jī)調(diào)度優(yōu)化對于不規(guī)則農(nóng)田的小麥播種、水稻播種、全覆蓋深耕等環(huán)節(jié)的全覆蓋作業(yè)路徑場景都具有一定的適用性，能夠提高農(nóng)機(jī)作業(yè)效率，降低農(nóng)機(jī)油耗。收割機(jī)田內(nèi)作業(yè)路徑規(guī)劃適合于所有復(fù)雜邊界地塊，無論是農(nóng)田面積大小都能得到應(yīng)用，大型農(nóng)田的復(fù)雜邊界地塊優(yōu)化效果更加明顯。實(shí)際情況下，小麥聯(lián)合收割機(jī)收獲作業(yè)中會出現(xiàn)卸糧過程以及收割機(jī)在不同農(nóng)田的田外轉(zhuǎn)移過程，但上述環(huán)節(jié)并不影響收割機(jī)單獨(dú)田塊的轉(zhuǎn)彎次數(shù)，因此為了簡化處理過程，本研究不考慮收割機(jī)卸糧和往返農(nóng)田的非工作時間、不考慮收割機(jī)配置參數(shù)等無關(guān)因素，固定割幅同時僅探究不同行走方向?qū)D(zhuǎn)彎次數(shù)的影響。

因此小麥聯(lián)合收割機(jī)田內(nèi)作業(yè)場景可以描述為：當(dāng)一臺收割機(jī)采用牛耕往復(fù)法進(jìn)行全覆蓋收獲作業(yè)時，在不規(guī)則區(qū)域內(nèi)尋找最優(yōu)路徑方案使轉(zhuǎn)彎次數(shù)最少，提高收割效率、降低作業(yè)成本。

2 基于牛耕往復(fù)的調(diào)度規(guī)劃模型

本文針對常見的二維田塊，對于規(guī)則形狀農(nóng)田(如矩形農(nóng)田)，常用的區(qū)域覆蓋作業(yè)方式主要是牛耕往復(fù)法和內(nèi)外螺旋法，相關(guān)文獻(xiàn)[9-11]已經(jīng)證實(shí)采用內(nèi)外螺旋法會造成重復(fù)覆蓋和遺漏覆蓋的現(xiàn)象，與牛耕往復(fù)法轉(zhuǎn)彎次數(shù)相同，因此規(guī)則矩形采用牛耕往復(fù)方式進(jìn)行聯(lián)合收割機(jī)收獲作業(yè)更為合適。牛耕往復(fù)法如圖1所示。

圖1 規(guī)則區(qū)域的牛耕往復(fù)法Fig. 1 Full coverage method for a regular region

當(dāng)作業(yè)區(qū)域?yàn)橐?guī)則矩形，沿著區(qū)域一邊每隔二分之一割幅繪制掃描線，掃描線方向的參考線為矩形農(nóng)田長邊，從左向右排序，實(shí)線為收割機(jī)作業(yè)路徑，箭頭表示行走方向，可以快速獲得牛耕往復(fù)法的作業(yè)路徑，此時由于是規(guī)則矩形，收割機(jī)沿長邊行走距離達(dá)到最大值，因此所需轉(zhuǎn)彎次數(shù)最少，行走路徑最優(yōu)。當(dāng)作業(yè)區(qū)域?yàn)椴灰?guī)則多邊形時，利用簡單圖形幾何關(guān)系無法精確滿足路徑規(guī)劃的要求，因此本研究利用掃描線法獲得農(nóng)田路徑信息，結(jié)合改進(jìn)的角度尋優(yōu)算法進(jìn)行作業(yè)路徑的規(guī)劃。首先由GIS軟件提取作業(yè)區(qū)域的地圖信息，提取作業(yè)農(nóng)田邊界點(diǎn)經(jīng)緯度，構(gòu)建二維平面坐標(biāo)地圖，繪制包裹整個作業(yè)農(nóng)田且長款均為收割機(jī)割幅整數(shù)倍的矩形。對于收割機(jī)作業(yè)而言，用一組方向相同、間距與收割機(jī)割臺寬度相等的掃描線進(jìn)行掃描，掃描線與閉合多邊形的邊界交點(diǎn)所形成的線段就即為收割機(jī)路徑集合。根據(jù)地塊形狀和農(nóng)機(jī)路徑規(guī)劃情況的分析，可將指定作業(yè)區(qū)域收割機(jī)作業(yè)路徑規(guī)劃等價于多邊形區(qū)域與掃描線交點(diǎn)問題。

對于不規(guī)則多邊形，待作業(yè)區(qū)域?yàn)榘歼呅位蛲惯呅无r(nóng)田，農(nóng)田面積為S，收割機(jī)收割幅寬為d，收割機(jī)基于行走方向?yàn)棣葧r的行走路徑設(shè)置為集合L，路徑個數(shù)為n，其中第i條直線路徑設(shè)置為li，i=1，2，…，n。設(shè)置農(nóng)田多邊形邊界與掃描線(即收割機(jī)工作路徑)交點(diǎn)個數(shù)記為路徑節(jié)點(diǎn)N，則可以計(jì)算出掃描線個數(shù)為交點(diǎn)個數(shù)的一半即N/2。

該模型目標(biāo)數(shù)學(xué)表達(dá)式

Z=min(fθ(N/2-1))，?θ∈(0°，360°)

(1)

式中：fθ(N/2-1)——行走方向θ時，收割機(jī)工作路徑的轉(zhuǎn)彎次數(shù)最小值。

約束條件

(2)

式(2)表明收割機(jī)總路徑長度與割幅寬度的乘積，即最小覆蓋面積要大于農(nóng)田面積。

理論表明：當(dāng)收割機(jī)每次行走路線上割幅相鄰且不重合時即農(nóng)田面積覆蓋不重復(fù)且不遺漏，由于農(nóng)田總面積固定，因此收割機(jī)的有效行駛路徑長度是固定的。因此，本研究基于以下假設(shè)建立收割機(jī)路徑規(guī)劃模型：(1)不考慮作業(yè)農(nóng)田的多收割機(jī)調(diào)度及田內(nèi)障礙物；(2)收割機(jī)兩個相鄰路線中無農(nóng)田遺漏面積及重復(fù)覆蓋面積；(3)收割機(jī)始終按照牛耕往復(fù)法行駛，并保持同一工作方向，不考慮其他的轉(zhuǎn)彎類型。

3 轉(zhuǎn)彎次數(shù)求解及角度優(yōu)化算法

3.1 轉(zhuǎn)彎次數(shù)求解算法

3.1.1 凸多邊形掃描線算法

掃描線法又稱為有序邊表法，是用于表征和求解地塊數(shù)據(jù)集和位置信息的算法，是計(jì)算機(jī)圖形學(xué)中的經(jīng)典問題，在計(jì)算機(jī)動畫、3D打印和機(jī)器人路徑規(guī)劃等領(lǐng)域均有運(yùn)用。掃描線法能夠提高對每一組線段相交信息的求解效率和速度，因此可以用于收割機(jī)牛耕往復(fù)法的作業(yè)情景。

可以將不規(guī)則農(nóng)田區(qū)域的經(jīng)緯度坐標(biāo)轉(zhuǎn)換為二維平面坐標(biāo)系下的閉合多邊形區(qū)域[15]，已知不規(guī)則多邊形區(qū)域的頂點(diǎn)坐標(biāo)，將掃描線與x軸的夾角θ作為掃描線方向。θ=0°，即若干等間距水平掃描線等價于行走路徑，計(jì)算掃描線與多邊形各邊的交點(diǎn)坐標(biāo)，能夠計(jì)算每條路徑的長短，通過統(tǒng)計(jì)與多邊形各邊交點(diǎn)個數(shù)來計(jì)算路徑個數(shù)，從而計(jì)算轉(zhuǎn)彎次數(shù)。

掃描線算法的最重要特點(diǎn)是，無須計(jì)算多邊形所有邊與掃描線的交點(diǎn)，每條掃描線與多邊形相交位置僅僅存在幾條邊；同時相鄰的掃描線由于具有相同間隔，因此對于多邊形同一條邊，所有相交掃描線均有一定的步進(jìn)關(guān)系，可以證明相鄰掃描線的步進(jìn)量Δx為相交邊所在直線(Ax+By+C=0)斜率的倒數(shù)。

Δx=-B/A

(3)

若相鄰掃描線間距不是1而是Δt，則表達(dá)式

Δx=-B×Δt/A

(4)

因此，基于掃描線的重要幾何、數(shù)量特征，將掃描線與多邊形相交邊集中在一個數(shù)據(jù)表中，就形成了“有序邊表法”：儲存邊的數(shù)據(jù)結(jié)構(gòu)，以水平掃描線(方向角為0°)為例，每行信息由數(shù)組(Ymax，Xymin，Δx，next)組成，Ymax表示該多邊形邊的縱坐標(biāo)最大值即該邊上端的Y值；Xymin表示該邊縱坐標(biāo)最小值對應(yīng)的橫坐標(biāo)X值，即該邊下端點(diǎn)X坐標(biāo)；Δx表示沿該邊方向相鄰掃描線之間的水平增量(X方向增量)，next表示下一條相交邊。建立邊表時，先按照下端點(diǎn)縱坐標(biāo)值(即從下到上的方向)對多邊形所有邊進(jìn)行分類，再將同一組的各邊按照下端點(diǎn)橫坐標(biāo)值進(jìn)行增量排序，若橫坐標(biāo)相同，按照Δx大小增量排序。具體實(shí)現(xiàn)過程見相關(guān)文獻(xiàn)[2]，本節(jié)不再贅述。

掃描線算法步驟如圖2所示。

圖2 掃描線算法流程圖Fig. 2 Flow chart of scanning line algorithm

3.1.2 凹多邊形假想?yún)^(qū)域求解算法

掃描線算法能夠滿足求解復(fù)雜凸多邊形邊界的收割機(jī)轉(zhuǎn)彎次數(shù)，但是實(shí)際環(huán)境中，作業(yè)農(nóng)田往往因?yàn)橹車亍淠?、建筑等出現(xiàn)相鄰邊界形成內(nèi)角大于180°的凹邊形區(qū)域。因此本研究在掃描線求解凸多邊形基礎(chǔ)上改進(jìn)并設(shè)計(jì)了基于凸邊形填補(bǔ)方法的幾何算法對凹邊形區(qū)域進(jìn)行行走方向的尋優(yōu)計(jì)算。主要步驟如下。

步驟1：依次輸入凹邊形區(qū)域S0各邊頂點(diǎn)，并選擇頂角大于180°的區(qū)域頂點(diǎn)o兩側(cè)相鄰頂點(diǎn)所成假想直線l與除該頂點(diǎn)外凹邊形所有頂點(diǎn)共同組成凸邊形區(qū)域S1，同時該直線與該頂點(diǎn)o相鄰兩邊界組成假想三角形區(qū)域S2。

步驟2：設(shè)置收割機(jī)作業(yè)參數(shù)，以及行走方向θ=0°，旋轉(zhuǎn)步進(jìn)量Δθ=1°。

步驟3：使用掃描線算法(參見3.3.1節(jié)算法步驟)分別計(jì)算行走方向θ時，凸邊形區(qū)域S1、S2對應(yīng)的各邊路徑節(jié)點(diǎn)個數(shù)n1、n2，同時記錄假想?yún)^(qū)域S2邊界的直線l節(jié)點(diǎn)個數(shù)為nl。

步驟4：計(jì)算凹邊形區(qū)域S0轉(zhuǎn)彎次數(shù)，N(S0)=(n1+n2-2nl)/2-1。

步驟5：令θ=θ+Δθ。

步驟6：當(dāng)θ>180°時，停止迭代并輸出最小N(S0)對應(yīng)的θ值。

該假想?yún)^(qū)域算法的示意如圖3所示。

圖3 假想凸邊形區(qū)域組成Fig. 3 Composition of farmland in an imaginary convex region

如圖3所示，當(dāng)不規(guī)則區(qū)域圖形為凹多邊形時，可以通過填補(bǔ)的形式，將凹邊形的相鄰兩條邊(夾角大于180°)所形成的區(qū)域直接用一條假想線連接頂點(diǎn)，從而形成凸邊形區(qū)域，因此該凸邊形就由原先凹邊形與假想?yún)^(qū)域凸邊形組成。原凹邊形由b、c邊以及剩余邊集合d組成，記為多邊形No.1；組合凸邊形由假想線a(圖3中虛線)與邊集合d組成，記為多邊形No.2；假想?yún)^(qū)域所形成的也是凸邊形，由假想線a、原邊b、c形成，記為多邊形No.3。對于收割機(jī)工作路徑來說，轉(zhuǎn)彎次數(shù)與路徑線個數(shù)有關(guān)，可以通過區(qū)域邊與路線交點(diǎn)數(shù)量計(jì)算得到，這里將多邊形邊與掃描線交點(diǎn)記為路徑節(jié)點(diǎn)，數(shù)量用N表示，假設(shè)區(qū)域各邊頂點(diǎn)不存在路徑節(jié)點(diǎn)，可以得到

(5)

通過凸多邊形掃描線算法可以得到凸邊形(No.2與No.3)各邊路徑節(jié)點(diǎn)數(shù)量。因此可以推出原凹變形區(qū)域節(jié)點(diǎn)數(shù)量，得到關(guān)于N(No.1)與N(a)的表達(dá)式如式(6)所示。

N(No.1)=N(No.3)+N(No.2)-2N(a)

(6)

因此已知原凹邊形邊界信息，形成的假想兩個凸邊形邊界信息通過凸邊形算法求解得到轉(zhuǎn)彎次數(shù)及假想邊界與路徑的相交次數(shù)，就可以獲得原凹邊形的轉(zhuǎn)彎次數(shù)。

(7)

式中：n——區(qū)域所有邊界或指定邊界線上的路徑節(jié)點(diǎn)數(shù)量。

若實(shí)際復(fù)雜環(huán)境下的農(nóng)田作業(yè)區(qū)域可以轉(zhuǎn)換為不規(guī)則凸、凹邊形區(qū)域，則通過轉(zhuǎn)彎次數(shù)求解算法可以得到相應(yīng)結(jié)果。

3.2 最優(yōu)作業(yè)角度搜索算法

對單一多邊形田塊而言，可以采用“旋轉(zhuǎn)法”進(jìn)行近似求解，本質(zhì)上屬于窮舉算法，從0°開始，以1°為步長，計(jì)算所有可能的行走方向的路徑，比較所有路線的轉(zhuǎn)彎次數(shù)N，取其最小者對應(yīng)的方向值為最優(yōu)行走方向。當(dāng)θ≠0時，通過坐標(biāo)變化可簡化計(jì)算過程，將多邊形頂點(diǎn)繞坐標(biāo)原點(diǎn)順時針旋轉(zhuǎn)θ(正變換)得到旋轉(zhuǎn)后的多邊形頂點(diǎn)，基于掃描線法計(jì)算得到中間路徑，再將路徑線端點(diǎn)(x0，y0)繞著矩形原點(diǎn)逆時針旋轉(zhuǎn)θ(逆變換)即得到真實(shí)路徑的端點(diǎn)(x，y)。

正變換

θ=-θ*(互為相反數(shù))

(8)

逆變換

(9)

總體來看，本研究通過旋轉(zhuǎn)步進(jìn)搜索算法，再結(jié)合多邊形轉(zhuǎn)彎次數(shù)求解算法，便能夠得到基于最優(yōu)行走方向的復(fù)雜多邊形最優(yōu)路徑軌跡。具體算法步驟如圖4所示。

圖4 算法流程圖Fig. 4 Algorithm flowchart

4 算例驗(yàn)證

上述全部算法過程在Window10系統(tǒng)環(huán)境下編碼實(shí)現(xiàn)，在同一工作參數(shù)條件下進(jìn)行多次試驗(yàn)，測試算法計(jì)算尋優(yōu)結(jié)果。本研究利用假想田塊邊界，轉(zhuǎn)化為二維平面直角坐標(biāo)，對單一多邊形邊界的田塊采用“旋轉(zhuǎn)法”優(yōu)化行走方向。轉(zhuǎn)彎次數(shù)通過計(jì)算掃描軌跡線個數(shù)得到，掃描線數(shù)目通過計(jì)算多邊形各邊交點(diǎn)數(shù)目(即路徑節(jié)點(diǎn))總和得到。一般小型聯(lián)合收割機(jī)割臺寬度在1.5～3 m，因此根據(jù)常見聯(lián)合收割機(jī)型號及中小型農(nóng)田區(qū)域面積，本文取收割機(jī)的工作寬幅為2.5 m。

4.1 凸多邊形作業(yè)路徑優(yōu)化方案

仿真算例轉(zhuǎn)換至笛卡爾坐標(biāo)系中，水平方向與x軸重合，農(nóng)田邊界信息及頂點(diǎn)坐標(biāo)如圖5所示，通過凸邊形掃描線算法求解，得到最優(yōu)作業(yè)角度為100°。為驗(yàn)證算法計(jì)算結(jié)果，使行走方向與水平方向夾角分別為0°、45°、90°、135°，沿區(qū)域最長邊方向29.5°，以及算法得出最優(yōu)角度100°的凸多邊形區(qū)域農(nóng)田填充掃描線如圖6所示。

圖5 凸邊形區(qū)域農(nóng)田Fig. 5 Cropland in single area with convex edge

(a) θ=0°

(b) θ=45°

(c) θ=90°

(d) θ=135°

(e) θ=29.5°

(f) θ=100°圖6 凸邊形區(qū)域不同行走方向路徑軌跡線Fig. 6 Path trajectories of different operating directions in the convex edge area

當(dāng)行走方向與水平夾角θ=100°時，該區(qū)域田塊的作業(yè)方案最佳，作業(yè)進(jìn)入點(diǎn)坐標(biāo)為(168，41)，作業(yè)路徑節(jié)點(diǎn)為96個，收割機(jī)轉(zhuǎn)彎次數(shù)為47次。指標(biāo)結(jié)果如表1所示：與基于其他方向的作業(yè)路徑方案相比，當(dāng)行走方向θ=100°時，同一收割機(jī)比行走方向?yàn)?°、135°轉(zhuǎn)彎次數(shù)少13次，優(yōu)化率達(dá)21.67%，比行走方向?yàn)?5°轉(zhuǎn)彎次數(shù)少9次，優(yōu)化率達(dá)16.07%、比行走方向?yàn)?0°少3次，優(yōu)化率為6%、比作業(yè)沿長邊方向?yàn)?9.5°轉(zhuǎn)彎次數(shù)少6次，優(yōu)化率為11.32%，因此可以得出該算法能夠有效處理基于不同角度尋優(yōu)的凸多邊形農(nóng)田的收割機(jī)調(diào)度規(guī)劃，并得出全局最優(yōu)行走方向。

表1 基于不同角度的凸多邊形農(nóng)田指標(biāo)Tab. 1 Indicators of convex polygons based on different operating directions

4.2 凹多邊形田內(nèi)作業(yè)路徑優(yōu)化方案

凹邊形仿真算例的邊界信息如圖7所示，對凹邊形進(jìn)行填充的區(qū)域已通過圖3表示，其中a為相鄰內(nèi)角大于180°的邊界(b、c)頂點(diǎn)形成的假想線，d為原凹邊形其余邊界，最長邊與橫軸夾角為29.5°。由第3節(jié)凹邊形作業(yè)角度優(yōu)化算法原理可知，關(guān)于N(No.1)與N(a)的表達(dá)式為N(No.1)=N(No.3)+N(No.2)-2N(a)。

圖7 不規(guī)則凹邊形區(qū)域農(nóng)田Fig. 7 Farmland with irregular concave edge area

通過凸多邊形掃描線算法可以得到凸邊形(No.2與No.3)各邊路徑節(jié)點(diǎn)數(shù)量。N(a)可以通過掃描線算法得到。因此通過算法求解原凹邊形區(qū)域填充掃描線，行走方向與水平方向夾角分別為0°、45°、90°、135°，沿區(qū)域最長邊方向29.5°，以及算法得出假想凸多邊形區(qū)域最優(yōu)角度100°，如圖8所示。

從圖8可以看出，θ=100°是凸多邊形No.2的最優(yōu)作業(yè)角度，但是對于去掉假想?yún)^(qū)域(No.3)后的實(shí)際凹邊形農(nóng)田(No.1)來說，θ=100°的轉(zhuǎn)彎次數(shù)要多于45°、90°、29.5°，即凹邊形農(nóng)田最優(yōu)作業(yè)方向并不能通過填補(bǔ)的假想凸邊形尋優(yōu)計(jì)算直接獲得。因此，依據(jù)3.2節(jié)的旋轉(zhuǎn)搜索算法，在Window10系統(tǒng)上設(shè)置旋轉(zhuǎn)步長為1°，旋轉(zhuǎn)次數(shù)為180次，得到0°～180°中轉(zhuǎn)彎次數(shù)最少的行走方向，即最優(yōu)作業(yè)方向。凹邊形農(nóng)田區(qū)域旋轉(zhuǎn)算法求解過程的收割機(jī)轉(zhuǎn)彎次數(shù)如圖9所示。

(a) θ=0°

(b) θ=45°

(c) θ=90°

(d) θ=135°

(f) θ=100°圖8 假想?yún)^(qū)域的掃描線軌跡Fig. 8 Scan line trajectories of imaginary regions

圖9 不同角度下凹多邊形區(qū)域的轉(zhuǎn)彎次數(shù)Fig. 9 Number of turns in a concave polygon area with different angles

通過圖9可知，當(dāng)行走方向?yàn)?0°時，凹邊形區(qū)域轉(zhuǎn)彎次數(shù)最少，因此對于凹邊形區(qū)域而言，收割機(jī)保持與水平夾角為90°的行走方向?yàn)樽顑?yōu)作業(yè)方案。

凹邊形區(qū)域不同角度的指標(biāo)結(jié)果如表2所示：與基于其他方向的作業(yè)路徑方案相比，當(dāng)行走方向θ=90°時，同一收割機(jī)比行走方向?yàn)?00°、135°轉(zhuǎn)彎次數(shù)少10次，優(yōu)化率達(dá)16.7%，比行走方向?yàn)?°轉(zhuǎn)彎次數(shù)少20次，優(yōu)化率達(dá)28.6%、比行走方向?yàn)?5°少6次，優(yōu)化率達(dá)10.7%、比作業(yè)沿邊界最長邊方向?yàn)?9.5°轉(zhuǎn)彎次數(shù)少3次，優(yōu)化率達(dá)5.66%，因此可以得出，基于填補(bǔ)方法的混合優(yōu)化算法能夠有效處理基于不同角度的凹多邊形農(nóng)田的收割機(jī)調(diào)度規(guī)劃，并得出全局較優(yōu)的路徑規(guī)劃方案。

表2 基于不同角度的凹邊形區(qū)域指標(biāo)Tab. 2 Indexes of concave edge area based on different angles

5 結(jié)論

1) 單臺聯(lián)合收割機(jī)田間作業(yè)通常采用全覆蓋路徑規(guī)劃，主要針對規(guī)則區(qū)域進(jìn)行牛耕往復(fù)法，對于不規(guī)則區(qū)域，如凹、凸多邊形農(nóng)田不同行走方向總會造成收割機(jī)轉(zhuǎn)彎次數(shù)增加，影響作業(yè)質(zhì)量、油耗與工作效率。因此本文針對不規(guī)則區(qū)域的單臺收割機(jī)作業(yè)角度建立調(diào)度模型與設(shè)計(jì)優(yōu)化求解算法，實(shí)現(xiàn)轉(zhuǎn)彎次數(shù)最少的田間行駛路徑規(guī)劃方案。結(jié)合仿真算例驗(yàn)證結(jié)果，所提出的優(yōu)化行走方向算法針對不規(guī)則多邊形區(qū)域而言能夠有效優(yōu)化收割機(jī)行走方向：在凸邊形農(nóng)田仿真案例中，該算法求解的最優(yōu)作業(yè)角度是100°，該方向路徑規(guī)劃在轉(zhuǎn)彎次數(shù)上要比沿區(qū)域最長邊(方向29.5°)牛耕往復(fù)的路徑軌跡優(yōu)化程度為11.32%，比普通方向(行走方向0°、45°、90°、135°等)優(yōu)化程度達(dá)到6%～21.7%；在凹邊形農(nóng)田仿真案例中，該算法求解的最優(yōu)作業(yè)路徑方向是90°，比沿邊界最長邊(方向29.5°)路徑的優(yōu)化程度為5.66%，比其他方向(行走方向0°、45°、135°、100°等)的優(yōu)化程度達(dá)到10%～28.6%。

2) 本研究設(shè)計(jì)了凹凸多邊形轉(zhuǎn)彎次數(shù)求解算法并結(jié)合了旋轉(zhuǎn)搜索算法以獲得復(fù)雜邊界區(qū)域最優(yōu)行走方向，形成該區(qū)域小麥?zhǔn)崭顧C(jī)的工作路徑方案。能夠進(jìn)一步推廣至實(shí)際復(fù)雜邊界的農(nóng)田區(qū)域，適用于全覆蓋路徑規(guī)劃的轉(zhuǎn)彎次數(shù)優(yōu)化環(huán)節(jié)，如小麥?zhǔn)崭顧C(jī)收獲作業(yè)、小麥、水稻等播種、全覆蓋深耕等具體環(huán)節(jié)，為減少農(nóng)機(jī)作業(yè)轉(zhuǎn)彎次數(shù)，提高作業(yè)效率等提供了有效的決策依據(jù)。

3) 針對全覆蓋路徑行走方向優(yōu)化問題，本研究基于單個收割機(jī)對單獨(dú)農(nóng)田區(qū)域的作業(yè)路徑規(guī)劃，并未考慮多收割機(jī)協(xié)同作業(yè)方式，未來可以通過大型農(nóng)田區(qū)域劃分的方法解決多機(jī)協(xié)同問題；同時本研究基于復(fù)雜凹邊形進(jìn)行假想?yún)^(qū)域填補(bǔ)形成簡單凸邊形，最終獲得轉(zhuǎn)彎次數(shù)，若作業(yè)區(qū)域含有多個凹形區(qū)域，可以利用分割而非填補(bǔ)的思想對不規(guī)則凹邊形進(jìn)行區(qū)域劃分，從而將整個不規(guī)則區(qū)域轉(zhuǎn)化為若干凸邊形作業(yè)區(qū)域，每個區(qū)域可以產(chǎn)生不同行走方向的優(yōu)化路線，從而達(dá)到整體最優(yōu)效果。因此未來研究方向可以集中在對復(fù)雜邊界環(huán)境的區(qū)域劃分方式及優(yōu)化求解等。