11institutetext:  Department of Mathematics, Toronto Metropolitan University,
Toronto, ON, Canada 11email<EMAIL_ADDRESS>
# Weighted Group Search on the Disk
& Improved Lower Bounds for Priority Evacuation ††thanks: Research supported
in part by NSERC.

Konstantinos Georgiou 11 Xin Wang 11

###### Abstract

We consider _weighted group search on a disk_ , which is a search-type problem
involving 2 mobile agents with unit-speed. The two agents start collocated and
their goal is to reach a (hidden) target at an unknown location and a known
distance of exactly 1 (i.e., the search domain is the unit disk). The agents
operate in the so-called _wireless_ model that allows them instantaneous
knowledge of each others findings. The termination cost of agents'
trajectories is the worst-case _arithmetic weighted average_ , which we
quantify by parameter $w$, of the times it takes each agent to reach the
target, hence the name of the problem.

Our work follows a long line of research in search and evacuation, but quite
importantly it is a variation and extension of two well-studied problems,
respectively. The known variant is the one in which the search domain is the
line, and for which an optimal solution is known. Our problem is also the
extension of the so-called _priority evacuation_ , which we obtain by setting
the weight parameter $w$ to $0$. For the latter problem the best upper/lower
bound gap known is significant.

Our contributions for weighted group search on a disk are threefold. First, we
derive upper bounds for the entire spectrum of weighted averages $w$. Our
algorithms are obtained as a adaptations of known techniques, however the
analysis is much more technical. Second, our main contribution is the
derivation of lower bounds for all weighted averages. This follows from a
_novel framework_ for proving lower bounds for combinatorial search problems
based on linear programming and inspired by metric embedding relaxations.
Third, we apply our framework to the priority evacuation problem, improving
the previously best lower bound known from $4.38962$ to $4.56798$, thus
reducing the upper/lower bound gap from $0.42892$ to $0.25056$.

###### Keywords:

Mobile Agents, Combinatorial Search, Lower Bounds, Linear Programming

##  1 Introduction

Autonomous mobile agent searching over geometric domains such as lines, disks,
circles, triangles and polygons has been the subject of extensive research
over the last decades. In these problems, a fleet of agents is tasked with
finding a hidden item in the geometric domain while complying with searchers'
specifications. One of the most significant parameters that distinguish these
variations is how the cost of the solution is quantified, effectively
identifying the set of feasible solutions and changing the computational
boundaries of the underlying problem. Indeed, in traditional search problems,
e.g. _search_ and rescue scenarios, one is concerned just with the finding of
the hidden item, hence quantifying the cost as the time it takes the first
agent to reach the target. In the other extreme, e.g. in _evacuating_
scenarios, one is concerned with minimizing the time the last agent reaches
the hidden item. These objective variations are combined with other
fundamental specifications, such as the communication model and possibility of
faultiness.

Despite the growing number of problems in the field, the number of problems
for which matching upper and lower bounds are known is also increasing.
Empirically, problems that admit full symmetry, involving the agents'
specifications, domain, communication model, etc., are those that admit strong
or matching upper and lower bounds. However, even a small deviation from
symmetry makes any lower bounds to the problems particularly difficult to
tackle. Examples include the face-to-face communication model, where knowledge
is shared in an asymmetric way during the execution of the search, different
agent speeds, or abstract domains such as triangles. Recently, asymmetry was
also introduced as part of the way the search cost is quantified by
considering the objective of only a _distinguished agent_ reaching the hidden
item, a problem known as _priority evacuation_. Negative results for this and
similar problems are rare, and usually weak and challenging.

The main contribution of our work is a framework that provides lower bounds
for combinatorial search problems. More generally, our starting point is the
study of a generalization of the priority evacuation problem on the disk,
which we obtain by considering _asymmetric_ cost functions. Aside from the
upper bounds we derive for these problems, our primary contribution is a
framework for proving lower bounds (for these as well as for more general
problems) that is based on linear programming and metric embedding
relaxations. We demonstrate the usefulness of the framework by establishing
lower bounds for our weighted evacuation problems, and in particular by
improving the previously best lower bound known for the priority evacuation
problem.

###  1.1 Related Work

The study of search-type problems dates back to the 1960's and has resulted to
a rich theory that has been summarized in books [1, 2] and surveys [21, 30,
37], among others. Originally, the problem pertained to the identification of
a hidden object within a search domain, and hence the objective was to
minimize the time the object was found [7]. Already with one searcher, the
problem has seen interesting, and surprisingly challenging variations touching
on the searcher's specs and the search domain, some of which we briefly
discuss next. More recently, and with the emergence of fleet-robotics, search-
type problems were considered with multiple searchers, see e.g. [15].

A basic example of a search space is the so-called linear search problem that
has been considered with one [5] or multiple searchers [11]. The same problem
has also been considered with the objective of minimizing the weighted average
of the searchers' termination times [36] (that we also use in this work).
Other 1-dimensional settings include variations such as searching rays [10] or
graphs [4], or also search for multiple objects [9, 14].

Searching two-dimensional domains has become a more dominant topic in the last
decade or so. Considered domains include polygons [29], the quite popular disk
[15], the plane [28], regular polygons [19] the equilateral triangle and
square [13, 26], arbitrary triangles [32], and $\ell_{p}$ unit disks [35].
Many of these problems have also seen variations pertaining to the
communication model or more generally to the the searchers' specifications,
e.g. searching the disk in the face-to-face model [27], with different
searchers' speeds [6], and with different searchers' communication
capabilities [23, 31]. Last but not least, search problems have also been
considered under faultiness settings, see for example [8, 16, 22, 24, 25, 34,
39]

A number of search problems have also been considered with less standard
objectives. For example [12] considered a multi-objective search-type problem,
[3] studied search problems under a broad competitive algorithmic lens, [38]
considered information/cost trade-offs, [17, 18] considered time/energy trade-
offs, and [33] introduced search-and-fetch problems in two dimensions. More
closely related to our work, is the so-called priority evacuation objective
introduced in [19, 20] where search termination is called when a distinguished
searcher reaches the target.

###  1.2 Discussion on New Results

In this study, we explore a natural extension of the priority evacuation
problem on the disk introduced in [19, 20]. Our specific problem, termed the
_weighted group search_ on the disk, is parameterized by $w\in[0,1]$.
Parameter $w$ represents a designated arithmetic weighted average (i.e.
$\tfrac{x+wy}{1+w}$, when considering the weighted average of $x,y$) that
defines the objective function, hence the name of the problem. The same
objective was previously considered with the line as the search domain and
solved optimally in [36]. Moreover, our weighted group search problem with
$w=0$ corresponds exactly to the previously studied priority evacuation
problem on the disk for which the best lower and upper bound known are
$4.38962$ and $4.81854$, respectively, creating a notable gap that remains an
open problem.

Our results are derivations of upper and lower bounds for the weighted group
search problem on the disk for all $w\in[0,1]$. Our upper bounds are obtained
by a family of mobile agent trajectories (algorithms) that are adapting with
$w$. The derived algorithm for $w=0$ is exactly the best algorithm known for
the previously studied priority evacuation problem (with performance
$4.81854$), and therefore our positive results can be understood as
generalizations, still technical to analyze, of known algorithmic techniques.
The main contribution of this work is the introduction of a novel framework
for deriving lower bounds for general search problems. We discuss the key
technical and conceptual ideas in the following section. Here we emphasize the
significance of the obtained results in an area where finding strong lower
bounds is notoriously challenging and rare. Indeed, we design a framework for
proving lower bounds that is applicable to general objective functions, and to
general discrete search domains. Our framework utilizes Linear Programming
relaxations that are inspired by metric embedding relaxations of Euclidean
2-dimensional metric spaces induced by optimal search strategies. Indeed, we
apply our framework to the weighted group search problem on the disk and we
find lower bounds for all $w\in[0,1]$, resulting in upper/lower bound gaps
that are diminishing with $w$. When $w=1$ the bound is optimal. However, the
punchline of our new methodology pertains to the lower bound obtained for
$w=0$, corresponding to previously studied priority evacuation. For this
problem our techniques allow us to improve the previously best lower bound
known to $4.56798$, reducing this way the upper/lower bound gap from $0.42892$
to $0.25056$.

###  1.3 Key Technical and Conceptual Ideas

Our approach to establishing _upper bounds_ for weighted group search involves
a generalization of the algorithm presented in [19]. We achieve this by
specifically parameterizing the algorithm's behavior and performance according
to the parameter $w$ of the cost function. Unsurprisingly, when $w=0$, our
algorithm aligns with the one detailed in [19].The inherent challenge in
analyzing our family of algorithms, which vary with $w$, lies in the fact that
they generate diverse trajectories for the agents, where critical domain
points are visited with varying order. These points are possible locations of
the hidden item, which have been explored already, but whose close
neighborhood has not been explored yet, and hence a adversarial placement of
the hidden item arbitrarily close to those points is a possibility. Such
points are necessarily introduced by strong search algorithms, as in these
algorithms an agent may abandon the search of the disk in order to move in its
interior, potentially in order to expedite evacuation should the hidden item
be located by the other agent. Hence, identifying the optimal choices within
that family (as a function of $w$) becomes more technical than the case $w=0$.
Consequently, quantifying the solution cost for all inputs necessitates a
meticulous analysis, which at a high level considers various searched space
configurations. For this reason, the contribution of this section is primarily
only technical in nature.

