同種農機機群動態作業任務分配方法

王 猛，趙 博，劉陽春，偉利國，汪鳳珠，方憲法

（中國農業機械化科學研究院土壤植物機器系統技術國家重點實驗室，北京 100083）

0 引言

中國是農業大國，農業機械化可極大提高農業生產效率、減輕農民體力勞動。隨著農機合作社和農場作業模式的快速發展，農機和土地都呈現集中的趨勢，如何更有效地規劃機群作業，提高作業效率，對有作業窗口期要求的農業生產具有重大作用。

動態任務分配是機群作業領域的一個重要研究內容，動態任務分配指機群作業過程中，面對導致機群無法繼續執行原有作業計劃的意外情況時，根據任務執行進度和機群位置，對作業任務計劃進行相應的調整使得機群能夠繼續執行并完成新的任務計劃。動態任務分配方法在機器人搜索、無人機作戰、水下機器人搜索和無人機搜索等領域有了較深入的研究和發展[1-5]。研究人員對靜態任務分配技術研究較多，研究方法包括基于作業經驗和效率的任務分配[6-8]、基于聚類的任務分配[9]、基于博弈論的任務分配[10]和基于啟發式算法的任務分配[11-16]等，對動態任務分配研究較少，主要采用合同網算法，動態任務分配比靜態任務分配更加復雜[17-20]。農機作業領域的相關研究有任務規劃和調度等。其中任務規劃指規劃農機執行任務的先后順序和田塊間的路徑，曹如月等[21]采用蟻群算法解決機群作業任務規劃，使農機行駛的距離最短；Jensen等[22]研究了一臺運糧車對多臺收割機運糧的田塊內和田間的路徑規劃方法，使農機作業代價最小；姚竟發等[23]提出聯合收割機多機無沖突協同作業路徑優化算法，縮短了矩形農田和梯形農田農機作業時間。農機調度是對一系列作業點選擇合適的行車路徑，讓農機有序地通過它們，在滿足作業點的時間窗和所需農機數約束條件下，達到路程最小或收益最高[24-28]。隨著我國農機合作社和農場作業模式的快速發展和農機管控平臺的開發[28]，農機和土地趨于集中且參數可知趨勢，如何在合作社或農場土地范圍內對多臺農機進行有效的任務分配，并在有突發狀況條件下進行合理的任務再分配對具有強“農時”性的農業生成具有重要意義。

本研究以同種作業農機為研究對象，以農機合作社或農場作業模式為作業場景，綜合考慮機群中作業時間最長的農機作業時間、農機機群的油耗和路上的路程建立機群代價，以代價最小作為優化目標，構建基于合同網算法的機群動態任務分配招投標流程和投標代價函數，針對農機作業特點優化合同網算法以降低機群作業代價、得到最優動態任務分配結果。

1 機群系統體系結構

根據農機機群動態任務分配特點設計了農機機群作業的體系結構，主要包括農機、服務器和客戶端三個部分。其中農機安裝車載計算機、北斗定位模塊和無線自組網模塊等，可實現自身定位和與其他農機通信；服務器中儲存田塊信息和農機信息并且具有計算功能；客戶端可以選擇和下發任務到指定作業機群。其結構如圖1所示。

2 農機機群代價數學模型

2.1 基本假設

農機機群作業過程中，作業情況往往過于復雜，為突出動態任務分配問題，簡化其他次要問題，做出農機作業的基本假設。

1）作業機群為具有高精度定位與導航功能的同種作業農機。

2）任務田塊數量大于作業農機數量。

3）每個任務田塊只有1臺農機作業，同一臺農機可以在連續多個任務田塊作業。

4）不考慮其他補給或配合農機的調配。

5）任務田塊沒有嚴格的作業時間窗口要求。

6）農機機群從車庫出發，完成全部任務后返回車庫。

7）機群的作業時間為機群中用時最長農機的作業時間。

2.2 目標函數

假設作業的農機數量為m，任務田塊的數量為n，用A={a1,a2,…,am}表示農機集合，T={T1,T2,…,Tn}表示任務田塊集合，任務分配是指將任務田塊集合T按一定的作業順序分配給農機集合A。

