基于自適應(yīng)升溫模擬退火算法的農(nóng)業(yè)機(jī)器人全區(qū)域覆蓋策略

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

(1 山東理工大學(xué) 機(jī)械工程學(xué)院，山東 淄博 255000； 2 山東理工大學(xué) 農(nóng)業(yè)工程與食品科學(xué)學(xué)院，山東 淄博 255000； 3 華南農(nóng)業(yè)大學(xué) 電子工程學(xué)院/人工智能學(xué)院，廣東 廣州 510642)

智慧化無(wú)人農(nóng)業(yè)是將傳感數(shù)據(jù)與智能決策作為管控全局的要素[1]，并結(jié)合多傳感信息融合技術(shù)、人機(jī)交互技術(shù)與云邊協(xié)同計(jì)算技術(shù)對(duì)農(nóng)業(yè)機(jī)器人進(jìn)行信息化管理的現(xiàn)代農(nóng)業(yè)[2]。解決農(nóng)業(yè)機(jī)器人在智慧化無(wú)人農(nóng)場(chǎng)中的全區(qū)域覆蓋問(wèn)題可減少機(jī)器人工作區(qū)域的重復(fù)率，達(dá)到對(duì)農(nóng)田工作區(qū)域的全覆蓋，是當(dāng)下急需解決的關(guān)鍵問(wèn)題。

針對(duì)機(jī)器人全區(qū)域覆蓋的環(huán)境不同，全區(qū)域覆蓋問(wèn)題可分為靜態(tài)已知環(huán)境的覆蓋與動(dòng)態(tài)未知環(huán)境的覆蓋[3-4]。農(nóng)業(yè)機(jī)器人所面對(duì)的大田作業(yè)一般為靜態(tài)已知環(huán)境下的離線預(yù)規(guī)劃地圖覆蓋問(wèn)題，目前已有的研究多通過(guò)柵格法與單元分解法簡(jiǎn)化機(jī)器人全區(qū)域覆蓋的復(fù)雜工作環(huán)境[5]。通過(guò)對(duì)復(fù)雜工作環(huán)境進(jìn)行柵格化處理，完成全區(qū)域覆蓋，可保證機(jī)器人遍歷的精度，如賀利樂(lè)等[6]通過(guò)機(jī)器人本體上的傳感器構(gòu)建基于動(dòng)態(tài)柵格法的工作環(huán)境，從而保證機(jī)器人實(shí)現(xiàn)路徑全覆蓋，但系統(tǒng)開(kāi)展機(jī)器人全區(qū)域覆蓋的計(jì)算量會(huì)隨區(qū)域地圖的增大而呈指數(shù)式增加[7-8]；單元分解法則根據(jù)工作區(qū)域中現(xiàn)有障礙物的形狀、大小、位置與區(qū)域分解規(guī)則將整體工作區(qū)域劃分成多個(gè)虛擬子區(qū)域，以完成對(duì)復(fù)雜工作區(qū)域的簡(jiǎn)化[9]，如胡詩(shī)宇[10]利用柵格法對(duì)環(huán)境地圖建模，通過(guò)矩形分解的思想對(duì)地圖單元分解，并通過(guò)深度優(yōu)先搜索算法求解子區(qū)域之間的遍歷順序，但深度優(yōu)先搜索算法只適用于求解可行解，不能找到區(qū)域間最優(yōu)遍歷順序。

本文通過(guò)柵格法與單元分解法相結(jié)合，簡(jiǎn)化農(nóng)業(yè)機(jī)器人的復(fù)雜工作環(huán)境；通過(guò)改進(jìn)的模擬退火算法，求解機(jī)器人在分區(qū)間的最優(yōu)遍歷順序；通過(guò)A*算法與八鄰域搜索法相結(jié)合的方法，進(jìn)行機(jī)器人的跨區(qū)域銜接路徑規(guī)劃，以此完成農(nóng)業(yè)機(jī)器人對(duì)工作區(qū)域的全區(qū)域覆蓋。

1 柵格化農(nóng)田與矩形分區(qū)

本文從山東理工大學(xué)蘭玉彬團(tuán)隊(duì)與淄博禾豐種業(yè)科技股份有限公司共建的智慧化無(wú)人農(nóng)場(chǎng)的實(shí)際農(nóng)業(yè)生產(chǎn)環(huán)境出發(fā)，定義農(nóng)業(yè)機(jī)器人的復(fù)雜工作環(huán)境，即智慧化無(wú)人農(nóng)場(chǎng)中存在的由縱橫交錯(cuò)的田間道路自然分割的離散分布的數(shù)片農(nóng)田，以及農(nóng)田中存在的一些分散障礙物如農(nóng)田中的風(fēng)力發(fā)電機(jī)、電線桿、固定安裝的傳感器等構(gòu)成了農(nóng)業(yè)機(jī)器人復(fù)雜的工作環(huán)境[11]。