The main contribution of this work lies in introducing a novel framework for
proving _lower bounds_ applicable to various combinatorial search-type
problems. As an illustration of our methodology, we derive lower bounds for
the weighted group search problem across all values of $w$. Specifically, we
establish a matching lower bound for $w=1$ and, notably, an improved lower
bound for $w=0$ addressing the priority evacuation problem. The challenge
inherent in proving lower bounds for the weighted group search (as well as the
priority evacuation or similar problems) stems from the contiguous search
domain and the asymmetry of the objective function. Any lower bound argument
necessitates the consideration of snapshots of an algorithm at certain time-
stamps, identifying a finite collection of potential input placements for
which the algorithm must perform well. Additionally, due to the online nature
of the problem, the algorithm must operate identically until the input is
discovered. The critical question revolves around how these finite points are
processed by the two agents. A key observation is that the time-stamps,
combined with potential input placements and agent trajectories, induce a
finite 2-dimensional $\ell_{2}$ metric space. By conditioning on the order in
which input placements are visited, one can model the optimal algorithm's
performance using a Non-Linear Program (NLP). While solving all NLPs
(corresponding to all permutations of placement visitations) identifies the
optimal algorithm for the specific finite search domain, the challenge lies in
the difficulty of solving these NLPs and providing proper certificates of
optimality. In that direction, a second key observation is that one can relax
the induced 2-dimensional $\ell_{2}$ metric spaces to abstract metric spaces,
leading to Linear Programs (LPs). These LPs can be solved efficiently, with
accompanying certificates of optimality. Importantly, the optimal values of
these LPs serve as lower bounds for the NLPs, consequently establishing lower
bounds for the original problems. Our framework relies among others on
symbolic (not numerical), computer-assisted calculations, which we did not
exhaust when deriving the lower bounds, suggesting that further improvements
are possible by bypassing current computational limitations.

###  1.4 Roadmap

We start with Section 2.1 where we give some formal definitions and introduce
proper terminology. This is followed by Section 2.2 where we present past and
new results using the underlying new terminology, along with some key
observations. Section 3 introduces our first main contribution, which is a
framework based on (metric-inspired) linear program relaxations that give rise
to lower bounds for geometric search-type problems. In Section 4 we apply our
framework to the previously studied priority evacuation problem with 2 agents,
effectively improving the previously best lower bound known. Finally, in
Section 5 we study the weighted group search problem on the disk, which is a
generalization of the priority evacuation problem, deriving upper and lower
bounds, the latter using our general framework of Section 3. Finally, in
Section 6 we conclude with some future directions.

##  2 Preliminaries

###  2.1 Problem Definition, Notation & and some Observations

We consider a class of search-type problems $\textsc{WS}_{\mathcal{D}}^{f}$
(for Wireless Search) with 2 agents in the wireless model, which we define
next. In these problems, 2 unit speed agents are initially collocated at the
origin of the Euclidean plane, i.e. $\mathbb{R}^{2}$ equipped with the
$\ell_{2}$ metric. The 2 agents have distinct (known) identities that we call
$A_{0},A_{1}$. Given a known geometric object
$\mathcal{D}\subseteq\mathbb{R}^{2}$ and a known cost function
$f:\mathbb{R}^{2}\mapsto\mathbb{R}$ (non-decreasing in both coordinates), a
solution to the problem is given by trajectories $\tau_{i}:\mathbb{R}_{\geq
0}\mapsto\mathbb{R}^{2}$, $i=0,1$, that induce movements for the 2 agents of
speed at most 1. The two agents operate in the _wireless model_ and they need
to find a hidden target, in the following mathematical sense. For each fixed
_target_ $I\in\mathcal{D}$, we allow _both_ trajectories $\tau_{i}$ to depend
on $I$ _only after_ $I$ is visited by _any_ agent, i.e. when for some $t\geq
0$ and $i\in\\{0,1\\}$ we have that $\tau_{i}(t)=I$. Equivalently, two
executions of the trajectories are identical for different inputs up to the
moment the first of these inputs is hit by a trajectory.

For each $I\in\mathcal{D}$, we also denote the _termination time_ $T_{i}(I)$
of agent $A_{i}$ as the first time that agent $A_{i}$ visits target $I$. The
agent who is the first that visits the target is referred to as the _finder_.
We emphasize that each $T_{i}(I)$ depends on all $\tau_{0},\tau_{1}$ and $I$
(while trajectories $\tau_{j}$ may only depend on $I$ after the target is
visited). The objective of $\textsc{WS}_{\mathcal{D}}^{f}$ is to determine
trajectories $\tau_{0},\tau_{1}$ so as to minimize the _search cost_

$\sup_{I\in\mathcal{D}}\tfrac{f\left(T_{0}(I),T_{1}(I)\right)}{f\left(\|I\|_{2},\|I\|_{2}\right)}.$

When $f$ is the $\max$ function, the problem is known as _evacuation_ , and
when $f$ is the projection function, then it is known as _priority
evacuation_. For this reason, also refer to the objective also as the
_evacuation cost_. In this work we consider the following search domains: (a)
$\mathcal{D}=\textsc{disk}$, the unit radius disk, and (b)
$\mathcal{D}=n$-gon, the vertices of a regular $n$-gon inscribed in the unit
radius disk.

Some important observations are in place. _First_ , the underlying search
space (i.e. the space where agents' movements take place) is the 2-dim
Euclidean space. Searching in other $\ell_{p}$ metrics has been considered in
[35]. For convenience, we think of the search domains embedded on the
Cartesian plane so that the unit disks are centered at the origin. The fact
that the underlying search space is a metric space, and in particular the
Euclidean metric space will be essential in our lower bound arguments.
_Second_ , for a given $I\in\mathcal{D}$, let agent $A_{i}$ be the finder of
the target, and suppose that this happens at time $t$, i.e. $I=\tau_{i}(t)$.
Since the other agent can have her trajectory depend on this finding (wireless
model), we may assume that $A_{1-i}$ moves directly to the target, i.e. that

$T_{1-i}(I)=t+\left\lVert\tau_{i}(t)-\tau_{1-i}(t)\right\rVert_{2}=t+\left\lVert
I-\tau_{1-i}(t)\right\rVert_{2}.$ (1)

_Third_ , for the search domains we consider, i.e. the disk or the vertices of
$n$-gons, all possible targets are at distance $1$ from the origin. Agents
that knew in advance the position of any target $I$ (i.e. if trajectories
$\tau_{i}(t)$ could depend on $I$ for all $t\geq 0$) would need time $1$ to
reach the target, inducing cost $f\left(\|I\|_{2}),\|I\|_{2})\right)=f(1,1)$,
independent of the target $I$. Hence, when quantifying the performance of a
search trajectory as per its search cost, we perform both worst case and
competitive analysis. In particular, both performance quantifications admit
the same optimal trajectories, and the corresponding optimal search costs are
off by constant multiplicative factor $f(1,1)$ that depends only on $f$, hence
they are also equal when $f(1,1)=1$.

###  2.2 Past Results, Search Domains & Cost Functions

A number of past results can be described in the framework of
$\textsc{WS}_{\mathcal{D}}^{f}$ problems as we demonstrate next. The
discussion focuses on the wireless model. For other communication models, one
has to adjust the definition of feasible trajectories.

Typical search problems, where search is complete when the first agent reaches
the target, are associated by definition with cost function
$f(x,y)=\min\\{x,y\\}$. When multiple agents are involved in search, and one
quantifies the performance by the time the last agent reaches the target, then
one uses $f(x,y)=\|(x,y)\|_{\infty}=\max\\{x,y\\}$. The case where the
performance is determined by the termination time of a designated agent, then
one needs the projection function $f(x,y)=\textrm{proj}_{2}(x,y)=y$ (or
$\textrm{proj}_{1}$). Finally, one may also consider a weighted average of the
termination times of the two agents, by using cost function
$f(x,y)=g_{w}(x,y):=wx+y$, where without loss of generality $w\in[0,1]$ (note
that one may use a scaling factor $w+1$ without affecting optimizers). With
these definitions in mind, we have that $g_{0}=\textrm{proj}_{2}$ and
$g_{1}=\|\cdot\|_{1}$.

There are four notable examples of $\textsc{WS}_{\mathcal{D}}^{f}$ problems
that were considered before. Our new findings build upon ideas found in these
results, which we naturally generalize as well as in some cases we also
improve:

  * •

$\textsc{WS}_{\mathbb{R}\setminus[-1,1]}^{g_{w}}$, also known as weighted
group search on a line, was considered in [36] where the search space
$\mathcal{D}$ was the one dimensional real line excluding all points at most
$1$ away from the origin. The problem has been solved optimally. Our work is
the first to consider the same cost function but on the disk.

  * •

$\textsc{WS}_{\textsc{disk}}^{\|\cdot\|_{\infty}}$ is the classic evacuation
problem on the disk, solved optimally in [15], where the cost function is
simply described as the time that the last agent reaches the target.

  * •

$\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$ is the priority evacuation
problem (with 1 servant and 1 distinguished searcher, the queen) considered in
[19]. In our current work, first we improve the lower bound for the problem,
as well as we generalize it by considering cost functions $g_{w}$, where
$w\in[0,1]$, and the same search domain. Recall that
$g_{0}=\textrm{proj}_{2}$.

  * •

$\textsc{WS}_{6\textsc{-gon}}^{\textrm{proj}_{2}}$ was considered in [19] and
solved optimally. Our methodology implies the same lower bound. Moreover, we
are the first to study search domain $n$-Gon, with $n>6$, where in particular
we derive lower bounds for $\textsc{WS}_{n\textsc{-gon}}^{g_{w}}$,
$w\in[0,1]$, for $n=7,8,9$.

The motivation for studying search domain $n$-Gon relates to the fact that a
lower bound to the problem is also a lower bound to searching domain disk (for
the same cost function), an idea introduced in [15], and later used in [19].
The following lemma is explicit in these works. Even though it was previously
used only for the $\|\cdot\|_{\infty}$ and $\textrm{proj}_{2}$ cost functions,
it holds more generally for any non-decreasing cost function $f$. Here we
generalize the statement, since we will need it when studying the weighted
group search problem. We emphasize that the lemma establishes lower bounds to
algorithms addressing the search of the disk, conditioning on their
performance of searching $n$-gons.

###### Lemma 1

Let $t_{0}$, $t_{1}$ be the termination time lower bounds of agents
$A_{0},A_{1}$, respectively, for some input to
$\textsc{WS}_{n\textsc{-gon}}^{f}$. Then, no algorithm for
$\textsc{WS}_{\textsc{disk}}^{f}$ with these termination times of the agents
has evacuation cost better than
$\frac{f\left(t_{0}+\pi/n,t_{1}+\pi/n\right)}{f\left(1,1\right)}.$

###### Proof

