Search

We focus on the following question about Gathering of n autonomous, mobile robots in the Euclidean plane: Is it possible to solve Gathering of robots that do not agree on their coordinate systems (disoriented) and see other robots only up to a constant distance (limited visibility) in linear time? Up to now, such a result is only known for robots on a two-dimensional grid [1, 8]. We answer the question positively for robots that are connected in one closed chain (like [1]), i.e., every robot is connected to exactly two other robots, and the connections form a cycle. We show that these robots can be gathered by asynchronous robots (\(\mathcal {A}\) sync) in \(\varTheta \left( n\right) \) epochs assuming the \(\mathcal {LUMI}\) model [12] that equips the robots with locally visible lights like in [1, 8]. The lights are used to initiate and perform so-called runs along the chain, which are essential for the linear runtime. Starting of runs is done by determining locally unique robots (based on geometric shapes of neighborhoods). In contrast to the grid [1], this is not possible in every configuration in the Euclidean plane. Based on the theory of isogonal polygons by Grunbaum [18], we identify the class of isogonal configurations in which, due to a high symmetry, no locally unique robots can be identified. Our solution consists of two algorithms that might be executed in parallel: The first one gathers isogonal configurations without any lights. The second one works for non-isogonal configurations; it is based on the concept of runs using a constant number of lights.

This work focuses on the following question related to the Gathering problem of n autonomous, mobile robots in the Euclidean plane: Is it possible to solve Gathering of disoriented robots with limited visibility in \(o(n^2)\) fully synchronous rounds ( Open image in new window )? The best known algorithm considering the \(\mathcal {OBLOT}\) model (oblivious robots) needs \(\varTheta \left( n^2\right) \) rounds [6]. The lower bound for this algorithm even holds in a simplified closed chain model, where each robot has exactly two neighbors and the chain connections form a cycle. The only existing algorithms achieving a linear number of rounds for disoriented robots assume robots that are located on a two dimensional grid [1] and [5]. Both algorithms consider the \(\mathcal {LUMINOUS}\) model.

Routing is a challenging problem for wireless ad hoc networks, especially when the nodes are mobile and spread so widely that in most cases multiple hops are needed to route a message from one node to another. In fact, it is known that any online routing protocol has a poor performance in the worst case, in a sense that there is a distribution of nodes resulting in bad routing paths for that protocol, even if the nodes know their geographic positions and the geographic position of the destination of a message is known. The reason for that is that radio holes in the ad hoc network may require messages to take long detours in order to get to a destination, which are hard to find in an online fashion.

We consider a multilevel network game, where nodes can improve their communication costs by connecting to a high-speed network. The n nodes are connected by a static network and each node can decide individually to become a gateway to the high-speed network. The goal of a node v is to minimize its private costs, i.e., the sum (SUM-game) or maximum (MAX-game) of communication distances from v to all other nodes plus a fixed price α > 0 if it decides to be a gateway. Between gateways the communication distance is 0, and gateways also improve other nodes’ distances by behaving as shortcuts. For the SUM-game, we show that for α ≤ n − 1, the price of anarchy is \(\Theta({n/\sqrt{\alpha}})\) and in this range equilibria always exist. In range α ∈ (n − 1,n(n − 1)) the price of anarchy is \(\Theta({\sqrt{\alpha}})\), and for α ≥ n(n − 1) it is constant. For the MAX-game, we show that the price of anarchy is either \(\Theta({1 + n/\sqrt{\alpha}})\), for α ≥ 1, or else 1. Given a graph with girth of at least 4α, equilibria always exist. Concerning the dynamics, both games are not potential games. For the SUM-game, we even show that it is not weakly acyclic.