多功能農用機器人路徑規劃的多種優化算法

王　輝， 王景良， 朱龍彪， 邵小江

(1.南通大學機械工程學院，江蘇南通 226019； 2.江蘇海事職業技術學院，江蘇南京 211170)

城鎮化進程加快、人口數量激增、耕地面積日益減少、農作物價格偏低等諸多問題持續突出，會嚴重影響農民種植作物的積極性。在此背景下，發展現代農業技術，研發農業機器人系列產品，對提高農戶勞動生產率、改善農業生產環境、提高農業作業質量及提高農業機械化程度等具有極其重要的現實意義[1]。為加快農業機器人研發進程，世界各國都投入了大量的人力和物力支持，國內外學者經過多年的攻關研究，設計出了多種類型用于解決農業生產實際問題的機器人，如采摘機器人、移栽嫁接機器人、耕作機器人、噴藥施肥機器人及飼養機器人等[2]。為解決農作物病蟲害監測、工作環境監測、實現物料搬運功能，設計了一種多功能農用機器人。該機器人是集傳感器、人工智能、計算機、圖像處理、通信及控制工程等多學科前沿技術于一體的智能裝置，具有柔性好、靈活性強、安全可靠、智能化程度高及通用性、適應性、可擴展性強等優點[3]，可實現農作物病蟲害監測，工作環境監測、物料或肥料搬運以及在特殊情況下的人員搜索救援等功能。為實現上述功能，解決路徑規劃問題是首要前提。針對路徑規劃問題，目前常用的有效方法主要有Dijkstra算法、遺傳算法、蟻群算法、模擬退火算法、禁忌搜索算法等。為了解決多功能農用機器人路徑規劃問題，通過引入禁忌搜索算法、遺傳算法、蟻群算法和模擬退火算法，對農用機器人路徑規劃過程進行研究。

1　數學模型建立

多功能農用機器人路徑規劃問題的實質是路徑搜索問題，其目的是在已知有障礙物存在的工作環境中，系統根據機器人的當前位置、目標點位置及運行環境等相關信息，按照一定評價指標(如距離最短、程序耗時最少及收斂代數最小等)采用特定搜索策略，在環境地圖中搜索出一條從起點到目標點的最優或次優無沖突路徑，確保機器人能夠沿著該優化路徑順利完成農作物病蟲害監測、工作環境監測以及物料或肥料搬運等任務[4]。在路徑規劃中，系統要求農用機器人從原點出發，遍歷各作物種植區1次，完成作物病蟲害監測、工作環境監測或肥料搬運等，然后再返回至原點，這一過程可抽象為旅行商(TSP)問題。TSP問題作為經典組合優化NP難題，在問題規模復雜度較大的環境下，運用當前所提算法至今仍未得到精確解。由于各領域均有涉及TSP問題，因此，研究TSP求解方法對解決多領域復雜工程應用問題具有極其重要的現實意義和理論意義[5-6]。

多功能農用機器人的TSP問題可描述為：在已知各作物種植區和各作物種植區間距離的前提下，農用機器人從原點出發，遍歷各作物種植區1次，完成系統指定任務，然后再返回至起始點，在此過程中尋找一條閉合回路，并確保該閉合回路長度最短[7]。其數學模型可描述為：繪制工作環境交通路網圖，建立工作環境賦權圖G=(V，E)，其中，V表示作物種植區節點集，V={1，2，3，…，n}；E表示各作物種植區節點間形成的可行路段集，E={e1，e2，e3，…，en}；D表示各作物種植區節點間的距離集，即權重集，D={d(1，1)，d(1，2)，d(1，3)，…，d(i，j)，…，d(n，n)}，其中，d(i，j)表示2個作物種植區節點間距離，i、j∈V。其數學模型方程式可表示為[8]：

(1)

(2)

式中：Lpath表示農用機器人在遍歷各作物種植區中所能搜索到的最短路徑長度；(xi，yi)、(xj，yj)分別表示i、j這2種作物種植區節點的坐標值。

2　算法設計

2.1　禁忌搜索算法