We let an arbitrary algorithm for $\textsc{WS}_{\textsc{disk}}^{f}$ run for
time $1+\pi/n-\epsilon$. In this time, the 2 agents have searched at most
$2\pi/n-2\epsilon$ of the disk. It is easy to see then that there is an
inscribed regular $n$-gon, none of whose vertices have been explored yet. Note
that $n$-gon is a subset of the search domain disk, and hence any target $I$
of $n$-gon is an eligible target of disk. For target $I$, the agents'
termination times are increased by $\pi/n$, and the claim follows. ∎

Specifically all cost-functions
$f\in\\{\textrm{proj}_{2},\|\cdot\|_{\infty},g_{w}\\}$ have the property that
$f(x+a,y+a)/f(1,1)=f(x,y)/f(1,1)+a.$ Now in Lemma 1, let $c_{n}$ be the
derived lower bound for $\textsc{WS}_{n\textsc{-gon}}^{f}$ induced by target
$I$. The same target $I$ is an eligible adversarial choice for
$\textsc{WS}_{\textsc{disk}}^{f}$, hence for the latter problem, the target is
reached at least $\pi/n$ time later. This means, the following quantity is a
valid lower bound to $\textsc{WS}_{\textsc{disk}}^{f}$.

$\frac{f\left(T_{0}(I)+\frac{\pi}{n},T_{1}(I)+\frac{\pi}{n}\right)}{f\left(1,1\right)}=\frac{f\left(T_{0}(I),T_{1}(I)\right)}{f(1,1)}+\frac{\pi}{n}=c_{n}+\frac{\pi}{n}$
(2)

In fact the best lower bound of $\pi/6+3+\sqrt{3}/2$ for
$\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$ is due to the provable lower
bound of $3+\sqrt{3}/2$ for
$\textsc{WS}_{6\textsc{-gon}}^{\textrm{proj}_{2}}$, see [19]. In this work we
strengthen this result by deriving new lower bounds for
$\textsc{WS}_{n\textsc{-gon}}^{\textrm{proj}_{2}}$, $n>6$.

##  3 Improved Framework for Proving Lower Bounds

In this section we leverage the existing framework for showing lower bounds
for $\textsc{WS}_{n\textsc{-gon}}^{f}$, and in light of Lemma 1, that would
imply adjusted lower bounds for $\textsc{WS}_{\textsc{disk}}^{f}$, too. In
what follows $[n]$ denotes the set $\\{0,1,\ldots,n\\}$, so for example
$[1]=\\{0,1\\}$. Moreover, we denote the set of all permutations of $[n]$ by
$\mathcal{R}_{n}$.

Our first task is to provide a systematic way in order to find the optimal
solution to $\textsc{WS}_{n\textsc{-gon}}^{f}$. At a high level that would be
accomplished by solving $\frac{(n-1)!2^{n-1}}{n}$ many Non-Linear Programs.
Recall that we think of the $n$-gon embedded on the Cartesian Euclidean space,
inscribed in a unit-radius circle and centered at the origin. For this reason
its vertices are identified by points
$\left(\cos\left(2i\pi/n\right),\sin\left(2i\pi/n\right)\right)$,
$i=0,\ldots,n-1$. Now, for a permutation $\rho\in\mathcal{R}_{n}$
(corresponding to the $n$ vertices of $n$-gon), we slightly abuse notation and
we write $\rho_{i}$ to denote both the $i$-th element of the permutation, as
well as the corresponding point
$\left(\cos\left(2\rho_{i}\pi/n\right),\sin\left(2\rho_{i}\pi/n\right)\right)$
on the plane.

The main idea of our formulation is that search strategies for
$\textsc{WS}_{n\textsc{-gon}}^{f}$ can be classified with respect to the order
that vertices are visited, given by some permutation $\rho$ over $[n]$, and
the identities of the agents that visit these vertices, given by a binary
string $b\in[1]^{n}$. In particular, this means vertex $\rho_{i}$, i.e. the
$i$-th visited vertex, is visited no later than vertex (target) $\rho_{j}$,
when $i<j$, and that target $\rho_{i}$ is visited by agent $A_{b_{i}}$. We
call such a search strategy a $(\rho,b)$-algorithm. Note that without loss of
generality (due to symmetry), we may assume that the first vertex to be
visited is vertex 0, and that the second visited vertex is one among
$1,\ldots,\lfloor(n-1)/2\rfloor+1$. This gives rise to at most
$\frac{(n-1)!2^{n-1}}{n}$ classes of search algorithms. Next we show how to
find the optimal $(\rho,b)$-algorithm, for each fixed $\rho,b$, by solving a
Non-Linear Program.

###### Lemma 2

For each $n\in\mathbb{N}$, permutation $\rho$ of $[n]$, binary string
$b\in[1]^{n}$ and $t_{0}\in\mathbb{R}_{\geq 0}$, consider the Non-Linear
Program111For the intended meaning of the variables, the reader may consult
the proof of the lemma.

$\displaystyle\min$
$\displaystyle~{}\max_{i\in[n]}\left\\{f\left(c^{0}_{i},c^{1}_{i}\right)\right\\}$
($\textsc{NLP}^{f}_{n}(\rho,b,t_{0})$) $\displaystyle s.t.:~{}$ $\displaystyle
t_{n}\geq t_{n-1}\geq\ldots\geq t_{1}\geq t_{0}$ $\displaystyle
t_{i+1}-t_{i}\geq\left\lVert
L^{j}_{i+1}-L^{j}_{i}\right\rVert_{2},~{}~{}i\in[n-1],j\in[1]$ $\displaystyle
c^{j}_{i}\geq t_{i}+\left\lVert
L^{j}_{i}-L^{b_{i}}_{i}\right\rVert_{2},~{}~{}i\in[n],j\in[1]$

in variables $\\{c^{j}_{i},t_{i},x_{i},y_{i}\\}_{j\in[1],i\in[n]}$, where in
particular we used abbreviations $L^{b_{i}}_{i}=\rho_{i}$ and
$L^{1-b_{i}}_{i}=(x_{i},y_{i})$. Then, for every convex cost function $f$,
($\textsc{NLP}^{f}_{n}(\rho,b,t_{0})$) admits a unique (hence global) minimum,
and the optimizer for $t_{0}=1$ corresponds to the optimal
$(\rho,b)$-algorithm for $\textsc{WS}_{n\textsc{-gon}}^{f}$.

###### Proof

It is easy to see that the domain of the Non-Linear Program is convex. Indeed,
any constraint of the form $\|\|_{2}\leq c$ is convex, hence the intersection
of convex constraints define a convex feasible region. As for the objective
$f$ is given to be convex, while $\max\\{\cdot\\}$ is convex too, hence also
their composition. This makes the Non-Linear Program convex. Note also that
the non-linear program is bounded from below by $f\left(t_{0}t_{0}\right)$,
hence it admits an optimal solution, which is the only (global) minimum.

Next we argue that for the fixed $\rho,b$, and by setting $t_{0}=1$, the Non-
Linear Program correctly finds the termination cost of the optimal
$(\rho,b)$-algorithm for $\textsc{WS}_{n\textsc{-gon}}^{f}$ (scaled by
$f(1,1)$). For this, we present the semantics of the chosen variables that
identify the behavior of the $(\rho,b)$-algorithm.
\- $c^{j}_{i}$ is the time by which agent $j$ reaches vertex $\rho_{i}$,
$j\in[1],i\in[n]$.
\- $t_{i}$ is the time by which vertex $\rho_{i}$ is visited for the first
time, by any agent, $i\in[n]$.
\- $x_{i},y_{i}$ are coordinates of agent $j=1-b_{i}$, i.e. the agent that
does not visit $\rho(i)$ first, $i\in[n]$.

Therefore, indeed, if $L^{j}_{i}$ denotes the position of agent $A_{j}$ when
potential target $\rho_{j}$ is visited (which are subject to an algorithmic
choice), we have that

$\displaystyle L^{b_{i}}_{i}$ $\displaystyle=\rho_{i},$ $\displaystyle
L^{1-b_{i}}_{i}$ $\displaystyle=(x_{i},y_{i}),$

for each $i$. By (1), we obtain

$c^{j}_{i}\geq t_{i}+\left\lVert L^{j}_{i}-L^{b_{i}}_{i}\right\rVert_{2},$

i.e. a bound for agent $j$ to visit vertex $\rho_{i}$. Since $f$ is non-
decreasing in each coordinate, this constraint will be satisfied with equality
for the optimal solution (hence we could also eliminate variables
$c^{j}_{i}$), but we leave the constraint as is for the sake of better
exposition.

Clearly, because the agents are moving at speed at most 1, the time elapsed
between the visitation of $\rho_{i+1}$ and $\rho_{i}$ cannot be less than the
time needed by each agent $A_{j}$ to move from $L^{j}_{i}$ to $L^{j}_{i+1}$,
i.e. no more than $\left\lVert L^{j}_{i+1}-L^{j}_{i}\right\rVert_{2}$.
Finally, the time that the first vertex is visited is at least $t_{0}=1$,
overall showing that the constraints capture the $(\rho,b)$-algorithm
visitation times of all potential targets.

Finally, as per the definition the search cost, and due to that in
$\textsc{WS}_{n\textsc{-gon}}^{f}$ there are only $n$ many potential targets,
one needs to compute the search cost for each potential target $\rho_{i}$,
which equals $f\left(c^{0}_{i},c^{1}_{i}\right)/f(1,1)$, only that in the
description of the non-linear program we omit the multiplicative factor
$f(1,1)$. ∎

We slightly abuse notation, and we denote by
$\textsc{NLP}^{f}_{n}(\rho,b,t_{0})$ also the optimal value of the same Non-
Linear Program. The following corollary follows immediately by our
definitions, and Lemma 2.

###### Corollary 1

The optimal search cost for $\textsc{WS}_{n\textsc{-gon}}^{f}$ equals
$\frac{1}{f(1,1)}\min_{\rho\in\mathcal{R}_{n},b\in[1]^{n}}\textsc{NLP}^{f}_{n}\left(\rho,b,1\right).$

