基于多親遺傳算法的B樣條軌跡規(guī)劃

黃 偉，鄭天江，寧學(xué)濤，陳 健，李夢群

（1.中北大學(xué) 機(jī)械與動力工程學(xué)院，太原 030051；2.中國科學(xué)院寧波材料技術(shù)與工程研究所 先進(jìn)制造技術(shù)研究所，寧波 315201）

0 引言

路徑規(guī)劃是指，根據(jù)環(huán)境要求,依據(jù)評價標(biāo)準(zhǔn)，指給定移動機(jī)械手的初始位姿及機(jī)械手末端的目標(biāo)位姿，找到一條行走過程中無碰撞路徑[1]。通常機(jī)器人路徑規(guī)劃又稱整體的運(yùn)動規(guī)劃，在進(jìn)行分析時，通常選取一個關(guān)鍵點(diǎn)，對機(jī)器人進(jìn)行簡化處理，自由度比較少，這樣路徑規(guī)劃問題相對比較簡單[2]。隨著機(jī)器人在各個領(lǐng)域應(yīng)用不斷增多，機(jī)器人行走的軌跡越發(fā)復(fù)雜，促進(jìn)了國內(nèi)外的學(xué)者關(guān)于機(jī)器人的運(yùn)動軌跡作出了深入研究，較常見的有單點(diǎn)搜索法、人工勢場法以及柵格法、最速下降法等，但是單點(diǎn)搜索法會陷入局部最優(yōu)的問題；人工勢場法會出現(xiàn)局部極小問題；柵格法經(jīng)常出現(xiàn)速度緩慢的問題；最速下降法在靠近的過程中走的是曲折路線，易產(chǎn)生鋸齒現(xiàn)象且速度緩慢。

前面優(yōu)化算法都是采用了單個初始值迭代求最優(yōu)解，運(yùn)算過程中容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，復(fù)蓋面大，利于全局擇優(yōu)。遺傳算法在很多領(lǐng)域都得到應(yīng)用，蘇小紅等研究了基于進(jìn)化穩(wěn)定策略的遺傳算法；謝宏斌劉國棟等基于遺傳算法的機(jī)器人動態(tài)路徑規(guī)劃的仿真，但是傳統(tǒng)遺傳算法存在著過早收斂或是收斂速度過慢的問題，為了避免過早收斂和早熟的問題本文提出多交遺傳算法用于機(jī)器人的軌跡規(guī)劃上面。

1 多親遺傳算法

多親遺傳算法在傳統(tǒng)算法的基礎(chǔ)上的一種改良，是通過改變交叉算子實(shí)現(xiàn)的，多親遺傳算法的流程圖如圖1所示。其主要作用使得對于適應(yīng)度高于群體平均適應(yīng)度的情況，逐漸增多；對于適應(yīng)度低于平均適應(yīng)度的情況，逐漸減小。多親算法表示為：

其中：C為個體編碼方法；E為適應(yīng)度評價函數(shù)；P0為初始群體；N為種群大??；φ為選擇算子；Γ為多親交叉算子；Ψ為變異算子；T為終止條件。

圖1 遺傳算法流程圖

2 單純交叉算子

MGA是對TGA的交叉算子的改進(jìn)算法即多親交叉，多親交叉常見有掃描交叉、斜對角交叉、種子交叉、群體中心交叉、單純交叉，本文選用單純交叉算子(SPX)的3個母體的遺傳算子。

在n維空間Rn內(nèi)，有n+1個相互獨(dú)立的點(diǎn)彼此形成一個單一的向量。方便起見，只考慮二維空間的三母體的單純交叉。其空間位置如圖所示，三個母體的向量為X(1)、X(2)、X(3)，這樣三個向量形成一個單純形成。我們分別沿著每個方向擴(kuò)展這些單純向量(1+) (>0)倍，O為三個母體的質(zhì)量中心，計(jì)算為：

然后，我們通過統(tǒng)一封裝從這一擴(kuò)大的單純向量產(chǎn)生三個后代。這樣我們從母體那里得到三個后代。

一般情況，單純交叉算法指定為 ，其中n為搜索空間的參數(shù)的數(shù)量；m為母體的數(shù)量； 為控制繁殖率的控制參數(shù)。圖中在單純交叉算法表示為。對于 我們定義一個更普遍的情況，m在[2,n+2]內(nèi)，讓X=(x1,…,xn)為一個n維實(shí)數(shù)向量作為一個可行解（染色體），在內(nèi)，m(≤n)不同于X(j)=(,…,)，是從母體中（總?cè)簕X1,…,Xn}）自由選擇的。

圖2 SPX-2-3-

我們把Rn由非重復(fù)的隨機(jī)n維坐標(biāo)轉(zhuǎn)換成 組Rm-1和一個Rq空間表示為：

在這里，h=integer(n/(m-1))、q=reminder(n/(m-1))。在每一個R-1里，我們用m個母體向量元素形成一個屬于Rn的單純交叉算子。我們通過裝從每一個Rm-1的單純向量統(tǒng)一封產(chǎn)生m個后代。最終，我們用向量元素值X(j)替換上一代向量元素值的會應(yīng)維數(shù)位置Rn，并且我們得到m后代向量 X'(j)=(, ...,),j=1 ,...,m 。在這里我們把q參數(shù)值給X'(j)且屬于Rq，即：

