基于農田環境的農業機器人群協同作業策略

宮金良，王 偉，張彥斐，蘭玉彬

（1. 山東理工大學機械工程學院，淄博 255049；2. 山東理工大學農業工程與食品科學學院，淄博 255049）

0 引言

隨著第四次產業革命的到來，農村人口老齡化、人力短缺等問題日趨嚴峻[1]，這為大型無人農場的出現提供了可能[2]。無人農場具有精準化種植、智能決策和智能化操控的特點，是未來農業發展的主流方向[3]。在無人農場的大田作業中，隨著農業機器人的作業任務日益復雜化，單機器人作業越發不能滿足無人農場中的工作需求，農業機器人群協同作業具有極大應用前景。

機器人群協同作業需解決任務分配與全區域覆蓋2個基本問題，即農場主控系統在接收到某一任務要求時通過任務分配方案決定哪些機器人參加工作以及確定各參加工作機器人的工作量，并根據機器人群全區域覆蓋方案分配各機器人工作區域與規劃各機器人工作路徑。

為合理分配各機器人的工作區域、提高機器人群的工作效率[4]，近些年已有機器人群全區域覆蓋的相關研究。Maxim等[5]利用機器人之間相互排斥的策略使其均勻散布在作業區域中，從而達到對目標工作區域的覆蓋。Viet等[6]通過梨耕式移動與A*算法相結合解決多機器人在線全覆蓋任務，機器人依次梨耕式移動覆蓋空閑區域。以上2種方案能夠保證多目標區域的全覆蓋，但是機器人群遍歷時會產生較多重復路徑。郝宗波等[7]提出基于柵格地圖的內螺旋算法（Internal Spiral Coverage，ISC），利用邊界探索獲得環境邊界之后進行路徑規劃。Agmon等[8]提出基于構造生成樹的方式為每個機器人規劃好覆蓋路徑，這些路徑聯合構成整個覆蓋地形。Rekleitis等[9]將目標二維區域分解成單元區域，通過對每個區域簡單地前后移動完成多機器人的全區域覆蓋。Acar等[10]通過構造不同的Morse方程尋求最合理的區域分解方式，以適合機器人覆蓋不同形狀的環境。上述4種方案在優化機器人群遍歷面積重復率的基礎上完成了機器人群對工作區域的全覆蓋，但并未考慮機器人性能參數的差異分配各機器人工作量與工作區域。

本文在考慮農業機器人異質性的基礎上，以機器人群整體效能為優化目標解決機器人群的任務分配問題。在任務分配的基礎上以機器人群總遍歷面積重復率為優化目標，通過改進的遺傳算法與深度優先搜索算法解決農田復雜環境下異質機器人群的全區域覆蓋問題。

1 機器人作業任務分配

隨著農業機器人的更新換代和工作損耗的累積，無人農場中的農業機器人在歷史任務量、能耗、故障率、服務質量、工作效率等方面可能存在差異，本文將以上性能參數不一致的農業機器人定義為異質農業機器人，反之為同質機器人。本文通過定義機器人團隊整體效能的概念，綜合考慮以上性能因素選擇農場中的同質與異質機器人參加工作并為其分配工作量。

根據任務分配的收益（reward）與成本（cost）相減得到任務分配的效能U，其中機器人i的服務質量isq代表收益，歷史工作量ih、能耗ic與故障率if代表成本，則機器人i的效能iU為

以上4種性能參數的取值范圍差異較大，數值較小的性能參數對機器人效能值的影響會被弱化。為方便調節計算機器人效能時4種性能參數的權重，在計算機器人i的收益或成本時引入全體機器人的對應參數數據，將各參數所代表的收益或成本控制在0～1之內，設無人農場的總機器人數量為ψ，效能計算公式為

式中 1w，2w，3w，4w分別為各性能參數的權重因子，其大小由農場管理者根據機器人的實際狀況設定，w1+w2+w3+w4=1。

