---
abstract: 'In this work we investigate this problem in the asynchronous model by luminous robots. In this model a light is attached to the robots, which serves as externally visible bits stored in that light encoded by a color. First, we present an algorithm solving the asynchronous Filling problem with robots having $1$ hop visibility range, $O(\log\Delta)$ bits of persistent storage, and $\Delta+3$ colors, where $\Delta$ is the maximum degree of the graph. Then we show, how the number of colors can be reduced to $O(1)$ at the cost of the running time. After this we show, how the running time can be improved by robots with visibility range of $2$ hops, $O(\log \Delta)$ bits of persistent memory, and $\Delta + 3$ colors. We show, that in the fully synchronous case, the running time of this algorithm is $O(n)$. Finally, we show how to extend our asynchronous solution to the $k$-Door case, $k\geq 2$, by using $\Delta + k + 3$ colors. Finally, we present simulation results that match very well the theoretical bounds.'
author:
- Attila Hideg
- Tamás Lukovszki
bibliography:
- 'bibliography.bib'
title: Asynchronous Filling by Luminous Robots
---

Introduction
============

Multi-robot systems can achieve great scalability, fault tolerance, and cost efficiency in certain problems. Instead of having an expensive robot with redundant hardware and software, the multi-robot system usually consists of rather simple and cheap robots. The robots cooperatively can solve different problems, as gathering, flocking, pattern formation, dispersing, filling, coverage, and exploration (e.g. [@Albers2002; @Albers2000; @Amir19; @Augustine2018; @Barrameda2008; @Barrameda2014; @Brass2011; @Cohen2005; @Hsiang2002; @LukovszkiH14; @Scheideler19]; see [@Flocchini2012; @Flocchini2019] for recent surveys).

The Filling problem was introduced by Hsiang et al. [@Hsiang2002], where the robots enter an a priori unknown but connected area and have to disperse. The area is subdivided into pixels and at the end of the dispersion each pixel has to be occupied by a robot, hence the name Filling.

A fundamental question is how ‘weak’ those robots can be in terms of hardware requirements with still being able to solve the problem, which was initiated by Barrameda et al. [@Barrameda2008; @Barrameda2014].

**Model:** The area which has to be filled is represented by a connected graph. A special vertex is an entry point, which is called the *Door*. When the Door vertex becomes empty, a new robot is placed there immediately. For simplicity we assume the degree of the Door vertex is $1$. Otherwise, we introduce an auxiliary vertex of Degree $1$ connected only to the Door, which takes the role of the original Door (this models the two sides of a doorstep). We assume that (as in [@hideg2018]), for each vertex $v$, the adjacent vertices are arranged in a fixed cyclic order. This cyclic order is only visible for robots at $v$ and it does not change during the dispersion.

The robots act according to the common Look-Compute-Move (LCM) model. In this model, their actions are decomposed into three phases: a *Look* phase, where they take a snapshot of their surrounding, a *Compute* phase, in which they perform calculations, and a *Move* phase, where they move to a neighboring vertex, or stay at place.

Based on the activation times of the robots, there are three main synchronization models studied in the literature: the fully synchronous (FSYNC), the semi-synchronous (SSYNC), and the asynchronous (ASYNC). In the FSYNC model, all robots are activated at the same time and they perform their Look, Compute, and Move phases synchronously at the same time, which is ensured by a global clock. In the SSYNC model, some robots might decide to ’skip’ an LCM cycle, and stay inactive. In the ASYNC model, there is no common notion of time available: the robots activate independently after a finite but arbitrary long time, and perform their LCM cycles. Moreover, their LCM cycle length is not fixed, it also can be arbitrarily long.

The robots are *autonomous*, i.e. no central coordination is present, *homogeneous*, i.e. all the robots have the same capabilities and behaviors, *anonymous*, i.e. they cannot distinguish each other, and *silent*, i.e. they have no communication capabilities and cannot directly talk to one another. However, *luminous* robots can communicate indirectly by using a light. Such robots have a light attached to them, which is externally visible by every robot in their visibility range. They can use a finite set of colors (including the color when the light is off) representing the value of a state variable. The robots are allowed to change these colors in their Compute phase. We denote the availability of lights using a superscript representing the number of colors. In particular, we denote by $X^i$ the model $X \in \{$ASYNC, SSYNC, FSYNC$\}$ when every robot is enhanced by a light with $i > 1$ colors. In the ASYNC$^{O(1)}$ model the robots use constant number of colors (see, e.g. [@das2012]).

**Related Work:** In [@hideg2017; @hideg2018] the Filling problem has been investigated in the FSYNC model. In [@hideg2017] the authors gave a solution for the orthogonal Filling problem by using robots with $1$ hop visibility range and $O(1)$ bits of persistent memory for both the Single and Multiple Door case.

In [@hideg2018] a method for a general Filling problem has been presented, where the area is represented by an arbitrary connected graph. The robots required $1$ hop visibility range and $O(\Delta)$ bits of persistent memory, where $\Delta$ is the degree of the graph. For the $k$-Door case, the memory requirement is $O(\Delta \cdot \log k)$. The general method is called the Virtual Chain Method (VCM), which is leader-follower method. In the VCM, the robots form a chain, and filled the area mimicking a DFS-like traversal of the graph. The algorithms presented in [@hideg2017] and [@hideg2018] are intensively utilizing the synchronous nature of the model to avoid collisions and backtracking. These algorithms do not work in the ASNYC model. In this paper we solve the Filling problem in the ASYNC$^{O(1)}$ model by light-attached robots, a.k.a. luminous robots. Light-attached robots were first investigated by Das et al. [@das2012; @Flocchini16]. They considered the case, where the robots can move in the continuous Euclidean plane and they proved that the asynchronous model with a constant number of colors ASYNC$^{O(1)}$ is strictly more powerful than the semi-synchronous model SSYNC, i.e. ASYNC$^{O(1)}$ $>$ SSYNC. Das et al. [@Flocchini16] also prove that there are problems that robots cannot solve without lights, even if they are fully synchronous, but can be solved by asynchronous luminous robots with $O(1)$ colors.

