基于動態(tài)輪廓誤差的微段速度規(guī)劃并行算法

方晨曦，張 輝，葉佩青，梁文勇

（1．清華大學 機械工程系，北京 100084；2．清華大學 精密超精密制造裝備及控制北京市重點實驗室，北京 100084；3．甘肅省數(shù)控機床工程技術研究中心，甘肅 天水 741024）

0 引言

如何使機床平穩(wěn)、快速、準確地執(zhí)行各種加工軌跡，一直是數(shù)控領域的研究重點。復雜曲面曲線的加工軌跡通常由計算機輔助制造（Computer Aided Manufacturing，CAM）系統(tǒng)生成的微小直線段組成，微段連續(xù)加工中的實際插補點不能恰好與線段端點重合，存在拐點問題［1］，國內(nèi)外學者針對該問題進行了大量研究［2－6］。但這些研究都以機床加速度與弓高誤差作為算法約束，沒有考慮動態(tài)誤差約束。建立符合實際的速度規(guī)劃約束條件是算法效果的決定性因素，一般文獻中通常簡化考慮幾何學與動力學約束，甚至不考慮動態(tài)系統(tǒng)約束，這種簡化模型既浪費進給性能，又無法保證加工的輪廓精度。文獻［7］也指出這種對約束的簡化處理存在缺陷，分析了參數(shù)曲線加工動態(tài)誤差，并將其作為約束條件，取得了軌跡精度的顯著提升。另一方面，單軸動態(tài)跟隨誤差并不能準確代表軌跡輪廓誤差，對于實時輪廓誤差估計在控制理論領域有大量研究［8－10］，本文將從數(shù)控速度規(guī)劃的角度對輪廓誤差約束條件進行研究。

除了解決局部拐點問題外，隨著軌跡曲率的不斷變化，也需要進行整體速度規(guī)劃［11－12］。軌跡整體速度規(guī)劃主要分為遍歷法與靜態(tài)規(guī)劃法，遍歷法因易保證計算實時性要求而得到廣泛應用。石川提出一種具有預讀（look－ahead）功能的速度規(guī)劃算法，通過劃分規(guī)劃單元和確定每個規(guī)劃單元的插補速度，根據(jù)軌跡的曲率特性實現(xiàn)自適應加減速控制［13］。Farouki將在機器人領域廣泛應用的相平面法移植于數(shù)控規(guī)劃領域［14－15］，對于兩軸平面運動需要計算速度限制曲線（Velocity Limited Curve，VLC），但對于三軸以上運動及復雜約束，則計算量會迅速增加。靜態(tài)規(guī)劃法直接將速度規(guī)劃問題作為一般非線性規(guī)劃問題求解［16］，因為難以估計計算量，所以對規(guī)劃軌跡長度有較大限制［17］。

傳統(tǒng)數(shù)控大多基于以各種“單核”、“少核”中央處理器（CPU）為核心的嵌入式平臺或PC平臺，其計算性能發(fā)展已接近瓶頸，當前采用大規(guī)模并行體系結構是解決這一性能瓶頸的有效途徑。在并行計算的背景下，圖形處理器（Graphics Processing，U－nit，GPU）作為一種成熟的多核芯片，其應用已經(jīng)逐漸從圖形專用領域轉為通用計算領域。由于消費級市場長期的競爭與發(fā)展，GPU目前在浮點數(shù)計算能力、數(shù)據(jù)帶寬等方面超出CPU數(shù)十倍。作為計算機的標準配置，GPU已經(jīng)在制造自動化領域得到大量實際應用［18］，但對于數(shù)控速度規(guī)劃尚無充分研究。并行計算在數(shù)控系統(tǒng)中的潛力尚未被充分挖掘，如何在計算機數(shù)控（Computer Numerical Control，CNC）系統(tǒng)中更好地利用GPU，使CNC系統(tǒng)擺脫CPU的計算瓶頸，是當前數(shù)控領域的研究方向。

