周 苑

（上海交通大學 電子信息與電氣工程學院，上海200240）

一般而言，對于機械手臂的空間軌跡規(guī)劃可分為關節(jié)空間規(guī)劃和笛卡爾空間規(guī)劃兩種[1]。其中，關節(jié)空間規(guī)劃計算量小，且在關節(jié)空間的軌跡規(guī)劃中能滿足機器人運動學約束條件，從而能夠保證機器人運動平穩(wěn)，對機器人的沖擊?。坏芽柨臻g軌跡規(guī)劃則能更好地滿足運動精度的要求，能對機器人運行的軌跡做更精確地跟蹤，在很多需要提高軌跡精度的場合，如一些焊接機器人上，一般都采用笛卡爾空間軌跡規(guī)劃。

在空間軌跡規(guī)劃的研究中，文獻[2] 中利用三次多項式插值算法和防止加速度突變的三次樣條插值算法對四自由度教學機器人進行運動軌跡規(guī)劃，使得書寫的字體筆劃平滑、穩(wěn)定。文獻[3] 中則在保證工作精度的情況下，對機器人運動軌跡規(guī)劃做優(yōu)化調整，使機器人的運動軌跡時間最優(yōu)化。文獻[4] 中，在機器人B樣條運動軌跡插值中引入了遺傳算法控制每段樣條曲線插值的分段時間，大幅度地提高了機器人移動所需的時間。Kim等[5]基于機械手的動力學模型，在關節(jié)空間中設計了一種滿足力矩約束的最小時間路徑規(guī)劃方法。Shiller等[6]在綜合考慮了工作環(huán)境中障礙物的影響以及機械手關節(jié)運動的約束后，提出了一種機械手的最優(yōu)時間動作規(guī)劃算法。Gasparetto[7-8]也提出了2種以時間最優(yōu)的軌跡規(guī)劃方法。但上述算法都只針對了關節(jié)空間的軌跡規(guī)劃，且都只考慮時間最優(yōu)，不針對路徑精確度。

在笛卡爾空間曲線擬合的研究中，文獻[9] 中利用自適應算法滿足一定空間精度要求的最少節(jié)點有理B樣條曲線的擬合，并在葉片造型上應用，但算法損失了空間精度。文獻[10] 中利用退火算法結合節(jié)點最少的最優(yōu)化有理B樣條曲線擬合，迭代計算量大，遺傳最大代數(shù)達到500。文獻[11-12] 中提出平面曲線擬合中可能出現(xiàn)的精度問題以及一些解決的方案。

本文研究利用機器人進行漢字書寫。鑒于中國書法要求筆畫圓潤、精確，因此，要求機器人的關節(jié)空間規(guī)劃快速，同時，還要保證運行軌跡精確與平滑，故進行笛卡爾空間軌跡規(guī)劃尤為重要。本文針對笛卡爾空間軌跡規(guī)劃計算量大、算法復雜等缺點，設計一種改進的遺傳算法。該算法從初始種群中剔除不良基因，并對每次種群進行評估，利用MatLab中的遺傳工具箱運行程序。實驗結果表明，與傳統(tǒng)遺傳算法相比，本文方法不但避免了遺傳算法隨機性大、計算量大的特點，還提高了收斂速度。

1 Bezier曲線

Bezier曲線是1962年由法國雷諾公司的工程師Bezier提出的一種曲線逼近方法。四階三次Bezier曲線包含4個控制點和一個節(jié)點向量，曲線方程[13-14]為

式中，P0，P1，P2，P3為4個控制點。

本文采用4次Bezier曲線擬合隨機產(chǎn)生N個控制點，同時按照給定型值點的數(shù)目產(chǎn)生N-2個節(jié)點向量，用于分析誤差?？刂祈旤c的數(shù)量若無指定一般為4個，但也可以根據(jù)需要由用戶自定義；對于精度較高的場合可以適當調高控制頂點的數(shù)量來實現(xiàn)分段逼近。本文采用最小二乘法計算誤差，即逼近曲線的節(jié)點和用戶指定型值點之間的距離最小。由m個Bezier曲線節(jié)點坐標和實際跟蹤曲線的累積誤差產(chǎn)生的距離為

式中，P（ti）為實際跟蹤曲線節(jié)點坐標；Q（i）為Bezier曲線坐標。

由于遺傳算法隨機性較大，故規(guī)定Bezier曲線的起點、終點始終與用戶指定型值點的起點、終點相同，以減少遺傳算法的隨機性，這樣也能減少計算機的計算量，對后期的最優(yōu)收斂也有一定輔助作用。故有