D’Emidio et al. [@Navarra16] have shown that on graphs one task can be solved in the fully synchronous model FSYNC but not in the asynchronous lights-enhanced model, while for other tasks, the converse holds. We show that the Filling problem can be solved in both models.

**Our Contribution:** In this work we present solutions for the Filling problem by luminous robots on graphs in the ASYNC$^{O(1)}$ model. First, we describe a method, called PACK, which solves the problem by robots with $1$ hop visibility range, $O(\log \Delta)$ bits of persistent memory, and $\Delta + 3$ colors for the single Door case. Then we show how the number of colors can be reduced to $O(1)$ at the cost of running time.

Assuming that all the robots are active all the time until having been switched to Finished state and that the length of the LCM cycles of robot $r_i$, $i=1,\dots,n$ is $t_i$, then the running time is $O(nT)$, where $T=\sum_{i=1}^n {t_i}$. For the fully synchronous case, when all LCM cycles have unit lenght, the running time of this algorithm is $O(n^2)$.

After this, in the ASYNC model we show how the running time can be significantly improved by robots with visibility range of $2$ hops, with no communication, $O(\log \Delta)$ bits of persistent memory, and $\Delta + 3$ colors, by presenting the algorithm called BLOCK. In the fully synchronous case, the running time of this algorithm is $O(n)$.

Then we extend the BLOCK algorithm for solving the $k$-Door Filling problem, $k\geq 2$, by using $\Delta + 3 + k$ colors and $O(\log \Delta)$ bits of memory. The visibility range of $2$ is optimal for the $k$-Door case (a counter example when this problem cannot be solved in the ASYNC model with a visibility range of $1$ hop was presented in [@Barrameda2008], also holds for the ASYNC$^{O(1)}$ model).

Beside the theoretical results, we have implemented our algorithms and performed simulations. The simulation results match very well the theoretical bounds.

PACK Algorithm
==============

Now we describe the PACK algorithm to solve the Filling problem for an area represented by a connected graph of $n$ vertices. PACK is based on the Virtual Chain Method described in [@hideg2018], in which the robots filled the area in a DFS-like dispersion.

The robots are allowed to be in one of the following states: None, Follower, Leader, Finished. They are initialized with None state when placed at the Door. The first robot becomes the Leader and moves to a vertex which has never been occupied before (these vertices are called *unvisited* vertices). The rest of the robots will become Followers and follow the Leader, until the Leader becomes stuck (i.e. no unvisited neighbors available). Then the robot behind the Leader, called the *successor* robot becomes a new Leader and moves if possible. The previous Leader switches to Finished state. The algorithm terminates when each robot is in Finished state.

The name virtual chain comes from the fact that the robots form a chain which is defined as the path from the current Leader to the Door. The chain contains only visited vertices, which can be occupied by the Followers. Each Follower follows its *predecessor*, which is the previously placed robot. We define a new state for the algorithm:

*Packed:* the state of the chain, when each Follower is behind its predecessor, i.e. each vertex in the path of the Leader is occupied by a robot. In this state none of the robots can move except the Leader. Therefore, only the Leader has to know this state.

**The concept:** The Leader moves to unvisited vertices until there is no such neighboring vertex. Before each movement, the Leader waits for packed state, thus it cannot collide with other robots, and the Leader can decide which vertex is unvisited. When the Leader has no neighboring unvisited vertex, it switches to Finished state and does not move anymore. Its successor then becomes the Leader, and the new Leader moves to other unvisited vertices. The robots use $\Delta + 3$ colors. The first $\Delta$ colors show the direction of the target vertex (for each vertex, the adjacent vertices are arranged in a fixed cyclic order), we refer to them as *DIR* colors. Furthermore, we use two colors, denoted by *CONF* and *CONF2* colors, for confirming that a robot has seen a DIR color of the predecessor, which allows the predecessor to move. For this purpose, the CONF color is sufficient, when the predecessor is a Follower robot. However, when the predecessor robot is the Leader and it must change the target vertex after the Packed state is reached (details are provided later) or the predecessor becomes the Leader and it chooses an unvisited target vertex, it indicates the new direction with a new DIR color. Then the CONF2 color is needed for ensuring that the successor has seen the lastly shown DIR color. Furthermore, we use an additional color, called *MOV* color to indicate that a robot is on the way to its target vertex.

Now we describe the rules followed by the robots in different states.

*Leader:* Can only move to an unvisited vertex. When it wants to move, it shows the direction it wants to go to by setting the corresponding DIR color, then it waits until its successor gives a confirmation that it can move by setting its CONF color. During moving the Leader shows the MOV color. When its successor sets its CONF color, the chain is in *Packed* state. This means, each not occupied vertex is also an unvisited vertex (as each vertex in the path of the Leader is occupied by a robot). If the Leader is still on the Door vertex, therefore, it does not have a successor, it can move without waiting the CONF color.

*Follower:* Follows its predecessor. The Follower robot $r$ sets the CONF color if and only if $i$) the predecessor of $r$ is showing its direction, and $ii$) the successor of $r$ – if exists – have set its CONF color (i.e. the successor knows in which direction $r$ will move). This allows the predecessor $r'$ of $r$ to move to its destination knowing: $i$) all the robots behind $r'$ have set CONF color, and $ii$) the robots behind $r'$ will not move until the predecessor of $r$ moved. When $r'$ is the Leader, the chain is in Packed state.

*None:* The robots are initialized with None state when they are placed at the Door. If the robot $r$ in None state has no neighboring robot, then $r$ changes its state to Leader, chooses the unique neighboring vertex as target vertex, sets the MOV color and starts moving there. Otherwise, if the robot $r$ in None state has one neighboring robot, then $r$ becomes a Follower and sets the neighbor to its predecessor.

There are three special situations, where we need the following additional rules:

*Leader target change*: It might happen that the Leader $r$ chooses a target vertex $v$, which is empty at the moment when $r$ performs its Look operation, however, when the successor of $r$ sets the CONF color and $r$ could start to move to $v$, another robot already moved to $v$. In such case, the Leader $r$ has to choose a new target, and the successor of $r$ has to know about this choice. Assume first, that $r$ has an unvisited neighboring vertex. Then $r$ sets the corresponding DIR color and waits until its successor sets the CONF2 color. Finally, the Leader moves to the target. Note that the chain is in Packed state when the successor of the Leader $r$ sets the CONF color. In this moment only the Leader can move. Consequently, the Leader can change the target vertex only once between two movements. If $r$ does not have any unvisited neighboring vertex after $r$ sees the CONF color of the successor then $r$ can not move anymore and the successor must take the leadership (see the rule below). The robot $r$ sets the $\Delta$ direction color, which has special meaning. The successor $r'$ confirms this by seting the CONF2 color. Then $r$ turn off its light $r'$ becomes the Leader. (Note that it would be possible to omit the Leader target change rule by introducing a new color for signaling the Packed state. Then the Leader would only show its direction once the Packed state is achieved, which could be acknowledged with the CONF color.)

*Taking the leadership*: When the Leader $r$ cannot move anymore, its successor has to become the new Leader. The Leader $r$ indicates that it does not have any unvisited neighboring vertex by setting its direction color to $\Delta$. I.e. this color has a special meaning: it indicates that the Leader cannot move anymore and wants to switch to Finished state and the leadership must be taken by its successor. When this is detected by the successor $r'$, it sets its CONF color, waits for the previous Leader to turn off its light, then $r'$ becomes the Leader. Afterwards, $r'$ tries to move to an unvisited vertex.

*Setting movement color*: Before performing the movement the robots have to set their color to MOV. Keeping the old color color could lead to an error. E.g., consider the following situation. 1. The Leader sets a DIR color. 2: The Follower confirms it by the CONF color. 3: The Leader moves by keeping the DIR color. 4: The Follower shows the corresponding DIR color, receives a CONF, and follows the Leader. 5: The Follower reaches its target, sees the old DIR color of the Leader and sets the CONF color, before the Leader chouses the new target. In order to prevent such situations, the moving robots set their color to MOV and keep this color until the target is reached and a new target is determined. After the movement, the robot sets the previous position as its *Entry* vertex Pseudocode of the PACK algorithm is provided in the Appendix.

Analysis
--------

Leader only moves to unvisited vertices. \[lemma:m1\_unvisited\]

An unvisited vertex means no robot has occupied it before. As the Leader can only move when the chain is in Packed state, each vertex not occupied by a robot is an unvisited vertex. Therefore, each unoccupied vertex, which can be chosen by the Leader, is an unvisited vertex.

There can be at most one Leader at any time. \[lemma:m1\_one\_leader\]

Recall the rule *taking the leadership*. When a Leader $r$ becomes stuck, $r$ signals this with a special color $\Delta$ and switches to Finished state after the successor $r'$ sets the CONF color. Then $r'$ becomes the new Leader, and acts accordingly.

The first robot placed becomes the Leader, and from that time each robot can become a Leader after the previous one became Finished. Therefore, at most one Leader can exist at any time during the dispersion.

Robots cannot collide. \[lemma:m1\_collision\]

When placed, except the first robot, each robot has only one neighbor robot. That will be its predecessor, which the robot will follow during the algorithm. Before the predecessor moves away, it shows which direction it moves. Therefore, the Follower can always follow it. As each Follower robot has one predecessor they cannot collide with each other.

However, the Leader does not follow its predecessor (as it does not have any). It is required to move to unvisited vertices in order to avoid collisions with Followers (which only move to already visited vertices). As there is only one Leader and it always moves to unvisited vertices, collisions are not possible.

PACK fills the area represented by a connected graph. \[lemma:m1\_fills\]

For contradiction, assume the area is not filled when the algorithm terminates. As the area is connected, there is a vertex $v$ which is not occupied and has a neighboring robot in Finished state. If $v$ is unvisited, let $r$ be the last neighboring robot of $v$ which became Finished. However, $r$ cannot switch to Finished state since there is an unvisited vertex neighboring to it. This contradicts the assumption that $v$ remains unoccupied.

Assume now $v$ is unoccupied but it has been visited during the algorithm. Let $t$ be the last time $v$ was occupied by a robot $r$. After $r$ moves from $v$, its successor will occupy $v$. This contradicts the assumption that $t$ was the last time of occupation of $v$. This proves the claim the area is filled when the algorithm terminates.

Algorithm PACK fills a connected area represented by a connected graph in the ASYNC model by robots having a visibility range of $1$ hop, $O(\log \Delta)$ bits of persistent storage and $\Delta + 3$ colors. \[thm:m1\]

As the area is filled (by Lemma \[lemma:m1\_fills\]), and collisions are not possible (by Lemma \[lemma:m1\_collision\]), the area will be filled without collisions. The robots require $O(\log \Delta)$ bits of memory to store the following: *$State$* (4 states – 2 bits), *$Target$* (direction of the target vertex – $\lceil \log \Delta \rceil$ bits), *$NextTarget$* (direction of the vertex, where the robot needs to move after the vertex $Target$ is reached – $\lceil \log \Delta \rceil$ bits). Regarding the number of colors, the robots use $\Delta$ colors to show the direction where the target of the robot is. There are two additional colors (CONF and CONF2) for confirming the robot saw the signaled direction of the predecessor and one color (MOV) during the movement.

**Remark**: The ASYNC model allows a robot to be inactive between two LCM cycles. Since the inactive phase allowed to be finite but arbitrarily long, the runtime of the algorithm can also be arbitrarily long. In the case, where we do not allow inactive intervals between the LCM cycles and assume that each cycle of the robot $r_i$ takes $t_i$ time, $i=1, \dots , n$, we can give a stronger upper bound for the running time.

Assume that the robots have no inactive intervals between two LCM cycles and each cycle of the robot $r_i$ takes $t_i$ time, $i=1, \dots , n$. Then the running time of the algorithm PACK is $O(n\cdot T)$, where $T=\sum_{i=1}^n {t_i}$. \[thm:m1b\]