本文建立了高速高精度加工場合下的速度規(guī)劃新模型，將進給軸簡化為二階動態(tài)系統(tǒng)，得到單軸跟隨誤差結合微段軌跡，提出了微段速度規(guī)劃動態(tài)輪廓誤差模型。隨后還提出一種基于統(tǒng)一計算設備架構（Compute Unified Device Achitecture，CUDA）框架的GPU并行算法，使用GPU作為數(shù)控系統(tǒng)中的速度規(guī)劃計算平臺。速度規(guī)劃遍歷方法包含前向遞推與后向回溯兩個過程，軌跡規(guī)劃過程前后相互依賴，給算法并行化帶來了難度，故引入速度規(guī)劃單元概念均勻劃分軌跡。曲線軌跡實驗表明，速度規(guī)劃中引入動態(tài)跟隨誤差模型能有效控制輪廓精度。以口腔修復體加工為例，通過海量數(shù)據(jù)進行并行計算，與串行算法效率對比，結果顯示并行算法比串行算法最高有50倍的加速比。

1 問題建模

1．1 軌跡局部速度約束

設微段軌跡由點P1P2…Pn組成，下面考慮在拐點Pi（1＜i＜n）處的局部速度約束（如圖1）。

設點Pi處的速度為vi，則vi首先應滿足指令速度約束條件：

式中vprog為指令速度。

轉接時進給速度的大小和方向發(fā)生變化將導致加減速的產(chǎn)生，由于電機功率有飽和極限，機械系統(tǒng)速度不能瞬間變化，即存在加速度約束。設線段Pi－1Pi和PiPi＋1的夾角為αi，系統(tǒng)插補周期為T，機床各軸加速度限制為Aj，max（j＝x，y，z），點Pi處的速度 變 化 矢 量 為 Δvi， 則 Δvi＝ ｜vi｜，記Δvi＝｜vi｜（Δx，Δy，Δz），可得加速度約束：

記vi，j為j 軸在i點的速度，即vi＝［vi，xvi，yvi，z］，vi方 向 與 Pi－1Pi相 同，即 vi＝｜vi｜·，可得vi的各軸分量。

軌跡連續(xù)加工時，在拐點處將單步轉接并形成弓高誤差earc。設弓高誤差上限為h，弓高誤差由插補階段確定，在速度規(guī)劃階段由式（3）進行最壞情況估計：

即

微段軌跡由CAM系統(tǒng)生成，線段長度已綜合考慮加工速度精度與數(shù)控系統(tǒng)插補周期，線段端點包含了這些速度與精度信息，因此數(shù)控系統(tǒng)一般禁止出現(xiàn)跨線段插補情況。設線段｜PiPi＋1｜＝Li，則插補周期約束為：

1．2 動態(tài)輪廓誤差約束

電機與進給系統(tǒng)作為動態(tài)系統(tǒng)，并不能隨輸入指令立即變化，各軸將產(chǎn)生跟隨誤差，各軸跟隨誤差合成產(chǎn)生的輪廓誤差將決定軌跡的實際精度。因此，動態(tài)輪廓誤差應作為速度規(guī)劃的重要約束。進給系統(tǒng)可簡化為如圖2所示的模型。

提高增益Kx和Ky可以提高各軸的響應速度，但增益過高會使系統(tǒng)不穩(wěn)定，產(chǎn)生振蕩。各軸的時間常數(shù)τx和τy一般由系統(tǒng)和速度環(huán)特性確定。對于本文所述速度規(guī)劃，可以認為這些參數(shù)已確定。包含這些動態(tài)參數(shù)的規(guī)劃已屬于最優(yōu)控制范疇，本文不進行討論。

以X軸為例，有瞬態(tài)誤差Ex對于系統(tǒng)輸入Xi的傳遞函數(shù)為

在線段內(nèi)梯形加減速規(guī)劃中，各軸輸入分為恒加速度加速段、勻速段、恒加速度減速段三種情況。設V（0）和A（0＋）為各段的初始條件，t＝0為各段的開始時刻，x（0）＝0為各段的開始位置坐標，各段時域下表示為：