農機作業過程中，對于農資、能源補給類車輛常以農機的路程為代價；對于需要在田間作業的農機常以農機作業的總時間為代價。本文考慮機群的作業時間、油耗和路程建立目標函數：

式中f為機群代價函數，α為系數向量，α=[1,0,0]表示以機群作業時間為代價，α=[0,1,0]表示以機群作業油耗為代價，α=[0,0,1]表示以機群到達作業地塊的路程為代價；ti為農機ai的作業時間，h；ci為農機ai的油耗，L；si為農機ai路上的路程，km。

當系數確定的情況下，當代價函數最小時，對應的任務分配方案即為該確定系數下多機協同最優分配方案。

2.2.1 田間路徑規劃

參考文獻[29-31]，以農田最長邊為作業方向可有效提高作業效率，降低作業代價；滿足半圓形調頭時采用半圓形調頭，不滿足半圓形調頭時采用弓形調頭可提高調頭效率，本文以不滿足半圓形調頭情況為例進行研究。

地頭轉彎區域分為種植農作物和不種植農作物2種情況，本文以種植農作物為例設置作業模式，根據文獻[32]，為實現作業區域的全覆蓋，采用直行與繞行相結合的方式進行路徑規劃，如圖2所示。

以圖2所示的帶斜邊的多邊形田塊為例，根據文獻[32]，弓形路徑調頭中地頭最小轉彎地帶寬度E∏為

式中R為農機的最小轉彎半徑，m；W為作業幅寬，m；Lk為農機機組中心至最遠農具作業部件的距離，m。

為使繞行路徑可以滿若干幅寬作業，令地頭轉彎地帶寬度為農機幅寬的整數倍，則地頭轉彎寬度E為

其中

弓形路徑調頭過程中，根據幾何關系，農機轉彎跳過的最小路徑smin為

根據文獻[30，33]，采用弓形調頭路徑時實現作業區域全覆蓋的的最小路徑數量Bmin為

作業過程中，當田塊剩余寬度小于農機作業幅寬時，收獲機械可直接進行作業；播種機械等為避免重復作業可采用小型機械補耕或調整相鄰作業行出種行數的方式，本研究中田塊數量較多且分散，采用后種方式。農機在田塊中總的縱向路徑數量N為田塊垂直于作業路徑的寬度與作業幅寬的比值，則N為

式中bT為任務田塊垂直于作業路徑的寬度，m。

當(N-2kE)≥Bmin時，滿足弓形調頭要求，將農田劃分為多個標準區塊和1個非標準區塊，為使農機在每個區塊都能完成全覆蓋作業，令標準區塊路徑數量為Bmin，非標準區塊數量BN≥Bmin，采用弓形調頭路徑進行逐區塊作業。圖3所示為smin=2時的區塊劃分結果，其中左側為標準區塊右側為非標準區塊。標準區塊數量ks為

標準區塊路徑編號qi,j為

式中qi,j為田塊中第j個區塊內第i個順序的路徑編號。

非標準區塊路徑數量BN為

非標準區域跳過的路徑數量sN為

非標準區塊路徑編號為

農機進入和離開田塊位于同一端地頭時，作業路徑數量為偶數，位于不同端地頭時則為奇數。若作業路徑數量為偶數，要實現農機進入和離開農田位置位于不同端地頭、或作業路徑數量為奇數要實現農機進入和離開農田位置位于同一端地頭時，需要在繞行區域增加一條空行路徑。當2個需要作業的田塊地頭相鄰，且農機可以從地界處進入田塊時，令要進入的田塊為目標田塊，正在作業的田塊為當前田塊，為方便農機進入目標田塊后經過最小的調整就能作業，令當前田塊的最后作業路徑與目標田塊的第1條作業路徑橫向偏差最小，如圖4所示，其中No.last（白色）行為當前田塊的最后作業行，區塊劃分中不包括No.last行。

根據文獻[32]，弓形調頭路徑近似長度S∏為