1.1 柵格化農(nóng)田與障礙物膨脹處理

根據(jù)本文建立的復(fù)雜農(nóng)田工作環(huán)境概念，定義工作環(huán)境地圖并參考文獻(xiàn)[12]方法對(duì)此區(qū)域進(jìn)行柵格化處理，將農(nóng)業(yè)機(jī)器人的工作范圍設(shè)置為柵格圖的單位長(zhǎng)度。農(nóng)田環(huán)境與農(nóng)田柵格化結(jié)果如圖1a所示。為避免農(nóng)業(yè)機(jī)器人在全遍歷過(guò)程中陷入死角，本文針對(duì)邊界與柵格線不重合的障礙物進(jìn)行二值化膨脹處理[13]，處理后的效果如圖1b所示。

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

為簡(jiǎn)化農(nóng)業(yè)機(jī)器人進(jìn)行大田作業(yè)時(shí)的復(fù)雜工作環(huán)境，本文將由田間道路自然分割形成的單片農(nóng)田作為一級(jí)工作區(qū)域分區(qū)，并在一級(jí)工作區(qū)域分區(qū)內(nèi)根據(jù)農(nóng)田區(qū)域中障礙物的形狀、大小與位置劃分農(nóng)業(yè)機(jī)器人可自由遍歷的二級(jí)工作區(qū)域分區(qū)，通過(guò)農(nóng)業(yè)機(jī)器人在一級(jí)分區(qū)與二級(jí)分區(qū)內(nèi)的遍歷完成對(duì)農(nóng)田工作區(qū)域的全區(qū)域覆蓋。

劃分二級(jí)柵格分區(qū)具體方案為：分別過(guò)障礙物膨脹處理后的左下角頂點(diǎn)與右上角頂點(diǎn)作垂直于X軸的分區(qū)線，遇到其他障礙物或田間道路即停止；分別過(guò)障礙物膨脹處理后的左上角頂點(diǎn)與右下角頂點(diǎn)作垂直于Y軸的分區(qū)線，遇到其他障礙物或田間道路即停止。在圖1b的基礎(chǔ)上進(jìn)行柵格分區(qū)的結(jié)果如圖2a所示。

圖1 柵格化農(nóng)田建模 (a)與障礙物膨脹處理 (b)Fig.1 Rasterized farmland modeling (a) and obstacle expansion treatment (b)

圖2 柵格分區(qū) (a)與柵格分區(qū)合并 (b)Fig.2 Grid partition (a) and grid partition merging (b)

工作區(qū)域中二級(jí)分區(qū)的數(shù)量與機(jī)器人遍歷面積重復(fù)率成正比，為減少機(jī)器人的路徑重復(fù)率，本文在柵格分區(qū)的基礎(chǔ)上進(jìn)行分區(qū)合并操作。一個(gè)柵格分區(qū)與其鄰近分區(qū)共同邊長(zhǎng)度相等則可以進(jìn)行分區(qū)合并[14]，分區(qū)時(shí)先合并可縱向合并的分區(qū)，再合并可橫向合并的分區(qū)。分區(qū)合并結(jié)果如圖2b所示。

2 基于模擬退火算法求解旅行商問(wèn)題

優(yōu)化農(nóng)業(yè)機(jī)器人在分區(qū)間的遍歷順序可減少農(nóng)業(yè)機(jī)器人在分區(qū)間的銜接路徑，進(jìn)而減少其遍歷路徑重復(fù)率、提高工作效率。本文在優(yōu)化各一級(jí)分區(qū)遍歷順序之后再優(yōu)化各一級(jí)分區(qū)內(nèi)二級(jí)分區(qū)的遍歷順序，通過(guò)農(nóng)業(yè)機(jī)器人在一級(jí)分區(qū)與二級(jí)分區(qū)內(nèi)的遍歷，實(shí)現(xiàn)整體工作區(qū)域的全覆蓋。尋找農(nóng)業(yè)機(jī)器人在分區(qū)間的最佳遍歷順序本質(zhì)上是一個(gè)旅行商問(wèn)題[15]。

2.1 旅行商問(wèn)題

