Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings

In the field of distributed computing, theoretical researches on autonomous mobile robots have attracted a lot of attention. The goal of the researches is to clarify the minimum capabilities of robots to achieve a given task. For this reason, many researches consider robots with very weak capabilities, that is, they are identical (i.e., robots execute the same algorithm), oblivious (i.e., robots have no memory to record past history), and silent (i.e., robots do not send messages explicitly). As a model of weak robots, the Look-Compute-Move (LCM) model [23] is commonly used. In the LCM model, each robot repeats a cycle of Look, Compute, and Move phases: the robot takes a snapshot in the Look phase, computes its behavior based on the snapshot in the Compute phase, and moves to a new position (if necessary) in the Move phase. By using the LCM model, solvability is clarified on various environments, various capabilities of robots, and various tasks. For example, some works focus on continuous environments (aka two- or three-dimensional Euclidean space)  [13, 23, 24] or discrete environments (aka graph networks)  [7, 11, 16]. Most traditional works assume oblivious robots with unlimited visibility, but recently some works consider light devices [9, 14] or limited visibility [13, 17]. As benchmark tasks, gathering [7, 23], exploration [8, 19], and pattern formation [15, 24] are mainly studied. State-of-the-art surveys are given in [12].

In this paper, we focus on myopic luminous robots in discrete environments. Recently many papers focus on myopic luminous robots because of the reasonable assumptions on the observation, communication, and memory capability [2, 3, 6, 8, 18, 19]. Myopic robots mean that they can observe nodes only within a certain fixed distance. This implies that myopic robots are less powerful than traditional robots with unlimited visibility. Luminous robots mean that they have light devices that can emit a color from a set of colors. The light color is visible to other robots and not reset at the end of each cycle, and hence the light device models a communication and memory device. This assumption is reasonable because real weak robots (such as Kilobots [22]) also have weak communication devices and small memories.

Since robots are weak, it is likely that robots crash during the execution, in particular when they work in dangerous environments. Once robots have crashed, they continue to reside in the system without moving or changing their colors, however they cannot be distinguished from correct robots with the same color. For robots with unlimited visibility in Euclidean plane, some works study crash-tolerant algorithms, for example, for gathering [1, 10], flocking [25], and complete visibility [20]. For robots with unlimited visibility in graph environments, some works study crash-tolerant algorithms for gathering [4, 5, 21]. On the other hand, for myopic luminous robots in graph environments, to the best of our knowledge, only one work [3] considers crash-tolerant algorithms. This work considers crash-tolerant gathering algorithms on line networks. Hence it is not clear what tasks can be achieved by myopic luminous robots when some robots may crash.

We focus on crash-tolerant perpetual exploration. The goal of perpetual exploration is to ensure that robots, starting from specific initial positions and colors, move in such a way that every node is visited by at least one robot infinitely often. The perpetual exploration is a benchmark task of mobile robots, and it is useful for patrolling, cleaning, disinfecting, searching, and so on. Thus, the perpetual exploration has been studied extensively. When no crash occurs, on ring networks the case of visibility one is studied in [19] and the case of visibility more than one is studied in [18]. On grid networks, many algorithms for various assumptions are proposed in [2, 6].

We investigate crash-tolerant perpetual exploration with myopic luminous robots on ring networks. We assume that each robot observes robots on nodes within distance $\varphi$ and has a light device with $l$ colors. In this paper, we clarify the minimum number of robots to achieve perpetual exploration when at most $f$ robots crash. Table 1 summarizes our contributions.

