试析基于obdd的装配序列生成算法研究

《试析基于obdd的装配序列生成算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级UDC编号桂林电子科技大学硕士学位论文题目基于OBDD的装配序列生成算法研究（英文）TheResearchonOBDD-BasedAlgorithmforGenerationofAssemlySquences研究生姓名:刘华东指导教师姓名、职务:古天龙教授申请学位门类:工学硕士学科、专业:控制理论与控制工程提交论文日期:2006年9月论文答辩日期:2006年12月年月日万方数据独创性（或创新性）声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论

2、文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得桂林电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：日期：关于论文使用授权的说明本人完全了解桂林电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属桂林电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为桂林电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文

3、；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。（保密的论文在解密后遵守此规定）本学位论文属于保密在____年解密后适用本授权书。本人签名：日期：导师签名：日期：万方数据基于OBDD的装配序列生成算法研究摘要可行装配序列生成是装配序列规划的核心问题，是个典型的NP难题。传统装配序列方法研究主要着眼于通过增加约束的方式减少无效序列的生成，而面对拥有大量可行装配序列的复杂装配体时依然收效甚微。为此在分析和总结现有装配序列生成算法的基础上，本文对解决组合问题方面取得成功的OBDD符号技术在装配序列生成中的应用

4、进行了研究。本文主要研究内容和结论如下：(1)在现有装配体模型的基础上进行简化，建立了一种新的基于OBDD符号技术的装配体模型。在此新模型的基础上，提出相应的基于OBDD的可行装配序列推理算法。分析表明该推理算法是正确完备的。(2)综合分析了现有求无向图所有割集的算法特点，提出基于OBDD的并行枚举割集算法，并通过理论证明了该算法的正确性。为无向图割集生成开辟了一条新的途径。(3)从装配体CAD模型中提取装配体中各零件的接触信息，建立了基于OBDD的装配体无向联接图模型。在此基础上，利用OBDD并行枚举割集算法生成装配体的所有装配割集。

5、(4)从装配体CAD模型中提取装配体中各零件的干涉信息，建立了OBDD并行干涉检测模型。并对生成的装配割集进行几何可行性判断。从而得到了完整的OBDD可行装配序列割集生成算法。实验结果表明这种基于OBDD的可行装配序列生成算法是正确完备的。关键词：装配序列生成；推理算法；割集；OBDD；i万方数据基于OBDD的装配序列生成算法研究AbstractThegenerationofallfeasibleassemblysequencesforgivenproductsisthekeyofassemblysequencesplanning(AS

6、P)andalsoanNP-hardproblem.Traditionalstudyonmethodsforgenerationofassemblysequencesmainlyfocusesonhowtoimposemoreconstraintstoreduceinvalidassemblysequences,whileitdoeslittleworkoncomplicatedassembliesthathavealargenumberofassemblysequences.Fortheendthattoexpandthescaleo

7、fassemblieswhichASPcanbeappliedto,inthispaper,aresearchwasconductedtointroduceOrderedBinaryDecisionDiagram(OBDD),akindofsymbolictechnologythathasmadeachievementsoncombinatorialproblems,intogenerationofassemblysequences.Andtheworkandresultsonthisresearchinclude:(1)AnewOBD

8、D-basedmodelofassembliesisestablishedatthebaseofreducedexistingmodels.AndanewOBDD-basedreasoningalgorit