遺傳禁忌搜索算法在工業(yè)機器人結(jié)構(gòu)參數(shù)辨識上的應(yīng)用*

熊　杰，楊東升，王允森

(1.中國科學院大學，北京　100049；2.中國科學院 沈陽計算技術(shù)研究所，沈陽　110168)

?

遺傳禁忌搜索算法在工業(yè)機器人結(jié)構(gòu)參數(shù)辨識上的應(yīng)用*

熊杰1,2，楊東升2，王允森1,2

(1.中國科學院大學，北京100049；2.中國科學院 沈陽計算技術(shù)研究所，沈陽110168)

摘要：針對工業(yè)機器人標定過程中的結(jié)構(gòu)參數(shù)辨識方程形式復雜、計算繁瑣等問題，提出一種采用遺傳禁忌搜索算法來尋求辨識方程的最優(yōu)解的方法。首先采用遺傳算法做全局搜索，為加快收斂速度，遺傳算法的選擇算子、交叉算子和變異算子的參數(shù)按照動態(tài)適應(yīng)的方式進行。遺傳算法調(diào)用結(jié)束后，將種群的最優(yōu)個體作為禁忌搜索的初始解，調(diào)用禁忌搜索算法做進一步局部搜索。為了提高解的精確性，鄰域半徑根據(jù)適應(yīng)度值進行動態(tài)調(diào)整。仿真實驗結(jié)果表明遺傳禁忌搜索算法能夠有效的得到結(jié)構(gòu)參數(shù)的完全辨識。

關(guān)鍵詞：工業(yè)機器人；參數(shù)辨識；遺傳算法；禁忌搜索

0引言

機器人重復定位精度很高，但絕對定位精度一般較差，這是因為制造誤差、關(guān)節(jié)磨損、環(huán)境條件等因素導致機器人實際結(jié)構(gòu)參數(shù)和理論結(jié)構(gòu)參數(shù)不一致的原因造成，一般采用標定技術(shù)提高絕對精度。機器人標定包含運動學建模，位姿測量，參數(shù)辨識，誤差補償四個過程。通常參數(shù)辨識是求解一組非線性方程的過程[1]，直接求解十分復雜甚至是低效的。傳統(tǒng)的方法[2-5]等只考慮末端的位置信息，按照測量點的位置約束建立起一組線性方程組，簡化了求解過程，但是這種方法建立的方程組部分列是線性相關(guān)的，并不能做到結(jié)構(gòu)參數(shù)的完全辨識。

隨著激光跟蹤技術(shù)的發(fā)展，機器人末端位姿的測量變得相對容易，因此可以利用位置和姿態(tài)信息進行結(jié)構(gòu)參數(shù)的完全辨識。由于辨識方程的復雜性，很多學者嘗試以智能算法[6-8]求解，取得了一定的效果。遺傳算法(GA)[9]作為一種性能優(yōu)異的全局優(yōu)化算法。該算法通過對父代種群進行選擇，交叉，變異等操作，按照優(yōu)勝劣汰，適者生存的進化規(guī)則，不斷得到更優(yōu)的群體。該算法具有固有的并行性，搜索效率高，但是也存在著易于早熟，爬山能力弱，局部搜索能力差等缺點。禁忌搜索(TS)[10-11]是一種擴展了的局部搜索技術(shù)，通過引入一個禁忌表和相應(yīng)的禁忌準則來避免重復搜索，并通過特赦準則以赦免部分被禁忌的優(yōu)良解，在搜索過程中，可以接受劣質(zhì)解，從而可以跳出局部最優(yōu)。但是禁忌搜索是串行的，對初始解有較強的依賴性，而且搜索效率低。

本文結(jié)合GA和TS的特點，在對機器人運動學建模之后，將結(jié)構(gòu)參數(shù)辨識的過程分為兩個階段，先采用GA做全局搜索，得到全局概要解，作為TS的初始解，然后采用TS做局部搜索，進一步改善所得解。仿真表明，該方法可以有效的得到結(jié)構(gòu)參數(shù)的完全辨識。

1運動學建模