取拉普拉斯變換，得

由拉式變換疊加原理可知，系統(tǒng)輸入為1和1 s2s3的線性組合，則系統(tǒng)輸出為1G（s）和1G（s）的線s2xs3x性組合。在數(shù)控系統(tǒng)應用中，為避免超調(diào)振蕩，將式（6）所代表的進給系統(tǒng)傳遞函數(shù)設置為過阻尼，則有

式中：

考慮勻速段vx（t）＝V（0），加速段vx（t）＝V（0）＋A（0）t，忽略瞬態(tài)響應部分，有

同理，y軸有

由于軌跡已知，通過單軸誤差可進一步求出輪廓誤差。圖3為微段軌跡通過拐點時刻的動態(tài)誤差示意圖為實際位置，有為跟隨誤差，ec1和ec2為相對于直線軌跡的輪廓誤差，則有

設

則

設輪廓誤差限制為Emax，引出輪廓誤差約束，有

1．3 軌跡整體約束

以式（1）、式（2）、式（4）、式（5）、式（18）為線段端點的局部速度限制，只需端點處的局部軌跡信息即可分別求出各端點的速度上限。但由于整條線段各軌跡端點間存在加減速過程，并不能保證各端點速度達到該值，從而引入新的曲線整體約束：

2 并行求解

2．1 劃分并行規(guī)劃單元

根據(jù)式（1）、式（2）、式（4）、式（5）、式（18）可并行獨立求出軌跡線段各個端點的局部速度最大值vl。設速度判據(jù)為vl，定義低速點Pj為局部速度最大值小于速度判據(jù)的點：

以低速點為依據(jù)劃分規(guī)劃單元。若將兩相鄰低速點間的軌跡劃分為一單元進行單元內(nèi)速度規(guī)劃，則由于低速點位置在整條軌跡中分布不均勻，難以保證線程間負載平衡，這將導致并行算法效率嚴重下降。為將軌跡較為均勻地劃分給各個并行執(zhí)行線程，設Ld為長度判據(jù)，將整條軌跡劃分為長度近似于Ld的包含若干線段的規(guī)劃單元。為使各個單元能獨立地進行速度規(guī)劃，規(guī)定如下參數(shù)約束：式中：Amax＝min｛Aj，max｝（j＝x，y，z），vprog為最大進給速度，均為系統(tǒng)輸入?yún)?shù)。圖4所示的陰影處為v2l與Ld的取值范圍。

假設兩低速點相距l(xiāng)。若0．5Ld＜l＜2Ld，則將此兩點間的軌跡劃為一規(guī)劃單元（單元類型A），兩低速端點的最終規(guī)劃速度即為其相應閾值。

命題1 若一規(guī)劃單元的兩端點為低速點，且相距0．5Ld＜l＜2Ld，則此兩點規(guī)劃速度能達到相應閾值，即不會出現(xiàn)從線段起點沿軌跡最大加（減）速也無法升（降）到終點速度的情況。

證明 假設低速點a為起點。如果其單元規(guī)劃速度低于該點的速度閾值（即該點速度的上確界），則設v′a為a點速度閾值，v＊a為a點規(guī)劃速度，即v＊a＜v′a，說明該點不是曲線速度限制來源，存在速度限制來源點c，使v＊c＝v′c，將a點規(guī)劃速度提升為v′a后會使c點的速度大于v′c。

由式（21）可知整條曲線不可能是最大降速曲線，因此c點不可能是另一減速點，即v′a＜v′c。

但因a點是起點且速度小于其他各點，設在它之前和它相鄰最近的滿足v′a＜v＊b的點為b，因為v′a＜v′c＝v＊c，所以b在c之前或b、c為同一點，又因為v＊a＜v′a＜v＊b，所以a到b間沒有減速線段且沒有速度受限制點，故將a點的規(guī)劃速度從v＊a提升為v′a后，不影響b點的規(guī)劃速度，因此也不會影響到c點的規(guī)劃速度。

