基于改進遺傳算法的時間最優軌跡規劃*

楊星濤 庫祥臣 趙歡樂 米 顯 馬東陽

(河南科技大學機電工程學院,河南 洛陽 471003)

當今工業機器人技術廣泛應用在焊接、碼垛、磨削拋光、裝配和噴涂等領域[1]。在優化操作時間、提高工業機器人自動化操作效率上，國內外學者對工業機器人時間最優軌跡規劃問題進行了大量的研究。在軌跡生成上，董甲甲等[2]采用改進的B樣條曲線生成軌跡，提高了機器人空間運動軌跡的平滑性；李俊等[3]采用4-3-4次樣條函數生成軌跡，降低了軌跡規劃中的計算量；總體來說，三次多項式插值、五次多項式插值、組合多項式插值、B樣條插值、PH樣條插值[4]等方法可以實現光滑連續的軌跡，但隨著插值軌跡的復雜度提高，軌跡規劃的計算量也在提高。在優化算法的設計上，Lin C S等[5]應用三次樣條插值生成關節軌跡，并開發優化插值時間間隔的數學算例，實現了機器人軌跡的時間最優；徐海黎等[6]提出一種新穎的罰函數排序方法，在時間最優軌跡規劃上獲得了更好的優化效率；鄧偉等[7]在遺傳算法中結合混沌優化算法，提高了算法的全局搜索能力；殷鳳健等[8]采用交叉、變異概率自適應的遺傳算法，提高了遺傳算法的收斂效率，但罰函數懲罰因子難以選取，需要多次嘗試。遞推法、模式搜索法可以快速計算理想結果，但容易陷入局部最優解，粒子群算法、遺傳算法及免疫算法等進化類算法可以獲得更好的全局最優解，但存在約束條件復雜，中間參數難以選取等問題。

基于以上分析，本文研究通過隨機排序方法改進遺傳算法在時間最優軌跡規劃上的應用，簡化遺傳算法中間參數的選取，提高遺傳算法的全局搜索和局部搜索的能力，進而優化工業機器人操作時間，提高工業自動化生產的效率。

1 最優軌跡規劃問題描述

1.1 作業的描述

根據機器人自動化加工過程中的操作工藝，可以將機器人在笛卡爾空間中的軌跡描述為一系列的關鍵點pi(i=1,2,…,n)之間的運動。如圖1所示，以測量作業為例，機器人攜帶測量工具從p1點出發，接近送料機構到達p2點，在p3點夾取工件，遠離送料機構到達p2點，接近物料箱到達p4點，在p5點將工件送入指定的物料箱，之后遠離物料箱，經過p4點回到p2點。可以把機器人測量的自動化作業看作是笛卡爾空間中機器人在關鍵點之間的自動化運動。通過優化關鍵點之間的時間間隔，可以實現多個關鍵點之間軌跡規劃時間間隔的最優化，進而提高自動化操作的效率。

1.2 軌跡生成

(1)

式中:aj、aj+1表示θj(t)在區間[tj,tj+1]上左右端點處加速度值，hj(j=1,2,…,n-1)表示[tj,tj+1]的時間間隔,同時hj=tj+1-tj。

(2)

對θj(t)一次求導，得

(3)

(4)

(5)

(6)

式(6)中:

因為需要足夠的自由度來求解約束問題，所以增加關于初末速度的邊界條件，根據已知軌跡初速度和末速度條件：

(7)

可以得到以q2和qn-1為參數，關于aj的兩個等式：

(8)

結合式(6)和式(8)可以看出，關鍵點處加速度值aj可以表示為關于hj和qj的為參數的方程組，如下所示：

Ha=d

(9)

式(9)中:

若已知關鍵點位置qj和關鍵點之間的時間間隔hj，可通過追趕法可以求解方程組(9)得到軌跡關鍵點加速度aj(j=1,2,3,…,n)，進而代入式(1)～(4)得到三次樣條曲線規劃的位移、速度、加速度和加加速度。

1.3 隨機排序

將自動化作業的總時間作為優化目標，由于各關鍵點之間位移已由自動化作業工藝的要求確定，測量時間的減少必然會導致關節速度、加速度及加加速度的增大。然而由于機器人硬件上的限制，關節速度、加速度和加加速度存在最大值，所以機器人自動化作業時間最優軌跡規劃的數學描述如式(10)所示。

(10)

式(10)中：x=[h1,h2,h3,…,hj,…,hn-1]表示各關鍵點之間的時間序列，vjmax、ajmax、jjmax分別表示機器人關節j的速度、加速度、加加速度最大值。

機器人時間最優軌跡規劃實際上是含有多個復雜約束的目標優化問題，通常以式(11)罰函數的形式處理約束條件，但罰函數的懲罰系數rg難以選取。

F(x)=H(x)+rgφ(gm(x);m=1,2,3)

(11)

式(11)中：x表示種群中的個體，F(x)表示種群適應度，H(x)表示種群的目標函數值，由式(10)計算，rg表示約束條件的懲罰系數，φ(gm(x);m=1,2,3)表示3個約束條件的約束函數值，由式(12)計算。

(12)

式(12)中：φ(gm(x))不妨簡記為φ(x)。

種群適應度值是進化算法中評價個體優劣的標準，本文評價種群適應度為避免懲罰系數rg的選取，根據種群目標函數值以及約束條件引用基于冒泡排序的隨機排序法[9]，在兩個個體適應度高低的評價中，引入概率參數Pf，滿足以下兩條規則：當兩個個體都滿足約束條件時，以個體目標函數值從小到大排序；存在一個個體不滿足約束條件時，以概率Pf判斷依據目標函數值從小到大排序或依據罰函數值從小到大排序。隨機排序的具體操作如圖2所示。

