For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Competitive Strategies for Evacuating from an Unknown Affected Area
Qi WEI Xuehou TAN Bo JIANG
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/10/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
evacuation problem, computational geometry, path planning, convex region, competitive ratio,
Full Text: PDF(580.2KB)>>
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.