ASAPs: asynchronous hybrid self-reconfiguration algorithm for porous modular robotic structures

Programmable matter refers to material that can be programmed to alter its physical properties, including its shape. Such matter can be built as a lattice of attached robotic modules, each seen as an autonomous agent with communication and motion capabilities. Self-reconfiguration consists in changing the initial arrangement of modules to form a desired goal shape, and is known to be a complex problem due to its algorithmic complexity and motion constraints. In this paper, we propose to use a max-flow algorithm as a centralized global planner to determine the concurrent paths to be traversed by modules through a porous structure composed of 3D Catoms meta-modules with the aim of increasing the parallelism of motions, and hence decreasing the self-reconfiguration time. We implement a traffic light system as a distributed asynchronous local planning algorithm to control the motions to avoid collisions. We evaluated our algorithm using VisibleSim simulator on different self-reconfiguration scenarios and compared the performance with an existing fully distributed synchronous self-reconfiguration algorithm for similar structures. The results show that the new method provides a significant gain in self-reconfiguration time and energy efficiency.