Evacuating from an Unknown Affected Area
Qi Wei, Xuehou Tan, Bo Jiang, Lijuan Wang · International Journal of Pattern Recognition and Artificial Intelligence · 2016
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.