Note that any solution to ($\textsc{NLP}^{f}_{n}(\rho,b,t_{0})$) is associated
with an embedding of points $L_{i}^{j}$ in the $(\mathbb{R}^{2},\ell_{2})$
metric space, where in particular
$d(L_{i}^{j},L_{i^{\prime}}^{j^{\prime}})=\left\lVert
L_{i}^{j}-L_{i^{\prime}}^{j^{\prime}}\right\rVert_{2}.$ This metric space
satisfies the triangle inequality. Therefore, requiring that distances
$d_{j,i,j^{\prime},i^{\prime}}:=d(L_{i}^{j},L_{i^{\prime}}^{j^{\prime}})$
satisfy the triangle inequality, but not necessarily that the space is
embeddable to $\mathbb{R}^{2}$ (or even that it is $\ell_{2}$), gives rise to
a natural relaxation to the problem. This idea is materialized in the next
lemma.

###### Lemma 3

For each $n\in\mathbb{N}$, permutation $\rho$ of $[n]$, $b\in[1]^{n}$ and
$t_{0}\in\mathbb{R}_{\geq 0}$, consider the Non-Linear Program (Relaxation)

$\displaystyle\min$
$\displaystyle~{}\max_{i\in[n]}\left\\{f\left(c^{0}_{i},c^{1}_{i}\right)\right\\}$
($\textsc{REL}^{f}_{n}(\rho,b,t_{0})$) $\displaystyle s.t.:~{}$ $\displaystyle
t_{n}\geq t_{n-1}\geq\ldots\geq t_{1}\geq t_{0}$ $\displaystyle
t_{i+1}-t_{i}\geq d_{j,i+1,j,i},~{}~{}i\in[n-1],j\in[1]$ $\displaystyle
c^{j}_{i}\geq t_{i}+d_{j,i,b_{i},i},~{}~{}i\in[n],j\in[1]$ $\displaystyle
d_{b_{i},i,b_{i^{\prime}},i^{\prime}}=\left\lVert\rho_{i}-\rho_{i^{\prime}}\right\rVert_{2},~{}~{}i,i^{\prime}\in[n]$
$\displaystyle\left(\left\\{L^{j}_{i}\right\\}_{j\in[1],i\in[n]},d(L^{j}_{i},L^{j^{\prime}}_{i^{\prime}}))=d_{j,i,j^{\prime},i^{\prime}}\right)~{}\textrm{is
a metric}$

in variables
$\\{c^{j}_{i},t_{i},d_{j,i,j^{\prime},i^{\prime}}\\}_{j,j^{\prime}\in[1],i,i^{\prime}\in[n]}$.
Then, ($\textsc{REL}^{f}_{n}(\rho,b,t_{0})$) admits a unique (global) minimum,
that we denote by $\textsc{REL}^{f}_{n}(\rho,b,t_{0})$, and in particular
$\textsc{NLP}^{f}_{n}(\rho,b,t_{0})\geq\textsc{REL}^{f}_{n}(\rho,b,t_{0}).$

###### Proof

First we observe that the feasible region of
($\textsc{REL}^{f}_{n}(\rho,b,t_{0})$) is a polyhedron. Indeed, for all
$i,i^{\prime}\in[n]$, we have that
$\left\lVert\rho_{i}-\rho_{i^{\prime}}\right\rVert_{2}$ is a constant, while
the axioms that distance function $d_{j,i,j^{\prime},i^{\prime}}$ defines a
metric for points $\\{L^{j}_{i}\\}_{j\in[1],i\in[n]}$ is a collection of
linear constraints (including the triangle inequalities). It is also easy to
see that the objective is bounded from below by $f(t_{0},t_{0})$, hence, the
Non-Linear Pogram admits a unique local (global) minimizer.

Finally, we show that ($\textsc{REL}^{f}_{n}(\rho,b,t_{0})$) is a relaxation
to ($\textsc{NLP}^{f}_{n}(\rho,b,t_{0})$), implying the claimed inequality. To
see why, note that the constraints of ($\textsc{NLP}^{f}_{n}(\rho,b,t_{0})$)
require that

$\left(\left\\{L^{j}_{i}\right\\}_{j\in[1],i\in[n]},d(L^{j}_{i},L^{j^{\prime}}_{i^{\prime}}))=d_{j,i,j^{\prime},i^{\prime}}\right)$

is embeddable in $(\mathbb{R}^{2},\ell_{2})$, and therefore the distance
function $d_{j,i,j^{\prime},i^{\prime}}=\left\lVert
L^{j}_{i}-L^{j^{\prime}}_{i^{\prime}}\right\rVert_{2}$ is a metric. ∎

The significance of ($\textsc{REL}^{f}_{n}(\rho,b,t_{0})$) over
($\textsc{NLP}^{f}_{n}(\rho,b,t_{0})$) is that the former can be solved much
faster, especially when $f$ is a linear function (e.g. when
$f\in\\{\textrm{proj}_{2},\|\cdot\|_{\infty},g_{w}\\}$), in which case the
resulting relaxation is a Linear Program (a basic trick introduces a new
linear variable, and a collection of inequality constraints that simulate that
the optimal solution simulates the $\max$ function). Because
($\textsc{REL}^{f}_{n}(\rho,b,t_{0})$) is easy to solve, it will be used to
provide search cost lower bounds to $\textsc{WS}_{\textsc{disk}}^{f}$, as the
next lemma suggests.

###### Lemma 4

For every $n\in\mathbb{N}$, no algorithm to $\textsc{WS}_{\textsc{disk}}^{f}$
has search cost better than

$\mathcal{L}_{n}^{f}:=\frac{1}{f(1,1)}\min_{\rho\in\mathcal{R}_{n},b\in[1]^{n}}\textsc{REL}^{f}_{n}\left(\rho,b,1+\frac{\pi}{n}\right).$

###### Proof

By Corollary 1 and Lemma 1, and for all $n\in\mathbb{N}$ we have that any
solution to $\textsc{WS}_{\textsc{disk}}^{f}$ has cost at least
$\frac{1}{f(1,1)}\min_{\rho\in\mathcal{R}_{n},b\in[1]^{n}}\textsc{NLP}^{f}_{n}\left(\rho,b,1+\frac{\pi}{n}\right)\geq\frac{1}{f(1,1)}\min_{\rho\in\mathcal{R}_{n},b\in[1]^{n}}\textsc{REL}^{f}_{n}\left(\rho,b,1+\frac{\pi}{n}\right),$
where the last inequality is due to Lemma 3. ∎

Lemma 4 effectively implies that for each $n$, one can solve $(n-1)!2^{n-1}/n$
Convex Programs (or more specifically Linear Programs, if $f$ is linear), in
order to obtain lower bound $\mathcal{L}_{n}^{f}$ for
$\textsc{WS}_{\textsc{disk}}^{f}$. This idea is explored in Section 4
specifically for $f=\textrm{proj}_{2}$, and more generally in Section 5 for
cost functions $f=g_{w}$, $w\in[0,1]$.

##  4 Implied (and Improved) Lower Bounds for Priority Evacuation

In this section we present and prove one of our main contributions, which is
an improved lower bound to the Priority Evacuation Problem
$\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$.

###### Theorem 4.1

No algorithm for $\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$ has
evacuation cost less than
$1+\pi/9+\sqrt{3}/2+\cos\left(\pi/18\right)+4\sin\left(\pi/9\right)\approx
4.56798.$

As a reminder, the previously best lower bound known for the problem was
$4.38962$. Note that not only the improvement is significant, but most
importantly, the provided framework allows for even further improvements if
one utilizes computational resources more efficiently, e.g. use specialized
software for solving LP's instead of Mathematica that was used in this
project.

The proof of Theorem 4.1 follows immediately from Lemma 4 once we present new
lower bounds for $\textsc{WS}_{n\textsc{-gon}}^{\textrm{proj}_{2}}$, $n>6$.
Indeed, for $f=\textrm{proj}_{2}$, we have that $f(1,1)=1$ and the cost
function is linear. For this reason, due to Lemma 4, and as per the
calculations (2), no algorithm for
$\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$ has evacuation cost less
than
$\frac{1}{f(1,1)}\min_{\rho\in\mathcal{R}_{n},b\in[1]^{n}}\textsc{REL}^{\textrm{proj}_{2}}_{n}\left(\rho,b,1+\frac{\pi}{n}\right)=\frac{\pi}{n}+\min_{\rho\in\mathcal{R}_{n},b\in[1]^{n}}\textsc{REL}^{\textrm{proj}_{2}}_{n}\left(\rho,b,1\right),$
where in particular
$\textsc{REL}^{\textrm{proj}_{2}}_{n}\left(\rho,b,1\right)$ is a lower bound
to the optimal $(\rho,b)$-algorithm for
$\textsc{WS}_{n\textsc{-gon}}^{\textrm{proj}_{2}}$. For each $n=3,\ldots,9$,
we solve $\textsc{REL}^{\textrm{proj}_{2}}_{n}(\rho,b,1)$ for all permutations
$\rho\in\mathcal{R}_{n}$ and all binary strings $b\in[1]^{n}$, and we report
the smallest values in Table 1. The calculations were computer-assisted but
also symbolic (non-numerical).222Calculations were performed symbolically with
Mathematica. The solution to any LP comes with a proof of optimality.

$\begin{array}[]{r | c c c c c c c c c c}n&min_{\rho\in\mathcal{R}_{n},b\in[1]^{n}}\textsc{REL}^{\textrm{proj}_{2}}_{n}\left(\rho,b,1\right)&\textrm{Num}&b&\rho\\\ \hline\cr\hline\cr 3&1+\sqrt{3}&2.73205&\\{0,1,0\\}&(1,2,3)&\\\ 4&1+3/\sqrt{2}&3.12132&\\{1,0,0,1\\}&(1,2,3,4)&\\\ 5&1+\sqrt{25+2\sqrt{5}}/2&3.71441&\\{0,1,0,1,1\\}&(1,3,2,4,5)&\\\ 6&3+\sqrt{3}/2&3.86603&\\{1,0,0,1,0,1\\}&(1,2,3,5,4,6)&\\\ 7&1+\cos\left(3\pi/14\right)+5\sin\left(\pi/7\right)&3.95125&\\{1,0,0,1,0,1,0\\}&(1,2,3,7,4,6,5)&\\\ 8&1+\sqrt{2}/2+6\sin\left(\pi/8\right)&4.00321&\\{1,0,0,1,0,1,0,1\\}&(1,2,3,8,4,6,5,7)&\\\ 9&1+\sqrt{3}/2+\cos\left(\pi/18\right)+4\sin\left(\pi/9\right)&4.21891&\\{1,0,0,1,0,1,0,1,0\\}&(1,2,3,9,4,8,5,7,6)&\end{array}$

