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

許本勝，王 燦，黃美發

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

0 引言

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

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

幾何尺寸和公差（Geometric Dimensioning and Tolerancing, GD&T）規范是當前加工制造業普遍采用的設計和制造標準規范。基準的概念和詳細的形位公差方案是GD&T規范的特點，也是進行零件自動裝夾規劃的基礎和條件。本文根據零件的GD&T規范，結合圖論的表示方法，進行計算機輔助裝夾規劃方法的研究，具體包括裝夾定位基準的確定、加工特征的聚類以及實現各組聚類特征之間的裝夾排序三個基本方面的內容，目的在于為實現計算機輔助裝夾規劃提供基礎。

1 GD&T規范及有向圖表示

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

圖1 兩種公差方案比較

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

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

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

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

2 基于圖論的計算機輔助裝夾規劃

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

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

為了方便裝夾規劃問題的計算機處理，本文采用面向對象的編程方法來實現擴展有向圖的計算機表示，有關結構體和類的代碼如下：

struct Label{ //邊

int id;

CString name;

CString tolerance_type;

float tolerance_value;

}

struct Node{ //節點

int id;

CString name;

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

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

}

class Graph{ //圖

private:

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

為節點儲存鏈表

public:

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

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

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

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

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

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

}

2.2 加工特征的聚類

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

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

圖3 加工特征聚類示例

規則1：先前完成加工的幾何表面特征優先作為裝夾基準。

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

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

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

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

表1 加工特征的聚類

2.3 算法流程

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

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

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

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

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

5)按照基準參考框架的加工生成順序對各組加工特征進行排序，并輸出最終裝夾規劃結果。

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

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

3 實例分析

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

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

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

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

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

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

根據本文方法，采用VC6.0編程軟件進行裝夾規劃原型系統的開發，示例零件結果如圖6所示。

圖6 原型系統

4 結論

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

[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] 巢炎,楊將新,吳昭同.基于圖論的產品自動定位設計[J].浙江大學學報(工學版),2005,39(12):1925-1929.

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

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

[6] 孫習武,褚學寧,蘇於梁,湯岑書.基于聚類分析法的裝夾規劃算法研究[J].計算機集成制造系統,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.