熊 晶 段曉坤

（常州信息職業(yè)技術(shù)學(xué)院，常州 213164）

產(chǎn)品裝配路徑規(guī)劃是產(chǎn)品裝配工藝設(shè)計(jì)的重要內(nèi)容之一。尤其是復(fù)雜產(chǎn)品，它的零部件數(shù)量多，結(jié)構(gòu)復(fù)雜，內(nèi)部空間緊湊。在狹窄空間內(nèi)為待裝配的零部件計(jì)算出一條從裝配起點(diǎn)到裝配終點(diǎn)的無碰撞路徑，是虛擬裝配設(shè)計(jì)的難點(diǎn)之一。

基于幾何圖的路徑規(guī)劃算法，如柵格法[1]，在路徑搜索之前，先對(duì)整個(gè)求解空間進(jìn)行單元分割，并用分割單元對(duì)障礙空間和自由空間進(jìn)行描述，再利用基于圖的搜索算法，如A*算法[2-3]，在所構(gòu)建的環(huán)境圖中搜索有效路徑，有利于獲得優(yōu)化路徑解。但是，這種方式用于狹窄三維空間內(nèi)的路徑求解時(shí)，分割單元的尺寸將直接決定狹窄空間內(nèi)有效節(jié)點(diǎn)的數(shù)量、求解成功率與效率。分割單元尺寸過大時(shí)，有效節(jié)點(diǎn)過少，求解困難；分割尺寸過小時(shí)，則存在組合爆炸的情況。

快速擴(kuò)展隨機(jī)樹（Rapid-exploring Random Tree，RRT）[4-5]是一種隨機(jī)采樣的路徑規(guī)劃算法，特點(diǎn)在于利用隨機(jī)性來處理C空間而無需對(duì)求解空間進(jìn)行精確計(jì)算，因而廣泛應(yīng)用于高維空間下的路徑規(guī)劃問題。但是，由于狹窄空間內(nèi)產(chǎn)品裝配時(shí)受到的空間約束較大，使用RRT算法進(jìn)行裝配路徑規(guī)劃時(shí)，隨機(jī)采樣點(diǎn)搜索到狹窄空間的概率低，路徑樹擴(kuò)展的成功率和效率都有待提高。

針對(duì)以上問題，本文結(jié)合柵格法與RRT算法的優(yōu)點(diǎn)改進(jìn)RRT算法，以待擴(kuò)展樹節(jié)點(diǎn)為中心，離散化局部空間，提出兩種運(yùn)動(dòng)策略及對(duì)應(yīng)的評(píng)價(jià)指標(biāo)，引導(dǎo)局部路徑的擴(kuò)展。

本文主要?jiǎng)?chuàng)新點(diǎn)如下。

（1）提出一種局部位移和轉(zhuǎn)動(dòng)空間的離散化方法，對(duì)待擴(kuò)展樹節(jié)點(diǎn)附近的局部空間進(jìn)行離散化設(shè)計(jì)，為路徑樹的擴(kuò)展提供多種備選位姿，以提高路徑擴(kuò)展的成功率與效率。

（2）根據(jù)裝配運(yùn)動(dòng)的難易程度，提出兩種運(yùn)動(dòng)策略及對(duì)應(yīng)的評(píng)價(jià)指標(biāo)，并依據(jù)評(píng)價(jià)指標(biāo)對(duì)備選位姿進(jìn)行選擇。

（3）基于上述局部空間離散化設(shè)計(jì)及兩種運(yùn)動(dòng)策略，提出一種改進(jìn)的快速搜索隨機(jī)樹算法，用于狹窄空間內(nèi)產(chǎn)品的虛擬裝配路徑求解。仿真實(shí)驗(yàn)表明，此方法在求解成功率和效率方面具有有效性。

1 快速搜索隨機(jī)樹算法

RRT算法的基本原理是通過均勻和隨機(jī)地搜索狀態(tài)空間來遞增地?cái)U(kuò)展路徑樹，直到路徑樹的葉節(jié)點(diǎn)到達(dá)終點(diǎn)區(qū)域。

它的搜索路徑過程主要包括以下步驟。

（1）路徑樹初始化，即將路徑起點(diǎn)（裝配起點(diǎn)） (xstar,ystar,zstar)加入路徑樹中。

（2）路徑樹擴(kuò)展。在自由空間內(nèi)生成隨機(jī)采樣位姿點(diǎn)qrand，遍歷樹中節(jié)點(diǎn)，從而找到與qrand距離最近的節(jié)點(diǎn)qnear。從qnear出發(fā)，將路徑樹朝著qrand按照某種運(yùn)動(dòng)曲線或運(yùn)動(dòng)規(guī)律運(yùn)動(dòng)一定時(shí)間到達(dá)一個(gè)新的位姿點(diǎn)qnew。若該新位姿點(diǎn)qnew滿足碰撞約束要求，則將該點(diǎn)及其局部路徑加入路徑樹中，否則重新進(jìn)行隨機(jī)采樣，直至路徑樹擴(kuò)展成功。

