基于工程語義約束的線束預(yù)裝配自動規(guī)劃方法

劉曉平， 李忠澤， 徐本柱， 朱吉滿， 何宏林

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院VCC研究室，安徽 合肥 230009）

汽車線束是指將不同工作用途的導(dǎo)線經(jīng)捆扎成束而形成的用于連接汽車各個電子設(shè)備的重要組件。線束預(yù)裝配是為了降低線束總成裝配時的復(fù)雜度和減少工作量而把線束分解成若干個子線束的過程。線束預(yù)裝配是線束進(jìn)入總裝流水線的前工序，是直接影響產(chǎn)品生產(chǎn)效率及質(zhì)量提高的重要因素之一。目前現(xiàn)有的裝配控制研究主要集中在機(jī)械零部件的裝配序列規(guī)劃方面，主要方法有遺傳算法[1-2]、割集法[3-4]、優(yōu)先約束規(guī)則法[5]等。然而，線束預(yù)裝配主要完成把經(jīng)過壓接工序的導(dǎo)線預(yù)先裝配到電器接插件的端口中，與傳統(tǒng)的機(jī)械產(chǎn)品裝配有很大不同。機(jī)械產(chǎn)品裝配中零部件之間總是存在某種緊固或接觸聯(lián)接關(guān)系，相互關(guān)聯(lián)的零件能自發(fā)分離或者借助外力能夠發(fā)生分離[6-7]，然而線束中的導(dǎo)線經(jīng)過壓接工序后，導(dǎo)線之間復(fù)雜的實(shí)際物理連接關(guān)系便完全確定，在預(yù)裝配過程中必須完全保持它們之間的聯(lián)接約束，不能夠隨便發(fā)生分離。因此，傳統(tǒng)的遺傳算法、割集法、優(yōu)先約束規(guī)則法等常見的裝配序列規(guī)劃策略并不能夠直接應(yīng)用于線束的預(yù)裝配過程中。

文獻(xiàn)[8]提出了一種基于約束集合模型的線束預(yù)裝配過程控制方法，然而該方法需要用戶手動選擇基準(zhǔn)件和刪除不需預(yù)裝的導(dǎo)線和接插件，因此其本質(zhì)上只完成了導(dǎo)線連接關(guān)系的提取，并不是真正意義上的預(yù)裝配序列自動規(guī)劃。本文通過總結(jié)線束工藝設(shè)計(jì)中的工程語義約束信息，建立裝配關(guān)聯(lián)圖模型，并在此基礎(chǔ)上提出一種無需與用戶進(jìn)行交互的線束預(yù)裝配自動規(guī)劃方法，實(shí)現(xiàn)對線束預(yù)裝配工藝的自動規(guī)劃。

1 相關(guān)概念

1.1 導(dǎo)線、接插件分類

線束圖紙是用來表示導(dǎo)線連接關(guān)系的 CAD圖紙。線束圖紙中存在大量的導(dǎo)線和接插件，為了在預(yù)裝配過程中針對不同情況實(shí)施不同的處理方法，本文先對導(dǎo)線和接插件進(jìn)行分類。線束圖紙中的導(dǎo)線根據(jù)電路邏輯連接關(guān)系可以分為兩大類：單根線和內(nèi)聯(lián)線。

在上述導(dǎo)線定義的基礎(chǔ)上，本文根據(jù)端口連接的導(dǎo)線類型不同而把接插件分為以下3類：

定義3 簡單接插件(Simple Connector，SC )設(shè)接插件全集為，若ci( ci∈C )端口中連接的任意導(dǎo)線wi均為單根線時，稱ci為簡單接插件。簡單接插件端口中不同單根線的數(shù)目稱為簡單接插件的“單聯(lián)度”，記為 s cdeg( S C )，顯然 s cdeg( S C)≥ 1。

