陸彩滿，劉艷梨，古 亮，吳洪濤

（1.江蘇安全技術(shù)職業(yè)學(xué)院機(jī)械工程系，江蘇 徐州 221011；2.南京航空航天大學(xué)機(jī)電學(xué)院，江蘇 南京 210016；3.重慶理工大學(xué)電氣工程學(xué)院，重慶 400054）

1 引言

并聯(lián)機(jī)構(gòu)因其優(yōu)點多而受到越來越多的國內(nèi)外學(xué)者深入研究［1］，如控制精度高、本體剛度大、結(jié)構(gòu)承載能力強(qiáng)等優(yōu)點。并聯(lián)機(jī)構(gòu)工作空間是指并聯(lián)機(jī)構(gòu)操作平臺執(zhí)行末端參考點所能運動的區(qū)域［2］。并聯(lián)機(jī)構(gòu)路徑規(guī)劃、避障運動控制中都需要考慮工作空間，工作空間是一種評價機(jī)構(gòu)靈活性的重要性能指標(biāo)，也是機(jī)構(gòu)設(shè)計與優(yōu)化重要參考依據(jù)［3］。

目前并聯(lián)機(jī)構(gòu)工作空間分析方法主要有：幾何繪圖法、解析法、數(shù)值法［4］。其中，具有較好的通用性搜索方法是數(shù)值法。每種方法都有其適用范圍且方法分析特點不一，文獻(xiàn)［5］中是利用工作空間邊界弦無限逼近邊界形式，把將工作空間分析轉(zhuǎn)化為最優(yōu)化計算問題，巧妙的將工程問題轉(zhuǎn)換為簡單的優(yōu)化計算問題。文獻(xiàn)［6］提出一種離散式蒙特卡洛數(shù)值搜索法，通過將一個轉(zhuǎn)動自由度進(jìn)行離散化處理，同時結(jié)合子空間的并集和交集的思想，使得可達(dá)工作空間與靈活工作空間分析簡單化。最后以一種三平移一轉(zhuǎn)動空間并聯(lián)機(jī)構(gòu)為例分析以及驗證其效果。文獻(xiàn)［7］基于粒子群算法原理基礎(chǔ)上，提出一種改進(jìn)的粒子群搜索算法，將工作工作空間搜索轉(zhuǎn)化為目標(biāo)函數(shù)優(yōu)化問題，通過得到的一系列優(yōu)化結(jié)果，將這些點的集合映射到工作空間邊界上得到工作空間邊界。文獻(xiàn)［8］根據(jù)混沌映射原理實現(xiàn)工作空間快速搜索，同時以空間3T1R機(jī)構(gòu)為例，驗證其有效性、快速性。文獻(xiàn)［9］針對蒙特卡洛法求解工作空間效率不高問題，將蒙特卡洛法進(jìn)行改進(jìn)，利用傳統(tǒng)方法得到的工作空間，在此基礎(chǔ)上細(xì)分成若干個子工作空間，根據(jù)標(biāo)準(zhǔn)動態(tài)可調(diào)的正態(tài)分布實現(xiàn)任意精度的閥值計算。文獻(xiàn)［10］考慮到蒙特卡洛法中隨機(jī)點分布的不均勻性所產(chǎn)生誤差導(dǎo)致精度不夠的問題。將前面的到邊界點的小鄰域內(nèi)重新生成隨機(jī)點，有效的解決蒙特拉洛法的精度不足、分布不均勻問題。

受文獻(xiàn)［11］啟發(fā)，借鑒格子氣自動機(jī)算法模型，提出一種基于3D格子氣自動機(jī)并行動態(tài)粒子搜索算法，同時重點介紹此方法的搜索原理以及分析過程，并以兩個空間并聯(lián)機(jī)構(gòu)為例進(jìn)行驗證，根據(jù)實例仿真分析機(jī)構(gòu)可達(dá)工作空間與定姿態(tài)工作空間，驗證該算法的有效性，并分析了算法參數(shù)對算法搜索效率的影響。

