1
|
Abstract
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.
Collapse
Affiliation(s)
- Qi Wei
- School of Information Science and Technology, Dalian Maritime University, Linghai Road 1, Dalian, P. R. China
- School of Information Science and Technology, Dalian Institute of Science and Technology, Bingang Road 999-26, Dalian, P. R. China
| | - Xuehou Tan
- School of Information Science and Technology, Tokai University, 4-1-1 Kitakaname, Hiratsuka 259-1292, Japan
| | - Bo Jiang
- School of Information Science and Technology, Dalian Maritime University, Linghai Road 1, Dalian, P. R. China
| | - Lijuan Wang
- School of Information Science and Technology, Dalian Maritime University, Linghai Road 1, Dalian, P. R. China
- School of Information Science and Technology, Dalian Institute of Science and Technology, Bingang Road 999-26, Dalian, P. R. China
| |
Collapse
|