A Multi-Objective Optimization Problem on Evacuating 2 Robots from the Disk in the Face-to-Face Model; Trade-Offs between Worst-Case and Average-Case Analysis ^†

Abstract

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 ${}_2$Evac${}_{F2F}$, in which one is trying to minimize the average-case cost of the evacuation algorithm given that the worst-case cost does not exceed w. 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 ${}_2$Evac${}_{F2F}$, for every w 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 any evacuation algorithm, can derive its worst- and average-case performance in a clean and unified way.

1. Introduction

In search-type problems, several searchers (robots or mobile agents) are moving within a domain with the objective to identify the location of a (hidden) item. Several variations have been introduced for the problem that range among others with respect to the domain, to searcher specs, to the termination criterion (definition of feasibility) and to the objective of the underlying optimization problem. When in particular there are more than one searchers, and the termination criterion is that all searchers reach the hidden item (also known as exit), then the search problem is usually referred to as an evacuation-type problem. The term was introduced recently by Czyzowicz et al. in [1] who studied the problem of locating a hidden item on the perimeter of the unit disk with at least two robots. Once all searchers reach the hidden item (hence the name of the problem), the cost of the solution was defined as the time that the last searcher reaches the item ( The termination criterion should not be confused with how the cost is quantified.). The problem was studied extensively also by subsequent publications exclusively under the lens of worst-case (competitive) performance, i.e., with the objective to minimize the worst-case (over all placements of the hidden item) time that the last searcher reaches the exit. In contrast, real-life applications are usually concerned with minimizing the average-case performance of an algorithm, especially if one must solve several instances of the problem. In our case, evacuation-type problems resemble search-and-rescue operations where on one hand it is desirable to minimize the average rescue time, but on the other hand one has to set hard thresholds regarding the possible worst-case performance of the operations (for example, due to safety concerns of the missing person/hidden item).

As a result, we are motivated to revisit existing evacuation-type problems in the realm of average-case performance, where the feasibility criterion is altered so as to also comply with possible bounds on the worst-case performance. Alternatively, one may think of an evacuation-type problem (or even search-type problem) as the multi-objective problem of minimizing simultaneously the worst-case and the average-case cost of feasible evacuation algorithm. In this direction, we study the evacuation problem [1] under the lens of average-case analysis with hard constraints on the worst-case performance, i.e., we study average-case worst-case trade-offs for the underlying optimization problem. More specifically, we introduce new evacuation-type problem ${}_2$Evac${}_{F2F}^w$ with two searchers, in which the objective is to optimize the average-case evacuation time (or equivalently to minimize the performance of a randomized algorithm with unbounded access to randomness) condition on that the worst-case evacuation time does not exceed value w. The latter optimization problem seems to be particularly challenging in light of all previous results for the problem that relied on tedious calculations and/or on arguments tailored to the proposed algorithmic solutions. In that direction, we rely on a simple, novel and systematic theoretical approach that allows us to analyze the performance (both average-case and worst-case) of any evacuation algorithm based on computer-assisted calculations. Taking advantage of this approach, we introduce new families of algorithms for ${}_2$Evac${}_{F2F}^w$. Interestingly, their worst-case analysis can be done rigorously, giving this way feasible evacuation protocols for the entire spectrum of values w. To motivate our results further, we also investigate the performance of existing algorithms of ${}_2$Evac${}_{F2F}^w$, and we actually show that our new algorithms indeed outperform them for many values of w.

1.1. Related Work

In search problems, robots (or commonly referred to as mobile agents or searchers) are equipped with the task of efficiently locating a hidden item in a geometric domain. Studied in many variations since the 1960s, see seminal results [2,3], search problems first focused on identifying optimal probabilistic search and hiding strategies. Several subsequent studies of search-variations gave rise to numerous publications, and eventually to surveys, e.g., [4,5], and books [6,7,8,9] that also coined the umbrella term Search Theory. Over the years, search problems were also studied under the lens (i) of exploration by single [10,11,12,13] or multiple robots [14,15,16], (ii) of terrain mapping [17,18,19] and (iii) of hide-and-seek and pursuit-evasion objectives, e.g., see [20,21,22,23].

Although the first reference to a theoretical evacuation problem seems to date back to [24,25], the problem we study follows the line of research of Czyzowicz et al. [1]. Among the many results reported in [1], the one relevant to the current paper pertains to searching with two unit-speed robots for an item/exit hidden at the perimeter of a unit circle. The two searchers operate in the so-called face-to-face model that does not allow exchange of information from distance, and their goal is to minimize the worst-case evacuation time, i.e., the worst-case (over all placements of the exit) time that the last searcher reaches the exit. The first reported upper bound of 5.73906 [1] used a basic evacuation algorithm, according to which robots choose an arbitrary point on the circle, search in opposite directions, while the exit finder detours once the exit is found in order to catch and notify her peer before the evacuate together from the exit. By analyzing the worst placement of the exit [26], improved the upper bound to 5.628 by introducing a carefully chosen detour, before even the exit was reported, that was meant to expedite the catching phase in case the exit was found in a critical time window. The detour trajectory was later simplified and coupled with an elegant performance analysis that resulted in a further improvement of 5.625 [27]. Only recently, [28] reported yet another improvement of 5.6234, which was achieved by employing multiple detours. In contrast, the best lower bound known of 5.255 is due to [26], and no improvement has been reported since.

Since the inception of ${}_2$Evac${}_{F2F}$ in [1], numerous search and evacuation-type variants have emerged that studied different robot specs and/or number of searchers, different communication models, and different domains. Some notable examples include search and/or evacuation in the disk with more than 1 exits [29,30], in triangles [31,32], on multiple rays [33], in graphs [34,35], on a line with at least two robots [36,37] (generalizing the seminal result of [38]), with faulty robots [39,40,41] or with probabilistically faulty robots [42], with advice (information) [43], with priority specification on the searchers [44,45], with immobile agents [46,47], with time/energy trade-off requirements [48,49], with speed bounds [50], and with terrain dependent speeds [51], just to name some. The interested reader may also see the recent survey [52] that elaborates more on some selected topics.

In a different direction, Baeza-Yates et al. posed the question of minimizing the worst-case trajectory of a single robot searching for a target point at an unknown location in the plane [38]. This was generalized to multiple robots in [53], and later has been studied in [54,55]. More recently, Refs. [56,57] gave lower bounds for related problems. However, in these papers, the robots cannot communicate, and moreover, the objective is for the first robot to find the target.

1.2. Discussion on Closely Related Literature and Improvements

The problem of evacuating robots from the disc was first introduced in [1]. Among the many results reported in the latter paper, the one we expand upon is that of evacuating 2 robots in the face-to-face model. The algorithmic analysis was done exclusively in the deterministic model, and hence was worst-case. The reported upper bound of 5.628 was achieved by a simple algorithm, call it $\mathcal{A}$, that deploys both robots in an arbitrary point on the perimeter of the unit disc, and then makes them search in different directions. When the exit is found, the finder follows the shortest trajectory (straight line) in order to catch the non-finder in her trajectory so that together they return to the exit.

The first improvement of [26] was motivated by the monotonicity of the cost of $\mathcal{A}$ as a function of the time that the exit is found. A careful analysis shows that the cost function is concave, with the maximizer corresponding to the placement of exit that induces the worst-case performance. The weakness of the underlying communication model is that the (potential) non-finder, call it $R_1$ has no way to know whether her peer, $R_2$ has found the exit. At the same time, if enough time has passed and if $R_1$ has not been caught (notified) by $R_2$, then $R_1$ can deduce that her peer might have found the exit in the “dangerous” neighborhood of the placement inducing the worst-case cost, and hence $R_2$ might be already moving toward $R_1$ in order to notify her. As a result, $R_1$ has the incentive to deviate from searching the perimeter and to move toward the interior to expedite the (possible) rendezvous. Such a detour needs to be carefully chosen so that it is long enough to save cost in case the exit was indeed found in the dangerous neighborhood and short enough so that the detour does not add much in the cost in case it did not. Overall, the time that the detour occurs together with the direction and length of the detour give three degrees of freedom with an objective to optimize the cost in two different cases; when the exit is found in the “dangerous neighborhood” and when it is not. Call this (family of) algorithm(s) ${\mathcal{A}}_0$. The search space for choosing the three optimal parameters for ${\mathcal{A}}_0$ is indeed enormous, and at a high level [26] considered only a restriction of the previous idea in which robots agree on a forced meeting on the diameter of the circle, effectively reducing the degrees of freedom of the algorithm but simplifying the already technical and theoretical analysis of its worst-case cost, which eventually relied on numerical calculations.

The upper bound was later improved to 5.625 in [27]. The novelty of the latter work pertained to the introduction of an elegant theoretical analysis of algorithms ${\mathcal{A}}_0$, which on one hand avoided the forced meeting and on the other improved upon the bound of [26] by choosing optimally its three parameters, which were eventually computed by numerical calculations. The authors of [27] further mentioned that their results could potentially be improved by introducing, at a high level, a recursively defined sequence of detour points aiming to address the reduction of the optimal worst-case cost, should the detour points were one less (so the improvement of $\mathcal{A}$ to ${\mathcal{A}}_0$ can be thought as the basic step in the inductive argument). Indeed, ref. [28] used exactly that idea and reported a new upper bound of 5.6234.

Quite interestingly, all previous results pertaining to the worst-case analysis relied on arguments that were somehow tailored to the aforementioned algorithms (robot trajectories). In contrast, we provide a framework that allows us to compute, with computer-assisted calculations, the worst-case cost of any evacuation algorithm, as long as robot trajectories are described by unit-speed-inducing parameterized curves. It is the same framework that allows us also to also compute the average-case cost for any such algorithm.