First, we consider the fully synchronous (FSYNC) model. In previous works [18, 19], it is proven that, when robots do not crash, two robots are necessary for any $\varphi$ and $l$, and two robots are sufficient for $\varphi =1$ and $l=2$. From this fact, when at most $f$ robots crash, we can easily obtain that $f+2$ robots are necessary for any $\varphi$ and $l$, and that $2f+2$ robots are sufficient for $\varphi =1$ and $l=2f+2$. For the sufficiency, let us construct $f+1$ groups such that each group contains two robots, and make each group execute crash-free perpetual exploration independently by assigning different colors to groups (i.e., $l=2f+2$). This algorithm achieves perpetual exploration because at least one group can continue the algorithm. On the other hand, $f+2$ robots are necessary for any $l$ because at least two robots must remain after $f$ robots crash. As the first main contribution, we close the gap between the necessary number and the sufficient number by proposing a crash-tolerant algorithm with $f+2$ robots. The algorithm uses $l=3f+2$ colors, that is, it uses asymptotically the same number of colors as the trivial algorithm mentioned above.

Next, we consider the semi-synchronous (SSYNC) and asynchronous (ASYNC) models. In previous works [18, 19], it is proven that, when robots do not crash, if $\varphi =1$ (resp., $\varphi \ge 2$), three (resp., two) robots are necessary for any $l$, and three (resp., two) robots are sufficient for $l=2$. Similarly to the FSYNC model, when at most $f$ robots crash, we can obtain that, if $\varphi =1$ (resp., $\varphi \ge 2$), $3f+3$ (resp., $2f+2$) robots are sufficient for $l=2f+2$. As the second main contribution of this paper, we prove that, different from the FSYNC model, these sufficient numbers are also necessary numbers for any $l$. That is, the trivial algorithms are optimal in terms of the number of robots even if we can use any number of colors. To prove this, we show that, if $x$ robots are necessary when no robot crashes, $(f+1)x$ robots are necessary when at most $f$ robots crash. Intuitively, this is because robots cannot distinguish crashed robots and slow robots. When some robot $r$ seems crashed, other robots must leave $r$ and continue exploration. However, if robots leave $r$ alone and $r$ is just slow, this means that robots abandon one correct robot. To avoid this situation, robots leave a group of $x$ robots so that the group does not get stuck. This implies that, if $f$ robots crash dispersedly, $f+1$ groups of $x$ robots can be created. For this reason $(f+1)x$ robots are necessary.

The system consists of robots and an environment which is modeled by an $n$-node undirected ring $G=(V,E)$, where $V=\{v_0,\mathrm{\dots },v_{n-1}\}$ and $E=\{(v_i,v_{i+1modn})\mid 0\le i\le n-1\}$. For simplicity we consider mathematical operations on node indices as operations modulo $n$. We say $v_i$ and $v_{i+1}$ are neighbors. We use $v_0,\mathrm{\dots },v_{n-1}$ for notation purposes only and no robot has access to indices of nodes. The ring is unoriented, that is, robots cannot recognize the direction of the ring. Robots do not know $n$, the size of the ring. When a robot $r$ is on a node $v$, we say $r$ occupies $v$. The distance between two nodes is the number of links in a shortest path between the nodes. The distance between two robots is the distance between the two nodes occupied by them. Two robots are neighbors if the nodes occupied by them are neighbors.

Robots are luminous, that is, each robot has a light (or state) that is visible to itself and other robots. A robot can choose the color of its light from a set $Col$. The number of available colors is denoted by $l=|Col|$. Robots have no other persistent memory. Each robot can communicate by observing positions and colors of other robots (for collecting information), and by changing its color and moving (for sending information). Robots are myopic, that is, each robot can observe positions and colors of robots within a fixed distance $\varphi$ ($\varphi >0$) from its current position. We assume that robots share the same $\varphi$. Robots execute the same deterministic algorithm and their behaviors depend on only their observations including their own colors.