矛盾，命題得證。

若兩低速點相距l(xiāng)（l≥2Ld），則將這兩點間的軌跡劃為［l/Ld］個單元（單元類型B）。先將各個單元端點的規(guī)劃速度設為閾值，作為之后單元內(nèi)速度規(guī)劃的初始條件。其中兩低速端點的最終規(guī)劃速度即為其相應閾值，證明與前處相似，不再贅述；其余規(guī)劃單元端點速度由之后單元內(nèi)的速度規(guī)劃最終確定。

若兩低速點相距過近或連續(xù)若干個低速點相距過近（l＜Ld/2），則將該段全部劃為1個規(guī)劃單元（單元類型C）。

整條軌跡被劃分為若干并行規(guī)劃單元，數(shù)控系統(tǒng)為每個規(guī)劃單元分配一個線程進行并行計算，每個線程內(nèi)執(zhí)行串行規(guī)劃算法，每個線程完成獨立計算后，經(jīng)過連接處理作為最終結果輸出。由上述單元劃分方法可知，除單元B與單元B連接外，其余規(guī)劃單元間連接時，兩個規(guī)劃單元分別計算的轉接點的規(guī)劃速度都等于該點的速度閾值，直接連接兩單元即可。

單元B與單元B連接時，前后兩個規(guī)劃單元在相交處的軌跡點的規(guī)劃速度結果不一定相等，取其中低值為該點的規(guī)劃速度，并重新規(guī)劃端點速度發(fā)生改變的單元。單元端點都為高速點時，其相互間沒有直接制約，其中一值減小后不影響另一高速點端點。

2．2 并行計算流程

使用NVIDIA公司設計的并行架構平臺CUDA編寫程序，在CUDA環(huán)境中，首先通過CUDA Runtime API將數(shù)據(jù)綁定到GPU全局存儲器（global memory），然后在 Device設定計算劃分Grid與Block規(guī)模，創(chuàng)建kernel函數(shù)，將基本相交計算映射到Device端多線程，最后將保存在Device端的測試結果寫回Host主存儲器。本文提出的數(shù)控微段連續(xù)速度規(guī)劃并行計算的算法流程如圖5所示。

步驟1 從編譯讀取軌跡序列寫入GPU，定義GPU數(shù)組，存儲軌跡點結果。

步驟2 調(diào)用GPU并行過程，并行計算各個軌跡點的局部速度最大值。

步驟3 同步至上一步并行過程結束。

步驟4 劃分規(guī)劃單元，定義GPU數(shù)組，存儲規(guī)劃單元結果。

步驟5 調(diào)用GPU并行過程，并行計算各個規(guī)劃單元的速度。

步驟6 同步至上一步并行過程結束。

步驟7 調(diào)用GPU并行過程，調(diào)整并連接各個規(guī)劃單元。

步驟8 向插補模塊輸出速度—軌跡序列。

3 算法實例

實驗計算平臺PC為CPU酷睿3．47GHz，顯卡Nvidia Geforce 450GTS，顯存1G。Nvidia Geforce 450GTS擁有192個計算核心。系統(tǒng)的軟件環(huán)境為 WindowsXP＋VISUAL studio 2008＋CUDA 4．0。數(shù)控系統(tǒng)采用自主研發(fā)的GT100型CNC，設定插補周期為1ms，指令速度為1 500 mm/min，各軸最大加速度為800mm/s2，最大弓高誤差20μm。

測試路徑如圖6所示，由平面參數(shù)樣條曲線按參數(shù)平均離散為200條微小直線段，整條軌跡曲率不斷變化，其中包含一個尖點，Y軸運動在此轉折。

取X和Y軸的增益Kx和Ky為40，時間常數(shù)τx和τy為100，圖7對比了各軸預測跟隨誤差結果與仿真實驗跟隨誤差結果，結果顯示兩者基本吻合，表明本文建立的單軸跟隨誤差模型能有效地預測各軸的實際跟隨情況。

