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

（1. 山東理工大學(xué)機(jī)械工程學(xué)院，淄博 255049；2. 山東理工大學(xué)農(nóng)業(yè)工程與食品科學(xué)學(xué)院，淄博 255049）

0 引言

隨著第四次產(chǎn)業(yè)革命的到來(lái)，農(nóng)村人口老齡化、人力短缺等問(wèn)題日趨嚴(yán)峻[1]，這為大型無(wú)人農(nóng)場(chǎng)的出現(xiàn)提供了可能[2]。無(wú)人農(nóng)場(chǎng)具有精準(zhǔn)化種植、智能決策和智能化操控的特點(diǎn)，是未來(lái)農(nóng)業(yè)發(fā)展的主流方向[3]。在無(wú)人農(nóng)場(chǎng)的大田作業(yè)中，隨著農(nóng)業(yè)機(jī)器人的作業(yè)任務(wù)日益復(fù)雜化，單機(jī)器人作業(yè)越發(fā)不能滿足無(wú)人農(nóng)場(chǎng)中的工作需求，農(nóng)業(yè)機(jī)器人群協(xié)同作業(yè)具有極大應(yīng)用前景。

機(jī)器人群協(xié)同作業(yè)需解決任務(wù)分配與全區(qū)域覆蓋2個(gè)基本問(wèn)題，即農(nóng)場(chǎng)主控系統(tǒng)在接收到某一任務(wù)要求時(shí)通過(guò)任務(wù)分配方案決定哪些機(jī)器人參加工作以及確定各參加工作機(jī)器人的工作量，并根據(jù)機(jī)器人群全區(qū)域覆蓋方案分配各機(jī)器人工作區(qū)域與規(guī)劃各機(jī)器人工作路徑。

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

本文在考慮農(nóng)業(yè)機(jī)器人異質(zhì)性的基礎(chǔ)上，以機(jī)器人群整體效能為優(yōu)化目標(biāo)解決機(jī)器人群的任務(wù)分配問(wèn)題。在任務(wù)分配的基礎(chǔ)上以機(jī)器人群總遍歷面積重復(fù)率為優(yōu)化目標(biāo)，通過(guò)改進(jìn)的遺傳算法與深度優(yōu)先搜索算法解決農(nóng)田復(fù)雜環(huán)境下異質(zhì)機(jī)器人群的全區(qū)域覆蓋問(wèn)題。

1 機(jī)器人作業(yè)任務(wù)分配

隨著農(nóng)業(yè)機(jī)器人的更新?lián)Q代和工作損耗的累積，無(wú)人農(nóng)場(chǎng)中的農(nóng)業(yè)機(jī)器人在歷史任務(wù)量、能耗、故障率、服務(wù)質(zhì)量、工作效率等方面可能存在差異，本文將以上性能參數(shù)不一致的農(nóng)業(yè)機(jī)器人定義為異質(zhì)農(nóng)業(yè)機(jī)器人，反之為同質(zhì)機(jī)器人。本文通過(guò)定義機(jī)器人團(tuán)隊(duì)整體效能的概念，綜合考慮以上性能因素選擇農(nóng)場(chǎng)中的同質(zhì)與異質(zhì)機(jī)器人參加工作并為其分配工作量。

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

以上4種性能參數(shù)的取值范圍差異較大，數(shù)值較小的性能參數(shù)對(duì)機(jī)器人效能值的影響會(huì)被弱化。為方便調(diào)節(jié)計(jì)算機(jī)器人效能時(shí)4種性能參數(shù)的權(quán)重，在計(jì)算機(jī)器人i的收益或成本時(shí)引入全體機(jī)器人的對(duì)應(yīng)參數(shù)數(shù)據(jù)，將各參數(shù)所代表的收益或成本控制在0～1之內(nèi)，設(shè)無(wú)人農(nóng)場(chǎng)的總機(jī)器人數(shù)量為ψ，效能計(jì)算公式為

