陳 凱 解印山 李彥明 劉成良 莫錦秋

(上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院， 上海 200240)

0 引言

路徑規(guī)劃是現(xiàn)代智能農(nóng)業(yè)機(jī)械實(shí)現(xiàn)自主導(dǎo)航移動(dòng)和作業(yè)的三大關(guān)鍵技術(shù)之一[1]，決定農(nóng)機(jī)工作總消耗并影響實(shí)際農(nóng)機(jī)工作的作業(yè)效率和作業(yè)質(zhì)量。

農(nóng)機(jī)路徑規(guī)劃可以分為全局路徑規(guī)劃與局部路徑規(guī)劃[2]。其中全局路徑規(guī)劃是在作業(yè)環(huán)境已知的情況下，基于完全先驗(yàn)信息的路徑規(guī)劃，一般在農(nóng)機(jī)作業(yè)前規(guī)劃。局部路徑規(guī)劃是農(nóng)機(jī)作業(yè)中采用傳感器感知作業(yè)區(qū)域環(huán)境信息，以此進(jìn)行的實(shí)時(shí)路徑規(guī)劃。全局路徑規(guī)劃常以減少作業(yè)總距離或時(shí)間消耗、提升作業(yè)覆蓋率、提高農(nóng)機(jī)作業(yè)效率[3]作為優(yōu)化目標(biāo)，優(yōu)化方法可分為全局覆蓋路徑規(guī)劃和全局點(diǎn)到點(diǎn)路徑規(guī)劃。全局覆蓋路徑規(guī)劃主要以往復(fù)遍歷平行作物行的方式進(jìn)行作業(yè)[4-8]，通常在處理地塊和生成作物行后，根據(jù)傳統(tǒng)遍歷方式確定軌跡。全局點(diǎn)到點(diǎn)路徑規(guī)劃是在已知作業(yè)區(qū)域環(huán)境信息后，規(guī)劃從起點(diǎn)到目標(biāo)點(diǎn)可行的無(wú)碰撞路徑，目前比較成熟的算法有A*算法、蟻群優(yōu)化算法、遺傳算法、模擬退火算法和粒子群優(yōu)化算法等[9-13]，這些算法可以根據(jù)不同優(yōu)化目標(biāo)進(jìn)行起始點(diǎn)間最優(yōu)路徑搜索。

全局覆蓋路徑規(guī)劃多針對(duì)地塊邊界約束和作物行約束，但大多使用傳統(tǒng)的梭行、套行、開壟等[14-16]方式進(jìn)行遍歷，無(wú)法針對(duì)不同的農(nóng)機(jī)轉(zhuǎn)彎參數(shù)進(jìn)行有效處理，對(duì)不同地塊邊界條件適用性較低。而全局點(diǎn)到點(diǎn)路徑規(guī)劃可以通過(guò)柵格化地塊后，利用啟發(fā)式算法等得到全局最優(yōu)解，但僅限于多點(diǎn)間路徑[17-19]，無(wú)法處理作物行約束，無(wú)法適用于需要往復(fù)遍歷作物行的農(nóng)業(yè)機(jī)械。

農(nóng)業(yè)機(jī)械實(shí)現(xiàn)自主作業(yè)時(shí)需解決多種約束的影響[20]，處理好各項(xiàng)約束才能保證農(nóng)機(jī)成功且高效地完成預(yù)定作業(yè)。常見的約束有農(nóng)機(jī)地頭轉(zhuǎn)彎方式、地塊邊界、作物行行線、障礙物等。農(nóng)機(jī)全覆蓋路徑規(guī)劃可具體表述成基于以上的多約束條件下，以距離/時(shí)間/總能源代價(jià)為優(yōu)化目標(biāo)的路徑規(guī)劃。

農(nóng)機(jī)作業(yè)總代價(jià)中作業(yè)代價(jià)與地頭轉(zhuǎn)彎代價(jià)占絕大部分，其余如出入地塊等代價(jià)可忽略。當(dāng)作業(yè)區(qū)域與作物行間距固定時(shí)，作業(yè)代價(jià)基本一致，因此該問(wèn)題可近似為作業(yè)轉(zhuǎn)彎代價(jià)的最優(yōu)化問(wèn)題。

本文提出一種考慮多約束的農(nóng)機(jī)全覆蓋路徑規(guī)劃算法，該算法將在量化不同地頭轉(zhuǎn)彎方式帶來(lái)的代價(jià)，處理地塊邊界、障礙物等約束后，針對(duì)多種優(yōu)化目標(biāo)生成最優(yōu)作物行。同時(shí)通過(guò)提出基于模擬退火和行數(shù)拆解與遍歷合成的混合規(guī)則遍歷順序算法，實(shí)現(xiàn)大規(guī)模農(nóng)機(jī)作業(yè)路徑規(guī)劃。

1 規(guī)劃算法流程

