不確定場(chǎng)景下無(wú)人農(nóng)機(jī)多機(jī)動(dòng)態(tài)路徑規(guī)劃方法

梁亞杰，楊麗麗，徐媛媛，陳智博，馮雅蓉，吳才聰,2

·智慧農(nóng)業(yè)技術(shù)與裝備·

不確定場(chǎng)景下無(wú)人農(nóng)機(jī)多機(jī)動(dòng)態(tài)路徑規(guī)劃方法

梁亞杰1，楊麗麗1，徐媛媛1，陳智博1，馮雅蓉1，吳才聰1,2※

（1. 中國(guó)農(nóng)業(yè)大學(xué)信息與電氣工程學(xué)院，北京 100083； 2. 農(nóng)業(yè)農(nóng)村部農(nóng)業(yè)信息獲取技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100083）

在現(xiàn)代化農(nóng)業(yè)中，越來(lái)越多的龍頭企業(yè)或農(nóng)村合作社提供一系列的農(nóng)業(yè)作業(yè)專(zhuān)業(yè)化服務(wù)，引入多臺(tái)農(nóng)機(jī)進(jìn)行規(guī)?；鳂I(yè)，不僅提高了效率，而且可以實(shí)現(xiàn)搶種搶收，減少自然災(zāi)害的風(fēng)險(xiǎn)。目前，多臺(tái)農(nóng)機(jī)并行作業(yè)仍以預(yù)先計(jì)劃的固定農(nóng)機(jī)和靜態(tài)的固定路線為主，但在實(shí)際耕種、收割等作業(yè)中，常會(huì)出現(xiàn)農(nóng)機(jī)突發(fā)故障、農(nóng)機(jī)臨時(shí)增加、農(nóng)機(jī)工作效率不一致等不確定場(chǎng)景，這些不確定性給多臺(tái)農(nóng)機(jī)集群控制帶來(lái)巨大挑戰(zhàn)。因此，研究不確定場(chǎng)景下多機(jī)動(dòng)態(tài)路徑規(guī)劃方法具有十分重要的理論意義和實(shí)用價(jià)值。該研究以總作業(yè)時(shí)長(zhǎng)為綜合優(yōu)化目標(biāo)，綜合各種不確定場(chǎng)景，針對(duì)輪式自動(dòng)駕駛拖拉機(jī)，提出了改進(jìn)的迭代貪婪（Improved Iterated Greedy, IIG）方法進(jìn)行多機(jī)動(dòng)態(tài)路徑規(guī)劃，解決以往傳統(tǒng)方法在不確定情況發(fā)生后路徑規(guī)劃結(jié)果低效甚至失效的問(wèn)題。試驗(yàn)表明，該方法在不確定場(chǎng)景下可及時(shí)、高效的動(dòng)態(tài)調(diào)整路徑規(guī)劃方案，能夠?yàn)椴煌瑪?shù)量、不同性能的農(nóng)機(jī)迭代找到當(dāng)前最優(yōu)路徑。與傳統(tǒng)的并排作業(yè)方法相比，IIG優(yōu)化的矩形農(nóng)田作業(yè)路徑總作業(yè)時(shí)間平均下降約35%，且隨著農(nóng)機(jī)性能差異越大，節(jié)省時(shí)間越多；與迭代貪婪（Iterated Greedy, IG）方法相比，IIG在一般播種作業(yè)中總掉頭時(shí)間平均減少約17%。該方法在不確定場(chǎng)景下路徑優(yōu)化效果較好，且具有很好的魯棒性及環(huán)境適應(yīng)性，可為農(nóng)田無(wú)人作業(yè)多機(jī)路徑規(guī)劃提供參考。

農(nóng)業(yè)機(jī)械；自動(dòng)化；無(wú)人駕駛；多機(jī)協(xié)同作業(yè)；動(dòng)態(tài)路徑規(guī)劃

0 引 言

在現(xiàn)代化農(nóng)業(yè)中，越來(lái)越多的龍頭企業(yè)或農(nóng)村合作社提供一系列的農(nóng)業(yè)作業(yè)專(zhuān)業(yè)化服務(wù)[1-2]，提高農(nóng)業(yè)機(jī)械的利用率和作業(yè)效率是重中之重[3-7]。單機(jī)作業(yè)[8]若出現(xiàn)故障，將會(huì)影響作業(yè)進(jìn)度，而引入多臺(tái)農(nóng)機(jī)進(jìn)行規(guī)?；鳂I(yè)[9-11]，可以更高效完成農(nóng)田的作業(yè)任務(wù)，并且對(duì)實(shí)現(xiàn)搶種搶收、減少自然災(zāi)害風(fēng)險(xiǎn)意義重大。因此，如何有效組織多臺(tái)農(nóng)機(jī)共同作業(yè)，節(jié)省作業(yè)成本，縮短作業(yè)時(shí)間是實(shí)現(xiàn)無(wú)人駕駛作業(yè)亟待解決的主要問(wèn)題[12-14]。

