Collaboration Without Communication: Evacuating Two Robots from a Disk

We consider the problem of evacuating two robots from a bounded area, through an unknown exit located on the boundary. Initially, the robots are in the center of the area and throughout the evacuation process they can only communicate with each other when they are at the same point at the same time. Having a visibility range of 0, the robots can only identify the location of the exit if they are already at the exit position. The task is to minimize the time it takes until both robots reach the exit, for a worst-case placement of the exit. For unit disks, an upper bound of 5.628 for the evacuation time is presented in [8]. Using the insight that, perhaps surprisingly, a forced meeting of the two robots as performed in the respective algorithm does not provide an exchange of any non-trivial information, we design a simpler algorithm that achieves an upper bound of 5.625. Our numerical simulations suggest that this bound is optimal for the considered natural class of algorithms. For dealing with the technical difficulties in analyzing the algorithm, we formulate a powerful new criterion that, for a given algorithm, reduces the number of possible worst-case exits radically. This criterion is of independent interest and can be applied to any area shape. Due to space restrictions, this version of the paper contains no proofs or illustrating figures; the full version can be found at http://disco.ethz.ch/publications/ciac2017-robotevac.pdf.