目前應(yīng)用最廣泛的機器人運動學模型是DH模型，根據(jù)DH模型所建立的相鄰關(guān)節(jié)之間的齊次變換矩陣為：

Ai=Rotz(θi)Tranz(di)Tranx(ai)Rotx(αi)

(1)

其中θi表示關(guān)節(jié)旋轉(zhuǎn)，di為連桿長度，ai為關(guān)節(jié)偏移，αi為連桿扭轉(zhuǎn)，i=1…N，N為關(guān)節(jié)連桿的個數(shù)。當相鄰關(guān)節(jié)平行或近似平行時，軸線的微小的偏移會引起連桿距離di的極大變化，此時通常使用Hayati所提出的MDH模型[12]。MDH模型在Ai中添加了繞Y軸旋轉(zhuǎn)的扭角βi，即：

Ai=Rotz(θi)Tranz(di)Tranx(ai)Rotx(αi)Roty(βi)

(2)

當相鄰連桿平行或近似平行時，di=0；否則，βi=0。確定了各關(guān)節(jié)之間的變換矩陣之后，那么按照機器人正運動學模型，其末端位姿可以表示為：

(3)

其中，θ=(θ1,…θN)，d,a,α,β同理，表示為結(jié)構(gòu)參數(shù)的向量。

由于裝配因素、負載因素、環(huán)境因素以及磨損變形等原因，各關(guān)節(jié)的實際參數(shù)和理論參數(shù)之間存在參數(shù)誤差[Δθi,Δdi,Δai,Δαi,Δβi],i=1…N，所以機器人的實際運動學模型可以修正為：

Tr=F(θ+Δθ,d+Δd,a+Δa,α+Δα,β+Δβ)

(4)

Tr表示末端的實際位姿，T表示末端的理論位姿。注意到Tr,T都是4×4的方陣，為便于計算，將姿態(tài)部分采用rpy角形式描述，這時Tr,T可以轉(zhuǎn)化為6×1的向量，即[px,py,pz,r,p,y]′，將轉(zhuǎn)化后的Tr,T分別記為Pr,P。因為Δθ,Δd,Δa,Δα,Δβ值實際上都比較小，所以ΔP可以表示為:

ΔP=Pr-P=

(5)

表示成矩陣的結(jié)構(gòu)即為：

(6)

機器人運動學結(jié)構(gòu)參數(shù)辨識就是要求出Δx的值。Δx的求解需要計算J的逆，這一過程非常復雜且需要耗費大量的時間計算。本文將其視作多參數(shù)的優(yōu)化問題，采用遺傳禁忌搜索算法求解該問題的最優(yōu)解，從而得到實際結(jié)構(gòu)參數(shù)。

2遺傳禁忌搜索算法

2.1遺傳算法做全局搜索

遺傳算法是一種模擬生物在自然環(huán)境中的遺傳和進化行為而形成的具有全局搜索能力的仿生優(yōu)化算法。本文將各連桿參數(shù)的誤差值作為種群的個體，將進化得到的個體修正機械臂的運動學參數(shù)，然后更新運動學模型，取末端執(zhí)行器的實際位姿和更新后的運動學模型計算得到的理論位姿之間的差值作為適應(yīng)度函數(shù)。根據(jù)適應(yīng)度函數(shù)對個體進行選擇，交叉，變異操作，得到新一代個體。由于適應(yīng)度好的個體能夠以更大的概率保留下來，而適應(yīng)度差的個體逐漸被淘汰，從而使得種群得到進化。遺傳算法的初始化及相關(guān)算子設(shè)定如下。

個體編碼及初始種群：將[Δθi,Δdi,Δai,Δαi,Δβi],i=1…N作為種群的個體，采用實數(shù)編碼，按照結(jié)構(gòu)參數(shù)誤差經(jīng)驗值的三倍設(shè)置個體變量的上下界。隨機初始化種群。

適應(yīng)度函數(shù)：設(shè)觀測集中樣本數(shù)量為Ns，那么適應(yīng)度函數(shù)設(shè)為所有樣本的誤差距離之和：

(7)

