雷康華 翟曉慶 華順剛

摘要：裝配序列生成是計算機(jī)輔助工藝規(guī)劃的重要環(huán)節(jié)。在VS2005環(huán)境下，對Pro/E進(jìn)行了產(chǎn)品裝配序列生成的二次開發(fā)，求出產(chǎn)品的拆卸序列，進(jìn)一步求反獲得產(chǎn)品的裝配序列。首先，提取零件特征信息和空間位姿信息并在自動拆卸過程中對零件進(jìn)行干涉檢查，建立干涉表；然后，根據(jù)零件間干涉關(guān)系選擇拆卸方向，生成可行的裝配序列。在此基礎(chǔ)上，對位置特殊、沿單一拆卸方向不能拆卸的零件采用Bi-RRT（雙向快速擴(kuò)展隨機(jī)樹）算法進(jìn)行路徑規(guī)劃，實現(xiàn)復(fù)雜環(huán)境中零件的拆卸，并以實例論證了方法的有效性。

關(guān)鍵詞：裝配序列；干涉檢查；Bi-RRT算法；拆卸路徑規(guī)劃

中圖分類號：TP202 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）21-0160-05

Application of Bi-RRT Algorithm in Assembly Sequence Generation

LEI Kang-hua1， ZHAI Xiao-qing2， HUA Shun-gang1

（1.School of Mechanical Engineering， Dalian University of Technology， Dalian 116024， China； 2. School of Machinery Engineering， Shandong University of Technology， Zibo 255049， China）

Abstract： Assembly sequence generation is an important segment of computer-aided process planning. The paper carries out the secondary development of Pro / E for disassembly sequence and inverts the sequence to get the assembly sequence under the VS2005. First， the information of the feature and space pose of the parts is extracted and the interference table of parts is established after the interference checking during the process of automatic disassembly. Second， the feasible assembly sequence is generated with the disassembly direction of part chosen built on the interference relationship among the parts. On that basis， the Bi-RRT （Bi-directional Rapidly Exploring Random Tree） algorithm is utilized for the path planning of the parts that cant be removed along a single direction because of their special positions. Then， the parts in the complex environment are disassembled successfully and the method using Bi-RRT algorithm is demonstrated effective according to the examples.

Key words： assembly sequence； interference checking； Bi-RRT algorithm； disassembly path planning

裝配序列的確定是產(chǎn)品裝配工藝規(guī)劃的基本任務(wù)，可行的裝配序列不僅要求零件裝配過程中不會發(fā)生干涉，而且最好是操作簡單、裝配耗時少、成本低等。近年來，機(jī)械產(chǎn)品愈來愈復(fù)雜，傳統(tǒng)裝配方法適用性降低，如何自動生成裝配序列成為研究熱點(diǎn)，并取得了階段性成果。王峻峰[1]等通過自動拆卸仿真生成表達(dá)拆卸干涉關(guān)系的干涉矩陣，在此基礎(chǔ)上利用蟻群算法實現(xiàn)多零件拆卸序列的生成；張秀芬[2，3]等采用拆卸賦權(quán)混合圖與粒子群優(yōu)化算法相結(jié)合的方法，實現(xiàn)了裝配體拆卸序列的快速求解；于嘉鵬[4]等提出一種基于擴(kuò)展干涉矩陣的幾何可拆性判別方法，對單個零件進(jìn)行可拆卸判斷，并結(jié)合蟻群算法成功確定裝配體拆卸序列；劉志峰[5]等在構(gòu)建模型拆卸約束圖的基礎(chǔ)上，運(yùn)用模擬退火粒子群優(yōu)化算法，實現(xiàn)對模型拆卸序列的求解。

本文基于拆卸并結(jié)合RRT算法實現(xiàn)裝配序列求解。首先通過拆卸仿真對裝配體中所有零件沿單一方向進(jìn)行可拆性判斷，選擇自由零件數(shù)較多的方向為零件的拆卸方向，完成裝配體零件的拆卸；其次，對于位置特殊的零件結(jié)合Bi-RRT算法，根據(jù)運(yùn)動規(guī)劃搜索較優(yōu)的拆卸路徑進(jìn)行拆卸。該方法解決了零件沿單一方向不能完全拆卸的局限性，適用性強(qiáng)。