2 理論基礎(chǔ)介紹

2.1 元胞自動機(jī)

元胞自動機(jī)（Cellular Automata）是一種通用、動態(tài)的計算機(jī)仿真數(shù)學(xué)模型，其應(yīng)用范圍十分廣泛，其應(yīng)用涉及社會與自然科學(xué)的各個領(lǐng)域［12］。物理定義為有限的空間和時間并且元胞狀態(tài)都是有限的離散的動力系統(tǒng)，所有元胞狀態(tài)每一時刻中根據(jù)設(shè)定的元胞規(guī)則不斷更新迭代。元胞自動機(jī)組成主要包括元胞、元胞空間、鄰居及規(guī)則等［13］。它們之間的關(guān)系可理解為是由一個元胞空間和定義于該空間的變換函數(shù)所組成。與一般動力學(xué)模型不同的是元胞自動機(jī)不需要嚴(yán)格的物理方程或函數(shù)構(gòu)成，只需要定義若干個轉(zhuǎn)換規(guī)則就能實現(xiàn)動力系統(tǒng)的演化，即使是簡單的規(guī)則也可以演化出復(fù)雜的結(jié)果是這個算法的一大亮點，而且還具有并行計算的特點。

2.2 3D格子氣自動機(jī)模型

格子氣動機(jī)是一種基于離散粒子運動論微觀模型的數(shù)值計算方法，屬于元胞自動機(jī)的一種，是元胞自動機(jī)在流體力學(xué)上的應(yīng)用，三維格子氣自動機(jī)模型常用于金屬材料腐蝕損傷演化、林火蔓延仿真、晶體生長仿真、微觀組織模擬等方面［14］。三維格子氣自動機(jī)模型鄰域類型根據(jù)由其鄰域半徑r分類，（1）r=1時，有6（上下左右前后）或者18、26 個運動方向（上下左右前后及其組合），（2）r=2時，有124個運動方向，以此類推，更大的鄰居類型將趨向于隨機(jī)矢量方向運動。以鄰域個數(shù)26為例，其運動方向有26個，沿著四周所有可能鄰域進(jìn)行運動。3D格子氣自動機(jī)離散速度模型，如圖1所示。箭頭所指方向為動態(tài)粒子運動方向，箭頭位置為動態(tài)粒子的運動位置。

圖1 3D格子氣自動機(jī)速度模型Fig.1 Velocity Model of 3D Lattice Gas Automata

3 算法提出

3.1 3D格子氣偏隨機(jī)模型動態(tài)演化搜索算法原理

受到格子氣動機(jī)模型理論啟發(fā)，假設(shè)在n×n×n的三維空間格子中，有m個粒子隨機(jī)分布在空間格子中，每個粒子有兩個基本屬性：運動方向和運動速度。（1）不同的隨機(jī)運動方向，運動方向數(shù)量按照鄰居類型不同進(jìn)行劃分。（2）運動速度，在每個更新步長內(nèi)的粒子在某一運動方向上從原格子位置移動到另外的格子空間的格子數(shù)目，格子數(shù)目可以是1，2，3 等，運動速度即是1，2，3等。格子氣動機(jī)具有不相容規(guī)則，即每個粒子同時只能占據(jù)一個格子空間。將3D元胞空間粒子點坐標(biāo)作為輸入，機(jī)構(gòu)工作空間約束函數(shù)作為映射函數(shù)，輸出符合機(jī)構(gòu)工作空間約束的點，即可得到機(jī)構(gòu)工作空間的數(shù)值模型。輸入可以在經(jīng)過壓縮，平移等操作函數(shù)使得更符合實際的機(jī)構(gòu)工作空間約束函數(shù)坐標(biāo)矩陣?？稍谶\動前后判斷滿足約束值的變化情況，若有變化，則判斷為邊界點，多次運動后，可得到邊界點的集合。若不需要邊界點，則直接判斷點滿不滿足約束即可。

