基于圖論的計(jì)算機(jī)輔助裝夾規(guī)劃方法研究

許本勝，王 燦，黃美發(fā)

（1. 桂林航天工業(yè)學(xué)院 機(jī)械工程系，桂林 541004；2. 桂林電子科技大學(xué) 機(jī)電工程學(xué)院，桂林 541004）

0 引言

零件裝夾規(guī)劃是自動(dòng)工藝規(guī)劃的核心內(nèi)容之一，其任務(wù)是通過(guò)綜合考慮工件幾何形狀、尺寸和公差、加工資源等信息，來(lái)確定工件裝夾的次數(shù)、順序以及每次裝夾中的定位基準(zhǔn)、加工特征和加工方法[1]。

隨著計(jì)算機(jī)技術(shù)的發(fā)展，如何利用計(jì)算機(jī)輔助進(jìn)行零件的裝夾規(guī)劃已經(jīng)受到人們的廣泛關(guān)注和研究。如Zhang等[2]使用混合圖理論對(duì)三軸立銑加工中心工件的裝夾工藝進(jìn)行設(shè)計(jì)。巢炎[3]等采用圖論方法研究了零件加工自動(dòng)定位設(shè)計(jì)的基本規(guī)則。張發(fā)平等[4]、黃偉軍等[5]進(jìn)行了面向CAPP的裝夾規(guī)程數(shù)學(xué)建模和算法的研究。孫習(xí)武等[6]提出基于聚類(lèi)分析法的裝夾規(guī)劃算法。當(dāng)前研究雖然實(shí)現(xiàn)了一定程度上裝夾規(guī)劃的自動(dòng)化，但主要采用的是基于經(jīng)驗(yàn)的方法（如規(guī)則和知識(shí)庫(kù)），且主要適用于只具有尺寸公差要求的情況。

幾何尺寸和公差（Geometric Dimensioning and Tolerancing, GD&T）規(guī)范是當(dāng)前加工制造業(yè)普遍采用的設(shè)計(jì)和制造標(biāo)準(zhǔn)規(guī)范。基準(zhǔn)的概念和詳細(xì)的形位公差方案是GD&T規(guī)范的特點(diǎn)，也是進(jìn)行零件自動(dòng)裝夾規(guī)劃的基礎(chǔ)和條件。本文根據(jù)零件的GD&T規(guī)范，結(jié)合圖論的表示方法，進(jìn)行計(jì)算機(jī)輔助裝夾規(guī)劃方法的研究，具體包括裝夾定位基準(zhǔn)的確定、加工特征的聚類(lèi)以及實(shí)現(xiàn)各組聚類(lèi)特征之間的裝夾排序三個(gè)基本方面的內(nèi)容，目的在于為實(shí)現(xiàn)計(jì)算機(jī)輔助裝夾規(guī)劃提供基礎(chǔ)。

1 GD&T規(guī)范及有向圖表示

采用上下偏差來(lái)規(guī)定公稱尺寸變動(dòng)范圍的參數(shù)化公差表示方法，是最早出現(xiàn)在零件圖紙上的公差方案。由于沒(méi)有指定明確的基準(zhǔn)（如圖1(a)所示），當(dāng)零件的加工表面具有定向或定位要求時(shí)，這種僅采用上下極限偏差表示的公差方案含義是不明確的，給后續(xù)加工和檢測(cè)階段零件裝夾方案的確定帶來(lái)困難。相反，幾何尺寸和公差方案以基準(zhǔn)概念為基礎(chǔ)，通過(guò)引入基準(zhǔn)參考框架來(lái)確定零件各表面間的相對(duì)位置。如圖1(b)所示，零件上A、B和C表面構(gòu)成基準(zhǔn)參考框架，通過(guò)基準(zhǔn)面B和C可以明確指定孔的位置公差（包括形狀和大?。?。顯然，幾何尺寸和公差方案中，零件的尺寸、形狀和幾何特征的相對(duì)位置更為清晰和明確，為后續(xù)計(jì)算機(jī)輔助裝夾規(guī)劃帶來(lái)了可操作性。

圖1 兩種公差方案比較

從幾何和拓?fù)鋵W(xué)角度看，零件功能表面可以劃分為平面、圓柱面、球面等共7種類(lèi)型。為了更好地表示零件各功能表面間的聯(lián)系，Clement等提出了MGDE（minimum geometric datum elements）概念[7]，即最小幾何基準(zhǔn)要素，MGDE實(shí)質(zhì)上是由參考點(diǎn)、參考線或參考面組成的最小集合以確定相應(yīng)的功能表面不變。7種基本功能表面及最小幾何基準(zhǔn)要素為構(gòu)成零件的基本幾何特征，各基本幾何特征之間的公差關(guān)系可利用圖論的方法來(lái)描述，如圖2所示。