式中 1w，2w，3w，4w分別為各性能參數(shù)的權(quán)重因子，其大小由農(nóng)場(chǎng)管理者根據(jù)機(jī)器人的實(shí)際狀況設(shè)定，w1+w2+w3+w4=1。

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

2 基于柵格法的環(huán)境建模與矩形分區(qū)

常規(guī)機(jī)器人群全區(qū)域覆蓋方案通?；诰哂胁糠终系K物且形狀規(guī)則的單片工作區(qū)域確定，但不適于機(jī)器人群在復(fù)雜農(nóng)田環(huán)境的遍歷，本文以山東理工大學(xué)蘭玉彬院士團(tuán)隊(duì)與淄博禾豐種業(yè)公司合作共建的數(shù)字生態(tài)循環(huán)農(nóng)業(yè)農(nóng)場(chǎng)[11]為基礎(chǔ)，重新設(shè)置農(nóng)田中的工作環(huán)境。數(shù)字生態(tài)循環(huán)農(nóng)業(yè)農(nóng)場(chǎng)中存在離散分布且工作區(qū)域不規(guī)則的數(shù)片農(nóng)田，田間道路縱橫交錯(cuò)，農(nóng)田中存在一些分散障礙物如風(fēng)力發(fā)電機(jī)、電線桿、固定安裝的傳感器等[12]，如圖1所示。

為簡(jiǎn)化復(fù)雜的農(nóng)田工作環(huán)境以便于規(guī)劃?rùn)C(jī)器人工作區(qū)域與遍歷路徑，本文將田間道路自然分割的單片農(nóng)田作為一級(jí)分區(qū)，通過(guò)柵格法對(duì)單片農(nóng)田建模并對(duì)不規(guī)則障礙物進(jìn)行膨脹處理，在此基礎(chǔ)上劃分單片農(nóng)田內(nèi)的二級(jí)分區(qū)并設(shè)置分區(qū)合并規(guī)則。

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

定義一個(gè)形狀不規(guī)則且障礙物隨機(jī)分布的單片農(nóng)田，通過(guò)柵格法對(duì)農(nóng)田建模時(shí)將機(jī)器人群共同的工作范圍設(shè)置成柵格圖中單元格的單位長(zhǎng)度，柵格建模結(jié)果如圖2a所示，空白單元格表示機(jī)器人可自由遍歷的工作區(qū)域。對(duì)于障礙物邊緣線與柵格邊緣線不重合的情況，用二值形態(tài)學(xué)中的膨脹運(yùn)算對(duì)不規(guī)則障礙物進(jìn)行膨脹處理[13]。膨脹結(jié)果如圖2b所示。

2.2 柵格分區(qū)與分區(qū)合并

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

1）尋找橫坐標(biāo)或縱坐標(biāo)相同的障礙物邊界，并沿此邊界畫(huà)一條連接2個(gè)障礙物的分區(qū)線；

2）對(duì)于矩形或正方形障礙物，過(guò)障礙物左上角頂點(diǎn)畫(huà)一條縱向直線，遇到其他障礙物或步驟1）形成的分區(qū)線即停止；過(guò)障礙物右下角頂點(diǎn)畫(huà)一條橫向直線，遇到其他障礙物或步驟1）形成的分區(qū)線即停止；

3）對(duì)于非矩形或正方形障礙物如障礙物D，按矩形障礙物數(shù)量最小化原則設(shè)置縱向虛擬分割線，將不規(guī)則障礙物分割成多個(gè)矩形，再轉(zhuǎn)至步驟2）。

在柵格矩形分區(qū)之后進(jìn)行分區(qū)合并，以盡量減少分區(qū)的數(shù)量。一個(gè)柵格分區(qū)與其鄰近分區(qū)共同邊長(zhǎng)度相等則可以進(jìn)行合并[14]，如圖3a中的分區(qū)1、2、3可以合并為圖3b中的分區(qū)4。分區(qū)時(shí)先合并可縱向合并的分區(qū)，再合并可橫向合并的分區(qū)。

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

3 基于改進(jìn)遺傳算法的分區(qū)遍歷