根據公式（2）確定各機器人的效能值之后確定參加工作的機器人和各機器人工作量，具體步驟為：對各機器人的效能值進行降序排序，依次選擇機器人進入機器人工作團隊，并根據機器人i的工作效率ie與工作時限要求H計算機器人i的理論工作量Wi（Wi=ei·H），直至機器人團隊工作量WN不小于工作量需求值Wd。機器人i的實際工作量由其理論工作量按比例分配：

2 基于柵格法的環境建模與矩形分區

常規機器人群全區域覆蓋方案通常基于具有部分障礙物且形狀規則的單片工作區域確定，但不適于機器人群在復雜農田環境的遍歷，本文以山東理工大學蘭玉彬院士團隊與淄博禾豐種業公司合作共建的數字生態循環農業農場[11]為基礎，重新設置農田中的工作環境。數字生態循環農業農場中存在離散分布且工作區域不規則的數片農田，田間道路縱橫交錯，農田中存在一些分散障礙物如風力發電機、電線桿、固定安裝的傳感器等[12]，如圖1所示。

為簡化復雜的農田工作環境以便于規劃機器人工作區域與遍歷路徑，本文將田間道路自然分割的單片農田作為一級分區，通過柵格法對單片農田建模并對不規則障礙物進行膨脹處理，在此基礎上劃分單片農田內的二級分區并設置分區合并規則。

2.1 柵格化建模與障礙物膨脹處理

定義一個形狀不規則且障礙物隨機分布的單片農田，通過柵格法對農田建模時將機器人群共同的工作范圍設置成柵格圖中單元格的單位長度，柵格建模結果如圖2a所示，空白單元格表示機器人可自由遍歷的工作區域。對于障礙物邊緣線與柵格邊緣線不重合的情況，用二值形態學中的膨脹運算對不規則障礙物進行膨脹處理[13]。膨脹結果如圖2b所示。

2.2 柵格分區與分區合并

根據膨脹處理后的障礙物形狀及位置劃分空閑矩形區域，如圖3a所示。柵格分區步驟如下：

1）尋找橫坐標或縱坐標相同的障礙物邊界，并沿此邊界畫一條連接2個障礙物的分區線；

2）對于矩形或正方形障礙物，過障礙物左上角頂點畫一條縱向直線，遇到其他障礙物或步驟1）形成的分區線即停止；過障礙物右下角頂點畫一條橫向直線，遇到其他障礙物或步驟1）形成的分區線即停止；

3）對于非矩形或正方形障礙物如障礙物D，按矩形障礙物數量最小化原則設置縱向虛擬分割線，將不規則障礙物分割成多個矩形，再轉至步驟2）。

在柵格矩形分區之后進行分區合并，以盡量減少分區的數量。一個柵格分區與其鄰近分區共同邊長度相等則可以進行合并[14]，如圖3a中的分區1、2、3可以合并為圖3b中的分區4。分區時先合并可縱向合并的分區，再合并可橫向合并的分區。

為保證對農田的全區域覆蓋，在分區合并的環境地圖基礎上還原各障礙物的形狀，將障礙物邊緣線、膨脹后的障礙物邊緣線以及分區線包圍形成的封閉圖形的空白區域按照“上-下-左-右”的順序合并至鄰近空白分區，找不到空白分區的不規則空白區域則設置為單獨分區，障礙物還原后的分區效果圖如圖4所示。

3 基于改進遺傳算法的分區遍歷

在工作區域涉及多片農田時，農場中既存在一級分區（單片農田）又存在二級分區。本文在確定各一級分區遍歷順序之后再確定各一級分區內二級分區的遍歷順序，通過深度優先搜索算法（Depth First Search，DFS）根據確定好的遍歷順序在一級分區以及二級分區內遍歷，同時根據機器人的工作量為其分配工作區域，實現工作區域的全覆蓋。

3.1 基于遺傳算法的分區遍歷