式中x為調頭中2條路徑的距離，m。

(N-2kE)2kE且(N-2kE)

魚尾形調頭路徑最小轉彎地帶寬度ET為

魚尾形調頭路徑近似長度ST為

2.2.2 農機作業時間

農機ai的作業時間ti主要由農機在路上的時間和農機在田塊的時間2部分構成：

式中tRi為農機ai在路上的時間，h；tFi為農機ai在田塊的時間，h；si為農機ai在路上的總路程，km；vi為農機ai在路上的速度，km/h。

2.2.3 農機作業路上的總路程

建立n個任務田塊間農機可行駛的實際最短距離矩陣，若將車庫作為第0個任務，得到矩陣D為

式中dij為第i-1個任務田塊到第j-1個任務田塊之間的實際可行駛距離，km，i,j=2,3,…,n+1,且i≠j。

如果j、k兩個任務田塊地頭相鄰，且農機可從地界直接駛入田塊進行作業，則dj+1,k+1=0。

總路程si由3部分組成：農機ai從車庫到其第一個任務田塊Tj的路程d1,j+1、農機從第j個任務田塊Tj到下一個任務田塊Tk的路程dj+1,k+1、農機從最后一個任務田塊Tl回到車庫的路程d1,l+1，其中j,k,l=1,2,…,n。具體計算如下：

其中

農機在田塊的作業時間tFi主要由作業時間、調頭時間和直線空行時間構成：

式中li,j,k為農機ai在任務田塊Tj的第k條直行路徑的長度，km；bi,j,k為農機ai在任務田塊Tj中繞行的第k條橫行路徑的長度，km；Si,j,k為農機ai在任務田塊Tj的第k條轉彎路徑的長度，km；Ni,j,t為農機ai在任務田塊Tj的調頭數量；lB為農機ai在任務田塊Tj的空行直線路徑長度，km；vwi為農機ai的作業速度，km/h；vti為農機ai在田塊的調頭的速度，km/h。 其中

2.2.4 農機作業油耗

農機ai的作業油耗ci主要農機在路上的油耗和農機在田塊的油耗由2部分構成：

式中cRi為農機ai在路上的油耗，L；cFi為農機ai在田塊的油耗，L；Fci為農機ai非作業狀態下平均每公里的油耗，L/km；Fwci為農機ai作業狀態下平均每公里油耗，主要由作業油耗、調頭油耗和直線空行油耗構成，L/km。

3 動態任務分配

農機機群作業過程中，受一些因素的影響，機群無法繼續執行原有作業計劃，需要根據任務執行進度和機群狀態進行動態任務分配。農機機群作業過程中需要進行動態任務分配的情況主要有：①新增作業任務；②作業過程中有農機出現故障無法繼續作業；③原有作業任務中一些作業任務取消。其中情況①、②是多機作業過程中最常見的情況，本文主要針對情況①、②進行動態任務分配研究。

動態任務分配分為集中式和分布式，在本文的體系結構中，集中式任務分配由服務器負責整個機群的任務分配，分布式任務分配由整個機群聯合處理進行任務分配。其中，在集中式任務分配中服務器處理所有計算，需要服務器具有強大的計算功能，對終端設備要求較低，當終端很多時會導致響應速度變慢；在分布式任務分配中所有終端都參與計算，對終端設備要求較高，處理能力強。考慮到目前農機終端計算機都有較強的計算能力，為減少服務器壓力，采用分布式方式處理動態任務分配問題。

3.1 合同網算法

合同網算法（CNP，Contract Net Protocol）是處理分布式任務分配方法的常用算法，通過模仿經濟行為的“招標-投標-中標”機制來實現任務分配[34-36]，其基本流程如圖5所示。

使用CNP解決農機機群任務分配過程中，服務器端作為招標者、農機端作為投標者。假設機群原分配任務及順序為最優分配結果，動態任務分配過程中投標者計算投標值時，使用將招標任務插入原有任務序列的方法計算農機ai執行新任務田塊Tj的代價Δfij，招標者選擇Δfij最小的招標者作為中標者。