The main improvement upon the previously results of the same problem pertains to minimizing the average-case cost. In one extreme, one can analyze the naive algorithm in which searchers always stay together, inducing very low average-case cost, but very high worst-case cost. In the other extreme, the optimal algorithm ${\mathcal{A}}_0$ of [27] has very low worst-case cost (nearly the best known) and, according to our results, relatively high average-case cost. As a result, we are motivated to minimize the average-case cost, subject to the worst-case cost ranges between the cost of the naive algorithm that of the optimal ${\mathcal{A}}_0$ (or equivalently to consider the multi-objective optimization problem of minimizing simultaneously the average-case cost and worst-case cost). Quite surprisingly, we verify, using our technical framework, that among the family of algorithms ${\mathcal{A}}_0$, the one inducing the minimum average-case cost is that of $\mathcal{A}$. It is the latter observation that gives the main motivation for introducing the three new parameterized families of evacuation algorithms that attempt to minimize their average-case cost, inducing worst-case cost that range, continuously, over the two extreme worst-case costs.

1.3. Outline of Our Results and Paper Organization

We introduce and study a multi-objective analog of the well-studied problem of evacuating two robots from the disk, performing in the face-to-face communication mode. More specifically, we introduce evacuation problem ${}_2$Evac${}_{F2F}^w$ in which the two searchers need to evacuate in worst-case time no more than w, while still minimizing their average-case performance. One of our main contributions is a systematic method that allows us to perform both worst-case and average-case analysis for any evacuation algorithm that admits an analytic description. We apply our method to verify that previously known algorithms are not efficient (or not feasible) to ${}_2$Evac${}_{F2F}^w$, for certain values of w. As a result, we also motivate the introduction of three new families of evacuation algorithms that are feasible to ${}_2$Evac${}_{F2F}^w$ for a wide spectrum of values w, and that induce a continuous bound for the efficient (pareto) frontier for the underlying multi-objective optimization problem. For our results we employ a rigorous analysis for the worst-case performance of the new algorithms, and we rely on numerical computer-assisted calculations and on the aforementioned novel systematic method for estimating their average-case performance.

The formal definition of our problem, along with a high-level exposition of our results appears in Section 2.1. In Section 2.2 our cornerstone observation pertaining to a systematic process for computing the average-case (and worst-case) performance of any evacuation algorithm that admits a convenient representation (as described in Section 2.3). Then in Section 3 we analyze two basic (benchmark) algorithms for ${}_2$Evac${}_{F2F}^w$. This allows us to motivate our problem for a range of w values that are related to the benchmark algorithms. In the same section, we also show that the families of previously proposed evacuation algorithms fail to be efficient for ${}_2$Evac${}_{F2F}^w$. In Section 4 we present new families of evacuation algorithms, which is also one of our main contributions. For these algorithms we give a rigorous worst-case performance analysis in Section 5, and computer-assisted average-case performance analysis in Section 6, based upon our results in Section 2.2. The reader can also find in the same section a formal quantification of our results for ${}_2$Evac${}_{F2F}^w$. Lastly, in Section 7 we conclude by discussing our findings and propose some future directions.

2. Preliminaries

2.1. Problem Definition and Main Results

The geometric domain of ${}_2$Evac${}_{F2F}$ is a unit disk, centered at the origin of the Cartesian plane. Two unit-speed searchers, starting from the origin, can move anywhere in the disk, and aim to identify a hidden object (exit) located at its perimeter (boundary). The object can be identified only by co-located robot, i.e., a robot that passes over it.

The two robots search in parallel, and perform under a centralized setting, i.e., they know each other’s trajectories under the assumption that no exit is found. The underlying communication model is the so-called face-to-face that does not allow robots to exchange messages from distance, rather only when they meet. A feasible evacuation algorithm is a pair of trajectories, one for each robot, in which for every placement of the exit, both robots reach it eventually. For a technical reason, but also without loss of generality, we also require that robots will eventually stay at the exit idle. Placements of the exit i.e., instances to our problem, will be identified by $\mathrm{cycle}\left(x\right):=(cos\left(x\right),sin\left(x\right))$, where $x\in [0,2\pi )$. The evacuation time (cost) $\mathcal{C}\left(x\right)$ of a feasible evacuation algorithm on instance $\mathrm{cycle}\left(x\right)$ is defined as the first time until both robots reach the exit. t.

In this work we are concerned with determining trade-offs between the worst-case and the average-case performance (of uniform placements of the exit) of evacuation algorithms for ${}_2$Evac${}_{F2F}$. More specifically, we say that an evacuation algorithm $\mathcal{A}$ with evacuation cost $\mathcal{C}\left(x\right)$ on instance $\mathrm{cycle}\left(x\right)$ is $(a,w)$-efficient if

$$\begin{array}{cc}\hfill & \mathrm{Avg}\left(\mathcal{A}\right):={\mathrm{E}}_{x\in [0,2\pi )}\left[\mathcal{C}\left(x\right)\right]\le a,\hfill \\ \hfill & \mathrm{Wrs}\left(\mathcal{A}\right):=\underset{x\in [0,2\pi )}{sup}\left\{\mathcal{C}\left(x\right)\right\}\le w.\hfill \end{array}$$

where the expectation is with respect to the uniform distribution over $[0,2\pi )$. Special to our problem is that $\mathrm{Avg}\left(\mathcal{A}\right)$ can also be interpreted as the expected performance of a randomized algorithm based on $\mathcal{A}$. Indeed, consider an algorithm which first performs a random rotation of the disk around the origin of angle $\theta$, where $\theta$ is chosen uniformly at random from $[0,2\pi )$, and then simulates $\mathcal{A}$. Please note that theoretically, this step requires infinitely many random bits, but one can simulate with any precision by enough many random bits. This random step is equivalent to choosing a deployment point uniformly at random on the disk. Due to the symmetry of the domain, it is irrelevant where the adversary will place the unique exit, and hence the expected performance of this randomized algorithm equals $\mathrm{Avg}\left(\mathcal{A}\right)$.

For algorithms $\mathcal{A}\left(p\right)$ parameterized by parameter(s) p, the pair $\left(\mathrm{Avg}\left(\mathcal{A}\left(p\right)\right),\mathrm{Wrs}\left(\mathcal{A}\left(p\right)\right)\right)$ will correspond to a subset of ${\mathbb{R}}^2$ (and a curve if p is only one parameter) that we will refer to as the Efficient Frontier. We also adopt an optimization perspective of the problem, and we introduce the following optimization problem ${}_2$Evac${}_{F2F}^w$ on parameter w:

$$\begin{array}{cc}\hfill min& \frac{1}{2\pi }{\int }_0^{2\pi }\mathcal{C}\left(x\right)dx\hfill \\ \hfill \mathrm{s}.\mathrm{t}.& \mathcal{C}\left(x\right)\le w,\forall x\in [0,2\pi ).\hfill \end{array}\left({}_2\mathrm{Evac}{}_{F2F}^w\right)$$

Please note that the problem above is equivalent to the multi-objective optimization problem $min\{\mathrm{Avg}\left(\mathcal{A}\left(p\right)\right),\mathrm{Wrs}\left(\mathcal{A}\left(p\right)\right)\}$, and the conversion to the constrained problem above is due to the well-known $ϵ$-constraint method, e.g., see [58]. At the same time, no optimal lower bound is known for the worst-case cost in the case of unconstrained average-case cost, not to mention that lower bounds for similar problems are notoriously difficult. Consequently, under the current state-of-the-art it seems particularly challenging to determine the pareto frontier of the multi-objective optimization problem. Nevertheless, our arguments directly imply bounds for the pareto frontier.

As we show later, the values of w that make ${}_2$Evac${}_{F2F}^w$ interesting lie between some special values $w_1,w_2$. Values $w_1,w_2$ are associated with benchmark algorithms, ${\mathcal{B}}_1,{\mathcal{B}}_2$, where in particular $\mathrm{Wrs}\left({\mathcal{B}}_1\right)=w_1\approx 5.739,\mathrm{Avg}\left({\mathcal{B}}_1\right)=a_1\approx 5.1172,\mathrm{Wrs}\left({\mathcal{B}}_2\right)=w_2\approx 7.283,\mathrm{Avg}\left({\mathcal{B}}_1\right)=a_2\approx 7.28319$. As a result, the reader may think of ${\mathcal{B}}_1$ as being inefficient in average case and efficient in worst case. Similarly, ${\mathcal{B}}_2$ is inefficient in worst case and efficient in average case.

As is the case for many variations of ${}_2$Evac${}_{F2F}$, the cost of best solutions known are computed numerically. Our results pertain to upper bounds for a continuous spectrum of parameter w for problem ${}_2$Evac${}_{F2F}^w$. In particular we propose families of algorithms $\mathcal{A}$ (over some parameters) so that as their parameters vary, we obtain $\mathrm{Wrs}\left(\mathcal{A}\right)=w$ and $\mathrm{Avg}\left(\mathcal{A}\right)=g\left(w\right)$, for each $w\in [w_1,w_2]$. The curve $\left(g\right(w),w)$ summarizing our results is depicted in Figure 1, and it is later quantified in Theorem 7 (see Section 5).

Please note that an $(a,w)$-efficient algorithm gives a solution of value a for ${}_2$Evac${}_{F2F}^w$. Our approach to prove Theorem 7 is to define families of evacuation algorithms $\mathcal{A}\left(p\right)$ parameterized by parameter(s) p. We will prove that these algorithms are $\left(u\right(p),v(p\left)\right)$-efficient for some functions $u\left(p\right),v\left(p\right)$, and in particular the evaluation of the worst-case performance will be exact and monotone in p, while the computation of $v\left(p\right)$ will be computer-assisted. Then we will set $p=v^{-1}\left(w\right)$, and will be able to describe the average-case performance as a function of w as $g\left(w\right):=u\left(v^{-1}\left(w\right)\right)$.

2.2. Computing Evacuation Times

