Fault Detection and Identification by Autonomous Mobile Robots

A swarm of robots is modeled as a set of autonomous mobile robots $ℛ=\{r_0,\mathrm{\dots },r_{n-1}\}$ acting in the Euclidean plane ${ℝ}^2$. Robots are indistinguishable (they cannot be distinguished by external appearance), anonymous (they are not provided with any id), homogeneous (they execute the same algorithm), and punctiform entities. Each robot has a local coordinate system and a sensor through which it perceives all the robots in the plane. Each robot $r$ has a light ${\mathrm{𝚕𝚒𝚐}}_r$ whose color is chosen from a constant-size palette $𝔏$. We assume that $𝔏$ contains at least the blank color $\text{/}b$, the default one. All the robots in the swarm are provided with the same deterministic algorithm, which is executed every time a robot is activated. The algorithm also defines the colors in $𝔏$ and a total order of $𝔏$; such colors are used to update the light of each robot. By default, a robot is idle. When activated by the activation scheduler, a robot $r$ executes a Look-Compute-Move cycle: it takes the snapshot of the whole swarm (Look), it executes the algorithm using the sole snapshot as input (Compute), and it can update the color of ${\mathrm{𝚕𝚒𝚐}}_r$ and subsequently it travels along a straight trajectory towards the computed destination (Move). After that, it returns idle, so that it can be activated by the scheduler again. The snapshot of $r$ contains the positions (according to the local coordinate system of $r$) and colors of all the robots of the swarm: no other information about the swarm can be perceived (e.g., whether robots are idle/active, still/moving). We assume rigid movements, i.e., each robot reaches its computed destination during its Move step. The local coordinate systems of the robots in the swarm may not be the same (disoriented robots); moreover, the local coordinate system of any robot may not persist from one activation to another (variable disorientation). Robots are allowed to form multiplicities, i.e., to occupy the same point of the plane at the same time. However, we assume strong multiplicity detection, so that each robot can see all the robots (and their colors) which form a multiplicity.

We now present the features under study: memory, communication, and synchronization. Regarding robots’ memory and communication capabilities, we consider the four models mainly proposed in the literature. Formally, such differences are implemented in the visibility of the robot lights which can be used as a persistent memory and/or a communication means. In the $𝒪ℬℒ𝒪𝒯$ model (w/o memory, w/o communication), the robots’ lights are visible to no robot in the swarm (equivalently, $𝔏=\{\text{/}b\}$ for any algorithm). In the $ℱ𝒮𝒯𝒜$ model (with memory, w/o communication), ${\mathrm{𝚕𝚒𝚐}}_r$ is visible only to $r$, for each $r\in ℛ$. In the $ℱ𝒞𝒪ℳ$ model (w/o memory, with communication), ${\mathrm{𝚕𝚒𝚐}}_r$ is visible to all robots but $r$. In the $ℒ𝒰ℳℐ$ model (with memory, with communication), each ${\mathrm{𝚕𝚒𝚐}}_r$ is visible to each robot in $ℛ$. Regarding the synchronization of robots, we consider only synchronous modes, so that time is divided into atomic rounds; a subset of robots is activated at each round, and they perform their LCM cycle in perfect synchrony. In particular, in the semi-synchronous mode (SSYNCH) an arbitrary non-empty subset of robots is activated at each round. We always assume the fairness condition: for each time $t$ and for each robot $r$, there exists a finite time $t^{\prime }>t$ when $r$ is activated. The fairness condition allows us to measure time as a sequence of consecutive and finite epochs: an epoch is the minimal time frame within which all robots are activated at least once. We consider two sub-modes of SSYNCH. In the fully synchronous mode (FSYNCH), the whole swarm is activated at each round. In the round-robin mode (RROBIN), all robots are activated in sequence, one robot in each round, before being reactivated in the same order. An epoch always lasts one round for FSYNCH and $n$ rounds for RROBIN. The choice of the subset of robots activated at every time is made by an activation scheduler.

We use the notation $X^Y$ to indicate a model for robots that possess all the above core features and that has $X\in \{𝒪ℬℒ𝒪𝒯,ℱ𝒮𝒯𝒜,ℱ𝒞𝒪ℳ,ℒ𝒰ℳℐ\}$ as communication-memory setting and $Y\in \{𝚂,𝙵,\mathrm{𝚁𝚁}\}$ as synchronization mode (i.e., SSYNCH, FSYNCH, RROBIN, resp.). We indicate with $ℳ$ the set of the resulting 12 robot models. For a model $X^Y\in ℳ$, we will consider both the fault-free version (i.e., where all robots are assumed to be always correct) and the fault-prone version (i.e., where robots may suffer from crash faults).