（3）終止判斷。若新加入路徑樹的節(jié)點(diǎn)qnew與路徑終點(diǎn)(xgoal,ygoal,zgoal)之間的距離小于基礎(chǔ)值dth，則路徑搜索成功。

2 改進(jìn)算法設(shè)計(jì)

在改進(jìn)算法中，對(duì)待擴(kuò)展樹節(jié)點(diǎn)附近的局部空間進(jìn)行離散化設(shè)計(jì)，并為路徑樹的局部擴(kuò)展提供兩種策略。每種策略提供多種備選位姿，以提高路徑樹局部擴(kuò)展的成功率和效率。

2.1 局部空間離散化設(shè)計(jì)

產(chǎn)品零部件進(jìn)行裝配時(shí)，裝配運(yùn)動(dòng)既包含移動(dòng)又包含轉(zhuǎn)動(dòng)，因此需要從移動(dòng)和轉(zhuǎn)動(dòng)兩個(gè)角度進(jìn)行局部空間的離散化設(shè)計(jì)。

以當(dāng)前路徑樹待擴(kuò)展的樹節(jié)點(diǎn)為中心所構(gòu)建的局部離散化空間，如圖1所示。該局部離散化空間由8個(gè)邊長為l的正方體單元組成。路徑樹擴(kuò)展時(shí)，只能從圖1中正方體單元的頂點(diǎn)選擇新節(jié)點(diǎn)。產(chǎn)品移動(dòng)運(yùn)動(dòng)可以選擇正方體單元的一條邊、一條面對(duì)角線或一條體對(duì)角線作為下一移動(dòng)運(yùn)動(dòng)路線軌跡。由圖1可以看出，與當(dāng)前待擴(kuò)展的樹節(jié)點(diǎn)所相鄰的頂點(diǎn)共26個(gè)。

圖1 局部位移空間的離散化設(shè)計(jì)

這種空間的離散化設(shè)計(jì)與柵格法的不同之處在于，它的計(jì)算過程并非在路徑搜索開始之前完成，而是在路徑搜索過程中進(jìn)行的，且無需對(duì)整個(gè)求解空間進(jìn)行離散化，只需對(duì)待擴(kuò)展路徑節(jié)點(diǎn)附近的局部空間進(jìn)行離散化即可。隨著路徑樹的生長，待擴(kuò)展樹節(jié)點(diǎn)與障礙物之間的距離發(fā)生變化，分割的單元尺寸l也可隨之變化。此時(shí)，可結(jié)合動(dòng)態(tài)步長策略[6]動(dòng)態(tài)地設(shè)計(jì)單元尺寸。

不同形狀的產(chǎn)品繞Z軸轉(zhuǎn)動(dòng)的離散化設(shè)計(jì)，如圖2所示。相鄰姿勢(shì)之間的轉(zhuǎn)動(dòng)角度間隔為αz，產(chǎn)品從當(dāng)前姿勢(shì)到下一姿勢(shì)只能選擇逆時(shí)針轉(zhuǎn)動(dòng)αz（記為正）或順時(shí)針轉(zhuǎn)動(dòng)αz（記為負(fù)）。

圖2 局部轉(zhuǎn)動(dòng)空間的離散化設(shè)計(jì)（繞Z軸轉(zhuǎn)動(dòng)）

假定繞軸X軸和Y軸轉(zhuǎn)動(dòng)的離散化設(shè)計(jì)，相鄰位姿之間的轉(zhuǎn)動(dòng)間隔分別為αX和αY。實(shí)際裝配運(yùn)動(dòng)中，產(chǎn)品相鄰姿勢(shì)之間的轉(zhuǎn)動(dòng)可能是僅繞單軸轉(zhuǎn)動(dòng)，也可能是繞兩軸轉(zhuǎn)動(dòng)的復(fù)合運(yùn)動(dòng)，還可能是繞X軸、Y軸、Z軸3軸轉(zhuǎn)動(dòng)的復(fù)合運(yùn)動(dòng)。它的轉(zhuǎn)動(dòng)組合共24種，結(jié)合移動(dòng)的26種情況，路徑樹的每一步擴(kuò)展有674種選擇，包含僅平移、僅轉(zhuǎn)動(dòng)和一邊移動(dòng)一邊轉(zhuǎn)動(dòng)。

為降低求解復(fù)雜性，本文只考慮相鄰位姿之間僅進(jìn)行平移運(yùn)動(dòng)和繞單根軸轉(zhuǎn)動(dòng)的情況。