For any feasible evacuation algorithm, we denote by $\mathcal{S}\left(x\right)$, the first time, after spending time 1 to reach the perimeter that $\mathrm{cycle}\left(x\right)$ is visited by any robot. In other words, $\mathcal{S}\left(x\right)$ is the time robots spend searching till the exit is found for the first time, assuming that robots do not waste time in the interior of the circle before they start searching. Clearly, when a robot, say ${\mathcal{R}}_1$, locates the exit at $\mathrm{cycle}\left(x\right)$, it may attempt to catch ${\mathcal{R}}_2$ while moving along ${\mathcal{R}}_2$’s trajectory along the shortest line segment, say of length $\mathcal{E}\left(x\right)$. Once robots meet, they return together to $\mathrm{cycle}\left(x\right)$, inducing total evacuation cost $\mathcal{C}\left(x\right)=1+\mathcal{S}\left(x\right)+2\mathcal{E}\left(x\right).$

All existing results for ${}_2$Evac${}_{F2F}$, from a worst-case complexity perspective, rely on numerical computer-assisted estimation of ${sup}_x\mathcal{C}\left(x\right)$, after identifying properties of the maximizer. In this section, we elevate existing arguments, and we propose a generalized and unified approach for computing $\mathcal{C}\left(x\right)$, for any x and for any robot trajectories. For the sake of formality, as well as for practical purposes, robot trajectories will be defined by parametric functions $\mathcal{F}\left(t\right)=\left(f\right(t),g(t\left)\right)$, where $f,g:\mathbb{R}\mapsto \mathbb{R}$ are continuous and piecewise differentiable. In particular, search protocols for the two robots will be given by trajectories ${\mathcal{R}}_1\left(t\right),{\mathcal{R}}_2\left(t\right)$, where ${\mathcal{R}}_i\left(t\right)$ will denote the position of robot ${\mathcal{R}}_i$ at time $t\ge 0$. Therefore, any evacuation algorithm will be identified by a tuple $({\mathcal{R}}_1,{\mathcal{R}}_2)$. To simplify notation, we will only determine the trajectories from the moment the two robots reach the perimeter of the circle, and until the entire circle is searched (under the assumption that no exit is found), and we will silently assume that robots stay put after exploration is over.

Lemma 1.

Consider instance $\mathrm{cycle}\left(x\right)$ of ${}_2$Evac${}_{F2F}$, and suppose that for a feasible evacuation algorithm $({\mathcal{R}}_1,{\mathcal{R}}_2)$, robot 1 is the first robot that finds the exit. Then $\mathcal{E}\left(x\right)=\overline{t}-\mathcal{S}\left(x\right)$, where $\overline{t}=\overline{t}\left(x\right)$ is the smallest root, no less than $\mathcal{S}\left(x\right)$, of function

$$h_x\left(t\right):=∥{\mathcal{R}}_2\left(t\right)-{\mathcal{R}}_1\left(\mathcal{S}\left(x\right)\right)∥-t+\mathcal{S}\left(x\right).$$

(1)

Proof. 

The reader may consult Figure 2 that complements our argument.

First observe that $h_x\left(t\right)$ is continuous. If the robots find the exit together then result holds trivially. So we may assume that that the two robots are not co-located when the exit is found, in which case we have $h_x\left(\mathcal{S}\left(x\right)\right)>0$. At the same time, since the evacuation algorithm is feasible, ${\mathcal{R}}_2\left(t\right)$ is eventually a constant, and hence for big enough t we have that $h_x\left(t\right)$ becomes eventually negative. By the mean value theorem, there is $t_0>0$ for which $h_x\left(t_0\right)=0$.

Now consider the smallest positive root $\overline{t}$ of $h_x$, no less than $\mathcal{S}\left(x\right)$. At time $\overline{t}$, ${\mathcal{R}}_2$ is located at point ${\mathcal{R}}_2\left(\overline{t}\right)$, and it is $∥{\mathcal{R}}_2\left(\overline{t}\right)-{\mathcal{R}}_1\left(\mathcal{S}\left(x\right)\right)∥$ away from the location $\mathrm{cycle}\left(x\right)$ of the discovered exit. At the same time, ${\mathcal{R}}_1$ moves with speed 1 along the shortest path to catch ${\mathcal{R}}_2$ in her trajectory. Hence it takes ${\mathcal{R}}_1$ some $\overline{t}-\mathcal{S}\left(x\right)$ extra time from the moment the exit is found until she reaches point ${\mathcal{R}}_2\left(\overline{t}\right)$. By definition we have ${\mathcal{R}}_1\left(\overline{t}\right)={\mathcal{R}}_2\left(\overline{t}\right)$, and therefore $\mathcal{E}\left(x\right)=\overline{t}-\mathcal{S}\left(x\right)$ as claimed. □

For some special trajectories, $\mathcal{E}\left(x\right)$ admits a simpler description that we describe next. Before that, we introduce some notation pertaining to a function $\delta :[0,\pi ]\mapsto {\mathbb{R}}_{+}$, which we widely use in the remaining of the paper:

$$\delta \left(x\right):=\mathrm{unique}\mathrm{non}-\mathrm{negative}\mathrm{root}\left(\mathrm{regarding}d\right)\mathrm{of}‘‘2sin\left(x+\frac{d}{2}\right)=d{}^{″}.$$

(2)

To simplify notation, we will also abbreviate $\delta \left(x\right)$ by ${\delta }_x$. To show that ${\delta }_x$ is well-defined, consider function $f_x\left(d\right)=2sin\left(x+\frac{d}{2}\right)-d$. The derivative of the function is $f_x^{\prime }\left(d\right)=cosx+\frac{d}{2}-1\le 0$. Since $f_x^{\prime }\left(d\right)$ has also a unique root in $[0,\pi ]$, it follows that $f_x\left(d\right)$ is strictly decreasing. Observe now that $f_x\left(0\right)=2sin\left(x\right)\ge 0$, while $f_x\left(2\right)=2sin\left(x+1\right)-2\le 0$. We conclude that due to the strict monotonicity of $f_x\left(d\right)$, the latter function has indeed unique root in $d\in [0,2]$. Finally, it is easy to see that $f_x\left(d\right)<0$ when $d>2$.

Lemma 2.

For some instance $\mathrm{cycle}\left(x\right)$ of ${}_2$Evac${}_{F2F}$, suppose that for a feasible evacuation algorithm $({\mathcal{R}}_1,{\mathcal{R}}_2)$, ${\mathcal{R}}_1$ is the finder of the exit, say at time $t_0=\mathcal{S}\left(x\right)$. Assume that both ${\mathcal{R}}_1\left(t_0\right),{\mathcal{R}}_2\left(t_0\right)$ lie on the circle at arc distance $2\alpha$, and suppose that ${\mathcal{R}}_2$’s movement is along the perimeter of the circle toward the complementary arc of length $2\pi -\alpha$. Then, $\mathcal{E}\left(x\right)={\delta }_{\alpha }$.

Proof. 

The lemma follows by applying transformation $t-\mathcal{S}\left(x\right)=d$ in the definition of $h_x\left(t\right)$ in Lemma 1, so that $\mathcal{E}\left(x\right)=t-\mathcal{S}\left(x\right)=d$. □

We are ready to conclude with a corollary that will be handy for computing evacuation times numerically, and without relying on excessive case analysis, as was the case before.

Corollary 1.

Consider feasible evacuation algorithm $({\mathcal{R}}_1,{\mathcal{R}}_2)$ for ${}_2$Evac${}_{F2F}$. For any instance $\mathrm{cycle}\left(x\right)$ for which ${\mathcal{R}}_1$ is the exit finder, the evacuation cost can be computed as $\mathcal{C}\left(x\right)=1+2\overline{t}-\mathcal{S}\left(x\right),$ where $\overline{t}=\overline{t}\left(x\right)$ is the smallest root, at least $\mathcal{S}\left(x\right)$, of $h_x\left(t\right):=∥{\mathcal{R}}_2\left(t\right)-{\mathcal{R}}_1\left(\mathcal{S}\left(x\right)\right)∥-t+\mathcal{S}\left(x\right)$.

2.3. Trajectory Description

Robot trajectories will be described in phases. We will always omit the “deployment phase”, i.e., the movement from the circle center to its perimeter, and we will only describe the trajectories from the moment robots start searching the circle. In each phase, robot ${\mathcal{R}}_{}$, will be moving between two explicit points, either along an arc, or along a line segment (chord of an arc), see Observations 1 and 2 below. We will summarize robot trajectories in tables of the following format.

Robot	Phase #	Trajectory	Duration
${\mathcal{R}}_{}$	1	${\mathcal{R}}_{}\left(t\right)$	$t_1$
	2	${\mathcal{R}}_{}\left(t\right)$	$t_2$
	⋮		⋮

To ease notation, trajectory ${\mathcal{R}}_{}\left(t\right)$ of phase i will be described with parametric equations as if the time is reset to 0 after time $t_0+t_1+t_2+\dots +t_{i-1}$, where $t_0=1$ (this is the time that robots reach the circle). The two fundamental trajectory components are movements along arcs and movements along line segments.

Observation 1.

Let $b\in [0,2\pi )$ and $\sigma \in \{-1,1\}$. The trajectory of an object moving at speed 1 on the perimeter of a unit circle with initial location $\mathrm{cycle}\left(b\right)$ is given by the parametric equation $\mathrm{cycle}(\sigma t+b)=(cos\left(\sigma t+b\right),sin\left(\sigma t+b\right)).$ If $\sigma =1$ the movement is counterclockwise (ccw), and clockwise (cw) otherwise.

Proof. 

It is immediate that when $t=1$, the object is located at $\mathrm{cycle}\left(b\right)$. Its speed is given by calculating $∥\frac{\partial }{\partial t}\mathrm{cycle}(\sigma t+b)∥$. Indeed, we have