禁忌搜索算法(tabu search algorithm，TSA)是由Glover教授通過模擬人類智力過程而提出的一種亞啟發式智能全局逐步尋優算法，因其具有記憶功能靈活、能跳出局部最優以及全局搜索能力強等優點，所以在優化組合、車間調度、路徑規劃、電路設計等領域得到了廣泛應用[9]。基本思想是搜索可行解空間，按照領域選優原則，在當前解領域內尋找一個更優解。為避免算法陷入局部最優和出現死循環，需將該解添加到禁忌表中。隨著迭代搜索進行，算法通過靈活使用禁忌表記錄搜索過程，并按照特赦準則不斷對記錄數據進行更新，最終確保算法在搜索到局部最優解的同時又能越過局部最優解而實現全局最優解搜索[10-11]。算法流程可進行如下描述，步驟一：初始化算法各參數，給出初始解，禁忌表置空TB=φ；步驟二：判斷算法搜索過程是否滿足終止準則，如果滿足，則算法搜索過程結束，輸出搜索結果，否則轉至步驟三；步驟三：由當前解產生鄰域解，并從中確定候選解；步驟四：判斷候選解是否滿足特赦準則，如果滿足，則將最佳狀態的候選解作為當前解。另外，還要按照先進先出的原則，用新當前解對應的禁忌對象替代最早進入禁忌表的禁忌對象，然后算法轉至步驟二，否則轉至步驟五；步驟五：判斷各候選解對應對象的禁忌屬性，從候選解集中選取非禁忌對象對應的最佳狀態為新的當前解，再按照先進先出原則更新禁忌表，然后轉至步驟二。

2.2　模擬退火算法

模擬退火算法(simulated annealing algorithm，SAA)是Metropolis等受固體物質退火原理啟發而提出的一種通用的自適應啟發式隨機優化搜索算法[12]，具有魯棒性強、全局收斂速度快、隱含并行性以及較強的環境適應能力等優點。基本思想是從初始時刻某一預設溫度出發，隨著迭代搜索進行，伴隨溫度參數不斷下降，按照Metropolis準則，結合概率突跳特性，在可行解空間中隨機尋找目標函數的全局最優解，即按照Metropolis準則以一定概率跳出局部最優陷阱而最終趨于全局最優解。選用模擬退火算法解決TSP的具體步驟如下[13]，步驟一：初始化算法參數，設定初始溫度、終止溫度、降溫速率以及鏈長等參數；步驟二：采用隨機排列方法生成初始解；步驟三：采用二鄰域變換法對當前解進行變換并生成新解，即產生新的路徑數組；步驟四：判斷Metropolis準則是否接受新解，判斷依據如方程(3)、(4)所示，如果Δδ<0，則以概率1接受新解，反之則以概率exp(-Δδ/T)接受新解；步驟五：判斷算法是否滿足終止條件T

Metropolis準則方程式如下[14]：

Δδ=f(S2)-f(S1)；

(3)

(4)

式中：S1、S2分別表示當前解和新解；f(S1)、f(S2)分別表示當前解路徑和新解路徑；Δδ表示當前解和新解路徑差。

2.3　蟻群算法

蟻群算法(ant colony optimization，ACO)是由Dorigo等通過模擬螞蟻覓食行為而提出的一種新型優化仿生進化算法。該算法是基于正反饋機制，利用螞蟻遺留在爬行路線上的信息素軌跡強弱和狀態轉移概率實現最優解搜尋。因其具有分布計算、信息正反饋、啟發式搜索以及較強的魯棒性等優點，所以被廣泛用于解決路徑規劃、生產調度、網絡路由以及圖像處理等問題[15]。選用蟻群算法解決農用機器人TSP問題具體步驟如下，步驟一：初始化算法參數，包括搜索次數、螞蟻數量、初始信息素濃度以及其他各主要調節參數等；步驟二：算法開始迭代搜索，將所有螞蟻初始條件下所在的各作物種植區節點加載到當前解集中，在算法執行過程中，螞蟻對下一作物種植區節點的訪問可按照方程式(5)確定；步驟三：判斷所有螞蟻是否完成對作物種植區節點訪問，若是，則計算所有螞蟻搜索的路徑長度，并記錄最優解，然后按照方程式(6)、式(7)和式(8)對各作物種植區連接路徑上的信息素進行更新；步驟四：判斷是否滿足終止條件N≤Nmax，如果滿足，則轉至步驟二，否則，算法搜索結束，輸出結果。