Table 1: Lower bounds to $\textsc{WS}_{n\textsc{-gon}}^{\textrm{proj}_{2}}$,
for $n=3,\ldots,9$ are given in the first column as the solutions to the
Linear Programs $\textsc{REL}^{\textrm{proj}_{2}}_{n}\left(\rho,b,1\right)$.
The second column is the numerical value of the lower bound, while the last
two columns contain the corresponding minimizer permutation
$\rho\in\mathcal{R}_{n}$ and binary string $b\in[1]^{n}$.

From Table 1, and for $n=9$, we derive a new lower bound to
$\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$, which is

$\frac{\pi}{9}+\min_{\rho\in\mathcal{R}_{9},b\in[1]^{9}}\textsc{REL}^{\textrm{proj}_{2}}_{9}\left(\rho,b,1\right)=\frac{\pi}{9}+1+\sqrt{3}/2+\cos\left(\pi/18\right)+4\sin\left(\pi/9\right)\approx
4.56798,$

as promised. The lower bounds for $n=3,4,5$ are only derived for comparison
(and to illustrate how easily our methodology can derive new lower bounds to
$\textsc{WS}_{n\textsc{-gon}}^{\textrm{proj}_{2}}$). We also emphasize that
the reported lower bound for $n=6$ agrees with the one reported and proven in
[19]. In particular, this implies that for $n=6$, and due to the matching
upper bound for $\textsc{WS}_{6\textsc{-gon}}^{\textrm{proj}_{2}}$ in [19], we
have that relaxation
$\textsc{REL}^{\textrm{proj}_{2}}_{6}\left(\rho,b,1\right)$ to
$\textsc{NLP}^{\textrm{proj}_{2}}_{6}\left(\rho,b,1\right)$ is exact, at least
for the optimizers $\rho,b$ on Table 1. This is no longer the case for
$n=7,8,9$, since the solution found for
$\textsc{REL}^{\textrm{proj}_{2}}_{7}\left(\rho,b,1\right)$ is not embeddable
in $(\mathbb{R}^{2},\ell_{2})$. For this reason, it is no surprise that
quantities

$\frac{\pi}{n}+\min_{\rho\in\mathcal{R}_{n},b\in[1]^{n}}\textsc{REL}^{\textrm{proj}_{2}}_{n}\left(\rho,b,1\right)$

are not increasing in $n$, and only the lower bounds for $n=7,9$ improve upon
the one derived for $n=6$. Finally, the computations for $n=10$ are more
intense, but unfortunately they do not give rise to further improvement
(without exhausting all permutations and binary strings, a solution was found
that gives a weaker lower bound that the case $n=9$). Finally, the case $n=11$
cannot be treated exhaustively since the number of configurations
(approximately $7\cdot 10^{8}$) becomes forbidden, especially for the size of
the linear programs that is growing too, with $\Theta(n^{3})$ constraints and
$\Theta(n^{2})$ variables.

##  5 Weighted Group Search on the Disk

In this section we derive upper and lower bounds for
$\textsc{WS}_{\textsc{disk}}^{g_{w}}$, stemming from the cost function
$g_{w}(x,y)=wx+y$, $w\in[0,1]$. Our upper and lower bounds are quantified by
concrete formulas. Our lower bounds are derived by utilizing Lemma 4. In
Figure 1 we summarize our results graphically before we give the technical
details in Sections 5.1, 5.2.

Figure 1: Derived upper and lower bounds for
$\textsc{WS}_{\textsc{disk}}^{g_{w}}$, where $g_{w}(x,y)=wx+y,w\in[0,1]$.

We emphasize that for $w=0$ we have that $g_{w}=g_{0}=\textrm{proj}_{2}$. In
particular, the upper bound depicted in Figure 1 is also the one reported in
[19] for $\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$, while the depicted
lower bound is an improvement of the one derived in [19], but lower than the
one we proved for the special problem $\textsc{WS}_{\textsc{disk}}^{g_{0}}$ in
Section 4. This is because for the lower bounds to
$\textsc{WS}_{\textsc{disk}}^{g_{w}}$ we relied on the lower bounds we managed
to prove for $\textsc{WS}_{7\textsc{-gon}}^{g_{w}}$. Indeed, dealing with
lower bounds to $\textsc{WS}_{9\textsc{-gon}}^{g_{w}}$ was computationally too
demanding, taking into consideration that parameter $w$ also ranges in
$[0,1]$.

###  5.1 Upper Bounds to Weighted Group Search on the Disk

The upper bound results are quantified in the following lemma (and are
depicted in Figure 1).

###### Lemma 5

For each $w\in[0,0.2]$, let $\alpha=\alpha_{w}$ and $\beta=\beta_{w}$ be the
solutions to non-linear system333$\alpha_{w},\beta_{w}$ are to be invoked only
for smaller values of $w$. Also $\gamma_{1}=\gamma_{2}=\gamma_{3},$ admits a
solution also for higher values, but not for all $w\in[0,1]$. The value of
$0.2$ was chosen only for aesthetic reasons.
$\gamma_{1}=\gamma_{2}=\gamma_{3},$ where

$\displaystyle\gamma_{1}$ $\displaystyle=\alpha+\frac{2\sin(\alpha)}{w+1}$
$\displaystyle\gamma_{2}$
$\displaystyle=2\pi-\alpha-\beta+\frac{2\sin\left(\alpha+\frac{\beta}{2}+\sin\left(\frac{\beta}{2}\right)\right)}{w+1}$
$\displaystyle\gamma_{3}$
$\displaystyle=2\sin\left(\frac{\beta}{2}\right)+\frac{\alpha+\beta+w(-\alpha-\beta+2\pi)}{w+1},$

see also Figure 2(b). Then for each $w\in[0,1]$,
$\textsc{WS}_{\textsc{disk}}^{g_{w}}$ admits a solution with search cost at
most $1+d_{w}+\frac{2\sin\left(d_{w}\right)}{w+1}$, where $d_{w}=\alpha_{w}$
if $w\leq w_{0}$ and $d_{w}=\arccos\left(-\frac{w+1}{2}\right)$ otherwise.
Moreover, $w_{0}$ is defined by equation
$\alpha_{w}=\arccos\left(-\frac{w+1}{2}\right)$, with $w_{0}\approx
0.0456911$.

As we will see next, the threshold of $w\leq 0.0456911$ corresponds to the
critical ratio of the two weights $1/0.0456911\approx 21.8861$ that indicates
when the agent with the higher weight has incentive to deviate from the search
in order to expedite her evacuation. When the agents' weight ratio is less
than $21.8861$, then a plain vanilla algorithm is the best we can report,
which however is optimal when the weight ratio is $1$, i.e. when $w=1$, see
Lemma 7.

(a) The $(a,b)$-Detour Algorithm for $\textsc{WS}_{\textsc{disk}}^{f}$. Agent
$A_{0}$ trajectory is depicted in blue, and agent $A_{1}$ trajectory is
depicted in red.

(b) The bevavior of parameters $\alpha_{w},\beta_{w}$, solutions to the non-
linear system of Lemma 5. Only the values for $w\leq 0.0456911$ are relevant
to the $(a,b)$-Detour Algorithm when applied to
$\textsc{WS}_{\textsc{disk}}^{g_{w}}$.

Figure 2: The Detour Algorithm for $\textsc{WS}_{\textsc{disk}}^{f}$, and some
of its parameters.

First we present the so-called $(a,b)$-detour Algorithm, introduced in [19],
specifically for $\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$. For this,
we present the two agent trajectories $\tau_{0},\tau_{1}:\mathbb{R}_{\geq
0}\mapsto\mathbb{R}^{2}$, where the functions depend on parameters $a,b$. Both
trajectories will be piece-wise movements along arcs and chords of the unit
radius disk. The description of the trajectories is given under the assumption
that no target is reported or found. Should the target be located by the
agent, then the agent halts and transmits the finding message to her peer.
Should the finding message reach an agent, then the agent moves along the
shortest path towards the target. We emphasize that the algorithm is
applicable to the search domain Disk, and therefore provides some solution to
$\textsc{WS}_{\textsc{disk}}^{f}$, for any cost function $f$. For the
exposition, we also use abbreviation
$c(t):=\left(\cos\left(t\right),\sin\left(t\right)\right)$, which is the
parametric equation of the unit-radius disk. Next we give formal description
of the search algorithm; the reader may also consult Figure 2(a). All
movements are always at unit speed.

######  Definition 1 (The $(a,b)$-Detour Algorithm for
$\textsc{WS}_{\textsc{disk}}^{f}$)

Trajectory $\tau_{0}:\mathbb{R}_{\geq 0}\mapsto\mathbb{R}^{2}$ of agent
$A_{0}$, starting from origin $O$: Move to point $L=c(-a)$; Search clockwise
up to point $E=c(b)$; Move to $D=c(0)$ along chord $ED$.
Trajectory $\tau_{1}:\mathbb{R}_{\geq 0}\mapsto\mathbb{R}^{2}$ of agent
$A_{1}$, starting from origin $O$: Move to point $L=c(-a)$; Search counter-
clockwise up to point $D=c(0)$; Move to $E=c(b)$ along chord $ED$; Search
clockwise up to $D=c(0)$.

The following lemma effectively proves our upper bound claim of Lemma 5.

###### Lemma 6

For each $w\in[0,1]$, let