優化DFS算法在一級分區與二級分區間的遍歷順序可以增加DFS算法規劃的機器人工作區域的連續性進而減少機器人在環境地圖中遍歷的重復率。尋找DFS算法在分區間的最優遍歷順序首先需要通過構造對偶圖的方式[15]確定形狀規則或不規則的一級分區與二級分區的重心坐標，進而通過遺傳算法尋找一條遍歷所有分區重心且每個分區重心僅遍歷1次的最短路徑[16-18]，此最短路徑中包含的分區重心遍歷順序即為DFS算法在分區間的最優遍歷順序。

本文通過交叉操作與交叉變異概率2方面改進遺傳算法，旨在提高傳統遺傳算法跳出局部最優解的能力，減少迭代次數，提高遺傳算法求解分區間遍歷順序的工作效率。

3.2 改進的交叉操作

遺傳算法中的染色體采用整數編碼，由各分區編號排列組成[19-21]，染色體適用度值與該染色體對應的遍歷各分區重心的路徑長度成反比[22-24]。傳統遺傳算法的交叉操作中兩兩染色體交叉產生2個新染色體的方式具有隨機性[25]，雖然增加了種群多樣性，但是算法收斂性差[26]。本文將混合粒子群算法的交叉操作應用于傳統遺傳算法的交叉操作中，通過染色體與迭代過程中出現的實時最優適應度值染色體交叉，在保證群體多樣性的基礎之上提高收斂速度。改進的遺傳算法交叉操作如圖5所示。

最優染色體與原染色體的交叉方式與傳統遺傳算法交叉操作兩兩染色體交叉的方式相同[27]。檢測經過交叉操作的新染色體，若其適應度值高于原染色體則接受此新染色體，否則視此次交叉操作無效，保留原染色體。

3.3 自適應交叉變異概率

對于高適應度染色體，應設置較低的交叉概率 cp與變異概率 mp值以免破壞其染色體的優質基因結構[28]，對于低適應度染色體，則應該提高 cp與 mp值以將其淘汰并且生成新染色體[29]；在種群多樣性較低時，應該適當提高低適應度染色體的交叉與變異概率以免算法陷入局部最優解。所以 cp與 mp的取值應根據染色體適應度值的高低與不同的種群多樣性階段自適應變化[30]。

本文根據種群實時最優適應度值maxf與種群實時平均適應度值avgf的關系定義當前種群多樣性Fβ：

當 avgf逐漸向 maxf靠攏時，表明種群逐漸進化，各染色體向最優解靠攏，此時Fβ減小。

1）自適應交叉概率

根據f(t)與 maxf的關系，將不同染色體分為3等，自適應交叉概率調節機制如下：

式中 ctp為染色體t發生交叉的概率，最大交叉概率 cmaxp與不同時期種群多樣性的大小有關。

2）自適應變異概率

變異概率一般在0.001～0.01之間[31]。自適應變異概率與自適應交叉概率的設置方式類似：

式中 mtp為染色體t發生變異的概率。

4 基于DFS算法的分區內遍歷規則

DFS算法用來尋找從出發點至目標點的可行路徑。算法通過依次訪問與上一節點相鄰的可行節點訪問完圖中所有與出發點有路徑相通的節點[32]。

4.1 DFS算法在二級分區內的遍歷順序

設（m,n）為分區中的單元格，未被DFS算法遍歷的單元格標記為“0”，已遍歷的標記為“1”。

為保證機器人工作區域的連續性和減少機器人的轉彎次數，建立P、Q兩種分區遍歷順序矩陣：

DFS算法在分區內搜索下一步要遍歷的單元格的過程如下：

式中下標q∈ { 1，2，3，4}，O1q表示矩陣O第1行第q列的元素，2qO表示矩陣O第2行第q列的元素。如果搜索到的新單元標記為“0”且在該分區范圍內則以該單元格為新起點繼續深度搜索并將q初始化為1且將該單元格標記為“1”，否則q從1開始依次加1搜索周圍單元格。算法遍歷至死角時則依次回溯已走過的單元格，同時根據公式（9）～（13）尋找新起點。

