Evacuating Two Robots from Two Unknown Exits on the Perimeter of a Disk with Wireless Communication

摘要

The evacuation of mobile robots is an interesting emerging application in distributed computing. This paper considers the fundamental problem of how to evacuate two robots from a unit disk. The robots, initially located at the center of the disk, need to exit the disk through two unknown exits, at known distance d from each other, located at the perimeter of the disk. The robots can coordinate when exploring the disk, using wireless communication. The objective is to minimize the evacuation time, i.e., the time until the last robot exits the disk. We consider two different model variants, where exits can either be labeled or unlabeled. We complement our analysis with simulations.