2.2 裝配路徑規(guī)劃的運(yùn)動(dòng)策略與評(píng)價(jià)指標(biāo)

為進(jìn)一步提高求解速度，根據(jù)實(shí)際裝配時(shí)操作的難易程度，將路徑裝配分為僅平移（26種情況）和僅轉(zhuǎn)動(dòng)（6種情況）兩種運(yùn)動(dòng)策略，其中將僅平移優(yōu)先為最高級(jí)。進(jìn)行裝配路徑規(guī)劃時(shí)，按照優(yōu)先級(jí)的高低順序進(jìn)行選擇。當(dāng)高一級(jí)的運(yùn)動(dòng)策略中的幾種情況均不滿足要求時(shí)，再選擇低一級(jí)的運(yùn)動(dòng)策略。

同一運(yùn)動(dòng)策略中，有多種備選位姿，需要根據(jù)評(píng)價(jià)指標(biāo)對(duì)各備選位姿進(jìn)行評(píng)價(jià)，并根據(jù)評(píng)價(jià)指標(biāo)進(jìn)行排序和選擇備選位姿。若該備選位姿通過碰撞檢測(cè)，則將其加入路徑樹中，否則將其刪除，并更新備選位姿，再依據(jù)剩余備選位姿的排序重新選擇，直至有新節(jié)點(diǎn)加入路徑樹中。若某一運(yùn)動(dòng)策略中的所有備選位姿均不滿足要求，則選擇低一級(jí)的運(yùn)動(dòng)策略，并按該策略的評(píng)價(jià)指標(biāo)對(duì)備選位姿進(jìn)行評(píng)價(jià)、排序、選擇和檢測(cè)。

在僅平移運(yùn)動(dòng)策略中，從當(dāng)前位姿至備選位姿均為僅平移運(yùn)動(dòng)，且平移距離均為分割單元正方體的邊長l，即從裝配起點(diǎn)經(jīng)當(dāng)前位姿至各備選位姿所產(chǎn)生的移動(dòng)累計(jì)距離一致，但各備選位姿至終點(diǎn)位姿的實(shí)際距離不一致。以備選位姿至終點(diǎn)位姿的直線距離為僅平移運(yùn)動(dòng)策略的評(píng)價(jià)指標(biāo)，備選位姿i評(píng)價(jià)指標(biāo)為：

式中：i=1,2,…,26，表示備選位姿編號(hào)；(xi1,yi1,zi1)表示備選位姿坐標(biāo)；(xgoal,ygoal,zgoal)表示終點(diǎn)坐標(biāo)；Pi1越小，表明與終點(diǎn)越近，有利于加快路徑搜索進(jìn)程。

在僅轉(zhuǎn)動(dòng)策略中，從當(dāng)前位姿至備選位姿均為僅轉(zhuǎn)動(dòng)運(yùn)動(dòng)，轉(zhuǎn)動(dòng)的方向只能是正轉(zhuǎn)或反轉(zhuǎn)，且位姿角度差只能是αX、αY或αZ。僅轉(zhuǎn)動(dòng)策略中優(yōu)先選擇正轉(zhuǎn)且轉(zhuǎn)動(dòng)角度最小的備選位姿。若αX、αY或αZ角度值相等，則隨機(jī)選擇。

2.3 改進(jìn)算法的流程設(shè)計(jì)

改進(jìn)算法的流程如圖3所示。本算法基于“可拆即可裝”的思路[7]，將裝配終點(diǎn)設(shè)置為路徑起點(diǎn)，將裝配起點(diǎn)設(shè)置為路徑終點(diǎn)，求解拆卸路徑。它只需將零部件移出產(chǎn)品包圍盒即可，無需關(guān)注拆卸終點(diǎn)零部件的姿態(tài)。獲得拆卸路徑后，對(duì)運(yùn)動(dòng)路徑進(jìn)行重新排序，即可獲得裝配路徑。

圖3 改進(jìn)算法流程圖