$${\left(\frac{d}{dt}cos\left(\sigma t+b\right)\right)}^2+{\left(\frac{d}{dt}sin\left(\sigma t+b\right)\right)}^2={\sigma }^2{\left(-sin\left(\sigma t+b\right)\right)}^2+{\sigma }^2{\left(cos\left(\sigma t+b\right)\right)}^2=1,$$

as wanted. □

Observation 2.

Consider distinct points $A=(a_1,a_2),B=(b_1,b_2)$ in ${\mathbb{R}}^2$. The trajectory of a speed 1 object moving along the line passing through $A,B$ and with initial position A is given by the parametric equation

$$\mathrm{line}(A,B,t):=\left(\frac{b_1-a_1}{∥A-B∥}t+a_1,\frac{b_2-a_2}{∥A-B∥}t+a_2\right).$$

Proof. 

By definition, the parametric equation above corresponds to a line. Elementary calculations show that $\mathrm{line}(A,B,0)=A$ and $\mathrm{line}(A,B,∥A-B∥)=B$, that is the object starts at A, and that it passes through B. Object speed is calculated as $∥\frac{\partial }{\partial t}\mathrm{line}(A,B,t)∥$. In that direction we have

$${\left(\frac{d}{dt}\left(\frac{b_1-a_1}{∥A-B∥}t+a_1\right)\right)}^2+{\left(\frac{d}{dt}\left(\frac{b_2-a_2}{∥A-B∥}t+a_2\right)\right)}^2={\left(\frac{b_1-a_1}{∥A-B∥}\right)}^2+{\left(\frac{b_2-a_2}{∥A-B∥}\right)}^2=1$$

as promised. □

Finally, the analysis of our algorithm trajectories will give rise to several constants. For the reader’s convenience, we list here the numerical values of the most common constants that will be encountered later. $w_1\approx 5.73906,w_0\approx 6.11953,w^{\prime }\approx 6.12851,w_2\approx 7.28319,{\alpha }^{\prime }\approx 1.15468,\overline{\alpha }\approx 1.54419,$ ${\beta }^{\prime }\approx 0.0241653,{\beta }_0\approx 0.04388.$

All constants are formally defined when they are first introduced.

3. Two Benchmark Algorithms and Motivation

In this section, we describe two benchmark algorithms for ${}_2$Evac${}_{F2F}$, as well as perform average-case analysis to algorithms previously proposed in the literature. The reader may consult Figure 3 for the algorithms analyzed in this section.

Czyzowicz et al. [1] were the first to introduce an evacuation algorithm for ${}_2$Evac${}_{F2F}$, which we denote here by ${\mathcal{B}}_1$ (see Figure 3 on the left).

Definition 1

(Benchmark Algorithm ${\mathcal{B}}_1$). For all $t\in [0,\pi ]$, ${\mathcal{R}}_1\left(t\right)=cycle\left(t\right)$ and ${\mathcal{R}}_2\left(t\right)=cycle(-t)$.

Observation 3.

Benchmark Algorithm ${\mathcal{B}}_1$ is $(5.1172,5.73906)$-efficient.

Proof. 

Please note that it takes time $\pi$ to search the entire circle, and that the two trajectories are symmetric with respect to horizontal axis. Therefore, we may assume that the instance $\mathrm{cycle}\left(x\right)$ satisfies $x\in [0,\pi ]$.

Clearly, for any such x, we have that $\mathcal{S}\left(x\right)=x$. By Lemma 2, we have that $\mathcal{C}\left(x\right)=1+\mathcal{S}\left(x\right)+2\mathcal{E}\left(x\right)=1+x+2{\delta }_x$. Numerical calculations (software assisted) show that

$$\begin{array}{cc}\hfill & \mathrm{Wrs}\left({\mathcal{B}}_1\right)=\underset{x\in [0,\pi ]}{sup}\left\{\mathcal{C}\left(x\right)\right\}=\underset{x\in [0,\pi ]}{sup}\{1+x+2{\delta }_x\}\approx 5.73906,\hfill \\ \hfill & \mathrm{Avg}\left({\mathcal{B}}_1\right)={\mathrm{E}}_{x\in [0,\pi ]}\left[\mathcal{C}\left(x\right)\right]=\frac{1}{\pi }{\int }_{x=0}^{\pi }\left(1+x+2{\delta }_x\right)dx\approx 5.1172.\hfill \end{array}$$

 □

${\mathcal{B}}_1$ should be understood as being efficient in the worst case, but inefficient on average. The claim becomes transparent by introducing the following naive algorithm for ${}_2$Evac${}_{F2F}$ that we depict in the middle of Figure 3.

Definition 2

(Benchmark Algorithm ${\mathcal{B}}_2$). For each $t\in [0,2\pi ]$, ${\mathcal{R}}_1\left(t\right)={\mathcal{R}}_2\left(t\right)=cycle\left(t\right)$.

Observation 4.

Benchmark Algorithm ${\mathcal{B}}_2$ is $(1+\pi ,1+2\pi )$-efficient.

Proof. 

It is easy to see that for all $x\in [0,2\pi )$ we have $\overline{t}\left(x\right)=\mathcal{S}\left(x\right)=x$ and $\mathcal{E}\left(x\right)=0$. Therefore $\mathcal{C}\left(x\right)=1+x$, and hence

$$\begin{array}{cc}\hfill & \mathrm{Wrs}\left({\mathcal{B}}_2\right)=\underset{x\in [0,2\pi )}{sup}\left\{\mathcal{C}\left(x\right)\right\}=1+2\pi ,\hfill \\ \hfill & \mathrm{Avg}\left({\mathcal{B}}_2\right)={\mathrm{E}}_{x\in [0,2\pi )}\left[\mathcal{C}\left(x\right)\right]={\int }_{x=0}^{2\pi }\left(1+x\right)dx=1+\pi .\hfill \end{array}$$

 □

${\mathcal{B}}_2$ should be understood as highly efficient on average, but inefficient in the worst case. Moreover, it should be clear that ${\mathcal{B}}_1,{\mathcal{B}}_2$ are feasible solutions to ${}_2$Evac${}_{F2F}^w$, for $w=5.1172$ and $w=1+2\pi$, respectively. We conjecture that ${\mathcal{B}}_1$ is indeed the optimal evacuation algorithm among all algorithms with worst-case performance no more than $1+2\pi$. At the same time, below we show that ${\mathcal{B}}_2$ is the best algorithm for ${}_2$Evac${}_{F2F}^w$, when $w=5.1172$, among those previously used to improve upon the worst-case performance up to the third decimal. The importance of this observation is two-fold; first we are motivated to study ${}_2$Evac${}_{F2F}^w$ for the entire spectrum of $w\in [\mathrm{Wrs}\left({\mathcal{B}}_1\right),\mathrm{Wrs}\left({\mathcal{B}}_2\right)]$, and second we deduce that in order to perform well on average, we need to devise and analyze new evacuation algorithms.

Upper bounds for the worst-case performance of ${\mathcal{B}}_1$ were later improved first to 5.628 [26], then to 5.625 [27], and then to 5.623 [28]. The main idea behind the improvement is to understand the monoticity of $\mathcal{C}\left(x\right)$ for algorithm ${\mathcal{B}}_1$. Indeed, the following lemma was implicit in both [26,27], and can be obtained numerically.

Lemma 3.

There is ${\alpha }_0$, where ${\alpha }_0\approx 0.96782$, so that evacuation cost $\mathcal{C}\left(x\right)$ of ${\mathcal{B}}_1$ for ${}_2$Evac${}_{F2F}$ on instance $\mathrm{cycle}\left(x\right)$ is strictly increasing for $x\in [0,{\alpha }_0]$, and strictly decreasing in $x\in [{\alpha }_0,\pi ]$. In particular, $\mathrm{Wrs}\left({\mathcal{B}}_1\right)=\mathcal{C}\left({\alpha }_0\right)\approx 5.73906$.

Consider now an execution of ${\mathcal{B}}_1$ in which one of the robots, say ${\mathcal{R}}_2$ continues searching on the circle and is close to approach a location that would be the meeting point if the instance was $\mathrm{cycle}\left({\alpha }_0\right)$. In an attempt to help expedite a potential meeting (in case ${\mathcal{R}}_1$ is approaching) and effectively reducing the cost of the worst case, ${\mathcal{R}}_2$ would make a minor detour toward the interior of the disk, before returning back to the exploration of the circle. This simple idea was explored in [26] and in [27] where the following family of algorithms were introduced, parameterized by $\alpha \in [0,\pi ]$ and point B within the unit disk, see also right of Figure 3 (the simplified version presented here is due to [27]).

Definition 3

(1-Detour Algorithm ${\mathcal{A}}_0(\alpha ,B)$). For all $t\in [0,\pi +2∥\mathrm{cycle}\left(\alpha \right)-B∥]$, the trajectory of ${\mathcal{R}}_1$ is defined as

Robot	Phase #	Trajectory	Duration
${\mathcal{R}}_1$	1	$\mathrm{cycle}\left(t\right)$	$\alpha$
	2	$\mathrm{line}\left(\mathrm{cycle}\right(\alpha ),B,t)$	$∥\mathrm{cycle}\left(\alpha \right)-B∥$
	3	$\mathrm{line}(B,\mathrm{cycle}(\alpha ),t)$	$∥\mathrm{cycle}\left(\alpha \right)-B∥$
	4	$\mathrm{cycle}(t+\alpha )$	$\pi -\alpha$

The trajectory of ${\mathcal{R}}_2$ is symmetric with respect to the horizontal axis.