式中，P（t0），P（tn）為實際逼近曲線起點坐標與終點坐標；Q（0）和Q（n）為Bezier曲線型值起點和終點。

實際計算中，在遺傳算法中加入跟隨誤差率變化的變異因子，即當判斷誤差小于一定誤差后，可以隨時調整遺傳算法中的變異率，甚至可以直接停止計算。雖然在計算的初期階段，變異率較高，誤差有所增大，但是在后期整體收斂階段改進效果明顯，收斂速度明顯加快。

2 改進的遺傳算法

2.1 遺傳個體的編碼

遺傳算法的編碼主要分成3類，本文選用二進制編碼方式。個體表述為默認4個控制點的x、y坐標和N-2個節(jié)點向量。個體編碼時，采用隨機方法產(chǎn)生4個Bezier曲線控制點，包括起點和終點，范圍為0～200。依據(jù)給定的路徑點數(shù)目產(chǎn)生N-2個節(jié)點向量，用于比較Bezier曲線上的點和實際需要追蹤的路徑點的誤差。N-2個節(jié)點向量是0～1之間的隨機小數(shù)，按遞增順序排列，但不包括邊界。依據(jù)上述設計，并編寫FieldD矩陣。

2.2 遺傳適應度函數(shù)

在遺傳算法中，適應度越大的個體被遺傳的可能就越大，故需要編寫適應度函數(shù)來計算每個個體的適應度。本文的適應度函數(shù)為

2.3 遺傳交叉因子與遺傳變異

與自然進化一樣，子女擁有父母的一部分染色體特征，集成父母的遺傳因子。本文采用多點交叉的方式，形成新的染色體。

雖然在下一代染色體中含有一部分的父母染色體，但是自然界中還存在一定數(shù)量小概率的基因突變，變異是一種隨機事件。本文中，當誤差比較大時，取變異率為1.5，這樣能變化出更多樣化的染色體；而當誤差小于一定數(shù)值后，變異率改為0.5，以更加精確地逼近目標值，使最終的數(shù)值更接近原曲線。

2.4 遺傳算法結束條件

當Bezier曲線形成的誤差小于指定誤差后，算法終止；當遺傳代數(shù)大于最大遺傳代數(shù)之后，算法還無法收斂，則自動終止，并返回當前種群中的最優(yōu)解。

2.5 遺傳算法改進

遺傳算法中存在大量的不確定因素，故在以往生成曲線頂點時，不考慮初始種群中本身具有的先天缺陷，如頂點圍成的多邊形本身不是凸多邊形而造成繪制的曲線具有尖點曲線、不平滑等。因此，在計算過程中，增加校驗環(huán)節(jié)，使初始種群中的數(shù)據(jù)都符合凸多邊形特性，這樣繪制出的Bezier曲線更加的平滑。

3 軌跡規(guī)劃算法具體步驟

（1）手動輸入N個型值比較點。算法隨機生成Bezier曲線控制點，且同時產(chǎn)生N個時間節(jié)點提供比較，時間節(jié)點為0～1的隨機數(shù)，按由大到小順序排列。

（2）按遺傳算法個體編碼產(chǎn)生初始種群，并校驗初始種群中先天不足的個體，補充符合標準的個體。計算初始種群的個體適應度，計算其中最優(yōu)秀的基因進行繼承重插。

（3）選擇適應度高的個體進行重組。計算種群中最優(yōu)解的誤差率，并按照誤差的大小選擇變異率。若種群中最優(yōu)個體誤差小于指定誤差，則變異率為0.5；若最優(yōu)個體誤差大于最大誤差，則變異率為1.5，再產(chǎn)生新的種群。

（4）返回（2），進行個體基因適應度計算，重新計算誤差度。判斷是否小于指定誤差。

（5）若種群中具有個體小于誤差，則遺傳計算終止，返回最優(yōu)個體；若計算無法收斂，則當遺傳代數(shù)大于最大遺傳代數(shù)后自動停止，最大遺傳代數(shù)為用戶指定，若無特殊指定，則默認最大遺傳代數(shù)為Gmax＝1 000。

（6）繪制Bezier曲線，按照t＝0.5s的時間間隔，利用Matlab對機器人進行示教點的仿真運行，觀察機器人的平面運行軌跡。

4 算法實驗

實驗計算機環(huán)境為Windows XP系統(tǒng)，CPU為Inter Core2，2GB內存。使用漢字筆畫中比較難實現(xiàn)的彎折筆畫字庫模型，利用MatLab 7.1軟件進行計算機字模分析。

