DISTRIBUTED COMPUTING BY MOBILE ROBOTS: COMPUTATIONAL POWER AND ALGORITHM DESIGN

The Look-Compute-Move (LCM) model is a theoretical framework widely used to formalize and study distributed systems of mobile autonomous robots, namely swarms of robots. Generally, the LCM model assumes robots are anonymous, indistinguishable, homogeneous, and punctiform entities acting on the Euclidean plane through LCM cycles. Other features may limit robots' power: e.g., mostly, literature considers disoriented robots, i.e., devoid of a global coordinate system, and with limited or absent storage and communication means. Each robot is embedded with the same deterministic algorithm, which is executed at any robot activation within an LCM cycle. Thanks to such an algorithm, the swarm solves a problem; typically, research focuses on problems requiring, for instance, the swarm to arrange in specific geometric patterns, or to move to satisfy some conditions. This thesis encompasses two research topics mainly involved in this field. The first part investigates the computational power of different LCM sub-models, which vary in certain robot features (i.e., memory, communication, visibility, and synchronization). Notably, we study whether different sub-models are able to solve the same set of problems or specific problems (e.g., the Fault Detection problem in fault-prone systems). The second part concerns the design and analysis of algorithms for solving specific formation problems under selected sub-models. Specifically, we provide two algorithms for the Uniform Circle Formation problem, which requires a swarm of n robots—that are luminous (i.e., equipped with constant-size memory and communication means), opaque (i.e., subject to obstructed visibility in the case of collinearity), and asynchronous—to form a regular n-gon. In particular, the first algorithm is O(log n)-time, while the second one is time-optimal. Finally, we constructively prove that a swarm of luminous and sequential robots (i.e., activated one at a time) can solve the Universal Dancing problem, which requires the swarm to form sequences of any patterns, starting from any initial configuration.