Research An Symbolic Algorithms For Constraint Satisfaction Problem And Their Applications In Assembly Planning

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.