本文提出的算法流程如圖1所示，可分為多作業(yè)約束處理與最優(yōu)遍歷順序求解兩部分。作業(yè)約束主要包括農(nóng)機(jī)動(dòng)力學(xué)參數(shù)約束、農(nóng)藝要求約束及地塊邊界條件約束，有效處理各約束可以保證作業(yè)軌跡按農(nóng)藝要求正確完成作業(yè)。對(duì)于最優(yōu)遍歷順序的求解，本文提出了基于模擬退火的混合規(guī)則求解方法，在大規(guī)模農(nóng)田作業(yè)時(shí)對(duì)作業(yè)遍歷順序進(jìn)行有效優(yōu)化，降低各項(xiàng)作業(yè)代價(jià)。本文將二者進(jìn)行結(jié)合，在處理約束的基礎(chǔ)上優(yōu)化了作業(yè)遍歷順序，實(shí)現(xiàn)了多約束下農(nóng)機(jī)的全覆蓋最優(yōu)效率路徑規(guī)劃。

圖1 全遍歷作業(yè)路徑規(guī)劃流程圖Fig.1 Process of coverage path planning

2 路徑規(guī)劃中的各種約束

2.1 地頭轉(zhuǎn)彎方式

農(nóng)機(jī)的最小轉(zhuǎn)彎半徑與轉(zhuǎn)彎間距之間的關(guān)系決定了其在地頭換行時(shí)的轉(zhuǎn)彎方式，一般可分為如圖2所示的弓形、梨形、魚尾形。圖2中陰影部分為作業(yè)區(qū)域。當(dāng)轉(zhuǎn)彎半徑為r，作業(yè)寬幅為w的農(nóng)機(jī)在相鄰作物行間換行時(shí)，由幾何關(guān)系可知，當(dāng)r小于或等于w/2時(shí)選擇弓形轉(zhuǎn)彎；當(dāng)r大于w/2時(shí)選用梨形或魚尾形轉(zhuǎn)彎，兩者可相互替代。

魚尾形轉(zhuǎn)彎雖然消耗小于梨形轉(zhuǎn)彎方式，但過(guò)程包含倒車操作，對(duì)農(nóng)機(jī)的轉(zhuǎn)彎性能要求高，難度大，因此本文中路徑算法優(yōu)先考慮弓形、梨形轉(zhuǎn)彎方式。

農(nóng)機(jī)轉(zhuǎn)彎的代價(jià)有：距離代價(jià)Cd，指單次轉(zhuǎn)彎的總距離；時(shí)間代價(jià)Ct，指單次轉(zhuǎn)彎的總時(shí)間；能量消耗代價(jià)Ce，指單次轉(zhuǎn)彎的總能量消耗。農(nóng)機(jī)轉(zhuǎn)彎相對(duì)總作業(yè)時(shí)間的占比小，燃油消耗與時(shí)間近似成正比，因此可近似使用轉(zhuǎn)彎時(shí)間代價(jià)表示。

圖2 地頭轉(zhuǎn)彎方式Fig.2 Ground turning modes

實(shí)際作業(yè)時(shí)農(nóng)機(jī)轉(zhuǎn)彎性能受到不同農(nóng)藝要求的約束。為實(shí)現(xiàn)農(nóng)業(yè)作業(yè)無(wú)重復(fù)、無(wú)遺漏的目標(biāo)，車輛在進(jìn)行轉(zhuǎn)彎時(shí)必須考慮到農(nóng)機(jī)具所支持的轉(zhuǎn)彎半徑，如植保機(jī)等有較寬作業(yè)范圍的機(jī)具需以較大半徑轉(zhuǎn)彎以避免重復(fù)噴藥。因此實(shí)際轉(zhuǎn)彎半徑需綜合考慮車輛動(dòng)力學(xué)轉(zhuǎn)彎半徑rveh與機(jī)具轉(zhuǎn)彎半徑rag，本文取二者中較大值進(jìn)行轉(zhuǎn)彎代價(jià)計(jì)算。

根據(jù)各項(xiàng)農(nóng)機(jī)參數(shù)，單次跨越n行的轉(zhuǎn)彎距離代價(jià)Cd與時(shí)間代價(jià)Ct分別為

(1)

(2)

其中

r=max(rveh,rag)

式中vf——農(nóng)機(jī)地頭區(qū)域直線行駛速度

vt——農(nóng)機(jī)轉(zhuǎn)彎速度

α——當(dāng)前作物行與地塊邊界夾角

車輛在不同作物行間的換行代價(jià)可使用轉(zhuǎn)彎代價(jià)鄰接矩陣L表示。對(duì)于作物行總數(shù)為N的地塊，其鄰接矩陣L大小為N×N，矩陣中元素Lij表示在第i行與第j行作物間進(jìn)行單次轉(zhuǎn)彎所消耗的代價(jià)，若i與j相等，則代價(jià)為0。某農(nóng)機(jī)在某田地中5行作物行間的時(shí)間轉(zhuǎn)彎代價(jià)鄰接矩陣為

(3)

其最小轉(zhuǎn)彎半徑r與作業(yè)寬幅w的關(guān)系為w

2.2 地塊邊界