定義4 復(fù)雜接插件(Complicated Connector,CC ) 設(shè)接插件全集為，若 ci( ci∈C )端口連接的導(dǎo)線中至少存在一根內(nèi)聯(lián)線，稱ci為復(fù)雜接插件。復(fù)雜接插件中不同內(nèi)聯(lián)回路的數(shù)目稱為復(fù)雜接插件的“內(nèi)聯(lián)度”，記為 ic deg( C C )，顯然 ic deg( C C)≥ 1。與簡單接插件類似，復(fù)雜接插件也可能存在“單聯(lián)度”，scdeg( C C )≥ 0 ，然而簡單接插件的“內(nèi)聯(lián)度”一定為0。

定義5 孤立接插件(Isolated Connector，IC )設(shè)接插件全集為若ci( ci∈C )中所有端口均不連接任何導(dǎo)線時，稱ci為孤立接插件。顯然，s c deg( I C ) = i cdeg( I C )=0。由孤立接插件構(gòu)成的集合記為ICS。

1.2 子裝配體的定義

線束預(yù)裝配規(guī)劃主要完成從線束圖紙中提取出各個符合工程設(shè)計(jì)要求的子裝配體。子裝配體是導(dǎo)線與接插件的集合，在線束預(yù)裝配過程中，先要確定一個主接插件（簡稱主件），其它的接插件都是在主件的基礎(chǔ)上進(jìn)行裝配。子裝配體的形式化定義如下：

子裝配體根據(jù)導(dǎo)線預(yù)裝過程的不同，還可以分為兩大類：后插型子裝配體和非后插型子裝配體。

如圖1(a)所示的為后插型子裝配體，圖1(b)所示的為非后插型子裝配體。

圖1 子裝配體

1.3 工程語義約束

對于導(dǎo)線和接插件數(shù)目很多的線束圖紙來說，如果通過組合方式直接生成所有的預(yù)裝配序列，必然會產(chǎn)生組合爆炸。然而，在實(shí)際的預(yù)裝配過程中，很多的預(yù)裝配序列并不符合工程設(shè)計(jì)上的要求。本文通過引入工程語義約束條件，可以直接在預(yù)裝配過程中把不符合約束條件的裝配序列排除掉，減少搜索空間，提高自動裝配效率。

約束 1 回路約束 對于內(nèi)聯(lián)線 wi, wj，若wi, wj為同一內(nèi)聯(lián)回路中的導(dǎo)線，則 wi, wj必須在同一裝配體SA內(nèi)，即 wi, wj∈SA。

約束 2 主件約束 主件選擇必須符合“CC先于SC”規(guī)則，即復(fù)雜、簡單接插件同時存在同一子裝配體時，應(yīng)優(yōu)先考慮把復(fù)雜接插件作為主件。若同時存在多個復(fù)雜接插件，則應(yīng)選擇“內(nèi)聯(lián)度”最大的接插件作為主件。

約束 3 端口約束 ICS=?，即預(yù)裝配過程中，不能出現(xiàn)把簡單、復(fù)雜接插件變成孤立接插件的情況。

2 預(yù)裝配規(guī)劃算法

2.1 裝配關(guān)聯(lián)圖模型

本文采用無向連接圖G( V, E)來對線束圖紙進(jìn)行描述，其中頂點(diǎn)集合 V ( v1, v2,… ,vn)表示線束圖紙中的接插件集合C，邊集合E( e1, e2,…,em)表示導(dǎo)線的連接關(guān)系，它體現(xiàn)了線束圖紙中的回路約束，G( V, E)稱為裝配關(guān)聯(lián)圖。由于接插件端口內(nèi)可能包含多根導(dǎo)線從而與多個接插件存在連接約束關(guān)系，即 vi={w1, w2,…,wj, …,wk} ,wj∈W ，因此G( V, E)存在平行邊，是一個多重圖。

如圖2(a)所示，頂點(diǎn)圓圈內(nèi)的數(shù)字表示該頂點(diǎn)所代表的接插件端口中包含的導(dǎo)線代號，該圖中包含 2 個內(nèi)聯(lián)回路（1，4，6）、（2，3，5）。頂點(diǎn)V1和V4之間存在兩條邊，其中一條邊表示V1中的導(dǎo)線2和V4中的導(dǎo)線5連通，另一條邊表示V1中的導(dǎo)線1和V4中的導(dǎo)線6連通。為了方便起見，規(guī)定把裝配關(guān)聯(lián)圖中兩個頂點(diǎn)之間的平行邊均合并為一條，于是，裝配關(guān)聯(lián)圖由多重圖變?yōu)楹唵蔚臒o向連通圖，如圖2(b)所示。根據(jù)裝配關(guān)聯(lián)圖的定義，可建立G( V, E)對應(yīng)的關(guān)聯(lián)矩陣 M ( G ) = (aij)n*n，其中i行 j列元素aij定義如下：

