基于OBDD的装配序列生成算法研究

摘要

可行装配序列生成是装配序列规划的核心问题,是个典型的NP难题。传统装配序列方法研究主要着眼于通过增加约束的方式减少无效序列的生成,而面对拥有大量可行装配序列的复杂装配体时依然收效甚微。为此在分析和总结现有装配序列生成算法的基础上,本文对解决组合问题方面取得成功的 OBDD符号技术在装配序列生成中的应用进行了研究。本文主要研究内容和结论如下:
　　(1)在现有装配体模型的基础上进行简化,建立了一种新的基于OBDD符号技术的装配体模型。在此新模型的基础上,提出相应的基于 OBDD的可行装配序列推理算法。分析表明该推理算法是正确完备的。
　　(2)综合分析了现有求无向图所有割集的算法特点,提出基于OBDD的并行枚举割集算法,并通过理论证明了该算法的正确性。为无向图割集生成开辟了一条新的途径。
　　(3)从装配体 CAD模型中提取装配体中各零件的接触信息,建立了基于 OBDD的装配体无向联接图模型。在此基础上,利用 OBDD并行枚举割集算法生成装配体的所有装配割集。
　　(4)从装配体CAD模型中提取装配体中各零件的干涉信息,建立了OBDD并行干涉检测模型。并对生成的装配割集进行几何可行性判断。从而得到了完整的OBDD可行装配序列割集生成算法。实验结果表明这种基于 OBDD的可行装配序列生成算法是正确完备的。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 引言

§1.1 装配序列规划研究背景

§1.2 本论文课题的提出、目的及意义

§1.3 装配序列规划的国内外研究现状

§1.4 本文的主要研究工作及章节安排

第二章 有序二叉决策图（OBDD）

§2.1 OBDD的概念及其简化

§2.2 OBDD的基本操作

§2.3集合的OBDD表示

§2.4 CUDD软件包

第三章 基于OBDD的装配体建模

§3.1相关概念

§3.2装配体的OBDD模型

§3.3基于OBDD推理技术的装配序列生成算法

§3.4 举例

§3.5 小结

第四章 基于OBDD的割集生成算法

§4.1 无向图割集相关概念

§4.2 无向图割集生成算法概述

§4.3 OBDD割集生成算法

§4.4 小结

第五章 基于OBDD的可行装配序列生成算法

§5.1装配关系连接图模型

§5.2装配割集生成

§5.3 并行干涉检测模型

§5.4 OBDD拆卸序列表示

§5.5 仿真实验

§5.6 小结

第六章 结束语

§6.1主要研究成果

§6.2 相关研究展望

参考文献

致谢

附录：读研期间所完成的学术论文