機(jī)械臂關(guān)節(jié)空間軌跡的累積非支配賦值NSGA-II算法規(guī)劃

朱永強(qiáng)，鮑官軍

（1.義烏工商職業(yè)技術(shù)學(xué)院機(jī)電信息學(xué)院，浙江 義烏 322000；2.浙江工業(yè)大學(xué)機(jī)械工程學(xué)院，浙江 杭州 310014）

1 引言

機(jī)械臂可以代替人類進(jìn)行繁重及重復(fù)性高的工作，同時(shí)減少人身傷害，并提高生產(chǎn)效率和生產(chǎn)質(zhì)量，因此機(jī)械臂在工業(yè)生產(chǎn)中得到了越來越廣泛的應(yīng)用，比如裝配、焊接、碼垛等。機(jī)械臂運(yùn)動(dòng)軌跡規(guī)劃是控制技術(shù)的核心內(nèi)容之一，軌跡規(guī)劃的優(yōu)劣對(duì)機(jī)械臂的使用壽命和生產(chǎn)效率影響極大[1]。因此，研究機(jī)械臂軌跡規(guī)劃對(duì)提高其使用壽命和生產(chǎn)效率具有重要意義。

按照規(guī)劃空間的不同，可以將軌跡規(guī)劃分為關(guān)節(jié)空間軌跡規(guī)劃[2]和笛卡爾空間規(guī)劃[3]。關(guān)節(jié)空間的軌跡規(guī)劃是指將關(guān)節(jié)角表示為時(shí)間的函數(shù)，其優(yōu)點(diǎn)是便于設(shè)置控制量，缺點(diǎn)是難以對(duì)末端執(zhí)行器進(jìn)行精確控制。笛卡爾空間軌跡規(guī)劃是指將末端執(zhí)行器位姿表示為時(shí)間的函數(shù)，優(yōu)點(diǎn)是規(guī)劃效果直觀明了，缺點(diǎn)是運(yùn)算量、存在奇異性和機(jī)械自鎖問題。從優(yōu)化指標(biāo)的角度講，機(jī)械臂軌跡規(guī)劃可以分為時(shí)間最優(yōu)[4]、能量最優(yōu)[5]和沖擊最優(yōu)、多指標(biāo)優(yōu)化[6]等。文獻(xiàn)[7]針對(duì)多個(gè)機(jī)器人運(yùn)動(dòng)路徑規(guī)劃問題，自定了5個(gè)交叉變異算子用于改進(jìn)遺傳算法，規(guī)劃了連續(xù)空間中起止點(diǎn)之間的最優(yōu)路徑。文獻(xiàn)[8]將改進(jìn)的模擬退火算法應(yīng)用于七自由度機(jī)械臂的軌跡規(guī)劃，所規(guī)劃軌跡具有良好的運(yùn)行性能。文獻(xiàn)[9]以6自由度機(jī)械臂為研究對(duì)象，將B樣條曲線作為機(jī)械臂軌跡基元，使用自適應(yīng)慣性權(quán)重約束粒子群算法對(duì)軌跡參數(shù)進(jìn)行優(yōu)化，該方法得到了機(jī)械臂的時(shí)間最優(yōu)軌跡，同時(shí)克服了運(yùn)動(dòng)學(xué)奇異性問題。對(duì)于機(jī)械臂軌跡的規(guī)劃優(yōu)劣，不僅與軌跡基元關(guān)系較大，而且與優(yōu)化算法的求解能力關(guān)系較大，普遍適用性較強(qiáng)的軌跡規(guī)劃方法仍然是當(dāng)前階段的研究熱點(diǎn)。

研究了七自由度冗余機(jī)械臂的關(guān)節(jié)空間軌跡優(yōu)化問題，建立了關(guān)節(jié)空間軌跡的多目標(biāo)優(yōu)化模型，并將累積非支配賦值的染色體選擇法引入到NSGA-II算法中，提高了算法的優(yōu)化能力，達(dá)到了優(yōu)化機(jī)械臂關(guān)節(jié)空間軌跡的目的。

