姜　康　胡　龍

合肥工業(yè)大學(xué)，合肥，230601

復(fù)雜環(huán)境下的裝配路徑求解與優(yōu)化

姜康胡龍

合肥工業(yè)大學(xué)，合肥，230601

針對(duì)三維復(fù)雜環(huán)境下的裝配路徑規(guī)劃問(wèn)題，運(yùn)用柵格法建立了規(guī)劃空間模型，基于蟻群算法求解出了一條避開障礙物的初始路徑；對(duì)求解得到的裝配初始路徑，提出采用二分法插值優(yōu)化方法縮短裝配路徑長(zhǎng)度，在規(guī)劃過(guò)程中采用目標(biāo)零件與障礙物的軸向包圍盒進(jìn)行避障。對(duì)裝配路徑的求解及優(yōu)化進(jìn)行了實(shí)例測(cè)試，獲得了一條無(wú)碰撞的最短的平滑路徑，驗(yàn)證了算法的有效性和可行性。

裝配路徑規(guī)劃；規(guī)劃空間；蟻群算法；二分法插值優(yōu)化

0　引言

良好的裝配工藝規(guī)劃可以提高效率和質(zhì)量，縮短加工時(shí)間，并降低整個(gè)產(chǎn)品制造過(guò)程中的成本，因此，對(duì)裝配路徑規(guī)劃進(jìn)行研究十分必要[1]。

裝配路徑規(guī)劃是指在有障礙物的工作環(huán)境下，尋找從起始位姿到終止位姿的一系列點(diǎn)或曲線，旨在避開空間障礙并提高裝配效率[2]。裝配路徑的求解是路徑規(guī)劃環(huán)節(jié)的核心部分，路徑的求解一方面是為了避障或滿足作業(yè)需要，另一方面用于驗(yàn)證產(chǎn)品設(shè)計(jì)和裝配序列規(guī)劃是否合理[3]。

隨著產(chǎn)品日趨復(fù)雜化、大型化、精密化，裝配路徑的求解也愈加復(fù)雜，國(guó)內(nèi)外學(xué)者在裝配路徑求解方面取得了大量的研究成果：如VMap法[4]、A*搜索算法[5]、視點(diǎn)跟隨法[6]、力反饋引導(dǎo)法[7]、人工勢(shì)場(chǎng)法[8]、遺傳算法[9]、RRT算法[10-11]等。這些算法求解的是二維環(huán)境條件下或較簡(jiǎn)單的三維環(huán)境下的裝配路徑，沒(méi)有考慮產(chǎn)品在多障礙物環(huán)境下的路徑規(guī)劃問(wèn)題。由于復(fù)雜環(huán)境下空間規(guī)模大、多約束、非線性，對(duì)路徑的求解必須進(jìn)行大量的碰撞檢測(cè)，所以算法效率低，實(shí)際工程應(yīng)用缺乏。

蟻群算法由Dorigo[12]提出，近年來(lái)已被廣泛應(yīng)用于路徑規(guī)劃問(wèn)題、旅行商問(wèn)題、生產(chǎn)調(diào)度問(wèn)題等。蟻群算法具有群體智能等優(yōu)勢(shì)，在路徑規(guī)劃上具有很大的潛力，文獻(xiàn)[13]提出了基于可視圖法與蟻群算法的裝配路徑規(guī)劃方法，該算法解決的是二維環(huán)境條件下簡(jiǎn)單的裝配路徑求解問(wèn)題，至于在三維環(huán)境條件下的效果還有待驗(yàn)證；文獻(xiàn)[14]將蟻群算法用于求解裝配序列規(guī)劃，文獻(xiàn)[15]基于改進(jìn)的蟻群算法和分布式局部導(dǎo)航對(duì)多機(jī)器人系統(tǒng)的路徑進(jìn)行規(guī)劃，但只是將蟻群算法用于求解較簡(jiǎn)單環(huán)境下的路徑規(guī)劃。

