基于改進(jìn)性遺傳算法的Bezier曲線笛卡爾空間軌跡規(guī)劃

周 苑

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

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

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

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

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

1 Bezier曲線

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

式中，P0，P1，P2，P3為4個(gè)控制點(diǎn)。

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

式中，P（ti）為實(shí)際跟蹤曲線節(jié)點(diǎn)坐標(biāo)；Q（i）為Bezier曲線坐標(biāo)。

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

式中，P（t0），P（tn）為實(shí)際逼近曲線起點(diǎn)坐標(biāo)與終點(diǎn)坐標(biāo)；Q（0）和Q（n）為Bezier曲線型值起點(diǎn)和終點(diǎn)。

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

2 改進(jìn)的遺傳算法

2.1 遺傳個(gè)體的編碼

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

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

在遺傳算法中，適應(yīng)度越大的個(gè)體被遺傳的可能就越大，故需要編寫(xiě)適應(yīng)度函數(shù)來(lái)計(jì)算每個(gè)個(gè)體的適應(yīng)度。本文的適應(yīng)度函數(shù)為

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

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

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

2.4 遺傳算法結(jié)束條件

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

2.5 遺傳算法改進(jìn)

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

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

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

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

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

（4）返回（2），進(jìn)行個(gè)體基因適應(yīng)度計(jì)算，重新計(jì)算誤差度。判斷是否小于指定誤差。

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

（6）繪制Bezier曲線，按照t＝0.5s的時(shí)間間隔，利用Matlab對(duì)機(jī)器人進(jìn)行示教點(diǎn)的仿真運(yùn)行，觀察機(jī)器人的平面運(yùn)行軌跡。

4 算法實(shí)驗(yàn)

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

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

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

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

圖1 彎折筆畫(huà)字庫(kù)模型與仿真結(jié)果的比較Fig.1 Comparison of bending font model simulation results

5 結(jié) 語(yǔ)

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

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

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

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

[4] 陳 丹.基于遺傳算法的B樣條曲線優(yōu)化在機(jī)器人軌跡規(guī)劃中的應(yīng)用[D] .武漢：武漢科技大學(xué)，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] 周紅梅，王燕銘，劉志剛，等.基于最少控制點(diǎn)的非均勻有理B樣條曲線擬合[J] .西安交通大學(xué)學(xué)報(bào)，2008，42（1）：73-77.

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

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

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

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

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

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