2 機(jī)械臂優(yōu)化模型

2.1 七自由度冗余機(jī)械臂

以7自由度冗余機(jī)械臂為研究對(duì)象，其實(shí)物及D-H 坐標(biāo)模型，如圖1所示。

圖1 七自由度冗余機(jī)械臂Fig.1 7 Degree of Freedom Manipulator

圖1（b）中坐標(biāo)系:x0y0z0—基座坐標(biāo)系；x1y1z1～x7y7z7—7 個(gè)轉(zhuǎn)動(dòng)關(guān)節(jié)坐標(biāo)系。為了防止圖片雜亂，圖中僅給出了各坐標(biāo)系的X軸和Z軸，Y軸根據(jù)右手定則確定。圖中：l0～l8—各連桿尺寸，l0=l8=70cm，l1=l2=l6=l7=43cm，l3=l5=208cm，l4=38.7cm。

2.2 問題描述及建模

研究的是七自由度冗余機(jī)械臂在關(guān)節(jié)空間的軌跡規(guī)劃問題。根據(jù)機(jī)械臂的關(guān)節(jié)活動(dòng)范圍、任務(wù)需求和障礙物分布設(shè)計(jì)其在笛卡爾空間必經(jīng)的軌跡點(diǎn)，記為P0，P1，P2，…，PM。其中P0為軌跡起點(diǎn)位姿，PM為軌跡終點(diǎn)位姿。

基于機(jī)械臂的逆運(yùn)動(dòng)學(xué)求解方法［10］，可以將笛卡爾空間的必經(jīng)軌跡點(diǎn)轉(zhuǎn)換為關(guān)節(jié)空間的軌跡點(diǎn)，記為θ0，θ1，θ2，…，θM。對(duì)于七自由度機(jī)械臂，每個(gè)關(guān)節(jié)空間軌跡點(diǎn)由七個(gè)關(guān)節(jié)角組成，記為θm=(θm1，θm2，…，θm7)，式中：m—軌跡點(diǎn)編號(hào)。使用插值法設(shè)計(jì)關(guān)節(jié)空間必經(jīng)軌跡點(diǎn)之間的軌跡，通過優(yōu)化機(jī)械臂到達(dá)各關(guān)節(jié)空間軌跡點(diǎn)的時(shí)間t0，t1，…，tM，使機(jī)械臂在滿足約束條件下規(guī)劃出設(shè)定意義下的最優(yōu)軌跡。優(yōu)化目標(biāo)包括工作時(shí)間最短、能耗最少和運(yùn)動(dòng)沖擊最小3個(gè)指標(biāo)。

（1）工作時(shí)間最短目標(biāo)函數(shù)。將機(jī)械臂到達(dá)軌跡點(diǎn)θm的時(shí)間記為t0，t1，…，tM，則機(jī)械臂的工作時(shí)間函數(shù)為：

式中：f1—機(jī)械臂工作時(shí)間。

（2）能耗最少目標(biāo)函數(shù)。根據(jù)前文所述，關(guān)節(jié)n在軌跡點(diǎn)θm對(duì)應(yīng)的關(guān)節(jié)角為θmn，則機(jī)械臂的能耗為：

式中：f2—機(jī)械臂系統(tǒng)能耗；—第m個(gè)軌跡點(diǎn)對(duì)應(yīng)的第n個(gè)關(guān)節(jié)角加速度。

（3）運(yùn)動(dòng)沖擊最小目標(biāo)函數(shù)。機(jī)械臂的運(yùn)動(dòng)沖擊使用關(guān)節(jié)角運(yùn)動(dòng)的平均加加速度進(jìn)行衡量，即：

式中：f3—機(jī)械臂的運(yùn)動(dòng)沖擊，—第m個(gè)軌跡點(diǎn)對(duì)應(yīng)的第n個(gè)關(guān)節(jié)角加加速度。

