We consider the distributed framework of swarms of mobile robots. A swarm is a set of computational, anonymous, indistinguishable, homogeneous, and autonomous entities that operate in the Euclidean plane through infinite sequences of Look-Compute-Move cycles. The goal of a swarm is to collaborate to solve a given problem. The ability to solve a problem depends on the swarm features and its setting X^S, where X ∈ {OBLOT, FSTA, FCOM, LUMI} denotes the memory/communication model and S denotes the class of schedulers (e.g., fully-synchronous, sequential, asynchronous) that activate the robots. Given a pool of settings, prior research has characterized the relations (dominance, equivalence, or orthogonality) among their computational powers, recently extending this analysis to the class of sequential schedulers (i.e., activating only one robot per round), and of the restricted ones (i.e., never activating a robot twice consecutively). In this paper, we extend the study on sequential schedulers (SEQ, PERM, and RROBIN) by defining two classes of sequential restricted schedulers R-SEQ and R-PERM. In particular, we analyze how the computational power of each model OBLOT, LUMI, and FCOM is affected by considering both sequential schedulers and their restricted variants; for FSTA, we only provide the relation between RROBIN and R-PERM. We establish both equivalence and dominance results: some settings are computationally equivalent, while others can be separated by problems solvable in one setting but not in the other.

The Dancing problem requires a swarm of n autonomous mobile robots to form a sequence of patterns, i.e., perform a choreography. Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models. Here, we prove that these necessary constraints can be dropped by considering the $$\mathcal {LUMI}$$ model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler. We formalize the class of Universal Dancing problems which require a swarm of n robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of n vertices (including multiplicities). However, we prove that, to be solvable under $$\mathcal {LUMI}$$ , the length of the feasible choreographies is bounded by the compositions of n into the number of colors available to the robots. We provide an algorithm solving Universal Dancing by exploiting the peculiar capability of sequential robots to implement a distributed counter. Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.

The Look-Compute-Move model (LCM) is adopted to study swarms of mobile robots that have to solve a given problem. Robots are generally assumed to be autonomous, indistinguishable, anonymous, homogeneous, and to move on the Euclidean plane. Different LCM sub-models have been theorized to study different settings and their computational power. Notably, the literature has focused on four base models (i.e., OBLOT , FSTA , FCOM , LUMI ) that differ in memory and communication capabilities, and in different synchronization modes (e.g., fully synchronous FSYNCH , semi-synchronous SSYNCH ). In this paper, we consider fault-prone models where robots can suffer from crash faults : each robot may irremediably stop working after an unpredictable time decided by a crash scheduler. We study the general Fault Detection ( FD ) problem which is solved by a swarm if it correctly detects whether a faulty robot exists in the swarm. The Fault Identification ( FI ) problem additionally requires identifying which robots are faulty. We consider 20 LCM sub-models ( OBLOT , FSTA , FCOM , LUMI , combined with FSYNCH , SSYNCH , and the sequential modes RROBIN , PERM , and SEQ ) and we study the (im)possibility of designing reliable procedures to solve FD or FI . In particular, we propose three distributed algorithms so that a swarm can collectively solve FD under the models LUMI FSYNCH , FCOM FSYNCH , and LUMI PERM . On the contrary, we prove a general impossibility to solve FI ; this leads to the introduction of less adversarial crash schedulers, which allows us to solve FI under LUMI FSYNCH .

We consider distributed systems of autonomous, punctiform, mobile robots that operate in the Euclidean plane by executing an infinite sequence of Look-Compute-Move cycles. Robots are anonymous, indistinguishable, homogeneous, and disoriented. In literature, four base models have been proposed to study four different memory-communication settings: $$\mathcal {OBLOT}$$ (oblivious and silent), $$\mathcal {FSTA}$$ (finite-state and silent), $$\mathcal {FCOM}$$ (oblivious and finite-communication), and $$\mathcal {LUMI}$$ (finite-state and finite-communication). In particular, the research has investigated how the computational power of these models is affected by considering three main classes of robot schedulers: FSYNCH (fully synchronous), SSYNCH (semi-synchronous), and ASYNCH (asynchronous). This paper focuses on a peculiar type of SSYNCH schedulers, the sequential ones, which activate only one robot at each round. We consider three subclasses: the general sequential scheduler (SEQ), the permutation scheduler (PERM), and the well-known round-robin (RROBIN). For each base model, we investigate how the robots’ computational power changes as the scheduler class varies, thus providing a first overview of the computational landscape of sequential schedulers.

The Dancing problem requires a swarm of n autonomous mobile robots to form a sequence of patterns, aka perform a choreography.Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models.Here, we prove that these necessary constraints can be dropped by considering the LUMI model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler.We formalize the class of Universal Dancing problems which require a swarm of n robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of n vertices (including multiplicities).However, we prove that, to be solvable under LUMI, the length of the feasible choreographies is bounded by the compositions of n into the number of colors available to the robots.We provide an algorithm solving the Universal Dancing problem by exploiting the peculiar capability of sequential robots to implement a distributed counter mechanism.Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.

The research on distributed computing by robot swarms has formalized different models where robots act through a sequence of Look-Compute-Move cycles in the Euclidean plane. Models mostly under study differ for (i) the possibility of storing constant-size information, (ii) the possibility of communicating constant-size information, (iii) the synchronization mode, and (iv) the visibility of robots. By varying features (i) and (ii) , we obtain the noted four base models: OBLOT (silent and oblivious robots), FSTA (silent and finite-state robots), FCOM (oblivious and finite-communication robots), and LUMI (finite-state and finite-communication robots). Feature (iii) comprehends the three main synchronization modes: fully synchronous , semi-synchronous , and asynchronous . According to robot visibility (iv) , models can assume robots to be transparent (thus enjoying complete visibility ) or opaque (thus experiencing obstructed visibility in case of collinearities). By combining features (i-iv) , we obtain 24 models. Extensive research has studied the computational power of the 12 transparent models, proving the hierarchical relations among them; to this regard, it is worth noticing that robots have been assumed to be collision-tolerant. In this work, we assume our robots to be collision-intolerant and we lay down the computational hierarchy by considering all 24 models. Firstly, we study the relations between the transparent and the opaque framework, focusing on how obstructed visibility affects the computational power of a model. Then, we introduce five witness problems that prove most of the computational relations among the 24 models. • We consider 24 robot models differing in memory, communication, synchronization, and visibility (transparent vs. opaque). • Some problems are exhibited, which cannot be solved under any opaque model. • Five witness problems are designed, showing the dominance and orthogonality relations among the models. • We introduce the phenomenon of “false election” occurring in case of asynchronism and obstructed visibility. • We provide an almost complete relation table depicting the computational hierarchy of the 24 models under study.