The crux of the contribution of [26] was to prove that there exists $\alpha ,B$ for which the worst-case performance is no more than 5.644 (and a delicate refinement is needed to achieve 5.628). Notably, their analysis is tedious and lengthy, whereas we can obtain the same result, relying again on numerical calculations, with minimal effort. Then, [27] proposed variations of ${\mathcal{A}}_0(\alpha ,B)$ in which each robot performs more than 1 detours (see Phases 2,3 of ${\mathcal{A}}_0(\alpha ,B)$), giving rise to [28]. Hence, t-detour algorithms are parameterized by a sequence ${\alpha }_1,\dots ,{\alpha }_t$, where ${\alpha }_i\ge 0$ and ${\sum }_i{\alpha }_i\le \pi$, and points $B_i$ in the disk. Even 2-detour algorithms achieve worst-case performance 5.623, while for each $t\ge 2$, t-detour algorithms do induce strictly improved performance (for appropriate choices of the parameters) but the improvement seems to be negligible.

Motivated by the results in [26,27], one is tempted to ask whether any algorithm in the family ${\mathcal{A}}_0(\alpha ,B)$ improves upon ${\mathcal{B}}_1$ with respect to the average-case analysis. The next claim is due to exhaustive, computer-assisted numerical calculations, see also Figure 4.

Theorem 5.

For every $\alpha \in [0,\pi )$ and for every B in the unit disk $\mathrm{Avg}\left({\mathcal{A}}_0(\alpha ,B)\right)\ge \mathrm{Avg}\left({\mathcal{B}}_1\right)$.

Theorem 5 provides strong motivation for studying problem ${}_2$Evac${}_{F2F}^w$, since it shows that in order to establish good upper bounds, i.e., our main results depicted in Figure 1 and quantified later in Theorem 7, one needs to employ new evacuation algorithms. Recall that even $\mathrm{Wrs}\left({\mathcal{B}}_1\right)$ and $\mathrm{Wrs}\left({\mathcal{A}}_0(\alpha ,B)\right)$ were estimated with computer-assisted calculations. Due to the nature of the problem, we are bound to rely on computer-assisted calculations as well. Notably, our much more intense computational work is feasible only because we employ the new method for computing evacuation times due to Corollary 1 and Definition 3 of ${\mathcal{A}}_0(\alpha ,B)$ trajectories. Overall, to verify Theorem 5 we compute pairs $\left(\mathrm{Avg}\left({\mathcal{A}}_0(\alpha ,B)\right),\mathrm{Wrs}\left({\mathcal{A}}_0(\alpha ,B)\right)\right)$ for more than 500,000 different parameter values and we depict them in Figure 4.

4. New Evacuation Algorithms

In this section, we propose families of evacuation algorithms for problem ${}_2$Evac${}_{F2F}^w$, for the entire spectrum of $w\in [\mathrm{Wrs}\left({\mathcal{B}}_1\right),\mathrm{Wrs}\left({\mathcal{B}}_2\right)]$. Our algorithms are summarized in Figure 5.

First we define families of evacuation algorithms that, as we show next, perform well for ${}_2$Evac${}_{F2F}^w$ in the “neighborhood of ${\mathcal{B}}_1$”, i.e., for w close to $\mathrm{Wrs}\left({\mathcal{B}}_1\right)$. Our algorithms are parameterized by $\alpha$, and their circle exploration lasts $2\pi -\alpha$.

Definition 4

(Algorithm ${\mathcal{A}}_1\left(\alpha \right)$). For all $t\in [0,2\pi -\alpha ]$, the trajectory of ${\mathcal{R}}_1$ is defined as

Robot	Phase #	Trajectory	Duration
${\mathcal{R}}_1$	1	$\mathrm{cycle}\left(t\right)$	$\alpha$
	2	$\mathrm{line}(\mathrm{cycle}\left(\alpha \right),\mathrm{cycle}(-\alpha -{\delta }_{\alpha }),t)$	${\delta }_{\alpha }$
	3	$\mathrm{cycle}(-\alpha -{\delta }_{\alpha }-t)$	$2\pi -2\alpha -{\delta }_{\alpha }$

where ${\delta }_a$ is defined in (2). The trajectory of ${\mathcal{R}}_2$ is defined as ${\mathcal{R}}_2\left(t\right)=\mathrm{cycle}(-t)$, for all $t\in [0,2\pi -\alpha ]$.

${\mathcal{A}}_1$ is depicted in Figure 5 on the left. At a high level ${\mathcal{A}}_1\left(\alpha \right)$ is a modification of ${\mathcal{B}}_1$ that is based on the following idea. The execution of ${\mathcal{A}}_1\left(\alpha \right)$ is the same as in ${\mathcal{B}}_1$ until each robot searches an arc of length $\alpha$ (and hence $\mathcal{A}\left(\pi \right)$ coincides with ${\mathcal{B}}_1$). After time $\alpha$, ${\mathcal{R}}_1$ abandons her trajectory and catches ${\mathcal{R}}_2$, on the perimeter of the circle resembling a trajectory as if the exit was located at ${\mathcal{R}}_1\left(\alpha \right)$. It is not difficult to see that the definition of ${\delta }_{\alpha }$ above satisfies ${\mathcal{R}}_1(\alpha +{\delta }_{\alpha })={\mathcal{R}}_2(\alpha +{\delta }_{\alpha })=\mathrm{cycle}(-\alpha -{\delta }_{\alpha })$.

Next we define a family of algorithms ${\mathcal{A}}_2$ which, as we show later, perform well in the “neighborhood of ${\mathcal{B}}_2$”, i.e., for w close to $\mathrm{Wrs}\left({\mathcal{B}}_2\right)$. For this recall definition (2) of ${\delta }_a$. We let ${\gamma }_0\approx 2.2412$ be the root of $2\alpha +{\delta }_{\alpha /2}=2\pi$. For every $\alpha \le {\gamma }_0$ we define a family of algorithms on parameter $\alpha$ whose circle exploration lasts $2\pi -\alpha$.

Definition 5

(Algorithm ${\mathcal{A}}_2\left(\alpha \right)$). For all $t\in [0,2\pi -\alpha ]$, the trajectory of ${\mathcal{R}}_1$ is defined as

Robot	Phase #	Trajectory	Duration
${\mathcal{R}}_1$	1	$\mathrm{cycle}\left(t\right)$	$\alpha$
	2	$\mathrm{line}(\mathrm{cycle}\left(\alpha \right),\mathrm{cycle}(2\alpha +{\delta }_{\alpha /2}),t)$	${\delta }_{\alpha /2}$
	3	$\mathrm{cycle}(2\alpha +{\delta }_{\alpha /2}+t)$	$2\pi -2\alpha -{\delta }_{\alpha /2}$

The trajectory of ${\mathcal{R}}_2$ is defined as ${\mathcal{R}}_2\left(t\right)=\mathrm{cycle}(\alpha +t)$, for all $t\in [0,2\pi -\alpha ]$.

${\mathcal{A}}_2$ is depicted in the middle of Figure 5. The condition that $\alpha \le {\gamma }_0$ is added for simplicity to ensure that the latest catching point occurs while the other robot is still searching, and is not mandatory. At a high level ${\mathcal{A}}_2\left(\alpha \right)$ is a generalization of ${\mathcal{B}}_2$ (note that ${\mathcal{A}}_2\left(0\right)={\mathcal{B}}_2$). For the first $\alpha$ time units, robots search in the same direction until ${\mathcal{R}}_1$ arrives at the deployment point of ${\mathcal{R}}_2$. Then, ${\mathcal{R}}_1$ catches ${\mathcal{R}}_2$ on the circle, as if the exit was located at ${\mathcal{R}}_1\left(\alpha \right)$ (which by Lemma 2 happens in ${\delta }_{\alpha /2}$ extra time).

Finally, we introduce a family of evacuation algorithms which will perform well for ${}_2$Evac${}_{F2F}^w$ for intermediate values of $w\in [\mathrm{Wrs}\left({\mathcal{B}}_1\right),\mathrm{Wrs}\left({\mathcal{B}}_2\right)]$. For this we generalize family ${\mathcal{A}}_2$ so that the two robots perform two alternating jumps, with parameters $\alpha ,\beta$ satisfying $2\alpha +2\beta +{\delta }_{(\alpha +\beta )/2}+{\delta }_{\beta /2}\le 2\pi$, see right of Figure 5.

Definition 6

(Algorithm ${\mathcal{A}}_2^{\prime }(\alpha ,\beta )$). For notational convenience, we set ${\zeta }_{\alpha ,\beta }:=2\alpha +\beta +{\delta }_{(\alpha +\beta )/2}$. For all $t\in [0,2\pi -\alpha -\beta ]$, the trajectories of ${\mathcal{R}}_1,{\mathcal{R}}_2$ are defined as follows

Robot	Phase #	Trajectory	Duration
${\mathcal{R}}_1$	1	$\mathrm{cycle}\left(t\right)$	$\alpha$
	2	$\mathrm{line}(\mathrm{cycle}\left(\alpha \right),\mathrm{cycle}\left({\zeta }_{\alpha ,\beta }\right),t)$	${\delta }_{(\alpha +\beta )/2}$
	3	$\mathrm{cycle}\left({\zeta }_{\alpha ,\beta }+t\right)$	$2\pi -2\alpha -\beta -{\delta }_{(\alpha +\beta )/2}$
${\mathcal{R}}_2$	1	$\mathrm{cycle}(\alpha +t)$	$\alpha +\beta +{\delta }_{(\alpha +\beta )/2}$
	2	$\mathrm{line}(\mathrm{cycle}\left({\zeta }_{\alpha ,\beta }\right),\mathrm{cycle}\left({\zeta }_{\alpha ,\beta }+{\delta }_{\beta /2}\right),t)$	${\delta }_{\beta /2}$
	3	$\mathrm{cycle}\left({\zeta }_{\alpha ,\beta }+\beta +{\delta }_{\beta /2}+t\right)$	$2\pi -2\alpha -2\beta -{\delta }_{(\alpha +\beta )/2}-{\delta }_{\beta /2}$