機(jī)械臂軌跡優(yōu)化的約束條件包括關(guān)節(jié)角運(yùn)動(dòng)范圍約束、關(guān)節(jié)角速度約束、關(guān)節(jié)角加速度約束等，即：

式中：θnmax、θnmin—關(guān)節(jié)n的最大和最小關(guān)節(jié)角；vnmax—關(guān)節(jié)n的最大關(guān)節(jié)角速度；anmax—關(guān)節(jié)n的最大關(guān)節(jié)角加速度。

2.3 軌跡插值函數(shù)

B樣條曲線具有局部支撐性和結(jié)構(gòu)緊密性，當(dāng)某段局部軌跡不滿足約束時(shí)只需對(duì)此局部軌跡進(jìn)行改動(dòng)，其他滿足約束的軌跡可不做改變，因此使用B樣條曲線作為軌跡插值函數(shù)。高于三階的B樣條曲線計(jì)算困難且計(jì)算量略大，因此在實(shí)際應(yīng)用中使用較少。使用3次B樣條曲線作為軌跡插值函數(shù)。

3次B樣條曲線及其基函數(shù)分別為［11］：

式中：u—（0，1）間參數(shù)，P(u)為3次B樣條曲線，di(i=0，1，2，3)-控制頂點(diǎn)；Ni3(u)—第i個(gè)3次樣條基函數(shù)。將基函數(shù)代入到定義式中，按照參數(shù)u的冪次合并同類項(xiàng)，得到3次B樣條曲線的多項(xiàng)式形式，為：

式（6）中的控制頂點(diǎn)di(i=0，1，2，3)由給定的軌跡點(diǎn)和邊界約束條件確定，從而得到具體的3次B樣條曲線表達(dá)式。

3 累積非支配賦值NSGA-II算法優(yōu)化

3.1 傳統(tǒng)NSGA-II算法簡(jiǎn)介

NSGA-II算法是在遺傳算法基礎(chǔ)上為適應(yīng)多目標(biāo)優(yōu)化而提出的，主要包括非支配排序、Pareto解集、擁擠度等重要內(nèi)容［12］，在此進(jìn)行簡(jiǎn)單介紹和說明，便于后文的算法原理分析。

（1）非支配排序。以N個(gè)目標(biāo)最小化問題為例進(jìn)行說明，優(yōu)化目標(biāo)函數(shù)記為fn，n=1，2，…N，若兩個(gè)染色體x1和x2滿足：對(duì)?n∈[1，N]，都有fn(x1)≤fn(x2)，則稱染色體x1支配x2，或者稱染色體x2被x1支配。

（2）Pareto解集。將整個(gè)染色體種群進(jìn)行非支配層排序，不被任何個(gè)體支配的染色體分配到第1非支配層，將第1非支配層的染色體刪除，剩余個(gè)體中不受支配的染色體分配到第2非支配層，重復(fù)刪除和排序的過程，直至所有個(gè)體的非支配層排序完畢，一般將第1非支配層個(gè)體稱為Pareto前沿解集。

（3）擁擠度計(jì)算方法。在傳統(tǒng)NSGA-II算法中，擁擠度是對(duì)同一非支配層的個(gè)體定義的。一般將同一非支配層兩端染色體的擁擠度定義為無窮大，其余染色體的擁擠度為：

式中：dk—染色體k的擁擠度。

3.2 傳統(tǒng)NSGA-II算法缺陷分析

3.2.1 選擇策略缺陷分析。

在傳統(tǒng)NSGA-II算法中，選擇包括兩個(gè)步驟，首先保留非支配層靠前的染色體，直到保留至某一支配層染色體總數(shù)超過設(shè)定規(guī)模為止，而后在最后選擇的非支配層中刪除擁擠度靠后的個(gè)體使染色體規(guī)模保持恒定。