在工作區(qū)域涉及多片農(nóng)田時(shí)，農(nóng)場(chǎng)中既存在一級(jí)分區(qū)（單片農(nóng)田）又存在二級(jí)分區(qū)。本文在確定各一級(jí)分區(qū)遍歷順序之后再確定各一級(jí)分區(qū)內(nèi)二級(jí)分區(qū)的遍歷順序，通過(guò)深度優(yōu)先搜索算法（Depth First Search，DFS）根據(jù)確定好的遍歷順序在一級(jí)分區(qū)以及二級(jí)分區(qū)內(nèi)遍歷，同時(shí)根據(jù)機(jī)器人的工作量為其分配工作區(qū)域，實(shí)現(xiàn)工作區(qū)域的全覆蓋。

3.1 基于遺傳算法的分區(qū)遍歷

優(yōu)化DFS算法在一級(jí)分區(qū)與二級(jí)分區(qū)間的遍歷順序可以增加DFS算法規(guī)劃的機(jī)器人工作區(qū)域的連續(xù)性進(jìn)而減少機(jī)器人在環(huán)境地圖中遍歷的重復(fù)率。尋找DFS算法在分區(qū)間的最優(yōu)遍歷順序首先需要通過(guò)構(gòu)造對(duì)偶圖的方式[15]確定形狀規(guī)則或不規(guī)則的一級(jí)分區(qū)與二級(jí)分區(qū)的重心坐標(biāo)，進(jìn)而通過(guò)遺傳算法尋找一條遍歷所有分區(qū)重心且每個(gè)分區(qū)重心僅遍歷1次的最短路徑[16-18]，此最短路徑中包含的分區(qū)重心遍歷順序即為DFS算法在分區(qū)間的最優(yōu)遍歷順序。

本文通過(guò)交叉操作與交叉變異概率2方面改進(jìn)遺傳算法，旨在提高傳統(tǒng)遺傳算法跳出局部最優(yōu)解的能力，減少迭代次數(shù)，提高遺傳算法求解分區(qū)間遍歷順序的工作效率。

3.2 改進(jìn)的交叉操作

遺傳算法中的染色體采用整數(shù)編碼，由各分區(qū)編號(hào)排列組成[19-21]，染色體適用度值與該染色體對(duì)應(yīng)的遍歷各分區(qū)重心的路徑長(zhǎng)度成反比[22-24]。傳統(tǒng)遺傳算法的交叉操作中兩兩染色體交叉產(chǎn)生2個(gè)新染色體的方式具有隨機(jī)性[25]，雖然增加了種群多樣性，但是算法收斂性差[26]。本文將混合粒子群算法的交叉操作應(yīng)用于傳統(tǒng)遺傳算法的交叉操作中，通過(guò)染色體與迭代過(guò)程中出現(xiàn)的實(shí)時(shí)最優(yōu)適應(yīng)度值染色體交叉，在保證群體多樣性的基礎(chǔ)之上提高收斂速度。改進(jìn)的遺傳算法交叉操作如圖5所示。

最優(yōu)染色體與原染色體的交叉方式與傳統(tǒng)遺傳算法交叉操作兩兩染色體交叉的方式相同[27]。檢測(cè)經(jīng)過(guò)交叉操作的新染色體，若其適應(yīng)度值高于原染色體則接受此新染色體，否則視此次交叉操作無(wú)效，保留原染色體。

3.3 自適應(yīng)交叉變異概率

對(duì)于高適應(yīng)度染色體，應(yīng)設(shè)置較低的交叉概率 cp與變異概率 mp值以免破壞其染色體的優(yōu)質(zhì)基因結(jié)構(gòu)[28]，對(duì)于低適應(yīng)度染色體，則應(yīng)該提高 cp與 mp值以將其淘汰并且生成新染色體[29]；在種群多樣性較低時(shí)，應(yīng)該適當(dāng)提高低適應(yīng)度染色體的交叉與變異概率以免算法陷入局部最優(yōu)解。所以 cp與 mp的取值應(yīng)根據(jù)染色體適應(yīng)度值的高低與不同的種群多樣性階段自適應(yīng)變化[30]。

