D ' Gianlorenzo
email: gianlorenzo.dangelo@inria.fr

Angelo

Gabriele Di
email: gabriele.distefano@univaq.it

Alfredo Navarra
email: alfredo.navarra@unipg.it

How to gather asynchronous oblivious robots on anonymous rings

A set of robots arbitrarily placed on different nodes of an anonymous ring have to meet at one common node and remain in there. This problem is known in the literature as the gathering. Anonymous and oblivious robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move). Cycles are asynchronous among robots. Moreover, each robot is empowered by the so called multiplicity detection capability, that is, it is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. The described problem has been extensively studied during the last years. However, the known solutions work only for specific initial configurations and leave some open cases. In this paper, we provide an algorithm which solves the general problem, and is able to detect all the ungatherable configurations. It is worth noting that our new algorithm makes use of a unified and general strategy for any initial configuration, even those left open by previous works.

Introduction

We study one of the most fundamental problems of self-organization of mobile entities, known in the literature as the gathering problem (see e.g., [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF][START_REF] Degener | A tight runtime bound for synchronous gathering of autonomous robots with limited visibility[END_REF][START_REF] Flocchini | Gathering of asynchronous robots with limited visibility[END_REF] and references therein). In particular, we consider oblivious robots initially located at different nodes of an anonymous ring that have to gather at a common node and remain in there. Neither nodes nor links are labeled. Initially, each node of the ring is either occupied by one robot or empty. Robots operate in Look-Compute-Move cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it moves to this neighbor (Move), eventually. Cycles are performed asynchronously for each robot. This means that the time between Look, Compute, and Move operations is finite but unbounded, and it is decided by the adversary for each robot. Hence, robots may move based on significantly outdated perceptions. Moves are instantaneous, and hence during a Look operation robots are seen at nodes and not on edges. Robots are identical, execute the same deterministic algorithm and are empowered by the so-called multiplicity detection capability [START_REF] Izumi | Randomized gathering of mobile robots with local-multiplicity detection[END_REF]. That is, a robot is able to perceive whether a node of the network is empty, occupied by a single robot or by more than one (i.e., a multiplicity occurs), but not the exact number. Without multiplicity detection the gathering has been shown to be impossible on rings [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF].

Related Work. The problem of let meet mobile entities on graphs [START_REF] Bampas | Almost optimal asynchronous rendezvous in infinite multidimensional grids[END_REF][START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF][START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF] or open spaces [START_REF] Cord-Landwehr | A new approach for analyzing convergence algorithms for mobile robots[END_REF][START_REF] Degener | A tight runtime bound for synchronous gathering of autonomous robots with limited visibility[END_REF][START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF] has been extensively studied in the last decades. When only two robots are involved, the problem is referred to as the rendezvous problem [START_REF] Alpern | The rendezvous search problem[END_REF][START_REF] Chalopin | Rendezvous of mobile agents without agreement on local orientation[END_REF][START_REF] Czyzowicz | How to meet asynchronously (almost) everywhere[END_REF][START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF][START_REF] Yamashita | Gathering two stateless mobile robots using very inaccurate compasses in finite time[END_REF]. Under the Look-Compute-Move model, many problems have been addressed, like the graph exploration and the perpetual graph exploration [START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF], while the rendezvous problem has been proved to be unsolvable on rings [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF].

Concerning the gathering, different types of robot disposals on rings (configurations) have required different approaches. In particular, periodicity and symmetry arguments have been exploited. A configuration is called periodic if it is invariable under non-trivial (i.e., non-complete) rotation. A configuration is called symmetric if the ring has a geometrical axis of symmetry, that reflects single robots into single robots, multiplicities into multiplicities, and empty nodes into empty nodes. A symmetric configuration with an axis of symmetry has an edge-edge symmetry if the axis goes through two edges; it has a node-edge symmetry if the axis goes through one node and one edge; it has a node-node symmetry if the axis goes through two nodes; it has a robot-on-axis symmetry if there is at least one node on the axis of symmetry occupied by a robot. In [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF], it is proved that the gathering is not solvable for periodic configurations, for those with edge-edge symmetry, and if the multiplicity detection capability is removed. Then all configurations with an odd number of robots, and all the asymmetric configurations with an even number of robots have been solved by different algorithms. In [START_REF] Klasing | Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring[END_REF], the attention has been devoted to the symmetric cases with an even number of robots, and the problem was solved when the number of robots is greater than [START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection[END_REF]. These left open the gatherable symmetric cases of an even number of robots between 4 and 18. Most of the cases with 4 robots have been solved in [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF]. The remaining ones, referred to as the set SP 4, are symmetric configurations of type node-edge with 4 robots and the odd interval cut by the axis bigger than the even one. They are ungatherable, in general, as outlined in [START_REF] Klasing | Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring[END_REF] for configurations of 4 robots on a five nodes ring. Actually, specific configurations in SP 4 could be gatherable but requiring suitable strategies difficult to be generalized.

Finally, the case of 6 robots with an initial axis of symmetry of type nodeedge, or node-node has been solved in [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF]. Besides the cases left open, a unified algorithm that handles all the above cases is also missing.

Other interesting gathering results on rings concern the case of the so called local weak multiplicity detection. That is, a robot is able to perceive the mul-tiplicity only if it is part of it. On this respect, our assumption in the rest of the paper concerns the global weak multiplicity detection. Whereas, the strong version would provide the exact number of robots on a node.

Using the local weak assumption, not all the cases has been addressed so far. In [START_REF] Izumi | Mobile robots gathering algorithm with local weak multiplicity in rings[END_REF], it has been proposed an algorithm for aperiodic and asymmetric configurations with the number of robots k strictly smaller than n 2 , with n being the number of nodes composing the ring. In [START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations[END_REF], the case where k is odd and strictly smaller than n -3 has been solved. In [START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection[END_REF], an algorithm for the case where n is odd, k is even, and 10 ≤ k ≤ n -5 is provided. The remaining cases are still open and a unified algorithm like the one we are proposing here for the global weak assumption is not known.

Without any multiplicity detection, in [START_REF] Angelo | Gathering of robots on anonymous grids without multiplicity detection[END_REF] the grid topology has been exhaustively studied.

Our Results. In this paper, we present a new distributed algorithm for solving all the gatherable configurations (but those potentially in SP 4) by using the (global weak) multiplicity detection. Our technique introduces a new approach and for some special cases makes use of previous ones. In particular, existing algorithms are used as subroutines for solving the basic gatherable cases with 4 or 6 robots from [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF] and [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF], respectively. Also, we exploit: Property 1. [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF] Let C be a symmetric configuration with an odd number of robots, without multiplicities. Let C ′ be the configuration resulting from C by moving the unique robot on the axis to any of its adjacent nodes. Then C ′ is either asymmetric or still symmetric but aperiodic. Moreover, by repeating this procedure a finite number of times, eventually the configuration becomes asymmetric (with possibly one multiplicity).

For all the other gatherable configurations, we design a new approach that has been suitably unified with the used subroutines. Our result answers to the posed conjectures concerning the gathering, hence closing all the cases left open, and providing a general approach that can be applied to all the initial configurations. The main result of this paper can be stated as follows.

Theorem 1. There exists a distributed algorithm for gathering k > 2 robots on a ring, provided that the composed configuration does not belong to the set SP 4, it is aperiodic, it does not admit an edge-edge axis of symmetry. The algorithm also allows robots to recognize whether a configuration is ungatherable.

Definitions and Preliminaries

We consider an n-nodes anonymous ring without orientation. Initially, k nodes of the ring are occupied by k robots. During a Look operation, a robot perceives the relative locations on the ring of multiplicities and single robots. The current configuration of the system can be described in terms of the view of a robot r. We denote a configuration seen by r as a tuple Q(r) = (q 0 , q 1 , . . . , q j ), j ≤ k -1, that represents the sequence of the numbers of free consecutive nodes broken up by robots when traversing the ring in one direction, starting from r. Abusing the notation, for any 0 ≤ i ≤ j, we refer by q i not only to the length of the i-th interval but also to the interval itself. Unless differently specified, we refer to Q(r) as the lexicographical minimum view among the two possibilities. For instance, in the configuration of Fig. 1a, we have that Q(x) = (1, 2, 1, 3, 1, 2). A multiplicity is represented as q i = -1 for some 0 ≤ i ≤ j, regardless the number of robots in the multiplicity. For instance, in the configuration of Fig. 1b,Q(x) = (1, -1, 0, 1, 0, -1, 1, 1, 3, 1). Given a generic configuration C = (q 0 , q 1 , . . . , q j ), let C = (q 0 , q j , q j-1 , . . . , q 1 ), and let C i be the configuration obtained by reading C starting from q i , that is C i = (q i , q (i+1) mod j+1 , . . . , q (i+j) mod j+1 ). The above definitions imply: Property 2. Given a configuration C, i) there exists 0 < i ≤ j such that C = C i iff C is periodic; ii) there exists 0 ≤ i ≤ j such that C = (C i ) iff C is symmetric; iii) C is aperiodic and symmetric iff there exists only one axis of symmetry.