傳統(tǒng)NSGA-II算法的選擇策略中，擁擠度的計(jì)算僅考慮了本非支配層染色體的距離，而沒有考慮染色體周圍個(gè)體的分布密集度，也就是說未考慮染色體被其他個(gè)體支配的程度，這顯然是不合理的。以圖2中的b、c、d三個(gè)個(gè)體為例進(jìn)行說明，假設(shè)圖中a、b、c、d、e為均勻分布。

圖2 染色體分布Fig.2 Distribution of Chromosomes

根據(jù)非支配層定義，圖中染色體I～VI的非支配排序?yàn)?，染色體a～e的非支配排序?yàn)?。根據(jù)擁擠度定義，染色體b、c、d的擁擠度相同，則被保留概率也相同。但是根據(jù)圖中矩形虛線圈出的個(gè)體數(shù)量可以看出，染色體d所屬范圍的密度明顯小于染色體c，也同樣小于染色體a。這意味著雖然其周圍染色體的密集度不同，雖然染色體被支配的程度不同，但是根據(jù)傳統(tǒng)定義卻具有相同的被選概率，這顯然是不合理的。

3.2.2 模擬交叉二進(jìn)制算子缺陷分析。

模擬二進(jìn)制交叉算子（Simulated Binary Crossover，SBX）可以使子代有選擇性地遺傳父代的優(yōu)秀基因，從而保證算法不斷向最優(yōu)解收斂。SBX算子的表達(dá)式為：

式中：g—迭代次數(shù)；Xs(g)—迭代g的染色體s；Xq(g)—迭代g的染色體q；λ—（0，1）間參數(shù)。式（8）中參數(shù)λ一般依據(jù)迭代次數(shù)進(jìn)行設(shè)置，但是隨著迭代進(jìn)行，染色體多樣性受到破壞，SBX算子的進(jìn)化能力極為有限，甚至停步不前。

3.3 累積非支配賦值NSGA-II算法

3.3.1 基于累積非支配賦值的選擇方法

針對(duì)3.2節(jié)中分析出的傳統(tǒng)NSGA-II算法在選擇策略中存在的缺陷，本節(jié)提出了累積非支配賦值方法。將染色體的累積非支配賦值定義為所有支配該染色體的個(gè)體排序值與該染色體自身排序值之和，即：

式中：r′(x，g)—染色體x迭代至g代的累積非支配賦值；r(x，g)—染色體x的非支配排序值；I—支配x的染色體數(shù)量；zxi—支配x第i個(gè)染色體；r(zxi，g)—染色體zxi的非支配排序值。

按照式（9）的定義，染色體b的非支配排序值為2，支配b的染色體為I、II、III、IV，則染色體b 的累積非支配賦值為6。同樣地，染色體c的累積非支配賦值為4，染色體d的累積非支配賦值為3，這意味著染色體d周圍的密集度低，也意味著能夠支配染色體d的個(gè)體更少，而能夠支配染色體b的個(gè)體更多，那么從染色體多樣性和特異性角度講，染色體d應(yīng)具有更大的選擇概率，通過以上定義，可以有效保留染色體多樣性和特殊性。

3.3.2 自適應(yīng)SBX算子

為了保持SBX 算子的進(jìn)化能力，本節(jié)提出了個(gè)體自適應(yīng)λ參數(shù)，其思想為：通過個(gè)體的累加非支配賦值構(gòu)造參數(shù)λ，使較優(yōu)的染色體能夠更大程度地遺傳給子代，方法為：

按照式（9）對(duì)累加非支配賦值的定義，個(gè)體越優(yōu)其累加非支配賦值越小。將式（10）代入到式（8）中，個(gè)體q越優(yōu)則λ越小，而(1-λ)越大，個(gè)體q越能夠?qū)⒆约旱膬?yōu)秀基因遺傳給子代。因此通過式（10）的構(gòu)造，可以使較優(yōu)個(gè)體得到更大程度遺傳。

3.4 基于累積非支配賦值NSGA-II算法的優(yōu)化方法

