The Self-Reconfiguration Problem

Introduction

One of the central control problems to be solved for achieving programmable matter with modular robotic systems is for the robot to self-reconfigure or self-assemble into a given shape. The former deals with transforming an initial shape into another, while the latter deals with assembling a shape from the ground up (quite literally in some cases). In this variety of metamorphic system -- i.e., a system that is able to change its shape -- the constituting modules have to communicate and self-organize in order to converge from a source arrangement to a desired one. Such an arrangement of individual modules is hereinafter referred to as a configuration. 

Self-reconfiguration is a hard problem. The size of the configuration space, defined as the search space represented by all configurations and the individual module motion representing the difference between them, is exponential in the number of modules in the configuration. Traditional search methods are therefore not tractable. Self-reconfiguration of a chain-type modular robotic system has been proven to be NP-complete, and is also suspected to be so in its lattice-type counterpart.

Within the context of our programmable matter project, we are focusing our efforts on designing realistic self-reconfiguration methods and algorithms that can scale up to millions of modules and that operate in a fully-distributed fashion, where each module is not only identical to the others but also executes the exact same code. The main properties of self-reconfiguration algorithms that are desirable in our approach are: scalability, kinematic and communication efficiency, robustness, and the guaranty to converge into the desired shape.

Several sub-problems nonetheless arise when attempting to design self-reconfiguration algorithms. For instance, we have investigated ways to devise a construction order for a goal shape that would guarantee that it can be constructed without deadlocks, and to efficiently compress the description of the target shape in order to reduce the memory impact on modules. These methods are covered in the sections below.