1 裝配體中零件干涉關(guān)系判斷

本文通過MFC和Pro/Toolkit開發(fā)包實現(xiàn)對Pro/E的二次開發(fā)，程序驅(qū)動裝配體模型中每個零件以既定步長沿幾何方向移動，移動過程中對零件進(jìn)行干涉檢查，建立零件干涉表。

1.1 提取模型裝配信息

為了提取裝配信息，需要對裝配體進(jìn)行特征遍歷，在Pro/Toolkit開發(fā)包中，遍歷實體特征的庫函數(shù)是ProSolidFeatVisit（），其原型函數(shù)如下所示：

ProSolidFeatVisit （ ProSolid p_handle，

ProFeatureVisitAction visit_action，

ProFeatureFilterAction filter_action，

ProAppData app_data）；

上述函數(shù)有4個參數(shù)，第1個參數(shù)表示被訪問模型的實體句柄，該句柄可通過調(diào)用庫函數(shù)ProMdlCurrentGet（）獲??；第2個是特征訪問動作函數(shù)，參數(shù)visit_action是動作函數(shù)的函數(shù)名；第3個是特征過濾函數(shù)，參數(shù)filter_action是過濾函數(shù)的函數(shù)名，該函數(shù)對訪問的特征類型進(jìn)行過濾，只有符合訪問條件的特征才被傳遞到動作函數(shù)中；第4個是結(jié)構(gòu)體類型指針，用于存儲提取的特征信息。函數(shù)在執(zhí)行時自動循環(huán)調(diào)用訪問動作函數(shù)和特征過濾函數(shù)，直至訪問完模型中所有的特征。本文利用該函數(shù)遍歷了模型中所有特征的id，并根據(jù)id獲取各個零部件的名稱和裝配路徑，進(jìn)而獲取零部件的位姿信息。

Pro/Toolkit開發(fā)中利用轉(zhuǎn)換矩陣表示Pro/E中模型的位姿信息[6]，矩陣定義如下：

[P=xv1xv2xv30yv1yv2yv30zv1zv2zv30xsyszs1] （1）

上述矩陣中前3行和3列構(gòu)成的3×3階子矩陣描述零件的姿態(tài)信息，改變子矩陣中變量可以產(chǎn)生比例、旋轉(zhuǎn)等幾何變換；矩陣[XsYsZs]描述零件的位置信息，改變[Xs]，[Ys]，[Zs]可以實現(xiàn)零件的平移。零部件從初始位置平移[dx]，[dy]，[dz]后的坐標(biāo)（[x，y，z]）可表示為：

[xyz1=dxdydz1*P] （2）

本文通過調(diào)用Pro/Toolkit開發(fā)庫函數(shù)ProAsmComppathTrfGet（）得到零件在裝配體中的初始位姿矩陣P，調(diào)用函數(shù)ProAsmComppathTrfSet（）設(shè)置平移后的矩陣為零件當(dāng)前的位姿矩陣，從而實現(xiàn)零件的平移。

1.2 獲取零件干涉關(guān)系

編程實現(xiàn)裝配體中每個零件沿方向集{X，-X，Y，-Y，Z，-Z }移動，移動過程中對裝配體進(jìn)行干涉檢查，建立干涉情況表。干涉表建立流程如圖1所示：

1） 獲取裝配體的最大長、寬、高；

調(diào)用Pro/Toolkit接口函數(shù)ProSolidOutLineGet（P_solid，point[2]），獲取裝配體模型實體包圍盒對角兩點(diǎn)的坐標(biāo)，X軸方向的最大距離[Lx=|points[1][0]- points[0][0]|]；Y軸方向的最大距離[Ly=|points[1][1]- points[0][1]|]；Z軸方向的最大距離[Lz=|points[1][2]- points[0][2]|]。

2） 從遍歷所得的模型數(shù)組中依次選擇零件，獲取零件的位姿信息；

3）零件沿方向集{X，-X，Y，-Y，Z，-Z}中的一個方向移動，移動最大距離L由移動方向決定：如果移動方向是X或-X方向，[L=Lx]；如果移動方向是Y或-Y方向，[L=Ly]；移動方向是Z或-Z方向，[L=Lz]；移動步長為L/100；

