Bi—RRT算法在装配序列生成中的应用
2015-10-27 02:14雷康华翟晓庆华顺刚
电脑知识与技术 2015年21期
雷康华 翟晓庆 华顺刚
摘要：装配序列生成是计算机辅助工艺规划的重要环节。在VS2005环境下，对Pro/E进行了产品装配序列生成的二次开发，求出产品的拆卸序列，进一步求反获得产品的装配序列。首先，提取零件特征信息和空间位姿信息并在自动拆卸过程中对零件进行干涉检查，建立干涉表；然后，根据零件间干涉关系选择拆卸方向，生成可行的装配序列。在此基础上，对位置特殊、沿单一拆卸方向不能拆卸的零件采用Bi-RRT（双向快速扩展随机树）算法进行路径规划，实现复杂环境中零件的拆卸，并以实例论证了方法的有效性。
关键词：装配序列；干涉检查；Bi-RRT算法；拆卸路径规划
中图分类号：TP202 文献标识码：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
装配序列的确定是产品装配工艺规划的基本任务，可行的装配序列不仅要求零件装配过程中不会发生干涉，而且最好是操作简单、装配耗时少、成本低等。近年来，机械产品愈来愈复杂，传统装配方法适用性降低，如何自动生成装配序列成为研究热点，并取得了阶段性成果。王峻峰[1]等通过自动拆卸仿真生成表达拆卸干涉关系的干涉矩阵，在此基础上利用蚁群算法实现多零件拆卸序列的生成；张秀芬[2，3]等采用拆卸赋权混合图与粒子群优化算法相结合的方法，实现了装配体拆卸序列的快速求解；于嘉鹏[4]等提出一种基于扩展干涉矩阵的几何可拆性判别方法，对单个零件进行可拆卸判断，并结合蚁群算法成功确定装配体拆卸序列；刘志峰[5]等在构建模型拆卸约束图的基础上，运用模拟退火粒子群优化算法，实现对模型拆卸序列的求解。
本文基于拆卸并结合RRT算法实现装配序列求解。首先通过拆卸仿真对装配体中所有零件沿单一方向进行可拆性判断，选择自由零件数较多的方向为零件的拆卸方向，完成装配体零件的拆卸；其次，对于位置特殊的零件结合Bi-RRT算法，根据运动规划搜索较优的拆卸路径进行拆卸。该方法解决了零件沿单一方向不能完全拆卸的局限性，适用性强。
1 装配体中零件干涉关系判断
本文通过MFC和Pro/Toolkit开发包实现对Pro/E的二次开发，程序驱动装配体模型中每个零件以既定步长沿几何方向移动，移动过程中对零件进行干涉检查，建立零件干涉表。
1.1 提取模型装配信息
为了提取装配信息，需要对装配体进行特征遍历，在Pro/Toolkit开发包中，遍历实体特征的库函数是ProSolidFeatVisit（），其原型函数如下所示：
ProSolidFeatVisit （ ProSolid p_handle，
ProFeatureVisitAction visit_action，
ProFeatureFilterAction filter_action，
ProAppData app_data）；
上述函数有4个参数，第1个参数表示被访问模型的实体句柄，该句柄可通过调用库函数ProMdlCurrentGet（）
Pro/Toolkit开发中利用转换矩阵表示Pro/E中模型的位姿信息[6]，矩阵定义如下：
[P=xv1xv2xv30yv1yv2yv30zv1zv2zv30xsyszs1] （1）
上述矩阵中前3行和3列构成的3×3阶子矩阵描述零件的姿态信息，改变子矩阵中变量可以产生比例、旋转等几何变换；矩阵[XsYsZs]描述零件的位置信息，改变[Xs]，[Ys]，[Zs]可以实现零件的平移。零部件从初始位置平移[dx]，[dy]，[dz]后的坐标（[x，y，z]）可表示为：
[xyz1=dxdydz1*P] （2）
本文通过调用Pro/Toolkit开发库函数ProAsmComppathTrfGet（）得到零件在装配体中的初始位姿矩阵P，调用函数ProAsmComppathTrfSet（）设置平移后的矩阵为零件当前的位姿矩阵，从而实现零件的平移。
1.2 获取零件干涉关系
编程实现装配体中每个零件沿方向集{X，-X，Y，-Y，Z，-Z }移动，移动过程中对装配体进行干涉检查，建立干涉情况表。干涉表建立流程如图1所示：
1） 获取装配体的最大长、宽、高；
调用Pro/Toolkit接口函数ProSolidOutLineGet（P_solid，point[2]），获取装配体模型实体包围盒对角两点的坐标，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） 从遍历所得的模型数组中依次选择零件，获取零件的位姿信息；
3）零件沿方向集{X，-X，Y，-Y，Z，-Z}中的一个方向移动，移动最大距离L由移动方向决定：如果移动方向是X或-X方向，[L=Lx]；如果移动方向是Y或-Y方向，[L=Ly]；移动方向是Z或-Z方向，[L=Lz]；移动步长为L/100；
4）单步平移时进行干涉检查，判断零件在当前状态下与其他零件是否干涉，干涉则停止移动，重新回到初始位置，执行3）继续下一方向，记录该零件在移动方向上的干涉情况。干涉检查调用Pro/E接口函数
pro_compute_global_interference （p_model， PROINTERF_SOLID_ONLY， &n_intf_parts， &intf_parts， &intf_part_surfs， &n_part_surfs）；
5）判断零件在某一方向移动距离是否达到最大长度L，若是则执行6），否则继续执行4）；
6）判断零件是否沿6个方向移动完毕，若是则执行7），否则返回执行3）选择下一移动方向；
7）判断装配体中的零件是否移动完毕，若是则执行8），否则返回执行2）选择下一零件；
8）输出干涉关系；
2 装配序列生成
生成装配序列流程如下：1）实际拆卸时，基础件是最后拆除零件，根据零件间约束关系及位置关系选出模型的基础件，不进行拆卸判断，如底座、箱体之类。2）选取自由零件个数最多的方向作为零件的优先拆卸方向；3）拆卸所选方向上的所有零件，并依据拆卸顺序给零件按顺序重命名；4）循环执行2）、3）步，直至装配体拆卸完成，生成可行的零件拆卸序列。基于“可拆即可装”的思想，装配序列即是装配模型拆卸序列的逆序列。
本文采用插销装配体作为例子。该装配体在Pro/E中建模完成，共有12个零件组成。本文通过对Pro/E二次开发，实现零件的自动拆卸仿真：采用遍历模型树的方法获取所有零件的特征信息、位姿信息存储在零件数组中，并按照遍历所得先后顺序对零件进行编号。
装配体中，基础件是最后一个拆卸的零件，如底座，箱体等，装配体拆卸前首先要确定其基础件。提取所有零件的属性信息，选择体积最大的零件作为模型的基础件，在Pro/E窗口中高亮显示，若因零件体积近似而引起选择误差时结合人工交互修正。从整体零件数组中剔除基础件，余下零件沿几何方向进行拆卸仿真，建立零件干涉表，0表示该零件在某方向移出装配体实体边界盒的过程中与其他零件不干涉，1表示干涉。本例中1号零件被选作基础件，剔除1号零件后零件的干涉情况如表1所示。
由表1知Y方向自由零件个数最多，所以Y为优先拆卸方向，沿Y方向拆卸零件集{5，6，7，8，9，10，11，12}，图2表示装配体第一轮拆卸完成后状态。从零件数组中剔除已拆卸零件，对剩余零件重新进行干涉判断，由表2知，X和-X方向的自由零件个数相同，X方向拆卸零件集为{4，3}，-X方向零件拆卸集为{4，2}。实际拆卸时，零件间存在拆卸顺序约束，本例中零件4和2存在装配关系，零件2是零件4的基础件，零件4要先于零件2拆卸。本文通过比较零件在六个方向拆卸时受到干涉的数量，得出零件2受到的干涉最多，说明零件2的配合关系数最多，故零件2应最后拆卸，X方向为优先拆卸方向，所以拆卸序列为[{5，6，7，8，9，10，11，12}→{4，3}→2]，对序列求反即可得模型的装配序列。
一般情况下，运用上述方法，可将装配体中零件沿单一方向依次完全拆卸，但实际拆卸时，该方法往往有一定的局限性，如图5所示，装配体有4个零件，分别是台灯体、灯管、插口和管盖。运用上述方法对装配体中零件进行拆卸仿真，建立干涉表如表3，由于零件位置特殊，所有零件沿单一方向拆卸时都发生干涉，上述方法无法完成零件拆卸。故而，本文在原方法的基础上运用快速扩展随机树RRT（Rapidly-exploring random tree）算法[7]对零件进行运动规划，搜索零件可行的拆卸路径，实现对目标零件的拆卸。
3 基于Bi-RRT算法的零件拆卸
快速扩展随机树（RRT）算法是近几年发展起来的一种基于随机采样的单一搜索路径规划的算法，该算法的优点是不用对空间建模，减少了路径搜索计算量，缩短了运算时间，提高了效率，在解决高维空间和复杂环境中机器人路径规划问题上得到了广泛的应用。基于其在机器人路径规划上的优越性，本文采用基于RRT算法[8]的运动规划为装配体零件寻找一条可到达装配体外自由空间的无干涉路径。
3.1 经典RRT算法
随机树构建过程如图6所示，设[Tk]为包含k个节点的随机树，C-free为无碰撞自由状态空间，定义qstart为初始位置即起点，[ qgoal∈Cfree]为目标位置即终点。Qrand为自由空间中随机选取点，且[qrand∈Cfree]找出[Tk]中距离qrand最近的点qnearest，在qnearest和qrand的连线上求一点qnew，满足条件[qnew∈Cfree]且Dinstance（qnearest， qnew）=d，d>0，是RRT生长的最小步长。如果qnew存在，则在[Tk]上增加一个新节点，否则重新选取qrand。在既定迭代次数内，如果新节点距离目标点距离小于阈值[ε]，算法搜索成功[9，10]。如图7所示，在VC6.0上采用RRT算法在具有不规则障碍物环境中规划出的仿真轨迹图。
3.2 双向搜索随机树（Bi-RRT）算法
RRT算法对状态空间随机采样，搜索无目标性，每次随机采样生成的随机树不尽相同，搜索树无任何目标导向性，收敛速度缓慢。为了改进搜索效率，在经典RRT算法的基础上，本文采用Bi-RRT算法进行路径搜索[11，12]，它是在RRT-connect算法思想的基础上提出来的，采取从起点和终点分别扩展随机树并相向扩展的方式，克服了RRT-connect算法易陷入局部极小值的缺点，效率更高，应用更广。Bi-RRT节点构建过程如图8所示，以起点qstart1为根节点，以随机点qrand为临时目标点扩展Tree_1，以终点qgoal为根节点，以新产生的节点qnew1为临时目标点扩展Tree_2，并在下一轮扩展时交换扩展顺序。这样一来，解决了经典RRT算法搜索无目标性的问题，提高了搜索效率，Bi-RRT路径搜索步骤如下：
1）定义所有参数，初始化随机树Tree_1、Tree_2，qstart1添加到Tree_1上，qgoal添加到Tree_1上。
2）调用随机节点生成函数，在自由状态空间内产生一个随机点qrand。
3）在Tree_1上搜索距离qrand最近的点qnearest1。调用函数计算Tree_1上所有节点与qrand的距离，找出最小值。
4）调用扩展节点函数扩展新节点qnew1，判断零件在点qnew1上与其他零件是否干涉，不干涉则把点qnew1添加到Tree_1上，记录其父节点后执行下一步，否则返回到2）。
5）在Tree_2上搜索距离qnew1的最近点qnearest2。
6）调用扩展节点函数朝着Tree_1扩展新节点方向扩展节点qnew2，判断零件在点qnew2上与其他零件是否干涉，不干涉则把点qnew2添加到Tree_2上，记录其父节点后执行下一步，否则执行9）。
7）判断Tree_1、Tree_2是否相遇，即Distance（qnew1， qnew2）是否小于一个给定阈值[ε]，若小于则停止搜索路径点，执行下一步，否则执行9）。
8）反向搜索qnew1和qnew2的父节点得到路径P。
9）交换T1和T2，改变其先后扩展顺序，返回执行2）。
为了使算法可控，在Step10中设置迭代次数上限，如果在设定的次数内，两棵树没有相遇，算法返回失败。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算法实现
为了验证算法的可靠性，算法实现图5模型中零件的路径规划。以零件在装配体中的空间坐标为初始点，以自由状态空间中的一点为目标点，搜索一条从初始点到目标点的有效路径作为零件的拆卸路径。以装配体中灯管零件的拆卸为例，拆卸关键点状态如图9所示，灯管在灯槽内水平向左移出插口后斜向下方移出灯槽，最终到达目标位置，生成拆卸路径，装配体中零件拆卸路径如图10所示。
同时，为了验证算法的适用性，本文模拟封闭箱体中零件的拆卸，如图11所示，箱体顶端有一拆卸窗口，待拆卸的零件在挡板的下方，待拆卸零件需要经拆卸窗口才能移出箱体，为了便于说明，将箱体从一端剖开。本例中目标零件的初始位置为随机树根结点，拆卸窗口上方一点为目标点，通过设定零件移动步长和与环境中障碍物的碰撞干涉检测扩展树节点，逐步接近目标位置。拆卸过程t特殊位置状态如图12所示，零件先向上移动至挡板下方后水平向右移动，移出挡板范围后继续向上运动，最终到达目标位置，生成拆卸路径如图13所示。
5 结束语
本文在VS2005环境下对Pro/E进行装配序列生成的二次开发，获取装配体中零件的特征信息、位姿信息，实现了基于自动拆卸仿真与动态干涉检查的可行装配序列生成。在此基础上，研究了基于RRT的路径规划算法，并应用双向搜索随机树（Bi-RRT）算法对装配位置特殊的零件进行路径规划，实现对目标零件的拆卸，有效地解决了目标零件沿单一方向无法拆卸的问题，适用性强，并在Pro/E平台上得到了实现。
参考文献：
[1] 王俊峰，李世奇，刘继红. 面向绿色制造的产品选择拆卸技术研究[J]. 计算机集成制造系统，2007，13（6）： 1097-1102.
[2] 张秀芬，张树有，伊国栋，等. 面向复杂机械产品的目标选择性拆卸序列规划方法[J]. 机械工程学报，2010，46 （11）： 172-178.
[3] 张秀芬，张树有. 基于粒子群算法的产品拆卸序列规划方法[J]. 计算机集成制造系统，2009，15（3）： 508-514.
[4] 于嘉鹏，邢宇飞. 基于扩展干涉矩阵的几何可拆卸性判别方法[J]. 机械工程学报，2011，47（21）： 146-148.
[5] 刘志峰，杨德军. 基于模拟退火粒子群优化算法的拆卸序列规划[J].合肥工业大学学报，2011，34（2）： 161-165.
[6] 吴立军，陈波等. Pro/ENGINEER二次开发技术基础[M]. 北京：电子工业出版社，2006：153-154.
[7] 赵柏萱，刘检华. 一种基于运动规划的选择拆卸序列规划技术[J]. 机械工程学报，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电子样机零件可达性及拆卸路径规划研究[D]. 秦皇岛：燕山大学，2013： 27-37.
[10] 王全. 基于RRT的全局路径规划方法及应用研究[D]. 长沙：国防科学技术大学，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]. 大连理工大学学报，2014，54（6）： 637-643.
