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

摘要

Distributed evacuation of mobile robots is a recent development. We consider the evacuation problem of two robots which are initially located at the center of a unit disk. Both the robots have to evacuate the disk through the exits situated on the perimeter of the disk at an unknown location. The distance between two exits along the perimeter $d$ is given. We consider two different communication models. First, in the wireless model, the robots can send a message to each other over a long distance. Second, in face-to-face communication model, the robots can exchange information with each other only when they touch each other. The objective of the evacuation problem is to design an algorithm which minimizes the evacuation time of both the robots. For the wireless communication model, we propose a generic algorithm for two robots moving to two points on the perimeter with an initial separation of $ζ\leq d$. We also investigate evacuation problem for both unlabeled and labeled exits in the wireless communication model. For the face-to-face communication model, we propose two different algorithms for $ζ=0$ and $ζ=d$ for unlabeled exits. We also propose a generic algorithm for $ζ\leq d$ for labeled exits. We provide lower bounds corresponding to different $d$ values in the face-to-face communication model. We evaluate the performance our algorithms with simulation for both of the communication models.