Average Case - Worst Case Tradeoffs for Evacuating 2 Robots from the\n Disk in the Face-to-Face Model

Abstract

The problem of evacuating two robots from the disk in the face-to-face model\nwas first introduced in [Czyzowicz et al., DISC'14], and extensively studied\n(along with many variations) ever since with respect to worst case analysis. We\ninitiate the study of the same problem with respect to average case analysis,\nwhich is also equivalent to designing randomized algorithms for the problem.\nFirst we observe that algorithm $B_{2}$ of~[Czyzowicz et al., DISC'14] with\nworst case cost $WRS(B_{2}):=5.73906$ has average case cost\n$AVG(B_{2}):=5.1172$. Then we verify that none of the algorithms that induced\nworst case cost improvements in subsequent publications has better average case\ncost, hence concluding that our problem requires the invention of new\nalgorithms. Then, we observe that a remarkable simple algorithm, $B_{1}$, has\nvery small average case cost $AVG(B_{1}):=1+\\pi$, but very high worst case cost\n$WRS(B_{1}):=1+2\\pi$.\n Motivated by the above, we introduce constrained optimization problem\n$_2Evac_{F2F}^w$, in which one is trying to minimize the average case cost of\nthe evacuation algorithm given that the worst case cost does not exceed $w$.\nThe problem is of special interest with respect to practical applications,\nsince a common objective in search-and-rescue operations is to minimize the\naverage completion time, given that a certain worst case threshold is not\nexceeded, e.g. for safety or limited energy reasons. Our main contribution is\nthe design and analysis of families of new evacuation parameterized algorithms\n$A(p)$ which can solve $_2Evac_{F2F}^w$, for every $w \\in\n[WRS(B_{1}),WRS(B_{2})]$.\n