装配序列规划问题的CSP模型及其符号OBDD求解技术  

A Constraint Satisfaction Problem Model and Its Symbolic OBDD Solving for Assembly Sequence Planning Problem

作　　者：徐周波[1,2] 古天龙[2] 

机构地区：[1]西安电子科技大学电子工程学院,西安710071 [2]桂林电子科技大学计算机学院,桂林541004

出　　处：《计算机辅助设计与图形学学报》2010年第5期803-810,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60963010;60903079)

摘　　要：完全、正确的可行装配序列的表示和生成是装配序列评价、优化和选择的前提,为此建立了单调非线性装配意义下的可行装配序列规划问题的约束满足问题(CSP)模型,并给出了基于有序二叉决策图(OBDD)的符号求解算法.首先以装配联接图和移动向量函数为装配体模型,给出了装配联接图模型的共享二叉决策图(SBDD)表示、移动向量函数的OBDD表示,以及装配序列规划问题的CSP描述;然后将生成所有可行装配序列的问题转化为对CSP求解所有可能解的问题,利用回溯算法对CSP问题进行符号OBDD求解,得到了满足几何可行性约束的所有可行装配序列.最后通过装配体实验验证了基于CSP模型和OBDD推理的装配序列生成技术的正确性和可行性.The correctness and completeness of assembly sequences are imperative in assembly sequence planning.In the paper,a novel scheme to integrate constraint satisfaction problem（CSP） model with the symbolic ordered binary decision diagram（OBDD） is presented for the monotonic and non-linear assembly sequence planning.In order to formulate the assembly sequence planning problem,the shared binary decision diagram（SBDD） is proposed to represent the assembly liaison graph,and the translational function is represented as ordered binary decision diagrams.Assembly sequence planning problem is formulated as a constraint satisfaction problem（CSP）,and the feasible assembly sequences are generated by solving the corresponding CSP model.Moreover,the symbolic OBDD based backtracking technique is given to generate all geometrically feasible assembly sequences.Experiments are also conducted to verify that the symbolic OBDD based CSP scheme can handle the assembly sequence planning properly and efficiently.

关 键 词：装配序列生成 装配联接图 约束满足问题 有序二叉决策图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]