ASAPs: Asynchronous Hybrid Self-Reconfiguration Algorithm for Porous Modular Robotic Structures

Abstract 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 performance.