農業(yè)機器人路徑優(yōu)化及軌跡跟蹤研究——基于遺傳算法

陳順立

(重慶工程職業(yè)技術學院，重慶 402260)

?

農業(yè)機器人路徑優(yōu)化及軌跡跟蹤研究
——基于遺傳算法

陳順立

(重慶工程職業(yè)技術學院，重慶 402260)

隨著我國信息化水平的不斷提高，以及機械自動化、計算機控制系統(tǒng)和測試計量行業(yè)的不斷發(fā)展，移動機器人達到了一個全新的高度，智能機器人被廣泛應用到農業(yè)生產、工業(yè)生產和高等研究等各個領域。在機器人眾多研究問題中，路徑規(guī)劃和軌跡跟蹤一直是比較復雜并較難解決的問題。為此，基于遺傳算法，根據移動機器人工作特點和運動特性，采用幾何法建立了機器人工作空間的環(huán)境模型，并對路徑進行了有效編碼，為機器人實時規(guī)劃出無碰撞、路線短的全局路徑，對其運動軌跡進行有效跟蹤。仿真實驗表明：所設計研究的機器人全局路徑規(guī)劃和軌跡跟蹤技術具有較好的效果，其在行進過程中能及時、有效地避開前方障礙，可靠性強，穩(wěn)定性好，應用前景非常廣闊。

移動機器人；全局路徑規(guī)劃；軌跡跟蹤；遺傳算法

0 引言

近年來，機器人的發(fā)展獲得了較大突破，工業(yè)機器人技術相當成熟，各類工業(yè)制造都開始實現自動化生產，應用于農業(yè)的移動機器人也獲得了很大進展。在機器人的研究中，全局路徑優(yōu)化和軌跡跟蹤是比較關鍵的環(huán)節(jié)，其對機器人自主路徑規(guī)劃具有重要的研究意義，是對機器人行進中路徑優(yōu)化控制的基礎。目前，對于移動機器人軌跡優(yōu)化的研究方法很多，主要采用蟻群、遺傳、BP網絡神經及人工智能等方法。本文引入遺傳算法，對移動機器人運動過程進行全局路徑優(yōu)化和軌跡跟蹤，可以有效提高機器人自主控制能力，實現機器人路徑規(guī)劃的實時性。

1 遺傳算法概述

遺傳算法是模擬自然選擇和遺傳生物進化過程中的計算模型，是一種全局搜索最優(yōu)解的方法。其模擬生物研究理論中進化和遺傳的過程，將生物進化中的繁殖、雜交、變異、競爭和選擇引入算法中。對于具體的優(yōu)化問題，常常采用具有一定數量個體抽象表示的種群，根據“適者生存,優(yōu)勝劣汰”的競爭規(guī)律向更好的解進化。生物進化過程中，常常從獨立隨機個體種群開始，然后一代代進化發(fā)展下去。在進化中，以種群適應度為評價標準，隨機選擇多個生存下來的個體，通過進化規(guī)律產生新的個體種群，然后根據算法一代代迭代下去。遺傳算法其實是一種計算機模擬方法，具有適用面廣、多點搜索、魯棒性好、自適應強及并行性高的特點，從本質來講,其是一種有著自適應能力的搜索優(yōu)化方法。遺傳算法解決機器人路徑優(yōu)化及軌跡跟蹤問題的流程如圖1所示。

圖1 遺傳算法流程圖

2 移動機器人環(huán)境描述與路徑編碼

在研究環(huán)境信息的過程中，主要有柵格法、拓撲法和幾何法3種建模方法。在機器人路徑優(yōu)化和軌跡跟蹤的研究中，常常根據環(huán)境、機器人的運動方式及需要解決問題的具體特點來選擇建模方法。柵格法和拓撲法首先需要先建立一個搜索圖，再根據路徑搜索方法求解路徑最優(yōu)解，過程較為復雜，靈活性低；而幾何法則是以幾何信息進行環(huán)境建模，采用幾何法描述環(huán)境信息，直接可以求出路徑規(guī)劃的最優(yōu)解，表達直接、精確。因此，本文采用幾何法建立環(huán)境模型，搭建前需要對作業(yè)區(qū)域進行幾種假設：

1)機器人在二維平面空間運動；

2)機器人的工作區(qū)域分布有限個障礙物，并可以用(X,Y)標注；

3)擴大障礙物邊界，不考慮機器人自生形狀和大小，將其看作為一個質點。

