学位论文 > 优秀研究生学位论文题录展示

约束满足问题的符号算法及其在装配规划中的应用研究

作　者: 徐周波
导　师: 古天龙
学　校: 西安电子科技大学
专　业: 模式识别与智能系统
关键词: 约束满足问题装配体模型装配序列生成符号算法有序二叉决策图
分类号: TP301.6
类　型: 博士论文
年　份: 2012年
下　载: 70次
引　用: 1次
阅　读: 论文下载

内容摘要

约束满足问题（CSP）是人工智能和计算机科学领域的一个重要研究课题，现实生活中的大量问题均可以适当地描述成一个CSP。由于受组合复杂性问题的制约，传统的CSP求解算法无法高效地求解大规模CSP。采用隐式的符号表示和操作技术是缓减乃至克服组合爆炸问题的一种可行策略。装配序列规划是产品设计生产过程中的重要环节，它极大地影响着装配成本及生产周期。装配序列规划的目标是求解满足各种装配约束条件的可行装配序列，通过适当描述，可将装配序列规划问题转化为约束满足问题。本文以有序二叉决策图和代数决策图为基础，对约束满足问题的符号求解技术进行了探索和研究；在此基础上，对装配序列规划问题的约束求解技术进行了研究。论文主要研究结果包括：1.对经典约束满足问题进行了研究。通过建立变量和变量域的二进制编码，以及约束的布尔特征函数表示，给出了经典CSP的有序二叉决策图（OBDD）描述。将经典CSP中的约束按变量在约束图中的度进行归类，结合问题归约法，提出了一种新的求解经典CSP的符号OBDD算法。为进一步提高算法的执行效率，结合桶消元算法，提出了经典CSP求解的符号OBDD桶消元算法。通过与传统桶消元算法和符号直接求解算法的实验对比，结果表明本文提出的两种符号算法均扩大了问题的求解规模，并提高了算法的执行效率。2.对加权约束满足问题（WCSP）进行了研究。通过对变量和变量域值的二进制编码，将WCSP转换成伪布尔函数表示，进而给出了WCSP的代数决策图（ADD）描述。在此基础上，将ADD的符号操作技术与分支定界搜索算法以及桶消元算法相结合，引入结点一致性预处理技术，在静态变量序的情况下给出了求解WCSP的符号ADD算法。为了进一步提高该算法的搜索下界，通过引入有向弧一致性计数技术，给出了另一种符号ADD求解算法。对大量随机生成的测试用例进行实验分析，结果表明本文提出的两种符号算法在性能上明显优于带有结点一致性或存在有向弧一致性技术的具有前向检查功能的深度优先分支定界搜索算法。3.对装配体模型及装配序列的符号OBDD表示进行了研究。通过对装配体中零件的二进制编码，基于符号OBDD技术，给出了装配体联结图和Gottipolu装配体模型的OBDD描述。建立了装配状态和装配任务的布尔函数表示，给出了装配序列的符号OBDD表示。建立了从装配序列的AND/OR图模型到OBDD表示的转换规则，给出了AND/OR图的符号OBDD表示。通过与装配序列表示的与或图模型、有向图模型的实验对比，结果表明，装配序列的符号OBDD表示具有较高的存储效率，适合于复杂装配体的可行装配序列的描述。4.基于拆卸法对装配序列规划问题进行了研究。通过对无向图的OBDD表示的重新分析，给出了装配联接图的新的OBDD表示和移动向量函数的共享二叉决策图（SBDD）表示。针对无向图G，给出了求解图G的顶点子集的导出子图的符号OBDD技术和判定图G的连通性的符号OBDD技术，并在此基础上，基于Sharafat递归收缩算法的思想，给出了求解无向图G的所有割集的符号OBDD算法。基于装配联接图和移动向量函数的新的符号表示模型，将符号OBDD割集算法与装配序列的割集分解法相结合，利用OBDD的符号操作实现装配操作的几何可行性分析，给出了装配序列的符号OBDD分解算法。通过装配体实验验证了基于分解法的装配序列的符号OBDD算法的正确性和可行性。5.基于装配法对装配序列规划问题进行了研究。以装配联接图和移动向量函数为装配体模型，给出了装配联接图的SBDD表示，移动向量函数的OBDD表示。建立了装配序列规划问题的CSP模型，将装配序列规划问题描述成为一个CSP问题。将生成所有可行装配序列的问题转化为对CSP求解所有可能解的问题，利用回溯算法对CSP问题进行符号OBDD求解，给出了基于CSP模型的装配序列生成的符号OBDD算法。通过装配体实验验证了基于CSP模型的可行装配序列的符号OBDD生成技术的正确性和可行性。