The next definition represents the key feature for our algorithm since it has a twofold advantage. In fact, based on it, a robot can distinguish if the perceived configuration (during the Look phase) is gatherable and if it is one of the robots allowed to move (during the Compute phase). Definition 1. Given a configuration C = (q 0 , q 1 , . . . , q j ) such that q i ≥ 0, for each 0 ≤ i ≤ j, the view defined as

C SM = min{C i , (C i ), | 0 ≤ i ≤ j} is called the supermin configuration view. An interval is called supermin if it belongs to the set I C = {q i | C i = C SM or (C i ) = C SM , 0 ≤ i ≤ j}.
The next lemma, based on Definition 1, is exploited to detect possible symmetry or periodicity features of a configuration: Lemma 1. Given a configuration C = (q 0 , q 1 , . . . , q j ) with q i ≥ 0, 0 ≤ i ≤ j: 1. |I C | = 1 if and only if C is either asymmetric and aperiodic or it admits only one axis of symmetry passing through the supermin; 2. |I C | = 2 if and only if C is either aperiodic and symmetric with the axis not passing through any supermin or it is periodic with period n 2 ; 3.

|I C | > 2 if and only if C is periodic, with period at most n 3 . Proof. 1.⇒) If |I C | = 1, then if C is symmetric
, there exists at least an axis of symmetry. This axis must pass through the supermin, as otherwise there exists another interval of the same size of supermin to which the supermin is reflected with respect to the axis. However, the same should hold for every neighboring interval of the supermin and so forth. Since by hypothesis, supermin is unique, there must exist at least two intervals of different sizes that are reflected by the supposed symmetry, and hence C results asymmetric.

If C is asymmetric then it must be aperiodic, as otherwise there exists 0 < i ≤ j such that C = C i and this implies more than one copy of the supermin.

1.⇐) If C is asymmetric and aperiodic, then

C i = (C i ), C i = C ℓ and C i = (C ℓ )
, for each i and ℓ = i and hence must exist a unique supermin. If C admits only one axis of symmetry traversing the supermin, then there exists a unique 0 ≤ i ≤ j such that C SM = C i = (C i ) as otherwise Property 2 would imply the existence of other axes of symmetry, one for each supermin.

2.⇒) If |I C | = 2 and C is asymmetric, then by Property 2, it is periodic and the period must be of n 2 . If |I C | = 2 and C is aperiodic and symmetric, the axis of symmetry cannot pass through both the supermins. In fact, if it does,

C SM = (C SM ) = (C SM ) j/2 = (C SM ) j/2 that implies (C SM ) ⌊j/4⌋ = (C SM ) ⌈j/4⌉ , i.e.
, there exists another axis of symmetry orthogonal to the first one that reflects the supermin into the other supermin. Hence, C would be periodic.

2.⇐) If C is aperiodic and symmetric with the unique axis not passing through any supermin, then each supermin must be reflected by the axis to another one. Moreover, there cannot be more than 2 supermins, as by definition of supermin, these imply other axes of symmetry, i.e., by Property 2, C is periodic. If C is periodic with period n 2 , then any supermin has an exact copy after n 2 intervals, and there cannot be other supermins, as otherwise the period would be smaller.

3.⇒) If |I C | > 2,
then there are at least 3 supermins, and hence C has a period of at most n 3 . 3.⇐) If C has a period of at most n 3 , then a supermin is repeated at least 3 times in C.

A first look to the algorithm

The above lemma already provides useful information for a robot when it wakes up. In fact, during the Look operation, it can easily recognize if the configuration contains only 2 robots, or if it belongs to the set SP 4, or if |I C | > 2 (i.e., the configuration is periodic), or in case |I C | = 2, if the configuration admits an edgeedge axis of symmetry or it is again periodic. After this check, a robot knows if the configuration is gatherable, and proceeds with its computations. Indeed, we will show in the next section that all the other configurations are gatherable. From now on, we do not consider the above ungatherable configurations.

The main strategy allows only movements that affect the supermin. In fact, if there is only one supermin, and the configuration allows its reduction, the subsequent configuration would still have only one supermin (the same as before but reduced), or a multiplicity is created. In general, such a strategy would lead asymmetric configurations or also symmetric ones with the axis passing through the supermin to create one multiplicity where the gathering will be easily finalized by collecting at turn the closest robots to the multiplicity.

For gatherable configurations with |I C | = 2, our algorithm requires more phases before creating the final multiplicity where the gathering ends. In this case there are two supermins that can be reduced. If both are reduced simultaneously, then the configuration is still symmetric and gatherable. Possibly, it contains two symmetric multiplicities. In fact, this is the status that we want to reach even when only one of the two supermins is reduced. In general, the algorithm tries to preserve the original symmetry or to create a gatherable symmetric configuration from an asymmetric one. It is worth to remark that in all symmetric configurations with an even number of robots, the algorithm always allows the movement of two symmetric robots. Then it may happen that, after one move, the obtained configuration is either symmetric or it is asymmetric with a possible pending move. In fact, if only one robot among the two allowed to move performs its movement, it is possible that its symmetric one either has not yet started its Look phase, or it is taking more time. If there might be a pending move, then the algorithm forces it before any other decision.

In contrast, asymmetric configurations cannot produce pending moves as the algorithm allows the movement of only one robot. In fact, we reduce the unique supermin by deterministically distinguish among the two adjacent robots, until one multiplicity is created. Finally, all the other robots will join the multiplicity one-by-one. In some special cases, from asymmetric configurations at one "allowed" move from symmetry (i.e., with a possible pending move), robots must guess which move would have been realized from the symmetric configuration, and force it in order to avoid unexpected behaviors. By doing this correctly, the algorithm brings the configuration to have two symmetric multiplicities as above, eventually. From here, a new phase that collects all the other robots but two into the multiplicities starts. Still the configuration may move from symmetric configurations to asymmetric ones at one move from symmetry. Once the desired symmetric configuration with two multiplicities and two single robots is reached, a new phase starts and moves the two multiplicities to join each other. The node where the multiplicities join represents the final gathering location.

Gathering algorithm

The algorithm works in 5 phases that depend on the configuration perceived by the robots, see Fig. 2. First, it starts from a configuration without multiplicities and performs phase multiplicity-creation whose aim is to create one multiplicity, where all the robots will eventually gather, or a symmetric configuration with two multiplicities. In the former case, phase convergence is performed to gather all the robots into the multiplicity. In the latter case, phases collect and then multiplicity-convergence are performed in order to first collect all the robots but two into the two multiplicities and then to join the two multiplicities into a single one. After that, phase convergence is performed. Special cases of 7 nodes and 6 robots are considered separately in phase seven-nodes. Due to space constraints, we do provide the details only for the first phase multiplicity-creation. The formal descriptions of the other phases can be found in the full version of the paper [START_REF] Angelo | How to gather asynchronous oblivious robots on anonymous rings[END_REF].