地塊邊界不僅是地塊特征也是作業(yè)路徑規(guī)劃的約束，農(nóng)機(jī)需在不越界的基礎(chǔ)上完成作業(yè)。作業(yè)地塊邊界、地塊內(nèi)部的障礙物可由首尾相連的直線段構(gòu)成的多邊形來(lái)描述，一個(gè)完整地塊可由一個(gè)地塊外邊界多邊形和內(nèi)部數(shù)個(gè)障礙物多邊形組成。一般可使用衛(wèi)星定位采集設(shè)備圍繞農(nóng)田地塊邊界或障礙物采樣得到離散經(jīng)緯度邊界坐標(biāo)點(diǎn)集，對(duì)采樣點(diǎn)進(jìn)行擬合可得到最終多邊形邊界。

本文基于道格拉斯-普克算法[21-22](Douglas-Peucker，DP)進(jìn)行地塊外邊界擬合。DP算法可在保留原幾何圖像骨架的基礎(chǔ)上進(jìn)行線狀要素抽稀實(shí)現(xiàn)多邊形擬合，步驟如圖3所示：在圖3a中待處理點(diǎn)集的首末點(diǎn)間連一條直線，求其余各點(diǎn)與該直線的距離，找出最大距離dDPMAX及其對(duì)應(yīng)的點(diǎn)P；設(shè)定閾值dthreshold，若dDPMAX

圖3 道格拉斯-普克算法Fig.3 Douglas-Peucker algorithm

直接采用DP算法進(jìn)行擬合時(shí)，若擬合后邊界超出地塊實(shí)際邊界會(huì)導(dǎo)致農(nóng)機(jī)越界。同理，若擬合后障礙物邊界無(wú)法包絡(luò)實(shí)際障礙物，會(huì)使農(nóng)機(jī)與障礙物發(fā)生碰撞。本文針對(duì)邊界擬合提出了內(nèi)縮改進(jìn)的DP算法，由于擬合后邊界線與邊界采樣點(diǎn)距離最大為dthreshold，可在采用DP算法擬合后，將所有擬合后邊界等距離內(nèi)縮dthreshold，此時(shí)所有邊界均在原采樣點(diǎn)內(nèi)部，確保所規(guī)劃軌跡不越界。

對(duì)于障礙物邊界，由于無(wú)需考慮形狀影響，直接尋找障礙物采樣點(diǎn)集的最小凸包即可完整外包絡(luò)采樣點(diǎn)。圖4為對(duì)一含障礙物地塊分別進(jìn)行地塊邊界擬合與障礙物邊界擬合后的結(jié)果，圖中黑色邊界為原采樣邊界，陰影部分為擬合后有效地塊。

圖4 邊界內(nèi)縮與外包絡(luò)擬合Fig.4 Inner boundary contraction and outer envelope fitting

農(nóng)機(jī)作業(yè)要求預(yù)留轉(zhuǎn)向地塊，該地塊位于作物行兩側(cè)，用于農(nóng)機(jī)完成轉(zhuǎn)彎換行操作。如圖5，一完整地塊可分為工作區(qū)域W與轉(zhuǎn)彎預(yù)留區(qū)域T，在其區(qū)域內(nèi)分別進(jìn)行作物行遍歷與轉(zhuǎn)彎換行操作。T寬度取決于轉(zhuǎn)彎方式、作物行方向與農(nóng)機(jī)自身參數(shù)，弓形轉(zhuǎn)彎寬度dU和梨形轉(zhuǎn)彎寬度dΩ分別為

dU=r(1+cosα)+w/2

(4)

(5)

圖5 轉(zhuǎn)向預(yù)留區(qū)域分割示意圖Fig.5 Segmentation schematic of reserved turning area

已完成邊界擬合的多邊形地塊可通過(guò)將各邊向地塊內(nèi)部平行偏移邊界的方式劃分W與T區(qū)域。本文采用基于角平分的等距線法來(lái)實(shí)現(xiàn)該邊界偏移：當(dāng)各邊均等距平移時(shí)，平移后兩邊交點(diǎn)位于原兩邊角平分線上；當(dāng)各邊平移距離不同時(shí)，可由不同邊平行距離的比例來(lái)劃分兩邊夾角，再求出平移后交點(diǎn)。

圖6 角平分法偏移邊界Fig.6 Parallel migration of angle bisectors

如圖6所示，AB、AC兩邊界向內(nèi)平行偏移距離分別為d1、d2，偏移后邊界A′B′、A′C′交于點(diǎn)A′，其中AB、AC夾角為αA，有

β=αAd2/(d1+d2)

(6)

d′=d2/sinβ

(7)

式中β——角分線方位角

d′——角分線偏移距離

求解β與d′后可由點(diǎn)A坐標(biāo)計(jì)算得到點(diǎn)A′坐標(biāo)。對(duì)所有相鄰邊重復(fù)以上過(guò)程，得出所有工作地塊邊界頂點(diǎn)，按順序連接后完成預(yù)留地塊劃分。

若實(shí)際作業(yè)條件允許，可選擇進(jìn)行封邊操作，即在工作區(qū)域內(nèi)正常作業(yè)完成后，遍歷轉(zhuǎn)向預(yù)留區(qū)域一周進(jìn)行作業(yè)，進(jìn)一步提高地塊作業(yè)覆蓋率。

