Automatic synthesis of controllers for distributed assembly and formation forming

Abstract

We consider the task of assembling a large number of self controlled parts (or robots) into copies of a prescribed assembly (or formation). In particular, we introduce a way to synthesize, from a specification of the desired assembly, local controllers to be used by each part which, when taken together, have the global effect of assembling the parts. We pay careful attention to the time and space complexity of the synthesis procedure, showing that the size of the representation of the synthesized controller is polynomial in the size of the specification and that the computational power needed by the controller is low.