约束满足问题的符号算法及其在装配规划中的应用研究
|
摘要
约束满足问题（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生成技术的正确性和可行性。
Constraint satisfaction problem (CSP) is an important research branch in artificialintelligence and computer science. In real life, a variety of different problems can, whenformulated appropriately, be seen as instances of the CSP. With the restricted of thecombination complexity, traditional algorithms for CSP cannot solve large scale CSPefficiently. Using implicitly symbolic representation and manipulation technique is afeasible strategy to combat or ease the combinatorial explosion problem. Assemblysequence planning (ASP) is an important tache in the product designing and producingprocess, it drastically affects the cost of assembly and the production cycle of product.The main target of ASP is to find out the feasible assembly sequence which satisfied allassembly constraints. Thus, ASP can be described as a CSP. Based on the ordered binarydecision diagram and algebraic decision diagram, the symbolic algorithms for CSP areexplored and researched, and constraint solving technique for ASP problem is carriedout on this basis. The main contributions of the dissertation are summarized as follows:
1. A research on classical CSP. By encoding the variables and variable domainswith binary variables and establishing the Boolean characteristic functions of constraint,a novel symbolic scheme to represent classical CSP is proposed using ordered binarydecision diagram (OBDD). All constraints in the classical CSP are classified by thedegree of variables in constraint graph, and a novel symbolic OBDD algorithm forclassical CSP is proposed by combining with problem reduction method. In order toimprove the efficiency of the symbolic algorithm, an improved symbolic OBDDalgorithm is presented by combining with bucket-elimination algorithm. Moreover,compared with the tranditional bucket-elimination algorithm and simplified symbolicalgorithm, the results show that two proposed symbolic algorithms enlarged the scopefor solving and improved the efficiency of the algorithm。
2. A research on weighted constraint satisfaction problem (WCSP). By encodingthe variables and variable domains with binary variables and establishing thepseudo-Boolean characteristic functions of weighted constraint, a novel symbolicscheme to represent WCSP is proposed using algebraic decision diagram (ADD). Onthis basis, a symbolic ADD algorithm is presented, where the branch and boundalgorithm is integrated with buck-elimination algorithm symbolically, and the staticvariable orderings and the node consistency during search are used. The countingtechnique of directional arc consistency is adopted to update the lower bounds of thesymbolic ADD algorithm, and the improved symbolic ADD algorithm is developed. Many experiments on random problems are implemented, and the results show that twoproposed symbolic algorithms outperform the depth-first branch and bound algorithmsenhanced with a look-ahead process and a preprocessing step of either existentialdirectional arc consistency or the node consistency.
3. A research on the symbolic representation of assembly model and assemblysequence. By encoding the parts in assembly with binary variables, OBDD is proposedto representation assembly liaison and Gottipolu’s assembly model. By establishing thepseudo-Boolean characteristic functions of assembly states and assembly tasks, asymbolic scheme to represent assembly sequences is proposed using OBDD. Byestablishing rules to translate AND/OR graph of assembly sequence to OBDDrepresentation, OBDD is proposed to representation AND/OR graph. Experimental testsshow that the OBDD scheme represented all the feasible assembly sequenceoutperforms both AND/OR graph and directed graph in storage efficiency, especially oncomplex assemblies.
4. A research on ASP problem based on disassembly method. Through renewdlyanalyzing OBDD representation of undirected graph, a new OBDD representation ofliaison graph and shared binary decision diagram (SBDD) representation of translationalfunction are presented. Aim at undirected graph G, a symbolic OBDD technique tosolve the induced subgraph of subset of vertices of graph G and a symbolic OBDDtechnique to judge the connectivity of graph G are presented. Then, a symbolic OBDDalgorithm is presented to find all cutest of undirected graph G based on the idea ofSharafat’s recursive contraction algorithm. Based on the new symbolic model of liaisongraph and translational function, a symbolic OBDD algorithm for generating assemblysequences using decomposition method is proposed, where the symbolic OBDD-basedcutset algorithm is integrated with cutest decomposition approach for generatingassembly sequence, and the geometrical feasibility checking is implemented bysymbolilc OBDD manipulation. Some applicable experiments show that the symbolicOBDD algorithm using decomposion approach can generate assembly sequencecorrectly and completely.
5. A research on ASP problem based on assembly method. In order to formulateASP problem, the SBDD is proposed to represent the assembly liaison graph, and thetranslational function is represented as OBDD. The ASP problem was formulated as aCSP by establishing the CSP model of ASP problem, and the feasible assemblysequences are generated by solving the corresponding CSP model. Moreover, thesymbolic OBDD based backtracking technique is given to generate all geometrically feasible assembly sequences. Experiments are also conducted to verify that the symbolicOBDD based CSP scheme can handle the ASP problem properly and efficiently.
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生成技术的正确性和可行性。
Constraint satisfaction problem (CSP) is an important research branch in artificialintelligence and computer science. In real life, a variety of different problems can, whenformulated appropriately, be seen as instances of the CSP. With the restricted of thecombination complexity, traditional algorithms for CSP cannot solve large scale CSPefficiently. Using implicitly symbolic representation and manipulation technique is afeasible strategy to combat or ease the combinatorial explosion problem. Assemblysequence planning (ASP) is an important tache in the product designing and producingprocess, it drastically affects the cost of assembly and the production cycle of product.The main target of ASP is to find out the feasible assembly sequence which satisfied allassembly constraints. Thus, ASP can be described as a CSP. Based on the ordered binarydecision diagram and algebraic decision diagram, the symbolic algorithms for CSP areexplored and researched, and constraint solving technique for ASP problem is carriedout on this basis. The main contributions of the dissertation are summarized as follows:
1. A research on classical CSP. By encoding the variables and variable domainswith binary variables and establishing the Boolean characteristic functions of constraint,a novel symbolic scheme to represent classical CSP is proposed using ordered binarydecision diagram (OBDD). All constraints in the classical CSP are classified by thedegree of variables in constraint graph, and a novel symbolic OBDD algorithm forclassical CSP is proposed by combining with problem reduction method. In order toimprove the efficiency of the symbolic algorithm, an improved symbolic OBDDalgorithm is presented by combining with bucket-elimination algorithm. Moreover,compared with the tranditional bucket-elimination algorithm and simplified symbolicalgorithm, the results show that two proposed symbolic algorithms enlarged the scopefor solving and improved the efficiency of the algorithm。
2. A research on weighted constraint satisfaction problem (WCSP). By encodingthe variables and variable domains with binary variables and establishing thepseudo-Boolean characteristic functions of weighted constraint, a novel symbolicscheme to represent WCSP is proposed using algebraic decision diagram (ADD). Onthis basis, a symbolic ADD algorithm is presented, where the branch and boundalgorithm is integrated with buck-elimination algorithm symbolically, and the staticvariable orderings and the node consistency during search are used. The countingtechnique of directional arc consistency is adopted to update the lower bounds of thesymbolic ADD algorithm, and the improved symbolic ADD algorithm is developed. Many experiments on random problems are implemented, and the results show that twoproposed symbolic algorithms outperform the depth-first branch and bound algorithmsenhanced with a look-ahead process and a preprocessing step of either existentialdirectional arc consistency or the node consistency.
3. A research on the symbolic representation of assembly model and assemblysequence. By encoding the parts in assembly with binary variables, OBDD is proposedto representation assembly liaison and Gottipolu’s assembly model. By establishing thepseudo-Boolean characteristic functions of assembly states and assembly tasks, asymbolic scheme to represent assembly sequences is proposed using OBDD. Byestablishing rules to translate AND/OR graph of assembly sequence to OBDDrepresentation, OBDD is proposed to representation AND/OR graph. Experimental testsshow that the OBDD scheme represented all the feasible assembly sequenceoutperforms both AND/OR graph and directed graph in storage efficiency, especially oncomplex assemblies.
4. A research on ASP problem based on disassembly method. Through renewdlyanalyzing OBDD representation of undirected graph, a new OBDD representation ofliaison graph and shared binary decision diagram (SBDD) representation of translationalfunction are presented. Aim at undirected graph G, a symbolic OBDD technique tosolve the induced subgraph of subset of vertices of graph G and a symbolic OBDDtechnique to judge the connectivity of graph G are presented. Then, a symbolic OBDDalgorithm is presented to find all cutest of undirected graph G based on the idea ofSharafat’s recursive contraction algorithm. Based on the new symbolic model of liaisongraph and translational function, a symbolic OBDD algorithm for generating assemblysequences using decomposition method is proposed, where the symbolic OBDD-basedcutset algorithm is integrated with cutest decomposition approach for generatingassembly sequence, and the geometrical feasibility checking is implemented bysymbolilc OBDD manipulation. Some applicable experiments show that the symbolicOBDD algorithm using decomposion approach can generate assembly sequencecorrectly and completely.
5. A research on ASP problem based on assembly method. In order to formulateASP problem, the SBDD is proposed to represent the assembly liaison graph, and thetranslational function is represented as OBDD. The ASP problem was formulated as aCSP by establishing the CSP model of ASP problem, and the feasible assemblysequences are generated by solving the corresponding CSP model. Moreover, thesymbolic OBDD based backtracking technique is given to generate all geometrically feasible assembly sequences. Experiments are also conducted to verify that the symbolicOBDD based CSP scheme can handle the ASP problem properly and efficiently.
引文
[1]苏强,林志航.计算机辅助装配顺序规划研究综述.机械科学与技术,1999,18(6):1006-1009
[2]石淼,唐朔飞,李明树.装配序列规划研究综述.计算机研究与发展,1996,31(6):30-34
[3]付宜利,田立中,谢龙等.基于有向割集分解的装配序列生成方法.机械工程学报,2003,39(6):58-62
[4] De Fazio T L, Whitney D E. Simplified generation of all mechanical assemblysequences. IEEE Journal of Robotics and Automation,1987, RA-3(6):640-658
[5] Homem de Mello L S, Sanderson A C. A correct and complete algorithm for thegeneration of mechanical assembly sequences. IEEE Transactions on Roboticsand Automation,1991,7(2):228-240
[6] Baldwin D F, Abell T E, Lui M C M, et al. An integrated computer aid forgenerating and evaluating assembly sequences for mechanical products, IEEETransactions on Robotics and Automation,1991,7(1):78-89
[7]李磊,魏生民,张军波.装配割集的可行性判断.计算机集成制造系统.2002,8(12):70-73
[8] Huang Y F, Lee C S G. An automatic assembly planning system, IEEEInternatinal Conference on Robotics and Automation,1990,3:1594-1599
[9] Tonshoff H K, Menzel E, Park H S. A knowledge-based system for automatedassembly planning. CIRP Annals–Manufacturing Technology,1992,41(1):19-24
[10] Heemskerk C J M, Reijers L N, Kals H J J. A concept for computer-aided processplanning of flexible assembly. CIRP Annals–Manufacturing Technology,1990,9(1):25-28
[11]周西苓.装配序列规划专家系统.模式识别与人工智能,1998,11(1):1-6
[12] Brailsford S C, Potts C N, Smith B M. Constraint satisfaction problems:algorithms and applications. European Journal of Operational Research,1999,119(3):557-581
[13] Miguel I, Shen Q. Solution techniques for constraint satisfaction problems:foundations. Artificial Intelligence Review,2001,15(4):243-267
[14] Miguel I, Shen Q. Solution techniques for constraint satisfaction problems:advanced approaches. Artificial Intelligence Review,2000,15(4):269-293
[15] Bryant R E. Symbolic Boolean manipulation with ordered binary decisiondiagrams. ACM Computing Surveys,1992,24(3):293-318
[16] Bryant R E. Graph-based algorithms for Boolean function manipulation. IEEETransactions on Computers,1986,35(8):677-691
[17] Drechsler R, Sieling D. Binary decision diagrams in theory and practice.International Journal on Software Tools for Technology Transfer,2001,3(2):112-136
[18]吕宗伟,林争辉,张镭. OBDD在组合逻辑电路测试中的应用研究.计算机辅助设计与图形学学报,2001,13(6):495-499
[19] Burch J R, Clarke E M, McMillan K L, et al. Symbolic model checking:1020states and beyond. Information and Computation,1998,98(2):142-170
[20] Cimatti A, Pistore M. Conformant planning via symbolic model checking.Journal of Artificial Intelligence Research,2000,13:305-338
[21] Hachtel G D, Somenzi F. A symbolic algorithm for maximum flow in0-1network. Formal Methods in System Design,1997,10(2-3):207-219
[22] Bachar R I, Frohm E A, Gaona C M, et al. Algebraic decision diagrams and theirapplications. Formal Methods in Systems Design,1997,10(2-3):171-206
[23] Bachar R I, Hachtel G D, Pardo A, et al. An ADD-based algorithm for shortestpath back-tracing of large graphs. Proceedings of the IEEE Great LakesSymposium on VLSI,1994:248-251
[24] Bachar R I, Cho H, Hachtel G D, et al. Timing analysis of combinational circuitsusing ADD’s. Proceedings of the European Conference on Design Automation,1994:625-629
[25] Huffman D A. Impossible objects as nonsense sentences. Edinbrugh UniversityPress, Machine Intelligence6, Edinburgh: Meltzer B, Michie D,1971:295-323
[26] Clowes M B. On seeing things. Artificial Intelligence,1971,2(1):79-116
[27] Waltz D L. Generating semantic descriptions from drawings of scenes withshadows. Technical Report AI-TR-271, Massachusetts Institute of Technology,Cambridge, MA,1972
[28] Dechter R, Pearl J. Tree clustering for constraint networks. Artificial Intelligence,1989,38(3):353-366
[29] Cabon B, De Givry S, Lobjois L, et al. Radio link frequency assignment.Constraints,1999,4(1):79-89
[30] Sadeh N, Sycara K, Xiong Y. Bachtracking techniques for the job shopscheduling constraint satisfaction problem. Artificial Intelligence,1995,76(1-2):455-480
[31] Pham D N, Thornton J, Sattar A. Modelling and solving temporal reasoning aspropositional satisfiability. Artificial Intelligence,2008,172(15):1725-1782
[32]伍丽华,陈蔼洋,姜云飞.规划问题编码为约束可满足问题的研究.计算机科学,2006,33(8):187-292
[33]史忠植.高级人工智能(第二版).科学出版社,2006:81-91
[34] Dechter R, Frost D. Backjump-based backtracking for constraint satisfactionproblems. Artificial Intelligence,136(2):147-188,2002
[35] Dechter R. Enhancement schemes for constraint processing: backjumping,learning, and cutest decomposition. Artificial Intelligence,1990,41(3):273-312
[36] Haralick R M, Elliot G L. Increasing tree-search efficiency for constraintsatisfaction problems. Artificial Intelligence,1980,14(3):263-313
[37] Frost D, Dechter R. Look-ahead value ordering for constraint satisfactionproblems. Proceedings of the14th International Joint Conference on ArtificialIntelligence,1995:572-578
[38] Paul W P J. Search rearrangement backtracking and polynomial average time.Artificial Intelligence,1983,21(1-2):117-133
[39] Freuder E C. A sufficient condition for backtrack-free search. Journal of theACM,1982,29(1):24-32
[40] Dechter R, Meiri I. Experimental evaluation of preprocessing algorithms forconstraint satisfaction problems. Artificial Intelligence,1994,68(2):211-241
[41] Bacchus F, van Run P. Dynamic variable ordering in CSPs. Proceedings of the1st International Conference on Principles and Practice of ConstraintProgramming,1995,976:258-275
[42] Bitner J R, Reingold E M. Backtrack programming techniques, Communicationsof the ACM,1975,18(11):651-656
[43] Bessière C, Regn J C. MAC and combined heuristics: two reasons to forsake FC(and CBJ?) on hard problems. Proceedings of the2nd International Conferenceon Priniciples and Practice of Constraint Programming,1996,1118:61-75
[44] Waltz D L. Understanding line drawings of scenes with shadows. ThePsychology of Computer Vision. New York, US: McGraw-Hill,1975:19-91
[45] Mackworth A K. Consistency in networks of relations. Artificial Intelligence,1977,8(1):118-126
[46] Mohr R, Henderson T C. Arc and path consistency revisited. ArtificialIntelligence,1986,28(2):225-233
[47] Van Hentenryck P, Deville Y, Teng C M. Generic arc-consistency algorithm andits specializations. Artificial Intelligence,1992,57(2-3):291-321
[48] Bessière C. Arc-consistency and arc-consistency again. Artificial Intelligence,1994,65(1):179-190
[49] Bessière C, Freduer E C, Regn J C. Using inference to reduce arc consistencycomputation. Proceedings of the14th International Joint Conference on ArtificialIntelligence,1995:592-598
[50] Bessière C, Regin J C. Refining the basic constraint propagateion algorithm.Proceedings of the17th International Joint Conference on Artificial Intelligence,2001:309-315
[51] Mackworth A K. Consistency in networks of relations. Artificial Intelligence,1977,8(1):99-118
[52] Gottlob G, Leone N, Scarcello F. A comparison of structural CSP decompositionmethods. Artificial Intelligence,2000,124(2):243–282
[53] Blum C, Roli A. Metaheuristics in combinatorial optimization: overview andconceptual comparison. ACM Computing Surveys,2003,35(3):268-308
[54] Bistarelli S, Montanari U, Rossi F. Semiring-based constraint satisfaction andoptimization. Journal of ACM,1997,44(2):201-236
[55] Schiex T, Fargier H, Verfaillie G. Valued constraint satisfaction problems: hardand easy problems. Proceedings of the14th International Joint Conference inArtificial Intelligence,1995:631-637
[56] Meseguer P, Bouhmala N, Bouzoubaa T, et al. Current approach for solving over-constrained problems. Constraints,2003,8(1):9-39
[57] Dubois D, Fargier H, Prade H. Possibility theory in constraint satisfactionproblems: handling priority, preference and uncertainty. Applied Intelligence,1996,6(4):287-309
[58] Freuder E, Wallace R. Partial constraint satisfaction. Artificial Intelligence,1992,58(1-3):21-71
[59] Larrosa J, Schiex T.. Solving weighted CSP by maintaining arc-consistency.Artificial Intelligence,2004,159(1-2):1-26
[60] Fragier H, Lang J. Uncertainty in constraint satisfaction problems: a probabilisticapproach. Proceedings of the2nd European Conference on Symbolic andQuantitative Approaches to Reasoning and Uncertainty,1993:97-104
[61] Bistarelli S, Montanari U, Rossi, F. Constraint solving over semirings.Proceedings of the14th International Joint Conference in Artificial Intelligence,1995:624-630
[62] Cooper M, Schiex T. Arc consistency for soft constraints. Artificial ntelligence,2004,154(1-2):199-227
[63] Larrosa J, Meseguer P, Schiex T. Maintaining reversible DAC for Max-CSP.Artificial Intelligence,1999,107(1):149-163
[64] Larrosa J, Schiex T. In the quest of the best form of local consistency forweighted CSP. Proceedings of the18th International Joint Conference onArtificial Intelligence,2003:239-244
[65] De Givry S, Heras F. Existential arc consistency: getting closer to full arcconsistency in weighted CSP. Proceedings of the19th International JointConference on Artificial Intelligence,2005:84-89
[66] Cooper M C, De Givry S, Sanchez M, et al. Virtual arc consistency for weightedCSP. Proceedings of the23rd National Conference on Artificial Intelligence,2008,1:253-258
[67] Cooper M C, De Givry S, Sanchez M, et al. Soft arc consistency revisited.Artificial Intelligence,2010,174(7-8):449-478
[68] Terrioux C, Jegou P. Hybrid backtracking bounded by tree-decomposition ofconstraint network. Artificial Intelligence,2003,146(1):43-75
[69] De Givry S, Schiex T, Verfaillie G. Exploiting tree decomposition and soft localconsistency in weighted CSP. Proceedings of the21st National Conference onArtificial Intelligence,2006,1:22-27
[70] Verfaillie G, Lemaitre M, Schiex T. Russian doll search for solving constraintoptimization problems. Proceedings of the13th National Conference onArtificial Intelligence,1996,1:181-187
[71] Sanchez M, Allouche D, De Givry S, et al. Russian doll search with treedecomposition. Proceedings of the21st International Joint Conference onArtificial Intelligence,2009:603-608
[72] Kash K, Dechter R. Branch and bound with mini-bucket heuristics. Proceedingsof the16th International Joint Conference on Artificial Intelligence,1999:426-433
[73] Dechter R, Rish I. Mini-buckets: A general scheme for bounded inference.Journal of ACM,2003,50(2):107-153
[74] Wallace R. Enhancements of branch and bound methods for maximal constraintsatisfaction problem. Proceedings of the13th National Conference on ArtificialIntelligence,1996,1:188-195
[75] Nonobe K, Ibaraki T. An improved tabu search method for the weightedconstraint satisfaction problem. INFOR,2001,39(2):131-151
[76] Gallardo J E, Cotta C, Fernández A J. Solving weighted constraint satisfactionproblems with memetic/exact hybrid algorithms. Journal of ArtificialIntelligence Research,2009,35(1):533-555
[77] Dechter R, Mateescu R. AND/OR search space for graphical models. ArtificialIntelligence,2007,171(2-3):73-106
[78] Mateescu R, Dechter R. AND/OR multi-valued decision diagrams (AOMDDs)for weighted graphical models. Journal of Artificial Intelligence Research,2008,33(1):465-519
[79] Marinescu R, Dechter R. AND/OR branch-and-bound search for combinatorialoptimization in graphical models. Artificial Intelligence,2009,173(16-17):1457-1491
[80] Wilson N. Decision diagrams for the computation of semiring valuations.Proceedings of the19th International Joint Conference on Artificial Intelligence,2005:331-336
[81] Sachenbacher M, Williams B C. Bounded search and symbolic inference forconstraint optimization. Proceedings of the19th International Joint Conferenceon Artificial Intelligence,2005:266-291
[82] Boutaleb K, Jégou P.(No)good recording and ROBDDs for solving structured(V)CSPs. Proceedings of the18th IEEE International Conference on Tools withArtificial Intelligence,2006:297-304
[83] Homem de Mello L. S., Sanderson A. C. Representations of mechanicalassembly sequences. IEEE Transactions on Robotics and Automation,1991,7(2):211-227
[84] Wilson R H. Minimizing user queries in interactive assembly planning. IEEETransactions on Robotics and Automation,1995,11(2):308-311
[85] Gottipolu R. B., Ghosh K., An integrated approach to the generation of assemblysequences. International Journal of Computer Application in Technology,1995,8(3-4):125-138
[86] Gottipolu R. B., Ghosh K., A simplified and efficient representation forevaluation and selection of assembly sequences. Computer in Industry,2003,50(3):251-264
[87] Bourjault A, Lambert J L. Design of an automated hard disk unit assemblysystem. Proceedings of the18th International Symposium on Industrial Roboots,1988:19-28
[88] Wilson R H, Latombe J C. Geometric reasoning about mechanical assembly.Artificial Intelligence,1994,71(2):371-396
[89]张建标,唐荣锡,魏生民等.装配顺序的生成算法研究.机械工程学报,1999,35(5):58-61
[90] Wesley M A, Lozano Perez T, Lieberman L I, et al. Geometric modeling systemfor automated mechanical assembly. IBM Journal of Research Development,1980,24(1):64-74
[91] Lee K, Gossard D C. A hierarchical data structure for representing assemblies:Part1. Computer-aided Design,1985,17(1):15-19
[92] Ishii K. Life-cycle engineering design. Journal of Mechanical Design,Transactions of the ASME,1995,117B:42-47
[93]冯毅雄,谭建荣,郑兵等.基于语义关联与驱动的产品概念装配模型研究.机械工程学报,2004,40(4):114-118
[94]纪杨建,谭建荣,伊国栋等.基于语义元的设计方案形式化与重用方法研究.机械工程学报,2004,40(2):30-36
[95] Dini G, Santochi M. Automated sequencing and subassembly detection inassembly planning. CIRP Annals–Manufacturing Technology,1992,41(1):1-4
[96]李海龙,董金祥,葛建新等，基于约束的装配体技术,计算机辅助设计与图形学报,1997,9(3):249-255
[97] Anahtha R, Kramer G. Assembly modeling by geometric constraint satisfaction.Computer-aided Design,1996,28(9):707-722
[98] Zha X F, Samuel Y E, Fok S C. Integrated knowledge-based assembly assemblysequence planning. International Journal of Advanced ManufacturingTechnology,1998,14:50-64
[99] Oliver J H, Huang H T. Automated path planning for integrated assembly design.Computer-Aided Design,1994,26(9):658-666.
[100] Ghen L L, Woo T C. Computational geometry on the sphere with application toautomated machining. American Society of Mechanical Engineering, DesignEngineering Division (Publication) DE,1990,23(pt1):165-174
[101] Laperriere L, Elmaraghy H A. GAPP: A generative assembly process planner.Jouranl of Manufactureing Systems,1996,15(4):282-293
[102] Huang Y F, Lee C S G. Precedence knowledge in feature mating operationassembly planning. IEEE International Conference on Robotics and Automation,1989,5:216-221
[103] Swaminathan A, Suzanne Barber K. An Experience-based assembly sequencesplaner for mechanical assembly. IEEE Transactions on Robotics and Automation,1996,12(2):252-267
[104]苏强，林志航，马万太等.基于事例推理的装配顺序规划研究.中国机械工程,1999,10(2):171-174
[105] Ko H, Lee K. Automatic assembling procedure generation from matingconditions. Computer-Aided Design,1987,119(1):3-10
[106] Qian W, Yan Y, Zhao X, et al. List representation of assembly sequences.Proceedings of The IEEE International Conference on Industrial Technology,1996,315-319
[107] Landam J, Dialami F. The Assembly State Vector: a new approach to thegeneration of assembly sequences. Proceedings of the4th IEEE InternationalSymposium on Assembly and Task Planning,2001:37-42
[108] Prenting T, Battaglin R. The precedence diagram: A tool for analysis in assemblyline balancing. Journal of Industrial Engineering,1964,15(4):208-213
[109] Warrats J J, Bonschancher N, Bronsvoort W F. A semiautomatic sequenceplanner. Proceeding of IEEE International Conference on Robotics andAutomation,1992:2431-2438
[110] Homem de Mello L S, Sanderson A C. AND/OR graph representation ofassembly plans. IEEE Transactions on Robotics and Automation,1990,6(2):188-199
[111] Lee C Y. Representation of switching circuits by binary decision programs. BellSystem Technical Journal,1959,38(4):985-999
[112] Akers S B. Binary decision diagrams. IEEE Transactions on Computers,1978,27(6):509-516
[113] Clarke E M, McMillan K L, Zhao X, et al. Multi-terminal binary decisiondiagrams: an efficient data structure for matrix representation. Proceedings ofInternational Workshop on Logic Synthesis,1993:1-15
[114] Lai Y T, Vrudhula S B K, Pedram M. EVBDD-based algorithms for linearinteger programming, spectral transformation and function decomposition. IEEETransactions on Computer Aided Design,1994,13(8):959-975
[115] Bryant R E, Chen Y A. Verification of arithmetic circuits using binary momentdiagrams. International Journal on Software Tools for Technology Transfer,2001,3(2):137-155
[116] Somenzi F. CUDD: CU decision diagram package release2.3.1.http://vlsi.Colorado.edu/fabio/CUDD/cuddIntro.html
[117] Minato S. Zero-suppressed BDDs and their applications. International Journal onSoftware Tools for Technology Transfer,2001,3(2):156-170
[118] Dechter R. Bucket elimination: A unifying framework for reasoning. ArtificialIntelligence,1999,113(1-2):41-85
[119] Pan G Q, Vardi M Y. Symbolic techniques in satisfiability solving. Journal ofAutomated Reasoning,2005,35(1-3):25-50
[120] Walsh T. SAT v CSP. Proceedings of the6th international Conference onPrinciples and Practice of Constraint Programming,2000,1894:441-456
[121]贺仁杰,谭跃进.加权约束满足问题的改进深度优先搜索算法.系统工程学报,2004,19(5):512-516
[122] Chatalic P, Simon L. Multi-resolution on compressed sets of clauses.Proceedings of the12th International Conference on Tools with ArtificialIntelligence,2000:2-10
[123]徐周波,古天龙,赵岭忠.网络最大流问题的一种新的符号ADD求解算法.通信学报,2005,26(2):1-8
[124] Larrosa J, Meseguer P. Exploiting the use of DAC in Max-CSP. Proceedings ofthe2nd International Conference on Principle and Practice of ConstraintProgramming,1996:308-322
[125] Wallace R. Directed arc consistency preprocessing. Proceedings of EuropeanConference on Artificial Intelligence Workshop on Constraint Processing,1995:121-137
[126] Sharafat A R, Ma’rouzi O R. A novel and efficient algorithm for scanning allminimal cutsets of a graph. ArXiv preprint math, CO/0211436,2002
[127] Gu T, Liu H. The symbolic OBDD scheme for generating mechanical assemblysequences. Formal Methods in System Design,2008,33(1-3):29-44
[128]钟艳如,黄美发,古天龙.装配序列生成的有序二叉决策图技术研究.计算机集成制造系统,2008,14(10):1996-2004
[129] Tsukiyama S, Shirakawa I, Ozaki H, et al. An algorithm to enumerate all cutsetsof a graph in linear time per cutest. Journal of the ACM,1980,27(4):619-632
[130] Minato S, Ishiua N, Yajima S. Shared binary decision diagram with attributededges for efficient Boolean function manipulation. Proceedings of the27th ACM/IEEE Design Automation Conference,1990:52-57
[131] Purvis L S. Intelligent design problem solving using case based and constraintbased techniques. Connecticut: University of Connecticut,1995
[2]石淼,唐朔飞,李明树.装配序列规划研究综述.计算机研究与发展,1996,31(6):30-34
[3]付宜利,田立中,谢龙等.基于有向割集分解的装配序列生成方法.机械工程学报,2003,39(6):58-62
[4] De Fazio T L, Whitney D E. Simplified generation of all mechanical assemblysequences. IEEE Journal of Robotics and Automation,1987, RA-3(6):640-658
[5] Homem de Mello L S, Sanderson A C. A correct and complete algorithm for thegeneration of mechanical assembly sequences. IEEE Transactions on Roboticsand Automation,1991,7(2):228-240
[6] Baldwin D F, Abell T E, Lui M C M, et al. An integrated computer aid forgenerating and evaluating assembly sequences for mechanical products, IEEETransactions on Robotics and Automation,1991,7(1):78-89
[7]李磊,魏生民,张军波.装配割集的可行性判断.计算机集成制造系统.2002,8(12):70-73
[8] Huang Y F, Lee C S G. An automatic assembly planning system, IEEEInternatinal Conference on Robotics and Automation,1990,3:1594-1599
[9] Tonshoff H K, Menzel E, Park H S. A knowledge-based system for automatedassembly planning. CIRP Annals–Manufacturing Technology,1992,41(1):19-24
[10] Heemskerk C J M, Reijers L N, Kals H J J. A concept for computer-aided processplanning of flexible assembly. CIRP Annals–Manufacturing Technology,1990,9(1):25-28
[11]周西苓.装配序列规划专家系统.模式识别与人工智能,1998,11(1):1-6
[12] Brailsford S C, Potts C N, Smith B M. Constraint satisfaction problems:algorithms and applications. European Journal of Operational Research,1999,119(3):557-581
[13] Miguel I, Shen Q. Solution techniques for constraint satisfaction problems:foundations. Artificial Intelligence Review,2001,15(4):243-267
[14] Miguel I, Shen Q. Solution techniques for constraint satisfaction problems:advanced approaches. Artificial Intelligence Review,2000,15(4):269-293
[15] Bryant R E. Symbolic Boolean manipulation with ordered binary decisiondiagrams. ACM Computing Surveys,1992,24(3):293-318
[16] Bryant R E. Graph-based algorithms for Boolean function manipulation. IEEETransactions on Computers,1986,35(8):677-691
[17] Drechsler R, Sieling D. Binary decision diagrams in theory and practice.International Journal on Software Tools for Technology Transfer,2001,3(2):112-136
[18]吕宗伟,林争辉,张镭. OBDD在组合逻辑电路测试中的应用研究.计算机辅助设计与图形学学报,2001,13(6):495-499
[19] Burch J R, Clarke E M, McMillan K L, et al. Symbolic model checking:1020states and beyond. Information and Computation,1998,98(2):142-170
[20] Cimatti A, Pistore M. Conformant planning via symbolic model checking.Journal of Artificial Intelligence Research,2000,13:305-338
[21] Hachtel G D, Somenzi F. A symbolic algorithm for maximum flow in0-1network. Formal Methods in System Design,1997,10(2-3):207-219
[22] Bachar R I, Frohm E A, Gaona C M, et al. Algebraic decision diagrams and theirapplications. Formal Methods in Systems Design,1997,10(2-3):171-206
[23] Bachar R I, Hachtel G D, Pardo A, et al. An ADD-based algorithm for shortestpath back-tracing of large graphs. Proceedings of the IEEE Great LakesSymposium on VLSI,1994:248-251
[24] Bachar R I, Cho H, Hachtel G D, et al. Timing analysis of combinational circuitsusing ADD’s. Proceedings of the European Conference on Design Automation,1994:625-629
[25] Huffman D A. Impossible objects as nonsense sentences. Edinbrugh UniversityPress, Machine Intelligence6, Edinburgh: Meltzer B, Michie D,1971:295-323
[26] Clowes M B. On seeing things. Artificial Intelligence,1971,2(1):79-116
[27] Waltz D L. Generating semantic descriptions from drawings of scenes withshadows. Technical Report AI-TR-271, Massachusetts Institute of Technology,Cambridge, MA,1972
[28] Dechter R, Pearl J. Tree clustering for constraint networks. Artificial Intelligence,1989,38(3):353-366
[29] Cabon B, De Givry S, Lobjois L, et al. Radio link frequency assignment.Constraints,1999,4(1):79-89
[30] Sadeh N, Sycara K, Xiong Y. Bachtracking techniques for the job shopscheduling constraint satisfaction problem. Artificial Intelligence,1995,76(1-2):455-480
[31] Pham D N, Thornton J, Sattar A. Modelling and solving temporal reasoning aspropositional satisfiability. Artificial Intelligence,2008,172(15):1725-1782
[32]伍丽华,陈蔼洋,姜云飞.规划问题编码为约束可满足问题的研究.计算机科学,2006,33(8):187-292
[33]史忠植.高级人工智能(第二版).科学出版社,2006:81-91
[34] Dechter R, Frost D. Backjump-based backtracking for constraint satisfactionproblems. Artificial Intelligence,136(2):147-188,2002
[35] Dechter R. Enhancement schemes for constraint processing: backjumping,learning, and cutest decomposition. Artificial Intelligence,1990,41(3):273-312
[36] Haralick R M, Elliot G L. Increasing tree-search efficiency for constraintsatisfaction problems. Artificial Intelligence,1980,14(3):263-313
[37] Frost D, Dechter R. Look-ahead value ordering for constraint satisfactionproblems. Proceedings of the14th International Joint Conference on ArtificialIntelligence,1995:572-578
[38] Paul W P J. Search rearrangement backtracking and polynomial average time.Artificial Intelligence,1983,21(1-2):117-133
[39] Freuder E C. A sufficient condition for backtrack-free search. Journal of theACM,1982,29(1):24-32
[40] Dechter R, Meiri I. Experimental evaluation of preprocessing algorithms forconstraint satisfaction problems. Artificial Intelligence,1994,68(2):211-241
[41] Bacchus F, van Run P. Dynamic variable ordering in CSPs. Proceedings of the1st International Conference on Principles and Practice of ConstraintProgramming,1995,976:258-275
[42] Bitner J R, Reingold E M. Backtrack programming techniques, Communicationsof the ACM,1975,18(11):651-656
[43] Bessière C, Regn J C. MAC and combined heuristics: two reasons to forsake FC(and CBJ?) on hard problems. Proceedings of the2nd International Conferenceon Priniciples and Practice of Constraint Programming,1996,1118:61-75
[44] Waltz D L. Understanding line drawings of scenes with shadows. ThePsychology of Computer Vision. New York, US: McGraw-Hill,1975:19-91
[45] Mackworth A K. Consistency in networks of relations. Artificial Intelligence,1977,8(1):118-126
[46] Mohr R, Henderson T C. Arc and path consistency revisited. ArtificialIntelligence,1986,28(2):225-233
[47] Van Hentenryck P, Deville Y, Teng C M. Generic arc-consistency algorithm andits specializations. Artificial Intelligence,1992,57(2-3):291-321
[48] Bessière C. Arc-consistency and arc-consistency again. Artificial Intelligence,1994,65(1):179-190
[49] Bessière C, Freduer E C, Regn J C. Using inference to reduce arc consistencycomputation. Proceedings of the14th International Joint Conference on ArtificialIntelligence,1995:592-598
[50] Bessière C, Regin J C. Refining the basic constraint propagateion algorithm.Proceedings of the17th International Joint Conference on Artificial Intelligence,2001:309-315
[51] Mackworth A K. Consistency in networks of relations. Artificial Intelligence,1977,8(1):99-118
[52] Gottlob G, Leone N, Scarcello F. A comparison of structural CSP decompositionmethods. Artificial Intelligence,2000,124(2):243–282
[53] Blum C, Roli A. Metaheuristics in combinatorial optimization: overview andconceptual comparison. ACM Computing Surveys,2003,35(3):268-308
[54] Bistarelli S, Montanari U, Rossi F. Semiring-based constraint satisfaction andoptimization. Journal of ACM,1997,44(2):201-236
[55] Schiex T, Fargier H, Verfaillie G. Valued constraint satisfaction problems: hardand easy problems. Proceedings of the14th International Joint Conference inArtificial Intelligence,1995:631-637
[56] Meseguer P, Bouhmala N, Bouzoubaa T, et al. Current approach for solving over-constrained problems. Constraints,2003,8(1):9-39
[57] Dubois D, Fargier H, Prade H. Possibility theory in constraint satisfactionproblems: handling priority, preference and uncertainty. Applied Intelligence,1996,6(4):287-309
[58] Freuder E, Wallace R. Partial constraint satisfaction. Artificial Intelligence,1992,58(1-3):21-71
[59] Larrosa J, Schiex T.. Solving weighted CSP by maintaining arc-consistency.Artificial Intelligence,2004,159(1-2):1-26
[60] Fragier H, Lang J. Uncertainty in constraint satisfaction problems: a probabilisticapproach. Proceedings of the2nd European Conference on Symbolic andQuantitative Approaches to Reasoning and Uncertainty,1993:97-104
[61] Bistarelli S, Montanari U, Rossi, F. Constraint solving over semirings.Proceedings of the14th International Joint Conference in Artificial Intelligence,1995:624-630
[62] Cooper M, Schiex T. Arc consistency for soft constraints. Artificial ntelligence,2004,154(1-2):199-227
[63] Larrosa J, Meseguer P, Schiex T. Maintaining reversible DAC for Max-CSP.Artificial Intelligence,1999,107(1):149-163
[64] Larrosa J, Schiex T. In the quest of the best form of local consistency forweighted CSP. Proceedings of the18th International Joint Conference onArtificial Intelligence,2003:239-244
[65] De Givry S, Heras F. Existential arc consistency: getting closer to full arcconsistency in weighted CSP. Proceedings of the19th International JointConference on Artificial Intelligence,2005:84-89
[66] Cooper M C, De Givry S, Sanchez M, et al. Virtual arc consistency for weightedCSP. Proceedings of the23rd National Conference on Artificial Intelligence,2008,1:253-258
[67] Cooper M C, De Givry S, Sanchez M, et al. Soft arc consistency revisited.Artificial Intelligence,2010,174(7-8):449-478
[68] Terrioux C, Jegou P. Hybrid backtracking bounded by tree-decomposition ofconstraint network. Artificial Intelligence,2003,146(1):43-75
[69] De Givry S, Schiex T, Verfaillie G. Exploiting tree decomposition and soft localconsistency in weighted CSP. Proceedings of the21st National Conference onArtificial Intelligence,2006,1:22-27
[70] Verfaillie G, Lemaitre M, Schiex T. Russian doll search for solving constraintoptimization problems. Proceedings of the13th National Conference onArtificial Intelligence,1996,1:181-187
[71] Sanchez M, Allouche D, De Givry S, et al. Russian doll search with treedecomposition. Proceedings of the21st International Joint Conference onArtificial Intelligence,2009:603-608
[72] Kash K, Dechter R. Branch and bound with mini-bucket heuristics. Proceedingsof the16th International Joint Conference on Artificial Intelligence,1999:426-433
[73] Dechter R, Rish I. Mini-buckets: A general scheme for bounded inference.Journal of ACM,2003,50(2):107-153
[74] Wallace R. Enhancements of branch and bound methods for maximal constraintsatisfaction problem. Proceedings of the13th National Conference on ArtificialIntelligence,1996,1:188-195
[75] Nonobe K, Ibaraki T. An improved tabu search method for the weightedconstraint satisfaction problem. INFOR,2001,39(2):131-151
[76] Gallardo J E, Cotta C, Fernández A J. Solving weighted constraint satisfactionproblems with memetic/exact hybrid algorithms. Journal of ArtificialIntelligence Research,2009,35(1):533-555
[77] Dechter R, Mateescu R. AND/OR search space for graphical models. ArtificialIntelligence,2007,171(2-3):73-106
[78] Mateescu R, Dechter R. AND/OR multi-valued decision diagrams (AOMDDs)for weighted graphical models. Journal of Artificial Intelligence Research,2008,33(1):465-519
[79] Marinescu R, Dechter R. AND/OR branch-and-bound search for combinatorialoptimization in graphical models. Artificial Intelligence,2009,173(16-17):1457-1491
[80] Wilson N. Decision diagrams for the computation of semiring valuations.Proceedings of the19th International Joint Conference on Artificial Intelligence,2005:331-336
[81] Sachenbacher M, Williams B C. Bounded search and symbolic inference forconstraint optimization. Proceedings of the19th International Joint Conferenceon Artificial Intelligence,2005:266-291
[82] Boutaleb K, Jégou P.(No)good recording and ROBDDs for solving structured(V)CSPs. Proceedings of the18th IEEE International Conference on Tools withArtificial Intelligence,2006:297-304
[83] Homem de Mello L. S., Sanderson A. C. Representations of mechanicalassembly sequences. IEEE Transactions on Robotics and Automation,1991,7(2):211-227
[84] Wilson R H. Minimizing user queries in interactive assembly planning. IEEETransactions on Robotics and Automation,1995,11(2):308-311
[85] Gottipolu R. B., Ghosh K., An integrated approach to the generation of assemblysequences. International Journal of Computer Application in Technology,1995,8(3-4):125-138
[86] Gottipolu R. B., Ghosh K., A simplified and efficient representation forevaluation and selection of assembly sequences. Computer in Industry,2003,50(3):251-264
[87] Bourjault A, Lambert J L. Design of an automated hard disk unit assemblysystem. Proceedings of the18th International Symposium on Industrial Roboots,1988:19-28
[88] Wilson R H, Latombe J C. Geometric reasoning about mechanical assembly.Artificial Intelligence,1994,71(2):371-396
[89]张建标,唐荣锡,魏生民等.装配顺序的生成算法研究.机械工程学报,1999,35(5):58-61
[90] Wesley M A, Lozano Perez T, Lieberman L I, et al. Geometric modeling systemfor automated mechanical assembly. IBM Journal of Research Development,1980,24(1):64-74
[91] Lee K, Gossard D C. A hierarchical data structure for representing assemblies:Part1. Computer-aided Design,1985,17(1):15-19
[92] Ishii K. Life-cycle engineering design. Journal of Mechanical Design,Transactions of the ASME,1995,117B:42-47
[93]冯毅雄,谭建荣,郑兵等.基于语义关联与驱动的产品概念装配模型研究.机械工程学报,2004,40(4):114-118
[94]纪杨建,谭建荣,伊国栋等.基于语义元的设计方案形式化与重用方法研究.机械工程学报,2004,40(2):30-36
[95] Dini G, Santochi M. Automated sequencing and subassembly detection inassembly planning. CIRP Annals–Manufacturing Technology,1992,41(1):1-4
[96]李海龙,董金祥,葛建新等，基于约束的装配体技术,计算机辅助设计与图形学报,1997,9(3):249-255
[97] Anahtha R, Kramer G. Assembly modeling by geometric constraint satisfaction.Computer-aided Design,1996,28(9):707-722
[98] Zha X F, Samuel Y E, Fok S C. Integrated knowledge-based assembly assemblysequence planning. International Journal of Advanced ManufacturingTechnology,1998,14:50-64
[99] Oliver J H, Huang H T. Automated path planning for integrated assembly design.Computer-Aided Design,1994,26(9):658-666.
[100] Ghen L L, Woo T C. Computational geometry on the sphere with application toautomated machining. American Society of Mechanical Engineering, DesignEngineering Division (Publication) DE,1990,23(pt1):165-174
[101] Laperriere L, Elmaraghy H A. GAPP: A generative assembly process planner.Jouranl of Manufactureing Systems,1996,15(4):282-293
[102] Huang Y F, Lee C S G. Precedence knowledge in feature mating operationassembly planning. IEEE International Conference on Robotics and Automation,1989,5:216-221
[103] Swaminathan A, Suzanne Barber K. An Experience-based assembly sequencesplaner for mechanical assembly. IEEE Transactions on Robotics and Automation,1996,12(2):252-267
[104]苏强，林志航，马万太等.基于事例推理的装配顺序规划研究.中国机械工程,1999,10(2):171-174
[105] Ko H, Lee K. Automatic assembling procedure generation from matingconditions. Computer-Aided Design,1987,119(1):3-10
[106] Qian W, Yan Y, Zhao X, et al. List representation of assembly sequences.Proceedings of The IEEE International Conference on Industrial Technology,1996,315-319
[107] Landam J, Dialami F. The Assembly State Vector: a new approach to thegeneration of assembly sequences. Proceedings of the4th IEEE InternationalSymposium on Assembly and Task Planning,2001:37-42
[108] Prenting T, Battaglin R. The precedence diagram: A tool for analysis in assemblyline balancing. Journal of Industrial Engineering,1964,15(4):208-213
[109] Warrats J J, Bonschancher N, Bronsvoort W F. A semiautomatic sequenceplanner. Proceeding of IEEE International Conference on Robotics andAutomation,1992:2431-2438
[110] Homem de Mello L S, Sanderson A C. AND/OR graph representation ofassembly plans. IEEE Transactions on Robotics and Automation,1990,6(2):188-199
[111] Lee C Y. Representation of switching circuits by binary decision programs. BellSystem Technical Journal,1959,38(4):985-999
[112] Akers S B. Binary decision diagrams. IEEE Transactions on Computers,1978,27(6):509-516
[113] Clarke E M, McMillan K L, Zhao X, et al. Multi-terminal binary decisiondiagrams: an efficient data structure for matrix representation. Proceedings ofInternational Workshop on Logic Synthesis,1993:1-15
[114] Lai Y T, Vrudhula S B K, Pedram M. EVBDD-based algorithms for linearinteger programming, spectral transformation and function decomposition. IEEETransactions on Computer Aided Design,1994,13(8):959-975
[115] Bryant R E, Chen Y A. Verification of arithmetic circuits using binary momentdiagrams. International Journal on Software Tools for Technology Transfer,2001,3(2):137-155
[116] Somenzi F. CUDD: CU decision diagram package release2.3.1.http://vlsi.Colorado.edu/fabio/CUDD/cuddIntro.html
[117] Minato S. Zero-suppressed BDDs and their applications. International Journal onSoftware Tools for Technology Transfer,2001,3(2):156-170
[118] Dechter R. Bucket elimination: A unifying framework for reasoning. ArtificialIntelligence,1999,113(1-2):41-85
[119] Pan G Q, Vardi M Y. Symbolic techniques in satisfiability solving. Journal ofAutomated Reasoning,2005,35(1-3):25-50
[120] Walsh T. SAT v CSP. Proceedings of the6th international Conference onPrinciples and Practice of Constraint Programming,2000,1894:441-456
[121]贺仁杰,谭跃进.加权约束满足问题的改进深度优先搜索算法.系统工程学报,2004,19(5):512-516
[122] Chatalic P, Simon L. Multi-resolution on compressed sets of clauses.Proceedings of the12th International Conference on Tools with ArtificialIntelligence,2000:2-10
[123]徐周波,古天龙,赵岭忠.网络最大流问题的一种新的符号ADD求解算法.通信学报,2005,26(2):1-8
[124] Larrosa J, Meseguer P. Exploiting the use of DAC in Max-CSP. Proceedings ofthe2nd International Conference on Principle and Practice of ConstraintProgramming,1996:308-322
[125] Wallace R. Directed arc consistency preprocessing. Proceedings of EuropeanConference on Artificial Intelligence Workshop on Constraint Processing,1995:121-137
[126] Sharafat A R, Ma’rouzi O R. A novel and efficient algorithm for scanning allminimal cutsets of a graph. ArXiv preprint math, CO/0211436,2002
[127] Gu T, Liu H. The symbolic OBDD scheme for generating mechanical assemblysequences. Formal Methods in System Design,2008,33(1-3):29-44
[128]钟艳如,黄美发,古天龙.装配序列生成的有序二叉决策图技术研究.计算机集成制造系统,2008,14(10):1996-2004
[129] Tsukiyama S, Shirakawa I, Ozaki H, et al. An algorithm to enumerate all cutsetsof a graph in linear time per cutest. Journal of the ACM,1980,27(4):619-632
[130] Minato S, Ishiua N, Yajima S. Shared binary decision diagram with attributededges for efficient Boolean function manipulation. Proceedings of the27th ACM/IEEE Design Automation Conference,1990:52-57
[131] Purvis L S. Intelligent design problem solving using case based and constraintbased techniques. Connecticut: University of Connecticut,1995