3.2 3D格子氣偏隨機(jī)模型動態(tài)演化搜索法流程

根據(jù)以上算法原理，具體的實現(xiàn)步驟過程如下：

（1）設(shè)定空間大小nx×ny×nz，nx，ny和nz為大于零的整數(shù)，設(shè)定粒子數(shù)目m和隨機(jī)位置Pm（x，y，z），其中，x，y，z為整數(shù)位置的集合；設(shè)定映射到工作空間的映射規(guī)則，Pm（x，y，z）—f（x）→PPm（x，y，z），映射規(guī)則為平移和縮放等操作，使得PPm（x，y，z）適應(yīng)待搜索機(jī)構(gòu)的空間；設(shè)定粒子運動的速度；

（2）記錄粒子的位置和工作空間位置，進(jìn)入機(jī)構(gòu)的約束條件，判斷其是否滿足約束，滿足記為1，不滿足記為0，記為ys1（PPm，｛0，1｝）矩陣中；產(chǎn)生隨機(jī)步長數(shù)（1-nu）和方向數(shù)（1～26），分別賦予每個粒子的運動速度和方向。產(chǎn)生新的粒子位置Pm’（x，y，z），和工作空間的位置坐標(biāo)PPm’（x，y，z）；

（3）進(jìn)入機(jī)構(gòu)的約束條件，判斷其是否滿足約束，滿足記為1，不滿足記為0，記為ys2（PPm’，｛0，1｝）矩陣中；計算ys2-ys1的結(jié)果，記為ysj（PPm’，｛0，1，-1｝），若集合中有不為零的元素，則判斷為邊界，可視化邊界點和粒子點。

（4）重復(fù)（2）與（3），直至達(dá)到需要的運動時間和搜索效果時結(jié)束。其搜索流程圖，如圖2所示。

圖2 算法搜索流程圖Fig.2 Algorithm Search Flow Chart

4 算法仿真案例

4.1 算例1仿真分析

4.1.1 4PPaR機(jī)構(gòu)運動學(xué)逆解分析

為了驗證所提出的工作空間搜索方法的有效性，這里以Pi-Ri1(-4R-)//Ri2⊥Ri3，(i=1，2，3，4)并聯(lián)機(jī)構(gòu)為例，此結(jié)構(gòu)簡圖，如圖3所示。此機(jī)構(gòu)支鏈結(jié)構(gòu)多，此空間機(jī)構(gòu)具有三平移一轉(zhuǎn)動（3T1R）的運動特性。

圖3 機(jī)構(gòu)結(jié)構(gòu)簡圖Fig.3 Structure of Mechanism

在建立運動學(xué)方程前，分別建立動靜坐標(biāo)系{P-uvw}、{O-xyz}，以參數(shù)(d1，d2，d3，d4)作為獨立運動輸入?yún)?shù)，以參數(shù)(x，y，z，θ)作為運動輸出，運動學(xué)逆解是根據(jù)輸出(x，y，z，θ)，得到輸入(d1，d2，d3，d4)。運動學(xué)逆解方程建立過程如下：

（1）根據(jù)主動移動副的位置可用參數(shù)(d1，d2，d3，d4)表示，可得到移動副的坐標(biāo)P1=(0，d1，0)，P2=(d2，0，0)，P3=()，P4=()，PiRi1與靜平臺夾角為αi，因此，Ri1，(i=1，2，3，4)表示為：

（2）動平臺的位姿為(x，y，z，θ)，已知動平臺Ri3，(i=1，2，3，4)，在{P-uvw} 下表示為R13(0，0)、R23(r，-r)、R33(2r，0)、R43(r，r)，Ri3，(i=1，2，3，4)需要通過轉(zhuǎn)換矩陣轉(zhuǎn)換到靜坐標(biāo)系中，并聯(lián)機(jī)構(gòu)從動坐標(biāo)系｛O｝到靜坐標(biāo)系｛P｝的轉(zhuǎn)換矩陣為TOP