We can show how robots interchange from one phase to another until the final gathering is achieved. In each phase we can distinguish the type of configuration and provide the algorithm to be performed by robots for each of these types. The way how a robot can identify the type of configuration will be outlined later.

Phase multiplicity-creation

The main idea is to reduce the supermin by enlarging the largest interval adjacent to it as follows: Definition 2. Let Q(r) = (q 0 , q 1 , . . . , q j ) be a supermin configuration view, then robot r performs the reduction if the obtained configuration after its move is (q 0 -1, q 1 , . . . , q j + 1).

The pseudo-code of reduction is shown above. The procedure, first checks whether the robot perceives the supermin configuration view by comparing the configuration C perceived by the robot with C SM . Note that, in asymmetric configurations, the robot that perceived C SM is the one among the two robots at the sides of the supermin allowed to move. In fact, the robot on the other side would perceive the configuration C and, by definition of C SM , we have C SM = C < C, as the configuration is asymmetric. Then, the procedure moves the robot towards the supermin. In symmetric configurations, the test at line 1 returns true for both robots adjacent to the unique supermin or for the two symmetric robots that perceive C SM in case that

|I C | = 2.
It is worth to note that, from a symmetric configuration, always two robots can perform the reduction when it is possible to perform it. If only one of them does it, the obtained configuration will contain exactly one supermin. However, if the perceived configuration contains only one supermin and it is not symmetric, Procedure: reduction Input : C = (q0, q1, . . . , qj)

1 if C = C SM then move towards q0;
the robots are able to understand whether there might be a pending move to reestablish the original symmetry or not. This constitutes one of the main results of the paper and it is obtained from the following lemma.

Lemma 2. Let C be a configuration with more than 2 single robots and let C ′ be the one obtained from C after a reduction performed by a single robot. If C is asymmetric then C ′ is at least at two moves from a symmetric configuration; if C is symmetric then C ′ is at least at two moves from any other symmetric configuration with an axis of symmetry different from that of C.

Proof. By Lemma 1, two cases may arise: there exists only one supermin in C or the configuration is symmetric and contains exactly two supermins.

We now show that in the case that there exists only one supermin in C, then C ′ is at least two moves from any symmetric configuration with the axis different from that passing through the supermin. By Lemma 1, it is enough to show that C ′ requires more than one move to create another supermin different from that of C. Let us consider the supermin configuration view C SM = (q 0 , q 1 , . . . , q j ). For the sake of simplicity, let us assume that, for each i = 1, 2, . . . , j, (C SM ) i < (C SM ) i , the case where, for some i, (C SM ) i > (C SM ) i is similar. The case that (C SM ) i = (C SM ) i cannot occur as, otherwise, there exists an axis of symmetry passing through q i , but, by Lemma 1, as |I C | = 1, the possible axis of symmetry can only pass through q 0 . By definition of supermin, for each (C SM ) i , i = 1, 2, . . . , j, there exists k i ∈ {0, 1, . . . , j} such that: q ℓ = q (i+ℓ) mod j+1 , for each ℓ < k i ; and q ki < q (i+ki) mod j+1 . Note that (i + k i ) mod j + 1 = 0 as otherwise it contradicts the hypothesis of minimality of q 0 . Moreover, k i = j as otherwise j ℓ=0 q ℓ = ki ℓ=0 q ℓ < ki ℓ=0 q (i+ℓ) mod j+1 = j ℓ=0 q (i+ℓ) mod j+1 , that is a contradiction. From C ′ , the supermin configuration view is C ′SM = (q ′ 0 , q ′ 1 , . . . , q ′ j ) = (q 0 -1, q 1 , . . . , q j + 1) and we have that, for each i = 1, 2, . . . , j, two cases may arise: if k i > 0, then q ′ 0 = q 0 -1 < q i = q ′ i and q ′ ki = q ki < q (i+ki) mod j+1 = q ′ (i+ki) mod j+1 ; if k i = 0, then q ′ 0 = q 0 -1 < q i -1 = q ′ i -1. In any case, C ′SM differs from (C ′SM ) i by two units. It follows that C ′ is at least two moves from any symmetric configuration with the axis different from that passing through the supermin. In fact, in order to obtain another axis of symmetry by performing only one move on C ′ , (C ′SM ) i has to differ from C ′SM by at most one unit. This is enough to show the statement for the case of symmetric configurations with exactly one supermin. Regarding the asymmetric case, it remains to show that C ′ is at least two moves from any symmetric configuration with the axis passing through the supermin. In an asymmetric configuration C SM = (q 0 , q 1 , . . . , q j ) there exists a q k , 1 ≤ k ≤ j 2 , such that q ℓ = q (j+1-ℓ) mod j+1 , for each ℓ < k, and q k < q j+1-k . From C ′ , the supermin configuration view is C ′SM = (q ′ 0 , q ′ 1 , . . . , q ′ j ) = (q 0 -1, q 1 , . . . , q j + 1) and two cases may arise: if k > 1, then q ′ 1 = q 1 = q j < q j + 1 = q ′ j and

q ′ k = q k < q j-1-k = q ′ j-1-k ; if k = 1, then q ′ 1 = q 1 < q j = q ′ j -1.
It follows that C ′ is at least two moves from any symmetric configuration with the axis passing through the supermin.

Regarding the case of symmetric configurations with exactly 2 supermins, we use similar arguments as above. Let us consider the supermin configuration view C SM = (q 0 , q 1 , . . . , q j ) and let us assume that h is the index such that C SM = (C SM ) h . By definition, for each (C SM ) i , i ∈ {1, 2, . . . , j} \ {h}, there exists k i ∈ {0, 1, . . . , j} such that: q ℓ = q (i+ℓ) mod j+1 , for each ℓ < k i , and q ki < q (i+ki) mod j+1 . As above we are assuming that (C SM ) i < (C SM ) i and we can show that k i = j, k i = (j + h) mod j + 1, (k i + i) mod j + 1 = 0, and (k i + i) mod j + 1 = h. From C ′ , the supermin configuration view is C ′SM = (q ′ 0 , q ′ 1 , . . . , q ′ j ) = (q 0 -1, q 1 , . . . , q j +1) we have that, for each i ∈ {1, 2, . . . , j}\{h} two cases may arise: if k i > 0, then q ′ 0 = q 0 -1 < q i = q ′ i and q ′ ki = q ki < q (i+ki) mod j+1 = q ′ (i+ki) mod j+1 ; if k i = 0, then q ′ 0 = q 0 -1 < q i -1 = q ′ i -1. In any case, C ′SM differs from (C ′SM ) i by two units. Similar arguments to the ones used for the asymmetric case can show that C ′ is at least two moves from any symmetric configuration with the axis passing through the supermin.

It follows that we can derive C from C ′ by enlarging the supermin of C ′ . This equals to reduce the largest adjacent interval (i.e., by performing the reduction backwards) hence deducing the possible original axis of symmetry and then performing the possible pending reduction. Before providing the designed procedures, we need the following definition: Definition 3. Given a configuration C = (q 0 , q 1 , . . . , q j ), the view defined as

C SSM = min{C i , (C i ) | C i = C SM and (C i ) = C SM , 0 ≤ i ≤ j} is called the second supermin configuration view.
As shown above, Procedure symmetric checks whether a configuration C is symmetric by exploiting Property 2. Procedure check reduction checks whether an asymmetric configuration C has been obtained from some symmetric configuration Ĉ by performing reduction. Procedure pending reduction performs the pending reduction.