圖2 特征公差關(guān)系有向圖表示

圖2中，節(jié)點(diǎn)v1、v2和v3表示零件幾何特征，聯(lián)結(jié)各節(jié)點(diǎn)的邊表示各加工特征之間的基準(zhǔn)和公差關(guān)系。顯然，由于兩節(jié)點(diǎn)間的公差約束存在多個(gè)的情況，常規(guī)的有向圖難以對(duì)其進(jìn)行表示。為此，在常規(guī)有向圖的基礎(chǔ)上，通過(guò)增加對(duì)兩個(gè)節(jié)點(diǎn)間約束關(guān)系的描述，采用擴(kuò)展有向圖進(jìn)行零件幾何特征-公差關(guān)系的表示，如下：

式中V為節(jié)點(diǎn)集合，元素vi(i=1，2，…，n，n為節(jié)點(diǎn)個(gè)數(shù))為圖的節(jié)點(diǎn)，vi代表零件上某個(gè)基準(zhǔn)或加工表面；E為各節(jié)點(diǎn)間邊的集合，元素ei為連接節(jié)點(diǎn)vj和vk的有向邊，每條邊表示兩節(jié)點(diǎn)間的一種公差約束關(guān)系；li為對(duì)應(yīng)邊ei的屬性，如公差類(lèi)型、公差值等的描述。

2 基于圖論的計(jì)算機(jī)輔助裝夾規(guī)劃

2.1 幾何特征-公差關(guān)系有向圖的計(jì)算機(jī)表示

有向圖的計(jì)算機(jī)表示常見(jiàn)方法為鄰接矩陣。采用矩陣進(jìn)行圖的存儲(chǔ)時(shí)，矩陣的長(zhǎng)度不能夠動(dòng)態(tài)變化，當(dāng)圖的頂點(diǎn)個(gè)數(shù)改變時(shí)需重寫(xiě)鄰接矩陣，難以實(shí)現(xiàn)如頂點(diǎn)的增加和移除等有關(guān)圖的操作，因而采用鄰接矩陣的表示方法靈活性差。另外，采用矩陣的表示方法不能描述節(jié)點(diǎn)間存在多種關(guān)系（如兩加工表面間存在多個(gè)公差約束）的情況。

為了方便裝夾規(guī)劃問(wèn)題的計(jì)算機(jī)處理，本文采用面向?qū)ο蟮木幊谭椒▉?lái)實(shí)現(xiàn)擴(kuò)展有向圖的計(jì)算機(jī)表示，有關(guān)結(jié)構(gòu)體和類(lèi)的代碼如下：

struct Label{ //邊

int id;

CString name;

CString tolerance_type;

float tolerance_value;

}

struct Node{ //節(jié)點(diǎn)

int id;

CString name;

LinkList＜Label＞ formEdges; //LinkList＜Label＞邊對(duì)應(yīng)起始節(jié)點(diǎn)儲(chǔ)存鏈表

LinkList＜Label＞ toEdges; // LinkList＜Label＞邊指向節(jié)點(diǎn)儲(chǔ)存鏈表

}

class Graph{ //圖

private:

LinkList＜Node＞ nodes; // LinkList＜Label＞

為節(jié)點(diǎn)儲(chǔ)存鏈表

public:

void add(Node); //增加節(jié)點(diǎn)

void remove(Node); //移除節(jié)點(diǎn)

void join(Node, Label, Node); //添加兩節(jié)點(diǎn)間的公差約束關(guān)系

void getSubGraph(Graph g); //獲取裝夾子圖

void unitGraph(Graph g1, Graph g2); //合并子圖

void getSetup(); //裝夾規(guī)劃結(jié)果集

}

2.2 加工特征的聚類(lèi)

所謂加工特征的聚類(lèi)指的是根據(jù)幾何特征-公差關(guān)系對(duì)各加工特征進(jìn)行分組。對(duì)加工特征進(jìn)行聚類(lèi)時(shí)，首先需要確定裝夾基準(zhǔn)特征。裝夾基準(zhǔn)的計(jì)算機(jī)輔助確定方法可由幾何特征-公差關(guān)系有向圖中各節(jié)點(diǎn)的入度（指向節(jié)點(diǎn)的邊的條數(shù)）來(lái)確定。入度為零的節(jié)點(diǎn)形成初始加工基準(zhǔn)，如圖3中節(jié)點(diǎn)X、Y和Z構(gòu)成初始加工基準(zhǔn)框架（X、Y、Z）。入度為3的節(jié)點(diǎn)，指向該節(jié)點(diǎn)的三條邊構(gòu)成裝夾基準(zhǔn)，如圖3中指向節(jié)點(diǎn)A的三條邊（X，A）、（Y，A）和（Z，A）以及指向節(jié)點(diǎn)B的三條邊。