2.3 非常規(guī)地塊

農(nóng)機(jī)作業(yè)需沿作物行作業(yè)且只能在地頭區(qū)域轉(zhuǎn)向換行，不能隨意跨越作物行。對(duì)于常規(guī)凸多邊形地塊，MICHEL等[23]已經(jīng)證明最佳作業(yè)方向應(yīng)與多邊形最長(zhǎng)邊平行，只需判斷地塊最長(zhǎng)邊，按該邊角度劃分等距平行線作為作物行行線即可。

相對(duì)一般凸多邊形地塊，非常規(guī)地塊指含有障礙物或地塊邊界為凹多邊形的地塊。若使用上述尋找最長(zhǎng)邊的方法處理非常規(guī)地塊則同一條作物行線可能會(huì)與障礙物或地塊邊界產(chǎn)生多個(gè)交點(diǎn)而帶來(lái)額外的轉(zhuǎn)彎次數(shù)，因此不能直接將最長(zhǎng)邊方向作為作物行傾角。

針對(duì)含障礙物地塊，可將其分割為多個(gè)無(wú)障礙物子區(qū)域后，分別進(jìn)行全覆蓋規(guī)劃后再連通各子區(qū)域，完成全地塊的遍歷[24]。一般可用梯形法[25]或線掃法[26]進(jìn)行地塊分割，本文使用基于最小高度和的線掃法完成區(qū)域分割。

2.3.1子區(qū)域分割

線掃分割法如圖7所示，使用傾角θ的作物行從左至右劃過(guò)整個(gè)區(qū)域，可按作物行與原地塊、障礙物的交點(diǎn)情況，將地塊分割成子區(qū)域①、②、③、④。此時(shí)全部子區(qū)域高度之和為

(8)

式中S(θ)——地塊劃分后總高度和

Hp(θ)——原地塊相對(duì)θ角分割線的高度

Hi(θ)——障礙物i相對(duì)θ角分割線的高總高度和最小時(shí)該區(qū)域劃分為最優(yōu)劃分。

圖7 線掃分割法Fig.7 Line-sweep decomposition

2.3.2作物行線方向優(yōu)化

當(dāng)作物行間距固定時(shí)，轉(zhuǎn)彎次數(shù)與子區(qū)域高度成正比，為此需找到最優(yōu)作物行方向θ，以該角度線掃凹形地塊或分割含障礙物地塊，并按該角度在地塊內(nèi)劃分作物行時(shí)，轉(zhuǎn)彎次數(shù)最少，所生成作物行為最優(yōu)作物行。

(9)

(10)

式中ns——地塊及障礙物總邊界數(shù)

θi——第i條邊界角度

li——第i條邊界長(zhǎng)于θ′與θ相近，因此sin(|θ′-θi|)與sin(|θ-θi|)近似相等，且方向?yàn)棣葧r(shí)與對(duì)應(yīng)平行邊界無(wú)交點(diǎn)，顯然此時(shí)N′raw>Nraw，即θ角對(duì)應(yīng)作物行數(shù)為鄰域內(nèi)極小值。

圖8 作物行數(shù)極小值示意圖Fig.8 Sketch of minimum crop row number

2.3.3區(qū)域遍歷順序優(yōu)化

完成地塊分割與作物行線生成后，農(nóng)機(jī)在分割后各子區(qū)塊內(nèi)的行走方式與無(wú)障礙物地塊一致。在各子區(qū)域內(nèi)，農(nóng)機(jī)作業(yè)出口位置只由作物行數(shù)決定：偶數(shù)行數(shù)情況下將會(huì)在出發(fā)點(diǎn)同側(cè)，奇數(shù)行情況下則相反。當(dāng)車輛出入口有位置要求或農(nóng)機(jī)在子區(qū)域的障礙物一側(cè)結(jié)束工作時(shí)，受到作物行約束會(huì)難以駛出農(nóng)田或前進(jìn)到下一地塊?？刹捎迷黾臃亲鳂I(yè)路徑的方法來(lái)調(diào)整出口位置。若某子區(qū)域存在n行作物行，定義遍歷順序集為

S={[s1,w1],[s2,w2],…,[si,wi],…,
[sn-1,wn-1],[sn,wn]}

(11)

式中si——農(nóng)機(jī)路徑中第i行在作物行中的順序

wi——農(nóng)機(jī)路徑中第i行是否作業(yè)，若工作值為1，否則為0

當(dāng)需調(diào)整出口位置時(shí)，在原n-1行空載不作業(yè)，在第n行正常作業(yè)后返回n-1行進(jìn)行作業(yè)，此時(shí)出口在n-1行上，且位于原出口另一側(cè)，即調(diào)整前后的遍歷順序集為

Sbefore={[s1,1],[s2,1],…,[sn-1,1],[sn,1]}

(12)

Safter={[s1,1],…,[sn-2,1],[sn-1,0],[sn,1],
[sn-1,1]}

(13)