$a_{w}=\left\\{\begin{array}[]{ll}\alpha_{w}&w\leq w_{0}\\\
\pi&w>w_{0}\end{array}\right.,~{}~{}b_{w}=\left\\{\begin{array}[]{ll}\beta_{w}&w\leq
w_{0}\\\ 0&w>w_{0}\end{array}\right.,$

where $\alpha_{w},\beta_{w}$ and $w_{0}\approx 0.0456911$ are as in Lemma 5.
Then, the $(a_{w},b_{w})$-Detour Algorithm for
$\textsc{WS}_{\textsc{disk}}^{g_{w}}$ has evacuation cost
$1+d_{w}+\frac{2\sin\left(d_{w}\right)}{w+1},$ where

$d_{w}=\left\\{\begin{array}[]{ll}\alpha_{w}&w\leq w_{0}\\\
\arccos\left(-\frac{w+1}{2}\right)&w>w_{0}\end{array}\right..$

###### Proof

We begin the proof by analyzing the $(\pi,0)$-Detour Algorithm that is
applicable to $\textsc{WS}_{\textsc{disk}}^{g_{w}}$ for $w\geq w_{0}\approx
0.0456911$ (we shall see soon that there is continuity of the evacuation cost
at $w=w_{0}$). In that case, each agent searches half the perimeter of the
unit disk. If the target is reported after searching for time $t\leq\pi$, then
the termination time $T_{i}(t)$ of the finder $i\in[1]$ is $T_{i}(t)=1+t$, and
as per (1) that of the non-finder is $T_{1-i}(t)=1+t+2\sin\left(t\right)$. Any
of the two agents could be the finder, but for cost function $g_{w}(x,y)=wx+y$
with $w\in[0,1]$, it is not less costly when the finder is agent $A_{0}$, and
for this reason, the search cost of the algorithm, should the exit be reported
after searching time $t$, is

$\frac{g_{w}\left(1+t,1+t+2\sin\left(t\right)\right)}{g_{w}(1,1)}=1+t+\frac{2\sin\left(t\right)}{w+1}.$

The last expression is increasing up to $t_{w}=\arccos\left(-(w+1)/2\right)$,
and then decreasing, i.e. it is concave. It follows that its maximum becomes
$1+t_{w}+\frac{2\sin\left(t_{w}\right)}{w+1}$, as claimed.

We now turn our attention to the performance of the
$(\alpha_{w},\beta_{w})$-Detour Algorithm, for $w\leq w_{0}$. Parameter values
for $\alpha_{w},\beta_{w}$ are depicted in Figure 2(b). We distinguish 4 cases
as to where the target may be placed, and in each of them we evaluate the
termination times of the agents, along with the associated worst case search
costs $c_{1},c_{2},c_{3},c_{4}$ (and our parameters $\alpha_{w},\beta_{w}$ are
identified by making all costs equal). For the analysis, the reader may also
consult Figure 2(a). In what follows arcs are read counter-clockwise.

Case 1: Target is placed in arc $DD^{\prime}$, i.e. it is found while the two
agents search in opposite direction for up to $\alpha_{w}$ time. The search in
this phase lasts for time $\alpha_{w}$, hence the target is reported after
searching for $t\leq\alpha_{w}$. From the analysis we performed when $w\leq
w_{0}$, we know that in the current case, the search cost is
$1+t+\frac{2\sin\left(t\right)}{w+1}$. For all $w\leq w_{0}$ we have that
$\alpha_{w}\leq\arccos\left((-(w+1)/2)\right)$, see also Figure 3(a) (in fact
$w_{0}$ was identified by equation
$\alpha_{w_{0}}\leq\arccos\left((-(w_{0}+1)/2)\right)$, see statement of Lemma
5). Therefore, as per our previous analysis, the cost in this case remains
strictly increasing in $t$, and hence in Case 1, the worst case search cost is

$c_{1}=1+\alpha_{w}+\frac{2\sin\left(\alpha_{w}\right)}{w+1}.$

(a) Comparison between $\alpha_{w}$ and $\arccos{-(w+1)/2}$, and the defining
value of $w_{0}$.

(b) The plot of $2\pi-2\alpha_{w}-\beta_{w}-2\sin\left(\beta_{w}\right)/2$ in
blue proves that for all $w\leq w_{0}$, point $K$ in Figure 2(a) lies within
arc $D^{\prime}E$ (case 2 in the proof of Lemma 6). The plot of
$-2\pi+2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}\right)/2$ in orange proves
that for all $w\leq w_{0}$, agent $A_{0}$ arrives at $E$ before agent $A_{1}$
reaches $D$ for the second time, (case 4 in the proof of Lemma 6). The line
$y=0$ in green is depicted for reference.

(c) The derivative of search cost (3). The plot depicts the plane $z=0$,
showing that the derivative of the function is negative and bounded away from
$0$, in the subject domain.

(d) The derivative of search cost (4). The values are are close to $1$ showing
that the cost function is strictly increasing in the subject domain.

Figure 3: The behavior of some expressions, as needed in the proof of Lemma 6.

Case 2: Target is placed in arc $D^{\prime}K$, i.e. while agent $A_{1}$ moves
from $D$ to $E$ along chord $DE$.
First we show that point $K$ lies in between arc $D^{\prime}E$, that is agent
$A_{1}$ arrives at $E$ before agent $A_{0}$. To see why, notice that agent
$A_{0}$ arrives at $E$ in time $1+2\pi-\alpha_{w}-\beta_{w}$. Similarly, agent
$A_{1}$ arrives at $E$ in time $1+\alpha_{w}+2\sin\left(\beta_{w}\right)/2$.
The time gap of these events is

$1+2\pi-\alpha_{w}-\beta_{w}\left(1+\alpha_{w}+2\sin\left(\beta_{w}\right)/2\right)=2\pi-2\alpha_{w}-\beta_{w}-2\sin\left(\beta_{w}\right)/2.$

The latter expression remains non-negative for all $w\leq w_{0}$ as claimed,
see Figure 3(b).

To resume, we verified that for the duration agent $A_{0}$ searches arc
$D^{\prime}K$ (of length $2\sin\left(\beta_{w}/2\right)$), agent $A_{1}$ moves
along chord $DE$ (of the same length). If the exit is reported by $A_{0}$ at
time $t\in[0,2\sin\left(\beta_{w}/2\right)]$, then the termination cost of
that agent is $T_{0}(t)=1+\alpha_{w}+t$. Note that in that case, the target is
placed at $c(-2\alpha_{w}-t)$. Agent $A_{1}$ needs to additionally spend the
time to reach the target, and this is what we compute next. For this we
utilize the parametric equation for a unit speed movement between points
$A,B$, which reads as

$l\left(t,A,B\right):=A+\frac{t}{\left\lVert B-A\right\rVert}(B-A).$

More specifically, for the aforementioned placement of the target, agent
$A_{1}$ lies at

$l\left(t,D,E\right)=l\left(t,c(0),c(\beta_{w})\right),$

and hence its termination cost is, as also per (1),

$T_{1}(t)=1+\alpha_{w}+t+\left\lVert
c(-2\alpha_{w}-t)-l\left(t,c(0),c(\beta_{w})\right)\right\rVert.$

We conclude that in this case, the search cost for cost function $g_{w}$ is

$\frac{g_{w}(T_{0}(t),T_{1}(t))}{g_{w}(1,1)}=\frac{g_{w}(T_{0}(t),T_{1}(t))}{w+1}=1+\alpha_{w}+t+\frac{\left\lVert
c(-2\alpha_{w}-t)-l\left(t,c(0),c(\beta_{w})\right)\right\rVert}{w+1}.$ (3)

The latter function admits an analytic formula, whose derivative for $t\leq
2\sin\left(\beta_{w}/2\right)$ is depicted in Figure 3(c), together with plane
$z=0$. The plot shows that the derivative of the function is negative and
bounded away from $0$, in the domain $t\in[0,2\sin\left(\beta_{w}/2\right)]$,
for all $w\in[0,w_{0}]$. By Figure 2(b), we know that
$\beta_{w}\leq\beta_{0}=0.925793$ (value $\beta_{0}$ was used in [19]
specifically for $\textsc{WS}_{\textsc{disk}}^{g_{0}}$). For this reason, our
plot ranging over $w\in[0,2\sin\left(1/2\right)]$ is sufficient for the
purpose of showing that the search cost in decreasing in $t$. Since at $t=0$,
the case was already considered in Case 1, we conclude that for the worst case
search cost in this case we have $c_{2}=c_{1}$.

Case 3: Target is placed in arc $KE$.
Note that by the previous case, while agent $A_{0}$ is moving counter-
clockwise along chord $KE$, agent $A_{1}$ is moving counter-clockwise along
arc $ED$, starting from points $K,E$, respectively. First we argue that agent
$A_{0}$ reaches $E$ before $A_{1}$ reaches $D$ for the second time. Indeed,
agent $A_{0}$ reaches $E$ in time $1+2\pi-2\alpha_{w}-\beta_{w}$, while
$A_{1}$ reaches $D$ for the second time at
$1+\alpha_{w}+2\sin\left(\beta_{w}/2\right)+\beta_{w}$. So we have

$1+\alpha_{w}+2\sin\left(\beta_{w}/2\right)+\beta_{w}-(1+2\pi-2\alpha_{w}-\beta_{w})=-2\pi+2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}/2\right).$

The latter expression is depicted in Figure 3(b) and is positive.

This means that Case 3 has a time span equal to the length of arc $KE$ which
equals $2\pi-2\alpha_{w}-\beta_{w}-2\sin\left(\beta_{w}/2\right)$ and during
that time, the distance between the two agents is invariant (and equal to the
length of arc $KE$). Therefore the search cost in this case is the highest
when the target is found by $A_{0}$ as late as possible, i.e. close to $E$ in
arc $KE$ (the maximum is not attained, rather we calculate the supremum of the
search cost). In the limit, the termination cost of agent $A_{0}$ is
$T_{0}=1+2\pi-\alpha_{w}-\beta_{w}$, while agent pays in addition its distance
to the exit, as in (1), that is

$T_{1}=1+2\pi-\alpha_{w}-\beta_{w}+2\sin\left(\alpha_{w}+\beta_{w}/2+\sin\left(\beta_{w}/2\right)\right).$

Overall, the worst case termination cost in this case is

$c_{3}=\frac{g_{w}(T_{0},T_{1})}{g_{w}(1,1)}=\frac{g_{w}(T_{0},T_{1})}{w+1}=1+2\pi-\alpha_{w}-\beta_{w}+\frac{2\sin\left(\alpha_{w}+\beta_{w}/2+\sin\left(\beta_{w}/2\right)\right)}{w+1}$

Case 4: Target is placed in arc $DE$.
In this case, the target is found by agent $A_{1}$. The phase has time span
equal to the length of arc $ED$, i.e. $2\sin\left(\beta_{w}/\right)$, and
recall that from our previous analysis, agent $A_{1}$ reaches $D$ for the
second time while agent $A_{0}$ is still moving along chord $ED$ from $E$
towards $D$.