2008年，Bochtis提出一種B-patterns農(nóng)機(jī)作業(yè)模式，將農(nóng)田劃分為若干平行、等寬的作業(yè)行，使用旅行商問(wèn)題來(lái)優(yōu)化農(nóng)機(jī)作業(yè)路徑，即加權(quán)圖中尋找最優(yōu)遍歷序列的問(wèn)題，并且每個(gè)作業(yè)行只能遍歷一次[15]。同年，又將其轉(zhuǎn)化為二進(jìn)制整數(shù)規(guī)劃問(wèn)題，提出一種計(jì)算平行遍歷序列算法[16]，相比并排作業(yè)方法，非作業(yè)成本可減少50%以上。2009年Bochtis 等[17]將多臺(tái)農(nóng)機(jī)作業(yè)問(wèn)題定義為車(chē)輛路徑問(wèn)題（Vehicle Routing Problem, VRP），求解農(nóng)業(yè)大田作業(yè)最優(yōu)作業(yè)路徑。2010年Jin等[18]通過(guò)將農(nóng)田分解為子區(qū)域并確定每個(gè)子區(qū)域作業(yè)方向，建立農(nóng)田幾何模型求解最優(yōu)覆蓋路徑規(guī)劃。2011年Hameed等[19]根據(jù)農(nóng)田幾何形狀計(jì)算出農(nóng)機(jī)作業(yè)最優(yōu)方向來(lái)優(yōu)化農(nóng)機(jī)作業(yè)路徑。2013年Bakhtiari等[20]提出了蟻群優(yōu)化的聯(lián)合收割田間覆蓋方案生成方法，與常規(guī)方案進(jìn)行比較，節(jié)省非工作距離18%～43%。2016年Conesa-Mu?oz等[21]基于模擬退火算法計(jì)算具有不同特性的車(chē)輛覆蓋作物軌跡。同年，又提出將Mix-opt算子集成到該算法來(lái)優(yōu)化多臺(tái)農(nóng)機(jī)作業(yè)路徑[22]。2017年Seyyedhasani等[23]使用改進(jìn)的Clark-Wright算法和禁忌搜索算法優(yōu)化多臺(tái)農(nóng)機(jī)作業(yè)路徑，使作業(yè)完成時(shí)間減少了32%。2019年，姚竟發(fā)等[24]提出了多臺(tái)聯(lián)合收割機(jī)無(wú)沖突協(xié)同作業(yè)路徑優(yōu)化算法，通過(guò)避免沖突，有效提高了田間作業(yè)能力。Utamima 等[25]提出進(jìn)化混合鄰域搜索方法解決農(nóng)機(jī)田間最優(yōu)路徑問(wèn)題。Zou等[26]把迭代貪婪算法引入到解決矩陣制造車(chē)間多艙室自動(dòng)引導(dǎo)車(chē)調(diào)度問(wèn)題，使總成本最小化。該方法的靈活特性在解決不確定場(chǎng)景下的多機(jī)任務(wù)分配問(wèn)題有著天然的優(yōu)勢(shì)，但其應(yīng)用在具體路徑規(guī)劃問(wèn)題中優(yōu)化效果并不理想。本文將迭代貪算法與具體農(nóng)業(yè)播種作業(yè)場(chǎng)景相結(jié)合，以總作業(yè)時(shí)長(zhǎng)（包括作業(yè)時(shí)間及掉頭時(shí)間）為綜合優(yōu)化目標(biāo)，提出了基于改進(jìn)迭代貪婪算法的無(wú)人農(nóng)機(jī)多機(jī)路徑規(guī)劃方法，根據(jù)環(huán)境變化動(dòng)態(tài)調(diào)整無(wú)人農(nóng)機(jī)作業(yè)路徑，避免不確定場(chǎng)景帶來(lái)的規(guī)劃失效問(wèn)題。同時(shí)，考慮輪式農(nóng)機(jī)作業(yè)掉頭模式特點(diǎn)，設(shè)計(jì)路徑優(yōu)化策略，為組織無(wú)人農(nóng)機(jī)機(jī)群規(guī)?；鳂I(yè)提供參考。

1 作業(yè)場(chǎng)景及問(wèn)題描述

1.1 大田多機(jī)作業(yè)不確定場(chǎng)景分析

隨著農(nóng)機(jī)規(guī)模的擴(kuò)大，不同農(nóng)機(jī)中品牌、型號(hào)、新舊程度各有不同[27-28]，農(nóng)機(jī)性能存在一定的差異，并且在多機(jī)作業(yè)中由于自然環(huán)境的變化也會(huì)產(chǎn)生多種不確定場(chǎng)景，導(dǎo)致以往固定路徑規(guī)劃難以順利進(jìn)行，這就迫切需要適應(yīng)不確定場(chǎng)景的路徑規(guī)劃方法來(lái)及時(shí)動(dòng)態(tài)調(diào)整路徑規(guī)劃方案。

基于Wu等[29]總結(jié)的6類(lèi)因素導(dǎo)致的不確定場(chǎng)景，為提升農(nóng)機(jī)作業(yè)質(zhì)量、效率、安全等主要目標(biāo)，本文主要考慮機(jī)械及自然環(huán)境這2類(lèi)關(guān)鍵的不確定因素導(dǎo)致的農(nóng)機(jī)數(shù)量、任務(wù)數(shù)量及作業(yè)效率的動(dòng)態(tài)變化，主要?dú)w納為6類(lèi)不確定場(chǎng)景，如表1所示。

表1 不確定場(chǎng)景分類(lèi)

1.2 問(wèn)題分析

1.2.1 問(wèn)題描述

考慮農(nóng)業(yè)大田作業(yè)一般場(chǎng)景，農(nóng)田分為規(guī)則農(nóng)田（如矩形）和不規(guī)則農(nóng)田（如梯形及其他多邊形），主要研究對(duì)象為帶有可提升機(jī)具的輪式自動(dòng)駕駛拖拉機(jī)，作業(yè)類(lèi)型主要有犁地、耕地、耙地、或播種等，根據(jù)作業(yè)類(lèi)型及機(jī)具幅寬將農(nóng)田分為若干個(gè)等寬的條帶作業(yè)行，如圖1。設(shè)每臺(tái)農(nóng)機(jī)從同一出發(fā)點(diǎn)開(kāi)始作業(yè)，作業(yè)完不需要返回初始或某個(gè)特定的位置。

