Find in Library

The problem of evacuating two robots from the disk in the face-to-face model was first introduced by Czyzowicz et al. [DISC’2014], and has been extensively studied (along with many variations) ever since with respect to worst-case analysis. We initiate the study of the same problem with respect to average-case analysis, which is also equivalent to designing randomized algorithms for the problem. In particular, we introduce constrained optimization problem <inline-formula><math display="inline"><semantics><msub><mrow></mrow><mn>2</mn></msub></semantics></math></inline-formula><span style="font-variant: small-caps;">Evac</span><inline-formula><math display="inline"><semantics><msub><mrow></mrow><mrow><mi>F</mi><mn>2</mn><mi>F</mi></mrow></msub></semantics></math></inline-formula>, in which one is trying to minimize the average-case cost of the evacuation algorithm given that the worst-case cost does not exceed <i>w</i>. The problem is of special interest with respect to practical applications, since a common objective in search-and-rescue operations is to minimize the average completion time, given that a certain worst-case threshold is not exceeded, e.g., for safety or limited energy reasons. Our main contribution is the design and analysis of families of new evacuation parameterized algorithms which can solve <inline-formula><math display="inline"><semantics><msub><mrow></mrow><mn>2</mn></msub></semantics></math></inline-formula><span style="font-variant: small-caps;">Evac</span><inline-formula><math display="inline"><semantics><msub><mrow></mrow><mrow><mi>F</mi><mn>2</mn><mi>F</mi></mrow></msub></semantics></math></inline-formula>, for every <i>w</i> for which the problem is feasible. Notably, the worst-case analysis of the problem, since its introduction, has been relying on technical numerical, computer-assisted calculations, following tedious robot trajectory analysis. Part of our contribution is a novel systematic procedure, which given <i>any evacuation algorithm</i>, can derive its worst- and average-case performance in a clean and unified way.