本文基于蟻群算法對(duì)三維復(fù)雜環(huán)境下的裝配路徑規(guī)劃進(jìn)行了詳細(xì)的分析，并給出了實(shí)例驗(yàn)證，最后對(duì)求解的初始路徑進(jìn)行了優(yōu)化。

1　裝配路徑規(guī)劃問(wèn)題描述

1.1路徑規(guī)劃概述

路徑規(guī)劃是指在有障礙物的工作環(huán)境中尋找一條從起點(diǎn)到終點(diǎn)、無(wú)碰撞地繞過(guò)所有障礙物的運(yùn)動(dòng)路徑的過(guò)程。裝配路徑規(guī)劃的總體思路如下：①?gòu)漠a(chǎn)品的CAD模型中抽象出三維規(guī)劃空間；②應(yīng)用路徑搜索算法求解出一條避障且路徑最短的初始路徑；③優(yōu)化初始路徑，得到最終裝配路徑。對(duì)裝配路徑規(guī)劃的描述如圖1所示。

圖1　裝配路徑規(guī)劃描述

圖1中環(huán)境空間是一個(gè)包含機(jī)械零部件、工裝夾具、障礙物等信息的無(wú)限大的空間，而目標(biāo)零件從起始點(diǎn)到目標(biāo)點(diǎn)的路徑是一個(gè)有限的空間，所以需要對(duì)目標(biāo)零件確定一個(gè)有限的規(guī)劃空間。在規(guī)劃空間中分布著位置與形狀已知的障礙物(圖1中的1、2、3)，在路徑規(guī)劃時(shí)，將障礙物尺寸根據(jù)目標(biāo)零件的尺寸及運(yùn)行安全性要求進(jìn)行相應(yīng)“膨化”處理，使“膨化”后的障礙物邊界為安全區(qū)域，這樣目標(biāo)零件就可以看作一個(gè)質(zhì)點(diǎn)。目標(biāo)零件的路徑path由目標(biāo)零件從起始點(diǎn)S到目標(biāo)點(diǎn)G繞過(guò)障礙物的有限個(gè)路徑點(diǎn)組成，即

path={S,P1,P2,…,Pi,…,G}i=1,2,…

1.2規(guī)劃空間建模

裝配路徑規(guī)劃首先需要從產(chǎn)品的CAD模型中抽象出三維空間模型。其方法為：以規(guī)劃空間左下角的頂點(diǎn)作為坐標(biāo)原點(diǎn)O建立空間直角坐標(biāo)系；采用柵格法對(duì)規(guī)劃空間進(jìn)行劃分(圖2)：設(shè)該規(guī)劃空間由(Xmin,Xmax,Ymin,Ymax,Zmin,Zmax)確定，先沿X軸方向進(jìn)行Nx等分，再沿Y軸方向進(jìn)行Ny等分，最后沿Z軸方向進(jìn)行Nz等分，則沿X、Y、Z軸方向的像素單位分別為a、b、c，其關(guān)系如下式所示：

(1)

圖2　規(guī)劃空間建模

如此整個(gè)規(guī)劃空間就離散化為一個(gè)小長(zhǎng)方體集合，集合中的每個(gè)元素對(duì)應(yīng)著相應(yīng)的序號(hào)Ri和坐標(biāo)(Xi,Yi,Zi)，而且序號(hào)與坐標(biāo)一一對(duì)應(yīng)，則可得關(guān)系式如下：

(2)

其中，坐標(biāo)(Xi,Yi,Zi)取長(zhǎng)方體柵格的質(zhì)心處坐標(biāo)；mod為取余運(yùn)算，floor為返回小于或等于指定表達(dá)式的最大整數(shù)函數(shù)；ceil為返回大于或者等于指定表達(dá)式的最小整數(shù)函數(shù)。