4）單步平移時進(jìn)行干涉檢查，判斷零件在當(dāng)前狀態(tài)下與其他零件是否干涉，干涉則停止移動，重新回到初始位置，執(zhí)行3）繼續(xù)下一方向，記錄該零件在移動方向上的干涉情況。干涉檢查調(diào)用Pro/E接口函數(shù)

pro_compute_global_interference （p_model， PROINTERF_SOLID_ONLY， &n_intf_parts， &intf_parts， &intf_part_surfs， &n_part_surfs）；

5）判斷零件在某一方向移動距離是否達(dá)到最大長度L，若是則執(zhí)行6），否則繼續(xù)執(zhí)行4）；

6）判斷零件是否沿6個方向移動完畢，若是則執(zhí)行7），否則返回執(zhí)行3）選擇下一移動方向；

7）判斷裝配體中的零件是否移動完畢，若是則執(zhí)行8），否則返回執(zhí)行2）選擇下一零件；

8）輸出干涉關(guān)系；

2 裝配序列生成

生成裝配序列流程如下：1）實際拆卸時，基礎(chǔ)件是最后拆除零件，根據(jù)零件間約束關(guān)系及位置關(guān)系選出模型的基礎(chǔ)件，不進(jìn)行拆卸判斷，如底座、箱體之類。2）選取自由零件個數(shù)最多的方向作為零件的優(yōu)先拆卸方向；3）拆卸所選方向上的所有零件，并依據(jù)拆卸順序給零件按順序重命名；4）循環(huán)執(zhí)行2）、3）步，直至裝配體拆卸完成，生成可行的零件拆卸序列?；凇翱刹鸺纯裳b”的思想，裝配序列即是裝配模型拆卸序列的逆序列。

本文采用插銷裝配體作為例子。該裝配體在Pro/E中建模完成，共有12個零件組成。本文通過對Pro/E二次開發(fā)，實現(xiàn)零件的自動拆卸仿真：采用遍歷模型樹的方法獲取所有零件的特征信息、位姿信息存儲在零件數(shù)組中，并按照遍歷所得先后順序?qū)α慵M(jìn)行編號。

裝配體中，基礎(chǔ)件是最后一個拆卸的零件，如底座，箱體等，裝配體拆卸前首先要確定其基礎(chǔ)件。提取所有零件的屬性信息，選擇體積最大的零件作為模型的基礎(chǔ)件，在Pro/E窗口中高亮顯示，若因零件體積近似而引起選擇誤差時結(jié)合人工交互修正。從整體零件數(shù)組中剔除基礎(chǔ)件，余下零件沿幾何方向進(jìn)行拆卸仿真，建立零件干涉表，0表示該零件在某方向移出裝配體實體邊界盒的過程中與其他零件不干涉，1表示干涉。本例中1號零件被選作基礎(chǔ)件，剔除1號零件后零件的干涉情況如表1所示。

由表1知Y方向自由零件個數(shù)最多，所以Y為優(yōu)先拆卸方向，沿Y方向拆卸零件集{5，6，7，8，9，10，11，12}，圖2表示裝配體第一輪拆卸完成后狀態(tài)。從零件數(shù)組中剔除已拆卸零件，對剩余零件重新進(jìn)行干涉判斷，由表2知，X和-X方向的自由零件個數(shù)相同，X方向拆卸零件集為{4，3}，-X方向零件拆卸集為{4，2}。實際拆卸時，零件間存在拆卸順序約束，本例中零件4和2存在裝配關(guān)系，零件2是零件4的基礎(chǔ)件，零件4要先于零件2拆卸。本文通過比較零件在六個方向拆卸時受到干涉的數(shù)量，得出零件2受到的干涉最多，說明零件2的配合關(guān)系數(shù)最多，故零件2應(yīng)最后拆卸，X方向為優(yōu)先拆卸方向，所以拆卸序列為[{5，6，7，8，9，10，11，12}→{4，3}→2]，對序列求反即可得模型的裝配序列。

