Evacuating two robots from multiple unknown exits in a circle

We consider two variants of the evacuation problem depending on whether or not the two robots have control over their initial distance. When the initial distance of the robots is part of the input (i.e. no control), we show that simple algorithms exist which achieve optimal worst case evacuation times for the cases where the robots begin colocated with an arbitrary arrangement of the exits; and when the exits are either colocated or evenly spaced, with arbitrary starting positions of the robots. We also give upper and lower bounds on the problem with arbitrary arrangement of exits and starting positions of the robots. For the problem where robots can choose their initial distance (with knowledge of, but not control over the distribution of exits), we propose a natural family of algorithms parameterized by the maximum distance between any two exits and analyse their cost.