At line 1, Procedure check reduction looks for the index k such that q k is the supermin, as it is the only candidate for being the interval that has Function: check reduction Input : C = (q0, q1, . . . , qj) Output : (true, Ĉ) if C is obtained from Ĉ by performing reduction, (false, ∅) if C has not been obtained by performing reduction

1 Let k such that C k = C SM or C k = C SM ; 2 if q (k-1
) mod j+1 > q (k+1) mod j+1 then Ĉ := (q0, q1, . . . , q (k-1) mod j+1 -1, q k + 1, . . . , qj);

3 else 4 if q (k-1) mod j+1 < q (k+1) mod j+1 then Ĉ := (q0, q1, . . . , q k + 1, q (k+1) mod j+1 -1, . . . , qj); been reduced by a possible reduction. Then, at lines 2-4, it computes the configuration Ĉ before the possible reduction. This is done by enlarging q k and reducing the largest interval among q (k-1) mod j+1 and q (k+1) mod j+1 . If q (k-1) mod j+1 = q (k+1) mod j+1 or Ĉ is not symmetric, then C has not been obtained by performing a reduction from a symmetric configuration. Then, the procedure returns (false, ∅). If Ĉ is symmetric, then C has been obtained by performing reduction on Ĉ and hence the procedure returns (true, Ĉ). Procedure pending reduction uses check reduction to check whether C has been obtained by performing reduction on a configuration Ĉ (lines 1 and 2). At line 2 the procedure checks whether the robot is at a side of one of the two supermins of Ĉ (min{ Ĉ, Ĉj } = ĈSM ) and if it has not yet performed reduction (min{C, C j } = C SM ). In the affirmative case, the robot has to move towards the supermin (line 2). The robot moves towards q 0 also if it is at the side of the second supermin of Ĉ (min{ Ĉ, Ĉj } = ĈSSM ). This corresponds to a move different from reduction that will be explained later in this section.

In general, it is not always possible to perform reduction. In fact, there are cases where it may lead to ungatherable configurations. These cases will be managed separately. However, we will show that a robot is always able to understand that there might be a pending move also for the other moves allowed by our algorithm from symmetric configurations.

When it is not possible to perform reduction, we either reduce the second supermin or we perform the xn move that is defined in the following: Definition 4. Let C be a configuration:

-If C is symmetric and there are no multiplicities, xn corresponds to moving towards the axis the two symmetric robots closest to the axis of symmetry that are divided by at most one robot and are not adjacent to a supermin;4 -If C is symmetric and there is only one multiplicity, xn corresponds to moving towards the multiplicity the two symmetric robots closest to the multiplicity; -If C is asymmetric and it has been possibly obtained by applying xn from a symmetric configuration C ′ (that is, from C ′ only one of the two robots on the above cases has moved), then xn on C corresponds to moving the second closest robot towards the axis/multiplicity; -If C is asymmetric with a multiplicity and it cannot be obtained by applying xn from a symmetric configuration, then xn corresponds to moving the robot lexicographically closest to the multiplicity towards it.

Each time a robot wakes up, it needs to find out which kind of configuration it is perceiving, and, if it is allowed to move, it needs to compute the right move to be performed. We need to distinguish among several types of configurations, requiring different strategies and moves. In this phase, as there are no multiplicities, a robot must distinguish among the following configurations: W1 Symmetric configurations with an odd number of robots; W2 Configurations with 4 robots; W3 Configurations with 6 robots; W4 Symmetric configurations with an even number of robots greater than 6, only 1 supermin of size 0 or with 2 supermins of size 0 divided by one interval of even size with no other intervals of size 0; W5 Symmetric configurations with an even number of robots greater than 6, only 1 supermin of size 0 or with 2 supermins of size 0 divided by one interval of even size, and other intervals of size 0; W6 Asymmetric configurations with an even number of robots greater than 6 and: a) only one interval of size 0, and it is in between two intervals of equal size; b) only two intervals of size 0, with only one in between two intervals of equal size; c) only two intervals of size 0, with one even interval in between; d) only three intervals of size 0, with only two of them separated by an even interval; e) only three consecutive intervals of size 0; f) only four intervals of size 0, with only three of them consecutive; W7 Remaining gatherable configurations.

From configurations in W1, only the robot on the axis can move in one of the two directions, arbitrarily. After this move either the configuration contains one multiplicity or it belongs to W1 or W7. Configurations in W7 will be described later in this section and the configurations with multiplicities will be described within the other phases. Regarding configurations in W1, from Property 1, we know that the number of times that the obtained configuration can belong again to W1 after this move is bounded.

When the configuration is in W2 or W3, a modified version of algorithms in [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF] and [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF] are performed, respectively. In particular, both the algorithms are able to manage symmetric configurations and to check whether in an asymmetric configuration there is a possible pending move. If the configuration is not symmetric and there are no pending moves, then reduction is performed. The resulting configuration is still in W2 or W3 or at least one multiplicity is created. From the correctness of algorithms in [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF] and [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF] and from the fact that performing reduction results in reducing the supermin, it follows that eventually at least one multiplicity is created.

When the configuration is in W7 and it is symmetric, then the algorithm performs reduction on two symmetric robots that leads to another symmetric configuration in W7, or to a configuration with at least one multiplicity, or to an asymmetric configuration with a pending move. In this latter case, by Lemma 2 the algorithm recognizes that the configuration is at one "allowed" move from symmetry and performs the pending move (even though it was not pending, indeed). When the configuration is asymmetric, again reduction is performed. By performing the described movements, at least one multiplicity is created.

Configurations in W4-W6 correspond to the cases where reduction is not allowed to be performed. In fact, if the configuration is symmetric and there is only one supermin of size 0, then reduction may result in swapping the robots at the borders of the supermin, hence obtaining infinitely many times the same configuration. Similarly, if the configuration is symmetric and there are two symmetric supermins of size 0 divided by one interval of even size, then reduction would produce two multiplicities divided by the interval of even size and we won't be able to join such multiplicities afterwards.

From W4, the algorithm performs xn, hence leading to configurations in W4, W6 or to configurations with one multiplicity on the axis.

From W5, the algorithm performs reduction on the configuration obtained without considering the supermin (that is, it reduces the second supermin, according to Definition 3). Note that, as in this case the second supermin has size 0, we obtain at least one multiplicity.

The asymmetric configurations in W6 are either asymmetric starting configurations or are obtained from the symmetric configurations in W4 after performing xn. In this cases, the algorithm checks whether the configuration is obtained after an xn move. This is realized by moving backward the robot closest to the other pole of the axis of symmetry that is assumed to pass through: The supermin in case a); The only interval of size 0 adjacent to two intervals of equal size in case b); The even intervals mentioned in cases c) and d); the only interval of size 0 in between other two intervals of size 0 in cases e) and f). If a backwards xn produces a symmetric configuration, then the symmetric xn is performed, otherwise, reduction is performed and this move creates a multiplicity. For each configuration type, the algorithm checks whether the robot perceiving the configuration C is allowed to move and eventually, performs the move.

This phase of the algorithm is summarized in Fig. 3. The next lemma states that such a phase eventually ends with at least one multiplicity and hence one of the other phases starts.

Lemma 3. Phase multiplicity-creation terminates with at least one multiplicity after a finite number of moves.

Proof. From the description provided before this lemma, it follows that the graph in Fig. 3 models the execution of phase multiplicity-creation. We now show that all the cycles are traversed a finite number of times. This implies that eventually at least one multiplicity is created.

From Property 1, and results in [START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF], and [START_REF] Angelo | Gathering of six robots on anonymous symmetric rings[END_REF] follows that the self-loops in W1, W2, and W3, respectively, are traversed a finite number of times.