Next we describe the meaning of parameters $\alpha ,\beta$ of the Robot trajectories above. As in the family of algorithms ${\mathcal{A}}_2$, parameter $\alpha$ represents the arc distance the two robots have before the one preceding decides to jump ahead. In ${\mathcal{A}}_2$ the two robots meet again once the jumper reaches the perimeter of the circle. In ${\mathcal{A}}_2^{\prime }$ the jumper deploys a little further away on the circle so that when the other robot reaches the deployment point of the jumper, the two robots are at arc distance $\beta$. As a result, the time it takes both robots to complete searching the entire circle is $2\pi -\alpha -\beta$, as well as ${\mathcal{A}}_2(\alpha ,0)$ coincides with ${\mathcal{A}}_2\left(\alpha \right)$. Finally, note that even though ${\mathcal{A}}_2^{\prime }$ will be eventually invoked for seemingly restricted values of $\beta$ ($\beta \le {\beta }_0\approx 0.04388$), the deviation in the performance will be significant enough (e.g., ${\delta }_{{\beta }_0/2}\approx 0.977997$) to account for its use in our upper bounds.

5. Worst-Case Performance Analysis

In this section, we perform worst-case analysis for all algorithmic families ${\mathcal{A}}_1,{\mathcal{A}}_2,{\mathcal{A}}_2^{\prime }$ with respect to their parameters. Notably, results in this section are quantified formally and exactly by closed formulas. At a high level, each of ${\mathcal{A}}_1,{\mathcal{A}}_2,{\mathcal{A}}_2^{\prime }$ will be invoked to solve ${}_2$Evac${}_{F2F}^w$ for different values of $w\in [\mathrm{Wrs}\left({\mathcal{B}}_1\right),\mathrm{Wrs}\left({\mathcal{B}}_2\right)]$, and each of them will have competitive average-case performance for the corresponding worst-case performance w. As an easy warm-up, we analyze ${\mathcal{A}}_1$.

Lemma 4

(Worst-Case Analysis for ${\mathcal{A}}_1$). Let $\overline{\alpha }=1+2\pi -w_1$, where $w_1=\mathrm{Wrs}\left({\mathcal{B}}_1\right)$. Then, for all $\alpha \in [0,\pi ]$, we have that

