Breaking Symmetries on Tessellation Graphs via Asynchronous Robots? Serafino Cicerone Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica, Università degli Studi dell’Aquila, Italy. serafino.cicerone@univaq.it Abstract. We consider the coordination of autonomous mobile robots operating in the standard Look–Compute–Move cycles. Robots are as- sumed 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 them- selves 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 infinite grids. In infinite grids, in order to form any pattern, the problem of breaking sym- metries 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 asyn- chrony of robots, this fact greatly increases the difficulty of the problem. We assume regular tessellation graphs as discretization of the Euclidean plane, and we devise an algorithm able to solve the Symmetry Break- ing problem on both the square and triangular grids. The algorithm is proposed so that it can be also combined with other modules. 1 Introduction The coordination of autonomous mobile robots has long been object of study in several fields, including robotics, control, AI, as well as distributed comput- ing. Within distributed computing, in particular, extensive research efforts 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), anony- mous (they are identical in their external appearance, no unique identifiers), ho- mogeneous (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 Com- mons 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 different from robot to robot). Each robot, when active, operates in Look-Compute-Move cycles: it determines the po- sitions of the robots in the system (Look); this information is used to compute a destination point (Compute); the robot then moves towards the computed desti- nation (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 effort has been on determining which problems can be solved by a swarm of such robots. Crucial for the solv- ability 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 specific version that asks to determine from which initial configurations it is possible to form any specific 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 different model impos- ing 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 accu- rate movements in any direction and by any amount, even by infinitesimally small amounts. Hence, even in densely crowded situations, punctiform robots can ma- neuver 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 floor layouts can be easily implemented in real-life robot navigation systems. From an algorith- mic 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 specific graph topolo- gies 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 refer- ences therein. Few results concerning the general pattern formation problem on grids exist. Recently, the Arbitrary Pattern Formation for a set of oblivious asyn- chronous robots on the infinite grid in absence of any global coordinate system was first considered in [2]. Authors have shown that if the initial configuration is asymmetric, then the Arbitrary Pattern Formation problem is deterministically solvable by Async robots starting from asymmetric configurations. They poses as an open problem that of investigating about what can be achieved from sym- metric configurations. 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 configurations, that is the symmetric configurations 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 configuration, most of the robots must be moved. Due to the asynchrony of robots, this fact greatly increases the difficulty 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 configuration). 2 Basic notation and problem definition We denote by R = {r1 , r2 , . . . , rn } 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 configuration. A vertex v ∈ V is said occupied if there exists r ∈ R such that µ(r) = v, unoccupied otherwise. A multiplicity occurs in any vertex v ∈ 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) = {r0 ∈ R : µ(r0 ) ∈ N (µ(r))}. 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 en- vironment 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 specifically ordered time instants. Let C(t) be the configuration observed by some robots at time t during their Look phase, and let {ti : i = 0, 1, . . .}, 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 different 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 configuration C is a sequence of configurations E : C(0), C(1), . . ., where C(0) = C and C(t+1) is obtained from C(t) by moving some robot according to the result of the Compute phase as implemented by A. Notice that this definition of execution works also for the other schedulers. Moreover, given an algorithm A, in Async there exists more than one execution from C(0) depending on the activation of the robots (which depends on the adversary). 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. Configurations on tessellation graphs. In this work, we consider G as an infinite 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, equilat- eral triangles or regular hexagons (see Fig. 1). An infinite 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 infinite graph embedded into the Euclidean plane induced by the infinite lattice formed Fig. 1: Part of regular plane tessellations. 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 configurations C = (G, R, µ) where G ∈ {GS , GT , GH }. Concerning any graph G ∈ {GS , GT , GH }, it follows from the definition 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. Configuration automorphisms and symmetries. Two undirected graphs G = (V, E) and G0 = (V 0 , E 0 ) are isomorphic if there is a bijection ϕ from V to V 0 such that {u, v} ∈ E if and only if {ϕ(u), ϕ(v)} ∈ E 0 . 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 |Aut(G)| = 1, that is G admits only the identity automorphism, then G is said asymmetric, otherwise it is said symmetric. Two distinct vertices u, v ∈ V are equivalent if there exists an automorphism ϕ ∈ Aut(G) such that ϕ(u) = v. The concept of graph isomorphism can be extended to configurations in a natural way. Two configurations C = (G, R, µ) and C 0 = (G0 , R0 , µ0 ) are isomor- phic 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 configuration 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 |Aut(C)| = 1 we say that C is asymmetric, otherwise it is symmetric. Two distinct robots r and r0 in a configuration (G, µ) are equivalent if there exists ϕ ∈ Aut(C) such that ϕ(r) = r0 . Notice that, according to the definition, distinct robots in the same multiplicity are equivalent and hence each configuration 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 finished its Move phase. Formally, a robot r is pending in a configuration 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 difficulty to devise algorithms for Async robots, and this holds in particular in symmetric configurations, 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 configuration: a configuration C(t) is called stationary if there are no pending robots in C(t). Leader configurations and the Symmetry Breaking problem. Concern- ing the configurations addressed in this work, it is not difficult to see that any C = (G, R, µ), with G ∈ {GS , GT , GH }, admits two types of automorphisms only: reflections, defined by a reflection axis which acts as a mirror; rotations, defined by a center and an angle of rotation. A configuration admitting only one reflection axis is called reflective, and a configuration admitting any rotation is called rotational. Notice that a configuration with two or more reflection 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 defined by the algorithm will be applied by the adversary to all the considered robots. As a final result, the moved robots will remain symmetric in any possible obtained configuration. This implies that it is worth to address the problem of designing symmetry breaking algorithms only for special cases of symmetric configurations, as defined in the following. Definition 1 (leader-configuration). A configuration C = (G, R, µ), with G ∈ {GS , GT , GH }, is a leader configuration if one of the following cases holds: (1) C is reflective, and there are one or more robots on the axis of reflection; (2) C is rotational, and there is one robot on the center of rotation. Notice that in any leader configuration there exists a robot which is equivalent to itself. In principle, this means that there could exist an algorithm that can move one of such robots to create an asymmetric configuration. We can now formalize the main problem addressed in this work. Definition 2 (initial-configuration). A configuration C = (G, R, µ), with G ∈ {GS , GT , GH }, is an initial configuration if both the following conditions hold: (1) each robot is idle and placed on a different vertex, that is mul (v) ≤ 1 for each v ∈ V ; (2) C is a leader configuration. The set containing all the initial configurations is denoted by I. The goal of the Symmetry Breaking (SB , for short) problem is to design any distributed algorithm A that, starting from any configuration C ∈ I, guides the robots to form an asymmetric configuration C 0 . Formally, an algorithm A solves the SB problem for any configuration C ∈ I if, for each possible execution E : C = C(0), C(1), . . . of A, there exists a finite time instant t∗ > 0 such that C(t∗ ) is asymmetric and no robot moves after t∗ , i.e., C(t) = C(t∗ ) holds for all t ≥ t∗ . 3 Concepts and notation used by algorithm Abreak Here we introduce some concepts and notation used in the proposed algorithm Abreak . They refer to any configuration C = (G, R, µ), with G ∈ {GS , GT }. Bounding parallelogram. We introduce the concept of bounding parallelo- gram bp(R), defined 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 ori- entations, 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 configuration. Any algorithm addressing the SB problem needs to elect a leader among the robots in any initial configu- ration. If C is rotational, such a leader can be naturally identified with the robot occupying the center of rotation. Less obvious is how to identify a specific robot in reflective configurations. To this aim, in the following, we associate a binary string to any configuration so that from that string it is possible to elect a leader also in the case of initial reflective configurations. 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 defined as follows. Scan the finite 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 defined 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 configuration is reflective or rotational. A B r0 r D C Fig. 2: Visualization of some notation used in the paper. An initial reflective configuration C defined on GT : circles represent robots. It shows the three possible bounding parallelograms. They have all the same size. LSS (R) = 0011000111011010 and it is generated in both the red and blue parallelograms. In the blue one, LSS (R) is generated from the corner A along the side AD. Robot r is the pivot of the configuration. Definition 3 (LSS (R)). Let C = (G, R, µ) be a configuration, with G ∈ {GS , GT }, 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 definition that LSS (R) is unique, even when it is computed on symmetric configurations, 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 reflective configuration C = (G, R, µ): the pivot is the median robot on the reflection 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 configuration is reflective with two robots on the axis of reflection, 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 configuration 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 lexico- graphically ordered. Definition 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: (1) each string s ∈ S is either equal to min(S) or max(S), and (2) min(S) can r r 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) defined as follows: • {S1 , S2 , . . . , Sk } is a rotational-partition of S(r) if: (1) there exists an integer q > 1 such that, for each set Si , |Si | = q and the hlines corresponding to the string in Si partition the plane into sectors of 360/q degrees each; (2) for each set Si , the strings in Si are almost-equal; (3) k is minimum. • {S1 , S2 , . . . , Sk } is a reflective-partition of S(r) if: (1) there exists a line L such that, for each set Si , |Si | = 2 and L is the bisector of the hlines corresponding to the strings in Si or L is coincident with both the hlines corresponding to the strings in Si ; (2) for each set Si , the strings in Si are almost-equal; (3) k is minimum. As an example, consider robot r in configuration C1 represented if Fig. 3: {S1 , S2 } with S1 = {1100, 1100, 1100} and S2 = {0100, 0100, 0010} is a rotational- partition of S(r). Notice that, in the previous definition 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 reflective- partition {S1 , S2 , . . . , Sk }, then by notation Reduce(C, r) we denote the configu- ration obtained from C by replacing, for each set Si , each string s ∈ Si with the largest string max(Si ). By Compact(C, r) we denote the configuration obtained from C by replacing each string s ∈ 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 configuration C = (G, R, µ), with G ∈ {GS , GT }, 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 configuration. Algorithm: Abreak Input: Leader configuration C = (G, R, µ), with G ∈ {GS , GT } and R composed of n ≥ 3 Async robots; external procedures IModule and FModule. 1 Call IModule ; 2 if C ∈ aRot then 3 let r be the robot that makes C a-rotational (cf. Definition 5) ; 4 let P = {S1 , S2 . . . , Sk } be the rotational-regular partition of S(r) ; 5 call MakeSpace(r, P) 6 else if C ∈ 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 reflection 8 else if C ∈ 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 reflection 10 else if C ∈ aDia then 11 let r be the robot that makes C a-diagonal (cf. Definition 7) ; 12 let P = {S1 , S2 . . . , Sk } be the diagonal-regular partition of S(r) ; 13 call MakeSpace(r, P) 14 else if C ∈ 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 reflection 17 else if C ∈ 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 (1) Procedure MakeSpace, which is a procedure used in Abreak “to make space around the cen- tral robot” by moving the robots that lie on the axes of symmetry so as to push them away from the center. (2) Procedure IModule, an external module taken as input. If Abreak is simply used to solve the SB problem, then it corresponds to an empty procedure (e.g., no instructions contained). In case Abreak is used as a breaking symmetry module for obtaining some more general algorithm A, it can be used to check the termination property of A. (3) Procedure FModule, an external module taken as input. If Abreak is used to solve the SB problem, then it contains the following simple instruction: each robot performs the nil movement. Conversely, in case Abreak is used as a breaking symmetry module for solving some general problem Π defined for leader or asymmetric configurations, then FModule corresponds to any algorithm for Π but for asymmetric configurations only. Basically, algorithm Abreak determines which class the input configuration belongs to, with respect to some classes that are formalized in what follows. Definition 5 (a-rotational configuration). A configuration C = (G, R, µ), with G ∈ {GS , GT }, is called almost-rotational (a-rotational, for short) if there exists a robot r ∈ R such that all the following conditions hold: (1) r is blocked 2 According to the LCM model, we assume that each robot terminates the execution of any algorithm or procedure as soon as it detects the move to be performed. Procedure: MakeSpace Input: Robot r and a partition P = {S1 , S2 . . . , Sk } of S(r). 1 if there exist a multiset Si ∈ P having different strings then 2 foreach Si ∈ P : min(Si ) 6= max(Si ) do 3 foreach s ∈ 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 ∈ Si that starts with 1 do 8 let r 0 be the robot corresponding to the 1 in the first occurrence of the substring “10” of s; 9 r 0 moves away from r along the hline corresponding to s in C; (2) all strings in S(r) form a rotational-regular partition; (3) Reduce(C, r) is rotational and r is central in Compact(C, r). Definition 6 (diagonal configuration). An initial configuration C = (G, R, µ), with G ∈ {GS , GT }, is called diagonal if it is reflective and its reflection axis does not coincide with any canonical line. Definition 7 (a-diagonal configuration). A configuration C = (G, R, µ), with G ∈ {GS , GT }, is called almost-diagonal (a-diagonal, for short) if there exists a robot r ∈ R such that all the following conditions hold: (1) r is blocked in C; (2) all strings in S(r) form a reflective-regular partition; (3) Reduce(C, r) is diagonal and r is pivot in Compact(C, r). Robot r as in Definition 5 (Definition 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 configurations, respectively. Addi- tional classes of configurations managed by Abreak are the following: – fRot denotes the class containing all the free-rotational (f-rotational, for short) configurations. A configuration 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) configurations. A configuration 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-reflective (f-reflective, for short) configurations. A configuration C is free-reflective if it is reflective and there exists a robot r on the axis of C with free paths; – uRef denotes the class containing all the unblocked-reflective (u-reflective, for short) configurations. A configuration C is u-reflective if it is reflective 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 definitions give rise to sets that cover all the initial configurations in I. In fact, (1) I can be partitioned into rotational and reflective configurations by definition; (2) rotational configurations are further partitioned into those with the central robot having free paths (i.e., f-rotational) and those with the central robot having no free paths - the latter are further di- vided into those with central robots unblocked (i.e., u-rotational) and those with central robot blocked (i.e., a-rotational); (3) similarly, reflective configurations are partitioned into the three classes of f-reflective, u-reflective, and a-reflective configurations. It is worth to note that Abreak checks the membership of the input configuration C to the defined classes in a specific order, and this order is important for the correctness of the algorithm. Theorem 1. Algorithm Abreak is able to solve the SB problem with respect to any initial configuration C = (G, R, µ) such that G ∈ {GS , GT }. Sketch of the Proof. If C ∈ 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 ∈ uRot, the central robot moves to a neighbor, and the obtained configuration is in fRef). In these cases, the algorithm produces an asymmetric configuration without pending moves. Assume there exists a robot r that makes C a-rotational: both r and a rotational- regular partition of S(r) are passed as input to MakeSpace. Let C(1) be any configuration generated according to the execution of MakeSpace. According to the hypothesis and to the move performed by the algorithm, it can be observed that C(1) results to be in aRot too, and in particular the same robot r that was central in C(0) is now the robot that makes C(1) a-rotational. Hence, when Abreak processes C(1), the procedure moves exactly those robots that were not activated in C(0) or pending in C(1). This implies that all such robots are moved so that they will become stationary. Repeated calls to MakeSpace will finally push the robots forward until the robot r - the central one in C(0) - becomes unblocked in an obtained configuration C(t), for a finite t > 0. If C ∈ aDia, the same analysis applies, but here the key property of the algorithm is that MakeSpace may produce an a-rotational configuration C(1). We are able to show that in such a case the robot r that was pivot in C becomes the central robot in C(1). Again, Abreak correctly processes all the pending robots. t u 5 Conclusion We investigated the Symmetry Breaking problem in grid graphs. In this envi- ronment, breaking the symmetry by moving some leader robot is not a straight- forward 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]. References 1. Adhikary, R., Bose, K., Kundu, M.K., Sau, B.: Mutual visibility by asynchronous robots on infinite grid. In: Algorithms for Sensor Systems - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGO- SENSORS. Lecture Notes in Computer Science, vol. 11410, pp. 83–101. Springer (2018). 2. Bose, K., Adhikary, R., Kundu, M.K., Sau, B.: Arbitrary pattern formation on infinite grid by asynchronous oblivious robots. Theor. Comput. Sci. 815, 213–227 (2020). 3. Bose, K., Kundu, M.K., Adhikary, R., Sau, B.: Optimal gathering by asynchronous oblivious robots in hypercubes. In: Proc. 20th Int.’l Symp. on Algorithms and Ex- periments for Sensor Systems, Wireless Networks and Distributed Robotics (Algo- sensors). LNCS, vol. 11410, pp. 102–117 (2019) 4. Bramas, Q., Tixeuil, S.: Arbitrary pattern formation with four robots. In: Proc. 20th Int.’l Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS). LNCS, vol. 11201, pp. 333–348. Springer (2018) 5. Cicerone, S., Di Stefano, G., Navarra, A.: Minimum-traveled-distance gathering of oblivious robots over given meeting-points. In: Proc. 10th Int.’l Symp. on Algo- rithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (Algosensors). LNCS, vol. 8847, pp. 57–72. Springer (2014) 6. Cicerone, S., Di Stefano, G., Navarra, A.: Minmax-distance gathering on given meeting-points. In: Proc. 9th Int.’l Conf. on Algorithms and Complexity (CIAC). LNCS, vol. 9079, pp. 127–139. Springer (2015) 7. Cicerone, S., Di Stefano, G., Navarra, A.: Gathering of robots on meeting-points: feasibility and optimal resolution algorithms. Distributed Computing 31(1), 1–50 (2018) 8. Cicerone, S., Di Stefano, G., Navarra, A.: “Semi-Asynchronous”: a new scheduler for robot based computing systems. In: Proc. 38th IEEE Int.’l Conf. on Distributed Computing Systems, (ICDCS). pp. 176–187. IEEE (2018) 9. Cicerone, S., Di Stefano, G., Navarra, A.: Asynchronous arbitrary pattern for- mation: the effects of a rigorous approach. Distributed Computing 32(2), 91–132 (2019) 10. Cicerone, S., Di Stefano, G., Navarra, A.: Asynchronous robots on graphs: Gath- ering. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing, LNCS, vol. 11340, pp. 184–217. Springer (2019). https://doi.org/10.1007/978-3-030-11072-7 8 11. Cicerone, S., Di Stefano, G., Navarra, A.: Embedded pattern formation by asyn- chronous robots without chirality. Distributed Computing 32(4), 291–315 (2019) 12. Cicerone, S., Di Stefano, G., Navarra, A.: Gathering synchronous robots in graphs: from general properties to dense and symmetric topologies. In: Proc. 26th Int.’l Col- loquium on Structural Information and Communication Complexity (SIROCCO). LNCS, vol. 11639, pp. 170–184. Springer (2019) 13. Cicerone, S., Di Stefano, G., Navarra, A.: On gathering of semi-synchronous robots in graphs. In: Stabilization, Safety, and Security of Distributed Systems - 21st International Symposium, (SSS). LNCS, vol. 11914, pp. 84–98. Springer (2019). https://doi.org/10.1007/978-3-030-34992-9 7 14. Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: Arbitrary Pattern Forma- tion on Infinite Regular Tessellation Graphs - In: 22nd Int. Conf. on Distributed Computing and Networking, (ICDCN). ACM, (2021). To appear. 15. Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: Gathering. SIAM J. on Computing 41(4), 829–879 (2012) 16. D’Angelo, G., Navarra, A., Nisse, N.: A unified approach for gathering and ex- clusive searching on rings under weak assumptions. Distributed Computing 30(1), 17–48 (2017) 17. Das, S., Flocchini, P., Santoro, N., Yamashita, M.: Forming sequences of geomet- ric patterns with oblivious mobile robots. Distributed Computing 28(2), 131–145 (2015) 18. Di Stefano, G., Navarra, A.: Gathering of oblivious robots on infinite grids with minimum traveled distance. Inf. Comput. 254, 377–391 (2017) 19. Di Stefano, G., Navarra, A.: Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings. Distributed Computing 30(2), 75–86 (2017) 20. Dieudonné, Y., Petit, F., Villain, V.: Leader election problem versus pattern for- mation problem. In: Proc. 24th Int.’l Symp. on Distributed Computing (DISC). LNCS, vol. 6343, pp. 267–281. Springer (2010) 21. Flocchini, P.: Gathering. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Dis- tributed Computing by Mobile Entities, Current Research in Moving and Comput- ing, Lecture Notes in Computer Science, vol. 11340, pp. 63–82. Springer (2019). https://doi.org/10.1007/978-3-030-11072-7 4 22. Flocchini, P., Prencipe, G., Santoro, N., Viglietta, G.: Distributed computing by mobile robots: uniform circle formation. Distributed Comput. 30(6), 413–457 (2017). https://doi.org/10.1007/s00446-016-0291-x 23. Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor. Comput. Sci. 407(1-3), 412– 447 (2008) 24. Flocchini, P., Prencipe, G., Santoro (Eds.), N.: Distributed Computing by Mobile Entities, Current Research in Moving and Computing, LNCS, vol. 11340. Springer (2019). https://doi.org/10.1007/978-3-030-11072-7 25. Fujinaga, N., Yamauchi, Y., Ono, H., Kijima, S., Yamashita, M.: Pattern forma- tion by oblivious asynchronous mobile robots. SIAM J. Computing 44(3), 740–785 (2015) 26. Grünbaum, B., Shepard, G.C.: Tiling and Patterns. W. H. Freeman & Co., New York (1987) 27. Guilbault, S., Pelc, A.: Gathering asynchronous oblivious agents with local vision in regular bipartite graphs. Theor. Comput. Sci. 509, 86–96 (2013) 28. Ionascu, E.J.: Half domination arrangements in regular and semi- regular tessellation type graphs. Math abs/1201.4624v1 (2012), https://arxiv.org/abs/1201.4624v1 29. Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999) 30. Yamashita, M., Suzuki, I.: Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theor. Comput. Sci. 411(26-28), 2433–2453 (2010) 31. Yamauchi, Y.: Symmetry of anonymous robots. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing, Lecture Notes in Computer Science, vol. 11340, pp. 109–133. Springer (2019). https://doi.org/10.1007/978-3-030-11072-7 6