Self-Assembly Planning

One of the most interesting capability of a system of modular robots is the ability of the modules to move towards a different position, that way changing the global shape or morphology of the whole. This is called self-assembly or even self-reconfiguration when modules are always connected during the process.

In our work, we focus on solving the problem of assembling 3D structures that may contain internal holes. While building the whole structure, modules are docking at available places but some positions may become impossible to reach, blocked by other modules.

As we tackle robots composed of thousands of modules, a centralized algorithm would exceed the available memory on one module whereas a distributed algorithm would scale well.

Importance of sequence planning shown on a Mug model made by 12,000 modules. Red modules represent docking problems using two simple planning algorithms. On the left, choosing a stochastic order produces 3,691 modules that does not verify the docking rule. On the right, filling regularly each module neighborhood in sequence results in 231 positions that could not be filled.

Distributed Self-Assembly Planning

We propose a distributed algorithm for a system of modular robots that is capable of generating an attraction list of its available positions. Our algorithm prevents positions from becoming impossible to reach and is able to create close-packed structures with internal holes that are applicable to a variety of modular robotic systems.

One of the tasks that requires lots of time in a self-assembly system is to find the exact location for the modules to dock. We show with that the algorithm can have many simultaneous docking positions and accelerate the creation of a model with a linear number of messages.