Given a global coordinate system $\widehat{\mathrm{\Xi }}$ on ${ℝ}^2$ (unknown by the swarm), we define the global state of a robot $r_i$ at time $t\in \mathbb{N}$ as the pair ${\widehat{\zeta }}_i=({\underset{¯}{\overset{^}{x}}}_i,{\widehat{c}}_i)$ where ${\underset{¯}{\overset{^}{x}}}_i\in {ℝ}^2$ is the position of $r_i$ according to $\widehat{\mathrm{\Xi }}$, and ${\widehat{c}}_i\in 𝔏$ is the light color of $r_i$, at time $t$. If $r_i$ performs an LCM cycle at time $t$ and $r_i$ changes its global state in $({\underset{¯}{\overset{^}{x}}}_i^{\prime },{\widehat{c}}_i^{\prime })$ in the related Move step, we assume that such change becomes effective at time $t+1$. If a group of $\mathrm{\#}>0$ robots have the same state $\widehat{\zeta }$ at time $t$, we say they form a (global) color-multiplicity, denoted as $\{\widehat{\zeta }\}\mathrm{\#}$. A configuration of the swarm at time $t$ is the set $C=\{\{{\widehat{\zeta }}_0\}{\mathrm{\#}}_0,\mathrm{\dots },\{{\widehat{\zeta }}_k\}{\mathrm{\#}}_k\}$ defining all the distinct color-multiplicities that exist at time $t$ (thus, ${\sum }_{j=0}^k{\mathrm{\#}}_j=n$).

From a robot’s point of view, the configuration of the swarm can be perceived differently: as a matter of fact, each robot $r$ has its own local (and not persistent) coordinate system, and the color of the robots’ lights may be not visible to $r$. By convention, we always assume that when a light is not visible to a robot $r$, then $r$ sees such light as $\text{/}b$-colored⁴⁴4Note that $r$ may not see even its own light.. Let $\mathrm{\Xi }$ be the local coordinate system of $r$ at time $t$. A local color-multiplicity $\{\zeta \}\mathrm{\#}$ is a set of $\mathrm{\#}>0$ robots with the same local state $\zeta =(\underset{¯}{x},c)$, where $\underset{¯}{x}$ is their position according to $\mathrm{\Xi }$, while $c$ is their light color seen by $r$. A snapshot can be described as a “local configuration” from the point of view of $r$. Thus, the snapshot of $r$ at time $t$ is the tuple $⟨\{{\zeta }_0\}{\mathrm{\#}}_0,\mathrm{\dots },\{{\zeta }_h\}{\mathrm{\#}}_h⟩$ containing all the distinct local color-multiplicities seen by $r$. We always assume that the first color-multiplicity $\{{\zeta }_0\}{\mathrm{\#}}_0$ of a snapshot represents the local color-multiplicity containing the robot $r$ itself. Note that a snapshot is represented and managed as an ordered data structure: such an order allows an activated robot to distinguish its state ${\zeta }_0$ from the others ${\zeta }_{i>0}$ (which are ordered according to the local coordinate system of $r$ and the total order of the colors in $𝔏$).

To solve FD/FI, ${ℱ}_M$ may adopt an ad hoc palette of colors ${𝔏}_{ℱ}$ during the evolution of $\mathrm{\Psi }(𝔸,{ℱ}_M)$. For the sake of clarity and w.l.o.g., we can assume that, under the fault-prone model $M$, each robot $r$ is embedded with two lights, the primary light ${\mathrm{𝚕𝚒𝚐}}_r$ which assumes the colors in $𝔏$ provided by the primary algorithm $𝔸$, and the service light ${\mathrm{𝚜𝚎𝚛}}_r$ which assumes the colors in ${𝔏}_{ℱ}$ provided by ${ℱ}_M$. So, the global state of a robot $r$ is the triple $\widehat{\zeta }=(\underset{¯}{\overset{^}{x}},\widehat{c},\widehat{f})$ where $\underset{¯}{\overset{^}{x}}$ is its position, $\widehat{c}\in 𝔏$ is the color of ${\mathrm{𝚕𝚒𝚐}}_r$ and $\widehat{f}\in {𝔏}_{ℱ}$ is the color of ${\mathrm{𝚜𝚎𝚛}}_r$. For the sake of uniformity, we assume ${𝔏}_{ℱ}=\{\text{/}b\}$ under $𝒪ℬℒ𝒪𝒯$; moreover, when the light of $r$ is not visible to a robot, then this robot will see ${\mathrm{𝚜𝚎𝚛}}_r$ (as well as ${\mathrm{𝚕𝚒𝚐}}_r$) as $\text{/}b$-colored. Thus, a combined algorithm $\mathrm{\Psi }(𝔸,{ℱ}_M)$ takes in input an augmented snapshot $\sigma =⟨\{{\zeta }_0\}{\mathrm{\#}}_0,\mathrm{\dots },\{{\zeta }_h\}{\mathrm{\#}}_h⟩$ with ${\zeta }_i=({\underset{¯}{x}}_i,c_i,f_i)$, and returns a triple $({\underset{¯}{x}}^{\prime },c^{\prime },f^{\prime })$ where ${\underset{¯}{x}}^{\prime }$ is the position to be reached, and $c^{\prime }$ ($f^{\prime }$, resp.) is the possible color of the primary (service, resp.) light to be set during the related Move step⁵⁵5Remind that hatted and unhatted notations are used to distinguish the global states of robots from the local views of them.. Remind that a robot may not update the color of its lights; in that case, the value $c^{\prime }$ ($f^{\prime }$, resp.) returned by the algorithm will be denoted with the symbol $-$.

Let us present our combined algorithm $\mathrm{\Psi }$, which uses $𝔸$ and ${ℱ}_M$ as black-box procedures for its implementation. The pseudo-code of $\mathrm{\Psi }$ is listed in Algorithm 1. We here assume that ${ℱ}_M$ is a FI procedure (if it were a FD procedure, the implementation would be similar). Let $r$ be an activated robot in a swarm $ℛ$ of $n$ robots that executes the algorithm $\mathrm{\Psi }$ using the just taken snapshot $\sigma$ as input. At first, $\mathrm{\Psi }$ runs the FI procedure ${ℱ}_M(\sigma )$, which outputs the vector $\underset{¯}{z}\in {\{\mathrm{𝖢𝖮𝖱𝖱𝖤𝖢𝖳},\mathrm{𝖥𝖠𝖴𝖫𝖳}\}}^n$, and the new color $f^{\prime }\in {𝔏}_{ℱ}$ to be set for the service light of $r$. Then $\mathrm{\Psi }$ implements two different actions according to the value of $\underset{¯}{z}$:

• $\mathrm{■}$

  (correctess): If the vector $\underset{¯}{z}$ contains only $\mathrm{𝖢𝖮𝖱𝖱𝖤𝖢𝖳}$ values, $\mathrm{\Psi }$ computes the restricted snapshot ${\sigma }_{𝔸}$ that is obtained by $\sigma$ by removing the service color $f_i$ from any state ${\zeta }_i$. Then, $\mathrm{\Psi }$ runs the primary algorithm $𝔸({\sigma }_{𝔸})$ and obtains the pair $({\underset{¯}{x}}^{\prime },c^{\prime })$, i.e., the possibly new position and primary color for $r$: this result perfectly simulates the behavior of $𝔸$ in the solution of the primary problem under the fault-free version of $M$.

• $\mathrm{■}$

  (soundness): Otherwise, $r$ is aware that some robots are faulty in the swarm, and it can identify them. In this case, $\mathrm{\Psi }$ returns the triple $({\underset{¯}{x}}_0,-,f^{\prime })$ where ${\underset{¯}{x}}_0$ is the current position $r$ (i.e., $r$ freezes itself).

This algorithm generalizes the case when ${ℱ}_M$ is a FD procedure: in that case, $\underset{¯}{z}$ consists of only one element.

The next theorem allows the use of ${ℱ}_M$ or $\mathrm{\Psi }(𝔸,{ℱ}_M)$ interchangeably in the following sections.

Let $𝔏$ be the palette used by ${𝔸}_{NOP}$ to solve SuperPoint under the fault-free $ℒ𝒰ℳ{ℐ}^{𝙵}$ model⁸⁸8Although the most efficient NOP algorithm can solve the problem with $𝔏=\{\text{/}b\}$, we here assume nothing else about ${𝔸}_{NOP}$ other than that it effectively solves SuperPoint.. Suppose ${𝔏}_{ℱ}$ is the palette used by $ℱ$. By hypothesis, the snapshot of a robot $r$ has this form: $\sigma =⟨\{(𝐎,b_0)\}{\mathrm{\#}}_0,\mathrm{\dots },\{(𝐎,b_h)\}{\mathrm{\#}}_h⟩$ where $𝐎=(0,0)$ is the position of any robot according to $\widehat{\mathrm{\Xi }}$, and where $b_i=(c_i,f_i)\in 𝔏\times {𝔏}_{ℱ}$ represents the pair of colors for the primary light and the service light of the robots. Note that $b_0$ represents the colors of the robot $r$ itself. The lemma can be easily proved by induction: in fact, at time $t=0$, all the robots have the same color $b_i=(\text{/}b,\text{/}b)$ (by convention, we set that $ℭ(-1)=\mathrm{\varnothing }$). Let us now assume the fact true for a time $t$, i.e., all the robots in $ℛ\setminus ℭ(t-1)$ have the same color, say $𝐛$, during the $t$-th round. Since $ℛ\setminus ℭ(t)\subseteq ℛ\setminus ℭ(t-1)$, all the active robots in the $t$-th Look step take the same snapshot $\sigma =⟨\{(𝐎,𝐛)\}{\mathrm{\#}}_0,\mathrm{\dots },\{(𝐎,b_h)\}{\mathrm{\#}}_h⟩$, and accordingly they compute the same next color ${𝐛}^{\prime }$ by executing $\mathrm{\Psi }({𝔸}_{NOP},ℱ)(\sigma )$. Thus, at the beginning of the $(t+1)$-th round, all the robots in $ℛ\setminus ℭ(t)$ have set the same color ${𝐛}^{\prime }$. $◀$ By the contrapositive of Section 3.5, we have:

By contradiction, let us assume that there exists a reliable FI procedure $ℱ$ for $ℒ𝒰ℳ{ℐ}^{𝙵}$ which uses a $k$-size palette ${𝔏}_{ℱ}$. Let us consider the SuperPoint problem under $ℒ𝒰ℳ{ℐ}^{𝙵}$, with $n\ge k+2$ robots, and let ${𝔸}_{NOP}$ be the optimal algorithm solving SuperPoint with $𝔏=\{\text{/}b\}$. By definition, the problem starts from a configuration where all the robots have the same color. Let us assume all the robots always use the coordinate system $\widehat{\mathrm{\Xi }}$. Thus, for the sake of conciseness, we can omit to state the position $(0,0)$ and the primary light color $\text{/}b$ in the snapshots of the robots; instead, we only specify the colors of the service lights. As proved in Section 3.5, at each round $t$, all the active and correct robots take the same snapshot $\sigma =⟨\{f_0\}{\mathrm{\#}}_0,\mathrm{\dots },\{f_h\}{\mathrm{\#}}_h⟩$, execute $ℱ(\sigma )=(\underset{¯}{z},f^{\prime })$ and update their service color from $f_0$ to $f^{\prime }$. Note in fact that $f_0$ corresponds to the current service color of all the robots in $ℛ\setminus ℭ(t-1)$ (and thus in $ℛ\setminus ℭ(t)$).

Let $ℭ$ be a suppression scheduler so that it crashes a number of robots $\in [k,n-2]$ in $k$ different rounds within a finite time $t_k$. Formally, there exists a series of $k$ finite crash times such that $ℭ(t_i)\subset ℭ(t_{i+1})$, and such that $|ℭ(t_k)|\in [k,n-2]$. Let $\widehat{t}$ be the first time when the robots in $ℛ\setminus ℭ(\widehat{t})$ execute $ℱ(\sigma )=(\underset{¯}{z},𝐟)$ and $𝐟$ is a color already present in the current snapshot $\sigma$. In other words, there is at least a faulty $𝐟$-colored robot in the swarm at time $\widehat{t}$. Note that this time exists and it holds $\widehat{t}\le t_k$. In fact, the worst case (i.e., $\widehat{t}=t_k$) is reached when, at each crash time $t_i$, $ℱ$ outputs a new service color not yet present in the swarm: after the $k$-th crash time $t_k$, the swarm contains all the $k$ colors of ${𝔏}_{ℱ}$. So, at time $\widehat{t}$, the correct robots set their color as $𝐟$.

Let $r$ be an active robot at time $\widehat{t}+1$ and let $⟨\{𝐟\}{\mathrm{\#}}_0,\mathrm{\dots },\{f_h\}{\mathrm{\#}}_h⟩$ be the snapshot $r$ takes. Note that, since the correct robots at time $\widehat{t}$ are at least 2 by hypothesis, then ${\mathrm{\#}}_0>2$. By applying $ℱ$, $r$ cannot distinguish which among the ${\mathrm{\#}}_0$ $𝐟$-colored robots are faulty or correct. This contradicts the hypothesis that $ℱ$ is reliable. $◀$

By contradiction, let $ℱ$ be a reliable FD procedure using a palette ${𝔏}_{ℱ}=\{f_0,\mathrm{\dots },f_{k-1}\}$ of $k\ge 1$ colors for an $ℱ𝒮𝒯𝒜$ model. We show that there exists a problem for which $ℱ$ is not reliable. Consider the problem Flip-Flop that can be trivially solved under any fault-free $ℱ𝒮𝒯𝒜$ model without the use of colors: let $𝔸$ be a solving algorithm with $𝔏=\{\text{/}b\}$. It is self-evident that the crash of a robot which is required to be still by the primary problem cannot be detected without assuming communication. In fact, $r$ can never detect whether a robot in $O$ has crashed. However, this impossibility is not limited to the static robots: we prove that $p$ (the same holds for $q$) cannot reliably detect the fault of $r$.

Let us denote the following coordinates: $𝐎=(0,0)$, $\mathrm{𝟏}=(1,0)$, and $-\mathrm{𝟏}=(-1,0)$. Let ${\mathrm{\Xi }}^{+}$ be a coordinate system which makes a robot perceives $O$ in position $𝐎$ and $x$ in position $\mathrm{𝟏}$ (and thus $x^{\prime }$ in position $-\mathrm{𝟏}$), and let ${\mathrm{\Xi }}^{-}$ be a coordinate system under which $O$ is in position $𝐎$ and $x$ in $-\mathrm{𝟏}$ (and thus $x^{\prime }$ in $\mathrm{𝟏}$). Let $𝔄$ be an activation scheduler (any under $\text{SSYNCH},\text{FSYNCH},\text{RROBIN}$) for $p,q,r$. Consider the swarm under the combined scheduler $𝔄\setminus ℭ$ where $ℭ$ is a suppression scheduler that crashes no robot. Suppose $p$ is activated at times $t_0,t_1,t_2,\mathrm{\dots }$, and suppose that its coordinate system is ${\mathrm{\Xi }}^{+}$ when $r$ lies on $x$ and ${\mathrm{\Xi }}^{-}$ when $r$ lies on $x^{\prime }$. In other words, $p$ always perceives $r$ in position $\mathrm{𝟏}$. Since $ℱ$ is reliable and no robot has crashed, $p$ will always obtain $\mathrm{𝖢𝖮𝖱𝖱𝖤𝖢𝖳}$ by executing $ℱ$ at times $t_0,t_1,\mathrm{\dots }$. In particular, let ${\sigma }_0,{\sigma }_1,\mathrm{\dots },{\sigma }_h$ be the set of the snapshots taken with some periodicity by $p$ along its activations $t_0,t_1,\mathrm{\dots }$, where and where ${\sigma }_i$ has this form⁹⁹9For the sake of conciseness, we here omit the notation for multiplicities.: $⟨(𝐎,\text{/}b,f_i),(𝐎,\text{/}b,\text{/}b),(\mathrm{𝟏},\text{/}b,\text{/}b)⟩$.

Now, consider the same swarm under the combined scheduler $𝔄\setminus {ℭ}^{\prime }$ where ${ℭ}^{\prime }$ only crashes $r$ at time $t_0$. W.l.o.g. suppose that $r$ lies on $x$ at $t_0$, and suppose that from $t_0$ onward $p$ will always have ${\mathrm{\Xi }}^{+}$ as coordinate system, thus perceiving $r$ in position $\mathrm{𝟏}$. Thus $p$ will be activated at times $t_0,t_1,t_2,\mathrm{\dots }$ and it will perform $ℱ({\sigma }_0),ℱ({\sigma }_1),\mathrm{\dots }ℱ({\sigma }_h)$ at the same times and periodicity as under $𝔄\setminus ℭ$, thus never detecting the fault of $r$. Contradiction achieved. $◀$