圖2中，Nx=5，Ny=7，Nz=4，第1個(gè)小長(zhǎng)方體序號(hào)R1=1，位置坐標(biāo)(X1,Y2,Z1)=(0.5a,0.5b,0.5c)；第36個(gè)小長(zhǎng)方體序號(hào)R36=36，位置坐標(biāo)(X36,Y36,Z36)=(0.5a,0.5b,1.5c)，…，其余以此類推。

2　基于蟻群算法的裝配路徑規(guī)劃

2.1裝配路徑規(guī)劃分析

裝配路徑規(guī)劃要求找到一條從起點(diǎn)到終點(diǎn)的繞過(guò)有限個(gè)障礙物的最佳路徑，為求解裝配路徑規(guī)劃問(wèn)題，首先需要構(gòu)造規(guī)劃空間，按1.2節(jié)的方法建立規(guī)劃空間模型。建立規(guī)劃空間時(shí)，像素a、b、c的值需根據(jù)障礙物的疏密程度及目標(biāo)零件的尺寸等進(jìn)行合理設(shè)置。像素小，環(huán)境信息描述得更精確，但會(huì)加大計(jì)算量；像素大，環(huán)境信息描述得不夠精確，影響路徑規(guī)劃的效果。

在路徑規(guī)劃過(guò)程中，螞蟻只能從當(dāng)前柵格向其鄰域柵格運(yùn)動(dòng)，如圖3所示。當(dāng)前柵格Ri的鄰域neighbor(Ri)指的是以當(dāng)前柵格為中心的立方體。圖3中除Ri共26個(gè)元素，其中N1=NxNy。Ri的鄰域?yàn)?/p>

neighbor(Ri)={Ri-1,Ri+1,Ri+Nx,Ri+Nx-1,

Ri+Nx+1,Ri-Nx,Ri-Nx-1,Ri-Nx+1,Ri+N1,Ri+N1-1,Ri+N1+1,Ri+N1+Nx,Ri+N1+Nx-1,Ri+N1+Nx+1,Ri+N1-Nx,Ri+N1-Nx-1,

Ri+N1-Nx+1,Ri-N1,Ri-N1-1,Ri-N1+1,

Ri-N1+Nx,Ri-N1+Nx-1,Ri-N1+Nx+1,Ri-N1-Nx,Ri-N1-Nx-1,Ri-N1-Nx+1}

柵格Ri、Rj間的距離指兩柵格的連線長(zhǎng)度，即

(3)

圖3　當(dāng)前柵格的鄰域

在用蟻群算法求解路徑規(guī)劃時(shí)，由于下一個(gè)可以前往的節(jié)點(diǎn)可能在障礙物中，所以，當(dāng)前柵格Ri的可行鄰域必須要去除落在障礙物中的柵格及禁忌表中已經(jīng)過(guò)的柵格，即

allow(Ri)=neighbor(Ri)-tabu(m)-obs

(4)

其中，allow(Ri)表示Ri的可行鄰域，tabu(m)表示第m只螞蟻的禁忌表，obs表示障礙柵格集，“-”為集合的差集運(yùn)算。

在裝配路徑規(guī)劃過(guò)程中，為了能夠盡快找到一條最優(yōu)路徑，需要對(duì)已裝配的裝配體進(jìn)行簡(jiǎn)化處理，如用軸向包圍盒包圍復(fù)雜的形狀等，并將障礙物尺寸按目標(biāo)零件尺寸的一半及安全指標(biāo)同向擴(kuò)展，進(jìn)行膨化處理，對(duì)環(huán)境中存在的障礙物，如果不滿一個(gè)柵格按一個(gè)柵格處理。目標(biāo)零件的位姿在裝配運(yùn)動(dòng)過(guò)程中保持不變。

2.2路徑規(guī)劃計(jì)算步驟

基于蟻群算法的裝配路徑規(guī)劃的具體計(jì)算步驟如下。

(1)初始化參數(shù)。

(2)將循環(huán)次數(shù)k←k+1。

(3)將螞蟻數(shù)目m←m+1。

