A Constraint Satisfaction Problem Model and Its Symbolic OBDD Solving for Assembly Sequence Planning Problem

The correctness and completeness of assembly sequences are imperative in assembly sequence planning.In the paper,a novel scheme to integrate constraint satisfaction problem(CSP) model with the symbolic ordered binary decision diagram(OBDD) is presented for the monotonic and non-linear assembly sequence planning.In order to formulate the assembly sequence planning problem,the shared binary decision diagram(SBDD) is proposed to represent the assembly liaison graph,and the translational function is represented as ordered binary decision diagrams.Assembly sequence planning problem is formulated as a constraint satisfaction problem(CSP),and the feasible assembly sequences are generated by solving the corresponding CSP model.Moreover,the symbolic OBDD based backtracking technique is given to generate all geometrically feasible assembly sequences.Experiments are also conducted to verify that the symbolic OBDD based CSP scheme can handle the assembly sequence planning properly and efficiently.