Agent $A_{1}$ starts searching arc $ED$ when $A_{0}$ is at point $K$ still
moving counter-clockwise along the perimeter. Agent $A_{0}$ reaches point $E$
in time equal to the length of arc $KE$, i.e.
$2\pi-2\alpha_{w}-\beta_{w}-2\sin\left(\beta_{w}/2\right).$ In this time
window, the distance of the two agents is invariant. In fact, the termination
cost in this case is dominated by the cost of Case 3, since now the extra
distance towards the target needs to be covered by the ``light'' agent whose
termination cost is scaled by $w\in[0,1]$. For this reason, we may assume that
the target is reported by $A_{1}$ in arc $ED$ after $A_{0}$ reaches $E$, and
while $A_{1}$ moves along chord $ED$, from $E$ towards $D$.

We reset the clock at time $1+2\pi-\alpha_{w}-\beta_{w}$ when $A_{0}$ reaches
point $E$, after which time the agent moves along trajectory
$l(t,c(\beta_{w}),c(0)),t\in[0,2\sin\left(\beta_{w}/2\right)]$. When we reset
the clock, agent $A_{1}$ lies in
$c\left(2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}/2\right)-2\pi\right)$, and
therefore at additional time $t$ it is located at

$c\left(2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}/2\right)-2\pi-t\right),$

where $t\leq 2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}/2\right)-2\pi$.

To conclude, each
$t\in[0,2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}/2\right)-2\pi]$
corresponds to a placement of the target that is located by agent $A_{1}$ for
her termination cost $T_{1}(t)=1+2\pi-\alpha_{w}-\beta_{w}+t$. Agent $A_{0}$
will have to pay the additional cost of moving to the target, and hence her
termination cost in this case, as in (1), is

$T_{0}(t)=1+2\pi-\alpha_{w}-\beta_{w}+t+\left\lVert
l(t,c(\beta_{w}),c(0))-c\left(2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}/2\right)-2\pi-t\right)\right\rVert.$

Hence, in this case the termination cost for cost function $g_{w}$ becomes

$\displaystyle~{}~{}~{}~{}~{}~{}\frac{g_{w}(T_{0}(t),T_{1}(t))}{g_{w}(1,1)}$
(4) $\displaystyle=$ $\displaystyle
1+2\pi-\alpha_{w}-\beta_{w}+t+w\frac{\left\lVert
l(t,c(\beta_{w}),c(0))-c\left(2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}/2\right)-2\pi-t\right)\right\rVert}{w+1}.$

Now we claim that this cost is increasing in $t\leq
2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}/2\right)-2\pi$. Note that the
function admits a closed formula, and therefore we can compute its derivative,
that is depicted in Figure 3(d). The plot confirms that derivative is remains
close to $1$, as expected, since the 2 agents are moving towards the same
point $c(0)$, one along the arc $ED$ and one along the chord $ED$. The domain
in the figure was chosen to be $t\in[0,5]$ which is a superset of time window
of the case we are considering, because
$2\alpha_{w}+2\beta_{w}+2\sin\left(\beta_{w}/2\right)-2\pi\leq
2\alpha_{0}+2\beta_{0}+2\sin\left(\beta_{0}/2\right)-2\pi\approx 0.460808$.

To conclude, in this case, the termination cost is the highest when the target
is placed within arc $ED$ arbitrarily close to point $D=c(0)$ (again the
maximum is not attained because point $D$ was visited before, so we report the
supremum). But then, the target is found by agent $A_{1}$ in time
$T_{1}=1+\alpha_{w}+2\sin\left(\beta_{w}/2\right)+\beta_{w}$, while agent
$A_{0}$ arrives at point $D$ at time

$T_{0}=1+2\pi-\alpha_{w}-\beta_{w}+2\sin\left(\beta_{w}/2\right).$

That is, in the current case the termination cost equals

$c_{4}=\frac{g_{w}(T_{0},T_{1})}{g_{w}(1,1)}=1+2\sin\left(\beta_{w}/2\right)+\frac{\alpha_{w}+\beta_{w}+w(-\alpha_{w}-\beta_{w}+2\pi)}{w+1},$

which also concludes the termination cost analysis for all cases 1,2,3,4.

In order to conclude the claim of Lemma 6 by calculating the termination cost
of the $(\alpha_{w},\beta_{w})$-Detour Algorithm when $w\leq w_{0}$, which
equals

$\max\\{c_{1},c_{2},c_{3},c_{4}\\}.$

Note that $c_{1}=c_{2}$, and as per the statement of Lemma 5 the values of
parameters $\alpha_{w},\beta_{w}$, as a function of $w$, where chosen
specifically by requiring that $c_{1}=c_{3}=c_{4}$. Therefore, the termination
cost is also described by the formula derived in Case 1, that is
$1+\alpha_{w}+\frac{2\sin\left(\alpha_{w}\right)}{w+1}$. ∎

###  5.2 Lower Bounds to Weighted Group Search on the Disk

In this section we give the details of how we obtained the lower bound values
to $\textsc{WS}_{\textsc{disk}}^{g_{w}}$ reported in Figure 1.

###### Theorem 5.1

For all $w\in[0,1]$, no algorithm for $\textsc{WS}_{\textsc{disk}}^{g_{w}}$
has evacuation cost less than
$\max\left\\{1+\pi,1+\pi/7+\frac{1}{w+1}\cos\left(3\pi/14\right)+5\sin\left(\pi/7\right)\right\\}\approx\max\left\\{4.14159,3.61822+\frac{0.781831}{w+1}\right\\}.$

We start with a weak lower bound.

###### Lemma 7

No algorithm for $\textsc{WS}_{\textsc{disk}}^{g_{w}}$ has evacuation cost
less than $1+\pi$.

###### Proof

An arbitrary algorithm for $\textsc{WS}_{\textsc{disk}}^{g_{w}}$ needs time at
least $1+\pi$ to search the entire domain. This means that there is always a
target placement for which the termination time of each agent is at least
$1+\pi-\epsilon$, resulting in overall search cost
$\frac{g_{w}(1+\pi-\epsilon,1+\pi-\epsilon)}{w+1}=1+\pi-\epsilon.$ ∎

Notably, the result is tight for $w=1$. Indeed, by Lemma 6 the upper bound for
$\textsc{WS}_{\textsc{disk}}^{g_{1}}$ uses the $(\pi,0)$-Detour Algorithm with
performance $1+d_{1}+2\sin\left(d_{1}\right)2=1+\pi$ (note that
$d_{1}=\arccos\left(-\tfrac{1+1}{2}\right)=\pi$).

For small values of $w$, we obtain better bounds by deriving lower bounds to
$\textsc{WS}_{n\textsc{-gon}}^{g_{w}}$ for $n=7$. Unlike how we approached
$\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$ (which is the same as
$\textsc{WS}_{\textsc{disk}}^{g_{0}}$), this time we need to solve
$\textsc{REL}^{g_{w}}_{n}\left(\rho,b,1+\frac{\pi}{n}\right)$ not only for all
permutations $\rho$ and binary strings $b$, but also for enough many values of
$w\in[0,1]$. In this direction, we use $n=7$ and compute the lower bounds to
$\textsc{WS}_{\textsc{disk}}^{g_{w}}$ from $w=0$ up to $1$ with step size
$0.001$444Considering $7$-Gons for our proof is the highest value we could
handle computationally, due to the large number of $w$ values we needed to
consider. For comparison, the results we obtained for
$\textsc{WS}_{\textsc{disk}}^{\textrm{proj}_{2}}$ using $9$-Gons took several
days to be computed. The order by which the number of configurations increase
between $n$-Gons and $(n+1)$-Gons, each time computing
$\textsc{REL}^{g_{w}}_{n}\left(\rho,b,1+\frac{\pi}{n}\right)$, is $2n$, but
this does not take into account the additional computation cost for solving
much larger linear programs with $\Theta(n^{2})$ variables and $\Theta(n^{3})$
constraints. . The following is a strict generalization of the results in
Table 1 pertaining to $\textsc{WS}_{7\textsc{-gon}}^{g_{w}}$ with $n=7$, and
was obtained by computer assisted calculations for determining the minimum
value of $\textsc{REL}^{g_{w}}_{7}\left(\rho,b,1\right)$ over all permutations
$\rho$ and binary strings $b$.

###### Lemma 8

No algorithm for $\textsc{WS}_{7\textsc{-gon}}^{g_{w}}$ has evacuation cost
less than
$1+\frac{1}{w+1}\cos\left(\tfrac{3\pi}{14}\right)+5\sin\left(\tfrac{\pi}{7}\right).$

Strictly speaking the bound of Lemma 8 equals
$\min_{\rho\in\mathcal{R}_{7},b\in[1]^{7}}\textsc{REL}^{g_{w}}_{7}\left(\rho,b,1\right)$
only for $w\leq 0.8$ (for higher values, this technique gives a slightly
better lower bound), however, this is already subsumed by the bound of Lemma
7. We conclude that for each $w$, and using Lemma 4 and the calculations (2),
no algorithm for $\textsc{WS}_{\textsc{disk}}^{g_{w}}$ has evacuation cost
less than

$\frac{1}{g_{w}(1,1)}\min_{\rho\in\mathcal{R}_{7},b\in[1]^{7}}\textsc{REL}^{g_{w}}_{7}\left(\rho,b,1+\frac{\pi}{7}\right)=\frac{\pi}{7}+\min_{\rho\in\mathcal{R}_{7},b\in[1]^{7}}\textsc{REL}^{g_{w}}_{7}\left(\rho,b,1\right),$

where in particular $\textsc{REL}^{g_{w}}_{7}\left(\rho,b,1\right)$ is a lower
bound to the optimal $(\rho,b)$-algorithm for
$\textsc{WS}_{7\textsc{-gon}}^{g_{w}}$. To resume, we solve
$\textsc{REL}^{g_{w}}_{7}(\rho,b,1)$ for all permutations
$\rho\in\mathcal{R}_{7}$ and all binary strings $b\in[1]^{n}$, and we report
the smallest values in Lemma 8. Overall, this implies that no algorithm for
$\textsc{WS}_{\textsc{disk}}^{g_{w}}$ has search cost less than
$1+\pi/7+\frac{1}{w+1}\cos\left(3\pi/14\right)+5\sin\left(\pi/7\right).$ This
observation, together with Lemma 7 give the proof of Theorem 5.1. Lastly we
note that the transition value of $w$ for which the lower bound of Lemma 7 is
weaker equals