圖2 裝配關(guān)聯(lián)圖

顯然，關(guān)聯(lián)矩陣M( G)具有以下規(guī)律：

1）M( G)是一個n階方陣，n為線束圖紙中接插件的數(shù)目。

2）由初始的G( V, E)建立M( G)時，M( G )是一個對稱矩陣。

3）M( G)中任意頂點(diǎn)對應(yīng)的行向量元素值不能同時存在1和-1。

4）M( G)中選為主件的頂點(diǎn)對應(yīng)的行向量元素值不能存在-1。

5）若內(nèi)聯(lián)回路的導(dǎo)線不滿足導(dǎo)線約束時，該內(nèi)聯(lián)回路導(dǎo)線所在頂點(diǎn)對應(yīng)的行向量元素值均為0或-1。

2.2 預(yù)裝配規(guī)劃算法

1）主件選取

為了滿足前面所述的主件約束條件，首先必須分析每個接插件的“內(nèi)聯(lián)度”和“單聯(lián)度”，因此從G( V, E)中確定當(dāng)前子裝配體主件的步驟如下：

Step 1 求出M( G)中行向量元素值不存在-1或2的頂點(diǎn)集合Vm；

Step 4 若滿足 ic deg( vi) = δ(vi)的頂點(diǎn)有多個，假設(shè)分別為只有一個，則把該頂點(diǎn)對應(yīng)的接插件作為主件；否則，隨機(jī)選取其中一個作為主件，主件選取結(jié)束。

2）最大子裝配體提取

主件確定后，需要提取出該主件對應(yīng)的最大子裝配體，在提取最大子裝配體時必須將與主件存在回路約束的頂點(diǎn)都?xì)w入該子裝配體中。根據(jù)裝配關(guān)聯(lián)圖的關(guān)聯(lián)矩陣定義，若兩個頂點(diǎn)之間有邊連接，其所在的行和列對應(yīng)元素值為1或-1，說明這兩個頂點(diǎn)存在回路約束，因此由主件行向量的元素值便可得到其對應(yīng)的最大子裝配體。

圖3所示的是某裝配關(guān)聯(lián)圖的關(guān)聯(lián)矩陣。若當(dāng)前主件對應(yīng)的頂點(diǎn)為vi，vi對應(yīng)的行向量說明vi和vj、vs存在回路約束關(guān)系，vi、vj、vs構(gòu)成了以vi為主件的最大子裝配體，如圖3(b)所示。