4.2 機器人工作區域與分區內DFS算法遍歷起點與終點的確定

DFS算法搜索機器人作業路徑的同時根據蒙特卡洛方法[33]計算當前單元格面積并計算已為機器人遍歷的實時總面積，在滿足機器人的工作區域要求之后記錄算法走過的路徑，繼續深度搜索下一個工作區域。

DFS算法遍歷完一個分區之后，根據改進的遺傳算法規定的最優分區遍歷順序，DFS算法跳轉至下一個分區的起點繼續遍歷。為保證機器人工作區域的連續性，選擇下一個分區中最靠近上一個分區終點的單元格作為下一個分區的起點。

4.3 路徑規劃

通過DFS算法為機器人規劃的工作區域可能涉及多個二級分區。機器人工作區域縱向跨度大于橫向跨度的稱為縱向區域，反之為橫向區域。

機器人在縱向區域（橫向區域）內從其工作區域最左端的最下方單元格開始遍歷，在進入一列（一行）單元格遍歷時檢測進入該列（行）單元格的入口與該列（行）單元格兩端的距離，優先向距離短的一端遍歷，之后回溯遍歷該列（行）中未遍歷的部分，在未遍歷部分的每個單元格中均按照“左-縱向-右”（“下-橫向-上”）的順序搜索工作區域進行遍歷。當四周無可遍歷單元格時，按照機器人群遍歷面積重復率最低原則評估未遍歷區域中的新遍歷起點，并應用A*算法和八鄰域搜索法規劃遍歷到達新起點的路徑[34]。

5 算法仿真

為驗證改進遺傳算法的收斂能力與尋優能力，以及機器人群全區域覆蓋策略對機器人群總遍歷面積重復率優化效果，本文在設定多組試驗樣本的基礎上，分別通過MATLAB 2014軟件對改進遺傳算法與機器人群全區域覆蓋策略進行仿真分析。

5.1 基于路徑代價與收斂速度的不同算法仿真結果與分析

分別定義10、20、30個分區的中心點坐標，對比傳統遺傳算法、模擬退火算法與本文改進遺傳算法對不同分區數量規模計算得到的遍歷各分區重心的路徑長度、算法收斂時的迭代次數與耗時，結果如表1所示。其中傳統遺傳算法與改進遺傳算法的種群規模均設置為75，最大遺傳代數均設置為200；傳統遺傳算法的固定交叉與變異概率設置為0.9與0.01，改進遺傳算法的最小交叉概率與最小變異概率設置為0.7與0.006；模擬退火算法的初始溫度與終止溫度設置為1400與 1× 10-6，各溫度下的迭代次數（鏈長）設置為1100，降溫速率設置為0.9。

表1 不同算法對不同分區規模的路徑規劃結果 Table 1 Planning results of different algorithms for different partition sizes

由表1可知，在分區規模為10、20時，傳統遺傳算法與模擬退火算法均能得到與改進遺傳算法相近的路徑長度，但算法收斂時的迭代次數與耗時均是改進遺傳算法的數倍。在分區規模為30時，改進的遺傳算法所獲得的路徑長度分別比傳統遺傳算法與模擬退火算法減少2.8%與9.3%，收斂時的迭代次數分別減少69.5%與19.0%，耗時分別減少64.2%與9.9%。

圖6a與圖6b為3種算法在分區規模為30時的路徑長度隨迭代次數的變化曲線。從圖6a中可以看出，在迭代次數為50次之前，改進的遺傳算法的曲線斜率的絕對值大于傳統遺傳算法，說明改進的遺傳算法收斂速度更快。從圖6b中可以看出，模擬退火算法的實時最優路徑長度隨迭代次數的增加呈現階梯式的下降，且在算法收斂之前出現了5～6個較明顯的平臺期，說明模擬退火算法容易陷入局部最優。平臺期的出現容易導致算法得不到全局最優解，而改進遺傳算法無較明顯的平臺期，且在收斂速度與尋優能力方面均優于模擬退火算法。