農機ai對任務田塊Tj投標的代價函數Δfi j為

式中tij為第i臺農機添加任務田塊Tj后所需作業的總時間，h；tmax為招標開始前整個機群的機群工作時間，h；Δci為第i臺農機添加任務Tj后所需油耗的增量，L；Δsi為第i臺農機添加任務Tj后路上路程的增量，km。

當第i臺農機中標任務田塊Tj后整個機群代價f'為

式中f為招標前機群的總代價。

3.2 改進合同網算法

3.2.1 任務分配結構設計

為減少服務器的計算量，設計了基于農機間招-投標過程的動態任務分配方法。如圖6所示，服務器端設有管理者和公告板2個模塊，管理者可以與客戶端和農機終端進行通信，當有新任務需要動態分配時，管理者通知相關農機讀取公告板；公告板接收管理者信息并展示，起到信息共享作用；農機終端可與管理者通信、讀取公告板信息；動態任務分配在農機終端之間進行。

3.2.2 算法改進

在設計的動態任務分配結構中，任務分配過程在正常作業的農機間進行，所有作業的農機作為投標者，其中一臺農機既作為招標者又作為投標者。招投標過程中可能出現以下問題，如果招標者距離其他投標者距離過遠會加大丟包率，影響任務分配效果；如果招標者為最終的中標者，多次招投標通信為無效通信；在有新任務加入的情況下，農機原有任務及序列可能不是最優分配。基于以上問題設計了幾種改進基于公告板合同網算法的幾種辦法。

1）選擇招標者

任務分配的招投標過程由農機間無線網絡完成通信，選擇招標者使招標者與投標者之間的直線距離和最短

式中(xi,yi)為農機ai當前位置的高斯平面坐標，m。

2）設定招標閾值

由于招標者自身也作為投標者，為減少無效投標，降低任務分配過程中農機間的通信，采用設定招標閾值的方法，招標者在對任務Tj進行招標前，首先計算招標者自身執行該任務的最小代價Δf j作為動態閾值。

式中Δfbidj為招標者執行新增任務Tj的代價。

投標者ai接收招標信息并計算自身執行該任務的最小代價Δfij，如果Δfij<Δf j發送投標信息，如果Δfij≥Δf j，則不發送投標信息。

3）中標者任務再分配

為使農機任務分配更加均衡，減小農機間作業代價的差，建立單機代價函數，按中標農機作業代價從高到低的順序依次作為招標者進行任務再分配，i臺農機的代價函數fi為

按招標農機任務面積從小到大的順序進行任務再分配，農機ai對任務田塊Tj招標的閾值Δf j為

式中ti-j為農機ai去掉任務田塊Tj后完成任務的時間，h；Δci'為農機ai去掉任務田塊Tj后減少的油耗，L；Δsi'為農機ai去掉任務田塊Tj后減少的路程，km。

4）農機間任務交換

農機執行任務過程中有部分代價發生在從一個任務到另一個任務的路程中，進行合理的任務交換以減少總路程是降低整體代價的一個辦法。

設農機ai執行任務Tj的路程代價fsij為

式中si-j為農機ai去掉任務Tj后的路程，km。

任務交換流程如下：

① 完成任務代價最大的農機ai計算出最大路程代價max(fsij)和對應的任務田塊Tj。

② 農機ai作為招標者對任務田塊Tj進行交換招標；

③ 其他工作正常的農機作為投標者，投標者將任務田塊Tj依次與自身未作業任務田塊進行替換，并使用2-opt進行優化，計算替換后自身最小代價；

④ 如果替換后代價小于替換前，該任務作為投標信息；

⑤ 招標者計算刪除任務j后加入每個投標任后的代價，并取最小代價fik和對應的任務田塊Tk；

⑥ 如果fik

3.3 基于改進合同網算法的任務分配流程

基于改進合同網算法的任務分配流程如圖7所示。

4 仿真試驗

