Symmetry groups in robotic assembly planning

摘要

In this dissertation group theory, being the standard mathematical tool for describing symmetry, is used to characterize the symmetries of bodies and features, especially the symmetries relevant to contact between bodies. Such a characterization reveals the necessity of intersecting subgroups of the proper Euclidean group ${\\cal E}\\sp{+}$. The central theoretical results of this dissertation are to establish this necessity mathematically and to provide a compact representation for the subgroups of ${\\cal E}\\sp{+}$ that leads an efficient group intersection algorithm. I define a geometric representation in terms of characteristic invariants for an important family of subgroups of ${\\cal E}\\sp{+}$. Each member of this family is called a $TR$ group since it is a semidirect product of a translation group $T$ and a rotation group $R$. I prove that there is a one-to-one correspondence between $TR$ groups and their characteristic invariants. I also prove that the intersection of $TR$ groups is closed and can be efficiently calculated from their characteristic invariants. A practical issue addressed in this dissertation is the linkage between mechanical design and robotic task-level planning. The formal treatment of $TR$ symmetry groups has been embedded into the implementation of an assembly planning system ${\\cal KA}$3, which takes as input the geometric boundary models of assembly components provided by an off-the-shelf geometric solid modeller PADL2, and a set of instructions in the form of 'body A fits body B'. ${\\cal KA}$3 finds a set of detailed robotic assembly task specifications in three steps: Step one: ${\\cal KA}$3 finds mating features from the boundary models of assembly components using a salient feature library and the symmetry group intersection algorithm. Step two: ${\\cal KA}$3 applies techniques used in constraint satisfaction problems (CSP) to satisfy kinematic and spatial constraints for each candidate assembly configuration. Step three: ${\\cal KA}$3 generates a partially ordered sequence of contact states for assembly components through an analysis of disassembly via translational motion. The interaction between algebra and geometry within a group theoretic framework and the interaction between CSP techniques and heuristic search strategies provide us with a unified computational treatment of reasoning about how parts with multiple contacting features fit together.