1,721,188 research outputs found
Gathering of Asynchronous Robots with Limited Visibility
No full textIn this paper we study the problem of gathering a collection of identical oblivious mobile robots in the same location of the plane. Previous investigations have focused mostly on the unlimited visibility setting, where each robot can always see all the others regardless of their distance.
In the more difficult and realistic setting where the robots have limited visibility, the existing algorithmic results are only for convergence (towards a common point, without ever reaching it) and only for semi-synchronous environments, where robots’ movements are assumed to be performed instantaneously.
In contrast, we study this problem in a totally asynchronous setting, where robots’ actions, com- putations, and movements require a finite but otherwise unpredictable amount of time. We present a protocol that allows anonymous oblivious robots with limited visibility to gather in the same location in finite time, provided they have orientation (i.e., agreement on a coordinate system). Our result indicates that, with respect to gathering, orientation is at least as powerful as instantaneous movements
Locating Facilities on a Network to Minimize Their Average Service Radius
No full textLet G = (V,E) denote an undirected weighted graph of n nodes and m edges, and let U ⊆ V. The relative eccentricity of a node v ∈ U is the maximum distance in G between v and any other node of U, while the radius of U in G is the minimum relative eccentricity of all the nodes in U. Several facility location problems ask for partitioning the nodes of G so as to minimize some global optimization function of the radii of the subsets of the partition. Here, we focus on the problem of partitioning the nodes of G into exactly p ≥ 2 non-empty subsets, so as to minimize the sum of the subset radii, called the total radius of the partition. This problem can be easily seen to be NP-hard when p is part of the input, but when p is fixed it can be solved in polynomial time by reducing it to a similar partitioning problem. In this paper, we first present an efficient O(n 3) time algorithm for the notable case p = 2, which improves the O(mn 2 + n 3 logn) running time obtainable by applying the aforementioned reduction. Then, in an effort of characterizing meaningful polynomial-time solvable instances of the problem when p is part of the input, we show that (i) when G is a tree, then the problem can be solved in O(n 3 p 3) time, and (ii) when G has bounded treewidth h, then the problem can be solved in O(n 4h + 4 p 3) time
Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots
No full textArbitrary 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
Computing All The Best Swap Edges Distributively
No full textRecently great attention has been given to point-of-failure swap rerouting, an efficient technique for routing in the presence of transient failures. According to this technique, a message follows the normal routing table information unless the next hop has failed; in this case, it is redirected towards a precomputed link, called swap; once this link has been crossed, normal routing is resumed. The choice of the swap edge is done according to some optimization criteria on the resulting new route. The amount of precomputed information required in addition to the routing table is rather small: a single link per each destination. Several efficient serial algorithms have been presented to compute this information for several optimization criteria (Fdist, Fsum, Fincr, Fmax). Only the algorithm corresponding to Fdist has been efficiently implemented in a distributed environment, while for the other optimization criteria no distributed solution has been devised yet. In this paper we present protocols, based on a new strategy, that allow the efficient distributed computation of all the optimal swap edges under Fsum, Fincr, Fmax. Although considerably more difficult than Fdist, these problems can be solved with the same cost. In systems allowing long messages, we develop solution protocols based on the same strategy that use only O (n) messages without increasing the total amount of transmitted data items
Gathering of Asynchronous Oblivious Robots With Limited Visibility
No full textWe consider a collection of robots which are identical (anony- mous), have limited visibility of the environment, and no memory of the past (oblivious); furthermore, they are totally asynchronous in their ac- tions, computations, and movements. We show that, even in such a to- tally asynchronous setting, it is possible for the robots to gather in the same location in finite time, provided they have a compass
Vertex Disjoint Paths for Dispatching in Railways
No full textWe study variants of the vertex disjoint paths problem in planar graphs where paths have to be selected from a given set of paths. We study the problem as a decision, maximization, and routingin- rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the location of the terminals, motivated by railway applications, lead to polynomially solvable cases for the decision and maximization versions of the problem, and to a p-approximation algorithm for the routing-in-rounds problem, where p is the maximum number of alternative paths for a terminal pair
- …