進(jìn)行隨機(jī)采樣時(shí)，以一定的概率p選擇路徑終點(diǎn)為隨機(jī)采樣點(diǎn)。獲得隨機(jī)采樣點(diǎn)后，路徑樹首先朝隨機(jī)采樣點(diǎn)擴(kuò)展。若路徑樹朝著隨機(jī)采樣點(diǎn)擴(kuò)展失敗，表明當(dāng)前樹節(jié)點(diǎn)在障礙物附近，則啟動(dòng)局部空間離散化，對(duì)障礙物附近的局部路徑提供多種備選位姿。獲得與qrand距離最近的樹節(jié)點(diǎn)qnear后，隨即以qnear現(xiàn)在的位置和姿態(tài)為中心進(jìn)行局部位移和局部轉(zhuǎn)動(dòng)空間的離散化，獲得多個(gè)備選位姿。按照運(yùn)動(dòng)策略的優(yōu)先級(jí)順序，先對(duì)僅平移策略中的備選位姿進(jìn)行評(píng)價(jià)、排序、選擇及碰撞干涉檢驗(yàn)，直至路徑樹局部擴(kuò)展成功。若僅平移策略中的備選位姿均不滿足要求，則對(duì)僅轉(zhuǎn)動(dòng)策略中的備選位姿進(jìn)行評(píng)價(jià)、排序、選擇及碰撞干涉檢驗(yàn)，直至路徑樹局部擴(kuò)展成功。若僅轉(zhuǎn)動(dòng)策略中的備選位姿仍不滿足要求，則重新進(jìn)行隨機(jī)采樣點(diǎn)的選擇，并重復(fù)以上過程，直至有備選位姿加入路徑樹，完成一次擴(kuò)展樹的過程。路徑樹多次擴(kuò)展成功，直至擴(kuò)展到拆卸路徑終點(diǎn)附近，拆卸路徑搜索過程結(jié)束。路徑節(jié)點(diǎn)重新排序后，返回從裝配起點(diǎn)至終點(diǎn)的路徑。

3 仿真驗(yàn)證與結(jié)果分析

為驗(yàn)證所提出方法的有效性，對(duì)引擎活塞桿帽裝配路徑進(jìn)行規(guī)劃仿真實(shí)驗(yàn)。裝配起點(diǎn)與終點(diǎn)如圖4所示，其中裝配終點(diǎn)附近約束強(qiáng)烈，是典型的狹窄空間下的裝配路徑規(guī)劃問題。

圖4 活塞桿帽裝配路徑規(guī)劃的起點(diǎn)與終點(diǎn)

將本文算法與RRT算法和Biased-RRT[8]算法比較后，可得所提方法適用于狹窄空間內(nèi)復(fù)雜產(chǎn)品的裝配路徑規(guī)劃問題。在仿真實(shí)驗(yàn)中，三維空間在OX、OY和OZ這3個(gè)方向上的范圍均為0～500 mm，其他仿真參數(shù)如表1所示。

表1 仿真參數(shù)設(shè)置表

3種算法在解決如圖4所示的裝配路徑問題時(shí)的表現(xiàn)如表2所示。由于RRT算法具有隨機(jī)性，故表2中成功率指的是算法重復(fù)執(zhí)行100次時(shí)搜索成功次數(shù)與總次數(shù)的比值。搜索時(shí)，設(shè)定每次執(zhí)行時(shí)最大允許迭代次數(shù)為100，在允許的迭代次數(shù)內(nèi)返回裝配路徑即表示此次搜索成功，超過迭代次數(shù)還未返回路徑則表明路徑搜索失敗。

表2 算法表現(xiàn)對(duì)比表

從表2可知，改進(jìn)算法找到路徑的成功率和效率最高。相比于RRT算法和Biased-RRT算法，本文提出的改進(jìn)算法先朝向隨機(jī)采樣點(diǎn)擴(kuò)展，若擴(kuò)展不成功再進(jìn)行局部離散化，為局部路徑的擴(kuò)展提供了多種選擇。只要存在可擴(kuò)展點(diǎn)，則該局部路徑即可擴(kuò)展成功。這一策略有利于提高狹窄空間中路徑擴(kuò)展的成功率和效率。

改進(jìn)算法獲得的裝配路徑，如圖5所示。該裝配路徑是由所獲得的拆卸路徑各節(jié)點(diǎn)重新排序獲得，而拆卸路徑規(guī)劃過程中只要零件拆出產(chǎn)品包圍盒即可，無需保證拆出時(shí)的姿態(tài)與拆卸終點(diǎn)（裝配起點(diǎn)）的姿態(tài)一致，故圖5中裝配起點(diǎn)處的局部運(yùn)動(dòng)姿態(tài)有較大改變，而這一局部運(yùn)動(dòng)在開闊區(qū)域完成，認(rèn)為是可接受的。

圖5 改進(jìn)算法所生成的路徑

4 結(jié)語

針對(duì)狹窄空間中復(fù)雜產(chǎn)品裝配路徑規(guī)劃成功率和求解效率低的問題，提出一種改進(jìn)的快速搜索隨機(jī)樹算法。此方法將路徑節(jié)點(diǎn)的局部空間離散化，提供多個(gè)備選位姿，提出兩種運(yùn)動(dòng)策略及對(duì)應(yīng)的評(píng)價(jià)指標(biāo)，提高了路徑擴(kuò)展的成功率與效率。仿真實(shí)驗(yàn)結(jié)果表明，此方法可有效解決狹窄空間中的裝配路徑規(guī)劃問題，并可提高求解成功率與效率。