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

朱永強，鮑官軍

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

1 引言

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

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

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

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

2.1 七自由度冗余機械臂

以7自由度冗余機械臂為研究對象，其實物及D-H 坐標模型，如圖1所示。

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

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

2.2 問題描述及建模

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

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

（1）工作時間最短目標函數。將機械臂到達軌跡點θm的時間記為t0，t1，…，tM，則機械臂的工作時間函數為：

式中：f1—機械臂工作時間。

（2）能耗最少目標函數。根據前文所述，關節(jié)n在軌跡點θm對應的關節(jié)角為θmn，則機械臂的能耗為：

式中：f2—機械臂系統能耗；—第m個軌跡點對應的第n個關節(jié)角加速度。

（3）運動沖擊最小目標函數。機械臂的運動沖擊使用關節(jié)角運動的平均加加速度進行衡量，即：

式中：f3—機械臂的運動沖擊，—第m個軌跡點對應的第n個關節(jié)角加加速度。

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

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

2.3 軌跡插值函數

B樣條曲線具有局部支撐性和結構緊密性，當某段局部軌跡不滿足約束時只需對此局部軌跡進行改動，其他滿足約束的軌跡可不做改變，因此使用B樣條曲線作為軌跡插值函數。高于三階的B樣條曲線計算困難且計算量略大，因此在實際應用中使用較少。使用3次B樣條曲線作為軌跡插值函數。

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

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

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

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

3.1 傳統NSGA-II算法簡介

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

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

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

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

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

3.2 傳統NSGA-II算法缺陷分析

3.2.1 選擇策略缺陷分析。

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

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

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

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

3.2.2 模擬交叉二進制算子缺陷分析。

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

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

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

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

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

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

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

3.3.2 自適應SBX算子

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

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

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

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

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

（2）染色體變異方法。根據染色體編碼方式和具體問題的限制條件，對染色體使用單點隨機變異方法，即隨機選擇一個基因位，在其取值范圍內進行隨機變異。

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

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

（2）染色體按照隨機方法進行初始化；

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

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

（5）算法是否達到最大迭代次數，若否則轉至（3）；若是則輸出Pareto前沿解，算法結束。

4 仿真驗證

4.1 仿真實驗設置

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

表1 不同算法規(guī)劃結果統計Tab.1 Statistics of Planning Results of Different Algorithms

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

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

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

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

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

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

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

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

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

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

經計算和統計，圖5給定的耗時最少軌跡，其關節(jié)角度運動范圍、關節(jié)角速度、關節(jié)角加速度均滿足設定的約束條件，可以實際運行。且機械臂某些關節(jié)速度和加速度達到了約束最大值，說明約束空間得到了充分利用。

5 結論

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