陳順立

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

?

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

陳順立

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

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

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

0 引言

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

1 遺傳算法概述

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

圖1 遺傳算法流程圖

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

在研究環(huán)境信息的過程中，主要有柵格法、拓?fù)浞ê蛶缀畏?種建模方法。在機(jī)器人路徑優(yōu)化和軌跡跟蹤的研究中，常常根據(jù)環(huán)境、機(jī)器人的運(yùn)動(dòng)方式及需要解決問題的具體特點(diǎn)來(lái)選擇建模方法。柵格法和拓?fù)浞ㄊ紫刃枰冉⒁粋€(gè)搜索圖，再根據(jù)路徑搜索方法求解路徑最優(yōu)解，過程較為復(fù)雜，靈活性低；而幾何法則是以幾何信息進(jìn)行環(huán)境建模，采用幾何法描述環(huán)境信息，直接可以求出路徑規(guī)劃的最優(yōu)解，表達(dá)直接、精確。因此，本文采用幾何法建立環(huán)境模型，搭建前需要對(duì)作業(yè)區(qū)域進(jìn)行幾種假設(shè)：

1)機(jī)器人在二維平面空間運(yùn)動(dòng)；

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

3)擴(kuò)大障礙物邊界，不考慮機(jī)器人自生形狀和大小，將其看作為一個(gè)質(zhì)點(diǎn)。

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

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

(1)

其中，(Xnj,Ynj)為障礙物的第nj個(gè)頂點(diǎn)坐標(biāo)，則

XOY={WSB,O1,…,Om}

(2)

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

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

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

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

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

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

圖3 個(gè)體路徑編碼簡(jiǎn)化

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

圖4 簡(jiǎn)化編碼格式

3 遺傳算法的適應(yīng)度函數(shù)

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

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

(3)

其中，i為路徑點(diǎn)序號(hào)；n為作業(yè)區(qū)域的障礙物總數(shù)；當(dāng)路徑點(diǎn)不經(jīng)過障礙物時(shí)，適應(yīng)度函數(shù)值為1，反之為0。

2)設(shè)移動(dòng)機(jī)器人某一段運(yùn)動(dòng)距離為didi+1,則與障礙物之間不相交的適應(yīng)度函數(shù)Fit(2) 為

(4)

結(jié)合式(2)和式(3)，躲避障礙物條件的適應(yīng)度函數(shù)為

Fi1t=Fit(1)×Fit(2)

(5)

3)最優(yōu)路徑以移動(dòng)距離最短為標(biāo)準(zhǔn)時(shí)，其適應(yīng)度函數(shù)表示為

(6)

其中，λ是一個(gè)可以根據(jù)仿真過程進(jìn)行調(diào)整且與精度相關(guān)的常數(shù)。

綜上所述，移動(dòng)機(jī)器人最終適應(yīng)度函數(shù)為

Fit=Fi1t×Fi2t

(7)

為了簡(jiǎn)化函數(shù)變量，式(7)將躲避障礙物和移動(dòng)距離最短兩個(gè)約束條件結(jié)合起來(lái)，計(jì)算方便，避免了不穩(wěn)定因素。

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

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

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

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

路徑轉(zhuǎn)折點(diǎn)為節(jié)點(diǎn)，可以用Pi=(xi,yi)來(lái)表示，那么抗體可以表示為

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

(Xn,Yn)}

(8)

其中，P1和P2分別表示為移動(dòng)機(jī)器人起點(diǎn)和終點(diǎn)。

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

P={y1,y2,…yn}

(9)

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

圖6 抗體編碼轉(zhuǎn)化為基因串形式

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

4.2 移動(dòng)機(jī)器人的軌跡跟蹤

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

圖7 移動(dòng)機(jī)器人位姿誤差

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

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

(8)

其中，θ為目標(biāo)方向角。

設(shè)定移動(dòng)機(jī)器人的位姿為

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

(9)

則機(jī)器人實(shí)際運(yùn)動(dòng)的速度為

q=(v,w)T

(10)

其中，v為移動(dòng)機(jī)器人的線速度；w為移動(dòng)機(jī)器人的角速度。

移動(dòng)機(jī)器人位姿誤差矢量表達(dá)式為

(11)

式(11)可以變換為

(12)

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

5 仿真實(shí)驗(yàn)

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

圖8 MATLAB仿真結(jié)果

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

6 結(jié)論

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

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

[1] 江斌.人工免疫算法的基礎(chǔ)研究及其應(yīng)用[D].長(zhǎng)沙:中南大學(xué),2008.

[2] 張穎.改進(jìn)的免疫遺傳算法在基于神經(jīng)網(wǎng)絡(luò)的多機(jī)器人協(xié)作搬運(yùn)中的應(yīng)用[D].長(zhǎng)沙:中南大學(xué),2008.

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

[4] 王評(píng).人工免疫算法研究及其在數(shù)據(jù)挖掘上的應(yīng)用[D].福州:福州大學(xué),2005.

[5] 劉傳領(lǐng).基于勢(shì)場(chǎng)法和遺傳算法的機(jī)器人路徑規(guī)劃技術(shù)研究[D].南京:南京理工大學(xué),2012.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[22] 牛雪梅,高國(guó)琴,鮑智達(dá),等.基于滑模變結(jié)構(gòu)控制的溫室噴藥移動(dòng)機(jī)器人路徑跟蹤[J].農(nóng)業(yè)工程學(xué)報(bào),2013(2):9-16.

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

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

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

[26] 黃超.模塊化移動(dòng)機(jī)器人控制系統(tǒng)及運(yùn)動(dòng)算法的研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),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

重慶市教委教改項(xiàng)目(142079)；重慶市社會(huì)科學(xué)基金項(xiàng)目(2014BS103)

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

S126；TP242

A

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