Motivated by concerns about diversity in social networks, we consider the following pattern formation problems in rings. Assume n mobile agents are located at the nodes of an n-node ring network. Each agent is assigned a colour from the set ( c_1, c_2, , c_q ). The ring is divided into k contiguous blocks or neighbourhoods of length p. The agents are required to rearrange themselves in a distributed manner to satisfy given diversity requirements: in each block j and for each colour (c_i ), there must be exactly (n_i(j) >0 ) agents of colour (c_i ) in block j. Agents are assumed to be able to see agents in adjacent blocks, and move to any position in adjacent blocks in one time step.
In discrete spaces, typically graphs like grids or rings, similar problems have been studied, see for example: gathering @cite_17 @cite_25 ; exploration @cite_21 ; pattern formation @cite_29 ; and deployment @cite_15 . Unlike in our paper, in all these studies, only a subset of the nodes of the graph is occupied by agents, and typically agents are identical, and not partitioned into colour classes.
@cite_29 @cite_21 @cite_15 @cite_25 @cite_17
2899152902 1617059252 1969099455 43751763 2144182788
The Arbitrary Pattern Formation problem asks to design a distributed algorithm that allows a set of autonomous mobile robots to form any specific but arbitrary geometric pattern given as input. The problem has been extensively studied in literature in continuous domains. This paper investigates a discrete version of the problem where the robots are operating on a two dimensional infinite grid. The robots are assumed to be autonomous, identical, anonymous and oblivious. They operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The robots do not agree on any common global coordinate system or chirality. We have shown that a set of robots can form any arbitrary pattern, if their starting configuration is asymmetric. We consider the problem of exploring an anonymous unoriented ring of size n by k identical, oblivious, asynchronous mobile robots, that are unable to communicate, yet have the ability to sense their environment and take decisions based on their local view. Previous works in this weak scenario prove that k must not divide n for a deterministic solution to exist. Also, it is known that the minimum number of robots (either deterministic or probabilistic) to explore a ring of size n is 4. An upper bound of 17 robots holds in the deterministic case while 4 probabilistic robots are sufficient. In this paper, we close the complexity gap in the deterministic setting, by proving that no deterministic exploration is feasible with less than five robots, and that five robots are sufficient for any n that is coprime with five. Our protocol completes exploration in O(n) robot moves, which is also optimal. We consider two variants of the task of spreading a swarm of agents uniformly on a ring graph. Ant-like oblivious agents having limited capabilities are considered. The agents are assumed to have little memory, they all execute the same algorithm and no direct communication is allowed between them. Furthermore, the agents do not possess any global information. In particular, the size of the ring (n) and the number of agents in the swarm (k) are unknown to them. The agents are assumed to operate on an unweighted ring graph. Every agent can measure the distance to his two neighbors on the ring, up to a limited range of V edges. The first task considered, is dynamical (i.e. in motion) uniform deployment on the ring. We show that if either the ring is unoriented, or the visibility range is less than @?n [email protected]?, this is an impossible mission for the agents. Then, for an oriented ring and V>[email protected]?n [email protected]?, we propose an algorithm which achieves the deployment task in optimal time. The second task discussed, called quiescent spread, requires the agents to spread uniformly over the ring and stop moving. We prove that under our model, in which every agent can measure the distance only to his two neighbors, this task is impossible. Subsequently, we propose an algorithm which achieves quiescent but only almost uniform spread. The algorithms we present are scalable and robust. In case the environment (the size of the ring) or the number of agents changes during the run, the swarm adapts and re-deploys without requiring any outside interference. 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. We consider the problem of gathering identical, memoryless, mobile robots in one node of an anonymous unoriented ring. Robots start from different nodes of the ring. They operate in Look-Compute-Move cycles and have to end up in the same node. In one cycle, a robot takes a snapshot of the current configuration (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. For an odd number of robots we prove that gathering is feasible if and only if the initial configuration is not periodic, and we provide a gathering algorithm for any such configuration. For an even number of robots we decide the feasibility of gathering except for one type of symmetric initial configurations, and provide gathering algorithms for initial configurations proved to be gatherable.