（3）根據(jù)上述轉(zhuǎn)換矩陣，可得點Ri3，(i=1，2，3，4)在靜坐標(biāo)系中的坐標(biāo)。

（4）已知動平臺上的轉(zhuǎn)動副布置特點，均垂直動平臺，即得到點Ri2，(i=1，2，3，4)在{O-xyz}中的坐標(biāo)。

（5）由于平行四邊形機(jī)構(gòu)Pa結(jié)構(gòu)不變，桿長為l2，建立如下所示方程等式：

將變量di分離，處理得到di的表達(dá)式：

其中，

工作空間分析是根據(jù)建立的逆解方程完成，主要根據(jù)逆解方程有解來判定是否為運動范圍內(nèi)的點，利用matlab編程實現(xiàn)工作空間分析以及搜索過程。

4.1.2 4PPaR機(jī)構(gòu)的可達(dá)工作空間搜索

根據(jù)上述的上一節(jié)中算法搜索步驟與流程，選擇具體的參數(shù)值進(jìn)行，如表1所示。用紅色顏色標(biāo)識為隨機(jī)移動的粒子，藍(lán)色標(biāo)識為工作空間邊界的粒子；搜索算法參數(shù)設(shè)定如下：元胞空間大小為（60×60×60），粒子數(shù)量為5000個，移動速度為1，運動方向為26個方向。并得到一系列滿足工作空間約束條件的粒子，動態(tài)搜索隨時間演化的過程，如圖4所示。最后得到的可達(dá)工作空間，如圖5所示。搜索過程邊界點變化圖，如圖6所示。

表1 4PPaR機(jī)構(gòu)的尺寸參數(shù)Tab.1 Size Parameters of Mechanism

圖4 機(jī)構(gòu)的可達(dá)工作空間動態(tài)搜索過程圖Fig.4 Dynamic Search Process of Reachable Workspace of Mechanism

圖5 機(jī)構(gòu)的可達(dá)工作空間搜索結(jié)果Fig.5 Reachable Workspace Search Results of Mechanism

圖6 機(jī)構(gòu)的搜索過程邊界點的變化過程Fig.6 Search Process of Mechanism Change Process of Boundary Point

根據(jù)圖4動態(tài)仿真圖分析可得：時間t=1至t=102為全部搜索演化過程，剛開始并聯(lián)機(jī)構(gòu)可達(dá)工作空間在搜索的過程中在滿足要求的藍(lán)色粒子在不斷地增加。最后得到滿足約束條件的可達(dá)工作空間，如圖5所示。所得機(jī)構(gòu)工作空間邊界光滑連續(xù)、無空洞情況，且邊界點清晰，表明了此算法的動態(tài)可視化搜索能力。

邊界點搜索過程的變化情況，可以發(fā)現(xiàn)每步搜索到點的個數(shù)呈鋸齒狀增加，每步得到的邊界點在400個以上，表明了算法的并行計算能力，同時累計的增加呈直線趨勢，在140多步時，邊界點的個數(shù)已超過7萬個，如圖6所示。

4.2 算例2仿真分析

4.2.1 4PRPaRR機(jī)構(gòu)運動學(xué)逆解分析

4PRPaRR機(jī)構(gòu)結(jié)構(gòu)簡圖，如圖7所示。機(jī)構(gòu)的逆解具體分析過程可參考文獻(xiàn)［6］，就不再此詳述，機(jī)構(gòu)主動副參數(shù)是以移動副的移動距離(d1，d2，d3，d4)表示，而動平臺的位置姿態(tài)輸出參數(shù)(x，y，z，θ)。分析得到機(jī)構(gòu)逆解表達(dá)式：

圖7 并聯(lián)機(jī)構(gòu)結(jié)構(gòu)簡圖Fig.7 Schematic Diagram of Parallel Mechanism

4.2.2 4PRPaRR并聯(lián)機(jī)構(gòu)定姿態(tài)工作空間搜索

