Symmetry Constraint Inference in Assembly Planning

Abstract

In this paper we shall discuss how to treat the automatic generation of assembly task specifications as a constraint satisfaction problem (CSP) over finite and infinite domains. Conceptually it is straightforward to formulate assembly planning in terms of CSP, however the choice of constraint representation and of the order in which the constraints are applied is nontrivial if a computationally tractable system design is to be achieved. This work investigates a subtle interaction between a pair of interleaving constraints, namely the kinematic and the spatial occupancy constraints. While finding one consistent solution to a general CSP is NP-complete, our work shows how to reduce the combinatorics in problems arising in assembly using the symmetries of assembly components. Group theory, being the standard mathematical theory of symmetry, is used extensively in this work since both robots and assembly components are three-dimensional rigid bodies whose features have certain symmetries. This forms part of our high-level robot assembly task planner in which geometric solid modelling, group theory and CSP are combined into one computationally effective framework.