Molecular Oblivious Robots: A New Model for Robots With Assembling Capabilities

Abstract

Research in theoretical swarm robotics focuses on models that assign to robots a minimal set of capabilities. One of the models well investigated is certainly $\mathcal {OBLOT}$ , addressing the case of distributed robots that are, anonymous, without means of communication, and oblivious. Here we propose $\mathcal {MOBLOT}$ , an extension of $\mathcal {OBLOT}$ that allows to resolve a larger spectrum of cases. $\mathcal {MOBLOT}$ stands for molecular oblivious robots: like atoms combine themselves to form molecules, in $\mathcal {MOBLOT}$ simple robots can bond with each other in order to create possibly bigger computational units with more intrinsic capabilities with respect to robots (called molecules also in the model); like in nature, molecules can further bond to create more complex structures (e.g., the matter), the $\mathcal {MOBLOT}$ version of molecules can exploit their own capabilities to accomplish new tasks or simply to arrange themselves to form any shape defined according to some compositional properties. In order to better understand the potentials of $\mathcal {MOBLOT}$ , we introduce a new problem called matter formation (MF). We do provide a necessary condition for the solvability of MF, in general. This relies on the ‘amount of symmetries’ arising by the disposal of the robots. In practice, we show how molecules can break certain symmetries that cannot be broken in $\mathcal {OBLOT}$ . Finally, as a case study of $\mathcal {MOBLOT}$ , we consider a representative problem derived from the general MF problem along with a distributed resolution algorithm and show its correctness.

Keywords

• Distributed algorithms
• swarm and modular robotics
• self-organizing systems
• oblivious robots
• pattern formation