4PRPaRR 并聯(lián)機(jī)構(gòu)定姿態(tài)工作空間搜索根據(jù)表2 中的參數(shù)值賦值，求解出姿態(tài)角為0°的定姿態(tài)工作空間，動態(tài)搜索隨時間演化的過程，如圖8 所示。最后得到定姿態(tài)工作空間，如圖9 所示。

圖8 機(jī)構(gòu)的定姿態(tài)工作空間動態(tài)搜索過程圖Fig.8 Dynamic Search Process of Fixed Pose Workspace for Mechanism

圖9 機(jī)構(gòu)定姿態(tài)工作空間搜索結(jié)果（0°）Fig.9 Search Results of Fixed Position Workspace（0°）

表2 機(jī)構(gòu)的尺寸參數(shù)Tab.2 Size Parameters of Mechanism

由上圖8動態(tài)仿真圖分析：t=1至t=106的動態(tài)仿真演化過程，在運動到14步時得到了基本的定姿態(tài)角的工作空間形狀，隨著步數(shù)增加，工作空間形狀趨于完整，搜索結(jié)果，如圖9所示。搜索得到的工作空間邊界點形狀精確，輪廓清晰。邊界點搜索過程的數(shù)量變化情況，和4PPaR機(jī)構(gòu)類似也是每步搜索到的點的個數(shù)層鋸齒狀增加，每步得到的邊界點在380個以上，同時累計的增加呈直線趨勢，在110多步時，邊界點的個數(shù)已超過4.5萬個，如圖10所示。更換了機(jī)構(gòu)也可以能得到邊界輪廓清晰工作空間，能實現(xiàn)支鏈復(fù)雜的空間并聯(lián)機(jī)構(gòu)工作空間搜索。表明該算法的適應(yīng)性能力較強(qiáng)。

圖10 機(jī)構(gòu)的搜索過程邊界點的變化過程Fig.10 Searching Process of Mechanism Changing Process of Boundary Point

4.3 3D格子氣偏隨機(jī)模型動態(tài)演化搜索法特點

從上述算例分析，可以發(fā)現(xiàn)該算法具有如下特點：（1）并行計算，能夠通過多個點的隨機(jī)運動，同時找到一定數(shù)量的邊界點，并行搜索能力突出；（2）適應(yīng)性強(qiáng)，可適應(yīng)不同的工作空間的搜索，只需更換判斷工作空間約束條件就能夠完成支鏈結(jié)構(gòu)復(fù)雜的并聯(lián)機(jī)構(gòu)的可達(dá)工作空間與定姿態(tài)空間的搜索；（3）動態(tài)特性，粒子動態(tài)可視化運動，能夠觀察完整的搜索全過程，通過粒子移動搜索可以發(fā)現(xiàn)機(jī)構(gòu)是否存在空洞的情況；（4）擴(kuò)展性能，可以設(shè)定特定的搜索運動模式，即控制粒子的運動方向，有6（上下左右前后）或者18、26個運動方向（上下左右前后及其組合），方向越多，同時搜索的點的數(shù)量越多，效率越高。這里所采用鄰域個數(shù)26，其速度運動方向有26個，以得到更加高效的搜索能力。

5 算法參數(shù)對搜索能力的影響分析

以4PPaR機(jī)構(gòu)為例，按照表1中的結(jié)構(gòu)參數(shù)，通過改變均勻格子氣偏隨機(jī)模型動態(tài)演化搜索法中的粒子數(shù)量、移動速度以及粒子位置等，研究這些參數(shù)對算法搜索能力的影響。

5.1 粒子個數(shù)對搜索能力的影響分析

觀察對邊界點搜尋個數(shù)的影響，粒子均勻布滿搜索空間，粒子運動速度為1，運動方向為26 個方向，粒子數(shù)目按照1000、2000、6000個進(jìn)行仿真，運算結(jié)果，如圖11所示。

圖11 不同粒子數(shù)量得到的搜索邊界點個數(shù)變化曲線Fig.11 Change Curve of the Number of Search Boundary Points Obtained by Different Particle Numbers

