Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userScatter of Weak Robots
87
0
0.0
(
0
)
Added by
Franck Petit
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Authors
Yoann Dieudonne
Ask ChatGPT about the research
No Arabic abstract
In this paper, we first formalize the problem to be solved, i.e., the Scatter Problem (SP). We then show that SP cannot be deterministically solved. Next, we propose a randomized algorithm for this problem. The proposed solution is trivially self-stabilizing. We then show how to design a self-stabilizing version of any deterministic solution for the Pattern Formation and the Gathering problems.
rate research
Read More
A Lyndon word is a non-empty word strictly smaller in the lexicographic order than any of its suffixes, except itself and the empty word. In this paper, we show how Lyndon words can be used in the distributed control of a set of n weak mobile robots. By weak, we mean that the robots are anonymous, memoryless, without any common sense of direction, and unable to communicate in an other way than observation. An efficient and simple deterministic protocol to form a regular n-gon is presented and proven for n prime.
The dispersion problem on graphs requires $k$ robots placed arbitrarily at the $n$ nodes of an anonymous graph, where $k leq n$, to coordinate with each other to reach a final configuration in which each robot is at a distinct node of the graph. The dispersion problem is important due to its relationship to graph exploration by mobile robots, scattering on a graph, and load balancing on a graph. In addition, an intrinsic application of dispersion has been shown to be the relocation of self-driven electric cars (robots) to recharge stations (nodes). We propose three efficient algorithms to solve dispersion on graphs. Our algorithms require $O(k log Delta)$ bits at each robot, and $O(m)$ steps running time, where $m$ is the number of edges and $Delta$ is the degree of the graph. The algorithms differ in whether they address the synchronous or the asynchronous system model, and in what, where, and how data structures are maintained.
We study the convergence problem in fully asynchronous, uni-dimensional robot networks that are prone to Byzantine (i.e. malicious) failures. In these settings, oblivious anonymous robots with arbitrary initial positions are required to eventually converge to an a apriori unknown position despite a subset of them exhibiting Byzantine behavior. Our contribution is twofold. We propose a deterministic algorithm that solves the problem in the most generic settings: fully asynchronous robots that operate in the non-atomic CORDA model. Our algorithm provides convergence in 5f+1-sized networks where f is the upper bound on the number of Byzantine robots. Additionally, we prove that 5f+1 is a lower bound whenever robot scheduling is fully asynchronous. This constrasts with previous results in partially synchronous robots networks, where 3f+1 robots are necessary and sufficient.
We consider the following variant of the two dimensional gathering problem for swarms of robots: Given a swarm of $n$ indistinguishable, point shaped robots on a two dimensional grid. Initially, the robots form a closed chain on the grid and must keep this connectivity during the whole process of their gathering. Connectivity means, that neighboring robots of the chain need to be positioned at the same or neighboring points of the grid. In our model, gathering means to keep shortening the chain until the robots are located inside a $2times 2$ subgrid. Our model is completely local (no global control, no global coordinates, no compass, no global communication or vision, ldots). Each robot can only see its next constant number of left and right neighbors on the chain. This fixed constant is called the emph{viewing path length}. All its operations and detections are restricted to this constant number of robots. Other robots, even if located at neighboring or the same grid point cannot be detected. Only based on the relative positions of its detectable chain neighbors, a robot can decide to obtain a certain state. Based on this state and their local knowledge, the robots do local modifications to the chain by moving to neighboring grid points without breaking the chain. These modifications are performed without the knowledge whether they lead to a global progress or not. We assume the fully synchronous $mathcal{FSYNC}$ model. For this problem, we present a gathering algorithm which needs linear time. This result generalizes the result from cite{hopper}, where an open chain with specified distinguishable (and fixed) endpoints is considered.
We consider a swarm of $n$ autonomous mobile robots, distributed on a 2-dimensional grid. A basic task for such a swarm is the gathering process: All robots have to gather at one (not predefined) place. A common local model for extremely simple robots is the following: The robots do not have a common compass, only have a constant viewing radius, are autonomous and indistinguishable, can move at most a constant distance in each step, cannot communicate, are oblivious and do not have flags or states. The only gathering algorithm under this robot model, with known runtime bounds, needs $mathcal{O}(n^2)$ rounds and works in the Euclidean plane. The underlying time model for the algorithm is the fully synchronous $mathcal{FSYNC}$ model. On the other side, in the case of the 2-dimensional grid, the only known gathering algorithms for the same time and a similar local model additionally require a constant memory, states and flags to communicate these states to neighbors in viewing range. They gather in time $mathcal{O}(n)$. In this paper we contribute the (to the best of our knowledge) first gathering algorithm on the grid that works under the same simple local model as the above mentioned Euclidean plane strategy, i.e., without memory (oblivious), flags and states. We prove its correctness and an $mathcal{O}(n^2)$ time bound in the fully synchronous $mathcal{FSYNC}$ time model. This time bound matches the time bound of the best known algorithm for the Euclidean plane mentioned above. We say gathering is done if all robots are located within a $2times 2$ square, because in $mathcal{FSYNC}$ such configurations cannot be solved.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