Assume a chain containing $r_1$, $r_2$, $\dots$, $r_i$ (where $r_1$ is the active Leader, and $r_2$, $\dots$, $r_i$ are on the path from the Leader to the Door), and assume the chain is in Packed state.

=\[draw,circle,fill=black,text=white,minimum size=21pt,inner sep=0pt\]

(0,1) node (0) [$r_4$]{}; (1,1) – (10,1); (0,2) node (1) [$r_3$]{}; (1,2) – (10,2); (0,3) node (2) [$r_2$]{}; (1,3) – (10,3); (0,4) node (3) [$r_1$]{}; (1,4) – (10,4); (0,4.2) – (0,4.7); (0) – (1); (1) – (2); (2) – (3);

in [0,...,9]{} (1.2+0.9\*,3.8) rectangle (2 +0.9\*,4.2); in [0,...,11]{} (1.2+0.7\*,2.8) rectangle (1.8+0.7\*,3.2); in [0,...,21]{} (1.2+0.4\*,1.8) rectangle (1.5+0.4\*,2.2); in [0,...,16]{} (1.2+0.5\*,0.8) rectangle (1.6+0.5\*,1.2);

(1.2,3.8) rectangle (2,4.2); (2.6,2.8) rectangle (3.2,3.2); (3.2,1.8) rectangle (3.5,2.2); (3.7,0.8) rectangle (4.1,1.2); (6.6,3.8) rectangle (7.4,4.2); (5.4,2.8) rectangle (6.0,3.2); (4.8,1.8) rectangle (5.1,2.2); (4.2,0.8) rectangle (4.6,1.2); (7.5,2.8) rectangle (8.1,3.2); (8.4,3.8) rectangle (9.2,4.2);

Assume first that the Leader $r_1$ has an unvisited neighboring vertex. Denote by $T'$ the time between two consecutive movements of the Leader. We divide $T'$ into three time intervals: $T'=T_1 + T_2 + T_3$. $T_1$ starts with the movement of the Leader, it includes the time, when all robots in the chain making one step forwards, and the time for placing a new robot at the Door. $T_2$ starts after placing a new robot at the Door. In $T_2$ the robots, starting from the Door, set their CONF color one by one. This CONF color is ’propagated’ to the Leader, meaning the Leader recognizes the Packed state, and can move again. $T_3$ starts after the Leader recognizes the CONF color of the successor, i.e. after achieving the Packed state. Then the Leader might find its target occupied by another robot. In this case the *Leader target change* rule will be used.

In $T_1$ the Leader $r_1$ moves to its target, then $r_1$ sets its direction color. After $t_1$ time (the length of the LCM cycle of $r_1$), the current LCM cycle of $r_2$ has to be finished, then $r_2$ recognizes the movement at the beginning of its next LCM cycle (i.e. after at most $t_2$ time). In that cycle it also moves and sets its direction color, this takes $t_2$ time. Therefore, after the movement of $r_1$ the robot $r_2$ moves within $2\cdot t_2$ time. This argument can be repeated to all robots until the last one $r_i$ moves. Therefore, the new robot $r_{i+1}$ will be placed after $T_1 \leq 2\sum_{j=1}^{i}{t_j}$ time (see  \[fig:movement\_step\]). Now the second phase $T_2$ starts.

In $T_2$ the new robot $r_{i+1}$ sets its color to CONF. The previous one recognizes it in the its next LCM cycle (within $t_i$ time) and sets its color to CONF in that LCM cycle (which takes $t_i$ time). Therefore, after the placement of $r_{i+1}$, the robot $r_i$ sets its CONF color in $2t_i$ time. Repeating this argument for $r_{i-1},\dots,r_2$, $T_2 \leq 2\sum_{j=2}^{i+1}{t_j}$.

In $T_3$ if the target vertex $v$ of the Leader is unoccupied the Leader can move immediately. Otherwise, if $v$ is occupied, the *Leader target change* protocol is performed, i.e. 1: the Leader chooses a new unoccupied neighboring vertex and shows the corresponding DIR color, 2: its successor sets its color to CONF2. This takes at most $2(t_1+t_2)$ time. After this the Leader can move.

Let $T=\sum_{j=1}^n {t_j}$ be the sum of the lengths of the LCM cycles of all robots. Then $T' = T_1 + T_2 + T_3 \leq 6 T$.

Assume now that $r_1$ has no unvisited neighboring vertex. Then $r_1$ sets its $\Delta$ color. The robot $r_2$ recognizes it in its next cycle and sets its CONF color (i.e. within $2t_2$ time). The robot $r_1$ sees it in its next cycle, $r_1$ turns its light off and switches to Finished state (takes $\leq 2t_1$ additional time). The robot $r_2$ sees it in its next cycle, $r_2$ becomes the new Leader, and checks if there is a neighboring unvisited vertex. If so, $r_2$ sets the corresponding DIR color (takes $\leq 2t_2$ additional time), otherwise the leadership has to be taken by the successor of $r_2$.

When a Leader can move, it occupies an unvisited vertex within $6T$ time. Otherwise, its successor takes the leadership. Since the leadership is taken at most once by each robot during the whoole algorithm, and there are $n$ robots in the filled graph, at most $6T$ time is used for all ’leadership taking’ altogether. Thus, after at most $6nT+6T=O(nT)$ time all vertices of the graph become filled.

In the fully synchronous model, the running time of the PACK algorithm $O(n^2)$ LCM cycles.

Filling of graphs using constant number of colors
-------------------------------------------------

The PACK algorithm uses $\Delta+3$ colors. We can reduce the number of colors to $O(1)$ at the cost of the running time, as follows. We encode the $L=\Delta+3$ colors by a sequence of $\lceil \log L \rceil$ bits and transmit this sequence by emulating the Alternating Bit Protocol (ABP), also referred to as Stop-and-wait ARQ (see, e.g. [@Tannenbaum10]). This protocol uses a sequence number from $\{0,1\}$ alternately to transmit the bits. The sender has four states corresponding to the transmitted bit $b\in \{0,1\}$ and the sequence number. The receiver has two states that represent which sequence number is awaited. The data bits are accepted with alternating sequence numbers. This protocol ensures the correct transmission of the bit sequence without duplicates.

