Competitive Strategies for Evacuating from an Unknown Affected Area

作者：Wei, Qi^*; Tan, Xuehou; Jiang, Bo

来源：IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2016, E99D(10): 2585-2590.

DOI：10.1587/transinf.2016EDP7118

• evacuation problem
• computational geometry
• path planning
• convex region
• competitive ratio

This article presents efficient strategies for evacuating from an unknown affected area in a plane. Evacuation is the process of movement away from a threat or hazard such as natural disasters. Consider that one or n(n >= 3) agents are lost in an unknown convex region P. The agents know neither the boundary information of P nor their positions. We seek competitive strategies that can evacuate the agent from P as quickly as possible. The performance of the strategy is measured by a competitive ratio of the evacuation path over the shortest path. We give a 13.812-competitive spiral strategy for one agent, and prove that it is optimal among all monotone and periodic strategies by showing a matching lower bound. Also, we give a new competitive strategy EES for n(n >= 3) agents and adjust it to be more efficient with the analysis of its performance.

• 出版日期2016-10
• 单位大连理工大学; 大连海事大学