選擇算子：將當前種群中適應(yīng)度高的個體按照一定的選擇壓差遺傳到下一代。選擇壓差設(shè)置的過大，會導致適應(yīng)度低的個體很快被淘汰，從而可能產(chǎn)生早熟現(xiàn)象。所以在進化的初期壓差應(yīng)該設(shè)置的較小，以保證多樣性；進化的后期壓差選擇大一些，以加快收斂?？梢圆捎萌缦聞討B(tài)的方式確定選擇壓差：

Press(i)=1+i/MAXGEN

(8)

i表示當前進化的代數(shù),MAXGEN表示最大代數(shù)。

交叉算子：在進化初期，希望交叉概率較大，能夠迅速對種群優(yōu)化；在進化后期，希望交叉概率較小，這樣能夠使得優(yōu)秀個體不被破壞。所以可以動態(tài)的設(shè)定交叉率:

Pc(i)=Pc(0)(1-i/MAXGEN)2

(9)

其中，Pc(0)表示預設(shè)的交叉率，通常取之間。

變異算子：在進化初期，應(yīng)該加大突變率，以提高優(yōu)良個體的產(chǎn)生，在進化后期，應(yīng)該減少突變量，防止好的基因丟失，所以可以動態(tài)設(shè)定變異率，

Pm(t)=Pm(0)-(Pm(0)-Pmin)·i/MAXGEN

(10)

其中，Pm(0)表示預設(shè)的變異率，Pmin表示變異率允許的最小值。

綜上，采用遺傳算法求解機器人結(jié)構(gòu)參數(shù)誤差的整體算法流程如圖1所示。

圖1　遺傳算法流程圖

圖1描述了GA的整體流程，但是由于遺傳算法的局部搜索能力較差，易早熟收斂，所以必須對終止種群的最優(yōu)個體進一步做局部搜索。這里采用禁忌搜索算法進一步求最優(yōu)解。

2.2禁忌搜索算法做局部搜索

禁忌搜索是一種啟發(fā)式迭代算法[11]，通過一種鄰域規(guī)則得到當前點的鄰域集，引入禁忌表的概念，避免對局部最優(yōu)解的重復搜索，并采用特赦規(guī)則移除對優(yōu)良個體的禁忌。在進一步求解運動學結(jié)構(gòu)參數(shù)的過程中，禁忌搜索相關(guān)的參數(shù)設(shè)定如下。

鄰域規(guī)則：在搜索初期，適應(yīng)度較差，此時鄰域半徑應(yīng)該選擇的大一些，這樣可以加快收斂，在搜索后期，適應(yīng)度較好，此時應(yīng)該減小鄰域半徑，以得到更加精確的解。采用超矩形環(huán)形成當前解的鄰域，其中，鄰域的大小與當前的適應(yīng)度大小動態(tài)調(diào)整。其定義如下：

(11)

其中r為鄰域半徑，F(xiàn)ieldR是個體變量的上下界的差向量。fitness是適應(yīng)度值，是鄰域半徑調(diào)節(jié)的參數(shù)。記x為當前解，這樣，鄰域的超矩陣環(huán)就可以定義為：

i=0,1…k-1,j=1,2…4N}

(12)

其中，Neighbour(x,i)表示x鄰域內(nèi)的第i個環(huán)，xj表示個體中的第j個變量，k表示鄰域中設(shè)置的矩陣環(huán)的數(shù)量。在每個環(huán)中隨機的選取一定數(shù)量的點，形成當前解的鄰域集。

終止規(guī)則：一般情況下可以設(shè)定一個最大迭代步數(shù)，或者在一個給定的迭代步數(shù)內(nèi)算法搜索到的最優(yōu)解沒有改進時，算法將終止計算。

采用禁忌搜索進一步求解機器人結(jié)構(gòu)參數(shù)誤差的算法流程如圖2所示。

圖2　禁忌搜索算法流程圖

3仿真

3.1機器人模型

在matlab中實現(xiàn)GTSA算法，仿真過程中所使用的機器人模型為MOTOMAN-MH6。該機器人為6R型，構(gòu)型如圖3所示，結(jié)構(gòu)參數(shù)取值如表1所示。

圖3　MOTOMAN-MH6運動學坐標系