一般情況下，運(yùn)用上述方法，可將裝配體中零件沿單一方向依次完全拆卸，但實際拆卸時，該方法往往有一定的局限性，如圖5所示，裝配體有4個零件，分別是臺燈體、燈管、插口和管蓋。運(yùn)用上述方法對裝配體中零件進(jìn)行拆卸仿真，建立干涉表如表3，由于零件位置特殊，所有零件沿單一方向拆卸時都發(fā)生干涉，上述方法無法完成零件拆卸。故而，本文在原方法的基礎(chǔ)上運(yùn)用快速擴(kuò)展隨機(jī)樹RRT（Rapidly-exploring random tree）算法[7]對零件進(jìn)行運(yùn)動規(guī)劃，搜索零件可行的拆卸路徑，實現(xiàn)對目標(biāo)零件的拆卸。

3 基于Bi-RRT算法的零件拆卸

快速擴(kuò)展隨機(jī)樹（RRT）算法是近幾年發(fā)展起來的一種基于隨機(jī)采樣的單一搜索路徑規(guī)劃的算法，該算法的優(yōu)點(diǎn)是不用對空間建模，減少了路徑搜索計算量，縮短了運(yùn)算時間，提高了效率，在解決高維空間和復(fù)雜環(huán)境中機(jī)器人路徑規(guī)劃問題上得到了廣泛的應(yīng)用?；谄湓跈C(jī)器人路徑規(guī)劃上的優(yōu)越性，本文采用基于RRT算法[8]的運(yùn)動規(guī)劃為裝配體零件尋找一條可到達(dá)裝配體外自由空間的無干涉路徑。

3.1 經(jīng)典RRT算法

隨機(jī)樹構(gòu)建過程如圖6所示，設(shè)[Tk]為包含k個節(jié)點(diǎn)的隨機(jī)樹，C-free為無碰撞自由狀態(tài)空間，定義qstart為初始位置即起點(diǎn)，[ qgoal∈Cfree]為目標(biāo)位置即終點(diǎn)。Qrand為自由空間中隨機(jī)選取點(diǎn)，且[qrand∈Cfree]找出[Tk]中距離qrand最近的點(diǎn)qnearest，在qnearest和qrand的連線上求一點(diǎn)qnew，滿足條件[qnew∈Cfree]且Dinstance（qnearest， qnew）=d，d>0，是RRT生長的最小步長。如果qnew存在，則在[Tk]上增加一個新節(jié)點(diǎn)，否則重新選取qrand。在既定迭代次數(shù)內(nèi)，如果新節(jié)點(diǎn)距離目標(biāo)點(diǎn)距離小于閾值[ε]，算法搜索成功[9，10]。如圖7所示，在VC6.0上采用RRT算法在具有不規(guī)則障礙物環(huán)境中規(guī)劃出的仿真軌跡圖。

3.2 雙向搜索隨機(jī)樹（Bi-RRT）算法

RRT算法對狀態(tài)空間隨機(jī)采樣，搜索無目標(biāo)性，每次隨機(jī)采樣生成的隨機(jī)樹不盡相同，搜索樹無任何目標(biāo)導(dǎo)向性，收斂速度緩慢。為了改進(jìn)搜索效率，在經(jīng)典RRT算法的基礎(chǔ)上，本文采用Bi-RRT算法進(jìn)行路徑搜索[11，12]，它是在RRT-connect算法思想的基礎(chǔ)上提出來的，采取從起點(diǎn)和終點(diǎn)分別擴(kuò)展隨機(jī)樹并相向擴(kuò)展的方式，克服了RRT-connect算法易陷入局部極小值的缺點(diǎn)，效率更高，應(yīng)用更廣。Bi-RRT節(jié)點(diǎn)構(gòu)建過程如圖8所示，以起點(diǎn)qstart1為根節(jié)點(diǎn)，以隨機(jī)點(diǎn)qrand為臨時目標(biāo)點(diǎn)擴(kuò)展Tree_1，以終點(diǎn)qgoal為根節(jié)點(diǎn)，以新產(chǎn)生的節(jié)點(diǎn)qnew1為臨時目標(biāo)點(diǎn)擴(kuò)展Tree_2，并在下一輪擴(kuò)展時交換擴(kuò)展順序。這樣一來，解決了經(jīng)典RRT算法搜索無目標(biāo)性的問題，提高了搜索效率，Bi-RRT路徑搜索步驟如下：

