Towards a Common Comparison Framework for Global-to-Local Programming of Self-Assembling Robotic Systems

摘要

Self-assembling robotic systems are a class of modular robots where many identically-programmed modules mix randomly and attach together to assemble into complex shapes. Recently several groups have proposed global-to-local compilers for such systems and for related robotic systems; the compilers take a global shape description and automatically generate appropriate local module attachment rules. A current challenge is understanding how these approaches compare in terms of complexity, parallelism, and expressivity. In this paper we present some initial steps towards a common framework for comparing algorithmic approaches to self-assembly. We specify a generic 2D self-assembly framework and then use this framework to compare self-assembly algorithms based on two distinct global-to-local compilers: the MakeGraphGrammar approach for generating topological graphs and the CollectiveConstruction approach for mobile robots that build structures using communicating blocks. We show that: (1) Both approaches generate module programs with the same high complexity, O(total modules); (2) Both approaches have dramatically different best-case parallelism: while the number of steps required to build a shape with CollectiveAssembly is bounded by the diameter of that shape, MakeGridGrammar has a best case of no more than four parallel steps to complete any shape it can handle; (3) Both approaches can provably generate 2D shapes without defects, but the class of shapes is much larger for CollectiveConstruction and poses less stringent module requirements.