(4)創(chuàng)建路徑表path、禁忌表tabu，將起點(diǎn)S添加到path、tabu中。

(5)

其中，τij(t)為信息素的濃度，ηij(t)為啟發(fā)式信息，α、β分別為τij(t)、ηij(t)的權(quán)重參數(shù)。為了能夠盡快找到一條最優(yōu)路徑，ηij(t)取為當(dāng)前柵格至目標(biāo)點(diǎn)距離的倒數(shù)；allowk表示螞蟻k下一步允許選擇的可行鄰域。

(6)若所有螞蟻都遍歷完，則更新信息量；否則跳轉(zhuǎn)到步驟(3)。

(7)重復(fù)步驟(2)～步驟(6)，直至達(dá)到最大循環(huán)次數(shù)K，則循環(huán)結(jié)束并輸出結(jié)果。

3　基于二分法的裝配路徑插值優(yōu)化方法

3.1二分法插值優(yōu)化方法

由于蟻群算法在選擇路徑時(shí)會(huì)走過(guò)一些多余的柵格，使得由一系列離散點(diǎn)連接成的裝配初始路徑不夠平滑，同時(shí)柵格像素的大小也會(huì)增加一些不必要的路徑長(zhǎng)度，為提高算法的可用性，本文對(duì)裝配初始路徑形成的離散點(diǎn)進(jìn)行插值優(yōu)化，盡量使規(guī)劃的路徑更加符合實(shí)際。

文獻(xiàn)[16]提出一種基于分段線性擬合的裝配路徑優(yōu)化技術(shù)，但該算法會(huì)產(chǎn)生路徑冗余中間點(diǎn)。為此，本文提出二分法插值優(yōu)化方法對(duì)規(guī)劃出的裝配初始路徑進(jìn)行優(yōu)化。

圖4　二分法插值優(yōu)化描述

二分法插值優(yōu)化描述如圖4所示，其中①為初始路徑，②為優(yōu)化后的路徑。①中的點(diǎn)從P(1)→P(2)→P(3)→P(4)，起始點(diǎn)為P(1)，若連接點(diǎn)P(1)→P(2)的路徑不與障礙物相碰，連接點(diǎn)P(1)→P(3)的路徑與障礙物相碰，則查找范圍為P(2)→P(3)，再找線段P(2)→P(3)上的一點(diǎn)Q，使得連接點(diǎn)P(1)→Q的路徑不與障礙物相碰。3.2路徑優(yōu)化的計(jì)算流程

圖5為二分法插值優(yōu)化計(jì)算流程，其中P為初始路徑中目標(biāo)零件的位置，L為優(yōu)化后路徑的長(zhǎng)度，path記錄優(yōu)化過(guò)程中目標(biāo)零件的位置。

圖5　二分法插值優(yōu)化計(jì)算流程

4　裝配路徑規(guī)劃實(shí)例

為驗(yàn)證算法求解裝配路徑規(guī)劃問(wèn)題的性能，本文用兩個(gè)實(shí)例進(jìn)行了驗(yàn)證，目標(biāo)零件與障礙物采用軸向包圍盒包圍進(jìn)行避障。

圖6為減速器裝配中零件螺釘?shù)某跏悸窂角蠼?，圖7為安裝架裝配中零件欄桿的初始路徑求解，圖中①為裝配初始路徑，②為優(yōu)化后的路徑。

圖6　減速器裝配路徑規(guī)劃與優(yōu)化

圖7　安裝架裝配路徑規(guī)劃與優(yōu)化

由圖6、圖7可知，目標(biāo)零件通過(guò)尋找障礙物外的可行柵格進(jìn)行路徑規(guī)劃；由表1可知，利用蟻群算法能夠快速求解出零件在復(fù)雜環(huán)境下的裝配初始路徑，整個(gè)計(jì)算過(guò)程用時(shí)0.30～0.55 s，蟻群算法具有群體智能等優(yōu)勢(shì)，將其應(yīng)用于路徑規(guī)劃中有很高的求解效率。