Each robot executes an algorithm by repeating a cycle of Look, Compute, and Move phases. At the beginning of the Look phase, the robot takes a snapshot of positions and colors of robots within distance $\varphi$. During the Compute phase, the robot computes its next color and movement according to the snapshot in the Look phase. The robot may change its color at the end of the Compute phase. If the robot decides to move, it moves to a neighboring node during the Move phase. Similarly to most works for graph environments, we assume that moves are instantaneous, that is, all robots exist on nodes in a snapshot. To model asynchrony of executions, we introduce the notion of scheduler that decides when each robot executes phases. When the scheduler makes robot $r$ execute some phase, we say the scheduler activates the phase of $r$ or simply activates $r$. We consider three types of synchronicity: the FSYNC (fully synchronous) model, the SSYNC (semi-synchronous) model, and the ASYNC (asynchronous) model. In all models, time is represented by an infinite sequence of instants $0,1,2,\mathrm{\dots }$. No robot has access to this global time. In the FSYNC model, the scheduler activates all robots at every instant $t$, and all robots execute a full cycle of Look, Compute, and Move phases synchronously and concurrently between $t$ and $t+1$. In the SSYNC model, the scheduler activates a non-empty subset of robots at every instant $t$, and all the activated robots execute a full cycle of Look, Compute, and Move phases synchronously and concurrently between $t$ and $t+1$. In the ASYNC model, the scheduler activates a non-empty subset of robots at every instant $t$, and every activated robot executes one of Look, Compute, and Move phases. If robot $r$ executes a Look phase and another robot $r^{\prime }$ executes a Compute or Move phase at instant $t$, $r$ obtains a snapshot before $r^{\prime }$ changes its color or its position. Note that, in the ASYNC model, the amount of time between two successive phases of a robot is finite but unbounded: For example, after some robot $r$ executes a Look phase, some other robot $r^{\prime }$ can execute an unbounded number of Look, Compute, and Move phases before $r$ executes its next Compute phase. This implies that, in the ASYNC model, a robot can move based on an outdated view obtained during the Look phase in the past configuration. Throughout the paper we assume that the scheduler is fair, that is, each robot is activated infinitely often.

During execution of an algorithm, at most $f$ robots crash. A robot can crash between two consecutive phases in all of the FSYNC, SSYNC, and ASYNC models. If a robot crashes, the robot neither changes its color nor its position after it crashes. Even after robot $r$ crashes, other robots still observe $r$ and the color of $r$, however they cannot distinguish $r$ from a correct robot with the same color as $r$.

In the sequel, $M_i(t)$ denotes the multiset of colors of robots located in node $v_i$ at an instant $t$. If $v_i$ is not occupied by any robot at $t$, then $M_i(t)=\mathrm{\varnothing }$ holds. Let $Crashed(t)$ be the set of crashed robots at an instant $t$. A configuration of the system at an instant $t$ is defined as $\gamma (t)=(Crashed(t),M_0(t),M_1(t),\mathrm{\dots },M_{n-1}(t))$. If $t$ is clear from the context, we simply write $\gamma =(Crashed,M_0,M_1,\mathrm{\dots },M_{n-1})$.

When a robot takes a snapshot of its environment, it gets a view up to distance $\varphi$. Consider a robot $r$ on node $v_i$; then, $r$ obtains two views: the forward view and the backward view. The forward and backward views of $r$ are defined as $V_f=(c_r,M_{i-\varphi },\mathrm{\dots },M_{i-1},M_i,M_{i+1},\mathrm{\dots },M_{i+\varphi })$ and $V_b=(c_r,M_{i+\varphi },\mathrm{\dots },M_{i+1},M_i,M_{i-1},\mathrm{\dots },M_{i-\varphi })$, respectively, where $c_r$ denotes $r$’s color. Since robots cannot recognize the direction, they cannot recognize which of the two views is forward and which is backward. If the forward view and the backward view of $r$ are identical, then $r$’s view is symmetric. In this case, $r$ cannot distinguish between the two directions when it moves, and the scheduler decides which direction $r$ moves to. Note that the scheduler can independently decide the direction regardless of any other movements. If $r$ observes no other robot in its view, $r$ is isolated.