目前，按照經(jīng)驗(yàn)作業(yè)，多臺(tái)自動(dòng)駕駛農(nóng)機(jī)一般采用并排套圈作業(yè)方式[24,30]，即相鄰的多臺(tái)農(nóng)機(jī)并排逐行作業(yè)，每個(gè)條帶只能由一臺(tái)農(nóng)機(jī)作業(yè)，每臺(tái)農(nóng)機(jī)同一時(shí)間只能作業(yè)一個(gè)條帶，完成當(dāng)前條帶后，需要沿掉頭區(qū)域行駛較長(zhǎng)距離進(jìn)入下一行。

注：圖中數(shù)字表示條帶編號(hào)，紅、綠、黑顏色有向線段分別表示第1～3號(hào)農(nóng)機(jī)路徑。下同。

Note: The numbers in the figure indicatesthe strip No., the red, green and black directed line segment represents the corresponding path ofthe 1st to 3rd agricultural machinery respectively. Same as below.

圖1 基于經(jīng)驗(yàn)的多機(jī)路徑規(guī)劃示意圖

Fig.1 Schematic diagram of multiple machines path planning by experience

為了在不確定場(chǎng)景下更安全、高效完成作業(yè)，本文針對(duì)以上6種不確定場(chǎng)景提出路徑規(guī)劃方法，根據(jù)環(huán)境的變化實(shí)現(xiàn)路徑的動(dòng)態(tài)規(guī)劃，從而確保作業(yè)不間斷進(jìn)行，最大程度減少作業(yè)時(shí)間及掉頭時(shí)間等。

1.2.2 多機(jī)動(dòng)態(tài)路徑規(guī)劃模型

本文以最小化總作業(yè)時(shí)長(zhǎng)為目標(biāo)，提出改進(jìn)迭代貪婪算法解決不確定場(chǎng)景下多機(jī)作業(yè)路徑規(guī)劃問(wèn)題。

為了在數(shù)學(xué)上表述該問(wèn)題，本文定義了一組輛自動(dòng)駕駛農(nóng)機(jī)=[1,…,V]，一塊農(nóng)田劃分為個(gè)作業(yè)條帶=[1,…,S]，每個(gè)條帶幅寬為。為所有農(nóng)機(jī)作業(yè)路徑集合，其中=[1,…,|R|]為第臺(tái)農(nóng)機(jī)作業(yè)路徑集合。f為第臺(tái)農(nóng)機(jī)結(jié)束第行的時(shí)刻，e為第臺(tái)農(nóng)機(jī)從第行進(jìn)入第行的時(shí)刻。

本文基于改進(jìn)迭代貪婪算法為農(nóng)機(jī)每輪迭代選擇從當(dāng)前位置最快到達(dá)的條帶進(jìn)行作業(yè)，見(jiàn)式（1）。

式（3）表示農(nóng)機(jī)作業(yè)路徑集合中農(nóng)機(jī)的數(shù)量閾值，即至少1臺(tái)農(nóng)機(jī)作業(yè)，最多不能超過(guò)個(gè)農(nóng)機(jī)；式（4）表示每臺(tái)農(nóng)機(jī)作業(yè)的條帶數(shù)量閾值，即每臺(tái)農(nóng)機(jī)至少作業(yè)1個(gè)條帶，最多不能超過(guò)個(gè)條帶；式（5）表示每個(gè)條帶只能被1臺(tái)農(nóng)機(jī)作業(yè)1次；式（6）表示第臺(tái)農(nóng)機(jī)結(jié)束第行的時(shí)刻一定早于第臺(tái)農(nóng)機(jī)從第行進(jìn)入第行的時(shí)刻。

2 多機(jī)動(dòng)態(tài)規(guī)劃路徑規(guī)劃算法

基于上述構(gòu)建的多機(jī)動(dòng)態(tài)路徑規(guī)劃模型，本文采用改進(jìn)的迭代貪婪算法IIG（Improved Iterated Greedy）解決大田作業(yè)不確定場(chǎng)景中的路徑規(guī)劃問(wèn)題。

2.1 參數(shù)設(shè)定

由于不同農(nóng)機(jī)性能存在差異，假設(shè)第臺(tái)農(nóng)機(jī)到達(dá)最近的條帶需要的總時(shí)間T，設(shè)農(nóng)機(jī)工作狀態(tài)屬性W，當(dāng)農(nóng)機(jī)空閑時(shí)，W=0，農(nóng)機(jī)在第條帶作業(yè)時(shí)，W=，第條帶狀態(tài)屬性分為作業(yè)狀態(tài)屬性O和配車(chē)狀態(tài)屬性A。其中條帶作業(yè)狀態(tài)分為可作業(yè)、不可作業(yè)，可作業(yè)時(shí)O=0，不可作業(yè)時(shí)O=1；當(dāng)條帶已分配給第臺(tái)農(nóng)機(jī)，配車(chē)狀態(tài)屬性A=，反之，A=0，見(jiàn)表2。

表2 路徑規(guī)劃參數(shù)設(shè)置

2.2 改進(jìn)的迭代貪婪算法

