Assume that two robots are located at the centre of a unit disk. Their goal is to evacuate from the disk through an exit at an unknown location on the boundary of the disk. At any time the robots can move anywhere they choose on the disk, independently of each other, with maximum speed @math . The robots can cooperate by exchanging information whenever they meet. We study algorithms for the two robots to minimize the evacuation time: the time when both robots reach the exit. In [CGGKMP14] the authors gave an algorithm defining trajectories for the two robots yielding evacuation time at most @math and also proved that any algorithm has evacuation time at least @math . We improve both the upper and lower bounds on the evacuation time of a unit disk. Namely, we present a new non-trivial algorithm whose evacuation time is at most @math and show that any algorithm has evacuation time at least @math . To achieve the upper bound, we designed an algorithm which non-intuitively proposes a forced meeting between the two robots, even if the exit has not been found by either of them.
Our problem is also related to the rendezvous problem and the problem of gathering @cite_4 @cite_6 . Indeed our problem can be seen as a version of a rendezvous problem for three robots, where one of them remains stationary.
@cite_4 @cite_6
2132239960 2010017329
We apply a new method of analysis to the asymmetric rendezvous search problem on the line (ARSPL). This problem, previously studied in a paper of Alpern and Gal (1995), asks how two blind, speed one players placed a distance d apart on the line, can find each other in minimum expected time. The distance d is drawn from a known cumulative probability distribution G, and the players are faced in random directions. We show that the ARSPL is strategically equivalent to a new problem we call the double linear search problem (DLSP), where an object is placed equiprobably on one of two lines, and equiprobably at positions ±d. A searcher is placed at the origin of each of these lines. The two searchers move with a combined speed of one, to minimize the expected time before one of them finds the object. Using results from a concurrent paper of the first author and J. V. Howard (1998), we solve the DLSP (and hence the ARSPL) for the case where G is convex on its support, and show that the solution is that conjectured in a paper of Baston and Gal (1998). In 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, computations, 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.