由于農機油耗與農機牽引力正相關，每公里油耗確定困難,為驗證改進合同網算法動態任務分配效果，以α=[1,0,0]為例，從中國農機開發的農業機械化精準作業平臺選擇包括多個較集中且平整地塊參數作為仿真試驗地塊參數，選擇農機合作社常見拖拉機及機具參數作為仿真試驗農機參數，試驗田塊如圖8所示，共15個任務，任務主要參數如表1所示，田塊較規則，均為標準矩形田塊；共4臺農機，農機主要性能參數如表2所示。分別用傳統合同網算法和改進合同網算法對新增任務情況和出現故障的情況進行動態任務分配仿真試驗。

表2 農機性能參數 Table 2 Performance parameters of agricultural machineries

表1 任務田塊參數 Table 1 Task field parameters

4.1 有新任務加入情況的動態任務分配試驗

假設農機a1、a2和a3共同進行作業，分別以{T1～T10}、{T1～T11}和{T1～T12}為原任務，{T11～T14}、{T12～T15}和{T13～T15}為新增任務。使用遺傳算法將原任務進行靜態任務分配，原任務的多機協同代價分別為7.63 、8.57 和9.22 h。實際作業過程中，假設農機同時開始作業，新增任務可能發生在農機作業后的各個階段，根據原有任務的作業時間，假設當作業時間分別為2、4、6 h時進行新增任務的動態任務分配，任務分配結果如表3所示。

表3 新增任務情況下動態任務分配結果 Table 3 Dynamic task allocation results in the case of new tasks

{T1～T10}為原任務{T11～T14}為新增任務時，動態任務分配前的任務分配結果為農機a1田塊作業順序為1→2 →4→6，農機a2田塊作業順序為7→8→10→9，農機a3田塊作業順序為3→5，動態任務分配結果表明，基于改進合同網算法比基于傳統合同網算法的動態任務分配農機機與服務器通信次數較少85%，機群多機協同時間代價降低7.34%～8.05%。

{T1～T11}為原任務{T12～T15}為新增任務時，動態任務分配前的任務分配結果為農機a1田塊作業順序為5 →10→9→11，農機a2田塊作業順序為2→1→3→4，農機a3田塊作業順序為6→8→7，動態任務分配結果表明，基于改進合同網算法比基于傳統合同網算法的動態任務分配農機機與服務器通信次數較少85%，機群多機協同時間代價降低4.41%～6.67%。

{T1～T12}為原任務{T13～T15}為新增任務時，動態任務分配前的任務分配結果為農機a1田塊作業順序為1→3 →11→9→12，農機a2田塊作業順序為7→8→6→5，農機a3田塊作業順序為4→10→2，動態任務分配結果表明，基于改進合同網算法比基于傳統合同網算法的動態任務分配農機機與服務器通信次數較少80%，機群多機協同時間代價降低0.83%～5.58%。

由任務分配結果可知，在不同時刻執行新增任務的動態任務分配，基于改進合同網算法的結果都優于基于傳統合同網算法的結果，在新增任務試驗情況下農機與服務器的通信次數降低80%～85%，機群時間代價降低0.83%～8.05%，均有較明顯降低。試驗結果表明，在新增任務情況下，基于改進合同網算法的動態任務分配方法性能更加優秀。

4.2 有農機出現故障情況的動態任務分配試驗

播種作業過程中，故障農機所在作業行及作業行中間的未作業行由故障農機修復后完成作業；收獲類作業將未作業區域全部規劃進行作業。以收獲作業為例假設作業開始前將任務T1～T15分配給農機a1～a4，任務分結果為：農機a1的田塊作業順序為15→5→1→3；農機a2的田塊作業順序為13→12→8→14；農機a3的田塊作業順序為2→4→6→7；農機a4的田塊作業順序為9→10→11；機群作業時間代價為10.26 h。分別假設開始作業1、3、5 h后農機a3發生故障，對農機a3未完成的任務進行動態任務分配，任務分配結果如表4所示，基于改進合同網算法比基于傳統合同網算法的動態任務分配農機與服務器通信次數較少77.4%，機群多機協同時間代價降低1.77%～12.89%。

