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.
There is a large literature on distributed computing by autonomous mobile agents, see the book @cite_12 that provides a very complete survey of results in this area. Much of this work is done for mobile agents located in the plane or a continuous region, and the main problems that have been considered are gathering of robots @cite_2 @cite_22 , scattering and covering @cite_26 , and pattern formation @cite_5 @cite_0 by autonomous mobile robots (see [section 1.3] flocchini2019distributed ). The solvability, i.e., termination or convergence, of these problems depends on the type of synchronization, visibility, agreement on orientation @cite_12 . @cite_9 , the authors introduce the problem of using a set of pairwise-communicating processes to constructing a given network.
@cite_26 @cite_22 @cite_9 @cite_0 @cite_2 @cite_5 @cite_12
1981643246 2782960731 1493636406 2963730940
Mobile agent computing is being used in fields as diverse as artificial intelligence, computational economics and robotics. Agents' ability to adapt dynamically and execute asynchronously and autonomously brings potential advantages in terms of fault-tolerance, flexibility and simplicity. This monograph focuses on studying mobile agents as modelled in distributed systems research and in particular within the framework of research performed in the distributed algorithms community. It studies the fundamental question of how to achieve rendezvous , the gathering of two or more agents at the same node of a network. Like leader election, such an operation is a useful subroutine in more general computations that may require the agents to synchronize, share information, divide up chores, etc. The work provides an introduction to the algorithmic issues raised by the rendezvous problem in the distributed computing setting. For the most part our investigation concentrates on the simplest case of two agents attempting to rendezvous on a ring network. Other situations including multiple agents, faulty nodes and other topologies are also examined. An extensive bibliography provides many pointers to related work not covered in the text. The presentation has a distinctly algorithmic, rigorous, distributed computing flavor and most results should be easily accessible to advanced undergraduate and graduate students in computer science and mathematics departments. Table of Contents: Models for Mobile Agent Computing Deterministic Rendezvous in a Ring Multiple Agent Rendezvous in a Ring Randomized Rendezvous in a Ring Other Models Other Topologies Swarms of mobile robots recently attracted the focus of the Distributed Computing community. One of the fundamental problems in this context is that of exploration: the robots must coordinate to visit all locations that are reachable from their initial positions. Despite its apparent simplicity, this problem proved quite hard to characterise fully, due to many model variants, leading to informal error-prone reasoning. Over the past few years, a significant effort permitted to set up a formal framework, relying on the Coq proof assistant, which was used to provide certified results when robots evolve in a continuous bi-dimensional Euclidean space. However, the most challenging issues with exploration arise in the discrete setting (a.k.a. graph), where locations are modeled as vertices and where edges between vertices denote the ability for a robot to move from one location to the next. We present a formal model to tackle problems and reason about robot algorithms arising in the discrete setting. Our approach extends and generalises previous research efforts focusing on the continuous model. As case studies, we consider fundamental impossibility results for exploration with stop in the discrete model. To our knowledge, those are the first certified results in this context. This framework paves the way for a general certification workflow dedicated to mobile robots on graphs. Two anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension δ > 0, starting from two arbitrary positions at distance at most d. Since the problem is clearly infeasible in such general setting, we assume that the grid is embedded in a δ-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position (but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length O(dδ polylog d). This bound for the case of 2D-grids subsumes the main result of [12]. The algorithm is almost optimal, since the Ω(dδ) lower bound is straightforward. Further, we apply our rendezvous method to the following network design problem. The ports of the δ-dimensional grid have to be set such that two anonymous agents starting at distance at most d from each other will always meet, moving in an asynchronous manner, after traversing a O(dδ polylog d) length trajectory. We can also apply our method to a version of the geometric rendezvous problem. Two anonymous agents move asynchronously in the δ-dimensional Euclidean space. The agents have the radii of visibility of r1 and r2, respectively. Each agent knows only its own initial position and its own radius of visibility. The agents meet when one agent is visible to the other one. We propose an algorithm designing the trajectory of each agent, so that they always meet after traveling a total distance of O((d r)δ polylog(d r)), where r = min(r1, r2) and for r ≥ 1. Consider a set of n finite set of simple autonomous mobile robots (asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, non-rigid, deterministic) initially in distinct locations, moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of the robots arranging themselves on the vertices of a regular n-gon not fixed in advance (Uniform Circle Formation). In the literature, the existing algorithmic contributions are limited to conveniently restricted sets of initial configurations of the robots and to more powerful robots. The question of whether such simple robots could deterministically form a uniform circle has remained open. In this paper, we constructively prove that indeed the Uniform Circle Formation problem is solvable for any initial configuration in which the robots are in distinct locations, without any additional assumption (if two robots are in the same location, the problem is easily seen to be unsolvable). In addition to closing a long-standing problem, the result of this paper also implies that, for pattern formation, asynchrony is not a computational handicap, and that additional powers such as chirality and rigidity are computationally irrelevant.