表1　裝配路徑規(guī)劃及優(yōu)化實(shí)例結(jié)果

對(duì)比表1中初始與優(yōu)化用時(shí)及路徑長(zhǎng)度可得，用二分法插值優(yōu)化后的路徑長(zhǎng)度明顯比初始路徑要短，而且二分法插值優(yōu)化用時(shí)極短，在1.1～1.5 ms之間，顯示出了很高的求解效率，優(yōu)化后的路徑是一條較為平滑的路徑，更加符合裝配實(shí)際。

5　結(jié)論

(1)本文基于蟻群算法對(duì)三維復(fù)雜環(huán)境下的裝配路徑規(guī)劃問(wèn)題進(jìn)行了詳細(xì)的分析，規(guī)劃出一條避開障礙物的裝配初始路徑，并對(duì)求解得到的初始路徑提出采用二分法插值優(yōu)化方法以縮短路徑長(zhǎng)度，仿真結(jié)果取得了良好的效果。

(2)裝配路徑規(guī)劃過(guò)程中，在處理目標(biāo)零件與障礙物的碰撞信息時(shí)，通過(guò)是否發(fā)生碰撞來(lái)選擇目標(biāo)零件的可行鄰域，并沒(méi)有充分利用碰撞方向、碰撞點(diǎn)等信息，如何利用上述信息來(lái)更有效地規(guī)劃裝配路徑將在以后的工作中進(jìn)一步探索。

[1]Wang L, Keshavarzmanesh S, Feng H Y, et al. Assembly Process Planning and Its Future in Collaborative Manufacturing: a Review[J]. The International Journal of Advanced Manufacturing Technology, 2009, 41(1/2): 132-144.

[2]Geng Junhao, Jia Xiaoliang, Tian Xitian, et al. Assembly Path Planning Method Based on Lightweight Model[J]. Advances in Intelligent and Soft Computing, 2010, 66: 27-40.

[3]余劍峰，程暉，姚定，等.復(fù)雜產(chǎn)品裝配順序評(píng)價(jià)的路徑反饋方法[J].西北工業(yè)大學(xué)學(xué)報(bào)，2009，27(1)：24-29.Yu Jianfeng, Cheng Hui, Yao Ding, et al. A Path Feedback Method for Evaluating the Assembly Sequence of Complex Products[J]. Journal of Northwestern Polytechnical University, 2009, 27(1): 24-29.[4]管凌峰.薄膜蒸發(fā)器三維參數(shù)化設(shè)計(jì)及其CAE研究[D].南京：南京工業(yè)大學(xué)，2006.

[5]田立中，付宜利，馬玉林，等.裝配路徑規(guī)劃中基于動(dòng)態(tài)坐標(biāo)的A*搜索算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2002，8(4)：316-319.

Tian Lizhong, Fu Yili, Ma Yulin, et al. A*Search Arithmetic Based on Dynamic Coordinate in Assembly Path Plan[J]. Computer Integrated Manufacturing Systems, 2002, 8(4): 316-319.

[6]田富君，田錫天，耿俊浩，等.基于視點(diǎn)跟隨的裝配路徑規(guī)劃與干涉檢查研究[J].中國(guó)機(jī)械工程，2011，22(15)：1810-1814.

Tian Fujun, Tian Xitian, Geng Junhao, et al. Assembly Path Planning Method Based on Viewpoint Tracking and Collision Detection[J]. China Mechanical Engineering, 2011, 22(15): 1810-1814.

[7]陳成軍，周以齊，曲斌.基于力反饋的虛擬示教式機(jī)械手臂裝配路徑規(guī)劃方法[J].系統(tǒng)仿真學(xué)報(bào)，2009，21(10)：2945-2950.

Chen Chengjun, Zhou Yiqi, Qu Bin. Assembly Path Planning for Robot Arm Based on Force Feedback Virtual Teaching Method[J]. Journal of System Simulation, 2009, 21(10): 2945-2950.

