Online Algorithm for Evacuating Crashed Faulty Robots from A Square

This paper considers an online problem of evacuating
$\boldsymbol{n}$
mobile robots from a square, of which at most
$\boldsymbol{f}$
are faulty, and the remaining are nonfaulty. We call this problem as
$\boldsymbol{(n, f)}$
-evacuation. There is an exit on the boundary of the square. Nonfaulty robots can find the exit when they reach it. The
$\boldsymbol{n}$
robots start from a point in the square. They can communicate with each other during the evacuation. The goal of them is to find the exit and evacuate from it. We use competitive ratio to measure the performance of the algorithm, which is the ratio of the cost between our algorithm and the optimal offline algorithm. For the case of (2, 1)-evacuation and (3, 1)-evacuation, we propose a
$\boldsymbol{(3+\sqrt{2}+2\alpha)}$
-competitive algorithm. For the case of (3, 2)-evacuation, we propose a
$(1+2\ \sqrt{2}+2\alpha+\sqrt{2}\ \beta)$
-competitive algorithm, where
$\alpha$
and
$\beta$
denote the change of the evacuation speed.