節點轉移概率函數式如下[16]：

(5)

式中：pijk表示轉移概率；allowedk表示下一步允許選擇的作物種植區節點集合；τij表示路段(i，j)的信息素軌跡強度；ηij表示啟發函數因子；α表示信息素軌跡相對重要程度因子；β表示期望程度因子。

信息更新規則方程式如下：

τij(t+1)=(1-ρ)·τij(t)+Δτij；

(6)

(7)

(8)

式中：ρ表示信息素揮發系數；Δτij表示路段(i，j)上的信息素增量；Q表示信息素增強因子。

2.4　遺傳算法

遺傳算法(genetic algorithm，GA)是由Holland與其同事在自然選擇和遺傳理論的基礎上，通過將自然界生物進化過程中的適者生存法則與種群內部染色體信息隨機交換機制進行有效結合，而發展起來的一種具有高效全局搜索能力的啟發式智能隨機優化算法。該算法主要由編碼、種群規模設定、適應度評估函數、選擇、交叉以及變異操作組成，具有并行計算、魯棒性強、全局尋優能力強以及易與其他啟發式算法結合等特點[17-18]。選用遺傳算法解決農用機器人TSP問題的具體步驟可表述為：(1)采用整數編碼方法將TSP問題空間解數據編碼成遺傳算法可以識別的串結構數據；(2)編碼操作結束后，隨機產生1個包含M個個體的種群，并確定算法初始搜索點；(3)根據目標函數設定種群適應度函數，具體如方程式(9)所示，依次計算種群中M個個體的適應度值，并以各個體適應度值的大小判斷種群中個體的優劣；(4)以適應度方程式(9)作為評價標準，采用輪盤賭法以一定概率從種群中篩選出優良個體，確保優良個體的某些重要基因遺傳到下一代；(5)采用部分映射交叉方法作用于步驟(4)中的種群；(6)確定變異對象，隨機選取2點，以一定變異概率置換其位置；(7)對步驟(6)中種群進行進化逆轉操作，產生新種群；(8)判斷終止條件N>Nmax是否滿足，若滿足，則搜索過程結束，輸出結果，反之則算法轉至步驟(3)。

適應度函數方程式如下：

(9)

3　仿真試驗與分析

為測試所提方法在多功能農用機器人路徑規劃中的實際效果，分別選用含有25、30、40、50個作物種植區的環境模型作為研究對象，以距離最短、程序耗時最少、收斂代數最小為評價指標，在Matlab軟件平臺上對所提方法進行仿真測試。為了使測試數據更好反映算法實際性能，每組數據均作了多次重復測試，結果見表1。另外，在作物種植區節點規模為50的環境模型中，由于禁忌搜索算法、模擬退火算法、蟻群算法無法搜索到滿足目標函數的優化路徑，因此，表1未給出該環境模型下的測試數據。

表1　各算法的測試數據

由表1數據可知，在作物種植區節點規模為25的環境模型下，TSA和ACO搜索路徑的最優解長度相同且最短，ACO搜索路徑的標準差和開始收斂代數均為最小，TSA的程序耗時最少；在節點規模為30的環境模型下，ACO搜索路徑的長度和標準差均為最小，SAA最先開始收斂，GA和ACO的數據測試次數相同且最少，TSA的程序耗時最少；在節點規模為40的環境模型下，ACO搜索路徑的長度和標準差均為最小，SAA最先開始收斂，GA的數據測試次數最少，TSA的程序耗時最少。綜上分析并結合表1數據可知，在節點規模較小環境模型下，算法全局搜索能力排序為ACO>GA>TSA>SAA；最優解穩定性排序大體為ACO>GA>SAA>TSA；收斂性能排序大體為SAA>ACO>GA>TSA，程序執行效率排序為TSA>SAA>GA>ACO；最優解獲得難易程度排序為GA>ACO>TSA>SAA；在節點規模較大環境模型下，GA的全局搜索能力優于其他3種算法。

各算法在節點規模為40的環境模型下的測試結果如圖1、圖2、圖3和圖4所示。