5.2 路徑遍歷仿真結果與分析

本小節重在驗證復雜環境下機器人群工作區域分配以及路徑規劃方案，故暫不使用本文設計的任務分配方案分配各機器人工作量。仿真試驗中將圖4所示農田中376.75 m2的總工作量隨機分配至6個機器人，1～6號機器人的工作量分別為75.91 、36.80、52.97、66.77、51.30和93.00 m2。在此基礎上通過改進遺傳算法與DFS算法規劃各機器人工作區域繼而規劃各機器人的工作路徑，最后統計DFS算法對農田工作區域的覆蓋率與機器人群遍歷面積與農田面積的重復率。

DFS算法的遍歷路徑如圖7a所示，在圖7a確定的各機器人工作區域的基礎上，根據本文設置的路徑規劃方案進行各機器人路徑遍歷仿真，結果如圖7b所示。因DFS算法/機器人在柵格圖虛擬柵格中遍歷，故在仿真圖中DFS算法/機器人遍歷至一個柵格重心點即表示完成對該單元格的遍歷。

以算法規劃的遍歷工作區域面積與原任務要求的遍歷面積的比值定義面積覆蓋率。由圖7a可知，通過改進的遺傳算法與DFS算法相結合規劃的各機器人工作區域可以保證工作區域對農田的100%覆蓋。機器人的工作區域是否連續將影響該機器人的作業面積重復率，從圖7a中可以看出，除了3號機器人的工作區域出現2個分離的子區域外，其余機器人的工作區域均為連續。

定義機器人i的遍歷面積重復率is為

式中iS表示機器人i的實際遍歷面積。

設置另外4副與圖7形狀大小相同的環境地圖，分別在4副地圖中設置障礙物總面積與圖7中障礙物總面積相等但數量不等的3、5、9、11個障礙物，1～6號機器人組成的機器人團隊分別在4副環境地圖中遍歷，各機器人的工作量分別為75.91、36.80、52.97、66.77、51.30和93.00 m2。以地圖中障礙物在X軸與Y軸的標準差表征障礙物的離散度。不同障礙物數量下的分區數量以及機器人總遍歷面積重復率如表2所示。

由表2可知，障礙物數量的增多以及障礙物分布離散程度的增加使分區數量增加，機器人群總遍歷面積重復率也隨之增加。在11個障礙物時，分區數量達到21個，機器人群總面積重復率達到23.4%。

表2 不同障礙物數量下的機器人群遍歷面積重復率 Table 2 Repetition rate of the traversal area of the robot groups with different number of obstacles

在圖7障礙物數量、位置、形狀不變的基礎上，設置3種形狀不同的農田，其中第一種環境地圖僅有1個一級分區，后2種環境地圖分別由縱向與T形田間道路將農田分割成2個二級分區。各環境地圖的總工作面積均為376.75 m2，1～6號機器人組成的機器人團隊分別在3種環境地圖中遍歷，各機器人的工作量分別為：75.91、36.80、52.97、66.77、51.30與93.00 m2。機器人群的遍歷路徑如圖8所示。

由圖8可知，3種農田環境下通過DFS算法規劃的工作區域均可以實現對農田的100%覆蓋，機器人群進行全區域覆蓋的面積重復率分別為13.1%、11.9%和6.7%，說明本文設計的機器人群全區域覆蓋方案對多片工作區域、形狀多元化、多種異形障礙物分布的農田環境具有較好的適應性。

6 驗證試驗

為驗證本文任務分配方案下機器人群能否在規定的時限要求內完成目標任務量，以及機器人群全區域覆蓋策略在實際應用中對遍歷面積重復率的優化作用，以數字生態農業農場中的信息采集機器人為對象進行任務分配與全區域覆蓋遍歷試驗。試驗地點為山東理工大學圖書館南側草坪。通過數字生態農業農場云平臺人機交互界面將整體工作區域劃分為圖9由虛擬道路分割成的3個子區域，并在整體工作區域中設置8個異形障礙物。