本文根據(jù)種群實(shí)時(shí)最優(yōu)適應(yīng)度值maxf與種群實(shí)時(shí)平均適應(yīng)度值avgf的關(guān)系定義當(dāng)前種群多樣性Fβ：

當(dāng) avgf逐漸向 maxf靠攏時(shí)，表明種群逐漸進(jìn)化，各染色體向最優(yōu)解靠攏，此時(shí)Fβ減小。

1）自適應(yīng)交叉概率

根據(jù)f(t)與 maxf的關(guān)系，將不同染色體分為3等，自適應(yīng)交叉概率調(diào)節(jié)機(jī)制如下：

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

2）自適應(yīng)變異概率

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

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

4 基于DFS算法的分區(qū)內(nèi)遍歷規(guī)則

DFS算法用來(lái)尋找從出發(fā)點(diǎn)至目標(biāo)點(diǎn)的可行路徑。算法通過(guò)依次訪問(wèn)與上一節(jié)點(diǎn)相鄰的可行節(jié)點(diǎn)訪問(wèn)完圖中所有與出發(fā)點(diǎn)有路徑相通的節(jié)點(diǎn)[32]。

4.1 DFS算法在二級(jí)分區(qū)內(nèi)的遍歷順序

設(shè)（m,n）為分區(qū)中的單元格，未被DFS算法遍歷的單元格標(biāo)記為“0”，已遍歷的標(biāo)記為“1”。

為保證機(jī)器人工作區(qū)域的連續(xù)性和減少機(jī)器人的轉(zhuǎn)彎次數(shù)，建立P、Q兩種分區(qū)遍歷順序矩陣：

DFS算法在分區(qū)內(nèi)搜索下一步要遍歷的單元格的過(guò)程如下：

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

4.2 機(jī)器人工作區(qū)域與分區(qū)內(nèi)DFS算法遍歷起點(diǎn)與終點(diǎn)的確定

DFS算法搜索機(jī)器人作業(yè)路徑的同時(shí)根據(jù)蒙特卡洛方法[33]計(jì)算當(dāng)前單元格面積并計(jì)算已為機(jī)器人遍歷的實(shí)時(shí)總面積，在滿足機(jī)器人的工作區(qū)域要求之后記錄算法走過(guò)的路徑，繼續(xù)深度搜索下一個(gè)工作區(qū)域。

DFS算法遍歷完一個(gè)分區(qū)之后，根據(jù)改進(jìn)的遺傳算法規(guī)定的最優(yōu)分區(qū)遍歷順序，DFS算法跳轉(zhuǎn)至下一個(gè)分區(qū)的起點(diǎn)繼續(xù)遍歷。為保證機(jī)器人工作區(qū)域的連續(xù)性，選擇下一個(gè)分區(qū)中最靠近上一個(gè)分區(qū)終點(diǎn)的單元格作為下一個(gè)分區(qū)的起點(diǎn)。

4.3 路徑規(guī)劃

通過(guò)DFS算法為機(jī)器人規(guī)劃的工作區(qū)域可能涉及多個(gè)二級(jí)分區(qū)。機(jī)器人工作區(qū)域縱向跨度大于橫向跨度的稱為縱向區(qū)域，反之為橫向區(qū)域。

機(jī)器人在縱向區(qū)域（橫向區(qū)域）內(nèi)從其工作區(qū)域最左端的最下方單元格開(kāi)始遍歷，在進(jìn)入一列（一行）單元格遍歷時(shí)檢測(cè)進(jìn)入該列（行）單元格的入口與該列（行）單元格兩端的距離，優(yōu)先向距離短的一端遍歷，之后回溯遍歷該列（行）中未遍歷的部分，在未遍歷部分的每個(gè)單元格中均按照“左-縱向-右”（“下-橫向-上”）的順序搜索工作區(qū)域進(jìn)行遍歷。當(dāng)四周無(wú)可遍歷單元格時(shí)，按照機(jī)器人群遍歷面積重復(fù)率最低原則評(píng)估未遍歷區(qū)域中的新遍歷起點(diǎn)，并應(yīng)用A*算法和八鄰域搜索法規(guī)劃遍歷到達(dá)新起點(diǎn)的路徑[34]。