根據(jù)累積非支配賦值NSGA-II算法原理和機(jī)械臂關(guān)節(jié)空間軌跡優(yōu)化方法，對(duì)優(yōu)化中的具體問題進(jìn)行明確。

（1）染色體編碼。優(yōu)化對(duì)象為各軌跡時(shí)間點(diǎn)，則根據(jù)軌跡點(diǎn)數(shù)量設(shè)定染色體的基因位數(shù)。將染色體使用十進(jìn)制編碼，基因位數(shù)為M，則染色體編碼為(t0，t1，…，tM)。

（2）染色體變異方法。根據(jù)染色體編碼方式和具體問題的限制條件，對(duì)染色體使用單點(diǎn)隨機(jī)變異方法，即隨機(jī)選擇一個(gè)基因位，在其取值范圍內(nèi)進(jìn)行隨機(jī)變異。

基于累積非支配賦值NSGA-II算法的機(jī)械臂關(guān)節(jié)空間軌跡規(guī)劃步驟為：

（1）初始化算法參數(shù)，即染色體規(guī)模、交叉概率、變異概率、最大迭代次數(shù)；

（2）染色體按照隨機(jī)方法進(jìn)行初始化；

（3）染色體按照概率進(jìn)行交叉和變異操作；

（4）對(duì)染色體進(jìn)行非支配排序，計(jì)算各染色體的累積非支配賦值，依據(jù)非支配排序和累積非支配賦值選擇染色體；

（5）算法是否達(dá)到最大迭代次數(shù)，若否則轉(zhuǎn)至（3）；若是則輸出Pareto前沿解，算法結(jié)束。

4 仿真驗(yàn)證

4.1 仿真實(shí)驗(yàn)設(shè)置

給出圖1所示七自由度冗余機(jī)械臂關(guān)節(jié)運(yùn)動(dòng)約束條件，七個(gè)關(guān)節(jié)的運(yùn)動(dòng)能力完全一致，關(guān)節(jié)角的活動(dòng)范圍為[-120°，120°]，關(guān)節(jié)角速度的約束范圍為[-5°/s，5°/s]，關(guān)節(jié)角加速度的約束范圍為[-2°/s2，2°/s2]。根據(jù)任務(wù)需求、機(jī)械臂關(guān)節(jié)運(yùn)動(dòng)約束和障礙物分布情況，得到機(jī)械臂在關(guān)節(jié)空間必須經(jīng)過的軌跡點(diǎn)，如表1所示。

表1 不同算法規(guī)劃結(jié)果統(tǒng)計(jì)Tab.1 Statistics of Planning Results of Different Algorithms

4.2 優(yōu)化結(jié)果與分析

算法的參數(shù)設(shè)置為：染色體規(guī)模為250、交叉概率為0.3、變異概率為0.05、最大迭代次數(shù)為200。分別使用傳統(tǒng)NSGA-II算法和累積非支配賦值NSGA-II算法對(duì)4.1節(jié)的算例進(jìn)行優(yōu)化，得到的Pareto前沿解集，如圖3所示。

圖3 中實(shí)線為傳統(tǒng)NSGA-II 算法的優(yōu)化結(jié)果，虛線為累積非支配賦值NSGA-II算法的優(yōu)化結(jié)果。圖中A點(diǎn)為能耗和沖擊最大點(diǎn)，B 點(diǎn)為能耗和沖擊最小點(diǎn)。從Pareto 解集的三維空間分布看，沖擊與能耗成正比，這與沖擊會(huì)增加機(jī)械臂能耗的直觀理解相吻合。另外，沖擊與耗時(shí)成反比，能耗也與機(jī)械臂耗時(shí)成反比，說明一味地提高生產(chǎn)效率而減少生產(chǎn)時(shí)間，會(huì)較大地增加機(jī)械臂耗能。

圖3 優(yōu)化的Pareto解集Fig.3 Pareto Solutions after Optimization