從表1中可以看出，該機器人第2和3關(guān)節(jié)相互平行，所以運動學模型應(yīng)該采用MDH方法，在第二關(guān)節(jié)引入繞y的轉(zhuǎn)角β2，然后基于表1即可構(gòu)造出機器人的理論運動學模型。因為在實際環(huán)境中，機器人的實際結(jié)構(gòu)參數(shù)和理論參數(shù)之間總是存在一定的誤差，所以可以根據(jù)表2預設(shè)的結(jié)構(gòu)參數(shù)誤差建立機器人的實際運動學模型。采集70組理論位姿點和對應(yīng)的實際位姿點，選擇其中50組作為訓練集，20組作為測試集。訓練集作為GTSA算法的輸入，調(diào)用GTSA算法反解出結(jié)構(gòu)參數(shù)誤差。

表1　MOTOMAN-MH6運動學結(jié)構(gòu)參數(shù)

表2　預設(shè)的結(jié)構(gòu)參數(shù)誤差(d2表示β2)

3.2基于GA的全局搜索

MOTOMAN-MH6為6R型機器人，共24個結(jié)構(gòu)參數(shù)，則種群個體為1×24的行向量，隨機初始化種群，種群中個體數(shù)量取40。初始交叉率設(shè)為0.95，初始變異率設(shè)為0.2，最小變異率設(shè)為0.05，迭代300次后得到的結(jié)果如圖4所示。

圖4　種群最優(yōu)個體以及適應(yīng)度變化曲線圖

從圖4中可以得出，整體上，種群朝著適應(yīng)度值下降的方向進化，200代以后，最佳適應(yīng)度和平均適應(yīng)度已經(jīng)基本重合，這表明種群已經(jīng)出現(xiàn)早熟現(xiàn)象。GA得到的最優(yōu)解中，θ,α,β計算的較為準確，而d,a計算誤差較大，這是因為θ,α,β的誤差對末端位姿產(chǎn)生的影響更顯著。

3.3基于TS的局部搜索

將GA算法中得到的最優(yōu)解作為TS的初始解。鄰域半徑調(diào)節(jié)參數(shù)，超矩形環(huán)的個數(shù)k=4，在每個環(huán)中隨機選擇5個點，故一個點的鄰域集可以形成20個點。禁忌表大小設(shè)為40，禁忌長度設(shè)為36。迭代2500次，TS算法中適應(yīng)度值的變化曲線如圖5所示，以及得到的最優(yōu)解如表3所示。

圖5　TS算法最優(yōu)解以及適應(yīng)度變化曲線圖

關(guān)節(jié)θ(10-2rad)d(mm)a(mm)α(10-2rad)10.17321.94221.94400.175020.17540.1754-1.94920.17473-0.17361.48671.5205-0.173840.34881.94341.99920.349150.1746-1.5036-1.49920.17466-0.17470.98791.0043-0.1744

從圖5和表3中可以看出，在GA的基礎(chǔ)上，TS得到的最優(yōu)解能夠更加逼近真實解。將TS得到的最優(yōu)解修正機器人的運動學結(jié)構(gòu)參數(shù)，在測試集上計算實際位姿和修正后的理論位姿之間的歐式距離，修正前和修正后的對比圖如圖6所示。

圖6　修正結(jié)構(gòu)參數(shù)后計算的誤差距離與修正前的對比圖

由圖6可知，修正后，理論位姿和實際位姿之間的誤差減少到幾乎為0，說明GTSA得到的解是有效的。

4結(jié)論

本文針對機器人結(jié)構(gòu)參數(shù)辨識方程形式復雜，直接求解計算繁瑣的問題，提出采用遺傳禁忌搜索算法得到機器人的結(jié)構(gòu)參數(shù)誤差值。該算法無需求解逆運動學，可以處于離線狀態(tài)下進行，整體上簡化了辨識過程，仿真結(jié)果表明該算法是有效性的。當然，該算法也有一些不足之處，比如，辨識的結(jié)果精度依賴于測試集的選取。所以在實際實驗中，必須建立起足夠的測試數(shù)據(jù)，同時盡可能減少觀測噪聲，并且要注意使測試集均勻分布于機器人的整個工作空間。

