Fault Detection and Identification by Swarms of Autonomous Mobile Robots

• We consider 20 crash-prone robot models under the Look-Compute-Move framework. • We define the Fault Detection (FD) and Fault Identification (FI) problems. • We formalize the concept of crashes in a swarm and their occurrence. • We provide three procedures that solve FD under various models. • We prove the impossibility of a reliable FI even under the most powerful models. 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 .