復雜環境下的裝配路徑求解與優化

姜　康　胡　龍

合肥工業大學，合肥，230601

復雜環境下的裝配路徑求解與優化

姜康胡龍

合肥工業大學，合肥，230601

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

裝配路徑規劃；規劃空間；蟻群算法；二分法插值優化

0　引言

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

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

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

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

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

1　裝配路徑規劃問題描述

1.1路徑規劃概述

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

圖1　裝配路徑規劃描述

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

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

1.2規劃空間建模

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

(1)

圖2　規劃空間建模

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

(2)

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

圖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　基于蟻群算法的裝配路徑規劃

2.1裝配路徑規劃分析

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

在路徑規劃過程中，螞蟻只能從當前柵格向其鄰域柵格運動，如圖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　當前柵格的鄰域

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

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

(4)

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

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

2.2路徑規劃計算步驟

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

(1)初始化參數。

(2)將循環次數k←k+1。

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

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

(5)

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

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

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

3　基于二分法的裝配路徑插值優化方法

3.1二分法插值優化方法

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

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

圖4　二分法插值優化描述

二分法插值優化描述如圖4所示，其中①為初始路徑，②為優化后的路徑。①中的點從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路徑優化的計算流程

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

圖5　二分法插值優化計算流程

4　裝配路徑規劃實例

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

圖6為減速器裝配中零件螺釘的初始路徑求解，圖7為安裝架裝配中零件欄桿的初始路徑求解，圖中①為裝配初始路徑，②為優化后的路徑。

圖6　減速器裝配路徑規劃與優化

圖7　安裝架裝配路徑規劃與優化

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

表1　裝配路徑規劃及優化實例結果

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

5　結論

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

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

[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]余劍峰，程暉，姚定，等.復雜產品裝配順序評價的路徑反饋方法[J].西北工業大學學報，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]管凌峰.薄膜蒸發器三維參數化設計及其CAE研究[D].南京：南京工業大學，2006.

[5]田立中，付宜利，馬玉林，等.裝配路徑規劃中基于動態坐標的A*搜索算法[J].計算機集成制造系統，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]田富君，田錫天，耿俊浩，等.基于視點跟隨的裝配路徑規劃與干涉檢查研究[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].系統仿真學報，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]劉密，劉檢華，何永熹，等.復雜結構條件下的裝配路徑求解與優化技術[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年生。合肥工業大學交通運輸工程學院副教授。主要研究方向為數字化設計與制造、系統建模與仿真、信息與控制等。發表論文10余篇。胡龍，男，1989年生。合肥工業大學交通運輸工程學院碩士研究生。