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

姜　康　胡　龍

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

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

姜康胡龍

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

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

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

0　引言

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

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

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

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

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

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

1.1路徑規(guī)劃概述

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

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

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

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

1.2規(guī)劃空間建模

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

(1)

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

如此整個規(guī)劃空間就離散化為一個小長方體集合，集合中的每個元素對應著相應的序號Ri和坐標(Xi,Yi,Zi)，而且序號與坐標一一對應，則可得關系式如下：

(2)

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

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

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

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

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

在路徑規(guī)劃過程中，螞蟻只能從當前柵格向其鄰域柵格運動，如圖3所示。當前柵格Ri的鄰域neighbor(Ri)指的是以當前柵格為中心的立方體。圖3中除Ri共26個元素，其中N1=NxNy。Ri的鄰域為

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間的距離指兩柵格的連線長度，即

(3)

圖3　當前柵格的鄰域

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

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

(4)

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

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

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

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

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

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

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

為驗證算法求解裝配路徑規(guī)劃問題的性能，本文用兩個實例進行了驗證，目標零件與障礙物采用軸向包圍盒包圍進行避障。

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

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

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

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

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

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

5　結(jié)論

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

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

[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]余劍峰，程暉，姚定，等.復雜產(chǎn)品裝配順序評價的路徑反饋方法[J].西北工業(yè)大學學報，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ù)化設計及其CAE研究[D].南京：南京工業(yè)大學，2006.

[5]田立中，付宜利，馬玉林，等.裝配路徑規(guī)劃中基于動態(tài)坐標的A*搜索算法[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]田富君，田錫天，耿俊浩，等.基于視點跟隨的裝配路徑規(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]陳成軍，周以齊，曲斌.基于力反饋的虛擬示教式機械手臂裝配路徑規(guī)劃方法[J].系統(tǒng)仿真學報，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]劉密，劉檢華，何永熹，等.復雜結(jié)構(gòu)條件下的裝配路徑求解與優(yōu)化技術[J].機械工程學報，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

國防基礎科研計劃資助項目(A1120110003)；國防技術基礎計劃資助項目(Z312011B003，Z312012B001，B3120110500)

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

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