將圖2b中的各分區(qū)抽象化為一個(gè)個(gè)由分區(qū)重心點(diǎn)代表的質(zhì)點(diǎn)，則旅行商問(wèn)題可以描述為：旅行商從某個(gè)質(zhì)點(diǎn)出發(fā)訪問(wèn)，尋找一條遍歷全部r個(gè)質(zhì)點(diǎn)且每個(gè)質(zhì)點(diǎn)僅遍歷1次的最短路徑[16]，即搜索自然子集N={1，2，…，r}中各元素(質(zhì)點(diǎn)編號(hào))的排序，使得遍歷各質(zhì)點(diǎn)的路徑長(zhǎng)度(R)最?。?/p>

2.2 模擬退火算法

模擬退火算法因其隨機(jī)跳變接受新解的特性而具有較好的收斂速度與尋優(yōu)能力[18]，故本文通過(guò)模擬退火算法求解旅行商問(wèn)題。算法求解旅行商問(wèn)題時(shí)首先設(shè)定初始溫度、降溫速率與鏈長(zhǎng)等參數(shù)，并建立模擬退火算法所得可行解i的適應(yīng)度值為：

算法在不斷降溫的過(guò)程中通過(guò)多種變換法生成新解，并根據(jù)Metropolis準(zhǔn)則以概率的形式選擇是否保留此解，則算法溫度為T(mén)時(shí)新解i被接受的概率P為：

3 基于自適應(yīng)升溫的模擬退火算法

本文提出基于貪婪機(jī)制的優(yōu)質(zhì)可行解生成方法與基于自適應(yīng)升溫的模擬退火算法改進(jìn)方法，以提高模擬退火算法求解旅行商問(wèn)題的尋優(yōu)能力與收斂性能。

3.1 基于貪婪機(jī)制的優(yōu)質(zhì)可行解生成方法

傳統(tǒng)模擬退火算法通常采用2變換法與3變換法生成新解，本文在以上2種方法的基礎(chǔ)上借鑒遺傳算法變異操作的思想，提出關(guān)于模擬退火算法的第3種新解生成方法即遺傳變異法。模擬退火算法新解生成方法如圖3所示。

圖3 模擬退火算法新解生成方法Fig.3 New solution generation methods of simulated annealing algorithm

2變換法任意選擇2個(gè)原解中的位置，將2個(gè)位置中間的排列順序進(jìn)行倒置操作以生成新解，將此種方法得到的新解適應(yīng)度值記為swap2(f)；3變換法任意選擇3個(gè)位置，將前兩個(gè)位置間的數(shù)字置于第3個(gè)數(shù)字后以生成新解，將此種方法得到的新解適應(yīng)度值記為swap3(f)；遺傳變異法通過(guò)交換隨機(jī)選擇的2個(gè)數(shù)字的位置以生成新解，將此種方法得到的新解適應(yīng)度值記為swap4(f)。

本文計(jì)算以上3種方法生成的新解的適應(yīng)度值，并借鑒貪婪機(jī)制逐步尋找局部最優(yōu)以達(dá)到全局最優(yōu)的思想，只保留適應(yīng)度值高的新解對(duì)應(yīng)的狀態(tài)作為算法的實(shí)時(shí)新?tīng)顟B(tài)(New state)，即：

3.2 基于自適應(yīng)升溫的模擬退火算法

在模擬退火算法陷入局部最優(yōu)解時(shí)，人為提高算法運(yùn)行的溫度，有助于提高算法對(duì)于較差解的接受概率，進(jìn)而有更大的可能跳出局部最優(yōu)解。若算法運(yùn)行中產(chǎn)生的可行解的鄰域內(nèi)無(wú)比該解更優(yōu)的可行解，即：則將其定義為算法已陷入局部最優(yōu)，式中k表示算法陷入局部時(shí)在當(dāng)前溫度下已迭代的次數(shù)，L表示算法鏈長(zhǎng)。

進(jìn)行局部升溫操作時(shí)若升溫幅度過(guò)小，則較差解的接受概率提升效果有限，達(dá)不到跳出局部最優(yōu)解的效果；若升溫幅度過(guò)大，則算法對(duì)較差解的接受概率接近100%[19]，算法尋優(yōu)又會(huì)進(jìn)入漫長(zhǎng)的全局搜索，嚴(yán)重降低算法的收斂速度。故本文建立解集多樣性的概念以設(shè)計(jì)自適應(yīng)升溫策略。算法運(yùn)行過(guò)程中產(chǎn)生的各可行解組成一個(gè)解集，根據(jù)算法所記錄的解集實(shí)時(shí)最優(yōu)適應(yīng)度值與解集實(shí)時(shí)平均適應(yīng)度值的關(guān)系定義當(dāng)前解集多樣性

