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

黃 偉，鄭天江，寧學濤，陳 健，李夢群

（1.中北大學 機械與動力工程學院，太原 030051；2.中國科學院寧波材料技術與工程研究所 先進制造技術研究所，寧波 315201）

0 引言

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

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

1 多親遺傳算法

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

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

圖1 遺傳算法流程圖

2 單純交叉算子

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

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

然后，我們通過統一封裝從這一擴大的單純向量產生三個后代。這樣我們從母體那里得到三個后代。

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

圖2 SPX-2-3-

我們把Rn由非重復的隨機n維坐標轉換成 組Rm-1和一個Rq空間表示為：

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

3 最優時間規劃模型建立及多親算法的應用

為提高生產效率，通過對機械手的時間軌跡優化，來解決工作時間過長問題。時間長短，通常與關節速度、加速度、加加速度的的變化相關。因此再進行優化問題常常要求滿足關節的運動約束為前提。

建立時間目標函數的方法以及約束的方法，前人（文獻[3]～[5]）已經給出了詳細的推算過程：

hi=ti-ti-1；

T：運動總時間；

hi：每段時間，為設計變量；

m：關鍵總數；

ti：關鍵點對應的時刻點。

3.1 最優時間軌跡規劃的遺傳算法

將最優時間算法中的約束條件轉化為遺傳算法中的罰函數得：

此時遺傳算法適應度函數的表示為：

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

表1 軌跡關鍵點

表2 初步的型值點

圖3 機械手運動軌跡

3.2 計算結果

本文通過對MATLAB的算法重的交叉算子進行修改，對送料機械手進行軌跡優化。為實現預想軌跡，需要進行工作空間的軌跡關鍵點和規劃如表1所示，再通過運動學逆解求得關節空間對應的關節角度如表2所示。根據初始條件、邊界條件如表3所示，為優化設定標準。本文通過MATLAB程序進行運算，結果如表4所示，得到得運動曲線圖如圖4所示。

表3 約束條件

4 添加約束條件

采用多親遺傳算法進行優化得到優化的時間結果如表4所示。

圖4 軌跡曲線圖

5 結論

本文通過B樣條曲線采用多親遺傳算法對機械手的軌跡進行優化，優化目標為時間最短。根據B樣條曲線可單獨處理每一段曲線的特點，把每個關節軌跡分成10段B樣條曲線，設定優化精度為0.0001s，在滿足上文提到的速度、加速度、加加速度的約束條件下，完成一個運動周期X、Y、Z方向的關節驅動器按照

表4 時間優結果

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

[1] 李新春,趙冬斌,易建強,宋佐時.一種移動機械手分級協調路徑規劃方法[J].制造業自動化,2005,05:28-32.

[2] 馬雪英,何臻峰,林蘭芬.人工智能技術在機器人運動規劃中的應用[J].計算機應用研究,2004,04:135-138.

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

[4] 王幼民,徐蔚鴻.機器人關節空間B樣條軌跡優化設計[J].機電工程,2000,17(4):57-60.

[5] 王幼民,徐蔚鴻.機器人連續軌跡控制中的B樣條軌跡優化設計[J].機械計,2000,10(10):33-35.