We emulate the ABP by using six different colors, one for each of the four states of the sender and one for each of the two states of the receiver. Seeing the current color of the sender, the receiver can decode the sequence number and the data bit. When a color corresponding the correct sequence number is seen, the receiver sets its color indicating that it waits for the next bit. When the sender sees the changed color of the receiver it sets its color corresponding to the next data bit and next sequence number. This modification leads to the following Theorem.

The modified Algorithm PACK fills an area represented by a connected graph in the ASYNC model by robots having a visibility range of $1$, $O(\log \Delta)$ bits of persistent storage and $O(1)$ colors.

BLOCK Algorithm
===============

The PACK algorithm solves the Filling problem in arbitrary connected graphs by robots with a visibility range of 1 hop. An important property of the PACK algorithm is that the Leader can only move when the chain has reached the Packed state. When the visibility range of the robots is only 1 hop and the Packed state of the chain is not required before the Leader moves, the Leader cannot distinguish between unvisited vertices and those that are unoccupied but part of the chain (those will be occupied and the Leader might collide with them). To handle this problem we consider robots with a visibility range of $2$ hops. Then the robots see each robot, that potentially could choose the same target vertex. The idea is that the Leader only chooses a vertex $v$ as target, if the $1$ hop neighborhood of $v$ does not contain any other robot with light turned on, except when the light showing direction $\Delta$ (i.e. the robot will not move anymore, it wants to switch to Finished state, and waiting to the confirmation of the successor). A vertex neighboring to a robot with its light on (except the color $\Delta$) is considered as *blocked* vertex for the Leader.

We introduce the following additional rules for the robots:

*Leader*: The Leader must not choose a blocked vertex as target. As the visibility range of the robots is 2 hops, the Leader can identify the blocked neighbors. When only blocked or occupied vertices surround the Leader, it chooses to terminate its actions (sets the color $\Delta$ and after the confirmation of the successor it switches to Finished state) and the leadership will be taken by its successor.

*Follower*: Follower robots ’block’ all their unoccupied neighboring vertices. As a result, all unoccupied vertices that are part of the chain are blocked: Before a Follower $r$ would move from a vertex $v$, it sets the DIR color corresponding to the target and blocks all of its unoccupied neighboring vertices. In particular, it blocks the target vertex. Thus the Leader cannot choose the same target. Then $r$ waits until the successor $r'$ sets its CONF color and $r$ moves from $v$. During the movement the MOV color is set, which keeps the same unoccupied vertices blocked. When $r$ leaves $v$, the vertex $v$ is blocked by $r'$. These rules ensure that each vertex on the chain is either occupied or blocked. Consequently, the Leader only moves to unvisited vertices. Pseudocode of the BLOCK algorithm is provided in the Appendix.

Analysis
--------

Leader only moves to unvisited vertices. \[lemma:m2\_unvisited\]

Consider a visited vertex $v$ neighboring to the Leader. Let $r$ be the last robot, that occcupied $v$. When $r$ left $v$, the successor of $r$ blocks $v$. Thus, the Leader cannot move to $v$.

There can be at most one Leader at a time. \[lemma:m2\_one\_leader\]

The arguments of Lemma \[lemma:m1\_one\_leader\] can be repeated as the rule for taking of the leadership did not change.

Robots cannot collide. \[lemma:m2\_collision\]

The arguments of Lemma \[lemma:m1\_collision\] can be repeated as Lemma \[lemma:m2\_one\_leader\] only allows one Leader, which only can move to unvisited vertices (Lemma \[lemma:m2\_unvisited\]).

BLOCK fills the area represented by a connected graph. \[lemma:m2\_fills\]

We use similar arguments to those in the proof of Lemma \[lemma:m1\_fills\]. Assume that all the robots are in Finished state and there is an unoccupied vertex $v$, such that $v$ has at least one occupied neighbor. Additionally, to the cases considered in the proof of Lemma \[lemma:m1\_fills\], we have to consider the case when $v$ is blocked, and all neighboring robots become Finished. Let $t$ be last time when a robot $r$, neighboring to $v$, switches to Finished state. Since all other neighboring robots of $v$ are in Finished state at time $t$, they do not block $v$. Therefore, at time $t$ the robot $r$ can move to $v$ instead of switching to Finished. Thus, we have a contradiction.

Algorithm BLOCK fills the area represented by a connected graph in the ASYNC model by robots having a visibility range of $2$ hops, $O(\log \Delta)$ bits of persistent storage and using $\Delta + 3$ colors.

We can use the arguments of the proof of Theorem \[thm:m1\] as the area is filled (by Lemma \[lemma:m2\_fills\]), and collisions are not possible (by Lemma \[lemma:m2\_collision\]), the area will be filled without collisions. The robots store the same data in their persistent storage as in Theorem \[thm:m1\] and use the same set of colors.

The runtime improves compared to the PACK algorithm. We provide runtime analysis of the BLOCK algorithm in the fully synchronous model.

In the fully synchronous model, the BLOCK algorithm fills the area represented by a connected graph in $O(n)$ LCM cycles. \[thm:m2r\]

Assume a chain containing $r_1$, $r_2$, $\dots$, $r_j$ (where $r_1$ is the active Leader, and $r_2$, $\dots$, $r_j$ are on the path from the Leader to the Door), and assume that the Leader $r_1$ occupied its position and its successor $r_2$ is arrived to the previous position of $r_1$. When the first robot is placed at the Door, it detects in its first LCM cycle if it is a Leader or a Follower. If the only neighbor is unoccupied, it becomes a Leader and moves in the first cycle. In the next cycle the next robot is placed at the Door.