The self-loop in W7 is traversed by performing reduction or pending reduction. Each time such moves are performed, the supermin decreases until, after a finite number of moves, it either creates a multiplicity or leads to configurations in W4 or W6. The number of moves is at most two times the size of the initial supermin and this is obtained for symmetric configurations with the axis not passing through the supermin.

The self-loop in W4 and the cycle between W4 and W6 are traversed by performing xn. Each time this happens, the interval between the two symmetric robots closest to the axis of symmetry (excluding those adjacent to the supermin) is reduced until creating a multiplicity on the axis. The number of moves performed equals the initial size of such an interval.

Further notes on the algorithm

We can show (see [START_REF] Angelo | How to gather asynchronous oblivious robots on anonymous rings[END_REF]) that all the types of configurations defined for the 5 phases are pairwise disjoint and that they cover all the possible configurations reachable by the algorithm.

Given a configuration C, in order to distinguish among the types, it is sufficient for a robot to compute simple parameters: number of nodes in the ring; number of multiplicities; number of robots (if possible) or number of occupied nodes; distances between robots and multiplicities; if C is symmetric; if C is at one move from the symmetries allowed by the algorithm.

The starting configuration can only belong to W1-W7. By Lemma 3, it follows that after a finite number of moves any other phase can be reached. Moreover, once reached a configuration with at least one multiplicity, the algorithm never goes back to configurations without multiplicities, but for a bounded number of times on some symmetric configurations with 6 robots.

The possible interactions among the phases are shown in Fig. 2, and we prove that all the possible cycles can be traversed a limited number of times, until reaching phase convergence without leaving it anymore.

Conclusion

The proposed algorithm answers to the posed conjectures concerning the gathering on the studied model by providing a complete characterization for the initial configurations. The obtained result is of main interest for robot-based computing systems. In fact, it closes all the cases left open with the exception of potentially gatherable configurations in SP 4. Our technique, mostly based on the supermin concept, may result as a new analytical approach for investigating related distributed problems.

Fig. 1 .

 1 Fig.1. a) The intervals between robots y, z and y ′ , z ′ are the supermins, while the supermin configuration view is (1, 2, 1, 2, 1, 3). b) Black nodes represent multiplicities.

Fig. 2 .

 2 Fig. 2. Phases interchanges.

  Function: symmetric Input : C = (q0, q1, . . . , qj) Output : true if C is symmetric, false otherwise 1 for i = 0, 1, . . . , j do 2 if C = Ci then return true; 3 return false;

5

  else return (false,∅); 6 if symmetric( Ĉ) then return (true, Ĉ); 7 return (false,∅); Procedure: pending reduction Input : C = (q0, q1, . . . , qj) 1 (b, Ĉ) = check reduction (C) ; 2 if b and ( min{ Ĉ, Ĉj} = ĈSM or min{ Ĉ, Ĉj} = ĈSSM ) and min{C, Cj} = C SM then move towards q0;

Fig. 3 .

 3 Fig. 3. Phase multiplicity-creation.

By Lemma 1, in gatherable configurations, the axis of symmetry cannot pass through two supermins hence there are always two robots allowed to move.


D ' Gianlorenzo
email: .gianlorenzo.dangelo@inria.fr

Angelo

Gabriele Di
email: gabriele.distefano@univaq.it

Ralf Klasing
email: klasing@labri.fr

Alfredo Navarra
email: alfredo.navarra@unipg.it

Gathering of Robots on Anonymous Grids without Multiplicity Detection ⋆

The paper studies the gathering problem on grid networks. A team of robots placed at different nodes of a grid, have to meet at some node and remain there. Robots operate in Look-Compute-Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move towards one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. The problem has been deeply studied for the case of ring networks. However, the known techniques used on rings cannot be directly extended to grids. Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task. That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. In this paper, we provide a full characterization about gatherable configurations for grids. In particular, we show that in this case, the multiplicity detection is not required. Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case. Moreover, our results reveal the importance of a structure like the grid that allows to overcome the multiplicity detection with respect to the ring case.

Introduction

In the field of robot based computing systems, one of the most popular problems is certainly the gathering. A pool of robots, initially situated at various locations, have to gather at the same place (not determined in advance) and remain there. Many variants of the problem have attracted the interest of numerous researchers (see e.g., [START_REF] Degener | A tight runtime bound for synchronous gathering of autonomous robots with limited visibility[END_REF][START_REF] Flocchini | Gathering of asynchronous robots with limited visibility[END_REF] and references therein). In this paper, we consider the case of anonymous grid networks where anonymous, asynchronous and oblivious robots can move according to the so-called Look-Compute-Move cycles [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF]. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, decides either to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. This means that the time between Look, Compute, and Move operations is finite but unbounded, and is decided by the adversary for each robot. Hence, robots may move based on significantly outdated perceptions. Robots are oblivious, i.e., they do not have any memory of past observations. Thus, the target node (which is either the current position of the robot or one of its neighbors) is decided by the robot during a Compute operation solely on the basis of the location of other robots perceived during the Look operation. Robots are anonymous and execute the same deterministic algorithm. They cannot leave any marks at visited nodes, nor send any messages to other robots. We remark that the Look operation provides the robots with the entire grid configuration concerning occupied nodes. That is, a robot perceives whether a node of the grid is occupied or not, but it cannot distinguish how many robots reside on an occupied node.