線性擬合方程為：1000個粒子：y_1000=88.7x-283；2000個粒子：y_2000=205x-548；6000個粒子：y_6000=589x-1710。

根據(jù)圖11 分析并結(jié)合擬合方程可得：數(shù)量為1000：2000：6000的粒子數(shù)量其邊界點增長速度比為1：2.3：6.6，基本和粒子數(shù)量成正比，表明粒子數(shù)目越多，其并行計算能力越強(qiáng)，找到邊界點的數(shù)量就越多，考慮實際時，可以選擇適宜的粒子數(shù)量。

5.2 粒子移動速度對搜索能力的影響分析

觀察粒子移動速度對邊界點搜尋個數(shù)的影響，粒子均勻布滿搜索空間，粒子運動速度為1、2和3，運動方向為26個方向，粒子數(shù)目按照2000個進(jìn)行計算仿真，運算結(jié)果，如圖12所示。

圖12 不同粒子移動速度得到的搜索邊界點個數(shù)變化曲線Fig.12 The Curve of the Number of Searching Boundary Points Obtained by Different Particle Velocity

線性擬合方程為：粒子移動速度為1：y_1=205x-548；粒子移動速度為2：y_2=212x-579；粒子移動速度為3：y_3=178x-489。按照圖12和擬合方程分析可得：粒子移動速度為1：2：3的粒子數(shù)量其邊界點增長速度比為1：1.03：0.87，呈先上升后下降的趨勢。移動速度過快，映射到工作空間的坐標(biāo)變化值越大，較難找到邊界值的一個比較窄的范圍，因此，選擇移動速度為2較為適宜。

5.3 粒子初始運動位置對搜索能力的影響分析

觀察對粒子初始位置對搜尋邊界點個數(shù)的影響，粒子集中于工作空間內(nèi)，粒子運動速度為2，運動方向為26個方向，粒子數(shù)目按照2000個進(jìn)行仿真，仿真的動態(tài)過程圖，如圖13所示。相應(yīng)的粒子處在不同位置得到的搜索邊界點個數(shù)變化曲線，如圖14所示。

圖13 粒子位置集中于工作空間的搜索動態(tài)過程圖Fig.13 Dynamic Process Diagram of Particle Location in Workspace

圖14 粒子處在不同位置得到的搜索邊界點個數(shù)變化曲線Fig.14 The Curve of the Number of Searching Boundary Points at Different Positions of Particles.

線性擬合方程為：集中位置：y_集中=614x+3097；均勻位置：y_均勻=212x-579。

根據(jù)圖13分析可得：粒子運動呈現(xiàn)擴(kuò)散趨勢，在146步時已基本擴(kuò)散至整個空間；初始位置在靠近工作空間時，相當(dāng)于提高了粒子密度，在動態(tài)搜索過程，得到更強(qiáng)的搜索能力，根據(jù)圖14分析可得：粒子集中分布與粒子均勻分布邊界點增長速度比為2.9。因此，可以根據(jù)機(jī)構(gòu)支鏈分布特點，改變初始粒子位置，讓粒子位置靠近工作空間來實現(xiàn)高效搜索。

6 結(jié)論

（1）提出一種新型并聯(lián)機(jī)構(gòu)工作空間分析方法，并逐一說明3D格子氣自動機(jī)搜索算法原理、搜索流程以及搜索算法特點。

（2）通過兩種機(jī)構(gòu)的可達(dá)空間和定姿態(tài)工作空間驗證了該算法的有效性和并行計算能力。

（3）通過改變算法參數(shù)，分析了影響算法搜索能力的影響因素，提高粒子數(shù)量，適宜的粒子運動速度，以及粒子集中分布和靠近工作空間可以提高該算法搜索能力。

（4）下一步工作構(gòu)想是可以構(gòu)件自動機(jī)繁殖和邊界點吸引規(guī)則，以提高粒子運動搜索能力。