首先，基于農(nóng)田信息、農(nóng)機(jī)信息及作業(yè)信息進(jìn)行參數(shù)設(shè)置，農(nóng)田信息包括農(nóng)田位置、尺寸、邊界，農(nóng)機(jī)信息包括數(shù)量、速度、機(jī)具幅寬、最小轉(zhuǎn)彎半徑，作業(yè)信息包括作業(yè)類(lèi)型、作業(yè)名稱(chēng)。然后將農(nóng)田根據(jù)作業(yè)機(jī)具幅寬劃分為若干等寬平行的條帶，生成農(nóng)機(jī)列表及條帶列表。進(jìn)而基于以上信息初始化相關(guān)參數(shù)。設(shè)所有農(nóng)機(jī)初始狀態(tài)均為空閑狀態(tài)，所有條帶初始化為未作業(yè)且未分配農(nóng)機(jī)，即W=0，O=0，A=0，通過(guò)調(diào)用改進(jìn)迭代貪婪算法生成初始路徑規(guī)劃方案。

如果發(fā)生不確定場(chǎng)景，路徑規(guī)劃結(jié)果將被動(dòng)態(tài)調(diào)整。當(dāng)農(nóng)機(jī)增加，將其加入到空閑農(nóng)機(jī)列表，等待系統(tǒng)迭代調(diào)用；當(dāng)農(nóng)機(jī)發(fā)生故障，將其移除農(nóng)田，并將正在作業(yè)的條帶作業(yè)狀態(tài)置為可作業(yè)；當(dāng)農(nóng)田條帶被占用導(dǎo)致暫時(shí)無(wú)法被作業(yè)，將條帶狀態(tài)置為不可作業(yè)，并將正在作業(yè)的農(nóng)機(jī)置為空閑狀態(tài)；當(dāng)條帶解除占用，將條帶作業(yè)狀態(tài)置為可作業(yè)，等待被其他農(nóng)機(jī)作業(yè)；當(dāng)農(nóng)機(jī)提速或降速，比預(yù)計(jì)時(shí)間提前完成作業(yè)或延期完成作業(yè)，則按照時(shí)間先后、先進(jìn)先出的原則將農(nóng)機(jī)依次加入到空閑農(nóng)機(jī)列表，等待系統(tǒng)迭代遍歷。

3 算例分析

3.1 試驗(yàn)數(shù)據(jù)

3.2 結(jié)果與分析

3.2.1 不確定場(chǎng)景下多機(jī)動(dòng)態(tài)路徑規(guī)劃

基于以上試驗(yàn)數(shù)據(jù)，根據(jù)本文提出的改進(jìn)迭代貪婪算法得出初始路徑規(guī)劃方案，如圖3所示。其中每臺(tái)農(nóng)機(jī)的作業(yè)路徑集合分別為1=[1, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]，2=[2, 5, 7, 11, 13, 17 19, 23]，3=[3, 9, 15, 21]。

當(dāng)不確定場(chǎng)景發(fā)生后，算法自適應(yīng)調(diào)整規(guī)劃路線，具體路徑規(guī)劃結(jié)果如圖4所示。

圖4a模擬按照初始路徑規(guī)劃方案作業(yè)250 s后，農(nóng)機(jī)3發(fā)生排種器損壞，動(dòng)態(tài)調(diào)整路徑規(guī)劃方案后，農(nóng)機(jī)路徑集合由1=[14, 16, 18, 20, 22, 24]，2=[13, 17, 19, 23]，3=[15, 21]，調(diào)整為1=[14, 16, 18, 20, 22, 24, 21]，2=[13, 15, 17, 19, 23]。試驗(yàn)結(jié)果表明，當(dāng)農(nóng)機(jī)發(fā)生故障后，該農(nóng)機(jī)未作業(yè)的條帶可由其他農(nóng)機(jī)高效、順利完成作業(yè)。

圖4b模擬按照初始路徑規(guī)劃方案作業(yè)210 s后，新增農(nóng)機(jī)4，其作業(yè)速度為4=6 m/s，動(dòng)態(tài)調(diào)整路徑規(guī)劃方案后每臺(tái)農(nóng)機(jī)的路徑集合由1=[12, 14, 16, 18, 20, 22, 24]，2=[11, 13, 17, 19, 23]，3=[15, 21]，調(diào)整為1=[13, 15, 19, 22]，2=[12, 16, 21]，3=[17, 24]，4=[11, 14, 18, 20, 23]。試驗(yàn)結(jié)果表明，當(dāng)新增農(nóng)機(jī)后，該農(nóng)機(jī)能夠分配到合適的作業(yè)任務(wù)，與原有農(nóng)機(jī)共同完成剩余作業(yè)。

圖4c模擬按照初始路徑規(guī)劃方案作業(yè)255 s后，由于土質(zhì)變差宜密植，農(nóng)機(jī)1減速，其作業(yè)速度由1=6 m/s降為1=2 m/s，動(dòng)態(tài)調(diào)整路徑規(guī)劃方案后每臺(tái)農(nóng)機(jī)的路徑集合由1=[14, 16, 18, 20, 22, 24]，2=[11, 13, 17, 19, 23]，3=[15, 21]，調(diào)整為1=[15, 17, 20, 22]，2=[11, 13, 16, 18, 21, 23]，3=[14, 19, 24]。試驗(yàn)結(jié)果表明，當(dāng)農(nóng)機(jī)減速后，該農(nóng)機(jī)作業(yè)能力下降，其原有部分任務(wù)被及時(shí)分配給其他農(nóng)機(jī)作業(yè)，避免了因農(nóng)機(jī)降速導(dǎo)致的部分條帶被延期作業(yè)的問(wèn)題。

