We consider the problem of evacuating some people from an unknown convex region. The people do neither have information about the region boundary nor their positions. We seek competitive strategy that achieves a competitive ratio of the evacuation path over the shortest path. In the scenario of general plane, we propose a strategy SOP for one group, and prove that its competitive ratio is 19.64. And we propose a 14.37-competitive strategy STP for two groups. Also, we present efficient strategies in the scenario of grid network. Furthermore, our strategies can be used for guiding the robot to search the boundary of an unknown region.
['Qi Wei', 'Xuehou Tan', 'Bo Jiang', 'Lijuan Wang']
Evacuating from an Unknown Affected Area