Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure

In the context of large distributed modular robots, self-reconfiguration is the process of having modules, seen as autonomous agents, acting together and moving to transform the morphology of their physical arrangement to produce a desired shape. However, due to motion constraints, the number of modules that can move concurrently is greatly limited, thus making self-reconfiguration a very slow process. In this paper, we propose an approach for accelerating self-reconfiguration to build a porous version of the desired shape, using scaffolding. We expand this idea and propose a method for constructing a parametric scaffolding model that increases the parallelism of the reconfiguration, supports its mechanical stability, and simplifies planning and coordination between agents. Each agent has a set of basic rules using only four states which guarantees that module movements and the construction of the scaffold are deterministic. Coupled with an underneath reserve of modules that allows the introduction of rotating quasi-spherical modules at various ground locations of the growing porous structure, our method is able to build the scaffolding structure in O(N-2/3) time with N the number of modules composing the structure. Furthermore, we provide simulation results showing that our method uses O(N-4/3) messages with no congestion.