圖5為遺傳算法在節點規模為50的環境模型下的路徑軌跡迭代圖。由仿真測試結果可知，在節點數為40的環境模型下，各算法均能為農用機器人規劃出一條距離最短的優化路徑，但在節點數為50的環境模型下，僅有GA能為其規劃出距離最短的優化路徑。由圖1至圖4還可看出，SAA收斂性能優于ACO，ACO優于GA，GA優于TSA。此外，對比不同環境模型下的測試數據可知，針對節點規模較大的環境模型，GA可通過增大種群數量和增加收斂代數獲取最優路徑。

4　結論

本研究提出采用禁忌搜索算法、模擬退火算法、遺傳算法和蟻群算法解決多功能農用機器人路徑規劃問題。為驗證算法的有效性，分別以作物種植區節點數為25、30、40、50的環境模型為實例，對多功能農用機器人路徑規劃過程進行仿真測試。由測試結果可知，在滿足目標函數約束的條件下，各算法均能為農用機器人規劃出評價指標最好的優化路徑；在作物種植區節點規模較小環境下，雖然蟻群算法具有最強的全局搜索能力和較好的收斂性能，但程序執行效率最低；遺傳算法雖能通過增大種群數量和增加收斂代數解決農用機器人節點規模較大路徑規劃問題，但收斂性能較差；雖然禁忌搜索算法和模擬退火算法的全局尋優能力較差，但其程序執行效率高，因此，可考慮通過算法融合策略來增強其全局尋優能力。

參考文獻：

[1]姬江濤，鄭治華，杜蒙蒙，等. 農業機器人的發展現狀及趨勢[J]. 農機化研究，2014(2)：1-4，9.

[2]林歡，許林云. 中國農業機器人發展及應用現狀[J]. 浙江農業學報，2015，27(5)：865-871.

[3]王寶梁，薛金林. 開放式系統農業機器人技術概述[J]. 農機化研究，2013(6)：8-12.

[4]Zhang X，Zhao Y，Deng N，et al.Dynamic path planning algorithm for a mobile robot based on visible space and an improved genetic algorithm[J]. International Journal of Advanced Robotic System，2016(13)：1-17.

[5]張鑫龍，陳秀萬，肖漢，等. 一種求解旅行商問題的新型帝國競爭算法[J]. 控制與決策，2016，31(4)：586-592.

[6]Dewil R，Vansteenwegen P，Cattrysse D.A review of cutting path algorithms for laser cutters[J]. International Journal of Advanced Manufacturing Technology，2016，87(5/6/7/8)：1865-1884.

[7]Michail O，Spirakis P G.Traveling salesman problems in temporal graphs[J]. Theoretical Computer Science，2016(634)：1-23.

[8]王輝，朱龍彪，朱天成，等. 基于粒子群遺傳算法的泊車系統路徑規劃研究[J]. 工程設計學報，2016，23(2)：195-200.

[9]李陽，李文芳，馬驪，等. 混合退火算法求解旅行商問題[J]. 計算機應用，2014，34(增刊1)：110-113.

[10]汪定偉，王俊偉，王洪峰，等. 智能優化方法[M]. 北京：高等教育出版社，2007.

[11]邵陸壽. 優化設計方法[M]. 北京：中國農業出版社，2007.

[12]鞏敦衛，曾現峰，張勇. 基于改進模擬退火算法的機器人全局路徑規劃[J]. 系統仿真學報，2013，25(3)：480-483，488.

[13]潘國強，胡俊逸，洪敏，等. 考慮GIS的物流配送區域劃分與路徑規劃算法[J]. 大連海事大學學報，2015，41(1)：83-90.

[14]郁磊，史峰，王輝，等. MATLAB智能算法30個案例分析[M]. 2版.北京：北京航空航天大學出版社，2015.

[15]Wang J G，Wang N，Jiang H Y.Robot global path planning based on improved ant colony algorithm[C]. Paris：International Conference on Material，2015：2099-2102.

[16]Cao J.Robot global path planning based on an improved ant colony algorithm[J]. Journal of Computer and Communications，2016，4(2)：11-19.

[17]Jiang M，Fan X，Pei Z，et al.Robot path planning method based on improved genetic algorithm[J]. Sensors and Transducers，2014，166(3)：255-260.

[18]雷英杰，張善文. MATLAB遺傳算法工具箱及應用[M]. 西安：西安電子科技大學出版社，2014.