Related Work and Our Results. The problem of making mobile entities meet on graphs [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF][START_REF] Bampas | Almost optimal asynchronous rendezvous in infinite multidimensional grids[END_REF][START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF][START_REF] Izumi | Randomized gathering of mobile robots with local-multiplicity detection[END_REF] or open spaces [START_REF] Degener | A tight runtime bound for synchronous gathering of autonomous robots with limited visibility[END_REF][START_REF] Cord-Landwehr | A new approach for analyzing convergence algorithms for mobile robots[END_REF][START_REF] Prencipe | Impossibility of gathering by a set of autonomous mobile robots[END_REF] has been extensively studied in the last decades. When only two robots are involved, the problem is usually referred to as the rendezvous [START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF][START_REF] Alpern | The rendezvous search problem[END_REF][START_REF] Chalopin | Rendezvous of mobile agents without agreement on local orientation[END_REF][START_REF] Czyzowicz | How to meet asynchronously (almost) everywhere[END_REF].Under the Look-Compute-Move model, many problems have been addressed, like the graph exploration and the perpetual graph exploration [START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF][START_REF] Devismes | Optimal probabilistic ring exploration by semisynchronous oblivious robots[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Flocchini | Remembering without memory: Tree exploration by asynchronous oblivious robots[END_REF], while the rendezvous problem has been proven to be unfeasible on rings [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF].

Concerning the gathering under the Look-Compute-Move model, much work has been done in the last years for the ring topology. It has been proven that the gathering is unsolvable if the robots are not empowered by the so-called multiplicity detection capability [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF], either in its global/strong or local/weak version. In the former type, a robot is able to perceive whether any node of the network is occupied by a single robot or more than one (i.e., a multiplicity occurs). In the latter type, a robot is able to perceive the multiplicity only if it is part of it.

Using the global multiplicity detection, different types of configurations have required different approaches. In particular, periodicity and symmetry arguments have been exploited. In a ring, a configuration is called periodic if it is invariable under non-trivial (i.e., non-complete) rotations. A configuration is called symmetric if the ring has a geometrical axis of symmetry that reflects single robots into single robots, multiplicities into multiplicities, and empty nodes into empty nodes. In [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF], it is proven that, even with the global multiplicity detection, the gathering is unsolvable for two robots, for periodic configurations and for those symmetric configurations where the axis of symmetry passes through two edges. Then, several algorithms have been proposed for different kinds of initial configurations, in detail: for the case of odd number of robots and that of asymmetric configurations [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF], for symmetric configurations with an even number of robots greater than 18 [START_REF] Klasing | Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring[END_REF], and for 4 and 6 robots [START_REF] D'angelo | Gathering of six robots on anonymous symmetric rings[END_REF][START_REF] Koren | Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej[END_REF].

Using the local multiplicity detection in a ring, in [START_REF] Izumi | Mobile robots gathering algorithm with local weak multiplicity in rings[END_REF] it is shown that a configuration is gatherable if k < ⌊ n 2 ⌋, while in [START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations[END_REF], the case where k is odd and smaller than n -5 is studied, where n and k are the number of nodes and robots, respectively. The remaining cases are still open.

In this paper, we fully characterize the gathering on grids. We show that the multiplicity detection capability is not needed. In particular, we show that even if the global multiplicity detection is assumed, a configuration is ungatherable only if it is periodic (i.e., the same view can be obtained by rotating the grid around its geometric center of an angle smaller than 360 degrees) on a grid with at least an even side, or it is symmetric with the axis of symmetry passing through edges. For all the other cases, we provide a gathering algorithm which does not require any multiplicity detection except for configurations on 2×2 grids with three robots where the local multiplicity detection would be helpful.

To our knowledge, the grid topology is the least structured class of graphs that permits to avoid the multiplicity detection assumption. Moreover, it is worth mentioning that in our solutions many robots can move concurrently, instead of just one or two as it was for the ring case.

Definitions and Notation

We consider an anonymous and undirected grid of m × n nodes, with m ≥ n. Initially, each node is occupied by at most one robot. The total number of robots is denoted by k. During a Look operation, a robot perceives the relative locations on the grid of occupied nodes, regardless of the number of robots on a node.

The current configuration of the system can be described in terms of the view of a robot r which is performing the Look operation at the current moment. We denote a configuration seen by r as an m × n matrix M on elements in the set {0, 1}. Value 0 represents an empty node, and 1 represents an occupied node. Note that, if one node is occupied by more than one robot, it is not perceived by the robots, even if they reside on such a node. Since the grid is anonymous and undirected, each robot can perceive the current configuration with respect to different rotations and reflections leading to any view of the grid satisfying the m × n dimension. In particular, when m = n each of the 4 rotations and 4 reflections provides a feasible view. Definition 1. A configuration is periodic if it is invariant with respect to rotations of 90, 180, or 270 degrees, where the rotation point coincides with the geometric center of the grid. Definition 2. A configuration is symmetric if it is invariant after a reflection with respect to a vertical, horizontal, or diagonal (in case of square grids) axis passing through the geometric center of the grid.

Gathering algorithms

In this section, we distinguish among different cases concerning the grid structure. In particular, if the grid has both sides odd, the gathering is easily solvable.

If only one side is odd, there are some ungatherable cases. However, the impossibility results do not depend on the assumed multiplicity detection capability. If both sides are even, the gathering strategy relies on the multiplicity detection only if the input grid has size 2×2 and there are three robots, otherwise there is no need of such a capability.

Odd×odd grids

This case is trivially solvable, in fact: Theorem 1. Configurations on odd×odd grids are always gatherable.

Proof. In odd×odd grids, a robot can always detect, during its Look operation, the central node of the grid

M [⌈ m 2 ⌉, ⌈ n 2 ⌉],
regardless of its possible view. This means that all the robots can move toward the center, concurrently.

⊓ ⊔

Odd×even grids

In this case, the gathering is not always feasible. In fact, similarly to the ring case on periodic or symmetric configurations of type edge-edge [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF], we can prove:

Theorem 2. If a configuration C is periodic, or symmetric with respect to an axis passing through edges (i.e., dividing the grid into two halves from the even side), then C is ungatherable.

In what follows, we assume that the starting configuration does not belong to the ungatherable configurations specified by the above theorem. Then, we provide an algorithm achieving the gathering without multiplicity detection in all the remaining cases. The idea is to distinguish among the two nodes that are the central nodes of the odd borders of the grid. If m (n, resp.) is odd, then the two mentioned nodes are given by positions

M [1, ⌈ m 2 ⌉] and M [n, ⌈ m 2 ⌉] (M [⌈ n 2 ⌉, 1] and M [⌈ n 2 ⌉, m], resp.
). The line connecting those two nodes will be denoted as the NS line. One of the two extreme nodes on the NS line will be the place where the gathering is finalized, eventually. In order to select the gathering node, a robot considers the line passing through the central edges of the even sides of the grid (denoted as the EW line) dividing the grid into two halves. The idea is to distinguish a north and a south part among the two halves and the gathering node will be the one in the north half. The north is the half with more nodes occupied by robots, if any. If the number of occupied nodes in the two halves is the same, then some more computations are required (see next paragraph). In both cases, the robots move from the south to the north until all the robots will be in the north part. Note that, during such a stage, if multiplicities are created in the south, then the number of occupied nodes decreases with respect to the north part. If multiplicities are created in the north, it means that a robot has moved from the south to the north part, still preserving the required distinction.

In order to distinguish the north from the south in the case of configurations with the same number of robots among the two halves obtained by the EW line, a robot associates to each configuration C a binary string as follows. Starting from each corner of the grid, and proceeding in the direction parallel to the NS line, a robot records the elements of M row by row, or column by column (according to the direction specified by the NS line). Once it has computed the four strings, it associates to C the lexicographically largest one. For instance, starting from corner M [1, 1], and assuming m odd, the corresponding binary string would be composed by the sequence

M [1, 1], M [2, 1], . . ., M [n, 1], M [1, 2], . . ., M [n, 2], M [1, m], . . ., M [n, m].
Lemma 1. Let C be a gatherable configuration, then, among the four possible strings coming from a robot view of the input grid, at most two strings can be the lexicographically largest ones. If there are two largest strings, then they represent the views of C starting from two symmetric corners with respect to the NS line.

Proof. If the equal strings correspond to the view of C starting from two symmetric corners with respect to the EW line, then C would be symmetric with respect to the EW line. In fact, from Definition 2, this would correspond to a reflection of the grid with respect to the EW line. But, from Theorem 2, it would imply that C is ungatherable. If the equal strings correspond to the view of C starting from two corners residing on one of the two diagonals of the grid, then C would be periodic. In fact, from Definition 1, this would correspond to a rotation of the grid of 180 degrees, again despite C being gatherable. Then, no more than two strings can be equal as otherwise one of the above situations would occur. It follows that either the four strings are all different among themselves, or there are two pairs of equal strings, one of which corresponds to the lexicographically largest ones. Moreover, both correspond to the view of C starting from two symmetric corners with respect to the NS line.

⊓ ⊔

From the above lemma, we define the gathering node as the one residing on the same odd side where the corner(s) providing the lexicographically largest string resides. Moreover, the gathering node will determine also the directions along the NS line: We say that the gathering node resides on the north pole. Theorem 3. Configurations on odd×even grids that are aperiodic and do not admit an axis of symmetry passing through edges are always gatherable.

Proof. Once the gathering node has been unambiguously identified by a robot during its Compute operation, if the robot resides on the half grid where the south pole is, with respect to the EW line, then it moves towards the north. Note that, each time a robot in the southern half of the grid performs such a movement, the gathering node cannot change. In fact, two cases can occur: 1) the number of occupied nodes decreases in the southern part of the grid, either because a robot moves to the northern part or because a multiplicity is created; 2) the string associated to the corners in the south are decreasing due to the robots' movements, and hence the corresponding strings defining the current configuration starting from the northern corners are increasing. This clearly leaves unchanged the direction on the NS line. Note that the corner to which the lexicographically largest string was associated might change during the described process but the only option is the other corner on the same odd side of the original one, hence preserving the direction on the NS line. By keeping on moving in the described way, all the robots will reach the northern part, eventually. The case in which a subset of robots from a multiplicity move, increasing the number of occupied nodes, does not require any special treatment. In fact, since the initial configuration does not contain multiplicities, either the minimality of the number of robots in one half of the grid is preserved, or case 2) still ensures that the lexicographically largest string is associated to a corner in the north.