全文目录

作者简介  5-6
摘要  6-8
ABSTRACT  8-13
第一章绪论  13-33
  1.1 问题的来源及研究目的  13
  1.2 研究背景及意义  13-15
  1.3 约束满足问题的研究现状  15-25
    1.3.1 经典约束满足问题  15-17
    1.3.2 经典约束满足问题的求解技术  17-21
      1.3.2.1 基于回溯的方法  17-19
      1.3.2.2 约束传播  19-20
      1.3.2.3 基于图的算法  20
      1.3.2.4 局部修正法  20-21
    1.3.3 软约束满足问题  21-22
    1.3.4 软约束满足问题求解技术  22-25
      1.3.4.1 对Soft CSP的混合求解技术的研究  23-24
      1.3.4.2 对Soft CSP的知识编译的研究  24-25
  1.4 装配序列规划问题及其研究现状  25-30
    1.4.1 装配体建模  25-26
    1.4.2 装配序列规划  26-29
    1.4.3 装配序列表示  29-30
  1.5 本文的研究内容及作者的主要工作  30-32
  1.6 本章小结  32-33
第二章有序二叉决策图及其扩展结构  33-51
  2.1 引言  33
  2.2 布尔函数的各种表示形式  33-35
  2.3 有序二叉决策图（OBDD）  35-41
    2.3.1 OBDD的定义  35-37
    2.3.2 OBDD的基本操作  37-38
    2.3.3 集合的OBDD操作  38-41
  2.4 代数决策图（ADD）  41-48
    2.4.1 ADD的定义  41-42
    2.4.2 ADD的基本操作  42-48
  2.5 CUDD软件包  48-49
  2.6 本章小结  49-51
第三章经典约束满足问题的符号OBDD求解技术  51-61
  3.1 引言  51-52
  3.2 基本概念  52
  3.3 桶消元法  52-54
  3.4 约束满足问题的符号OBDD表示  54-55
  3.5 约束满足问题的符号OBDD求解技术  55-57
  3.6 约束满足问题的符号OBDD桶消元算法  57-59
  3.7 实验结果及分析  59-60
  3.8 本章小结  60-61
第四章加权约束满足问题（WCSP）的符号ADD求解技术  61-73
  4.1 引言  61-62
  4.2 基本概念  62-63
  4.3 深度优先分支定界法  63-64
  4.4 WCSP的符号ADD表示  64-65
  4.5 WCSP的符号ADD求解技术  65-69
  4.6 实验结果及分析  69-72
  4.7 本章小结  72-73
第五章装配体模型及装配序列的符号OBDD表示  73-87
  5.1 引言  73-74
  5.2 基本概念  74-75
  5.3 装配体模型的OBDD表示  75-78
    5.3.1 装配联接图的OBDD表示  75-76
    5.3.2 接触向量和移动向量函数的OBDD表示  76-78
  5.4 装配序列的符号OBDD表示  78-83
    5.4.1 装配序列的符号OBDD表示  78-81
    5.4.2 AND/OR图的符号OBDD表示  81-83
  5.5 实验结果及分析  83-84
  5.6 本章小结  84-87
第六章基于分解法的装配序列生成的符号OBDD算法  87-99
  6.1 引言  87-88
  6.2 Sharafat的递归收缩算法  88-91
  6.3 基于分解法的装配序列生成的符号OBDD算法  91-96
  6.4 实验结果及分析  96-98
  6.5 本章小结  98-99
第七章装配序列规划问题的CSP模型及其符号OBDD算法  99-111
  7.1 引言  99-100
  7.2 装配序列规划问题的CSP模型  100-101
  7.3 基于CSP模型的装配序列生成的符号OBDD算法  101-104
  7.4 装配序列规划实例  104-109
  7.5 本章小结  109-111
第八章总结与展望  111-113
  8.1 结论  111-112
  8.2 未来工作  112-113
致谢  113-115
参考文献  115-125
攻读博士学位期间的研究成果  125-127
  学术著作  125
  学术论文  125
  主持和参加研究的科研项目  125-127

约束满足问题的符号算法及其在装配规划中的应用研究

内容摘要

全文目录

相似论文