Introduction
One of the central control problems of modular-robot-based programmable matter 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), or at least finding an assembly plan to effectively assemble that shape without deadlock. 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 intractable. Self-reconfiguration of a both chain-type and lattice-type modular robotic system have been proven to be NP-complete in the recent years.
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 guarantee 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.
Furthermore, as self-reconfiguration processes are usually very slow due to both the amount of modules that need to be displaced, and the time it takes for them to move without colliding with each other, we have researched a number of methods for achieving unprecedented reconfiguration speed, within a dedicated environment, engineered for that purpose. Visit the Massively Parallel Reconfiguration section below to learn more.