$\tfrac{7\cos\left(\frac{3\pi}{14}\right)}{6\pi-35\sin\left(\frac{\pi}{7}\right)}-1\approx
0.493827.$

##  6 Conclusion

It this work we studied the weighted group search problem on the disk with 2
agents operating in the wireless model, a problem that was previously studied
on the line. The weighted problem on the disk is a generalization of the so-
called priority evacuation problem, for which the best upper and lower bounds
known exhibit a significant gap. For the problem on the disk, we designed and
analyzed algorithms that adapt with the underlying cost function. We
complemented our results by providing lower bounds for the entire spectrum of
arithmetic weighted average cost functions. Our most significant contribution
is the framework we developed in order to prove the lower bounds. More
specifically, we introduced linear programs, which arise as relaxations to
non-linear programs modeling the behavior of optimal solutions to
combinatorial search type problems. The framework is applicable to more
general cost functions, as well as it can be adjusted to provide lower bounds
to highly asymmetric searchers' specifications. Among others, we demonstrate
the power of this technique by improving the previously best lower bound known
for priority evacuation, from $4.38962$ to $4.56798$. The bound can be further
improved if one uses the provided framework and utilizes more efficient
computational tools, e.g. software tailored to solving LPs (the current
symbolic results were obtained using Mathematica). One of the the most
challenging future directions in the area would be to consider other
searchers' communication models, including the face-to-face model, that has
been proved to be challenging even with standard cost functions.

## References

  * [1] S. Alpern, R. Fokkink, L. Gasieniec, R. Lindelauf, and V. Subrahmanian.  Search Theory: A Game Theoretic Perspective.  Springer, 2013.
  * [2] S. Alpern and S. Gal.  The Theory of Search Games and Rendezvous.  Kluwer, 2003.
  * [3] S. Angelopoulos, C. Dürr, and S. Jin.  Best-of-two-worlds analysis of online search.  In R. Niedermeier and C. Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 7:1–7:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [4] S. Angelopoulos, C. Dürr, and T. Lidbetter.  The expanding search ratio of a graph.  Discret. Appl. Math, 260:51–65, 2019.
  * [5] R. Baeza Yates, J. Culberson, and G. Rawlins.  Searching in the plane.  Information and Computation, 106(2):234–252, 1993.
  * [6] E. Bampas, J. Czyzowicz, L. Gasieniec, D. Ilcinkas, R. Klasing, T. Kociumaka, and D. Pajak.  Linear search by a pair of distinct-speed robots.  Algorithmica, 81(1):317–342, 2019.
  * [7] A. Beck.  On the linear search problem.  Israel Journal of Mathematics, 2(4):221–228, 1964.
  * [8] A. Bonato, K. Georgiou, C. MacRury, and P. Prałat.  Algorithms for p-faulty search on a half-line.  Algorithmica, pages 1–30, 2022.
  * [9] P. Borowiecki, S. D. 0001, D. Dereniowski, and L. Kuszner.  Distributed evacuation in graphs with multiple exits.  In J. Suomela, editor, Structural Information and Communication Complexity - 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland, July 19-21, 2016, Revised Selected Papers, volume 9988 of Lecture Notes in Computer Science, pages 228–241, 2016.
  * [10] S. Brandt, K.-T. Foerster, B. Richner, and R. Wattenhofer.  Wireless evacuation on m rays with k searchers.  Theor. Comput. Sci, 811:56–69, 2020.
  * [11] M. Chrobak, L. Gasieniec, T. Gorry, and R. Martin.  Group search on the line.  In G. F. Italiano, T. Margaria-Steffen, J. Pokorný, J.-J. Quisquater, and R. Wattenhofer, editors, SOFSEM, volume 8939 of Lecture Notes in Computer Science, pages 164–176. Springer, 2015.
  * [12] H. Chuangpishit, K. Georgiou, and P. Sharma.  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.  Information, 11(11):506, 2020.
  * [13] H. Chuangpishit, S. Mehrabi, L. Narayanan, and J. Opatrny.  Evacuating equilateral triangles and squares in the face-to-face model.  Comput. Geom, 89:101624, 2020.
  * [14] J. Czyzowicz, S. Dobrev, K. Georgiou, E. Kranakis, and F. MacQuarrie.  Evacuating two robots from multiple unknown exits in a circle.  In ICDCN, pages 28:1–28:8. ACM, 2016.
  * [15] J. Czyzowicz, L. Gasieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pajak.  Evacuating robots via unknown exit in a disk.  In F. Kuhn, editor, DISC 2014, volume 8784 of Lecture Notes in Computer Science, pages 122–136. Springer, 2014.
  * [16] J. Czyzowicz, K. Georgiou, M. Godon, E. Kranakis, D. Krizanc, W. Rytter, and M. Wlodarczyk.  Evacuation from a disc in the presence of a faulty robot.  In S. Das and S. Tixeuil, editors, SIROCCO 2017, volume 10641 of Lecture Notes in Computer Science, pages 158–173. Springer, 2017.
  * [17] J. Czyzowicz, K. Georgiou, R. Killick, E. Kranakis, D. Krizanc, M. Lafond, L. Narayanan, J. Opatrny, and S. Shende.  Energy Consumption of Group Search on a Line.  In C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 137:1–137:15, Dagstuhl, Germany, 2019\. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [18] J. Czyzowicz, K. Georgiou, R. Killick, E. Kranakis, D. Krizanc, M. Lafond, L. Narayanan, J. Opatrny, and S. Shende.  Time-energy tradeoffs for evacuation by two robots in the wireless model.  Theoretical Computer Science, 852:61–72, 2021.
  * [19] J. Czyzowicz, K. Georgiou, R. Killick, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. Shende.  Priority evacuation from a disk: The case of n= 1, 2, 3.  Theoretical Computer Science, 806:595–616, 2020.
  * [20] J. Czyzowicz, K. Georgiou, R. Killick, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. Shende.  Priority evacuation from a disk: The case of $n\geq 4$.  Theoretical Computer Science, 846:91–102, 2020.
  * [21] J. Czyzowicz, K. Georgiou, and E. Kranakis.  Group search and evacuation.  In Distributed Computing by Mobile Entities, pages 335–370. Springer, 2019.
  * [22] J. Czyzowicz, K. Georgiou, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. Shende.  Search on a line by byzantine robots.  International Journal of Foundations of Computer Science, 32(04):369–387, 2021.
  * [23] J. Czyzowicz, R. Killick, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, D. Pankratov, and S. Shende.  Group evacuation on a line by agents with different communication abilities.  ISAAC 2021, pages 57:1–57:24, 2021.
  * [24] J. Czyzowicz, R. Killick, E. Kranakis, and G. Stachowiak.  Search and evacuation with a near majority of faulty agents.  In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), pages 217–227. SIAM, 2021.
  * [25] J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, and J. Opatrny.  Search on a line with faulty robots.  Distributed Comput, 32(6):493–504, 2019.
  * [26] J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. M. Shende.  Wireless autonomous robot evacuation from equilateral triangles and squares.  In S. Papavassiliou and S. Ruehrup, editors, 14th International Conference, ADHOC-NOW, volume 9143 of Lecture Notes in Computer Science, pages 181–194. Springer, 2015.
  * [27] Y. Disser and S. Schmitt.  Evacuating two robots from a disk: a second cut.  In International Colloquium on Structural Information and Communication Complexity, pages 200–214. Springer, 2019.
  * [28] O. Feinerman and A. Korman.  The ants problem.  Distributed Computing, 30(3):149–168, 2017.
  * [29] S. P. Fekete, C. Gray, and A. Kröller.  Evacuation of rectilinear polygons.  In W. Wu and O. Daescu, editors, Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part I, volume 6508 of Lecture Notes in Computer Science, pages 21–30. Springer, 2010.
  * [30] P. Flocchini, G. Prencipe, and N. Santoro, editors.  Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science.  Springer, 2019.
  * [31] K. Georgiou, N. Giachoudis, and E. Kranakis.  Evacuation from a disk for robots with asymmetric communication.  In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [32] K. Georgiou and W. Jang.  Triangle evacuation of 2 agents in the wireless model.  In Algorithmics of Wireless Networks: 18th International Symposium on Algorithmics of Wireless Networks, ALGOSENSORS 2022, Potsdam, Germany, September 8–9, 2022, Proceedings, pages 77–90. Springer, 2022.
  * [33] K. Georgiou, G. Karakostas, and E. Kranakis.  Search-and-fetch with 2 robots on a disk: Wireless and face-to-face communication models.  Discrete Mathematics & Theoretical Computer Science, 21, 2019.
  * [34] K. Georgiou, E. Kranakis, N. Leonardos, A. Pagourtzis, and I. Papaioannou.  Optimal circle search despite the presence of faulty robots.  In F. Dressler and C. Scheideler, editors, ALGOSENSORS 2019, volume 11931 of Lecture Notes in Computer Science, pages 192–205. Springer, 2019.
  * [35] K. Georgiou, S. Leizerovich, J. Lucier, and S. Kundu.  Evacuating from $\ell_{p}$ unit disks in the wireless model.  Theoretical Computer Science, 944:113675, 2023.
  * [36] K. Georgiou and J. Lucier.  Weighted group search on a line & implications to the priority evacuation problem.  Theoretical Computer Science, 939:1–17, 2023.
  * [37] R. Hohzaki.  Search games: Literature and survey.  Journal of the Operations Research Society of Japan, 59(1):1–34, 2016.
  * [38] A. Miller and A. Pelc.  Tradeoffs between cost and information for rendezvous and treasure hunt.  J. Parallel Distributed Comput, 83:159–167, 2015.
  * [39] X. Sun, Y. Sun, and J. Zhang.  Better upper bounds for searching on a line with byzantine robots.  In Complexity and Approximation, pages 151–171. Springer, 2020\.