1）定義所有參數(shù)，初始化隨機(jī)樹Tree_1、Tree_2，qstart1添加到Tree_1上，qgoal添加到Tree_1上。

2）調(diào)用隨機(jī)節(jié)點(diǎn)生成函數(shù)，在自由狀態(tài)空間內(nèi)產(chǎn)生一個隨機(jī)點(diǎn)qrand。

3）在Tree_1上搜索距離qrand最近的點(diǎn)qnearest1。調(diào)用函數(shù)計算Tree_1上所有節(jié)點(diǎn)與qrand的距離，找出最小值。

4）調(diào)用擴(kuò)展節(jié)點(diǎn)函數(shù)擴(kuò)展新節(jié)點(diǎn)qnew1，判斷零件在點(diǎn)qnew1上與其他零件是否干涉，不干涉則把點(diǎn)qnew1添加到Tree_1上，記錄其父節(jié)點(diǎn)后執(zhí)行下一步，否則返回到2）。

5）在Tree_2上搜索距離qnew1的最近點(diǎn)qnearest2。

6）調(diào)用擴(kuò)展節(jié)點(diǎn)函數(shù)朝著Tree_1擴(kuò)展新節(jié)點(diǎn)方向擴(kuò)展節(jié)點(diǎn)qnew2，判斷零件在點(diǎn)qnew2上與其他零件是否干涉，不干涉則把點(diǎn)qnew2添加到Tree_2上，記錄其父節(jié)點(diǎn)后執(zhí)行下一步，否則執(zhí)行9）。

7）判斷Tree_1、Tree_2是否相遇，即Distance（qnew1， qnew2）是否小于一個給定閾值[ε]，若小于則停止搜索路徑點(diǎn)，執(zhí)行下一步，否則執(zhí)行9）。

8）反向搜索qnew1和qnew2的父節(jié)點(diǎn)得到路徑P。

9）交換T1和T2，改變其先后擴(kuò)展順序，返回執(zhí)行2）。

為了使算法可控，在Step10中設(shè)置迭代次數(shù)上限，如果在設(shè)定的次數(shù)內(nèi)，兩棵樹沒有相遇，算法返回失敗。Bi-RRT算法偽代碼如下：

1 Tree_1， Tree_2←Tree_init （qstart， qgoal）；

14←for i=1 to l do

3 qrand← Randnode （）；

4 qnearest1 ←Nearest_node_get （Tree_1， qrand）；

5 qnew1←Tree_1Extend （qnearest1， qrand， d）；

6 if qnew1[≠]NULL， then

7 qnearest2 ←Nearest_node_get （Tree_2， qnew1）；

8 qnew2 ←Tree_2Extend （qnearest2， qnew1， d）；

9 if qnew2[≠]NULLthen

10 Tree_1←Tree_1+qnew1；

11 Tree_2←Tree_2+qnew2；

12 if ||qnew1-qnew2||<[ε] then

10 P←ExtractPath （Tree_1， qnew1， Tree_2， qnew2）；

11 else Swap （Tree_1， Tree_2）；

12 end；

13 end；

14 Return 0；

4 Bi-RRT算法實現(xiàn)

為了驗證算法的可靠性，算法實現(xiàn)圖5模型中零件的路徑規(guī)劃。以零件在裝配體中的空間坐標(biāo)為初始點(diǎn)，以自由狀態(tài)空間中的一點(diǎn)為目標(biāo)點(diǎn)，搜索一條從初始點(diǎn)到目標(biāo)點(diǎn)的有效路徑作為零件的拆卸路徑。以裝配體中燈管零件的拆卸為例，拆卸關(guān)鍵點(diǎn)狀態(tài)如圖9所示，燈管在燈槽內(nèi)水平向左移出插口后斜向下方移出燈槽，最終到達(dá)目標(biāo)位置，生成拆卸路徑，裝配體中零件拆卸路徑如圖10所示。

