Scattering with Programmable Matter

We aim at studying the Scattering problem (or Distancing) in the context of Programmable Matter (PM). This is intended as some kind of matter with the ability to change its physical properties (e.g., shape or color) in a programmable way. PM can be implemented by assembling a system of self-organizing computational entities, called particles, that can be programmed via distributed algorithms. A rather weak model proposed in the literature for PM is SILBOT, where particles are all identical, executing the same algorithm based on their local neighborhood. They have no direct means of communication and are disoriented. We aim to achieve Scattering, i.e., all particles are at least two hops far apart from each other. We show that the problem is unsolvable within the pure asynchronous setting whereas we do provide a resolution algorithm for the event-driven case where a particle reacts to the presence of other particles in its neighborhood. Furthermore, we investigate (also by simulations) on configurations where some nodes of the grid can be occupied by obstacles, i.e., immovable but recognizable elements.