基于改進(jìn)遺傳算法的時(shí)間最優(yōu)軌跡規(guī)劃*

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

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

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

基于以上分析，本文研究通過隨機(jī)排序方法改進(jìn)遺傳算法在時(shí)間最優(yōu)軌跡規(guī)劃上的應(yīng)用，簡化遺傳算法中間參數(shù)的選取，提高遺傳算法的全局搜索和局部搜索的能力，進(jìn)而優(yōu)化工業(yè)機(jī)器人操作時(shí)間，提高工業(yè)自動(dòng)化生產(chǎn)的效率。

1 最優(yōu)軌跡規(guī)劃問題描述

1.1 作業(yè)的描述

根據(jù)機(jī)器人自動(dòng)化加工過程中的操作工藝，可以將機(jī)器人在笛卡爾空間中的軌跡描述為一系列的關(guān)鍵點(diǎn)pi(i=1,2,…,n)之間的運(yùn)動(dòng)。如圖1所示，以測量作業(yè)為例，機(jī)器人攜帶測量工具從p1點(diǎn)出發(fā)，接近送料機(jī)構(gòu)到達(dá)p2點(diǎn)，在p3點(diǎn)夾取工件，遠(yuǎn)離送料機(jī)構(gòu)到達(dá)p2點(diǎn)，接近物料箱到達(dá)p4點(diǎn)，在p5點(diǎn)將工件送入指定的物料箱，之后遠(yuǎn)離物料箱，經(jīng)過p4點(diǎn)回到p2點(diǎn)?？梢园褭C(jī)器人測量的自動(dòng)化作業(yè)看作是笛卡爾空間中機(jī)器人在關(guān)鍵點(diǎn)之間的自動(dòng)化運(yùn)動(dòng)。通過優(yōu)化關(guān)鍵點(diǎn)之間的時(shí)間間隔，可以實(shí)現(xiàn)多個(gè)關(guān)鍵點(diǎn)之間軌跡規(guī)劃時(shí)間間隔的最優(yōu)化，進(jìn)而提高自動(dòng)化操作的效率。

1.2 軌跡生成

(1)

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

(2)

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

(3)

(4)

(5)

(6)

式(6)中:

因?yàn)樾枰銐虻淖杂啥葋砬蠼饧s束問題，所以增加關(guān)于初末速度的邊界條件，根據(jù)已知軌跡初速度和末速度條件：

(7)

可以得到以q2和qn-1為參數(shù)，關(guān)于aj的兩個(gè)等式：

(8)

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

Ha=d

(9)

式(9)中:

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

1.3 隨機(jī)排序

將自動(dòng)化作業(yè)的總時(shí)間作為優(yōu)化目標(biāo)，由于各關(guān)鍵點(diǎn)之間位移已由自動(dòng)化作業(yè)工藝的要求確定，測量時(shí)間的減少必然會導(dǎo)致關(guān)節(jié)速度、加速度及加加速度的增大。然而由于機(jī)器人硬件上的限制，關(guān)節(jié)速度、加速度和加加速度存在最大值，所以機(jī)器人自動(dòng)化作業(yè)時(shí)間最優(yōu)軌跡規(guī)劃的數(shù)學(xué)描述如式(10)所示。

(10)

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

機(jī)器人時(shí)間最優(yōu)軌跡規(guī)劃實(shí)際上是含有多個(gè)復(fù)雜約束的目標(biāo)優(yōu)化問題，通常以式(11)罰函數(shù)的形式處理約束條件，但罰函數(shù)的懲罰系數(shù)rg難以選取。

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

(11)

式(11)中：x表示種群中的個(gè)體，F(xiàn)(x)表示種群適應(yīng)度，H(x)表示種群的目標(biāo)函數(shù)值，由式(10)計(jì)算，rg表示約束條件的懲罰系數(shù)，φ(gm(x);m=1,2,3)表示3個(gè)約束條件的約束函數(shù)值，由式(12)計(jì)算。

(12)

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

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

1.4 遺傳算法

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