實際農業生產過程中有關任務分配的4個性能參數權重因子根據農場管理者對各性能參數的偏好制定，本文試驗中設定4個性能參數權重因子均為0.25，根據農場中各機器人的歷史工作記錄統計各機器人的工作效率（hm2/h）、服務質量（取值范圍：0～100）、能耗（W）、故障率（取值范圍：0～1）以及歷史工作量（hm2）等參數數據，總工作量需求值設置為1 hm2，任務時限要求為25 min。信息采集機器人搭載RMONCAM HD600紅外攝像頭進行農情勘測遍歷試驗，各機器人的攝像頭對地工作范圍均設置為1.5 m。

根據本文任務分配方案對農場中現有的10臺信息采集機器人進行任務分配，最終選擇7～10號機器人參加工作，根據公式（3）計算各機器人的實際工作量，如表 3所示。4臺機器人的工作效率分別為0.810、0.594、0.648和0.702 hm2/h。以整體工作區域的左下角為起點。實際遍歷面積表示機器人從進入草坪至駛出草坪全過程中遍歷的面積；覆蓋率為機器人在目標工作區域上的遍歷面積與目標工作區域面積的比值；遍歷面積重復率的定義與5.2 節一致；實際工作時間為機器人從起點至遍歷完其工作區域的時間。機器人群現場遍歷試驗如圖9所示。

通過各信息采集機器人實時回傳至云平臺的工作信息統計各機器人的實際遍歷面積、對原定工作區域的覆蓋率、機器人群總遍歷面積重復率以及完成遍歷任務的實際工作時間，結果如表3所示。

表3 各機器人工作數據統計 Table 3 Working data statistics of robots

由表3可知，4個試驗機器人對目標工作區域的覆蓋率均為100%，且能在規定的時限要求內完成分配的任務量，遍歷面積重復率分別為5.77%、4.14%、6.75%以及4.85%，說明本文設計的農業機器人群任務分配與全區域覆蓋方案能在保證機器人群任務完成度與優化機器人群遍歷面積重復率的基礎上，實現機器人的協同作業。

7 結論

1）本文在考慮遺傳算法不同種群多樣性階段與染色體適應度值差異的基礎上提出了自適應交叉變異概率，將混合粒子群算法與傳統遺傳算法相結合建立改進的遺傳算法交叉操作。仿真試驗表明，改進遺傳算法所獲得的遍歷各分區重心的路徑長度分別比傳統遺傳算法與模擬退火算法減少2.8%與9.3%，算法收斂時的迭代次數分別減少69.5%與19.0%，收斂到最優解的耗時分別減少64.2%與9.9%。

2）本文綜合考慮農業機器人的異質性差異設計機器人群任務分配方案；通過分區簡化工作環境，并分別通過改進遺傳算法與深度優先搜索算法解決分區間與分區內的遍歷順序問題并根據機器人工作量分配其工作區域；通過設計機器人在其工作區域內的路徑規劃方案實現機器人群對整體工作區域的全覆蓋。仿真試驗結果表明，在包含3、5、7、9和11個障礙物的不同環境地圖中，機器人群總遍歷面積重復率分別為6.3%、8.9%、16.7%、21.7%和23.4%；障礙物數量、形狀、位置相同而農田形狀不同的環境地圖中，機器人群總遍歷面積重復率分別為16.7%、13.1%、11.9%與6.7%。

實際農業生產過程中，各機器人的性能參數不可能完全一致，同質機器人只在理論上存在。對于同質機器人群系統、異質與同質并存的機器人系統的協同作業策略，依然可以使用本文設計的任務分配方案根據各機器人性能參數與工作效率等選擇機器人參加工作并計算各機器人工作量，確定任務分配結果后根據本文設計的全區域覆蓋方案確定各機器人工作區域和路徑規劃。