在進(jìn)行加工特征的聚類(lèi)時(shí)，必須遵循一定的規(guī)則，如：

圖3 加工特征聚類(lèi)示例

規(guī)則1：先前完成加工的幾何表面特征優(yōu)先作為裝夾基準(zhǔn)。

規(guī)則2：為減少加工誤差的累積，一次裝夾盡可能完成多個(gè)幾何表面特征的加工。

通常零件需要多次裝夾才能完成各幾何表面特征的加工，進(jìn)行裝夾規(guī)劃還必須考慮各裝夾基準(zhǔn)參考框架的加工生成順序，對(duì)應(yīng)有如下規(guī)則：

規(guī)則3：裝夾規(guī)劃次序必須根據(jù)裝夾基準(zhǔn)參考框架自身加工生成的順序來(lái)安排。

根據(jù)幾何特征-公差關(guān)系有向圖，將圖中節(jié)點(diǎn)分為三類(lèi)：入度為零的節(jié)點(diǎn)、出度為零的節(jié)點(diǎn)和其他節(jié)點(diǎn)。其他節(jié)點(diǎn)的特點(diǎn)在于加工時(shí)不但具有裝夾基準(zhǔn)要求，同時(shí)在完成加工后有可能作為后續(xù)加工特征的裝夾基準(zhǔn)。由此，加工特征聚類(lèi)的算法為：從圖中出度為零的節(jié)點(diǎn)開(kāi)始，根據(jù)邊的指向關(guān)系，逆向追溯直至找到入度大于等于3的節(jié)點(diǎn)，且指向最終節(jié)點(diǎn)的三條邊對(duì)應(yīng)的起始節(jié)點(diǎn)為該組加工特征的裝夾基準(zhǔn)，并將這些節(jié)點(diǎn)歸為一組。若逆向追溯的最終節(jié)點(diǎn)的入度大于3，則根據(jù)規(guī)則1，選擇先前完成加工的三個(gè)節(jié)點(diǎn)作為該組加工特征的裝夾基準(zhǔn)。對(duì)于所獲得的結(jié)果，根據(jù)規(guī)則2，可將具有相同的裝夾基準(zhǔn)的多組加工特征合并為一組；最后，由規(guī)則3，具有不同裝夾基準(zhǔn)的各組加工特征，根據(jù)裝夾基準(zhǔn)完成加工的先后來(lái)安排其裝夾規(guī)劃的次序。據(jù)此思路對(duì)圖3所示加工特征進(jìn)行聚類(lèi)，得到各分組次序及裝夾基準(zhǔn)結(jié)果如表1所示。

表1 加工特征的聚類(lèi)

2.3 算法流程

由以上分析，基于擴(kuò)展有向圖的計(jì)算機(jī)輔助裝夾規(guī)劃算法流程為：

1)根據(jù)零件圖確定加工特征-公差關(guān)系有向圖，并進(jìn)行計(jì)算機(jī)存儲(chǔ)和表示；

2)從出度為零的節(jié)點(diǎn)開(kāi)始，根據(jù)邊的指向，逆向追溯至入度大于等于3的節(jié)點(diǎn)，獲取包括裝夾基準(zhǔn)特征在內(nèi)的裝夾子圖，即實(shí)現(xiàn)對(duì)加工特征的聚類(lèi)；

3)除初始基準(zhǔn)特征（入度為零的節(jié)點(diǎn)）以外，判斷其余各節(jié)點(diǎn)是否全部包含在步驟3的裝夾子圖結(jié)果中，若是則表明全部加工特征都已經(jīng)實(shí)現(xiàn)裝夾聚類(lèi)，從而可以繼續(xù)步驟4），否則從判斷節(jié)點(diǎn)開(kāi)始執(zhí)行步驟2；

4)將具有相同裝夾基準(zhǔn)的多組加工特征合并為一組；

5)按照基準(zhǔn)參考框架的加工生成順序?qū)Ω鹘M加工特征進(jìn)行排序，并輸出最終裝夾規(guī)劃結(jié)果。

由于實(shí)際加工中，零件某些加工特征在加工后會(huì)作為其它特征的加工裝夾基準(zhǔn)，上述流程中的步驟3目的在于保證所有加工特征節(jié)點(diǎn)在各自的聚類(lèi)分組中都實(shí)現(xiàn)加工，從而保證裝夾規(guī)劃的完整性。

與2.1節(jié)中有向圖計(jì)算機(jī)表示相對(duì)應(yīng)，步驟2、3結(jié)果由getSubGraph(Graph g)獲得、步驟4由函數(shù)unitGraph(Graph g1, Graph g2)實(shí)現(xiàn)，通過(guò)執(zhí)行函數(shù)getSetup()完成步驟5。

3 實(shí)例分析

