We consider the coordination of autonomous mobile robots operating in the standard Look{Compute{Move cycles. Robots are assumed to be very weak computational units, since they are asynchronous, oblivious, anonymous, silent and execute the same distributed algorithm. In this area, the main focus has been on the important class of Pattern Formation problems, where the robots are required to arrange themselves to form a given geometric shape. This class of problems has been extensively studied in the Euclidean plane, whereas few results exist when robots move on a discretization of the plane, like in nite grids. In in nite grids, in order to form any pattern, the problem of breaking symmetries clearly emerges. Breaking the symmetry by moving some leader robot is not a straightforward task due to the movement restrictions as all the adjacent nodes of the leader may be occupied. Due to the asynchrony of robots, this fact greatly increases the di culty of the problem. We assume regular tessellation graphs as discretization of the Euclidean plane, and we devise an algorithm able to solve the Symmetry Breaking problem on both the square and triangular grids. The algorithm is proposed so that it can be also combined with other modules.
The coordination of autonomous mobile robots has long been object of study in several elds, including robotics, control, AI, as well as distributed computing. Within distributed computing, in particular, extensive research e orts have been conducted in the last two decades to investigate the computational and complexity issues arising in distributed systems composed of a team of mobile computational entities moving and operating in a Euclidean space (e.g., see [24]).
These entities, called robots, are autonomous (no centralized control), anonymous (they are identical in their external appearance, no unique identi ers), homogeneous (have the same capabilities and execute the same algorithm), silent (they have no explicit means of direct communication), and disoriented (no common coordinate system, no common left-right orientation). Each robot in the system has sensory capabilities allowing it to determine the location of other ? Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). robots in the environment, relative to its own location (each robot refers in fact to a local coordinate system that might be di erent from robot to robot). Each robot, when active, operates in Look-Compute-Move cycles: it determines the positions of the robots in the system (Look); this information is used to compute a destination point (Compute); the robot then moves towards the computed destination (Move); after the execution of a cycle, the robot may become temporarily inactive. Furthermore, the entities are oblivious : at the beginning of a cycle the robot has no recollection of computations and operations performed in previous cycles; that is, there is no persistent memory. This computational model is called oblot and it is a standard de-facto in the context of distributed computing by mobile entities [24]. In this model, the research e ort has been on determining which problems can be solved by a swarm of such robots. Crucial for the solvability of a problem is the activation schedule of robots and the duration of their activities in each cycle. We consider the asynchronous setting (Async), where robots do not have a common notion of time (which is possibly continuous), and the times when each robot is activated as well as the duration of each activity is decided by an adversary for each cycle.
Concerning the coordination of autonomous mobile robots, the main focus has been on the important class of Pattern Formation problems, where the robots are required to arrange themselves to form a given geometric shape (e.g., [17, 20, 22, 29, 30]). The Arbitrary Pattern Formation is a speci c version that asks to determine from which initial con gurations it is possible to form any speci c but arbitrary geometric pattern given as input (e.g., [4, 9, 23]). In [11, 25], the so-called Embedded Pattern Formation problem was studied where the pattern to be formed is provided as a set of visible points in the plane. The general class includes also the Gathering problem requiring the robots to move to the same location, not decided in advance. This problem is of particular importance and has been extensively studied. It has been fully characterized in [15] (for a recent survey, see [21] and references therein). A slightly di erent model imposing robots to gather at some visible and predetermined points provided in the Euclidean plane has been also investigated and fully characterized, see [5{7].
In the continuous setting, the robots are assumed to be able to execute accurate movements in any direction and by any amount, even by in nitesimally small amounts. Hence, even in densely crowded situations, punctiform robots can maneuver avoiding collisions. Certain models also permit the robots to move along curved trajectories, in particular, the circumference of a circle. The correctness of the algorithms relies on the accurate execution of the movements. However, for robots with weak mechanical capabilities, it may not be possible to execute such intricate movements with precision. This motivates to consider robots moving in a grid-based terrain where the movements are restricted only along grid lines and only to a neighboring grid point in each step. Grid type oor layouts can be easily implemented in real-life robot navigation systems. From an algorithmic perspective, the restrictions imposed by model on the movements make it harder to solve problems that resulted to be easy in the continuous environment. In the grid environment, the most investigated types of formation problems are the Gathering problem [18] and Mutual Visibility problem [1], where a set of opaque robots have to form a pattern in which no three robots are collinear. The gathering problem has been investigated also in other speci c graph topologies like trees [19], rings [16, 8], regular bipartite graphs [27], hypercubes [3], complete and complete bipartite [12, 13]. For a recent survey, see [10] and references therein. Few results concerning the general pattern formation problem on grids exist. Recently, the Arbitrary Pattern Formation for a set of oblivious asynchronous robots on the in nite grid in absence of any global coordinate system was rst considered in [2]. Authors have shown that if the initial con guration is asymmetric, then the Arbitrary Pattern Formation problem is deterministically solvable by Async robots starting from asymmetric con gurations. They poses as an open problem that of investigating about what can be achieved from symmetric con gurations. This leads to the problem addressed in this work: how to break symmetries on grid based environments so that robots can later form any requested geometric pattern.
Our contribution. We extend the concept of discretization of the Euclidean plane by considering regular tessellation graphs, that is square, triangular, and hexagonal grids. We assume very weak robots moving in this environment: they are asynchronous, oblivious, anonymous, silent, and fully disoriented. In this context, we consider the so-called leader con gurations, that is the symmetric con gurations in which it is possible to elect a leader and, as a consequence, it is possible to break the symmetry. However, breaking the symmetry by moving a leader robot is not a straightforward task due to the movement restrictions as all the adjacent nodes of the leader may be occupied. It may even happen that before obtaining the requested asymmetric con guration, most of the robots must be moved. Due to the asynchrony of robots, this fact greatly increases the di culty of breaking the symmetry. We devise an algorithm called Abreak able to solve the Symmetry Breaking problem on both the square and triangular grids. The algorithm is proposed so that it can be also combined with other modules (e.g., modules that are able to form some kind of pattern starting from any asymmetric con guration). 2
We denote by R = fr1; r2; : : : ; rng the set of robots forming the swarm under consideration.1 The topology where robots are placed on is represented by a simple, undirected, and connected graph G = (V; E), with vertex set V and edge set E. Given a function : R ! V that maps each robot to the vertex in G where the robot is placed, we call C = (G; R; ) a con guration. A vertex v 2 V is said occupied if there exists r 2 R such that (r) = v, unoccupied otherwise. A multiplicity occurs in any vertex v 2 V whenever there is more than one robot occupying v (i.e., when is not injective). With mul (v) we denote the 1 We recall that robots are anonymous and such a notation is used only for the sake of presentation, hence no algorithm can take advantage of names of elements in R. multiplicity in v, that is the number of robots occupying v. As usual, N (v) represents the set containing all the neighbors of the vertex v, that is all vertices adjacent to v; concerning robots, N (r) contains all the robots \adjacent" to r, that is N (r) = fr0 2 R : (r0) 2 N ( (r))g. In our algorithm, in some cases, a robot is moved only when N (r) = ;: accordingly, a robot r is said blocked if N (r) 6= ;, unblocked otherwise.
Movements of robots and execution of an algorithm. The movement of the robots are restricted along the edges of the graph representing the environment in which robots operate, from one vertex to one of its neighboring vertices. Traditionally in discrete domains, robot movements are assumed to be instantaneous. This results in always perceiving robots on vertices and never on edges during Look phases. Hence, robots cannot be seen while moving, but only at the moment they may start moving or when they arrived.
In the Async scheduler, the activations of the robots determine speci cally
ordered time instants. Let C(t) be the con guration observed by some robots
at time t during their Look phase, and let fti : i = 0; 1; : : :g, with ti < ti+1,
be the set of all time instances at which at least one robot takes the snapshot
C(ti). Since the information relevant for the computing phase of each robot is
the order in which the di erent snapshots occur and not the exact time in which
each snapshots is taken, without loss of generality we can assume ti = i for all
i = 0; 1; : : :. Then, an execution of an algorithm A from an initial con guration C
is a sequence of con gurations E : C(0); C(
Initially robots are inactive, but once the execution of any algorithm A starts there is no instruction to stop it, i.e., to prevent robots to enter their LCM cycles. Then, the termination property for A can be stated as follows: once robots have reached the required goal by means of A, from there on robots can perform only the nil movement.
Con gurations on tessellation graphs. In this work, we consider G as an in nite graph generated by a plane tessellation. A tessellation is a tiling of a plane with polygons without overlapping. A regular tessellation is a tessellation which is formed by just one kind of regular polygons of side length 1 and in which the corners of polygons are identically arranged. According to [26], there are only three regular tessellations, and they are generated by squares, equilateral triangles or regular hexagons (see Fig. 1). An in nite lattice of a regular tessellation is a lattice formed by taking the vertices of the regular polygons in the tessellation as the points of the lattice. A graph G is induced by the point set S if the vertices of G are the points in S and its edges connect vertices that are distance 1 apart. A tessellation graph of a regular tessellation is the in nite graph embedded into the Euclidean plane induced by the in nite lattice formed by that tessellation [28]. We denote by GS (GT and GH , resp.) the tessellation graphs induced by the regular tessellations generated by squares (equilateral triangles and regular hexagons, resp.). In this work we consider con gurations C = (G; R; ) where G 2 fGS ; GT ; GH g.
Concerning any graph G 2 fGS ; GT ; GH g, it follows from the de nition that G is regular, and hence by deg (G) we denote the degree of each vertex. Notice that deg (G) equals three, four, and six in GH , GS , and GT , respectively. Any line parallel to an edge of G is called a canonical line, and the smallest angle formed by the available canonical lines is called the canonical angle. According to this notation, in GS all the canonical lines have just two orientations and the canonical angle is of 90 . In both GT and GH all the canonical lines have three orientations and the canonical angle is of 60 . In the rest of the paper, given any tessellation graph G, by hline we mean any half-line starting from a vertex and coincident with any canonical line.
Con guration automorphisms and symmetries. Two undirected graphs G = (V; E) and G0 = (V 0; E0) are isomorphic if there is a bijection ' from V to V 0 such that fu; vg 2 E if and only if f'(u); '(v)g 2 E0. An automorphism on a graph G is an isomorphism from G to itself, that is a permutation of the vertices of G that maps edges to edges and non-edges to non-edges. The set of all automorphisms of G, under the composition operation, forms a group called automorphism group of G and denoted by Aut(G). If jAut(G)j = 1, that is G admits only the identity automorphism, then G is said asymmetric, otherwise it is said symmetric. Two distinct vertices u; v 2 V are equivalent if there exists an automorphism ' 2 Aut(G) such that '(u) = v.
The concept of graph isomorphism can be extended to con gurations in a natural way. Two con gurations C = (G; R; ) and C0 = (G0; R0; 0) are isomorphic if there exists an isomorphism ' between G and G0 that can be extended to obtain a bijection from R to R0 such that two robots can be associated by ' only if they reside on equivalent vertices. Formally, if '(r) = r0 then '( (r)) = 0(r0). In this way, analogously to the case of graph automorphism, an automorphism of a con guration C = (G; R; ) is an isomorphism from C to itself, and the set of all automorphisms of C forms a group under the composition operation that we call automorphism group of C and denote as Aut(C). Moreover, if jAut(C)j = 1 we say that C is asymmetric, otherwise it is symmetric. Two distinct robots r and r0 in a con guration (G; ) are equivalent if there exists ' 2 Aut(C) such that '(r) = r0. Notice that, according to the de nition, distinct robots in the same multiplicity are equivalent and hence each con guration with a multiplicity is symmetric. Also, note that mul (u) = mul (v) whenever u and v are equivalent.
It can be observed that if r and r0 are equivalent robots, no algorithm can distinguish between them. Hence, no algorithm can avoid the two equivalent Async robots start the computational cycle simultaneously at a certain time t0. In such a case, there might be a so-called pending move (or pending robot ), that is one of the two robots performs its entire computational cycle while the other has not started or not yet nished its Move phase. Formally, a robot r is pending in a con guration C(t), if at time t robot r is active, has taken a snapshot C(t0) 6= C(t) with t0 < t, and is planning to move or is moving with a non-nil trajectory. Clearly, any other robot r0 that takes the snapshot C(t) is not aware whether there is a pending robot r, that is it cannot deduce such a piece of information from the snapshot acquired in the Look phase. This fact greatly increases the di culty to devise algorithms for Async robots, and this holds in particular in symmetric con gurations, where pending moves can be easily generated by the adversary. It follows that each time a formal and sound proof of the correctness of the algorithm must be provided, each algorithm must ensure to solve a general task by providing a stationary con guration: a con guration C(t) is called stationary if there are no pending robots in C(t).
Leader con gurations and the Symmetry Breaking problem. Concerning the con gurations addressed in this work, it is not di cult to see that any C = (G; R; ), with G 2 fGS ; GT ; GH g, admits two types of automorphisms only: re ections, de ned by a re ection axis which acts as a mirror; rotations, de ned by a center and an angle of rotation. A con guration admitting only one re ection axis is called re ective, and a con guration admitting any rotation is called rotational. Notice that a con guration with two or more re ection axes is rotational.
It is well-known (e.g., see [31]) that no algorithm can break a symmetry
among a group of two or more pairwise equivalent robots if it acts on that
group only, even in the synchronous setting. In fact, since the algorithm cannot
distinguish between them, any strategy de ned by the algorithm will be applied
by the adversary to all the considered robots. As a nal result, the moved robots
will remain symmetric in any possible obtained con guration. This implies that
it is worth to address the problem of designing symmetry breaking algorithms
only for special cases of symmetric con gurations, as de ned in the following.
De nition 1 (leader-con guration). A con guration C = (G; R; ), with
G 2 fGS ; GT ; GH g, is a leader con guration if one of the following cases holds:
(
De nition 2 (initial-con guration). A con guration C = (G; R; ), with
G 2 fGS ; GT ; GH g, is an initial con guration if both the following conditions
hold: (
Abreak Here we introduce some concepts and notation used in the proposed algorithm Abreak . They refer to any con guration C = (G; R; ), with G 2 fGS ; GT g. Bounding parallelogram. We introduce the concept of bounding parallelogram bp(R), de ned as any parallelogram enclosing all robots, with sides parallel to two of the available grid line orientations, and with each pair of parallel sides as close together as possible. Since GT or GH admit canonical lines along three orientations, it can be observed that the bounding parallelogram of R is not unique on such topologies. In fact, there are up to three possible bounding rectangles (e.g., see Fig. 2). On GS , bp(R) is unique and corresponds to the well-known concept of minimum bounding rectangle. We denote by h(bp(R)) and w (bp(R)) the width and height of any bp(R), respectively. Without loss of generality, we assume h(bp(R)) w (bp(R)).
Binary strings associated to a con guration. Any algorithm addressing the SB problem needs to elect a leader among the robots in any initial con guration. If C is rotational, such a leader can be naturally identi ed with the robot occupying the center of rotation. Less obvious is how to identify a speci c robot in re ective con gurations. To this aim, in the following, we associate a binary string to any con guration so that from that string it is possible to elect a leader also in the case of initial re ective con gurations.
Given any bp(R), we associate a binary string to each canonical corner of bp(R) (a canonical corner is a corner of the parallelogram that forms a canonical angle, e.g., corners A and C in Fig. 2). The string associated with a canonical corner A is de ned as follows. Scan the nite tessellation enclosed by bp(R) from A along h(bp(R)) (say, from A to B) and sequentially all canonical lines parallel to AB in the same direction. For each vertex v, put a 0 or 1 according to whether it is empty or occupied. Denote the obtained string as s(AB). Being h(bp(R)) = w(bp(R)) in the example, from A it is also possible to obtain the string s(AD), and hence four strings can be de ned in total, two for the corner A and two for the corner C. Notice that if any two of these strings are equal, then the con guration is re ective or rotational.
De nition 3 (LSS (R)). Let C = (G; R; ) be a con guration, with G 2 fGS ; GT g, and let S be the set containing all the binary strings associated to each canonical corner of bp(R), for each bp(R) with minimum height and, in case of ties, with minimum width. LSS (R) denotes the lexicographically smallest string in S. It follows from the de nition that LSS (R) is unique, even when it is computed on symmetric con gurations, where multiple bp(R)'s must be considered (cf. Fig. 2). By using LSS (R), it is now possible to elect a leader, called pivot, in any initial re ective con guration C = (G; R; ): the pivot is the median robot on the re ection axis of C (in case of ties, i.e. when the number of robots on the axis is even, the pivot is the median robot having the smallest position in LSS (R)). Concerning the example in Fig. 2, the represented con guration is re ective with two robots on the axis of re ection, the pivot is the robot denoted as r since its position in LSS (R) is 8 whereas the position of the other is 10.
Strings generated from a robot. Given a robot r, the strings generated from r are the binary strings obtained in three steps, in order, as follows: 1. scan a hline that starts from the vertex v = (r) and stop when the last occupied vertex is reached: for each encountered vertex (v excluded) put 0 or 1 according to whether it is empty or occupied; if no occupied vertices are encountered, the empty string is returned; 2. repeat the previous step for each hline starting from the vertex v = (r), and insert all the obtained strings into a multiset S(r) - let be the length of the longest string in S(r); 3. modify each string in S(r) by adding to the right of each string as many 0's as necessary to make the length of each string equal to + 1.
Concerning con guration C2 in Fig. 3, S(r) contains six strings, three equal to 110 and three equal to 010. Elements in S(r) are considered again as lexicographically ordered.
De nition 4. Let S be a multiset containing some strings of S(r), and let
min(S) and max(S) be the largest and smallest strings of S, respectively: we
say that the strings in S are almost-equal if both the following conditions hold:
(
r C1
C2
C3 Fig. 3: Examples about notation Compact() and Reduce(): C2 = Reduce(C1; r) and C3 = Compact(C2; r) = Compact(C1; r). be made equal to max(S) by just reversing one occurrence of the substring 01 in min(S).
Given a robot r, if S(r) contains strings without any 1 we say that r has free paths. When r has no free paths, there could exist partitions of S(r) de ned as follows:
fS1; S2; : : : ; Skg is a rotational-partition of S(r) if: (
fS1; S2; : : : ; Skg is a re ective-partition of S(r) if: (
As an example, consider robot r in con guration C1 represented if Fig. 3: fS1; S2g with S1 = f1100; 1100; 1100g and S2 = f0100; 0100; 0010g is a rotationalpartition of S(r). Notice that, in the previous de nition the value k ranges from one to three, and the latter occurs in the tessellation graph with the largest degree, i.e. GT . If the strings in S(r) form a rotational-partition or a re ectivepartition fS1; S2; : : : ; Skg, then by notation Reduce(C; r) we denote the con guration obtained from C by replacing, for each set Si, each string s 2 Si with the largest string max(Si). By Compact (C; r) we denote the con guration obtained from C by replacing each string s 2 S(r) with its \compact version", that is the largest binary string containing the same number of 1's as s. Examples about notation Compact () and Reduce() are provided in the caption of Fig. 3. 4
Formalization of Abreak In this section, we formalize the proposed algorithm Abreak designed to solve the SB problem for any initial con guration C = (G; R; ), with G 2 fGS ; GT g, composed of n Async robots endowed with all the minimal capabilities recalled in the Introduction. We assume n 3, since for n = 1 the SB problem is trivial and for n = 2 we get that C cannot be a leader con guration.
Algorithm: Abreak Input: Leader con guration C = (G; R; ), with G 2 fGS ; GT g and R composed of n Async robots; external procedures IModule and FModule. 1 Call IModule ; 2 if C 2 aRot then 3 let r be the robot that makes C a-rotational (cf. De nition 5) ; 4 let P = fS1; S2 : : : ; Skg be the rotational-regular partition of S(r) ; 5 call MakeSpace(r; P) 6 else if C 2 uRot then 7 the central robot r of C moves on one of its neighbors; if possible, r selects a neighbor not belonging to an axis of re ection 8 else if C 2 fRot then 9 the central robot r of C moves on a neighbor belonging to any free path; if possible, r selects a neighbor not belonging to an axis of re ection 10 else if C 2 aDia then 11 let r be the robot that makes C a-diagonal (cf. De nition 7) ; 12 let P = fS1; S2 : : : ; Skg be the diagonal-regular partition of S(r) ; 13 call MakeSpace(r; P) 14 else if C 2 uRef then 15 let r be the robot on the axis of C, with N(r) = ;, and having smallest position in
LSS; 16 r moves on one of its neighbors not belonging to the axis of re ection 17 else if C 2 fRef then 18 let r be the robot on the axis of C with free paths, and having smallest position in
LSS ; 19 r moves on a neighbor belonging to any free path 20 else if C is asymmetric then 21 call FModule
Algorithm Abreak makes use of three distinct procedures:2 (
Basically, algorithm Abreak determines which class the input con guration
belongs to, with respect to some classes that are formalized in what follows.
De nition 5 (a-rotational con guration). A con guration C = (G; R; ),
with G 2 fGS ; GT g, is called almost-rotational (a-rotational, for short) if there
exists a robot r 2 R such that all the following conditions hold: (
Input: Robot r and a partition P = fS1; S2 : : : ; Skg of S(r).
1 if there exist a multiset Si 2 P having di erent strings then
2 foreach Si 2 P : min(Si) 6= max(Si) do
3 foreach s 2 Si : s = max(Si) do
4 let r be the robot corresponding to the bit 1 in the substring \10" to be
reversed in order to make s equal to min(Si) ;
5 r moves so that s becomes equal to min(Si)
6 else // for each Si, the strings in Si are all the same
7 foreach s 2 Si that starts with 1 do
8 let r0 be the robot corresponding to the 1 in the rst occurrence of the substring
\10" of s;
9 r0 moves away from r along the hline corresponding to s
in C; (
De nition 6 (diagonal con guration). An initial con guration C = (G; R; ), with G 2 fGS ; GT g, is called diagonal if it is re ective and its re ection axis does not coincide with any canonical line.
De nition 7 (a-diagonal con guration). A con guration C = (G; R; ),
with G 2 fGS ; GT g, is called almost-diagonal (a-diagonal, for short) if there
exists a robot r 2 R such that all the following conditions hold: (
Robot r as in De nition 5 (De nition 7, resp.) is said the robot that makes C a-rotational (a-diagonal, resp.). Symbols aRot and aDia denote the classes containing all the a-rotational and a-diagonal con gurations, respectively. Additional classes of con gurations managed by Abreak are the following: { fRot denotes the class containing all the free-rotational (f-rotational, for short) con gurations. A con guration C is free-rotational if it is rotational and its central robot r has free paths; { uRot denotes the class containing all the unblocked-rotational (u-rotational, for short) con gurations. A con guration C is u-rotational if it is rotational and its central robot r has no free paths, but N (r) = ;; { fRef denotes the class containing all the free-re ective (f-re ective, for short) con gurations. A con guration C is free-re ective if it is re ective and there exists a robot r on the axis of C with free paths; { uRef denotes the class containing all the unblocked-re ective (u-re ective, for short) con gurations. A con guration C is u-re ective if it is re ective and each robot on its axis has no free paths, but there exists a robot r on the axis such that N (r) = ;.
It can be observed that the above de nitions give rise to sets that cover all the
initial con gurations in I. In fact, (
Theorem 1. Algorithm Abreak is able to solve the SB problem with respect to any initial con guration C = (G; R; ) such that G 2 fGS ; GT g.
Sketch of the Proof. If C 2 fRef [ uRef [ fRot [ uRot it is possible to select just
one robot to break the symmetry. In some cases, one move is enough, whereas
in other cases several moves are necessary (e.g., C 2 uRot, the central robot
moves to a neighbor, and the obtained con guration is in fRef). In these cases,
the algorithm produces an asymmetric con guration without pending moves.
Assume there exists a robot r that makes C a-rotational: both r and a
rotationalregular partition of S(r) are passed as input to MakeSpace. Let C(
We investigated the Symmetry Breaking problem in grid graphs. In this environment, breaking the symmetry by moving some leader robot is not a straightforward task due to the movement restrictions as all the adjacent nodes of the leader may be occupied. We have shown that it is possible solve the problem on both GS and GT graphs. The algorithm is proposed so that it can be also combined with other modules.
The most obvious open problem is to extend the proposed algorithm Abreak to work also in the hexagonal grid GH . Abreak uses few geometric concepts, such as: bounding parallelogram, grid line, shortest path, and \moving along a line". Moving to hexagonal grids, GH can be considered as a sub graph of GT in which the center of the hexagons correspond to removed vertices. However by simply assuming the \presence" of the missing nodes and edges with respect to GT , most of the geometric concepts introduced are still valid with the exception of \movement along a line". In fact, in GH a robot cannot move along a line but it needs to move along the edges of successive hexagons.
As another possible future investigation, it would be worth to test whether
it is possible to combine the proposed algorithm with that proposed in [2] to
solve the Arbitrary Pattern Formation problem. This would bring us closer to
characterizing such a problem on square grids. An advancement in this direction
is presented in a very recent work [14].
29. Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of
geometric patterns. SIAM J. Comput. 28(