以圖9為例，原遍歷順序集為{[1，1]，[2，1]，[3，1]，[4，1]，[5，1]}，出口位于入口另一側(cè)，當(dāng)需要調(diào)整出口位置時(shí)，改變遍歷順序?yàn)閧[1，1]，[2，1]，[3，1]，[4，0]，[5，1]，[4，1]}，此時(shí)通過(guò)增加非作業(yè)路徑的方法改變總行數(shù)的奇偶性，使子區(qū)域出口在入口一側(cè)。

圖9 切換子區(qū)域出口位置示意圖Fig.9 Sketch of changing subdomain exit position

增加非作業(yè)路徑方法會(huì)額外帶來(lái)單次作物行行走與轉(zhuǎn)彎代價(jià)，但農(nóng)機(jī)在非作業(yè)路徑無(wú)需慢速作業(yè)，可快速通過(guò)節(jié)省時(shí)間代價(jià)。該方法以較小的代價(jià)解決了無(wú)法避免的車輛出入、切換地塊問(wèn)題，同時(shí)對(duì)作業(yè)條件和農(nóng)機(jī)農(nóng)具的行駛條件如倒車等無(wú)要求，具備一定的可行性。

3 基于多約束的遍歷方式

現(xiàn)有農(nóng)機(jī)作業(yè)行走路徑模式常指梭行、套行、開壟形、閉壟形這些傳統(tǒng)規(guī)則走法。下面進(jìn)行最優(yōu)作物行遍歷順序的生成研究，在上述各種約束條件下，求解以最小代價(jià)，無(wú)重復(fù)、不遺漏地遍歷作物行的最優(yōu)順序。作物行遍歷問(wèn)題的本質(zhì)為經(jīng)過(guò)全部作物行且中間換行代價(jià)和最小的旅行商(Traveling salesman problem，TSP)問(wèn)題[28]，其中換行代價(jià)使用轉(zhuǎn)彎代價(jià)鄰接矩陣求得。面對(duì)TSP問(wèn)題，一些無(wú)規(guī)則啟發(fā)式算法如模擬退火(Simulated annealing，SA)算法[29]理論上可以應(yīng)對(duì)地塊中的作物行約束。但當(dāng)需面對(duì)大型農(nóng)田時(shí)啟發(fā)式算法面臨規(guī)模效應(yīng)的挑戰(zhàn)，除了計(jì)算時(shí)間長(zhǎng)外，其更容易陷入局部最優(yōu)解，尋優(yōu)率低[30]。為彌補(bǔ)標(biāo)準(zhǔn)模擬退火法的缺點(diǎn)，本文提出基于模擬退火優(yōu)化的最小單元拆解與遍歷合成的方法。

本文基于模擬退火的行數(shù)拆解與遍歷合成的路徑規(guī)劃的實(shí)施路線與一般規(guī)則實(shí)施路徑區(qū)別如圖10所示。本文方法為根據(jù)當(dāng)前作業(yè)參數(shù)的農(nóng)機(jī)，通過(guò)改進(jìn)模擬退火算法求解最優(yōu)遍歷單元。進(jìn)行路徑規(guī)劃時(shí)將完整地塊劃分為數(shù)個(gè)重復(fù)最優(yōu)單元，通過(guò)不斷循環(huán)各單元，直至遍歷完整塊農(nóng)田。因此，對(duì)全區(qū)域的遍歷求解可轉(zhuǎn)化為對(duì)最優(yōu)行走單元的求解。

圖10 路徑規(guī)劃實(shí)施路線Fig.10 Roadmap of path planning

3.1 基于改進(jìn)模擬退火的最優(yōu)單元求解

遍歷最優(yōu)單元為利用農(nóng)機(jī)參數(shù)等先驗(yàn)信息在全覆蓋規(guī)劃前得到的可重復(fù)小規(guī)模農(nóng)機(jī)路徑。由于單元行數(shù)較少，避免規(guī)模效應(yīng)的同時(shí)可充分利用模擬退火搜索的便利性完成求解。最優(yōu)單元行數(shù)可通過(guò)求解最小平均單次轉(zhuǎn)彎代價(jià)得到，對(duì)于單元內(nèi)走法，本文采用引入尋優(yōu)擾動(dòng)算子的改進(jìn)模擬退火算法進(jìn)行求解。

模擬退火算法通過(guò)模擬金屬退火的過(guò)程，從某一較高初始溫度To開始降溫，不斷改變當(dāng)前解s，若其評(píng)價(jià)值F(s)變小，則接收新解，否則以概率PSA接收新解，當(dāng)溫度降至終止溫度Tf，結(jié)束降溫。多次退火后所獲穩(wěn)定解即為最終尋優(yōu)解。對(duì)于本文所述問(wèn)題，所求解s為單元內(nèi)遍歷順序，si為單元內(nèi)第i行對(duì)應(yīng)實(shí)際作物行順序，評(píng)價(jià)值F(s)為單元內(nèi)以及前進(jìn)到下一單元的總轉(zhuǎn)彎代價(jià)，其定義為

(14)

式中Nu——單元內(nèi)行數(shù)

Lij——轉(zhuǎn)彎代價(jià)鄰接矩陣中i行j列對(duì)應(yīng)元素值