$$\mathrm{Wrs}\left({\mathcal{A}}_1\left(\alpha \right)\right)=\left\{\begin{array}{cc}1+2\pi -\alpha \hfill & ,\forall \alpha \in [0,\overline{\alpha })\hfill \\ \mathrm{Wrs}\left({\mathcal{B}}_1\right)\hfill & ,\forall \alpha \in [\overline{\alpha },\pi ]\hfill \end{array}\right..$$

Proof. 

First it is easy to show that the worst-case evacuation time is induced either when ${\mathcal{R}}_1$ finds the exit while moving from $\mathrm{cycle}\left(0\right)$ to $\mathrm{cycle}\left(\alpha \right)$, or while ${\mathcal{R}}_1,{\mathcal{R}}_2$ are exploring the circle together (after having met). By Lemma 2, the cost in the first case would be

$$\underset{0\le x\le \alpha }{max}\{1+x+2{\delta }_x\}=\left\{\begin{array}{cc}1+\alpha +2{\delta }_{\alpha }\hfill & ,\mathrm{if}\alpha \le {\alpha }_0\hfill \\ \mathrm{Wrs}\left({\mathcal{B}}_1\right)\hfill & ,\mathrm{otherwise}\hfill \end{array}\right.$$

where the values of the piecewise function above follow from Lemma 3. In the other case, the worst placement of exit is obtained using instances $\mathrm{cycle}(\alpha +ϵ)$ for arbitrary small values of $ϵ>0$ in which case the evacuation cost becomes $1+2\pi -\alpha$.

Overall, is is easy to see that $1+{\alpha }_0+2{\delta }_{{\alpha }_0}\le 1+2\pi -{\alpha }_0$ showing that the dominant evacuation cost when $\alpha \le \overline{\alpha }$ is $1+2\pi -\alpha$. For $\alpha >\overline{\alpha }$ the evacuation cost becomes equal to $w_1$. □

In a similar fashion, we can easily analyze ${\mathcal{A}}_2$.

Lemma 5

(Worst-Case Analysis for ${\mathcal{A}}_2$). For all $\alpha \le \pi -2$, we have $\mathrm{Wrs}\left({\mathcal{A}}_2\left(\alpha \right)\right)=1+2\pi -\alpha$.

Proof. 

We distinguish three cases as to where the exit is. If $x\in [0,\alpha )$, then the worst instance $\mathrm{cycle}\left(x\right)$ is when $x=\alpha -ϵ$ for arbitrarily small $ϵ>0$, and the cost is $1+\alpha +2{\delta }_{\alpha /2}$. In the second case $x\in [\alpha ,2\alpha +{\delta }_{\alpha /2})$ and it is not difficult to see that the worst-case induced cost in this case is not more than that of the first case. Finally, in the third case $x\in [2\alpha +{\delta }_{\alpha /2},2\pi )$, and the two robots move together, so the total cost, in the worst-case, is $1+2\pi -\alpha$, when $x=2\pi -ϵ$ for arbitrarily small $ϵ>0$. It is not difficult to see that the dominant case is actually the third one, and in fact the two cases induce the same cost when $\pi =\alpha +{\delta }_{\alpha /2}$. By the definition of ${\delta }_{\alpha /2}$ we know that ${\delta }_{\alpha /2}=2sin\left(\frac{\alpha +{\delta }_{\alpha /2}}{2}\right)=2sin\left(\pi /2\right)=2$. Hence, the costs become equal when $\alpha =\pi -2$. □

Next, we analyze ${\mathcal{A}}_2^{\prime }(\alpha ,\beta )$, which requires more technical arguments. For this we will invoke ${\mathcal{A}}_2^{\prime }$ only for special parameters, whose choice is motivated by the following observation pertaining to the performance of ${\mathcal{A}}_2$ (whose generalization is ${\mathcal{A}}_2^{\prime }$). From the proof of Lemma 5, it follows that among all algorithms ${\mathcal{A}}_2\left(\alpha \right)$, where $\alpha \le {\gamma }_0$ (see discussion before Definition 5), the one with minimum worst-case evacuation cost is ${\mathcal{A}}_2(\pi -2)$, and the cost becomes $3+\pi$. In fact, for all $w\in [3+\pi ,1+2\pi ]$ there are two different values of $\alpha$ for which $\mathrm{Wrs}\left({\mathcal{A}}_2\left(\alpha \right)\right)=w$, and we restrict $\alpha \in [0,\pi -2]$ so that we obtain evacuation algorithms with minimum average-case cost. Moreover, $\alpha =\pi -2$ is the only parameter for which $\mathrm{Wrs}\left({\mathcal{A}}_2\left(\alpha \right)\right)=3+\pi$ and as a byproduct, it is the algorithm in the family ${\mathcal{A}}_2$ that minimizes the worst-case.

By Lemma 5 we know that as $\beta \to 0$, the value of $\alpha$ that minimizes $\mathrm{Wrs}\left({\mathcal{A}}_2^{\prime }(\alpha ,\beta )\right)$ approaches $\pi -2$. That value of $\alpha$ is what made the evacuation cost of ${\mathcal{A}}_2\left(\alpha \right)$ attain the same value in two different (worst-case) exit placements. Motivated by this, and for values of $\beta >0$ not too big, we still find the optimal choices of $\alpha$ that minimize the worst-case performance.

Lemma 6

(Worst-Case Analysis for ${\mathcal{A}}_2^{\prime }$). Let ${\beta }_0=0.0438855$, and set ${\alpha }_{\beta }:=\pi -\beta /2-2cos\left(\beta /4\right)$. Then for all $\beta \in [0,{\beta }_0]$ we have $\mathrm{Wrs}\left({\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )\right)=1+\pi -\beta /2+2cos\left(\beta /4\right).$

Proof. 

Let $w\left(\beta \right)=1+\pi -\beta /2+2cos\left(\beta /4\right)$. First we show that $w\left(\beta \right)$ is the worst-case performance of ${\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )$ for two specific placements of the exit.

We proceed by describing evacuation cost $\mathcal{C}\left(x\right)$ assuming two arbitrary $\alpha ,\beta$ for two different instances $\mathrm{cycle}\left(x\right)$. Using Lemma 2, we see that

$$\underset{ϵ\to 0^{+}}{lim}\mathcal{C}(\alpha -ϵ)=1+\underset{ϵ\to 0^{+}}{lim}\mathcal{S}(\alpha -ϵ)+2\underset{ϵ\to 0^{+}}{lim}\mathcal{E}(\alpha -ϵ)=1+\alpha +2{\delta }_{\alpha /2}.$$

(3)

Since the total search time is $2\pi -\alpha -\beta$, we also see that

$$\underset{ϵ\to 0^{+}}{lim}\mathcal{C}(2\pi -ϵ)=1+2\pi -\alpha -\beta .$$

(4)

Now we claim that (3), (4) are equal when $\alpha ={\alpha }_{\beta }$. Indeed, equating (3), (4) gives

$$a+{\delta }_{\alpha /2}=\pi -\beta /2.$$

(5)

However, then, using (2), we see that

$${\delta }_{\alpha /2}=2sin\left(\frac{\alpha +{\delta }_{\alpha /2}}{2}\right)=2sin\left(\frac{\pi -\beta /2}{2}\right)=2cos\left(\beta /4\right).$$

(6)

Substituting (6) into (5), we see that the value of $\alpha$ for which (3), (4) are equal satisfies $\alpha =\pi -\beta /2-2cos\left(\beta /4\right)$, as promised. Substituting this special value of $\alpha ={\alpha }_{\beta }$ either in (3) or in (4) induces evacuation cost $w\left(\beta \right)=1+\pi -\beta /2+2cos\left(\beta /4\right)$.

Next we show that as long as $\beta$ is not too big, $w\left(\beta \right)$ is indeed the worst-case evacuation cost. We consider the following cases $x\in I_i$, $i=1,\dots ,4$ for possible instances $\mathrm{cycle}\left(x\right)$;

$$\begin{array}{cc}\hfill I_1:=& [0,\alpha ),\hfill \\ \hfill I_2:=& [\alpha ,2\alpha +\beta +{\delta }_{(\alpha +\beta )/2}),\hfill \\ \hfill I_3:=& [2\alpha +\beta +{\delta }_{(\alpha +\beta )/2},2\alpha +2\beta +{\delta }_{(\alpha +\beta )/2}+{\delta }_{\beta /2}),\hfill \\ \hfill I_4:=& [2\alpha +2\beta +{\delta }_{(\alpha +\beta )/2}+{\delta }_{\beta /2},2\pi ).\hfill \end{array}$$

Clearly, (3), (4) demonstrate the worst-case evacuation costs for instances in $I_1,I_4$, respectively, and the cost in both cases, for $\alpha ={\alpha }_{\beta }$ is equal to $w\left(\beta \right)$.

If $x\in I_2$ then $\mathcal{C}\left(x\right)=1+\mathcal{S}\left(x\right)+2\mathcal{E}\left(x\right)$. It is easy to see that both $\mathcal{S}\left(x\right),\mathcal{E}\left(x\right)$ are monotone in $I_2$, so the worst-case evacuation in this case is

$$\underset{ϵ\to 0^{+}}{lim}\mathcal{C}(2{\alpha }_{\beta }+\beta +{\delta }_{({\alpha }_{\beta }+\beta )/2}-ϵ)=1+{\alpha }_{\beta }+\beta +{\delta }_{({\alpha }_{\beta }+\beta )/2}+2{\delta }_{\beta /2}.$$

(7)

Denote ${\delta }_{\beta /2}$ satisfying (2) by ${\delta }_{\beta }^{\prime }$. Using (2) and the definition of ${\alpha }_{\beta }$, we see that

$${\delta }_{({\alpha }_{\beta }+\beta )/2}=2sin\left(\frac{{\alpha }_{\beta }+\beta +{\delta }_{({\alpha }_{\beta }+\beta )/2}}{2}\right)=2cos\left(cos\left(\beta /4\right)-\beta /4-{\delta }_{({\alpha }_{\beta }+\beta )/2}\right).$$

For simplicity, we denote ${\delta }_{({\alpha }_{\beta }+\beta )/2}$ that satisfies the equation above by ${\delta }_{\beta }^{″}$. Then, continuing from (7), the worst-case evacuation cost when $x\in I_2$ becomes $1+\pi +\beta /2-2cos\left(\beta /4\right)+{\delta }_{\beta }^{″}+2{\delta }_{\beta }^{\prime }$, an expression that depends exclusively on $\beta$. The latter cost is no more than $w\left(\beta \right)$ if and only if $4cos\left(\beta /4\right)-\beta -{\delta }_{\beta }^{″}-2{\delta }_{\beta }^{\prime }\ge 0$, and numerically we verify that this is satisfied as long as $\beta \le {\beta }_0$ (see also Figure 6).

Finally, it is easy to verify that ${\delta }_{\beta /2}$ and $|I_4|$ are increasing and decreasing, respectively, for $\beta \le {\beta }_0$, and that ${\delta }_{{\beta }_0/2}=0.977997\le 1.01099=\left|I_4\right|$ (for $\beta ={\beta }_0$). As a result, the worst-case evacuation cost of case $x\in I_3$ cannot exceed that of case $x\in I_4$, and hence the lemma follows.  □

It is important to note that the worst-case performance of ${\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )$ of Lemma 7 is decreasing in $\beta$. Indeed, $\frac{\partial }{\partial \beta }\mathrm{Wrs}\left({\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )\right)=\frac{1}{2}-\frac{1}{2}sin\left(\beta /4\right)<0$. For values of $\beta$ close to 0, the derivative is nearly a constant. This also explains why in Figure 1, the performance of algorithm ${\mathcal{A}}_2^{\prime }$ seems to have nearly invariant worst-case performance, which however is provably decreasing in $\beta$.

Lemma 7

(Worst-Case Analysis for ${\mathcal{A}}_2^{\prime }$). Let ${\beta }_0=0.0438855$, and set ${\alpha }_{\beta }:=\pi -\beta /2-2cos\left(\beta /4\right)$. Then for all $\beta \in [0,{\beta }_0]$ we have $\mathrm{Wrs}\left({\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )\right)=1+\pi -\beta /2+2cos\left(\beta /4\right).$

6. Average-Case Performance Analysis and the Efficient Frontier

In this section, we perform average-case analysis for all algorithmic families ${\mathcal{A}}_1,{\mathcal{A}}_2,{\mathcal{A}}_2^{\prime }$, with respect to their parameters. For the sake of exposition of our results, we set $w_1=\mathrm{Wrs}\left({\mathcal{B}}_1\right)\approx 5.73906,$$w_2=\mathrm{Wrs}\left({\mathcal{B}}_2\right)=1+2\pi \approx 7.28319$ and for ${\beta }_0\approx 0.04388$, as in Lemma 7, we set $w_0:=\mathrm{Wrs}\left({\mathcal{A}}_2^{\prime }({\alpha }_{{\beta }_0},{\beta }_0)\right)\approx 6.11953$. We also recall $\overline{\alpha }\approx 1.54419$ of Lemma 4. Finally, we set

$$\begin{array}{cc}\hfill v\left(\alpha \right)& :=1+2\pi -\alpha \hfill \\ \hfill v_2\left(\beta \right)& :=1+\pi -\beta /2+2cos\left(\beta /4\right)\hfill \\ \hfill u_1\left(\alpha \right)& :=0.00889{\alpha }^3-0.16944{\alpha }^2+0.71518\alpha +4.23089\hfill \\ \hfill u_2^{\prime }\left(\beta \right)& :=530.673{\beta }^3-78.5498{\beta }^2+7.36219\beta +4.70493\hfill \\ \hfill u_2\left(\alpha \right)& :=0.093056{\alpha }^2+0.346659\alpha +4.1719\hfill \end{array}$$

Combined with our findings of Section 5, the main result of the current section is the following.

Theorem 6.

For every $w\in [w_1,w_2]$ there is algorithm $\mathcal{A}\in \{{\mathcal{A}}_1,{\mathcal{A}}_2^{\prime },{\mathcal{A}}_2\}$ and unique parameter(s) p such that $\mathrm{Wrs}\left(\mathcal{A}\left(p\right)\right)=w$. In particular,

-

for all $\alpha \in [1,\overline{\alpha }]$, ${\mathcal{A}}_1\left(\alpha \right)$ is $(u_1\left(\alpha \right),v\left(\alpha \right))$-efficient, and $v\left([1,\overline{\alpha }]\right)=[w_1,2\pi ]$,

-

for all $\beta \in [0,{\beta }_0]$, ${\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )$ is $(u_2^{\prime }\left(\beta \right),v_2\left(\beta \right))$-efficient, and $v_2\left([0,{\beta }_0]\right)=[w_0,3+\pi ]$,

-

for all $\alpha \in [0,\pi -2]$, ${\mathcal{A}}_2\left(\alpha \right)$ is $(u_2\left(\alpha \right),v\left(\alpha \right))$-efficient, and $v\left([0,\pi -2]\right)=[3+\pi ,w_2]$.

Proof. 

The claims for the worst-case performances of ${\mathcal{A}}_1,{\mathcal{A}}_2^{\prime },{\mathcal{A}}_2$ follow directly from Lemmata 4, 7 and 5, respectively. Next we argue that as the parameters vary in their specified range, we obtain the entire spectrum of $w\in [w_1,w_2]$, and this for unique values of the parameters. For this, we will rely on that for all evacuation algorithm families, the worst-case cost is monotone in the parameters.

First, we argue about ${\mathcal{A}}_1$. We observe that by the definition of $\overline{\alpha }$, $\mathrm{Wrs}\left({\mathcal{A}}_1\left(\overline{\alpha }\right)\right)=w_1$, and $\mathrm{Wrs}\left({\mathcal{A}}_1\left(1\right)\right)=1+2\pi -1=2\pi$. Together with the fact that $v\left(\alpha \right)$ is strictly decreasing, we see that $\mathrm{Wrs}\left({\mathcal{A}}_1\left(\alpha \right)\right)$ is 1-1 and onto to $[w_1,2\pi ]$ as $\alpha$ ranges in $[1,\overline{\alpha }]$.

Second, we study ${\mathcal{A}}_2^{\prime }$ whose worst-case cost $v_2\left(\beta \right)$ is strictly decreasing in $\beta$. Moreover, by definition of ${\beta }_0$, we have $\mathrm{Wrs}\left({\mathcal{A}}_2({\alpha }_{{\beta }_0},{\beta }_0)\right)=w_0$. Then we note that for $\beta =0$, ${\mathcal{A}}_2({\alpha }_{\beta },\beta )$ coincides with ${\mathcal{A}}_2(\pi -2)$, and in particular the induced worst-case cost becomes $3+\pi$. Therefore $\mathrm{Wrs}\left({\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )\right)$ is 1-1 and onto to $[w_0,3+\pi ]$ as $\beta$ ranges in $[0,{\beta }_0]$.

Third, we study ${\mathcal{A}}_2$, for which we know that $\mathrm{Wrs}\left({\mathcal{A}}_2(\pi -2)\right)=3+\pi$. Again, the worst-case cost is monotone in $\alpha$ and ${\mathcal{A}}_2\left(0\right)$ coincides with benchmark algorithm ${\mathcal{B}}_2$, which is $\mathrm{Wrs}\left({\mathcal{A}}_2\left(0\right)\right)=w_2$. Hence, $\mathrm{Wrs}\left({\mathcal{A}}_2\left(\alpha \right)\right)$ is 1-1 and onto to $[3+\pi ,w_2]$ as $\alpha$ ranges in $[0,\pi -2]$.

Finally, we argue that

$$\begin{array}{cc}\hfill \mathrm{Avg}\left({\mathcal{A}}_1\left(\alpha \right)\right)\le u_1\left(\alpha \right)& ,\forall \alpha \in [1,\overline{\alpha }]\hfill \\ \hfill \mathrm{Avg}\left({\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )\right)\le u_2^{\prime }\left(\beta \right)& ,\forall \beta \in [0,{\beta }_0]\hfill \\ \hfill \mathrm{Avg}\left({\mathcal{A}}_2\left(\alpha \right)\right)\le u_2\left(\alpha \right)& ,\forall \alpha \in [0,\pi -2]\hfill \end{array}$$

For this, we numerically compute $\mathrm{Avg}\left({\mathcal{A}}_1\left(\alpha \right)\right),\mathrm{Avg}\left({\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )\right),\mathrm{Avg}\left({\mathcal{A}}_2\left(\alpha \right)\right)$ for various values of parameters $\alpha ,\beta$, and we heuristically choose $u_1,u_2^{\prime },u_2$ so as to upper bound the average-case performance of ${\mathcal{A}}_1,{\mathcal{A}}_2^{\prime },{\mathcal{A}}_2$, effectively verifying our claim numerically. For each evacuation algorithm, we use Corollary 1, which together with the analytic description of our evacuation algorithms (see Definitions 4, 6, and 5) allow us to compute their average-case performance using computer-assisted calculations. Our numerical calculations are depicted in Figure 7. □

Finally, we aim to formally quantify the efficient frontier of our algorithms as depicted in Figure 1 (see Section 2.1). The parametric curves described in Theorem 6 provide, strictly speaking, an upper bound for the parametric curve of Figure 1. Next, we compute $g:\mathbb{R}\mapsto \mathbb{R}$, so that the parametric curves of Theorem 6 are written in the form ${\left\{(g\left(w\right),w)\right\}}_{w\in [w_1,w_2]}$. That would also imply that there is a solution to ${}_2$Evac${}_{F2F}^w$ of cost at most $g\left(w\right)$.

In that direction, we study each evacuation algorithm family $\mathcal{A}\left(p\right)$ with worst-case performance, say, $v\left(p\right)$, and average-case upper bound, say, $u\left(p\right)$. For each $w\in [w_1,w_2]$ in the range of $\mathcal{A}\left(p\right)$, we set $p=v^{-1}\left(w\right)$ so that the average-case performance achieved becomes $u\left(v^{-1}\left(w\right)\right)$.

Recall that $\mathrm{Wrs}\left({\mathcal{A}}_i\left(\alpha \right)\right)=v\left(\alpha \right)$, so that $v^{-1}\left(w\right)=1+2\pi -w$, and hence for algorithms ${\mathcal{A}}_i$ we can easily compute $u_i\left(v^{-1}\left(w\right)\right)$, $i=1,2$. For ${\mathcal{A}}_2^{\prime }$ we recall that $\mathrm{Avg}\left({\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )\right)$ is decreasing in $\beta$. Since $v_2^{-1}$ does not admit a closed form, we need to observe that $2.999+\pi -\beta /2\le v_2\left(\beta \right)\le 3+\pi -\beta /2$ for all $\beta \in [0,{\beta }_0]$ so that an upper bound for $\mathrm{Avg}\left({\mathcal{A}}_2^{\prime }({\alpha }_{\beta },\beta )\right)$ admitting worst-case performance w can be computed by $u_2^{\prime }(12.2812-2w)$.

Now for each $w\in [w_1,w_2]$ we need to specify which of the evacuation algorithms we will invoke. Please note that in Theorem 6 we chose the range of $\alpha$ in ${\mathcal{A}}_1$ to start from 1 so that as to guarantee that $\mathrm{Wrs}\left({\mathcal{A}}_1\left(1\right)\right)\ge w_0$. We note that $u_2^{\prime }(12.2812-2w)=u_1(1+2\pi -w)$ for $w^{\prime }\approx 6.12851$, so algorithm ${\mathcal{A}}_1$ should be invoked for $w\in [w_1,w^{\prime }]$ (and $w^{\prime }$ is obtained for ${\alpha }^{\prime }:=1+2\pi -w^{\prime }\approx 1.15468$), then ${\mathcal{A}}_2^{\prime }$ for $w\in [w^{\prime },3+\pi ]$ (and $w^{\prime }$ is obtained for ${\beta }^{\prime }$ so that $v_2\left({\beta }^{\prime }\right)=w^{\prime }$, where ${\beta }^{\prime }\approx 0.0241653$), and ${\mathcal{A}}_2$ for $w\in [3+\pi ,w_2]$. We conclude with the next Theorem (for convenience, the values of all constants are summarized at the end of Section 2.3).

Theorem 7.

For every $w\in [w_1,w_2]$, the optimal solution to ${}_2$Evac${}_{F2F}^w$ is at most $g\left(w\right)$, where

$$g\left(w\right)=\left\{\begin{array}{cc}-0.00889w^3+0.0248026w^2+0.338241w+3.88629\hfill & ,w\in [w_1,w^{\prime }]({\mathcal{A}}_1\left(\alpha \right),\alpha \in [{\alpha }^{\prime },\overline{\alpha }])\hfill \\ -4245.38w^3+77893.3w^2-476397.w+971235\hfill & ,w\in [w^{\prime },3+\pi ]({\mathcal{A}}_2({\alpha }_{\beta },\beta ),\beta \in [0,{\beta }^{\prime }])\hfill \\ 0.093056w^2-1.70215w+11.6328\hfill & ,w\in [3+\pi ,w_2]({\mathcal{A}}_2\left(\alpha \right),\alpha \in [0,\pi -2])\hfill \end{array}\right.$$

7. Conclusions and Open Problems

We offered a new perspective to the well-studied problem of evacuating two robots from the disk, in the face-to-face model, first introduced in [1]. A series of results pertaining especially to the same domain have focused exclusively on deterministic algorithms and their worst-case (competitive) analyses. Our work can be understood as a first attempt to study the same problem in the realm of randomized algorithms. More specifically, in light of known positive results for the problem, we asked the question of minimizing the average-case performance of an evacuation algorithm, condition on that the worst-case performance remains bounded. We allowed that latter bound to range between the best known guarantee of a simple yet efficient evacuation algorithm (that was introduced in [1]) and that of a naive algorithm that simulates the optimal solution of one searcher. Our main contribution is the introduction of three new evacuation algorithms that perform well for different values of the worst-case bound, inducing a continuous bound of the efficient (pareto) frontier for the underlying multi-objective optimization problem (that of minimizing both the worst and the average-case performance). We also motivated our results by verifying, somehow surprisingly, that among the family of algorithms introduced in [27], which gave the second subsequent improvement of the worst-case performance, none of them could improve the average-case performance of the simple algorithm presented in [1]. In that sense our new algorithms outperform the best algorithms known for the problem, but in the new multi-objective setting. Our findings give rise to several open questions and directions that aim to better understand ${}_2$Evac${}_{F2F}^w$ as well as multi-objective optimization search-type problems.

Open questions specific to our problem ${}_2$Evac${}_{F2F}^w$ are:

-

Prove lower bounds for ${}_2$Evac${}_{F2F}^w$, for any w. Is any of our algorithms, for any w optimal?

-

For the value $w=\mathrm{Wrs}\left({\mathcal{B}}_1\right)$, we designed algorithm ${\mathcal{A}}_1\left(\alpha \right)$ for ${}_2$Evac${}_{F2F}^w$ which for a proper value of a has worst-case performance exactly w, while its average-case performance is strictly less than $\mathrm{Avg}\left({\mathcal{B}}_1\right)$. Is it feasible to attain worst-case performance strictly less than w, while having average-case performance at most $\mathrm{Avg}\left({\mathcal{B}}_1\right)$?

-

The bound to the efficient (pareto) frontier we derived for problem ${}_2$Evac${}_{F2F}^w$ is indeed continuous, with respect to parameter w, but not differentiable. Is the optimal pareto frontier smooth, or is there any other family of algorithms that improves upon our results and gives a smooth transition between families of evacuation algorithms?

-

The algorithmic families we derived for ${}_2$Evac${}_{F2F}^w$ exhibit the following property. ${\mathcal{A}}_2$ is a natural extension to ${\mathcal{B}}_2$. Similarly, ${\mathcal{A}}_2^{\prime }$ is a natural extension to ${\mathcal{A}}_2$. Finally, ${\mathcal{A}}_1$ is a natural extension to ${\mathcal{B}}_1$. However, ${\mathcal{A}}_1$ and ${\mathcal{A}}_2^{\prime }$ have different behavior (there are no values of their parameters that induce the same evacuation protocol), even though for a proper choice of their parameters, they induce algorithms with the same worst-case and average-case performance.

-

Observe that the average-case performance of ${\mathcal{B}}_2$ is $1+\pi$. All our evacuation algorithms induce average cost at least $1+\pi$. We conjecture that even in the wireless model, as well as for any number of robots, $1+\pi$ is tight lower bound for the average performance of evacuation algorithm.

We conclude with some future directions that are inspired by our work and pertain to more general problems:

-

Our algorithms can also be interpreted as randomized algorithms that have access to infinitely many bits (or enough many bits, in order to simulate a uniformly random deployment point on the circle). What if the algorithm has access only to a limited number of random bits?

-

To the best of our knowledge, the current paper is the first attempt to study multi-objective optimization search-type problems. It was followed by [48,49] who considered time energy trade-offs for a search problems on the line. This line of research admits many future directions based on any combination of multiple objectives, e.g., worst-case, average-case and competitive cost, time, energy and any other efficiency measure, or even trade-offs involving number of faults or even complexity resources, e.g., memory, communication or randomness.