Assume, a robot $r_i$, $i<j$, is either a Leader or a Follower and has its successor $r_{i+1}$ at its previous vertex. If $r_i$ is Leader, we additionally assume that it has an unblocked and unoccupied neighboring vertex. Then $r_i$ sets the corresponding DIR color in that LCM cycle. We denote this LCM cycle by $t$. In the LCM cycle $t+1$ the robot $r_{i+1}$ sets its color to the CONF color, allowing $r_i$ to move in $t+2$. Consequently, the robot $r_i$ can move in $3$ cycles if the successor is on its previous vertex.

Then, in cycle $t+3$ the robot $r_{i+1}$ detects that $r_i$ left the neighboring vertex $v$ and $r_{i+1}$ sets the DIR color indicating the target $v$. In cycle $t+4$ the robot $r_{i+2}$ – if exists – confirms it by setting its color to CONF. Therefore, $r_{i+1}$ can move in cycle $t+5$. (If $r_{i+1}$ is at the Door and $r_{i+2}$ does not exists, $r_{i+1}$ does not have to wait for the confirmation before the movement.) Now, as $r_{i+1}$ is on the previous vertex of $r_i$, $r_i$ can move in $3$ cycles, i.e. in cycle $t+8$. Therefore, the robot $r_i$ moves in every $6^{th}$ cycle if $r_i$ is a Follower or it is a Leader with an unblocked and unoccupied neighbor.

Assume now that $r_i$ is Leader, its successor $r_{i+1}$ is at its previous vertex, and all neighboring vertices of $r_i$ are blocked or occupied in cycle $t$. Then $r_i$ sets its $\Delta$ color to show the successor that it has to switch to Finished state. The successor $r_{i+1}$ confirms it in cycle $t+1$. In cycle $t+2$ the robot $r_i$ becomes Finished and $r_{i+1}$ becomes the new Leader. Therefore, the leadership is taken in $3$ LCM cycles. In $t+3$ the new Leader $r_{i+1}$ shows its new target if there is an unblocked and unoccupied neighboring vertex, or it sets the $\Delta$ to show the successor that it has to switch to Finished state.

When a Leader can move, it occupies an unvisited unblocked vertex in every $6^{th}$ cycle. Otherwise, its successor takes the leadership. Since the leadership is taken at most once by each robot during the whoole algorithm, and there are $n$ robots in the filled graph, at most $3n$ cycles used for all ’leadership taking’. Therefore, after $6n+3n$ cycles all vertices of the graph become filled.

Multiple Door
=============

For the multiple Door Filling, there is a situation which cannot be solved by the above methods: Let $v$ be an unvisited vertex, which is neighboring to (at least) two Leaders $r_1$ and $r_2$. In order to fill the graph, exactly one of the Leaders, $r_1$ or $r_2$, has to move to vertex $v$. If one of the robots, say $r_1$, has been activated earlier, then $r_1$ sets the direction color corresponding to $v$ and it prevents $r_2$ to move to $v$ ($r_1$ blocks $v$ from $r_2$). However, if the activation times of $r_1$ and $r_2$ are exactly the same, then they would set the direction color at the same time, meaning they mutually block each other from moving to $v$. If $r_1$ or $r_2$ has no other unvisited vertex in their neighborhood, then none of them could move, and particularly, none of them would occupy $v$.

We propose a protocol, which uses a strict priority order between the Leaders originating from different doors.

**Priority protocol**: The robots have $k$ additional different colors corresponding to the door they used for entering the area, where $k$ is the number of doors. We define a strict total order between these colors, called priority order. We call these $k$ colors priority colors. After showing the direction to the successor and after the successor has confirmed it, the Leader sets its color to the corresponding priority color (instead of the MOV color) and starts its movement. It arrives to its target showing its priority color. We modify the blocking rule for the Leader in the following way: If there is a robot with a direction color (except the special color $\Delta$), or confirmation color, or MOV color, or priority color with higher priority than $r$, then its neighbors are considered as blocked. Since there is a strict total order between the priority colors, in such situation exactly one of them is allowed to move there.

We slightly change the rule *taking the leadership*: when the successor robot $r$ notices that the Leader is switching to Finished state (by setting the direction color to $\Delta$), $r$ confirms it by setting its color to the priority color of the old Leader.

Priority protocol does not allow collisions. \[lemma:m3\_collision\]

Assume $v$ is an unvisited vertex which is neighboring to two Leaders $r_1$ and $r_2$, i.e. both $r_1$ and $r_2$ could move to $v$. Let $t_1$ (resp. $t_2$) be the first activation time of $r_1$ (resp. $r_2$) after it has arrived at its current position.

If $t_1 \neq t_2$, then one of them, which was activated before the other one, will block the other one and they cannot collide. If $t_1 = t_2$, then they will see each others priority color. Then they can decide which robot has higher priority. The robot with higher priority will block the other one. Consequently, Leaders cannot collide with each other.

Now we show that the collision with a Follower is also not possible. When the Follower $r$ would move to a vertex $v$ it has its CONF color set allowing the predecessor $r'$ to leave $v$. This blocks $v$ for all Leaders. The predecessor $r'$ also blocks $v$ until $r$ occupies it. Therefore, $r$ cannot collide with a Leader.

The BLOCK algorithm extended with the Priority protocol fills the connected graph. \[lemma:m3\_fills\]

We can repeat the arguments of the proof of Lemma \[lemma:m2\_fills\].

Algorithm BLOCK extended with the Priority protocol solves the $k$-Door Filling problem, $k\geq 2$, in the ASYNC model in finite time, with $2$ hops of visibility, $O(\log \Delta)$ bits of memory and using $\Delta + k + 3$ colors.

We can use the arguments of the proof of Theorem \[thm:m1\] as the area is filled (by Lemma \[lemma:m3\_fills\]), and collisions are not possible (by Lemma \[lemma:m3\_collision\]), the area will be filled without collisions. The robots store the same data in their persistent storage as in Theorem \[thm:m1\] and use $\Delta + k + 3$ colors.

Simulation Results
==================