Once all the robots belong to one half of the grid, then they are allowed to move, during their Move operation, towards the gathering node. In fact, such a node is now well-defined and cannot change as the robots are not allowed to move to the other half of the grid. ⊓ ⊔

Even×even grids

In this section, we study the case of grids whose sides are both even. Also in this case, by Theorem 2, there are some configurations which are ungatherable, namely the periodic configurations and those configurations having a vertical or a horizontal axis of symmetry. We show that all the other cases are gatherable without any multiplicity detection, but for the case of 2×2 grids.

Theorem 4. Let us consider a 2×2 grid with more than one node occupied. If the multiplicity detection is not allowed, then any configuration is ungatherable.

If the local multiplicity detection is allowed, a configuration is gatherable if and only if it has three nodes occupied.

Proof. Clearly, a 2×2 grid equals a ring of dimension four. Hence, any ungatherable configuration on a ring of four nodes is ungatherable on a 2×2 grid. In particular, configurations with two or four nodes occupied are ungatherable even with the global multiplicity detection and configurations with three nodes occupied are ungatherable if the multiplicity detection is not allowed [START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF]. Finally, we show that a configuration is gatherable with the local multiplicity detection if three nodes are occupied. Consider the following algorithm: 1. move the robot in between the other two occupied nodes arbitrarily; 2. move the robot not in the multiplicity towards the other occupied node. ⊓ ⊔ Hence, the remaining gatherable configurations are the aperiodic, asymmetric, and those with only one axis of symmetry passing through the diagonal of a square grid of dimensions larger than 2×2. We refer to all such configurations as the set EG (Even-Gatherable). In Theorem 5, we will show that all the configurations in EG are indeed gatherable without any multiplicity detection.

In the following, we first assume that at least one node on the border of the grid is occupied. Then, in the proof of Theorem 5, we will show how to extend the given strategies to the general case. First, we give some definitions about the "reading" of grid configurations needed for the subsequent proofs. Let us consider the eight sequences of distances (number of empty nodes) between occupied nodes obtained by traversing the grid starting from the four corners and proceeding towards the two possible directions (see, e.g. Fig. 1). Note that the two sequences associated to a corner occupied by some robot starts with 0. We associate for each corner the lexicographically smallest sequence between the two readings from such corner. Note that, in square grids such two sequences are always different, but for the two corners through which passes the possible of symmetry. In rectangular grids, these two sequences can be equal but we can distinguish one of them by assuming that if two sequences are equal, the one read in the direction of the smallest side is smaller than the other.

We define the minimal sequence as follows. If the configuration is symmetric, it is the smallest sequence between the two sequences associated to the two corners through which passes the axis of symmetry, otherwise it is the smallest among the four sequences associated to the four corners. Note that, under the assumption that the configuration does not fall into the hypothesis of Theorem 2, in any case there exists a minimal sequence which identifies a single corner, unambiguously. We denote the minimal sequence as C = (q 0 , q 1 , . . . , q j ) and by c the corner which it is associated to.

An important property of our gathering strategy that we are going to present is: In all the movements used in the following results we do not allow a robot to move into a corner different from c. Lemma 2. For any EG configuration with no corners occupied and at least one robot on the border there exists a strategy that leads to a configuration with exactly one corner occupied.

Proof. If there are no corners occupied, the idea is to reduce q 0 by moving towards c the robot (or the two robots, when the configuration is symmetric) on the border which is (are) closest to c. Note that, as we are assuming that there is at least a node on the border and that C is the minimal sequence, the robot (robots) involved in the movement towards c is (are) on the border.

In the case of symmetric configurations, we aim to move towards c the two symmetric robots on the border which are the closest ones to c. Let us denote these two robots by r and r ′ . First of all, we prove that if only one robot moves (let us assume r), no symmetric configuration can be created and, moreover, there exists only one robot (r ′ ) at one allowed move from a symmetric configuration. We prove this by showing that contradicting such statement would imply that, in the initial configuration, the sequence associated to the corner on the axis different from c starts with q 0 -1 (see Fig. 2), which is a contradiction with respect to the minimality of C. Moving robot r may create three potential axes of symmetry which are, with respect to the drawing of Fig. 2: a vertical, horizontal, or diagonal axis different from the original one. Let us assume that there exists a vertical axis of symmetry (see Fig. 2c). In this case the presence of the vertical axis of symmetry and of robot r at distance q 0 -1 from c, implies the presence of robot r 1 of Fig. 2c which is specular to r with respect to the vertical axis of symmetry. Note that, in this case, q 0 -1 < n 2 as otherwise r 1 would be closer to c than r, a contradiction. Therefore, r 1 is at distance q 0 -1 from the upper left corner of Fig. 2c. Now, since this robot did not move, the original diagonal axis of symmetry implies the presence of a robot r 2 at distance q 0 -1 from the lower right corner of Fig. 2c. Again, the two axes imply the presence of robots r 3 and r 4 , both at distance q 0 -1 from the corner opposite to c, a contradiction to the minimality of C. The case of horizontal axis of symmetry is similar and it is shown in Fig. 2d. Let us now assume that there exists a diagonal axis of symmetry different from the original one (see Fig. 2e). Such axis implies the presence of robot r 1 at distance q 0 -1 from the corner opposite to c. Moreover, the original axis implies the presence of robot r 2 at distance q 0 -1 from the corner opposite to c. Again, this is a contradiction to the minimality of C. Similar arguments can be used to show that there cannot exist other robots besides r ′ at one allowed move from a symmetric configuration. Hence, in the case of symmetric configurations, or asymmetric configurations at one allowed move from symmetry, the strategy leads to the occupation of c, possibly with a pending move towards c.

a) c q 0 r r ′ q 0 b) q 0 r q 0 -1 c r c) c q 0 r ′ q 0 -1 q 0 -1 r 3 r q 0 -1 r 1 q 0 -1 r 4 r 2 q 0 -1 d) c q0 q 0 -1 q 0 -1 r 3 q 0 -1 r 2 q 0 -1 q 0 -1 r ′ r r 1 r 4 e) c q 0 r ′ r q 0 -1 q 0 -1 r 1 q 0 -1 r 2
In the case of asymmetric configurations, first of all the robots check whether the configuration is at one step from a symmetric configuration belonging to EG that can be obtained by the move performed by a robot (potentially corresponding to r ′ ) on the border towards the corner c that would be obtained when the axis of symmetry occurs. We recall that, in the case of symmetric configurations, c is defined as the corner whose associated sequence is the smallest one among the two corners lying on the axis of symmetry and not among all the corners. If such a symmetry cannot be established, then c corresponds to the minimal sequence and the algorithm proceeds by reducing q 0 until it becomes 0, that is, c is occupied. In fact, if the initial configuration is asymmetric and q 0 > 1, then after reducing q 0 , the obtained configuration is again asymmetric as the minimal sequence of the new configuration starts with 0 -1 while any other sequence starts with at least q 0 . When the initial configuration is asymmetric and q 0 = 1, after the move, the configuration might become symmetric but with one corner occupied. In conclusion, in any case the obtained configuration has the corner c occupied, and possibly one pending move towards c.

⊓ ⊔

Before showing the case of configurations in EG with two corners occupied, we need to exclude all the configurations with exactly three occupied nodes, two of which are two corners that share a coordinate, and the other one is at one node apart from another corner. See the configuration in the middle of Fig. 3. We denote such configurations as the set 3EG2. Lemma 3. For any configuration in EG\3EG2 with two corners occupied there exists a strategy that leads to a configuration with either exactly one corner occupied or exactly three corners occupied.