以某簡(jiǎn)化汽車(chē)底盤(pán)前轉(zhuǎn)向節(jié)零件為例，該零件是汽車(chē)制動(dòng)系統(tǒng)、懸架系統(tǒng)和轉(zhuǎn)向系統(tǒng)的接合關(guān)節(jié)。零件上各幾何加工特征如圖4所示。由零件功能確定的幾何加工特征-公差關(guān)系有向圖如圖5所示。

圖4 示例零件幾何表面加工特征示意圖

圖5 加工特征-公差約束關(guān)系擴(kuò)展有向圖

按圖5完成對(duì)加工特征-公差約束關(guān)系擴(kuò)展有向圖的計(jì)算機(jī)存儲(chǔ)和表示。在此基礎(chǔ)上，根據(jù)前述裝夾規(guī)劃算法流程，首先計(jì)算各節(jié)點(diǎn)出度和入度，得到入度為零的初始加工基準(zhǔn)（X、Y、Z），其余特征為裝夾規(guī)劃中的待加工特征。從出度為零的節(jié)點(diǎn)C、E和G開(kāi)始，向前追溯分別得到以下加工特征分組：

查詢各分組中除基準(zhǔn)特征以外的加工特征，可判斷出沒(méi)有對(duì)加工特征B進(jìn)行裝夾規(guī)劃。因而從節(jié)點(diǎn)B開(kāi)始繼續(xù)向前追溯，得到聚類(lèi)特征B←（X、Y、Z、A），由于特征X與A之間存在基準(zhǔn)約束關(guān)系，特征X先于A加工，由規(guī)則1，優(yōu)先選擇特征X作為特征B的裝夾基準(zhǔn)。從而有加工特征分組：

結(jié)果（5）～（8）中，共有兩組裝夾基準(zhǔn)，顯然基準(zhǔn)（X、Y、Z）先于（A、B、Z）加工生成。從而，按照規(guī)則2和規(guī)則3，對(duì)具有相同基準(zhǔn)的各分組加工特征進(jìn)行合并、裝夾排序，得到最終裝夾規(guī)劃結(jié)果如下：

根據(jù)本文方法，采用VC6.0編程軟件進(jìn)行裝夾規(guī)劃原型系統(tǒng)的開(kāi)發(fā)，示例零件結(jié)果如圖6所示。

圖6 原型系統(tǒng)

4 結(jié)論

本文從零件幾何尺寸和公差規(guī)范著手，闡述了基于圖論的計(jì)算機(jī)輔助裝夾規(guī)劃方法，包括零件加工特征-公差關(guān)系的擴(kuò)展有向圖表示、加工特征的聚類(lèi)以及裝夾規(guī)劃的算法流程。實(shí)例表明，本文方法可以有效地確定工藝路線中的裝夾次數(shù)、裝夾基準(zhǔn)和裝夾順序。后續(xù)將從以下兩個(gè)方面對(duì)本文方法作進(jìn)一步的完善：1）綜合考慮加工資源，如機(jī)床加工能力、生產(chǎn)方案對(duì)裝夾規(guī)劃的影響，加強(qiáng)加工特征聚類(lèi)和裝夾順序處理能力；2）實(shí)現(xiàn)零件在裝夾、加工過(guò)程中的誤差累積關(guān)系分析和建模，與夾具設(shè)計(jì)集成。

[1] Y.Zhang,W.Hu,Y.Rong, etc. Graph-based set-up planning and tolerance decomposition for computer-aided fixture design[J].International Journal of Production Research,39:14,3109-3126.

[2] ZHANG H C,LIN E.A hybrid-graph approach for automated setup planning in CAPP[J].Robotics and Compute-Integrated Manufacturing,1999,15(1):89-100.

[3] 巢炎,楊將新,吳昭同.基于圖論的產(chǎn)品自動(dòng)定位設(shè)計(jì)[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版),2005,39(12):1925-1929.

[4] 張發(fā)平,孫厚芳,焦黎.面向CAPP的裝夾規(guī)程模型與算法研究[J].北京理工大學(xué)學(xué)報(bào),2006,26(12):1056-1060.

[5] 黃偉軍,胡于進(jìn),蔡力鋼.面向CAPP的零件裝夾規(guī)劃算法研究[J].中國(guó)機(jī)械工程,2011,22(22):2700-2706.

[6] 孫習(xí)武,褚學(xué)寧,蘇於梁,湯岑書(shū).基于聚類(lèi)分析法的裝夾規(guī)劃算法研究[J].計(jì)算機(jī)集成制造系統(tǒng),2009,15(6):1179-1186.

[7] Clement A.Riviere A.Tolerancing versus nominal modeling in next generation CAD/CAM system[A].In:Processing of 3rd CIRP Seminar on Computer Aided Toleracing, Cachan, France, 1993:98-113.