Competitive Strategies for Evacuating from an Unknown Affected Area

Qi WEI  Xuehou TAN  Bo JIANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.10   pp.2585-2590
Publication Date: 2016/10/01
Publicized: 2016/06/22
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016EDP7118
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
evacuation problem,  computational geometry,  path planning,  convex region,  competitive ratio,  

Full Text: PDF(580.2KB)>>
Buy this Article



Summary: 
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.