同時，為了驗證算法的適用性，本文模擬封閉箱體中零件的拆卸，如圖11所示，箱體頂端有一拆卸窗口，待拆卸的零件在擋板的下方，待拆卸零件需要經(jīng)拆卸窗口才能移出箱體，為了便于說明，將箱體從一端剖開。本例中目標(biāo)零件的初始位置為隨機(jī)樹根結(jié)點(diǎn)，拆卸窗口上方一點(diǎn)為目標(biāo)點(diǎn)，通過設(shè)定零件移動步長和與環(huán)境中障礙物的碰撞干涉檢測擴(kuò)展樹節(jié)點(diǎn)，逐步接近目標(biāo)位置。拆卸過程t特殊位置狀態(tài)如圖12所示，零件先向上移動至擋板下方后水平向右移動，移出擋板范圍后繼續(xù)向上運(yùn)動，最終到達(dá)目標(biāo)位置，生成拆卸路徑如圖13所示。

5 結(jié)束語

本文在VS2005環(huán)境下對Pro/E進(jìn)行裝配序列生成的二次開發(fā)，獲取裝配體中零件的特征信息、位姿信息，實現(xiàn)了基于自動拆卸仿真與動態(tài)干涉檢查的可行裝配序列生成。在此基礎(chǔ)上，研究了基于RRT的路徑規(guī)劃算法，并應(yīng)用雙向搜索隨機(jī)樹（Bi-RRT）算法對裝配位置特殊的零件進(jìn)行路徑規(guī)劃，實現(xiàn)對目標(biāo)零件的拆卸，有效地解決了目標(biāo)零件沿單一方向無法拆卸的問題，適用性強(qiáng)，并在Pro/E平臺上得到了實現(xiàn)。

參考文獻(xiàn)：

[1] 王俊峰，李世奇，劉繼紅. 面向綠色制造的產(chǎn)品選擇拆卸技術(shù)研究[J]. 計算機(jī)集成制造系統(tǒng)，2007，13（6）： 1097-1102.

[2] 張秀芬，張樹有，伊國棟，等. 面向復(fù)雜機(jī)械產(chǎn)品的目標(biāo)選擇性拆卸序列規(guī)劃方法[J]. 機(jī)械工程學(xué)報，2010，46 （11）： 172-178.

[3] 張秀芬，張樹有. 基于粒子群算法的產(chǎn)品拆卸序列規(guī)劃方法[J]. 計算機(jī)集成制造系統(tǒng)，2009，15（3）： 508-514.

[4] 于嘉鵬，邢宇飛. 基于擴(kuò)展干涉矩陣的幾何可拆卸性判別方法[J]. 機(jī)械工程學(xué)報，2011，47（21）： 146-148.

[5] 劉志峰，楊德軍. 基于模擬退火粒子群優(yōu)化算法的拆卸序列規(guī)劃[J].合肥工業(yè)大學(xué)學(xué)報，2011，34（2）： 161-165.

[6] 吳立軍，陳波等. Pro/ENGINEER二次開發(fā)技術(shù)基礎(chǔ)[M]. 北京：電子工業(yè)出版社，2006：153-154.

[7] 趙柏萱，劉檢華. 一種基于運(yùn)動規(guī)劃的選擇拆卸序列規(guī)劃技術(shù)[J]. 機(jī)械工程學(xué)報，2014，50（7）： 136-144.

[8] X.Z.Zang， W.T. Yu， L.Zhang， et al. Path Planning Based on Bi-RRT Algorithm for Redundant Manipulator[C]//2015 International Conference on Electrical， Automation and MechanicalEngineering. Atlantis Press， 2015， 189-191.

[9] 周偉. 基于CATIA電子樣機(jī)零件可達(dá)性及拆卸路徑規(guī)劃研究[D]. 秦皇島：燕山大學(xué)，2013： 27-37.

[10] 王全. 基于RRT的全局路徑規(guī)劃方法及應(yīng)用研究[D]. 長沙：國防科學(xué)技術(shù)大學(xué)，2014.

[11] D. Berenson， SS. Srinivasa， D. Ferguson， et al. Manipulation planning on constraintmanifolds[C]//Robotics and Automation， 2009. ICRA'09， IEEE International Conference on. IEEE， 2009： 625-632.

[12] 王凡.一種基于RRT_ConCon改進(jìn)的路徑規(guī)劃算法[J]. 大連理工大學(xué)學(xué)報，2014，54（6）： 637-643.