5 算法仿真

為驗(yàn)證改進(jìn)遺傳算法的收斂能力與尋優(yōu)能力，以及機(jī)器人群全區(qū)域覆蓋策略對(duì)機(jī)器人群總遍歷面積重復(fù)率優(yōu)化效果，本文在設(shè)定多組試驗(yàn)樣本的基礎(chǔ)上，分別通過(guò)MATLAB 2014軟件對(duì)改進(jìn)遺傳算法與機(jī)器人群全區(qū)域覆蓋策略進(jìn)行仿真分析。

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

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

表1 不同算法對(duì)不同分區(qū)規(guī)模的路徑規(guī)劃結(jié)果 Table 1 Planning results of different algorithms for different partition sizes

由表1可知，在分區(qū)規(guī)模為10、20時(shí)，傳統(tǒng)遺傳算法與模擬退火算法均能得到與改進(jìn)遺傳算法相近的路徑長(zhǎng)度，但算法收斂時(shí)的迭代次數(shù)與耗時(shí)均是改進(jìn)遺傳算法的數(shù)倍。在分區(qū)規(guī)模為30時(shí)，改進(jìn)的遺傳算法所獲得的路徑長(zhǎng)度分別比傳統(tǒng)遺傳算法與模擬退火算法減少2.8%與9.3%，收斂時(shí)的迭代次數(shù)分別減少69.5%與19.0%，耗時(shí)分別減少64.2%與9.9%。

圖6a與圖6b為3種算法在分區(qū)規(guī)模為30時(shí)的路徑長(zhǎng)度隨迭代次數(shù)的變化曲線。從圖6a中可以看出，在迭代次數(shù)為50次之前，改進(jìn)的遺傳算法的曲線斜率的絕對(duì)值大于傳統(tǒng)遺傳算法，說(shuō)明改進(jìn)的遺傳算法收斂速度更快。從圖6b中可以看出，模擬退火算法的實(shí)時(shí)最優(yōu)路徑長(zhǎng)度隨迭代次數(shù)的增加呈現(xiàn)階梯式的下降，且在算法收斂之前出現(xiàn)了5～6個(gè)較明顯的平臺(tái)期，說(shuō)明模擬退火算法容易陷入局部最優(yōu)。平臺(tái)期的出現(xiàn)容易導(dǎo)致算法得不到全局最優(yōu)解，而改進(jìn)遺傳算法無(wú)較明顯的平臺(tái)期，且在收斂速度與尋優(yōu)能力方面均優(yōu)于模擬退火算法。

5.2 路徑遍歷仿真結(jié)果與分析

本小節(jié)重在驗(yàn)證復(fù)雜環(huán)境下機(jī)器人群工作區(qū)域分配以及路徑規(guī)劃方案，故暫不使用本文設(shè)計(jì)的任務(wù)分配方案分配各機(jī)器人工作量。仿真試驗(yàn)中將圖4所示農(nóng)田中376.75 m2的總工作量隨機(jī)分配至6個(gè)機(jī)器人，1～6號(hào)機(jī)器人的工作量分別為75.91 、36.80、52.97、66.77、51.30和93.00 m2。在此基礎(chǔ)上通過(guò)改進(jìn)遺傳算法與DFS算法規(guī)劃各機(jī)器人工作區(qū)域繼而規(guī)劃各機(jī)器人的工作路徑，最后統(tǒng)計(jì)DFS算法對(duì)農(nóng)田工作區(qū)域的覆蓋率與機(jī)器人群遍歷面積與農(nóng)田面積的重復(fù)率。