為改善算法性能，本文引入了尋優(yōu)擾動(dòng)算子，在產(chǎn)生新解時(shí)根據(jù)當(dāng)前溫度高低調(diào)整當(dāng)前需調(diào)整路徑行數(shù)，進(jìn)一步提高在高溫時(shí)算法的搜索范圍而不影響低溫時(shí)的收斂尋優(yōu)。每次調(diào)整的路徑行數(shù)Nadjust為

(15)

式中 int()——取整算子

Nmaxa、Nmina——允許最大和最小的調(diào)整行數(shù)

T——當(dāng)前溫度

由此，使用該改進(jìn)模擬退火算法求解最小單元走法步驟為：

(1)設(shè)定初始溫度To，根據(jù)當(dāng)前單元行數(shù)產(chǎn)生隨機(jī)初始解s，計(jì)算其轉(zhuǎn)彎代價(jià)評(píng)價(jià)值F(s)。

(2)降低溫度，根據(jù)當(dāng)前溫度T計(jì)算尋優(yōu)擾動(dòng)算子，隨機(jī)選取Nadjust行，對(duì)其遍歷順序進(jìn)行擾動(dòng)交換，產(chǎn)生新解s′并計(jì)算當(dāng)前新的評(píng)價(jià)值F(s′)。

(3)新解s′的接受：若F(s′)

(16)

(4)判斷算法終止條件，若當(dāng)前溫度T

模擬退火算法所求得的無(wú)規(guī)則走法，沒有改變車輛行駛條件與作業(yè)條件，僅對(duì)車輛在轉(zhuǎn)彎區(qū)域內(nèi)的換行順序進(jìn)行優(yōu)化，不改變?nèi)采w作業(yè)過(guò)程，對(duì)農(nóng)藝無(wú)影響，具備可行性。

3.2 基于最小單元的行數(shù)拆解及遍歷合成

在單地塊內(nèi)，由于無(wú)法事先確定作物行數(shù)，當(dāng)總行數(shù)不是最小單元行數(shù)的整數(shù)倍時(shí)，單元重復(fù)遍歷后會(huì)存在多余行。因此本文通過(guò)行數(shù)拆解與遍歷合成的方式完成規(guī)劃，拆解前后總行數(shù)與單元行數(shù)的關(guān)系為

(17)

其中

k=int(Ntotal/Nunit)

式中Ntotal——地塊總行數(shù)

Nunit——最小單元行數(shù)

Nleft——單元遍歷后的剩余行

k——完整單元數(shù)

根據(jù)式(17)，任意總作物行數(shù)均可拆解為數(shù)個(gè)單元行數(shù)Nunit與剩余行數(shù)Nleft，只需分別對(duì)各單元行及剩余行內(nèi)的走法進(jìn)行規(guī)劃即可完成全地塊遍歷。由此本文提出最優(yōu)路徑集的概念，最優(yōu)路徑集包含從第1行至2Nunit-1行各情況下的最優(yōu)規(guī)劃走法，通過(guò)改進(jìn)模擬退火算法求解各情況下走法。最優(yōu)路徑集在全覆蓋規(guī)劃前生成，全覆蓋規(guī)劃時(shí)可按式(17)對(duì)總作業(yè)行數(shù)進(jìn)行拆解，再于最優(yōu)路徑集中分別提取單元內(nèi)走法與剩余行內(nèi)走法，通過(guò)合成即可生成完整地塊軌跡。

3.3 行數(shù)拆解及遍歷合成應(yīng)用

根據(jù)該行數(shù)拆解及遍歷合成方式，本文進(jìn)行了不同農(nóng)機(jī)參數(shù)條件下的最優(yōu)單元和路徑集生成。本文采用±Ui、±Ωi、±∝i分別表示隔i行的弓形、梨形、魚尾形轉(zhuǎn)彎，其中±表示正反向。采用F(Ui)、F(Ωi)、F(∝i)表示對(duì)應(yīng)的單次轉(zhuǎn)彎代價(jià)，可由F(s′)

(1)r

此情況下轉(zhuǎn)彎代價(jià)關(guān)系式為F(U1)

圖11 梭行遍歷Fig.11 Fusiform traverse

(2)w/2≤r

此情況下轉(zhuǎn)彎代價(jià)關(guān)系式為F(U2)