圖4d模擬按照初始路徑規(guī)劃方案作業(yè)250 s后，由于土質(zhì)改善宜稀植，農(nóng)機(jī)3提速，其作業(yè)速度由3=2 m/s加速為3=8 m/s，動(dòng)態(tài)調(diào)整路徑規(guī)劃方案后每臺(tái)農(nóng)機(jī)的路徑集合由1=[12, 14, 16, 18, 20, 22, 24]，2=[13, 17, 19, 23]，3=[9, 15, 21]，調(diào)整為1=[12, 14, 16, 19, 21, 24]，2=[15, 18, 22]，3=[13, 17, 20, 23]。試驗(yàn)結(jié)果表明，當(dāng)農(nóng)機(jī)提速后，該農(nóng)機(jī)能夠分配更多的作業(yè)任務(wù)，適量減少其他農(nóng)機(jī)任務(wù)，使總作業(yè)效率更高。

圖4e模擬按照初始路徑規(guī)劃方案作業(yè)55 s后，農(nóng)田條帶5，6，7，8被臨時(shí)占用，禁止農(nóng)機(jī)進(jìn)入，動(dòng)態(tài)調(diào)整路徑規(guī)劃方案后每臺(tái)農(nóng)機(jī)的路徑集合由1=[6, 8, 10, 12, 14, 16, 18, 20, 22, 24]，2=[5, 7, 11, 13, 17, 19, 23]，3=[9, 15, 21]，調(diào)整為1=[10, 12, 14, 16, 18, 20, 22, 24]，2=[9, 11, 15, 17, 21, 23]，3=[13, 19]。試驗(yàn)結(jié)果表明，當(dāng)部分條帶被臨時(shí)占用時(shí)，原計(jì)劃執(zhí)行這些條帶的農(nóng)機(jī)能夠順利參與剩余條帶作業(yè)。

圖4f模擬按照?qǐng)D4e 所示的任務(wù)減少場(chǎng)景繼續(xù)作業(yè)250 s 后，農(nóng)田條帶5，6，7，8解除占用，動(dòng)態(tài)調(diào)整路徑規(guī)劃方案后每臺(tái)農(nóng)機(jī)的路徑集合由1=[16, 18, 20, 22, 24]，2=[17, 21, 23]，3=[19]，調(diào)整為1=[5, 7, 16, 18, 20, 22, 24]，2=[6, 17, 19, 23]，3=[8, 21]。試驗(yàn)表明，當(dāng)被占用的條帶解除占用或新增了作業(yè)條帶時(shí)，這些條帶被增加到剩余未作業(yè)任務(wù)中，分配給合適的農(nóng)機(jī)。

基于以上分析，本文提出的改進(jìn)迭代貪婪算法能夠很好的解決不確定場(chǎng)景下的多機(jī)動(dòng)態(tài)路徑規(guī)劃問(wèn)題，具有很好的環(huán)境適應(yīng)性及魯棒性，可支持農(nóng)業(yè)大田無(wú)人作業(yè)，實(shí)現(xiàn)多機(jī)高效精準(zhǔn)作業(yè)。

3.2.2 算法性能分析

本文提出的改進(jìn)迭代貪婪算法IIG分別與傳統(tǒng)方法TM（按經(jīng)驗(yàn)并排作業(yè)方法）、迭代貪婪算法IG在總作業(yè)時(shí)間、總掉頭時(shí)間進(jìn)行算法性能比較。為便于試驗(yàn)結(jié)果分析，對(duì)比方法計(jì)算的總作業(yè)時(shí)間記為OTX；IIG 計(jì)算得到的時(shí)間記為OT；OT比OTX總作業(yè)時(shí)間下降率記為OTDR，具體定義如下：

對(duì)比方法計(jì)算的總掉頭時(shí)間記為T(mén)TX；IIG 計(jì)算得到的總掉頭時(shí)間記為T(mén)T；TT比TTX總掉頭時(shí)間下降率記為T(mén)TDR，具體定義如下：

分析表3可知，農(nóng)機(jī)速度標(biāo)準(zhǔn)差（記為SD）從0增加到4，3臺(tái)農(nóng)機(jī)在300 m×135 m矩形農(nóng)田并排作業(yè)的總作業(yè)時(shí)間OTX均為900 s。IIG方法與并排作業(yè)方法相比，由算法策略決定了在總掉頭時(shí)間上二者差異較小，作業(yè)時(shí)間差異較大。因此，本試驗(yàn)中總作業(yè)時(shí)間指標(biāo)間接反映了總作業(yè)時(shí)長(zhǎng)的優(yōu)化效果。試驗(yàn)結(jié)果表明，在3臺(tái)農(nóng)機(jī)速度相等或差異很小時(shí)，總作業(yè)時(shí)間相等，即OTDR=0。隨著農(nóng)機(jī)速度差異的增加，IIG比TM計(jì)算 的總作業(yè)時(shí)間下降率呈階梯遞增趨勢(shì)，平均下降率約35%。

表3 作業(yè)時(shí)間優(yōu)化結(jié)果

注：1、2、3分別為農(nóng)機(jī)1、2、3的作業(yè)速度，m·s-1；SD為農(nóng)機(jī)速度標(biāo)準(zhǔn)差，m·s-1；OT為IIG方法計(jì)算的總作業(yè)時(shí)間，s；OTDR為IIG比按經(jīng)驗(yàn)并排作業(yè)方法總作業(yè)時(shí)間下降率，%。

Note:1,2,3are the operating speeds of agricultural machinery 1, 2 and 3 respectively, m·s-1; SD is the standard deviation of agricultural machinery speed, m·s-1;OT is the total operation time calculated by IIG(Improved Iterated Greedy) method, s; OTDR is the decline rate of total operation time of IIG compared with that of side by side operation method according to experience, %.

通過(guò)上述分析可得，當(dāng)農(nóng)機(jī)性能存在差異時(shí)，IIG方法路徑優(yōu)化后可比傳統(tǒng)方法減少總作業(yè)時(shí)間，并且隨著農(nóng)機(jī)性能差異越大，總作業(yè)時(shí)間下降率越大。