We have implemented our algorithms for the single Door case and conducted simulations on different graph topologies. The tested topologies are Line graphs, Stars, and Delaunay triangulations with vertices uniformly randomly distributed in a square area. For the runtime, we assumed the FSYNC model (i.e. all robots are active in every LCM-cycle), therefore the runtimes are better comparable.

Line graph
----------

A line graph consist of $n\geq 1$ vertices $V=\{v_1,...,v_n\}$ and edges $E=\{(v_i,v_{i+1}): 1\leq i< n\}$. The Door vertex is at $v_1$ in the end of the line. In this case there are no branching vertices, the robots move on a unique path.

table \[x=a, y=b, col sep=comma\] [line\_PACK.csv]{}; table \[x=a, y=b, col sep=comma\] [line\_BLOCK.csv]{};

The line graph exhibits a worst case input for the PACK algorithm, since one Leader traverse the whole line and between two consecutive steps of the Leader all robots must form a Packed chain. This results in a quadratic running time. The BLOCK algorithm runs in linear time, which is also confirmed by the simulations. (Figure \[fig:line\_simulation\]).

Star graph
----------

A star graph of $n\geq 1$ consist of one central vertex $v_1$, which is connected to all other vertices $\{v_2,...,v_n\}$ by an edge. All vertices in $\{v_2,...,v_n\}$ are only conneted to $v_1$ by an edge. The Door is placed at one of the degree 1 vertices. In this topology the Leader first moves to the central vertex, then to one of the degree 1 nodes, and becomes Finished. The leadership is taken by its Follower occuying $v_1$. Then the new Leader moves to one of the leaves and the leadership is taken by its Follower occuying $v_1$, etc... In this case the lenghts of the chain behind the current Leader is at most 2 and the Packed state is achieved in constant number of LCM-cycles. Therefore, the PACK algorithm runs in linear time on the star.

table \[x=a, y=b, col sep=comma\] [star\_PACK.csv]{}; table \[x=a, y=b, col sep=comma\] [star\_BLOCK.csv]{};

The results can be seen in  \[fig:star\_simulation\], which shows that the runtime of the PACK and the BLOCK algorithm is exactly the same in both cases, both runtimes are linear in the number of vertices.

Random Delaunay triangulation
-----------------------------

In these test cases the graphs are generated by using the following method. $i$) In a square area we select $n$ points independently, uniformly at random, where $n$ is the size of the graph. $ii$) Using the first $n-1$ points we compute a Delaunay triangulation. Then we add $n$-th point as Door vertex as an auxiliary vertex to the closest random vertex.

table \[x=a, y=b, col sep=comma\] [rand\_PACK.csv]{}; table \[x=a, y=b, col sep=comma\] [rand\_BLOCK.csv]{}; table \[x=a, y=b, col sep=comma\] [reference\_x2.csv]{};

For this simulation, we generated $50$ random Delaunay graphs using the described method for each vertex set size, $n=3,\dots, 200$. Then, for each input graph, we measured the number of LCM-cycles performed by both the PACK and the BLOCK algorithms. Then we computed the average runtimes of the 50 runs of both algorithms for each input size, $n=3,\dots, 200$. The simulation results (Figure \[fig:simulation\_del\]) for the PACK algorithm suggest quadratic growth: In the plot with log-scaled $x$- and $y$-axis the runtime curve $x\rightarrow x^2$, which suggests quadratic growth. The simulations also confirm linear runtime for the BLOCK algorithm.

Multiple Doors
--------------

For this simulation, for $n=1000$ vertices and $k=1,\dots, 200$ Doors, we generate 50 random Delaunay graphs as follows: $i$) In a square area we select $n$ points independenty, uniformly at random, where $n$ is the size of the graph. $ii$) Using the first $n-k$ points we compute a Delaunay triangulation. Then we add the remaining $k$ points as Door vertices and join each of them with the closest Delaunay vertex. The purpose of this simulation was to test the speed-up of the algorithm in case there are multiple entry points (Doors). For each $k=1,\dots, 200$ we plotted the average runtime on the 50 randomly generated Delaunay triangulations. The simulation results in Figure \[fig:simulation\_md\] indicate that runtime of the $k$-Door BLOCK algorithm is proportional to $n/k$ for this simulation setting.

table \[x=a, y=b, col sep=comma\] [multi\_BLOCK.csv]{};