In the FSYNC and SSYNC models, we say that an infinite sequence of configurations $E={\gamma }_0,{\gamma }_1,\mathrm{\dots },{\gamma }_i,\mathrm{\dots }$ is an execution from initial configuration ${\gamma }_0$ if, for any $j>0$, ${\gamma }_j$ is obtained from ${\gamma }_{j-1}$ after every non-crashed robot activated in instant $j-1$ executes a cycle. In the ASYNC model, we say that an infinite sequence of configurations $E={\gamma }_0,{\gamma }_1,\mathrm{\dots },{\gamma }_i,\mathrm{\dots }$ is an execution from initial configuration ${\gamma }_0$ if (i) for any $j>0$, ${\gamma }_j$ is obtained from ${\gamma }_{j-1}$ after every non-crashed robot activated in instant $j-1$ executes a Look, Compute, or Move phase, and (ii) every robot repeats Look, Compute, and Move phases in this order.

A problem $𝒫$ is defined as a set of executions: An execution $E$ solves $𝒫$ if $E\in 𝒫$ holds. An algorithm $𝒜$ solves problem $𝒫$ from initial configuration ${\gamma }_0$ if any execution from ${\gamma }_0$ solves $𝒫$. An algorithm $𝒜$ solves problem $𝒫$ if there exists a configuration ${\gamma }_0$ such that $𝒜$ solves $𝒫$ from ${\gamma }_0$.

In this paper, we consider the perpetual exploration problem.

Since robots do not know $n$, they should explore a ring with any number of nodes in principle. However some algorithms for large rings cannot work on small rings, and consequently many works assume the minimum size of rings to propose algorithms. In this paper, we also assume the minimum size of rings to propose algorithms. On the other hand, for the impossibility, we prove that no algorithm exists for large rings.

First, we show the necessary number of robots to achieve crash-tolerant perpetual exploration.

In this subsection, we propose an algorithm with $f+2$ robots in case of visibility $\varphi =1$. From Theorem 2, this algorithm is optimal in terms of the number of robots.

As described in Section 1.2, we can design simple crash-tolerant algorithms by having $f+1$ teams of robots independently execute crash-free algorithms. Note that the team size depends on $\varphi$. When $\varphi \ge 2$, a team of two robots (e.g., red and blue robots) can achieve perpetual exploration as follows: if the two robots are neighbors, the red robot moves away from the blue robot; otherwise, the blue robot moves toward the red robot [18]. This behavior is not feasible when $\varphi =1$, however by adding an additional robot, they can achieve perpetual exploration as demonstrated in [19]. We formalize these facts in the following theorem.

In the previous subsection, we proved that, when at most $f$ robots crash, $3f+3$ (resp., $2f+2$) robots can achieve perpetual exploration if $\varphi =1$ (resp., $\varphi \ge 2$). In this subsection, we prove that these numbers of robots are necessary. To prove this fact, we use the following lemmas for the case of no crashed robots.

Since these lemmas are almost trivial, we give brief proofs of them. If the number of robots is one, the view of the robot is always symmetric and hence the scheduler decides the direction of the movement. This makes the robot continue to move backward and forward on two neighboring nodes. If the number of robots is two and $\varphi =1$ holds, the scheduler can make two robots separated. This is because, when two robots move in the same directions, the scheduler can activate only the head robot. Once two robots get separated, the views of the two robots are symmetric, and hence they continue to move backward and forward on neighboring nodes.

In the rest of this section, we prove the main impossibility. To prove the impossibility, we consider the behaviors of robots on an infinite line. This is because, if robots can achieve perpetual exploration in any ring, they should visit infinite nodes on an infinite line. Indeed, if robots can visit at most $n$ nodes on an infinite line, they can also visit at most $n$ nodes on a ring with more than $n+\varphi$ nodes and hence they cannot achieve perpetual exploration. On an infinite line, we define a hole as a set of successive non-occupied nodes such that each end node is a neighbor of an occupied node. The size of a hole is defined as the number of nodes in the hole.