Evacuating two robots from multiple unknown exits in a circle
Distributed on a unit circle are k exits. Two autonomous mobile robots are placed on the circle. Each robot has a maximum speed of 1 and the robots can communicate wirelessly. The robots have a map of the domain, including exits, but do not have knowledge of their own initial locations on the domain, rather they only know their relative distance. The goal of the evacuation problem is to give an algorithm for the robots which minimizes the time required for both robots to reach an exit, in the worst case. We consider two variations of the problem depending on whether 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 distribution 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 exit distribution 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.
|Keywords||Algorithm, Circle, Evacuation, Mobile robots, Searching|
|Conference||17th International Conference on Distributed Computing and Networking, ICDCN 2016|
Czyzowicz, J. (Jurek), Dobrev, S. (Stefan), Georgiou, K. (Konstantinos), Kranakis, E, & Macquarrie, F. (Fraser). (2016). Evacuating two robots from multiple unknown exits in a circle. Presented at the 17th International Conference on Distributed Computing and Networking, ICDCN 2016. doi:10.1145/2833312.2833318