1,721,124 research outputs found
Searching for a black hole in arbitrary networks: optimal mobile agents protocols
No full textConsider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance \Delta+1 agents are needed and suffice, and the cost is \Theta(n^2), where \Delta is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is \Theta(n^2); and with complete topological knowledge only two agents suffice and the cost is Theta(nlogn). All the upper-bound proofs are constructive
Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
No full textFrom an engineering point of view, the problem of coordinating a set of autonomous,
mobile robots for the purpose of cooperatively performing a task has been studied
extensively over the past decade. In contrast, in this paper we aim to understand the
fundamental algorithmic limitations on what a set of autonomous mobile robots can or
cannot achieve. We therefore study a hard task for a set of weak robots. The task is for
the robots in the plane to form any arbitrary pattern that is given in advance. This task
is fundamental in the sense that if the robots can form any pattern, they can agree on
their respective roles in a subsequent, coordinated action. The robots are weak in several
aspects. They are anonymous; they cannot explicitly communicate with each other, but
only observe the positions of the others; they cannot remember the past; they operate in
a very strong form of asynchronicity.
We show that the tasks that such a system of robots can perform depend strongly on
their common agreement about their environment, i.e. the readings of their environment
sensors. If the robots have no common agreement about their environment, they cannot
form an arbitrary pattern. If each robot has a compass needle that indicates North (the robot
world is a flat surface, and compass needles are parallel), then any odd number of robots
can form an arbitrary pattern, but an even number cannot (in the worst case). If each robot
has two independent compass needles, say North and East, then any set of robots can form
any pattern
Mobile Search for a Black Hole in an Anonymous Ring
No full textIn this paper we address the problem of mobile agents searching for a highly harmful item (called a black hole) in a ring network. The black hole is a stationary process that destroys visiting agents upon their arrival without leaving any observable trace of such a destruction. The task is to have at least one surviving agent able to unambiguously report the location of the black hole.
We consider different scenarios and in each situation we answer some computational as well as complexity questions. We first consider agents that start from the same home base (co-located). We prove that two such agents are necessary and sufficient to locate the black hole; in our algorithm the agents perform O(n log n) moves (where n is the size of the ring) and we show that such a bound is optimal. We also consider time complexity and show how to achieve the optimal bound of 2n − 4 units of time using n − 1 agents. We generalize our technique to establish a trade-off between time and number of agents. We then consider the case of agents that start from different home bases (dispersed) and we show that if the ring is oriented, two dispersed agents are still necessary and sufficient. Also in this case our algorithm is optimal in terms of number of moves (\Theta(n log n)). We finally show that if the ring is unoriented, three agents are necessary and sufficient; an optimal algorithm follows from the oriented case
Distributed computing by mobile robots: uniform circle formation
Get PDFConsider 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
Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots
No full text- …
