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

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

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

0 引言

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

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

幾何尺寸和公差（Geometric Dimensioning and Tolerancing, GD&T）規(guī)范是當前加工制造業(yè)普遍采用的設計和制造標準規(guī)范?；鶞实母拍詈驮敿毜男挝还罘桨甘荊D&T規(guī)范的特點，也是進行零件自動裝夾規(guī)劃的基礎和條件。本文根據(jù)零件的GD&T規(guī)范，結合圖論的表示方法，進行計算機輔助裝夾規(guī)劃方法的研究，具體包括裝夾定位基準的確定、加工特征的聚類以及實現(xiàn)各組聚類特征之間的裝夾排序三個基本方面的內(nèi)容，目的在于為實現(xiàn)計算機輔助裝夾規(guī)劃提供基礎。

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

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

圖1 兩種公差方案比較

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

圖2 特征公差關系有向圖表示

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

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

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

2.1 幾何特征-公差關系有向圖的計算機表示

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

為了方便裝夾規(guī)劃問題的計算機處理，本文采用面向?qū)ο蟮木幊谭椒▉韺崿F(xiàn)擴展有向圖的計算機表示，有關結構體和類的代碼如下：

struct Label{ //邊

int id;

CString name;

CString tolerance_type;

float tolerance_value;

}

struct Node{ //節(jié)點

int id;

CString name;

LinkList＜Label＞ formEdges; //LinkList＜Label＞邊對應起始節(jié)點儲存鏈表

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

}

class Graph{ //圖

private:

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

為節(jié)點儲存鏈表

public:

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

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

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

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

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

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

}

2.2 加工特征的聚類

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

在進行加工特征的聚類時，必須遵循一定的規(guī)則，如：

圖3 加工特征聚類示例

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

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

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

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

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

表1 加工特征的聚類

2.3 算法流程

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

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

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

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

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

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

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

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

3 實例分析

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

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

圖5 加工特征-公差約束關系擴展有向圖

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

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

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

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

圖6 原型系統(tǒng)

4 結論

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

[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)品自動定位設計[J].浙江大學學報(工學版),2005,39(12):1925-1929.

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

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

[6] 孫習武,褚學寧,蘇於梁,湯岑書.基于聚類分析法的裝夾規(guī)劃算法研究[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.