障礙物標注的方法是環(huán)境建模的核心，一般采用幾何標量來描述障礙物。假設在機器人作業(yè)區(qū)域XOY存在m個障礙物(O1,O2,…,Om)，第s個障礙物有nj個頂點，則作業(yè)區(qū)域中障礙物Oj可表示為

Oj={(X1,Y1),(X2,Y2),…,(Xnj,Ynj)}

(1)

其中，(Xnj,Ynj)為障礙物的第nj個頂點坐標，則

XOY={WSB,O1,…,Om}

(2)

其中，WSB為作業(yè)區(qū)域的全部邊界。

根據移動機器人全局路徑規(guī)劃和軌跡跟蹤環(huán)境建模的分析，建立如圖2所示的作業(yè)區(qū)域環(huán)境模型。

圖2 機器人作業(yè)區(qū)域環(huán)境模型

圖2中，移動機器人作業(yè)環(huán)境為150m×150m方形區(qū)域，深色不規(guī)則形狀為障礙物，一共有13個。

遺傳算法迭代優(yōu)化中的個體都可以看作一條路徑，并可以采用編碼方式進行表示。為了表示形象化以及計算方便，把路徑表示為可操作的路徑，稱之為個體編碼。

編碼長度決定遺傳算法優(yōu)化求解時間的長短，編碼太長會讓求解時間成幾何倍數增長。因此，在進行路徑編碼時常常需要簡化編碼長度,用一維編碼表示二維軌跡。個體路徑編碼簡化如圖3所示。

圖3 個體路徑編碼簡化

圖3中，S為移動機器人運動起點；G為終點。路徑優(yōu)化方法是在起點和中點路線間選擇最優(yōu)路徑的點坐標(xi,yi)。在作業(yè)區(qū)域XOY中，路徑點為二維，為了優(yōu)化編碼長度，將XOY坐標系進行變換為X′O′Y′，X′軸為起末點之間連線，并將其分為x1，x2，… ，xn，即可以將二維路徑點轉換位Y′坐標編碼。簡化格式如圖4所示。

圖4 簡化編碼格式

3 遺傳算法的適應度函數

適應度函數是影響遺傳算法收斂速度及能否找到最優(yōu)解的直接因素，移動機器人路徑規(guī)劃的一般需要考慮兩點：躲避障礙物和移動距離最短。一般而言，適應度函數由目標函數通過映射變換而成，常常采用評價函數加權求和法的方法確定，這種方法比較難確定權值，穩(wěn)定性差，權值常常因路徑與障礙物特點變化而變化。因此，在選擇目標函數時，需要將其變量最小化，同時與躲避障礙物和移動距離最短最優(yōu)相結合。躲避障礙物是首要條件，是移動機器人在工作區(qū)域正常作業(yè)的保證，躲避障礙物條件需要確定最優(yōu)路徑沒有任何障礙物。假設移動機器人在圖4作業(yè)區(qū)域工作，則

1)優(yōu)化路徑不經過障礙物，根據遺傳算法神經網絡模式確定適應度函數Fit(1) 為

(3)

其中，i為路徑點序號；n為作業(yè)區(qū)域的障礙物總數；當路徑點不經過障礙物時，適應度函數值為1，反之為0。

2)設移動機器人某一段運動距離為didi+1,則與障礙物之間不相交的適應度函數Fit(2) 為

(4)

結合式(2)和式(3)，躲避障礙物條件的適應度函數為

Fi1t=Fit(1)×Fit(2)

(5)

3)最優(yōu)路徑以移動距離最短為標準時，其適應度函數表示為

(6)

其中，λ是一個可以根據仿真過程進行調整且與精度相關的常數。

綜上所述，移動機器人最終適應度函數為

Fit=Fi1t×Fi2t

(7)

為了簡化函數變量，式(7)將躲避障礙物和移動距離最短兩個約束條件結合起來，計算方便，避免了不穩(wěn)定因素。

4 移動機器人全局路徑規(guī)劃與軌跡跟蹤

4.1 移動機器人的全局路徑規(guī)劃

在遺傳算法實現過程中，可以將優(yōu)化問題對應于抗原并求解。在路徑規(guī)劃問題上，抗體可以抽象為求最優(yōu)路徑，在所有從起點到終點中選擇一條最優(yōu)解。路徑節(jié)點求優(yōu)示意如圖5所示。

圖5 路徑節(jié)點求優(yōu)示意圖

路徑轉折點為節(jié)點，可以用Pi=(xi,yi)來表示，那么抗體可以表示為