4 基于 A＊算法的分區(qū)間銜接路徑

農(nóng)業(yè)機(jī)器人在一個(gè)分區(qū)內(nèi)完成遍歷工作時(shí)，需根據(jù)改進(jìn)模擬退火算法規(guī)劃的分區(qū)間最優(yōu)遍歷順序轉(zhuǎn)至下個(gè)分區(qū)起點(diǎn)繼續(xù)遍歷。由于農(nóng)業(yè)機(jī)器人工作環(huán)境的復(fù)雜性，上個(gè)分區(qū)終點(diǎn)與下個(gè)分區(qū)起點(diǎn)可能并不連續(xù)，所以，為了提高農(nóng)業(yè)機(jī)器人的工作效率，降低農(nóng)業(yè)機(jī)器人的遍歷路徑重復(fù)率，本文以路徑重復(fù)率為優(yōu)化目標(biāo)，通過(guò)A*算法規(guī)劃?rùn)C(jī)器人分區(qū)間的銜接路徑。

A*算法通過(guò)建立從起始點(diǎn)到目標(biāo)點(diǎn)的評(píng)價(jià)函數(shù)規(guī)劃兩點(diǎn)間的最優(yōu)路徑，評(píng)價(jià)函數(shù)計(jì)算式為：

啟發(fā)代價(jià)函數(shù)表示一種預(yù)估距離，此函數(shù)的存在能夠保證機(jī)器人始終向目標(biāo)點(diǎn)移動(dòng)[20]，本文中啟發(fā)代價(jià)函數(shù)通過(guò)曼哈頓距離實(shí)現(xiàn)：

通過(guò)八鄰域搜索法搜索當(dāng)前點(diǎn)(m,n)的周?chē)鷸鸥?，?(m-1,n+1)、(m,n+1)、(m+1,n+1)、(m+1,n)、(m+1,n-1)、(m,n-1)、(m-1,n-1)、(m-1,n)。將以上柵格作為當(dāng)前點(diǎn)代入評(píng)價(jià)函數(shù)計(jì)算其路徑代價(jià)，在路徑代價(jià)最小的柵格基礎(chǔ)上繼續(xù)使用A*算法與八鄰域搜索法重復(fù)以上過(guò)程探索路徑直至目標(biāo)點(diǎn)。

5 算法仿真與試驗(yàn)驗(yàn)證

為驗(yàn)證改進(jìn)模擬退火算法的收斂能力與尋優(yōu)能力，以及農(nóng)業(yè)機(jī)器人全區(qū)域覆蓋策略對(duì)路徑重復(fù)率的優(yōu)化效果。本文分別通過(guò)Matlab 2014軟件對(duì)改進(jìn)模擬退火算法與農(nóng)業(yè)機(jī)器人全區(qū)域覆蓋策略進(jìn)行仿真分析。

5.1 改進(jìn)模擬退火算法仿真

定義3組分別包含20、30、40個(gè)分區(qū)的重心點(diǎn)坐標(biāo)，對(duì)比傳統(tǒng)遺傳算法、模擬退火算法與本文改進(jìn)模擬退火算法規(guī)劃各組最優(yōu)路徑所得到的路徑長(zhǎng)度、算法收斂時(shí)的迭代次數(shù)，結(jié)果如表1所示。3個(gè)算法規(guī)劃40個(gè)分區(qū)的最優(yōu)遍歷路徑如圖4所示。

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

由表1可知，在分區(qū)數(shù)量為20、30時(shí)，3種算法均能得到相近的路徑長(zhǎng)度，但在分區(qū)數(shù)量為20時(shí)，改進(jìn)模擬退火算法收斂時(shí)的迭代次數(shù)較模擬退火算法和傳統(tǒng)遺傳算法分別減少了63.3%和66.7%；在分區(qū)數(shù)量為30時(shí)，改進(jìn)模擬退火算法收斂時(shí)的迭代次數(shù)較模擬退火算法和傳統(tǒng)遺傳算法分別減少了35.5%和72.0%。由表1和圖4可知，在分區(qū)數(shù)量為40時(shí)，改進(jìn)的模擬退火算法所獲得的路徑長(zhǎng)度分別比模擬退火算法和傳統(tǒng)遺傳算法減少了14.7%和10.1%，收斂時(shí)的迭代次數(shù)分別減少了9.8%和59.1%。

圖4 3 種算法對(duì) 40 個(gè)分區(qū)的最優(yōu)遍歷路徑規(guī)劃圖Fig.4 The optimal traversal path planning diagram of 40 partitions by three algorithms