(3)w≤r<3w/2(F(Ω2)

此情況下轉(zhuǎn)彎代價(jià)關(guān)系式為F(U3)

(4)w≤r<3w/2(F(U4)

此種情況下的轉(zhuǎn)彎代價(jià)關(guān)系式為F(U3)

(5)3w/2≤r<2w

此種情況下的轉(zhuǎn)彎代價(jià)關(guān)系式為F(U4)

圖12 最優(yōu)路徑集Fig.12 Aggregation of optimal path

以上已涵蓋大多數(shù)農(nóng)機(jī)與作物行參數(shù)關(guān)系，因此其余情況本文不再展開。

4 測(cè)試與分析

4.1 測(cè)試方式

在北京小湯山國(guó)家精準(zhǔn)農(nóng)業(yè)研究基地對(duì)該規(guī)劃算法進(jìn)行了驗(yàn)證。地塊數(shù)據(jù)使用卓林A5型多功能測(cè)畝儀的點(diǎn)采集功能繞基地中形狀不一的多個(gè)地塊各一周采樣得到，平均水平定位精度為0.55 m。測(cè)試農(nóng)機(jī)設(shè)備為約翰迪爾6B-1204型拖拉機(jī)，其最小轉(zhuǎn)向半徑為5.2 m，拖掛耕地設(shè)備作業(yè)寬幅為6 m，工作行進(jìn)速度為2 m/s，轉(zhuǎn)彎平均速度為1 m/s。配置編程環(huán)境為Windows 10、Visual Studio 2019。

4.2 評(píng)價(jià)指標(biāo)

農(nóng)機(jī)路徑可使用總時(shí)間代價(jià)CT、總距離代價(jià)CD、作業(yè)覆蓋率Ccov、工作占空比D等指標(biāo)來(lái)評(píng)價(jià)其質(zhì)量。其中，總時(shí)間代價(jià)CT與總距離代價(jià)CD分別為農(nóng)機(jī)沿規(guī)劃路徑完成遍歷所需的總時(shí)間與總距離，表述農(nóng)機(jī)完成工作所需的總資源，代價(jià)越低，該軌跡質(zhì)量越高。

工作占空比D表征作業(yè)時(shí)間與總時(shí)間的比例，工作占空比越大，農(nóng)機(jī)工作效率越高，公式為

(18)

式中twork——農(nóng)機(jī)負(fù)載工作時(shí)間

tall——總作業(yè)時(shí)間

作業(yè)覆蓋率Ccov表征有效作業(yè)面積在地塊總面積中的比例，覆蓋率越大，土地利用率越高，規(guī)劃質(zhì)量越高，公式為

(19)

式中Lw——工作路徑總長(zhǎng)度

Sfield——地塊有效總面積

4.3 結(jié)果與分析

為驗(yàn)證本文提出的多約束處理方案的正確性，按不同約束條件在北京小湯山國(guó)家精準(zhǔn)農(nóng)業(yè)研究基地采集了多個(gè)地塊邊界數(shù)據(jù)，包括規(guī)則凸多邊形地塊(地塊a)、不規(guī)則凹多邊形地塊(地塊b)及含障礙物地塊(地塊c)。使用上述農(nóng)機(jī)，按本文所述全覆蓋路徑規(guī)劃方法對(duì)不同地塊分別進(jìn)行了規(guī)劃，生成路徑結(jié)果如圖13，并求出各路徑的作業(yè)覆蓋率及作業(yè)占空比。考慮到農(nóng)業(yè)生產(chǎn)可在作業(yè)完成后通過(guò)封邊作業(yè)對(duì)轉(zhuǎn)彎預(yù)留地塊進(jìn)行遍歷以提高土地利用率，因此同時(shí)計(jì)算出封邊操作后的作業(yè)覆蓋率。結(jié)果如表1所示。

圖13 地塊邊界及規(guī)劃路徑Fig.13 Plot boundaries and planned paths

表1 不同地塊所得軌跡評(píng)價(jià)指標(biāo)Tab.1 Trajectory evaluation indexes obtained from different plots %

由圖13可看出，各路徑均預(yù)留了邊界轉(zhuǎn)彎地塊并根據(jù)地塊形狀生成了最優(yōu)作物行，對(duì)含障礙物地塊進(jìn)行了區(qū)域分割處理，并針對(duì)多種轉(zhuǎn)彎方式約束利用本文單元拆解合成方法，優(yōu)先選取弓形轉(zhuǎn)彎生成了最優(yōu)單元，完成了全覆蓋遍歷。

分析表1可知，本算法面對(duì)包含不同約束的地塊，作業(yè)參數(shù)均可滿足規(guī)劃需求，封邊作業(yè)后各測(cè)試地塊土地利用率均可達(dá)98%以上，最高可達(dá)99.87%。同時(shí)，作業(yè)占空比均較高，保證了農(nóng)機(jī)的作業(yè)效率。說(shuō)明本文提出的規(guī)劃算法可以在有效處理各種約束的基礎(chǔ)上完成農(nóng)機(jī)全覆蓋路徑規(guī)劃。

為驗(yàn)證本文提出的行數(shù)拆解及合成的遍歷算法的性能，對(duì)規(guī)則凸多邊形地塊a分別使用傳統(tǒng)規(guī)則遍歷方法、經(jīng)典模擬退火算法(取To=200℃，Tf=50℃，經(jīng)200次重復(fù)退火取代價(jià)最小值)與本文提出的遍歷方法進(jìn)行規(guī)劃，求出各方法所得軌跡評(píng)價(jià)指標(biāo)，包括總時(shí)間代價(jià)、總距離代價(jià)、作業(yè)覆蓋率(均不進(jìn)行封邊)、工作占空比。為驗(yàn)證不同農(nóng)機(jī)參數(shù)對(duì)算法的影響，更換農(nóng)機(jī)拖掛作業(yè)設(shè)備，改變作業(yè)寬幅為3.5 m，農(nóng)機(jī)轉(zhuǎn)向參數(shù)不變，再次規(guī)劃并計(jì)算評(píng)價(jià)指標(biāo)，結(jié)果如表2所示。

為驗(yàn)證不同地塊約束對(duì)算法的影響，在同樣的作業(yè)參數(shù)下使用各遍歷方式對(duì)地塊c進(jìn)行規(guī)劃。相對(duì)地塊a，地塊c更符合大田的特征：面積更大，作物行相對(duì)地塊寬度更長(zhǎng)，作物行約束更明顯，同時(shí)存在障礙物約束，因此可用于檢驗(yàn)算法對(duì)不同地塊的適應(yīng)性。地塊c條件下各算法所得軌跡評(píng)價(jià)指標(biāo)如表3所示。

表2 地塊a不同走法下軌跡評(píng)價(jià)指標(biāo)Tab.2 Trajectory evaluation index of plot a under different moves

表3 地塊c不同走法下軌跡評(píng)價(jià)指標(biāo)Tab.3 Trajectory evaluation index of plot c under different moves

分析表2可知，傳統(tǒng)規(guī)則走法中：套行走法與閉壟走法均只適用于農(nóng)機(jī)轉(zhuǎn)向性能較差及地塊寬度較小的情況，因此梭行走法各代價(jià)均相對(duì)較小，但逐行梭形遍歷無(wú)法避免使用梨形轉(zhuǎn)彎，需要預(yù)留更寬的轉(zhuǎn)彎區(qū)域，作業(yè)覆蓋率較低。非規(guī)則走法中：模擬退火算法結(jié)果與梭行法相近，但當(dāng)作物行數(shù)增多時(shí)，規(guī)模效應(yīng)使得模擬退火算法難以逼近全局最優(yōu)解。而本文提出方法在模擬退火的基礎(chǔ)上，降低了規(guī)模效應(yīng)，使得結(jié)果更加接近最優(yōu)解，相比傳統(tǒng)規(guī)則走法節(jié)約距離消耗最高達(dá)30.3%，相比經(jīng)典模擬退火算法，節(jié)約距離消耗6.9%，同時(shí)提高了作業(yè)覆蓋率與作業(yè)效率。

對(duì)比分析表2與表3，作物行長(zhǎng)度與地塊寬度的比例增大，使得地塊c相比地塊a中各算法所得軌跡作業(yè)占空比均有提升，但傳統(tǒng)規(guī)則算法受邊界條件變化影響更大，魯棒性低，未能有效處理不同地塊邊界約束。而本文提出的行數(shù)拆解及合成的遍歷算法在不同地塊邊界條件下均可保持較高的作業(yè)占空比，在地塊c中高達(dá)94.72%。說(shuō)明本文提出的遍歷順序算法可以有效克服各約束的影響，以較優(yōu)的代價(jià)和作業(yè)效率完成農(nóng)機(jī)的路徑規(guī)劃工作。

5 結(jié)論

(1)針對(duì)大型農(nóng)機(jī)作業(yè)路徑規(guī)劃中存在的多種約束，本文通過(guò)引入轉(zhuǎn)彎代價(jià)鄰接矩陣量化了不同地頭轉(zhuǎn)彎方式對(duì)規(guī)劃的影響，采用內(nèi)縮改進(jìn)的道格拉斯-普克(Douglas-Peucker)擬合算法和采樣點(diǎn)的最小凸包法分別處理地塊邊界和障礙物邊界，避免車輛越界和與障礙物發(fā)生碰撞。使用角平分線的平行偏移法求得轉(zhuǎn)向預(yù)留地塊后，以轉(zhuǎn)彎代價(jià)最小為優(yōu)化條件對(duì)多種形狀地塊進(jìn)行了最優(yōu)作物行生成。

(2)在作物行的最優(yōu)遍歷順序求解的問(wèn)題上，提出了基于模擬退火的行數(shù)拆解及遍歷合成的混合規(guī)則優(yōu)化算法，該方法適應(yīng)性強(qiáng)且優(yōu)化高效穩(wěn)定，解決了傳統(tǒng)無(wú)規(guī)則模擬退火算法因規(guī)模效應(yīng)而容易陷入局部最優(yōu)解的問(wèn)題。同時(shí)相對(duì)傳統(tǒng)規(guī)則遍歷方式，有效處理了不同邊界約束，大幅減少了作業(yè)消耗，提升了作業(yè)效率。

(3)通過(guò)實(shí)地測(cè)試，測(cè)量了多個(gè)地塊參數(shù)并使用本文方法進(jìn)行了規(guī)劃。所得規(guī)劃軌跡的各項(xiàng)指標(biāo)中，總距離、時(shí)間代價(jià)均低于傳統(tǒng)規(guī)則走法與經(jīng)典模擬退火算法，較傳統(tǒng)走法最多可節(jié)約距離消耗30.3%，較模擬退火算法節(jié)約距離消耗6.9%。本文算法所得軌跡平均作業(yè)覆蓋率達(dá)90.78%，平均作業(yè)占空比達(dá)85.10%，封邊作業(yè)后地塊有效覆蓋率達(dá)98%，可以滿足實(shí)際規(guī)劃需求。