劃問題的優(yōu)化過程。機(jī)器人時(shí)間最優(yōu)軌跡規(guī)劃中應(yīng)用遺傳算法的關(guān)鍵在于設(shè)計(jì)種群編碼方式、適應(yīng)度函數(shù)和遺傳算子。

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

適應(yīng)度函數(shù)，根據(jù)類冒泡隨機(jī)排序的結(jié)果確定適應(yīng)度函數(shù)的大小。

選擇算子，模仿生物進(jìn)化過程中優(yōu)勝劣汰的法則，采用輪盤賭的方法，

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

x′=pcxi+(1-pc)xj

(13)

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

其中:pcmax、pcmin為交叉最大概率和交叉最小概率，F(xiàn)max、Favg為種群最大適應(yīng)度和種群平均適應(yīng)度。

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

(14)

1.5 時(shí)間最優(yōu)軌跡規(guī)劃的步驟

基于以上分析，基于改進(jìn)遺傳算法的時(shí)間最優(yōu)軌跡規(guī)劃步驟如下：

(1)根據(jù)測量工藝確定笛卡爾坐標(biāo)系中測量關(guān)鍵點(diǎn)，通過機(jī)器人逆運(yùn)動(dòng)學(xué)將關(guān)鍵點(diǎn)映射到各個(gè)關(guān)節(jié)空間中，得到關(guān)節(jié)空間中的關(guān)鍵點(diǎn)位移值。

(2)根據(jù)關(guān)節(jié)關(guān)鍵點(diǎn)位移值和初始化種群中的時(shí)間間隔序列，進(jìn)行三次樣條軌跡的插值計(jì)算，獲得軌跡速度、加速度及加加速度參數(shù)，進(jìn)而計(jì)算目標(biāo)函數(shù)值及罰函數(shù)值。

(3)結(jié)合目標(biāo)函數(shù)值及罰函數(shù)值以隨機(jī)排序法對種群個(gè)體排序。

(4)對排序后的種群個(gè)體分配適應(yīng)度。

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

(6)判斷是否達(dá)到遺傳代數(shù)，如果是，進(jìn)入步驟(7);否則，回到步驟(2)。

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

2 仿真模型的建立

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

表1 軸承圓柱滾子自動(dòng)化測量工藝路徑過程

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

表2 機(jī)器人DH參數(shù)

表3 機(jī)器人各關(guān)節(jié)的約束

表4 機(jī)器人移動(dòng)路線關(guān)鍵點(diǎn)對應(yīng)關(guān)節(jié)角度

3 仿真結(jié)果及分析

在關(guān)節(jié)路徑規(guī)劃中，一次處理機(jī)器人的1個(gè)關(guān)節(jié)，以仿真模型中的關(guān)節(jié)1為例，將關(guān)節(jié)1路徑關(guān)鍵點(diǎn)輸入改進(jìn)遺傳算法優(yōu)化模型，設(shè)置遺傳算法參數(shù)：種群規(guī)模為100、進(jìn)化代數(shù)200代。遺傳算法計(jì)算收斂曲線函數(shù)運(yùn)行優(yōu)化過程，優(yōu)化過程的收斂曲線如圖4所示，規(guī)劃軌跡在進(jìn)化60代后得到最優(yōu)解。

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

表5 優(yōu)化路徑時(shí)間間隔對比

4 結(jié)語

(1)本文詳細(xì)闡述了三次多項(xiàng)式插值擬合關(guān)節(jié)空間中關(guān)鍵點(diǎn)的方法，說明了關(guān)節(jié)軌跡在關(guān)節(jié)關(guān)鍵點(diǎn)確定的條件下取決于各關(guān)節(jié)關(guān)鍵點(diǎn)加速度的理論依據(jù)，推導(dǎo)出了在邊界條件為初末速度時(shí)根據(jù)關(guān)鍵點(diǎn)之間時(shí)間間隔和關(guān)鍵點(diǎn)位移值計(jì)算關(guān)節(jié)軌跡的方法，建立了測量機(jī)器人時(shí)間最優(yōu)軌跡規(guī)劃的數(shù)學(xué)模型。

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