Proof. If two corners are occupied, and the configuration is symmetric with the axis passing through the occupied corners, then one of them corresponds to c. We move the robot in the occupied corner which does not corresponds to c towards the other one, and we end up with the case of only one corner occupied.

The case where two corners are occupied, and the configuration is asymmetric or symmetric with the axis not passing through the occupied corners requires some more effort. In this case, it is risky to move the robots from the occupied corners, since if the adversary forces to move only one of them, we could not be able to recognize the possible move of the other robot which is still pending. Therefore, let d be the corner not occupied by a robot from which we read the minimal sequence D. We move towards d the first robot not in a corner that reduces D, and possibly, the symmetric one. 5 By repeating this strategy, d will be occupied by at least one robot, eventually. Arguments similar to those used in the proof of Lemma 2 can be used to show that no symmetries different from the original one can be created. It follows that for each step in which this strategy is applied, d remains the same. The final configuration has three corners occupied and possibly one pending move towards d of a robot not in a corner.

⊓ ⊔ Note that the configuration obtained after the strategy given in Lemma 3 is always in EG with possibly one pending move.

Theorem 5. Aperiodic configurations on even×even grids larger than 2×2, that do not admit an axis of symmetry passing through edges, are gatherable.

Proof. First, we can restrict the set of possible grids as follows. Let us consider the minimal even×even sub-grid which is centered in the geometrical middle of the original grid and includes all the occupied nodes of it. Such minimal wrapping grid is still of type even×even and preserves the possible symmetry of the original one. Moreover, it always has at least an occupied node on the border. Our algorithm only uses such sub-grids and it never changes the size of it, i.e. it neither enlarges it by moving robots outside of it, nor it reduces it by moving the robots on the border inside. Therefore, in what follows, we can assume without loss of generality that a grid always has at least an occupied node in the border. However, the case in which the resulting wrapping grid is a 2×2 grid will be considered separately.

If no corners are occupied, we can apply Lemma 2 that leads to a configuration with one corner occupied with possibly one pending move towards c. However, such a move would have been performed also in the strategy used for the case of one corner occupied which is given in the following.

If only one corner is occupied, then it corresponds to c. In this case, all the robots move towards c by reducing the Manhattan distance to c and then achieving the gathering. We remind that the allowed movements are performed always without occupying any other corner than c.

In case two corners are occupied but the configuration is not in 3EG2, we apply the strategy of Lemma 3 and reach a configuration with one or three corners occupied. Also in this case there could be a pending move and, again, such a move would have been performed also in the strategy for one corner or three corners occupied.

If three corners are occupied, we move all the robots, but those in the corners, towards the corner that does not share any coordinate with the empty corner. This process finishes with a symmetric configuration with exactly three corners occupied. In this configuration, c is the corner on the axis of symmetry, and the other two robots move one step towards c either concurrently or alternately, until creating a configuration with only one corner occupied as shown in Fig. 3. Note that these final steps also solve the gathering for the configurations in 3EG2.

If four corners are occupied, we move the robot which occupies the corner farthest from c in an arbitrary direction, generating a configuration where only three corners are occupied.

It remains the case where the minimal wrapping even×even sub-grid which includes all the occupied nodes of the original grid has dimension 2×2. As shown in Theorem 4, the configuration is not gatherable on this sub-grid without multiplicity detection. However, in the case of exactly three nodes occupied, we can exploit the larger dimensions of the original grid in order to avoid the multiplicity detection. The cases of two or four nodes occupied clearly remain not gatherable. The strategy is then to move the robot on the corner of the 2×2 grid which is in between the other two occupied corners towards the external row or column, arbitrarily. In doing so, we obtain the case where the minimal wrapping grid has dimension 4×4 and no corners are occupied.

⊓ ⊔

Conclusion

We fully characterized the gathering in the Look-Compute-Move model on grids.

We have shown that a configuration is ungatherable if and only if it is periodic on a grid with at least an even side, or it is symmetric with the axis passing through edges, or it is a 2×2 grid. For all the other cases we provided a gathering algorithm which does not require any multiplicity detection. It would be of interest to investigate whether the grid topology is the least structured class of graphs that permits to avoid the multiplicity detection assumption.

  Fig.1. Case of a 10 × 6 grid. The arrows indicate the horizontal direction of the reading from corner c1, it gives[START_REF] Izumi | Randomized gathering of mobile robots with local-multiplicity detection[END_REF][START_REF] Prencipe | Impossibility of gathering by a set of autonomous mobile robots[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Chalopin | Rendezvous of mobile agents without agreement on local orientation[END_REF][START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF][START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF]. The other seven sequences read by the robots are: (3, 6, 20, 4, 9, 13) from c1 vertically, (3, 10, 24, 2, 5, 11) and (16, 1, 6, 26, 4, 2) from c2 horizontally and vertically, resp.,[START_REF] Blin | Exclusive perpetual ring exploration without chirality[END_REF][START_REF] Dessmark | Deterministic rendezvous in graphs[END_REF][START_REF] Chalopin | Rendezvous of mobile agents without agreement on local orientation[END_REF][START_REF] Flocchini | Computing without communicating: Ring exploration by asynchronous oblivious robots[END_REF][START_REF] Prencipe | Impossibility of gathering by a set of autonomous mobile robots[END_REF][START_REF] Izumi | Randomized gathering of mobile robots with local-multiplicity detection[END_REF] and[START_REF] Devismes | Optimal probabilistic ring exploration by semisynchronous oblivious robots[END_REF][START_REF] Alpern | The rendezvous search problem[END_REF][START_REF] Bampas | Almost optimal asynchronous rendezvous in infinite multidimensional grids[END_REF][START_REF] Kamei | Asynchronous mobile robot gathering from symmetric configurations[END_REF][START_REF] Izumi | Randomized gathering of mobile robots with local-multiplicity detection[END_REF][START_REF] Klasing | Gathering asynchronous oblivious mobile robots in a ring[END_REF] from c3, (11, 5, 2, 24, 10, 3) and (2, 4, 26, 6, 1, 16) from c4. The minimal sequence is[START_REF] Flocchini | Gathering of asynchronous robots with limited visibility[END_REF][START_REF] Bampas | Almost optimal asynchronous rendezvous in infinite multidimensional grids[END_REF] 26,[START_REF] Izumi | Randomized gathering of mobile robots with local-multiplicity detection[END_REF][START_REF] Degener | A tight runtime bound for synchronous gathering of autonomous robots with limited visibility[END_REF][START_REF] Klasing | Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring[END_REF]) and c = c4.

Fig. 2 .

 2 Fig. 2. Symmetric square grid with no corners occupied. Dashed lines represent axes of symmetry. a) original configuration; b) configuration once only robot r has moved; c) configuration with a possible vertical axis; d) configuration with a possible horizontal axis; e) configuration with a possible diagonal axis different from the original one.

Fig. 3 .

 3 Fig.3. Strategy from a symmetric square grid where exactly three corners are occupied and all the other nodes are empty to a configuration with only one occupied corner, possibly passing through configurations in 3EG2.

  1. Case of a 10 × 6 grid. The arrows indicate the horizontal direction of the read-

	ing from corner c1, it gives (6, 8, 14, 10, 5, 12). The other seven sequences read by the
	robots are: (3, 6, 20, 4, 9, 13) from c1 vertically, (3, 10, 24, 2, 5, 11) and (16, 1, 6, 26, 4, 2)
	from c2 horizontally and vertically, resp., (12, 5, 10, 14, 8, 6) and (13, 9, 4, 20, 6, 3) from c3, (11, 5, 2, 24, 10, 3) and (2, 4, 26, 6, 1, 16) from c4. The minimal sequence is
	(2, 4, 26, 6, 1, 16) and c = c4.

Here we do not need to preserve the symmetry as it was necessary in Lemma 2.

⋆ Research supported by the LaBRI under the "Project émergent" program.