Summary {#sec:summary}
=======

In this work we have presented solutions for the Filling problem by luminous robots in the ASYNC$^{O(1)}$ model. We have presented a method, called PACK, which solves the problem by robots with $1$ hop visibility range, $O(\log \Delta)$ bits of persistent memory, and $\Delta + 3$ colors for the single Door case. We have shown how the number of colors can be reduced to $O(1)$ at the cost of running time. Assuming that all the robots are active all the time until switching in Finished state and that the length of the LCM cycles of robot $r_i$, $i=1,\dots,n$ is $t_i$, then the running time is $O(nT)$, where $T=\sum_{i=1}^n {t_i}$. For the fully synchronous case, when all LCM cycles have unit length, it implies an $O(n^2)$ running time.

After this, in the ASYNC model we have shown how the running time can be significantly improved by robots with visibility range of $2$ hops, $O(\log \Delta)$ bits of persistent memory, and $\Delta + 3$ colors, by presenting the algorithm called BLOCK. In the fully synchronous case the running time of this algorithm is $O(n)$.

We have extended the BLOCK algorithm for solving the $k$-Door Filling problem, $k\geq 2$, by using $\Delta + 3 + k$ colors and $O(\log \Delta)$ bits of memory. The visibility range of $2$ is optimal for the $k$-Door case (a counter example when this problem cannot be solved in the ASYNC model with a visibility range of $1$ hop was presented in [@Barrameda2008], also holds for the ASYNC$^{O(1)}$ model).

Beside the theoretical results, we have implemented our algorithms and performed simulations. The simulation results match very well the theoretical bounds.

Appendix
========

If $r$.$State$ is Follower:\
If $r$.$NextTarget$ is not set:\
If $r$.$Predecessor$ shows DIR color:\
Store shown DIR as $r$.$NextTarget$\
Else If $r$.$Predecessor$ shows DIR color $\Delta$:\
$r$ switches to Leader state\
Else:\
If $r$.$Color$ is not set to CONF:\
If $r$.$Entry$ is not set:\
Set $r$:$Color$ to CONF\
Else If $r$.$Entry$ is occupied and $r$.$Successor$ has light set to a CONF color:\
Set $r$:$Color$ to CONF\
Else If $r$.$Target$ is unoccupied:\
$r$ sets $r$.$Color$ to MOV\
$r$ moves to $r$.$Target$ and\
$r$ sets $r$.$Color$ sets light to match $r$.$NextTarget$\
$r$ sets $r$.$Target$ to $r$.$NextTarget$\
Else If $r$.$Predecessor$ shows DIR color $\Delta$:\
$r$ switches to Leader state\
Else If $r$.$NextTarget$ has been set:\
If $r$.$Predecessor$ shows different direction:\
$r$ sets $r$.$NextTarget$ to new shown direction\
$r$ sets light to CONF2 color

If $r$.$State$ is Leader:\
If $r$.$Target$ is not set:\
$r$ sets $r$.$Target$ to first empty neighbor\
If $r$.$Target$ is not set (no empty neighbor found):\
$r$ sets DIR color $\Delta$ and becomes Finished\
Else:\
If $r$ is waiting for CONF:\
If $r$.$Successor$ has light set to a CONF color:\
If $r$.$Target$ is unoccupied:\
$r$ sets $r$.$Color$ to MOV\
$r$ moves to $r$.$Target$\
$r$ clears $r$.$Target$\
Else If $r$ has unoccupied neighbor $v$:\
$r$ sets $r$.$Target$ and set DIR color to match the direction of $v$\
$r$ is now waiting for CONF2\
Else:\
$r$ sets DIR color $\Delta$ and becomes Finished\
Else:\
Waits for $r$.$Successors$ to set CONF color\
Else If $r$ is waiting for CONF2:\
If $r$.$Successor$ has light set to a CONF2 color:\
$r$ sets $r$.$Color$ to MOV\
$r$ moves to $r$.$Target$\
$r$ clears $r$.$Target$\
Else:\
Waits for $r$.$Successors$ to set CONF color\
If $r$.$State$ is None:\
$r$ sets $r$.$Target$ to neighbor\
If $r.Target$ does not contain robot:\
$r$ becomes the Leader\
$r$ sets $r$.$Color$ to MOV\
$r$ moves to $r$.$Target$\
$r$ clears $r$.$Target$\
Else:\
$r$ becomes a Follower\

If $r$.$State$ is Follower:\
If $r$.$NextTarget$ is not set:\
If $r$.$Predecessor$ shows DIR color:\
Store shown DIR as $r$.$NextTarget$\
Set $r$.$Color$ to CONF\
If $r$.$Predecessor$ shows DIR color $\Delta$:\
$r$ switches to Leader state\
Else:\
If $r$.$Color$ is set to CONF or CONF2:\
If $r$.$Target$ is unoccupied:\
Set $r$.$Color$ to DIR to match $r$.$Target$\
Else:\
If $r$.$Predecessor$ shows DIR color $\Delta$:\
$r$ switches to Leader state\
Else If $r$.$NextTarget$ has been set:\
If $r$.$Predecessor$ shows different direction:\
$r$ sets $r$.$NextTarget$ to new shown direction\
$r$ sets light to CONF2 color Else:\
If $r$.$Entry$ is not set or $r$.$Entry$ is occupied\
and $r$.$Successor$ has light set to a CONF color:\
Else If $r$.$Target$ is unoccupied:\
$r$ sets $r$.$Color$ to MOV\
$r$ moves to $r$.$Target$\
sets light to match $r$.$NextTarget$\
$r$ sets $r$.$Target$ to $r$.$NextTarget$\
Else If $r$.$Predecessor$ shows DIR color $\Delta$:\
$r$ switches to Leader state\
$r$ is now waiting for CONF2\
If $r$.$State$ is Leader:\
If $r$.$Target$ is not set:\
$r$ sets $r$.$Target$ to first empty and not blocked neighbor\
If $r$.$Target$ is not set (no empty neighbor found):\
$r$ sets DIR color $\Delta$ and becomes Finished\
Else:\
If $r$ is waiting for CONF:\
If $r$.$Entry$ is not set:\
$r$ sets $r$.$Target$ to first empty and not blocked neighbor\
If $r$.$Target$ is not set (no empty neighbor found):\
$r$ sets DIR color $\Delta$ and becomes Finished\
Else:\
$r$ sets $r$.$Color$ to MOV\
$r$ moves to $r$.$Target$\
$r$ clears $r$.$Target$\
If $r$.$Entry$ is occupied\
If $r$.$Successor$ has light set to a CONF or CONF2 color:\
If $r$.$Target$ is occupied:\
$r$ sets $r$.$Target$ to first empty and not blocked neighbor\
If $r$.$Target$ is not set (no empty neighbor found):\
$r$ sets DIR color $\Delta$ and becomes Finished\
Else:\
$r$ sets $r$.$Color$ to MOV\
$r$ moves to $r$.$Target$\
$r$ clears $r$.$Target$\
Else:\
$r$ sets $r$.$Target$ to first empty and not blocked neighbor\
If $r$.$Target$ is not set (no empty neighbor found):\
$r$ sets DIR color $\Delta$ and becomes Finished\
Else If $r$ is waiting for CONF2:\
If $r$.$Successor$ has light set to a CONF2 color:\
$r$ sets $r$.$Color$ to MOV\
$r$ moves to $r$.$Target$\
$r$ clears $r$.$Target$\
Else:\
Waits for $r$.$Successors$ to set CONF2 color\
If $r$.$State$ is None:\
$r$ sets $r$.$Target$ to neighbor\
If $r.Target$ does not contain robot:\
$r$ becomes the Leader\
$r$ sets light to MOV\
$r$ moves to $r$.$Target$\
$r$ clears $r$.$Target$\
Else:\
$r$ becomes a Follower\