實驗中，提取型值點（20，80；40，80；60，80；50，60；40，30；40，20；60，20；80，20），利用 MatLab的遺傳基因工具箱對改進后的遺傳算法和傳統(tǒng)遺傳算法進行仿真模擬。圖1所示為彎折筆畫字庫模型與仿真結果的比較。其中，圖1（a）為彎折筆畫模型，圖1（b）為利用改進后的遺傳算法在G＝30時得到的計算結果；圖1（c）為利用傳統(tǒng)遺傳算法在G＝30得到的計算結果。

利用改進后的遺傳算法，在算法初期就去除不必要的曲線的尖點，取默認4個控制點的Bezier曲線進行笛卡爾空間曲線逼近。計算出最優(yōu)的Bezier控制頂點為（20，80；85.249 0，86.813 2；8.603 1，25.809 3；80，20），最 優(yōu) 時 間 節(jié) 點 為（0.906 6，0.463 0，0.323 0，0.723 7，0.319 1，0.747 1）。由圖可見，計算結果收斂明顯，算法優(yōu)化效果顯著。

而利用傳統(tǒng)遺傳算法計算[10]不僅計算迭代次數(shù)增加，而且還導致Bezier曲線的尖點，由圖1（c）可見，計算結果收斂性差。

圖1 彎折筆畫字庫模型與仿真結果的比較Fig.1 Comparison of bending font model simulation results

5 結 語

本文針對笛卡爾空間軌跡計算量大、算法復雜等缺點，設計了一種改進的遺傳算法，分段跟蹤Bezier曲線的各部分，使機器人運行平衡，路經(jīng)圓滑平順。通過實驗測試表明，選用遺傳算法計算機器人路徑進行笛卡爾空間規(guī)劃不僅精度提高，計算過程也相對簡單，對于需要精確跟蹤軌跡的場合非常合適。但是遺傳算法本身隨機性比較大，導致每次計算的路徑結果都不相同，在需要重復路徑的場合還需要進行路徑存儲來節(jié)省更多的計算時間，減少不確定性。

[1] 蔡自興.機器人學[M] .2版.北京：清華大學出版社，2009.

[2] 馬曉花，孔慶忠，馬為民，等，四自由度寫字機器人軌跡規(guī)劃研究[J] .機械工程與自動化，2010（5）：161-163.

[3] 李東潔，邱江艷，尤 波.一種機器人軌跡規(guī)劃的優(yōu)化算法[J] .電機與控制學報，2009，13（1）：123-127.

[4] 陳 丹.基于遺傳算法的B樣條曲線優(yōu)化在機器人軌跡規(guī)劃中的應用[D] .武漢：武漢科技大學，2007：3-4.

[5] Kim B K，Shin K G.Minimum-time path planning for robot arms and their dynamics[J] .IEEE Transactions on Systems，Man，and Cybernetics，1985，15（2）：213-223.

[6] Dubowsky S，Blubaugh T D.Planning time-optimal robotic manipulator motions and work places for point-to-point tasks[J] .IEEE Transactions on Robotics and Automation，1989，5（3）：377-381.

[7] Gasparetto A，Zanotto V.A technique for timejerk optimal planning of robot trajectories[J] .Robotics Computer Integrated Manufacturing，2008，24（3）：415-426.

[8] Gasparetto A，Zanotto V.Optimal trajectory planning for industrial robots[J] .Advances in Engineering Software，2010，41（4）：548-556.

[9] 周紅梅，王燕銘，劉志剛，等.基于最少控制點的非均勻有理B樣條曲線擬合[J] .西安交通大學學報，2008，42（1）：73-77.

[10] 劉 彬，張仁津.基于退火遺傳算法的NURBS曲線逼近[J] .山東大學學報：工學版，2010，40（5），96-100.

[11] 張銀娟，王永科.遺傳算法在 NURBS曲線擬合精度的研究應用[J] .自動化儀表，2012，33（1）：9-11.

[12] 張聚梅，王洪倫.基于遺傳算法和模擬退火算法的B樣條曲線擬合[J] .計算機工程與科學，2011，33（3）：191-193.

[13] 王幼民，徐蔚鴻.機械臂關節(jié)空間Bezier曲線軌跡規(guī)劃[J] .安徽機電學院學報，2000，15（3）：59-64.

[14] 王幼民.機器人關節(jié)空間Bezier曲線軌跡優(yōu)化設計[J] .機械科學與技術，2001，20（3）：350-352.

[15] 王春武，劉春玲，姜文龍.基于VB 6.0的點陣字模信息提取方法[J] .計算機工程，2010，36（11）：283-284.