DFS算法的遍歷路徑如圖7a所示，在圖7a確定的各機(jī)器人工作區(qū)域的基礎(chǔ)上，根據(jù)本文設(shè)置的路徑規(guī)劃方案進(jìn)行各機(jī)器人路徑遍歷仿真，結(jié)果如圖7b所示。因DFS算法/機(jī)器人在柵格圖虛擬柵格中遍歷，故在仿真圖中DFS算法/機(jī)器人遍歷至一個(gè)柵格重心點(diǎn)即表示完成對(duì)該單元格的遍歷。

以算法規(guī)劃的遍歷工作區(qū)域面積與原任務(wù)要求的遍歷面積的比值定義面積覆蓋率。由圖7a可知，通過(guò)改進(jìn)的遺傳算法與DFS算法相結(jié)合規(guī)劃的各機(jī)器人工作區(qū)域可以保證工作區(qū)域?qū)r(nóng)田的100%覆蓋。機(jī)器人的工作區(qū)域是否連續(xù)將影響該機(jī)器人的作業(yè)面積重復(fù)率，從圖7a中可以看出，除了3號(hào)機(jī)器人的工作區(qū)域出現(xiàn)2個(gè)分離的子區(qū)域外，其余機(jī)器人的工作區(qū)域均為連續(xù)。

定義機(jī)器人i的遍歷面積重復(fù)率is為

式中iS表示機(jī)器人i的實(shí)際遍歷面積。

設(shè)置另外4副與圖7形狀大小相同的環(huán)境地圖，分別在4副地圖中設(shè)置障礙物總面積與圖7中障礙物總面積相等但數(shù)量不等的3、5、9、11個(gè)障礙物，1～6號(hào)機(jī)器人組成的機(jī)器人團(tuán)隊(duì)分別在4副環(huán)境地圖中遍歷，各機(jī)器人的工作量分別為75.91、36.80、52.97、66.77、51.30和93.00 m2。以地圖中障礙物在X軸與Y軸的標(biāo)準(zhǔn)差表征障礙物的離散度。不同障礙物數(shù)量下的分區(qū)數(shù)量以及機(jī)器人總遍歷面積重復(fù)率如表2所示。

由表2可知，障礙物數(shù)量的增多以及障礙物分布離散程度的增加使分區(qū)數(shù)量增加，機(jī)器人群總遍歷面積重復(fù)率也隨之增加。在11個(gè)障礙物時(shí)，分區(qū)數(shù)量達(dá)到21個(gè)，機(jī)器人群總面積重復(fù)率達(dá)到23.4%。

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

在圖7障礙物數(shù)量、位置、形狀不變的基礎(chǔ)上，設(shè)置3種形狀不同的農(nóng)田，其中第一種環(huán)境地圖僅有1個(gè)一級(jí)分區(qū)，后2種環(huán)境地圖分別由縱向與T形田間道路將農(nóng)田分割成2個(gè)二級(jí)分區(qū)。各環(huán)境地圖的總工作面積均為376.75 m2，1～6號(hào)機(jī)器人組成的機(jī)器人團(tuán)隊(duì)分別在3種環(huán)境地圖中遍歷，各機(jī)器人的工作量分別為：75.91、36.80、52.97、66.77、51.30與93.00 m2。機(jī)器人群的遍歷路徑如圖8所示。

由圖8可知，3種農(nóng)田環(huán)境下通過(guò)DFS算法規(guī)劃的工作區(qū)域均可以實(shí)現(xiàn)對(duì)農(nóng)田的100%覆蓋，機(jī)器人群進(jìn)行全區(qū)域覆蓋的面積重復(fù)率分別為13.1%、11.9%和6.7%，說(shuō)明本文設(shè)計(jì)的機(jī)器人群全區(qū)域覆蓋方案對(duì)多片工作區(qū)域、形狀多元化、多種異形障礙物分布的農(nóng)田環(huán)境具有較好的適應(yīng)性。

6 驗(yàn)證試驗(yàn)

