Evacuating two robots from multiple unknown exits in a circle

Abstract

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.