直接由裝配關(guān)聯(lián)圖關(guān)聯(lián)矩陣的行向量得到的最大子裝配體并不一定是最終的子裝配體，因?yàn)槠淇赡苓`背第1節(jié)所述的工程語義約束規(guī)則。如圖4所示，頂點(diǎn)圓圈內(nèi)的數(shù)字表示該頂點(diǎn)所代表的接插件端口中包含的導(dǎo)線代號，圖4(a)中包含了 3 個內(nèi)聯(lián)回路（1，2，3）、（4，5，6）、（7，8，9）。如果選擇頂點(diǎn)v2作為主件（虛線方框表示），直接由v2對應(yīng)的行向量提取得到的最大子裝配體如圖 4(b)所示，v3中包含了（7，8，9）內(nèi)聯(lián)回路中的導(dǎo)線7，從而造成圖4(b)、圖4(c)所示的子裝配體不滿足回路約束。因此需要將圖4(b)中v3頂點(diǎn)的導(dǎo)線7刪除，從而得到圖4(d)、圖4(e)所示的子裝配體。圖4(e)中虛線圓圈表示頂點(diǎn)v3對應(yīng)的接插件已經(jīng)在其它子裝配體中預(yù)裝，其實(shí)際為一個后插型子裝配體。

圖3 裝配關(guān)聯(lián)圖的關(guān)聯(lián)矩陣

圖4 子裝配體提取示例

由前面分析可見，最大子裝配體提取完成后，還需要對其進(jìn)行工程語義約束檢測，對不符合約束規(guī)則的最大子裝配體通過適當(dāng)刪除某些接插件或?qū)Ь€，使得該最大子裝配體本身及隨后生成的各個子裝配體都能滿足所有工程語義約束規(guī)則。因此，最終得到的子裝配體是最大子裝配體的一個子集。

3）工程語義約束檢測

為了敘述的方便，下面首先引入集合封閉性的定義。

定義9 集合封閉性 在G( V, E)中，設(shè)存在非空頂點(diǎn)集合任意頂點(diǎn) vi( 1 ≤ i≤n )，若與vi存在回路約束的頂點(diǎn)都是頂點(diǎn)集合V中的元素，則稱V具備集合封閉性。

在關(guān)聯(lián)矩陣M( G)中，行向量值為 1或-1的元素表明了與該行向量對應(yīng)頂點(diǎn)存在回路約束的其它頂點(diǎn)。如圖 5所示，若關(guān)聯(lián)矩陣中時，頂點(diǎn)集合 V { vi, vj, vk}具備集合封閉性；若 ajs=1， asj= 1 或-1時，頂點(diǎn)集合 V { vi, vj, vk}不具備集合封閉性，因?yàn)檫@時vj與vs存在回路約束，

圖5 裝配關(guān)聯(lián)圖的關(guān)聯(lián)矩陣

具備集合封閉性的頂點(diǎn)集合中任意頂點(diǎn)與集合外其它頂點(diǎn)不存在回路約束關(guān)系，因此如果最大子裝配體中所有頂點(diǎn)構(gòu)成的集合具有集合封閉性，那么此最大子裝配體與其它頂點(diǎn)也不會存在任何回路約束關(guān)系，其它子裝配體也不會因?yàn)榇俗畲笞友b配體而產(chǎn)生違背工程語義約束規(guī)則的情況。所以，具備集合封閉性的最大子裝配體可以直接作為最終的子裝配體而無需經(jīng)過工程語義約束檢測。

如果提取得到的最大子裝配體SA不具備集合封閉性，我們必須利用工程語義約束規(guī)則對它進(jìn)行檢測，具體檢測方法如下：

Step 2 判斷wi是單根線還是內(nèi)聯(lián)線，并由判斷結(jié)果分別執(zhí)行1）或2）。

（1）若iw是單根線，則進(jìn)行端口約束檢測，即判斷wi另一端是否存在于其它未被預(yù)裝的接插件內(nèi)，若是則把wi從SA中刪除，否則保留wi。

（2）若wi是內(nèi)聯(lián)線，判斷wi所在內(nèi)聯(lián)回路是否屬于SA的主件c1中的內(nèi)聯(lián)回路，若不是則把wi從SA中刪除，同時判斷wi所在內(nèi)聯(lián)回路的導(dǎo)線是否滿足導(dǎo)線約束，若不滿足，把iw所在的接插件也從SA中刪除。

Step 3 取出SA中下一根未處理的導(dǎo)線wj，重復(fù)，Step 2直至把SA中所有的導(dǎo)線處理完畢，這時SA便是最終的子裝配體。

4）預(yù)裝配規(guī)劃算法

根據(jù)前文所述，得到下面完整的線束預(yù)裝配規(guī)劃算法：

Step 1 由線束圖紙G( V, E)構(gòu)造初始關(guān)聯(lián)矩陣M( G)；

Step 2 在M( G)中選取一個主件頂點(diǎn)vi，同時提取出vi對應(yīng)的最大子裝配體SiA；

Step 3 對SiA進(jìn)行工程語義約束檢測，得到最終的子裝配體SA，并更新M( G)；

Step 4 重復(fù)Step2至Step3，直到M( G)中所有元素的值均為2。

3 應(yīng)用實(shí)例

本文所述的思想已經(jīng)在由作者所在研究團(tuán)隊(duì)基于Object ARX進(jìn)行開發(fā)的線束工藝設(shè)計(jì)軟件系統(tǒng)中得到驗(yàn)證。系統(tǒng)把線束圖紙讀入后，用戶只需要從菜單執(zhí)行“預(yù)裝設(shè)計(jì)”命令，便能夠自動生成各個子裝配體，并保存到指定目錄中。

圖6為某汽車車型簡化的線束圖紙，其中包含了9個接插件，內(nèi)聯(lián)回路為（11，21，32）、（43，50，16）、（71，82，91）、（104，89，13）、（143，152，160），其中101號導(dǎo)線為單根線，其兩端分別接于接插件HL02FB-M和HNMWP02FGYM-LOCK端口內(nèi)。

經(jīng)過預(yù)裝配自動規(guī)劃后依次得到的子裝配體如圖7(a)、圖7 (b)、圖7 (c)所示，其中圖7 (b)、圖7 (c)為后插型子裝配體，圖7 (a)為非后插型子裝配體。

圖6 線束圖紙

圖7 子裝配體

4 總結(jié)與展望

本文針對線束預(yù)裝配設(shè)計(jì)的特點(diǎn)，總結(jié)了線束預(yù)裝配過程中的工程語義約束信息，并建立裝配關(guān)聯(lián)圖模型，通過主件選取、最大子裝配體提取以及工程語義約束檢測來自動完成對整個線束圖紙的預(yù)裝配序列規(guī)劃。最后的實(shí)例表明該方法是有效可行的，能較好的解決大線束圖紙中預(yù)裝配序列規(guī)劃問題。本方法的最大優(yōu)點(diǎn)是整個預(yù)裝配序列規(guī)劃能夠自動完成，不需要與用戶進(jìn)行交互。然而由本文方法得到的裝配序列僅是所有可行裝配序列中的一個，并不能確保其是最優(yōu)的，原因在于當(dāng)多個接插件的“內(nèi)聯(lián)度”和“單聯(lián)度”都相等時，主件選擇具有一定的隨機(jī)性。此外，若遇到線束圖紙中存在某些極端情況，如大接插件與其它所有接插件均有回路約束關(guān)系時，該算法會把整個線束作為一個子裝配體。如果能夠進(jìn)一步總結(jié)線束預(yù)裝配過程中的其他約束，如設(shè)定主件的內(nèi)聯(lián)回路數(shù)目閾值，考慮壓接位置約束、子裝配體數(shù)目約束等，將使自動預(yù)裝配規(guī)劃的結(jié)果更符合工程設(shè)計(jì)上的要求，進(jìn)一步提高裝配的效率。

[1]王敬品, 胡志勇, 藺吉順, 等. 基于遺傳算法的裝配序列規(guī)劃[J]. 機(jī)械工程與自動化, 2008, (2): 9-11.

[2]Shan Hongbo, Li Shuxia, Gong Degang, et al. Genetic simulated annealing algorithm-based assembly sequence planning [C]//Technology and Innovation Conference, 2006: 1573-1579.

[3]張艷萍, 李從東. 集成環(huán)境下基于割集的裝配順序生成算法研究[J]. 機(jī)械設(shè)計(jì), 2004, 21(9): 10-13.

[4]Mello L S, Sanderson A C. A correct and complete algorithm for the generation of mechanical assembly sequences [J]. IEEE Transactions on Robotics and Automation, 1991, 7(2): 228-240.

[5]朱海平, 邵新宇, 張國軍. 基于自動拆卸過程的裝配序列生成方法研究[J]. 工程圖學(xué)學(xué)報(bào), 2008, 29(4):27-32.

[6]楊培林, 朱 均, 陳曉南. 裝配規(guī)劃中裝配體的表達(dá)及子裝配的識別[J]. 西安交通大學(xué)學(xué)報(bào), 1999,33(12): 40-43, 60.

[7]張 勐, 古天龍. 基于帶權(quán)無向連接圖的子裝配體識別方法研究[J]. 桂林電子科技大學(xué)學(xué)報(bào), 2008,28(1): 18-22.

[8]何士雙, 程光春, 吳 黃, 等. 汽車線束預(yù)裝配過程控制研究[C]//計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展(下), 2007:957-960.