Wireless evacuation on m rays with k searchers

摘要

We study the online problem of evacuating k robots on m concurrent rays to a single unknown exit. All k robots start on the same point s, not necessarily on the junction j of the m rays, move at unit speed, and can communicate wirelessly. The goal is to minimize the competitive ratio, i.e., the ratio between the time it takes to evacuate all robots to the exit and the time it would take if the location of the exit was known in advance, in the worst-case instance.