[參考文獻]

[1] 王琨. 提高串聯(lián)機械臂運動精度的關(guān)鍵技術(shù)研究[D]. 合肥:中國科學技術(shù)大學, 2013.

[2] 劉振宇, 陳英林, 曲道奎, 等.機器人標定技術(shù)研究[J]. 機器人,2002,24(5):447-450.

[3] 童上高,李權(quán)峰,龔瀟,等. 碼垛機器人運動定位誤差補償[J]. 組合機床與自動化加工技術(shù),2012(5):65-69.

[4] 吳蒙蒙,許兆棠,吳海兵,等. 環(huán)境溫度影響下并聯(lián)機床的加工誤差解耦[J]. 組合機床與自動化加工技術(shù),2014(6):4-7.

[5] Zhang T, Du L, Dai X. Test of Robot Distance Error and Compensation of Kinematic Full Parameters[J].Advances in Mechanical Engineering,2014,2014:1-9.

[6] 丁度坤. 工業(yè)機器人智能運動控制方法的分析與研究[D].廣州:華南理工大學,2010.

[7] 汪霖,曹建福,韓崇昭. 基于粒子群優(yōu)化的機器人多傳感器自標定方法[J].機器人,2009,31(5):391-396.

[8] 周煒,廖文和,田威,等. 基于粒子群優(yōu)化神經(jīng)網(wǎng)絡(luò)的機器人精度補償方法研究[J].中國機械工程,2013,24(2):174-179.

[9] 邊霞,米良. 遺傳算法理論及其應(yīng)用研究進展[J]. 計算機應(yīng)用研究,2010,27(7):2425-2429,2434.

[10] 張曉菲,張火明. 基于連續(xù)函數(shù)優(yōu)化的禁忌搜索算法[J]. 中國計量學院學報,2010,21(3):251-256.

[11] 王明興. 連續(xù)禁忌搜索算法改進及應(yīng)用研究[D]. 杭州:浙江大學, 2005.

[12] Hayati R.Robot Arm Geometric Link Parameter Estimation[J]. Proceedings of The 22nd IEEE Conf. on Decision and Control, 1983,12: 1477-1483.

(編輯趙蓉)

Application of Genetic-Tabu Search Algorithm in Industrial Robot Structural Parameter Identification

XIONG Jie1,2，YANG Dong-sheng2，WANG Yun-sen1,2

(1.University of Chinese Academy of Sciences,Beijing 100049, China; 2.Shenyang Institute of Computing Technology, Chinese Academy of Sciences,Shenyang 110168, China)

Abstract：For structural parameter identification problems with industrial robot calibration, considering the identification equations tends to form complexes, tedious calculation, so a genetic-tabu search algorithm(GTSA) for the optimal solution of identification equation was proposed. Firstly, genetic algorithm(GA) was used to global search. To accelerate the convergence speed of GA, the selection operator, crossover operator, mutation operator parameters was deal with the dynamic adaptive way. After GA called, the best individual in the population would be treated as the initial solution to tabu-search(TS). Then TS was called for further local search. In order to improve the accuracy of the solution, the neighborhood radius dynamically adjusted based on the fitness value. Through simulation experiment, the results show that GTSA can effectively get the full identification of structural parameters.

Key words：industrial robot; parameter identification; genetic algorithm; tabu search

中圖分類號：TH166;TG659

文獻標識碼：A

作者簡介：熊杰(1990—)，男，河南南陽人，中科院大學碩士研究生，研究方向為機器人標定技術(shù)，(E-mail)xiongjiezk@163.com；楊東升(1965—)，男，中國科學院沈陽計算技術(shù)研究所研究員，博導，研究方向為數(shù)控系統(tǒng)，現(xiàn)場總線，機器人，(E-mail)dsyang@sict.ac.cn。

*基金項目：核高基專項(2012ZX01029-001-002)

收稿日期：2015-02-12；修回日期：2015-03-12

文章編號：1001-2265(2015)12-0004-04

DOI:10.13462/j.cnki.mmtamt.2015.12.002