通過(guò)3組試驗(yàn)分析不同機(jī)具幅寬的掉頭時(shí)間優(yōu)化結(jié)果?？捎棉r(nóng)機(jī)共有5臺(tái)，農(nóng)機(jī)初始速度序列為=[6, 4, 2, 2, 6] (m/s)，每臺(tái)農(nóng)機(jī)轉(zhuǎn)向半徑均為7.15 m。設(shè)試驗(yàn)初始規(guī)模為4臺(tái)農(nóng)機(jī)，3組試驗(yàn)農(nóng)田大小分別300 m×96 m、 300 m×144 m、300 m×216 m，每塊農(nóng)田對(duì)應(yīng)幅寬分別為4、6、9 m。每組試驗(yàn)分別在6種不確定場(chǎng)景下計(jì)算總掉頭時(shí)間，見(jiàn)表4。由于本文提出的改進(jìn)迭代貪婪方法IIG與傳統(tǒng)迭代貪婪方法IG均適用于解決不確定場(chǎng)景問(wèn)題，在算法改進(jìn)策略上主要考慮的是對(duì)掉頭時(shí)間的節(jié)約，2種方法所得的作業(yè)時(shí)間相等。因此，總掉頭時(shí)間指標(biāo)可間接反映總作業(yè)時(shí)長(zhǎng)的優(yōu)化效果。試驗(yàn)對(duì)比分析可得，作業(yè)幅寬分別為4、6、9 m時(shí)，IIG方法相對(duì)于IG方法總掉頭時(shí)間平均下降了20.91%、20.64%、9.15%。

表4 掉頭時(shí)間優(yōu)化結(jié)果

注：-V1表示移除農(nóng)機(jī)V1，+V5表示增加農(nóng)機(jī)V5，S-4表示減少4個(gè)條帶，S+4表示增加4個(gè)條帶，V1ˉ表示農(nóng)機(jī)V1速度由6 m·s-1降至4 m·s-1、V4-表示農(nóng)機(jī)V4速度由2 m·s-1提速至4 m·s-1。TTX、TT分別為IG、IIG方法計(jì)算的總掉頭時(shí)間，s；TTDR為IIG比IG總掉頭時(shí)間下降率，%。

Note: -V1 indicates the removal of the agricultural machinery V1, +V5 indicates the increase of the agricultural machinery V5, S-4 indicates the decrease of 4 strips, S+4 indicates the increase of 4 strips, V1ˉindicates the deceleration of the agricultural machinery V1 from 6 m·s-1to 4 m·s-1, V4-indicates the acceleration of the agricultural machinery V4 from 2 m·s-1to 4 m·s-1. TTX and TT are the total turning time calculated by IG(Iterated Greedy) and IIG methods respectively, s; and TTDR is the decline rate of total turning time of IIG compared with IG, %.

試驗(yàn)表明，作業(yè)幅寬小于農(nóng)機(jī)轉(zhuǎn)向半徑時(shí)，節(jié)約掉頭時(shí)間較多，反之節(jié)約時(shí)間相對(duì)較少。通常在實(shí)際大田播種機(jī)具幅寬主要為4～9 m，試驗(yàn)數(shù)據(jù)表明通過(guò)本文提出的方法可平均節(jié)省總掉頭時(shí)間約17%。

4 結(jié) 論

為提高農(nóng)業(yè)大田作業(yè)效率，本文以總作業(yè)時(shí)長(zhǎng)為目標(biāo)，提出了一種不確定場(chǎng)景下多臺(tái)農(nóng)機(jī)作業(yè)路徑規(guī)劃算法，并以矩形農(nóng)田進(jìn)行了不確定場(chǎng)景路徑規(guī)劃試驗(yàn)及算法性能對(duì)比試驗(yàn)。試驗(yàn)結(jié)果表明，在6種常見(jiàn)的不確定場(chǎng)景中，該方法能夠及時(shí)高效地調(diào)整路徑規(guī)劃方案，始終能為不同數(shù)量、不同性能的農(nóng)機(jī)找到更優(yōu)的作業(yè)路徑。

改進(jìn)的迭代貪婪（Improved Iterated Greedy, IIG）方法可比傳統(tǒng)并排作業(yè)方法平均可減少總作業(yè)時(shí)間約35%，并且隨農(nóng)機(jī)性能差異越大，總作業(yè)時(shí)間下降率越大；此外，針對(duì)一般播種作業(yè)，在不確定場(chǎng)景中，該方法比迭代貪婪（Iterated Greedy, IG）方法可減少總掉頭時(shí)間達(dá)17%。

綜上，在不確定場(chǎng)景下，本文提出的改進(jìn)迭代貪婪算法始終能以最短的掉頭時(shí)間為多臺(tái)農(nóng)機(jī)找到最優(yōu)作業(yè)路徑，動(dòng)態(tài)規(guī)劃策略可確保所有作業(yè)連續(xù)、高效地完成，提高機(jī)群作業(yè)效率，降低作業(yè)成本。

[1] 吳才聰，方向明．基于北斗系統(tǒng)的大田智慧農(nóng)業(yè)精準(zhǔn)服務(wù)體系構(gòu)建[J]. 智慧農(nóng)業(yè)，2019，1(4)：83-90．

Wu Caicong, Fang Xiangming. Construction of precision service system of field smart agriculture based on Beidou system[J]. Smart Agriculture, 2019, 1(4): 83-90. (in Chinese with English abstract)

