《基于加权约束求解技术的装配序列优化算法》由会员分享，可在线阅读，更多相关《基于加权约束求解技术的装配序列优化算法（8页珍藏版）》请在金锄头文库上搜索。
1、基于加权约束求解技术的装配序列优化算法 唐浩 刘桂珍 徐周波 桂林电子科技大学计算机与信息安全学院 摘 要： 针对符号约束求解技术无法解决装配序列择优的问题, 提出一种装配序列优化算法。该算法通过筛选合适的装配评价指标构建装配评价函数, 以装配联接图和带权移动向量函数为装配体模型, 给出装配联接图和带权移动向量函数的ADD 表示, 并将装配序列规划问题描述为加权约束满足问题, 利用深度优先分枝定界 (DFBB) 算法和符号 ADD 技术对加权约束满足问题求解。仿真实验表明, 该装配序列优化算法能够求解最优装配序列, 并增强了对装配序列的优化能力。关键词： 装配序列规划; 加权约束满足问题; 代
2、数决策图; 评价; 作者简介：徐周波 (1976-) , 女, 浙江奉化人, 副教授, 博士, 研究方向为符号计算、智能规划、约束求解。E-mail:xzbli_收稿日期：2017-05-09基金：广西自然科学基金 (2015GXNSFAA139285, 2014GXNSFAA118354) An assembly sequence optimization algorithm based on weighted constraint solvingTANG Hao LIU Guizhen XU Zhoubo School of Computer and Information Securit
3、y, Guilin University of Electronic Technology; Abstract： In order to solve the problem that the assembly sequence optimization can not be solved by technique of symbol constraints, an assembly sequence optimization algorithm is proposed.In the algorithm, the assembly evaluation function is building
4、by screening the appropriate assembly evaluation index.Taking the assembly diagram and the weighted motion vector function as the assembly model, the ADD is proposed to represent the assembly liaison graph.The weight translational function is represented as algebraic decision diagram.The weighted co
5、nstraint satisfaction problem (WCSP) is established to solve the problem of assembly sequence planning.The DFBB algorithm and the symbol ADD technique are used to solve the WCSP.The simulation result shows that the assembly sequence optimization algorithm can effectively solve the optimal assembly s
6、equence and enhance optimization ability of the assembly sequence.Keyword： assembly sequence planning; weighted constraint satisfaction problem; ADD; evaluation; Received： 2017-05-09装配序列规划 (assembly sequences planning, 简称 ASP) 问题的本质是 NP组合优化问题。解决 ASP 问题的传统方法有交互式问答法1、割集生成法2等。交互式问答法的原理是通过人机交互向系统使用者提出装配
7、联接图模型相关问题, 获取装配约束关系, 利用这些约束关系求得 ASP 问题的解。该方法中系统需要提出的问题数目随着零件数目的增加成指数级增加。割集生成法是运用割集法在装配联接图模型上求解, 得到装配割集, 并在装配割集中对装配序列进行可行性判定, 最终求得问题的所有可行装配序列。近年来, OBDD 及其扩展形式在求解 ASP 问题上有了广泛的应用。文献3运用OBDD 技术求解可行装配序列;文献6应用 ZBDD 技术对装配序列可行性进行有效判定;文献7给出了基于 CSP 模型的装配序列规划求解方法。这些方法虽然可以生成可行的装配序列, 但如何对生成的装配序列进行择优与优化, 仍是亟需解决的问题
8、。可应用加权约束满足问题 (weighted constraint satisfaction problem, 简称 WCSP) 求解技术解决此问题。加权约束求解技术的优势是能够根据装配评价指标定义对应的约束条件, 并且能够为这些定义的约束指派对应的权值, 即问题的约束得不到满足时产生的代价, 从而将求解最优装配序列目标转变为先求解满足权值之和最小的几组变量赋值, 再根据装配评价指标计算每组的装配代价, 最后通过筛选得到一组装配代价的最小赋值。鉴于此, 提出一种基于加权约束求解技术的装配序列优化算法。通过筛选合适的装配评价指标建立装配评价函数, 以装配联接图和带权移动向量函数为装配体模型, 给
9、出装配联接图和带权移动向量函数 ADD 表示, 并构建装配序列规划问题为 WCSP 模型, 利用 DFBB 算法和符号 ADD 技术对 WCSP 求解。1 代数决策图及加权约束满足问题1.1 代数决策图ADD 表示是一个基于变量 x1, x2, , xn的一簇伪布尔函数 f:0, 1S 的有向无环图。在 ADD 的有向路径上, 给定变量序 :x 0Uj, 则装配零件质量的权值为 C1=Ui。2.1.2 装配零件的联接关系装配零件的联接关系对于装配操作的可靠性有直接的影响。用 C2对装配中各零件的联接关系进行量化:2.1.3 装配方向的重定向次数装配方向改变次数越少, 装配成本就越小, 越有利于
10、装配序列择优。因此, 在所有可行的装配序列中, 要选择装配方向改变次数较少的序列。设定装配零件的重定向次数为 C3=n, n 为装配方向改变的总次数。2.1.4 建立目标函数创建目标函数:对 C1、C 2、C 3进行加权。2.2 装配体模型的 ADD 表示装配联接图可用 G=P, C表示。其中:G 为装配体;P 为装配联接图中的顶点集;C 为连接至少有一种装配关系的连接边集。装配联接图中顶点用 gx0x1xn-1表示, 其中 g 表示零件的质量。长度为 n (n=#log2|P|$) 位长的二进制串 x0x1xn-1能够与零件一一对应, 任意有向边u, v用 x0x1xn-1y0y1yn-1表
11、示, 边的起点 u=x0x1xn-1, 边的终点v=y0y1yn-1。简单装配体如图 2 所示。图 2 (a) 中装配体的零件 a、b、c 和 d对应的二进制串编码分别为 10x0x 1、5x 0x1、1x 0x1和 5x0x 1, 用图 2 (c) 所示的 ADD 图表示。图 2 (b) 装配联接图 G 中的连接边 c1, c2, c3, c4, c5对应二进制串分别为 x0x 1y0y1, x 0x 1y0y1, x0x 1y0y 1, x 0x1y 0y 1, x0x1y0y 1, 用图 2 (d) 所示的 ADD 表示。图 2 简单装配体 Fig.2 Simple assembly 下
12、载原图参考移动向量函数和装配评价函数描述, 在原移动向量函数基础上增加代价权值, 给出带权移动向量函数 W。2 个零件 a、b 之间的带权移动向量函数可表示为 Wab= (C0, C1, C2, C3, C4, C5) , 可定义为 Wab=Ci0, 1, 2, i 取 05。其中:C i=0 表示零件 b 在 i 方向装配到零件 a 时产生冲突, 无法在方向 i 上进行装配;C i=1 表示零件 b 可在方向 i 无冲突地装配到零件 a 上, 且装配后 2 个零件的联接关系为接触联接;C i=2 表示零件b 在方向 i 可无冲突地装配到零件 a 上, 且装配后 2 个零件的联接关系为稳定联接
13、。i 取值 0、1、2、3、4、5 时, 分别对应+X、+Y、+Z、-X、-Y、-Z 这 6 个方向。图 2 (a) 所示装配体的带权移动向量函数 W 如表 1 所示。该带权移动向量函数的编码方式参照文献7, 若设对应的零件对为 (c, d) , 则带权移动向量函数中的第 i 行第 j 列为 2 的元素可表示为 2 (x0x1xn-1 1) (y0y1yn-1 1) z0z1z2, 数值 2 表示当前零件对的联接关系是稳定联接关系, x 0x1xn-1 1对应零件 c, y0y1yn-1 1对应零件 d, z0z1z2表示零件 d 装配到零件 c 的方向。图 2 (a) 装配体的带权移动向量函
14、数的 ADD 表示如图 3 所示。表 1 带权移动向量函数 Tab.1 Weighted translational function 下载原表 图 3 带权移动向量函数 Fig.3 Weighted translational function 下载原图3 ASP 问题的符号加权约束求解算法3.1 装配序列规划问题的 WCSP 模型设 WCSP 中变量集 X=x1, x2, , xm, 其中每个变量对应 G 中的一条连接边。设各变量的域 D=1, n-1, n 为装配体的零件个数。WCSP 问题的赋值结构 S (k) = (0, k, +, ) 。对 WCSP 进行约束 C 的定义如下:1)
15、 约束 c1:对于拥有连接边 e1, e2, , ek的装配联接图, 若已有 n-1 (nbu, 则执行回溯操作;否则, 转步骤 2) 。5) 算法结束。4 仿真实验利用 Visual C+和 Colorado 大学开发的 CUDD 软件包, 在 Windows 7 操作系统, i5-2430M 处理器, 6GB 内存环境下进行实验。以图 2 (a) 装配体为例进行实验, 生成的最优装配序列 ADD 表示如图 4 所示, 用装配序列优化算法求解所需时间为 0.005s。选用其他规模的装配体进行实验, 以图 5 所示的圆珠笔装配体为例, 该装配体有 6 个零件, 用装配序列优化算法求解所需时间为
16、 0.011s。生成的最优装配序列表示为:4u0u 1u 2u 3u 4u 5w 0w 1w 2w3w 4w 5z 0z 1z 2+8u 0u 1u 2u3u4u 5w 0w1w 2w3w 4w 5z 0z 1z 2+12u 0u1u 2u3u 4u 5w 0w1w 2w3w4w5z 0z 1z2+17u0u1u 2u3u 4u5w 0w1w 2w3w4w5z0z 1z2+20u0u1u 2u3u4u5w0w1w2w3w4w5z0z 1z2。对图 6 的机用虎钳装配体进行实验。该装配体具有 15 个零件, 需消耗6094.845s 才能得到最优装配序列。图 4 简单装配体的 ADD Fig.4 ADD of simple assembly 下载原图图 5 圆珠笔装配体 Fig.5 Assembly