5.2 路徑遍歷仿真

為減少機(jī)器人的轉(zhuǎn)彎次數(shù)，機(jī)器人在分區(qū)內(nèi)遍歷時(shí)沿矩形分區(qū)的長(zhǎng)邊作往返式遍歷。選擇下個(gè)分區(qū)中最靠近上個(gè)分區(qū)終點(diǎn)的單元格作為下個(gè)分區(qū)的起點(diǎn)。農(nóng)業(yè)機(jī)器人在圖2b基礎(chǔ)上進(jìn)行的路徑遍歷仿真如圖5所示。

圖2b中農(nóng)業(yè)機(jī)器人可自由遍歷的工作面積為189 m2，圖5 中機(jī)器人移動(dòng)總面積為 222 m2，機(jī)器人遍歷路徑重復(fù)率為14.86%，工作區(qū)域覆蓋率接近100%。

圖5 遍歷路徑規(guī)劃圖Fig.5 Traversal path planning diagram

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

為驗(yàn)證本文全區(qū)域覆蓋策略對(duì)農(nóng)業(yè)機(jī)器人遍歷面積重復(fù)率與覆蓋率的優(yōu)化作用，以山東理工大學(xué)蘭玉彬團(tuán)隊(duì)研發(fā)的高地隙噴藥機(jī)器人為對(duì)象進(jìn)行全區(qū)域覆蓋遍歷試驗(yàn)。

通過(guò)智慧化無(wú)人農(nóng)場(chǎng)云平臺(tái)人機(jī)交互界面將整體工作區(qū)域劃分為由虛擬道路分割成的4個(gè)子區(qū)域，在整體工作區(qū)域中設(shè)置分散的11個(gè)異形障礙物，并以此為環(huán)境地圖進(jìn)行機(jī)器人路徑規(guī)劃。

本試驗(yàn)中高地隙噴藥機(jī)器人雙臂噴藥桿展開(kāi)后的工作范圍為10 m，行駛速度為1.7 m/s，試驗(yàn)工作區(qū)域面積為0.8 hm2。高地隙噴藥機(jī)器人、部分異形障礙物放大圖與虛擬道路分割線如圖6所示。

圖6 農(nóng)業(yè)機(jī)器人試驗(yàn)現(xiàn)場(chǎng)Fig.6 Experimental site of agricultural robot

根據(jù)高地隙噴藥機(jī)器人遍歷過(guò)程中實(shí)時(shí)回傳至農(nóng)場(chǎng)云平臺(tái)的工作數(shù)據(jù)可知，高地隙噴藥機(jī)器人使用9.1 min完成整體工作區(qū)域的遍歷，實(shí)際遍歷面積為0.927 hm2，遍歷面積重復(fù)率為15.83%，工作區(qū)域覆蓋率接近100%。

6 結(jié)論

本文引入遺傳算法變異操作的思想，建立基于貪婪機(jī)制的模擬退火算法優(yōu)質(zhì)可行解生成方法；設(shè)定模擬退火算法陷入局部最優(yōu)解的判斷依據(jù)并建立算法解集多樣性的概念，設(shè)計(jì)基于自適應(yīng)升溫的模擬退火算法改進(jìn)方案，以提高算法的尋優(yōu)能力與收斂速度。仿真試驗(yàn)表明，在分區(qū)規(guī)模為40時(shí)，改進(jìn)的模擬退火算法所獲得的路徑長(zhǎng)度分別比模擬退火算法和傳統(tǒng)遺傳算法減少了14.7%和10.1%，收斂時(shí)的迭代次數(shù)分別減少了9.8%和59.1%。

本文根據(jù)農(nóng)場(chǎng)實(shí)際工作環(huán)境建立一級(jí)分區(qū)的概念，在柵格化環(huán)境建模與障礙物膨脹處理的基礎(chǔ)上，在一級(jí)分區(qū)內(nèi)部建立二級(jí)分區(qū)的柵格分區(qū)和分區(qū)合并規(guī)則。通過(guò)改進(jìn)的模擬退火算法優(yōu)化機(jī)器人在分區(qū)間的遍歷順序，通過(guò)A*算法與八鄰域搜索法相結(jié)合進(jìn)行機(jī)器人跨區(qū)域銜接路徑規(guī)劃。仿真試驗(yàn)表明，機(jī)器人遍歷路徑重復(fù)率為14.86%。機(jī)器人現(xiàn)場(chǎng)遍歷試驗(yàn)表明，高地隙噴藥機(jī)器人遍歷面積重復(fù)率為15.83%，工作區(qū)域覆蓋率接近100%。