P={P1,P2,…Pn}={(X1,Y1),(X2,Y2),…,

(Xn,Yn)}

(8)

其中，P1和P2分別表示為移動機器人起點和終點。

為了簡化編碼長度，提高路徑優(yōu)化能力，可以減少空間維數，抗體可以表示為

P={y1,y2,…yn}

(9)

在計算求解中，將該抗體編碼轉化為如圖6所示的基因串形式。

圖6 抗體編碼轉化為基因串形式

選擇初始個體是遺傳算法進行迭代算法最重要的因素。首次迭代時，其任意產生，個體的抗體節(jié)點數為一整數；而在后面迭代運算中，則采用生物進化論規(guī)律，保存抗體強的個體。

4.2 移動機器人的軌跡跟蹤

移動機器人軌跡跟蹤是解決機器人在t時刻如何運動的問題。如果規(guī)劃路徑是一條隨時間變化的連續(xù)曲線，移動機器人位姿誤差如圖7所示，則可以根據下面方法設計軌跡跟蹤器。

圖7 移動機器人位姿誤差

如圖7所示，模擬生成的機器人規(guī)劃路徑為

pd(t)=((xd(t),yd(t),θd(t))T

(8)

其中，θ為目標方向角。

設定移動機器人的位姿為

p(t)=(x(t),y(t),θ(t))T

(9)

則機器人實際運動的速度為

q=(v,w)T

(10)

其中，v為移動機器人的線速度；w為移動機器人的角速度。

移動機器人位姿誤差矢量表達式為

(11)

式(11)可以變換為

(12)

由以上分析可知：移動機器人軌跡跟蹤的問題可以轉化為求解最優(yōu)線速度v和線速度w，使得對于任何初始誤差的狀態(tài)(ex,ey,eθ)都可以穩(wěn)定在(0,0,0)附近。

5 仿真實驗

為了驗證遺傳算法在移動機器人全局路徑規(guī)劃和軌跡跟蹤的可行性和有效性，本文在MatLab軟件中進行路徑規(guī)劃仿真實驗，移動機器人工作起點坐標為[0,0]，終點坐標為[150,0]。為了和傳統(tǒng)一般算法做對比，同時進行遺傳算法和傳統(tǒng)算法兩種優(yōu)化模式。仿真過程中兩組算法采用相同的參數：初始個體共有m=50個，設定進化代數N=60，仿真結果如圖8所示。

圖8 MATLAB仿真結果

由圖8可以看出：傳統(tǒng)和遺傳算法都可以有效對路徑進行優(yōu)化；從路徑長度和光滑度來看，遺傳算法路徑較短并且光滑度高，具有更好的優(yōu)化效果，優(yōu)勢更加明顯。

6 結論

為了實現移動機器人全局路徑規(guī)劃和軌跡跟蹤的功能，利用遺傳算法對路徑規(guī)劃進行有效優(yōu)化，采用幾何法對機器人工作空間進行環(huán)境建模，并對路徑采用有效編碼，簡化了計算的復雜性，大大提高了優(yōu)化的效率和實時性。

利用MatLab軟件對機器人路徑規(guī)劃進行了仿真實驗，結果表明：遺傳算法比傳統(tǒng)算法具有更明顯的優(yōu)化效果；從路徑長度和光滑度來看，遺傳算法的全局優(yōu)化效果更為明顯，大大提高了機器人的可行性、可靠性和工作效率，可以有效節(jié)省作業(yè)時間，降低機器人的能量消耗，實際應用前景寬廣。

[1] 江斌.人工免疫算法的基礎研究及其應用[D].長沙:中南大學,2008.

[2] 張穎.改進的免疫遺傳算法在基于神經網絡的多機器人協(xié)作搬運中的應用[D].長沙:中南大學,2008.

[3] 陳曦.基于免疫遺傳算法的移動機器人路徑規(guī)劃研究[D].長沙:中南大學,2008.

[4] 王評.人工免疫算法研究及其在數據挖掘上的應用[D].福州:福州大學,2005.

[5] 劉傳領.基于勢場法和遺傳算法的機器人路徑規(guī)劃技術研究[D].南京:南京理工大學,2012.

[6] 崔建軍.基于遺傳算法的移動機器人路徑規(guī)劃研究[D].西安：西安科技大學,2010.

[7] 伍洲,方彥軍.基于智能路徑規(guī)劃算法的移動機器人系統(tǒng)設計[J].傳感器與微系統(tǒng),2008(9):93-96.

[8] 趙秀平,譚冠政.基于免疫遺傳算法的多約束QoS組播路由選擇方法[J].計算機應用,2008(3):591-595.

[9] 劉國聯(lián),譚冠政,何燕.基于改進人工免疫算法的PID參數優(yōu)化研究[J].計算機工程與應用,2008(19): 84-86.

[10] 劉國聯(lián),譚冠政,何燕.一種改進的免疫遺傳算法的性能分析[J].科學技術與工程,2008(14):3773-3776, 3782.

[11] 杜宗宗,劉國棟.基于遺傳模擬退火算法的移動機器人路徑規(guī)劃[J].計算機仿真,2009(12):118-121,125.

[12] 賈亞軍,叢爽.基于相似性矢量距選擇的改進人工免疫算法[J].計算機工程與應用,2011(6):26-29.

[13] 張銀玲,牛小梅.蟻群算法在移動機器人路徑規(guī)劃中的仿真研究[J].計算機仿真,2011(6):231-234.

[14] 楊獻峰,付俊輝.移動機器人路徑規(guī)劃的仿真研究[J].計算機仿真,2012(7):223-226.

[15] 黎竹娟.人工蜂群算法在移動機器人路徑規(guī)劃中的應用[J].計算機仿真,2012(12):247-250.

[16] 奚茂龍.群體智能算法及其在移動機器人路徑規(guī)劃與跟蹤控制中的研究[D].無錫:江南大學,2008.

[17] 樸松昊,洪炳熔.一種動態(tài)環(huán)境下移動機器人的路徑規(guī)劃方法[J].機器人,2003(1):18-21,43.

[18] 劉國棟,謝宏斌,李春光. 動態(tài)環(huán)境中基于遺傳算法的移動機器人路徑規(guī)劃的方法[J].機器人,2003(4): 327-330,343.

[19] 呂冬梅.足球機器人路徑規(guī)劃算法的研究及其仿真[D].青島:青島科技大學,2006.

[20] 余炎峰.基于免疫遺傳算法的移動機器人全局路徑規(guī)劃[D].合肥:合肥工業(yè)大學,2007.

[21] 王志文,郭戈.一種新的移動機器人路徑跟蹤控制策略[J].蘭州理工大學學報,2006(4):90-92.

[22] 牛雪梅,高國琴,鮑智達,等.基于滑模變結構控制的溫室噴藥移動機器人路徑跟蹤[J].農業(yè)工程學報,2013(2):9-16.

[23] 楊星.改進的免疫遺傳算法與人工神經網絡在多機器人系統(tǒng)圍捕問題的應用[D].長沙：中南大學,2007.

[24] 楊黎明.一種改進的免疫遺傳算法及在PID控制器優(yōu)化設計中的應用[D].長沙：中南大學,2007.

[25] 王曙霞,涂俊英,鄭艷君.基于Elitism策略的改進免疫遺傳算法求解TSP問題[J].電腦知識與技術,2010(1):193-195.

[26] 黃超.模塊化移動機器人控制系統(tǒng)及運動算法的研究[D].哈爾濱:哈爾濱工業(yè)大學,2010.

Path Optimization and Trajectory Tracking of Agricultural Robot
——Based on Genetic Algorithm

Chen Shunli

(Chongqing Vocational Institute of Engineering, Chongqing 402260, China)

With the continuous improvement of the information-based level of our country, machinery automation, computer control system and test and measurement field and the development of the mobile robot has reached a new height, intelligent robots have been widely applied to agricultural production, industrial production and higher research in various fields. Many problems in robot research, path planning and trajectory tracking is more complicated and difficult to solve the problem. The based on genetic algorithm, according to the characteristics of mobile robot and motion characteristics by geometric method of robot work space environment model is established, and the path for the effective coding, for real-time robot planning a collision free, short routes for the global path, and the motion trajectory tracking. Simulation results show that in this paper, the design of robot global path planning and trajectory tracking technology of, with good effect, in the process of moving can be a timely and effective to avoid the obstacles ahead, its reliability, stability, application prospects very broad.

mobile robot; global path planning; trajectory tracking； genetic algorithm

2016-05-05

重慶市教委教改項目(142079)；重慶市社會科學基金項目(2014BS103)

陳順立(1973-)，男，河南西平人，副教授，碩士，(E-mail)csl73@sina.cn。

S126；TP242

A

1003-188X(2017)08-0017-05