表4 有農機故障情況下動態任務分配結果 Table 4 Dynamic task allocation results in the case of agricultural machinery failure

由任務分配結果可知，在有農機出現故障的情況下基于改進合同網算法的動態任務分配結果比基于傳統合同網算法的動態任務分配結果機群時間代價平均降低5.86%，最高降低12.89%，農機與服務器間的通信次數降低77.4%，均有較明顯降低。試驗結果表明，在有農機出現故障情況下，基于改進合同網算法的動態任務分配方法性能更加優秀。

仿真結果表明，傳統合同網算法和改進合同網算法都可以用來處理動態任務分配問題。其中，使用改進合同網算法可以得到更好的任務分配效果并且減少農機與服務器間的通信次數，同時，在使用改進合同網算法的任務分配過程中，服務器只執行簡單的通信而不參與任務分配的計算，將全部計算和部分通信放在農機終端計算機，充分利用了農機終端計算機的計算能力，大大減輕了服務器負擔，因此，基于改進合同網算法的動態任務分配方法具有明顯優勢。

5 實際播種作業試驗

為驗證本文基于改進合同網算法的動態任務分配方法在實際作業場景中的有效性，進行實際播種作業試驗。圖9為內蒙古興安農墾吐列毛杜農場一區某日播種作業情況，3臺播種機共完成11個田塊任務。根據中國農機院農機合作社管理云服務平臺得到播種機性能參數和任務參數，3臺播種機所用拖拉機型號分別為約2臺翰迪爾2204拖拉機和1臺約翰迪爾1854拖拉機，主要性能參數如表5所示，11個任務參數如表6所示。

3臺播種機執行任務的實際作業田塊順序分別為1→2→8 →9→10→11、6→7和3→4→5，如圖10所示，其中亮色區域為相應播種機該日作業田塊。3臺播種機的理論作業時間分別為14.14 、5.78 和6.50 h。播種機1率先完成任務1和任務2回到車庫后接到新增任務8、9、10和11，造成任務分配不均衡播種機1作業時間過大，導致機群作業代價增加。

假設3臺播種機同時出發作業，當作業時間分為2、4、6 h時進行基于改進合同網算法的動態任務分配試驗，結果如表7所示。當作業時間分別為2、4、6 h時，經過基于改進合同網算法的多機協同動態任務分配機群時間代價比實際作業理論機群時間代價降低30.20～34.09%。

表7 不同時間下試驗結果 Table 7 Experiment results at different times

由試驗結果可知，在不同時間執行動態任務分配均可得到較優的任務分配結果，任務分配后機群代價比實際作業理論機群代價降低30%以上。因此，基于改進合同網的動態任務分配方法可以較好的解決實際作業情況下有突發情況的動態任務分配問題。

6 結 論

1）本文對同種作業農機機群動態任務分配問題進行了研究，以機群中用時最長農機的作業時間、機群的油耗和機群的路程為代價建立代價函數和目標函數。

2）提出了基于合同網算法的動態任務分配方法和改進合同網算法的4種方法，包括基于直線距離和最短的招標者選擇方法、基于招標者作業能力的閾值設定方法、基于最小面積的任務再招標方法和基于路程最大的任務交換方法。

3）選擇適當田塊作為任務田塊，分別對有新任務增加的情況和農機出現故障的情況進行了基于合同網算法和基于改進合同網算法的動態任務分配仿真試驗，仿真結果表明基于改進合同網算法的動態任務分配結果比基于傳統合同網的動態任務分配結果農機與服務器通信次數減少77.4%～85.0%，機群時間代價均降低0.83%～12.89%。

4）進行實際播種新增任務情況下動態任務分配試驗，由試驗結果可知，在不同的時間執行基于改進合同網算法新增任務的動態任務分配，任務分配后機群時間代價比真實機群理論時間代價降低30.20%～34.09%。試驗結果表明，基于改進合同網的農機機群動態任務分配方法可以解決機群作業過程中有突發情況且無嚴格作業時間窗口的動態任務分配問題。