為驗(yàn)證本文任務(wù)分配方案下機(jī)器人群能否在規(guī)定的時(shí)限要求內(nèi)完成目標(biāo)任務(wù)量，以及機(jī)器人群全區(qū)域覆蓋策略在實(shí)際應(yīng)用中對(duì)遍歷面積重復(fù)率的優(yōu)化作用，以數(shù)字生態(tài)農(nóng)業(yè)農(nóng)場(chǎng)中的信息采集機(jī)器人為對(duì)象進(jìn)行任務(wù)分配與全區(qū)域覆蓋遍歷試驗(yàn)。試驗(yàn)地點(diǎn)為山東理工大學(xué)圖書(shū)館南側(cè)草坪。通過(guò)數(shù)字生態(tài)農(nóng)業(yè)農(nóng)場(chǎng)云平臺(tái)人機(jī)交互界面將整體工作區(qū)域劃分為圖9由虛擬道路分割成的3個(gè)子區(qū)域，并在整體工作區(qū)域中設(shè)置8個(gè)異形障礙物。

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

根據(jù)本文任務(wù)分配方案對(duì)農(nóng)場(chǎng)中現(xiàn)有的10臺(tái)信息采集機(jī)器人進(jìn)行任務(wù)分配，最終選擇7～10號(hào)機(jī)器人參加工作，根據(jù)公式（3）計(jì)算各機(jī)器人的實(shí)際工作量，如表 3所示。4臺(tái)機(jī)器人的工作效率分別為0.810、0.594、0.648和0.702 hm2/h。以整體工作區(qū)域的左下角為起點(diǎn)。實(shí)際遍歷面積表示機(jī)器人從進(jìn)入草坪至駛出草坪全過(guò)程中遍歷的面積；覆蓋率為機(jī)器人在目標(biāo)工作區(qū)域上的遍歷面積與目標(biāo)工作區(qū)域面積的比值；遍歷面積重復(fù)率的定義與5.2 節(jié)一致；實(shí)際工作時(shí)間為機(jī)器人從起點(diǎn)至遍歷完其工作區(qū)域的時(shí)間。機(jī)器人群現(xiàn)場(chǎng)遍歷試驗(yàn)如圖9所示。

通過(guò)各信息采集機(jī)器人實(shí)時(shí)回傳至云平臺(tái)的工作信息統(tǒng)計(jì)各機(jī)器人的實(shí)際遍歷面積、對(duì)原定工作區(qū)域的覆蓋率、機(jī)器人群總遍歷面積重復(fù)率以及完成遍歷任務(wù)的實(shí)際工作時(shí)間，結(jié)果如表3所示。

表3 各機(jī)器人工作數(shù)據(jù)統(tǒng)計(jì) Table 3 Working data statistics of robots

由表3可知，4個(gè)試驗(yàn)機(jī)器人對(duì)目標(biāo)工作區(qū)域的覆蓋率均為100%，且能在規(guī)定的時(shí)限要求內(nèi)完成分配的任務(wù)量，遍歷面積重復(fù)率分別為5.77%、4.14%、6.75%以及4.85%，說(shuō)明本文設(shè)計(jì)的農(nóng)業(yè)機(jī)器人群任務(wù)分配與全區(qū)域覆蓋方案能在保證機(jī)器人群任務(wù)完成度與優(yōu)化機(jī)器人群遍歷面積重復(fù)率的基礎(chǔ)上，實(shí)現(xiàn)機(jī)器人的協(xié)同作業(yè)。

7 結(jié)論

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

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

實(shí)際農(nóng)業(yè)生產(chǎn)過(guò)程中，各機(jī)器人的性能參數(shù)不可能完全一致，同質(zhì)機(jī)器人只在理論上存在。對(duì)于同質(zhì)機(jī)器人群系統(tǒng)、異質(zhì)與同質(zhì)并存的機(jī)器人系統(tǒng)的協(xié)同作業(yè)策略，依然可以使用本文設(shè)計(jì)的任務(wù)分配方案根據(jù)各機(jī)器人性能參數(shù)與工作效率等選擇機(jī)器人參加工作并計(jì)算各機(jī)器人工作量，確定任務(wù)分配結(jié)果后根據(jù)本文設(shè)計(jì)的全區(qū)域覆蓋方案確定各機(jī)器人工作區(qū)域和路徑規(guī)劃。