圖8所示為最右端處軌跡的輪廓跟隨情況，圖8a為無輪廓誤差約束模型規(guī)劃實驗結果，其最大處輪廓誤差為44μm，圖8b為包含輪廓誤差約束模型所得規(guī)劃實驗結果，給定允許最大輪廓誤差為20 μm，實驗結果為21μm，仿真實驗結果表明：只有弓高誤差約束并不能保證實際輪廓精度，本文算法能有效控制輪廓誤差。

圖9顯示了本算法的速度規(guī)劃結果，可見各軸加減速過程速度平滑，加速度不超過設定閾值，顯然與逐段加工方法相比，本文的微段連續(xù)方法可以顯著減少加減速次數(shù)，提高加工平均速度。

本文對口腔修復體進行實際加工驗證（如圖10），加工程序線段總數(shù)為78萬，圖10a為加工CAD模型，加工設備為自主研發(fā)的口腔修復體專用加工設備（如圖10b），加工結果如圖10c所示。表1對本文算法實現(xiàn)的GPU代碼與CPU代碼運行時間進行了比較。結果顯示，隨著輸入線段數(shù)的增加，CPU的計算時間呈線性增長，而GPU則增長緩慢，當30 000條線段規(guī)模時，GPU并行算法已經(jīng)取得了50倍的加速比。

表1 口腔修復體加工不同算法對比

當輸入規(guī)模較小時，由于CUDA計算所需的數(shù)據(jù)傳送時間開銷和線程同步開銷，不能發(fā)揮并行計算的優(yōu)勢，隨著輸入規(guī)模的加大，實驗結果體現(xiàn)了大規(guī)模并行計算顯著的加速效果。表1同時顯示了相比同一軌跡逐直線段加工方法，本文的連續(xù)微段方法能帶來超過70%的效率提升。這一數(shù)據(jù)與指令速度和機床加減速能力相關，隨著速度與加速度設定閾值的提高，該值也相應增加。

圖11所示為被加工口腔修復體戴上牙模后的截面在電子顯微鏡下放大300倍后的圖像，測量結果顯示修復體（左邊銀色）頸緣線與牙模（右邊黃色）輪廓配合緊密，滿足臨床需求。本算法現(xiàn)已應用于臨床實際加工。

4 結束語

本文提出了基于輪廓誤差約束的速度規(guī)劃模型，實驗結果顯示這是保證加工輪廓精度的必要條件。接著提出了針對此模型的大規(guī)模并行計算體系的速度規(guī)劃算法，實驗結果表明本算法的加工速度連續(xù)平滑，相比逐段加工方法，加工效率有顯著提高，同時并行算法相比串行算法的計算效率成倍提高，能有效解決計算實時性問題。目前速度規(guī)劃與插補還是兩個獨立的模塊，這加大了規(guī)劃問題的最優(yōu)求解難度，今后將把速度規(guī)劃與插補統(tǒng)一考慮，探索運動控制在并行計算體系中的完整實現(xiàn)，挖掘并行計算體系在數(shù)控中更多的計算潛力。

［1］ YE P，SHI C，YANG K，et al．Interpolation of continuous micro line segment trajectories based on look－ahead algorithm in high－speed machining［J］．International Journal of Advanced Manufacturing Technology，2008，37（9/10）：881－897．

［2］ WANG Lin，CAO Jianfu．Look－ahead ＆adaptive speed optimization algorithm for high speed quipments［J］．Computer Integrated Manufacturing Systems，2010，16（5）：998－1005（in Chinese）．［汪 霖，曹建福．高速裝備前瞻自適應速度優(yōu)化算法［J］．計算機集成制造系統(tǒng)．2010，16（5）：998－1005．］

［3］ PESSOLES X，REDONNET J M，SEGONDS S，et al．Modelling and optimising the passage of tangency discontinuities in NC linear paths［J］．International Journal of Advanced Manufacturing Technology，2012，58（5/6/7/8）：631－642．