考慮到3維空間難以直觀比較傳統(tǒng)NSGA-II算法與累積非支配賦值NSGA-II算法Pareto解的優(yōu)劣性，將其在時(shí)間-耗能兩個(gè)維度上進(jìn)行投影結(jié)果，如圖4所示。

圖4 Pareto解集的二維分布Fig.4 2-Dimension Distribution of Pareto Solutions

由圖4可以直觀看出，累積非支配賦值NSGA-II算法的Pa?reto解分布在傳統(tǒng)NSGA-II算法的Pareto解左下方，對(duì)于多目標(biāo)最小優(yōu)化問題來講，累積非支配賦值NSGA-II算法搜索的Pare?to 解集更優(yōu)。統(tǒng)計(jì)圖中A點(diǎn)和B點(diǎn)的能耗和耗時(shí)，對(duì)比結(jié)果，如表2所示。

表2 不同算法優(yōu)化結(jié)果對(duì)比Tab.2 Optimization Result Comparison of Different Algorithms

由表2中數(shù)據(jù)可以看出，對(duì)于耗時(shí)最少點(diǎn)（即A點(diǎn)），傳統(tǒng)NS?GA-II算法的運(yùn)動(dòng)時(shí)間為42.121s，能耗為4.167°/s2；改進(jìn)NSGAII算法的運(yùn)動(dòng)時(shí)間為40.112s，能耗為3.839°/s2，比傳統(tǒng)NSGA-II算法分別減少了4.77%和7.87%。對(duì)于能耗最少點(diǎn)（即B點(diǎn)），傳統(tǒng)NSGA-II 算法的運(yùn)動(dòng)時(shí)間為101.879s，能耗為0.876°/s2；改進(jìn)NSGA-II 算法的運(yùn)動(dòng)時(shí)間為99.994s，能耗為0.568°/s2，比傳統(tǒng)NSGA-II算法分別減少了1.87%和35.16%。結(jié)合上述數(shù)據(jù)和圖4可以看出，累積非支配賦值NSGA-II算法的搜索結(jié)果優(yōu)于傳統(tǒng)NSGA-II算法，這是因?yàn)樵诶鄯e非支配賦值NSGA-II算法中引入的累積非支配賦值排序法，充分考慮了染色體周圍個(gè)體的密集度及自身的特殊性，進(jìn)化過程中可以較好的保留染色體的多樣性，因此改進(jìn)NSGA-II算法的優(yōu)化結(jié)果優(yōu)于傳累積非支配賦值NS?GA-II算法統(tǒng)算法。以累積非支配賦值NSGA-II算法搜索的時(shí)間最少結(jié)果為例，給出7個(gè)機(jī)械臂的關(guān)節(jié)軌跡，如圖5所示。

圖5 耗時(shí)最少軌跡Fig.5 Trajectory of Minimizing Time-cost

經(jīng)計(jì)算和統(tǒng)計(jì)，圖5給定的耗時(shí)最少軌跡，其關(guān)節(jié)角度運(yùn)動(dòng)范圍、關(guān)節(jié)角速度、關(guān)節(jié)角加速度均滿足設(shè)定的約束條件，可以實(shí)際運(yùn)行。且機(jī)械臂某些關(guān)節(jié)速度和加速度達(dá)到了約束最大值，說明約束空間得到了充分利用。

5 結(jié)論

這里研究了七自由度冗余機(jī)械臂的關(guān)節(jié)空間多目標(biāo)優(yōu)化問題，建立了多目標(biāo)優(yōu)化模型，使用NSGA-II算法進(jìn)行了多目標(biāo)優(yōu)化，經(jīng)驗(yàn)證可以得出以下結(jié)論：（1）累積非支配賦值的選擇方法可以更好地保護(hù)染色體多樣性，從而提高算法的優(yōu)化能力；（2）基于累積非支配賦值NSGA-II算法優(yōu)化的軌跡滿足約束條件，且優(yōu)于傳統(tǒng)NSGA-II算法的優(yōu)化結(jié)果。