[8]Christiand, Yoon J, Kumar P. A Novel Optimal Assembly Algorithm for Haptic Interface Applications of a Virtual Maintenance System[J]. Journal of Mechanical Science and Technology, 2009, 23(1): 183-194.

[9]Ali M, Babu N, Varghese K. Collision Free Path Planning of Cooperative Crane Manipulators Using Genetic Algorithm[J]. Journal of Computing in Civil Engineering, 2005, 19(2): 182-193.

[10]Aguinaga I, Borro D, Matey L. Parallel RRT-based Path Planning for Selective Disassembly Planning[J]. The International Journal of Advanced Manufacturing Technology, 2008, 36(11/12): 1221-1233.

[11]Comes J, Jaillet L, Simeon T. Disassembly Path Planning for Complex Articulated Objects[J]. IEEE Transactions on Robotics, 2008, 24(2): 475-481.

[12]Dorigo M, Maniezzo V, Colorni A. Ant System: Optimization by a Colony of Cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 1996, 26(1):29-41.

[13]Liu Haicheng, Li Yuan, Yu Jianfeng, et al. Path Planning Algorithm for Assembly of Complex Product Based on V-Map and Ant Colony Optimization Algorithm[C]//2010 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE). Chengdu, 2010: V5-398-V5-402.

[14]Wang J F, Liu J H, Zhong Y R. A Novel Ant Colony Algorithm for Assembly Sequence Planning [J]. The International Journal of Advanced Manufacturing Technology, 2005, 25(11/12): 1137-1143.

[15]Liu Shirong, Mao Linbo, Yu Jinshou. Path Planning Based on Ant Colony Algorithm and Distributed Local Navigation for Multi-robot Systems[C]//Proceedings of the 2006 IEEE International Conference on Mechatronics and Automation. Luoyang, Henan, 2006: 1733-1738.

[16]劉密，劉檢華，何永熹，等.復(fù)雜結(jié)構(gòu)條件下的裝配路徑求解與優(yōu)化技術(shù)[J].機(jī)械工程學(xué)報(bào)，2013，49(9)：97-105.

Liu Mi, Liu Jianhua, He Yongxi, et al. Research on Assembly Path Planning and Optimization of Complex Structures[J]. Journal of Mechanical Engineering, 2013, 49(9): 97-105.

(編輯王艷麗)

Assembly Path Panning and Optimization under Complex Environments

Jiang KangHu Long

Hefei University of Technology,Hefei,230601

In order to solve the problem of assembly path planning in three-dimensional complex environments, a model of planning space was established by using grid method and the ant colony algorithm was applied to obtain the initial path to avoid obstacles. The dichotomy interpolation optimization was proposed to reduce the original assembly path length. The obstacle avoidance was achieved by using the axis-aligned bounding boxes between target part and obstacles in the planning process. Some example tests were carried out on the assembly path planning and optimization to verify the effectiveness and feasibility of the proposed algorithm by achieving a shortest smooth collision-free path.

assembly path planning; planning space; ant colony algorithm; dichotomy interpolation optimization

2014-01-13

國(guó)防基礎(chǔ)科研計(jì)劃資助項(xiàng)目(A1120110003)；國(guó)防技術(shù)基礎(chǔ)計(jì)劃資助項(xiàng)目(Z312011B003，Z312012B001，B3120110500)

TP391DOI：10.3969/j.issn.1004-132X.2015.05.011

姜康，男，1974年生。合肥工業(yè)大學(xué)交通運(yùn)輸工程學(xué)院副教授。主要研究方向?yàn)閿?shù)字化設(shè)計(jì)與制造、系統(tǒng)建模與仿真、信息與控制等。發(fā)表論文10余篇。胡龍，男，1989年生。合肥工業(yè)大學(xué)交通運(yùn)輸工程學(xué)院碩士研究生。