[2] Sorensen C G, Bochtis D D. Conceptual model of fleet management in agriculture[J]. Biosystems Engineering, 2010, 105(1): 41-50.

[3] Santos L C, Santos F N, Pires E J S, et al. Path planning for ground robots in agriculture: A short review[C]//2020 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC).IEEE, 2020: 61-66.

[4] Wang J, Zhu Y T, Chen Z B, et al. Auto-steering based precise coordination method for in-field multi-operation of farm machinery[J]. International Journal of Agricultural and Biological Engineering, 2018, 11(5): 174-181.

[5] Zhu Y T, Wang J, Wu C C. Cloud based precise coordination system for multi-machinery of single-operation[J]. IFAC-PapersOnLine, 2018, 51(17): 626-630.

[6] Zhou K, Jensen A L, Bochtis D D, et al. Simulation model for the sequential in-field machinery operations in a potato production system[J]. Computers and Electronics in Agriculture, 2015, 116: 173-186.

[7] Rodias E, Berruto R, Busato P, et al. Energy savings from optimised in-field route planning for agricultural machinery[J]. Sustainability, 2017, 9(11): 1956.

[8] 張漫，季宇寒，李世超，等．農(nóng)業(yè)機(jī)械導(dǎo)航技術(shù)研究進(jìn)展[J]．農(nóng)業(yè)機(jī)械學(xué)報(bào)，2020，51(4)：1-18.

Zhang Man, Ji Yuhan, Li Shichao, et al. Research progress of agricultural machinery navigation technology[J]. Transactions of Chinese Society for Agricultural Machinery, 2020, 51(4): 1-18. (in Chinese with English abstract)

[9] Bechar A, Vigneault C. Agricultural robots for field operations. Part 2: Operations and systems[J]. Biosystems Engineering, 2017, 153: 110-128.

[10] 曹如月，李世超，季宇寒，等．多機(jī)協(xié)同導(dǎo)航作業(yè)遠(yuǎn)程管理平臺(tái)開(kāi)發(fā)[J]．中國(guó)農(nóng)業(yè)大學(xué)學(xué)報(bào)，2019，24(10)：92-99．

Cao Ruyue, Li Shichao, Ji Yuhan, et al. Development of remote monitoring platform for multi-machine cooperative navigation operation[J]. Journal of China Agricultural University, 2019, 24(10): 92-99. (in Chinese with English abstract)

[11] Bsaybes S, Quilliot A, Wagler A K. Fleet management for autonomous vehicles: Online PDP under special constraints[J]. RAIRO-Operations Research, 2019, 53(3): 1007-1031.

[12] Hameed I A. A coverage planner for multi-robot systems in agriculture[C]//2018 IEEE International Conference on Real-time Computing and Robotics (RCAR). IEEE, 2018: 698-704.

[13] Wu C C, Chen Z B, Wang D X, et al. A cloud-based in-field fleet coordination system for multiple operations[J]. Energies, 2020, 13(4): 775.

[14] Zhou K, Jensen A L, Bochtis D D, et al. Quantifying the benefits of alternative fieldwork patterns in a potato cultivation system[J]. Computers and Electronics in Agriculture, 2015, 119: 228-240.

[15] Bochtis D D. Planning and control of a fleet of agricultural machines for optimal management of field operations[D]. Greece: Aristotle University, 2008.

[16] Bochtis D D, Vougioukas S G. Minimising the non-working distance travelled by machines operating in a headland field pattern[J]. Biosystems Engineering, 2008, 101(1): 1-12.

[17] Bochtis D D, Sorensen C G. The vehicle routing problem in field logistics part I[J]. Biosystems Engineering, 2009, 104(4): 447-457.

[18] Jin J, Tang L. Optimal coverage path planning for arable farming on 2D surfaces[J]. Transactions of the ASABE, 2010, 53(1): 283-295.

[19] Hameed I A, Bichtis D D, Sorensen C G. Driving rangle and track sequence optimization for operational path planning using genetic algorithms[J]. Applied Engineering in Agriculture, 2011, 27(6): 1077-1086.

[20] Bakhtiari A, Navid H, Mehri J, et al. Operations planning for agricultural harvesters using ant colony optimization[J]. Spanish Journal of Agricultural Research, 2013, 11(3): 652-660.

[21] Conesa-Mu?oz J, Bengochea-guevara J M, Andujar D, et al. Route planning for agricultural tasks: A general approach for fleets of autonomous vehicles in site-specific herbicide applications[J]. Computers and Electronics in Agriculture, 2016, 127: 204-220.

[22] Conesa-munoz J, Pajares G, Ribeiro A. Mix-opt: A new route operator for optimal coverage path planning for a fleet in an agricultural environment[J]. Expert Systems with Applications, 2016, 54: 364-378.

[23] Seyyedhasani H, Dvorak J S. Using the vehicle routing problem to reduce field completion times with multiple machines[J]. Computers and Electronics in Agriculture, 2017, 134: 142-150.

[24] 姚竟發(fā)，滕桂法，霍利民，等. 聯(lián)合收割機(jī)多機(jī)協(xié)同作業(yè)路徑優(yōu)化[J]. 農(nóng)業(yè)工程學(xué)報(bào)，2019，35(17)：12-18.

