Line formation and scattering in silent programmable matter

Programmable Matter (PM) has been widely investigated in recent years. It refers to some kind of substance with the ability to change its physical properties (e.g., shape or color) in a programmable way. In this paper, we refer to the SILBOT model, where the particles live and move on a triangular grid, are asynchronous in their computations and movements, and do not possess any direct means of communication (silent) or memory of past events (oblivious). Within SILBOT , we aim at studying Spanning problems, i.e., problems where the particles are required to suitably span all over the grid. We first address the Line Formation problem where the particles are required to end up in a configuration where they all lie on a line, i.e., they are aligned and connected. Secondly, we deal with the more general Scattering problem: starting from any initial configuration, we aim at reaching a final one where no particles occupy neighboring nodes. Furthermore, we investigate configurations where some nodes of the grid can be occupied by unmovable elements (i.e., obstacles) from both theoretical and experimental view points. • In this paper we investigate on Spanning Problems within Programmable Matter. • We focused on the Line Formation and the Scattering problem within the SILBOT model. • We prove the Line Formation problem to be unsolvable when particles share chirality. • We prove the Scattering problem to be unsolvable in the asynchronous setting. • We propose distributed algorithms to solve the two problems.