1.4 遺傳算法

隨機排序后的最優軌跡規劃問題可以通過進化策略、免疫算法、粒子群算法、遺傳算法等進化算法優化，本文以操作較為簡單的遺傳算法為例說明最優軌跡規

劃問題的優化過程。機器人時間最優軌跡規劃中應用遺傳算法的關鍵在于設計種群編碼方式、適應度函數和遺傳算子。

編碼方式，根據公式(10)最優軌跡規劃需要對一條關節軌跡中的時間間隔h=[h1,h2,…,hj,…,hn-1]T進行編碼，編碼采用長度為n-1的定長方式，設計種群的編碼方式為滿足均勻分布的浮點數編碼，即編碼的每一位hj都是區間[(qj+1-qj)/vjmax,A]上均勻分布的隨機數，其中A為一個足夠大的常數。

適應度函數，根據類冒泡隨機排序的結果確定適應度函數的大小。

選擇算子，模仿生物進化過程中優勝劣汰的法則，采用輪盤賭的方法，

交叉算子，采用算數交叉方式交叉，具體方式如式(13)所示。

x′=pcxi+(1-pc)xj

(13)

式(13)中：xi、xj為隨機選擇的父代個體，x′為交叉產生的新個體,pc為交叉概率。

其中:pcmax、pcmin為交叉最大概率和交叉最小概率，Fmax、Favg為種群最大適應度和種群平均適應度。

變異算子，采用非一致實值變異方式，具體方式如式(14)所示。

(14)

1.5 時間最優軌跡規劃的步驟

基于以上分析，基于改進遺傳算法的時間最優軌跡規劃步驟如下：

(1)根據測量工藝確定笛卡爾坐標系中測量關鍵點，通過機器人逆運動學將關鍵點映射到各個關節空間中，得到關節空間中的關鍵點位移值。

(2)根據關節關鍵點位移值和初始化種群中的時間間隔序列，進行三次樣條軌跡的插值計算，獲得軌跡速度、加速度及加加速度參數，進而計算目標函數值及罰函數值。

(3)結合目標函數值及罰函數值以隨機排序法對種群個體排序。

(4)對排序后的種群個體分配適應度。

(5)種群進行遺傳操作。

(6)判斷是否達到遺傳代數，如果是，進入步驟(7);否則，回到步驟(2)。

(7)將改進遺傳算法得到最優軌跡的各段時間間隔輸出，得到軌跡的位移、速度、加速度和加加速度曲線。

2 仿真模型的建立

如圖3所示，以某氣動量儀測量圓柱軸承滾子的自動化測量工藝路徑為例，該機械手需要完成抓取、測量、分類等動作，以機器人末端手爪相對于機器人基坐標的位置p=[x,y,z]T和姿態R表示機器人末端手爪的位姿T，其中姿態R使用RPY角方式表示。該目標路徑工作所需的關鍵點如表1所示。

表1 軸承圓柱滾子自動化測量工藝路徑過程

仿真模型采用Stanford Manipulator機器人，DH參數如表2所示，機器人各關節的約束如表3所示。根據自動化測量工藝路徑分析得到的各關鍵點相對于機器人坐標系的位姿，通過MATLAB中robot toolbox計算機器人逆運動學，得到機器人移動路線對應關節空間中的各關節關鍵路徑點角位移值如表4所示。結合謝菲爾德(Sheffield)遺傳算法工具箱完成遺傳算法優化過程。

表2 機器人DH參數

表3 機器人各關節的約束

表4 機器人移動路線關鍵點對應關節角度

3 仿真結果及分析

在關節路徑規劃中，一次處理機器人的1個關節，以仿真模型中的關節1為例，將關節1路徑關鍵點輸入改進遺傳算法優化模型，設置遺傳算法參數：種群規模為100、進化代數200代。遺傳算法計算收斂曲線函數運行優化過程，優化過程的收斂曲線如圖4所示，規劃軌跡在進化60代后得到最優解。

在三次樣條插值軌跡規劃中采用改進遺傳算法和采用模式搜索法[10]都可以得到滿足速度、加速度連續，加加速度滿足約束的各階段時間間隔，如圖5和圖6所示。但采用改進的遺傳算法得到的結果比模式搜索法整體縮短了36.93%的時間，兩種方法各階段具體優化時間間隔對比如表5所示，可以看出模式搜索法可以找到問題的可行解，但改進遺傳算法對全局最優解的搜索能力遠高于模式搜索法。

表5 優化路徑時間間隔對比

4 結語

(1)本文詳細闡述了三次多項式插值擬合關節空間中關鍵點的方法，說明了關節軌跡在關節關鍵點確定的條件下取決于各關節關鍵點加速度的理論依據，推導出了在邊界條件為初末速度時根據關鍵點之間時間間隔和關鍵點位移值計算關節軌跡的方法，建立了測量機器人時間最優軌跡規劃的數學模型。

(2)針對測量機器人時間最優軌跡規劃問題，通過提出一種隨機排序法改進遺傳算法。基于機器人自身的約束和機器人測量工藝確定的路徑關鍵點，建立仿真實驗模型，以斯坦福機器人關節1路徑關鍵點為例仿真得到的優化軌跡與采用模式搜索法相比優化得到的總時間縮短了36.93%，達到了良好的效果。其他關節仿真優化過程與結果與關節1類似，故不再贅述。