Yao Jingfa, Teng Guifa, Huo Limin, et al. Path optimization of multi machine cooperative operation of combine[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2019, 35(17): 12-18. (in Chinese with English abstract)

[25] Utamima A, Reiners T, Ansaripoor A H. Optimisation of agricultural routing planning in field logistics with evolutionary hybrid neighbourhood search[J]. Biosystems Engineering, 2019, 184: 166-180.

[26] Zou W Q, Pan Q K, Tasgetiren M F. An effective iterated greedy algorithm for solving a multi-compartment AGV scheduling problem in a matrix manufacturing workshop[J]. Applied Soft Computing, 2021, 99(3): 106945.

[27] Han Shufeng, He Yong, Fang Hui. Overview of the development of automatic navigation and driverless vehicles for agricultural machinery[J]. Journal of Zhejiang University (Agriculture and Life Sciences Edition), 2018, 44(4): 381-391, 515.

韓樹(shù)豐，何勇，方慧. 農(nóng)機(jī)自動(dòng)導(dǎo)航及無(wú)人駕駛車(chē)輛的發(fā)展綜述[J]. 浙江大學(xué)學(xué)報(bào)：農(nóng)業(yè)與生命科學(xué)版，2018，44(4)：381-391，515. (in English with Chinese abstract)

[28] 冷博峰，馮中朝，周曉時(shí)，等. 農(nóng)機(jī)購(gòu)置補(bǔ)貼對(duì)農(nóng)戶(hù)購(gòu)機(jī)投入模型與影響分析[J]. 農(nóng)業(yè)工程學(xué)報(bào)，2020，36(23)：324-334.

Leng Bofeng, Feng Zhongchao, Zhou Xiaoshi, et al. Model and impact analysis of agricultural machinery purchase subsidy on farmers' purchase input [J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2020, 36(23): 324-334. (in Chinese with English abstract)

[29] Wu C C, Cai Y P, Hu B B, et al. Classification and evaluation of uncertain influence factors for farm machinery service[J]. International Journal of Agricultural and Biological Engineering, 2017, 10(6): 164-174.

[30] Zhang C, Noguchi N. Development of a multi-robot tractor system for agriculture field work[J]. Computers and Electronics in Agriculture, 2017, 142: 79-90.

[31] Zhou K. Simulation Modelling for In-field Planning of Sequential Machinery Operations in Cropping Systems[D]. Denmark: Aarhus University, 2015.

Dynamic path planning method for multiple unmanned agricultural machines in uncertain scenarios

Liang Yajie1, Yang Lili1, Xu Yuanyuan1, Chen Zhibo1, Feng Yarong1, Wu Caicong1,2※

(1100083; 2100083)

Most machinery can be hands-free and remotely operated in modern agriculture. Almost all tractors are equipped with some sort of GPS technology in recent years, indicating a step on the way to fully autonomous farms in the future. A series of multiple agricultural machinery have also been introduced to realize highly efficient plant and harvest, while reducing the risk of natural disasters for large-scale production in China. Particularly, the vehicle can travel on pre-mapped roads, even to move around the obstacle. However, the parallel operation is still widely used in current multiple machinery, indicating the fixed agricultural machinery and static fixed route in advance. Furthermore, there are often most uncertain scenarios, such as a sudden failure, temporary increase, and inconsistent work efficiency of agricultural machinery in the actual farming and harvesting. These uncertainties have also posed great challenges to the operation of multiple agricultural machinery. Therefore, it is necessary to explore the multi-machine dynamic path planning, whenever the information is accessible about the barrier, particularly when the environment tends to be unpredictable and changeable. Moreover, the future unmanned farm is highly requiring the large-scale operation of multiple agricultural machinery. In this study, a multi-machine dynamic path planning was proposed for the wheeled autonomous tractors in various uncertain scenarios using an Improved Iterative Greedy (IIG) algorithm. The total completion time was also taken as the comprehensive optimization objective. More importantly, an attempt was made to deal with the inefficient or even invalid path planning after the occurrence of uncertain scenarios. The experimental results show that the scheme of path planning was timely and efficiently adjusted in uncertain scenarios. An optimal path was also found for the different numbers and performances of agricultural machinery during an iterative process. The total operation time of IIG optimized operation path in rectangular farmland decreased by 35%, compared with the traditional side-by-side operation. Specifically, there was a significant optimization effect, as the performance of agricultural machinery varied greatly. Additionally, the total turning time was reduced by 17% after IIG optimization, compared with the original. Consequently, the optimization algorithm presented a remarkable performance in uncertain scenarios, indicating excellent robustness and environmental adaptability. The finding can also provide a strong reference for the path planning of multiple autonomous machinery in unmanned farmland.

agricultural machinery; automation; driverless; multi-machine cooperative operation; dynamic path planning

10.11975/j.issn.1002-6819.2021.21.001

S24

A

1002-6819(2021)-21-0001-08

梁亞杰，楊麗麗，徐媛媛，等.不確定場(chǎng)景下無(wú)人農(nóng)機(jī)多機(jī)動(dòng)態(tài)路徑規(guī)劃方法[J]. 農(nóng)業(yè)工程學(xué)報(bào)，2021，37(21)：1-8.doi：10.11975/j.issn.1002-6819.2021.21.001 http://www.tcsae.org

Liang Yajie, Yang Lili, Xu Yuanyuan, et al. Dynamic path planning method for multiple unmanned agricultural machines in uncertain scenarios[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2021, 37(21): 1-8. (in Chinese with English abstract) doi：10.11975/j.issn.1002-6819.2021.21.001 http://www.tcsae.org

2021-07-14

2021-10-20

北京市科技計(jì)劃項(xiàng)目（Z201100008020008）

梁亞杰，博士生，研究方向?yàn)闊o(wú)人農(nóng)機(jī)路徑規(guī)劃、導(dǎo)航控制。Email：liangyajie@cau.edu.cn.

吳才聰，副教授，博士生導(dǎo)師，研究方向?yàn)檗r(nóng)機(jī)導(dǎo)航與位置服務(wù)。Email：wucc@cau.edu.cn.