［4］ PESSOLES X，LANDON Y，RUBIO W．Kinematic modelling of a 3－axis NC machine tool in linear and circular interpolation［J］．International Journal of Advanced Manufacturing Technology，2010，47（5－8SI）：639－655．

［5］ ZHANG L X，SUN R Y，GAO X S，et al．High speed interpolation for micro－line trajectory and adaptive real－time look－ahead in CNC machining［J］．Science China Technology Sciences，2011，54（6）：1481－1495．

［6］ ZHANG Xiaohui，YU Dong，YANG Dongsheng，et al．Corner curve transition interpolation algorithm for high speed machining of micro－line segment［J］．Journal of Mechanical Engineering，2010，46（19）：183－191（in Chinese）．［張曉輝，于 東，楊東升，等．面向微線段高速加工的拐角曲線過渡插補算法［J］．機械工程學報，2010，46（19）：183－191．］

［7］ DONG J，STORI J A．Optimal feed－rate scheduling for high

speed contouring［J］．Journal of Manufacturing Science and

Engineering－Transactions of the Asme，2007，129（1）：63－76．

［8］ YEH S，HSU P．Estimation of the contouring error vector for the cross－coupled control design［J］．IEEE/ASME Transactions on Mechatronics，2002，7（1）：44－51．

［9］ CHENG M，LEE C．Motion controller design for contour－following tasks based on real－time contour error estimation［J］．IEEE Transactions on Industrial Electronics．2007，54（3）：1686－1695．

［10］ JIANGZHAO Y，ZEXIANG L．A novel contour error estimation for position loop－based cross－coupled control［J］．IEEE/ASME Transactions on Mechatronics，2011，16（4）：643－655．

［11］ HUANG Xin，LI Di，LI Fang，et al．Micro line blocks velocity planning based on bidirectional scan algorithm［J］．Computer Integrated Manufacturing Systems，2009，15（11）：2188－2192，2203（in Chinese）．［黃 昕，李 迪，李 方，等．基于雙向掃描算法的小線段速度規(guī)劃［J］．計算機集成制造系統(tǒng)，2009，15（11）：2188－2192，2203．］

［12］ LENG Hongbin，WU Yijie，PAN Xiaohong．Velocity planning algorithm for high speed machining of micro line blocks based on cubic polynomial model［J］．Computer Integrated Manufacturing Systems，2008，14（2）：336－340（in Chinese）．［冷洪濱，鄔義杰，潘曉弘．三次多項式型微段高速加工速度規(guī)劃算法研究［J］．計算機集成制造系統(tǒng)，2008，14（2）：336－340．］

［13］ SHI C A，YE P Q．The look－ahead function－based interpolation algorithm for continuous micro－line trajectories［J］．International Journal of Advanced Manufacturing Technology，2011，54（5/6/7/8）：649－668．

［14］ TIMAR S D，F(xiàn)AROUKI R T，SMITH T S，et al．Algorithms for time－optimal control of CNC machines along curved tool paths［J］．Robotics and Computer－Integrated Manufacturing，2005，21（1）：37－53．

［15］ TIMAR S D，F(xiàn)AROUKI R T．Time－optimal traversal of curved paths by Cartesian CNC machines under both constant and speed－dependent axis acceleration bounds［J］．Robotics and Computer－Integrated Manufacturing，2008，24（1）：16－31．

［16］ FAN W，GAO X S，YAN W，et al．Interpolation of parametric CNC machining path under confined jounce［J］．International Journal of Advanced Manufacturing Technology，2012，62（5/6/7/8）：719－739．

［17］ ZHANG Q，LI S R．Efficient computation of smooth minimum time trajectory for CNC machining［J］．International Journal of Advanced Manufacturing Technology，2013，68（1/2/3/4）：1－10．

［18］ BI Q Z，WANG Y H，DING H．A GPU－based algorithm for generating collision－free and orientation－smooth five－axis finishing tool paths of a ball－end cutter［J］．International Journal of Production Research，2010，48（4）：1105－1124．