3 最優(yōu)時間規(guī)劃模型建立及多親算法的應(yīng)用

為提高生產(chǎn)效率，通過對機(jī)械手的時間軌跡優(yōu)化，來解決工作時間過長問題。時間長短，通常與關(guān)節(jié)速度、加速度、加加速度的的變化相關(guān)。因此再進(jìn)行優(yōu)化問題常常要求滿足關(guān)節(jié)的運(yùn)動約束為前提。

建立時間目標(biāo)函數(shù)的方法以及約束的方法，前人（文獻(xiàn)[3]～[5]）已經(jīng)給出了詳細(xì)的推算過程：

hi=ti-ti-1；

T：運(yùn)動總時間；

hi：每段時間，為設(shè)計(jì)變量；

m：關(guān)鍵總數(shù)；

ti：關(guān)鍵點(diǎn)對應(yīng)的時刻點(diǎn)。

3.1 最優(yōu)時間軌跡規(guī)劃的遺傳算法

將最優(yōu)時間算法中的約束條件轉(zhuǎn)化為遺傳算法中的罰函數(shù)得：

此時遺傳算法適應(yīng)度函數(shù)的表示為：

本文以三次元送料機(jī)械手為例，對三次元送料機(jī)械手的路徑的軌跡進(jìn)行規(guī)劃，送料機(jī)械手的軌跡如圖3所示，完成夾緊-提升-進(jìn)給-下降-松開-回退的動作。

表1 軌跡關(guān)鍵點(diǎn)

表2 初步的型值點(diǎn)

圖3 機(jī)械手運(yùn)動軌跡

3.2 計(jì)算結(jié)果

本文通過對MATLAB的算法重的交叉算子進(jìn)行修改，對送料機(jī)械手進(jìn)行軌跡優(yōu)化。為實(shí)現(xiàn)預(yù)想軌跡，需要進(jìn)行工作空間的軌跡關(guān)鍵點(diǎn)和規(guī)劃如表1所示，再通過運(yùn)動學(xué)逆解求得關(guān)節(jié)空間對應(yīng)的關(guān)節(jié)角度如表2所示。根據(jù)初始條件、邊界條件如表3所示，為優(yōu)化設(shè)定標(biāo)準(zhǔn)。本文通過MATLAB程序進(jìn)行運(yùn)算，結(jié)果如表4所示，得到得運(yùn)動曲線圖如圖4所示。

表3 約束條件

4 添加約束條件

采用多親遺傳算法進(jìn)行優(yōu)化得到優(yōu)化的時間結(jié)果如表4所示。

圖4 軌跡曲線圖

5 結(jié)論

本文通過B樣條曲線采用多親遺傳算法對機(jī)械手的軌跡進(jìn)行優(yōu)化，優(yōu)化目標(biāo)為時間最短。根據(jù)B樣條曲線可單獨(dú)處理每一段曲線的特點(diǎn)，把每個關(guān)節(jié)軌跡分成10段B樣條曲線，設(shè)定優(yōu)化精度為0.0001s，在滿足上文提到的速度、加速度、加加速度的約束條件下，完成一個運(yùn)動周期X、Y、Z方向的關(guān)節(jié)驅(qū)動器按照

表4 時間優(yōu)結(jié)果

10段B樣條曲線組成運(yùn)動軌跡需要的最優(yōu)時間分別為1.7213s，1.7042s，1.6808s，相對于原來預(yù)定的時間減少了0.1787s，0.1958s，0.2102s，完成了關(guān)于時間最小優(yōu)化。優(yōu)化后的時間滿足了一分鐘執(zhí)行35次送料。通過多親遺傳算法優(yōu)化了送料機(jī)械手的運(yùn)動時間，提高了機(jī)械手的移送效率，為送料機(jī)械手伺服電機(jī)選型提供了參考。

[1] 李新春,趙冬斌,易建強(qiáng),宋佐時.一種移動機(jī)械手分級協(xié)調(diào)路徑規(guī)劃方法[J].制造業(yè)自動化,2005,05:28-32.

[2] 馬雪英,何臻峰,林蘭芬.人工智能技術(shù)在機(jī)器人運(yùn)動規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究,2004,04:135-138.

[3] 李東潔,邱江艷,尤波.一種機(jī)器人軌跡規(guī)劃的優(yōu)化算法[J].電機(jī)與控制學(xué)報,2009,01:123-127.

[4] 王幼民,徐蔚鴻.機(jī)器人關(guān)節(jié)空間B樣條軌跡優(yōu)化設(shè)計(jì)[J].機(jī)電工程,2000,17(4):57-60.

[5] 王幼民,徐蔚鴻.機(jī)器人連續(xù)軌跡控制中的B樣條軌跡優(yōu)化設(shè)計(jì)[J].機(jī)械計(jì),2000,10(10):33-35.