Search-and-Fetch with 2 Robots on a Disk:
Wireless and Face-to-Face Communication Models ∗
Konstantinos Georgiou† ¶

George Karakostas‡ ¶

Evangelos Kranakis§ ¶

arXiv:1611.10208v1 [cs.DS] 30 Nov 2016

December 1, 2016

Abstract
We initiate the study of a new problem on searching and fetching in a distributed environment concerning treasure-evacuation from a unit disk. A treasure and an exit are located at unknown positions
on the perimeter of a disk and at known arc distance. A team of two robots start from the center of the
disk, and their goal is to fetch the treasure to the exit. At any time the robots can move anywhere they
choose on the disk, independently of each other, with the same speed. A robot detects an interesting
point (treasure or exit) only if it passes over the exact location of that point. We are interested in designing distributed algorithms that minimize the worst-case treasure-evacuation time, i.e. the time it takes
for the treasure to be discovered and brought (fetched) to the exit by any of the robots.
The communication protocol between the robots is either wireless, where information is shared at
any time, or face-to-face (i.e. non-wireless), where information can be shared only if the robots meet.
For both models we obtain upper bounds for fetching the treasure to the exit. Our main technical contribution pertains to the face-to-face model. More specifically, we demonstrate how robots can exchange
information without meeting, effectively achieving a highly efficient treasure-evacuation protocol which
is minimally affected by the lack of distant communication. Finally, we complement our positive results
above by providing a lower bound in the face-to-face model.

1

INTRODUCTION

We introduce the study of a new distributed problem on searching and fetching called treasure evacuation.
Two robots are placed at the center of a unit disk, while an exit and a treasure lie at unknown positions on
the perimeter of the disk. Robots search with maximum speed 1, and they detect an interesting point (either
the treasure or the exit) only if they pass over it. The exit is immobile, while the treasure can be carried
by any of the robots. The goal of the search is for at least one of the robots to bring (fetch) the treasure to
the exit, i.e. evacuate the treasure, in the minimum possible completion time. The robots do not have to
evacuate, rather they only need to co-operate, possibly by sharing information, so as to learn the locations
of the interesting points and bring the treasure to the exit. Contrary to previous work, this is the first time an
explicit ordering on the tasks to be performed is imposed (first the treasure, then the exit). This makes the
problem inherently different in nature and more difficult than similarly looking results.
¶

Research supported in part by NSERC of Canada.
Dept. of Mathematics, Ryerson University, Toronto, ON, Canada, konstantinos@ryerson.ca
‡
Dept. of Computing & Software, McMaster University, Hamilton ON, Canada, karakos@mcmaster.ca
§
School of Computer Science, Carleton University, Ottawa ON, Canada, kranakis@scs.carleton.ca
∗
This is the full version of the paper with the same title which will appear in the proceedings of the 6th International Conference
on Operations Research and Enterprise Systems (ICORES), February 23-25, 2017, Porto, Portugal.
†

1

Finding an optimal algorithm turns out to be a challenging task even when the robots have some knowledge, e.g., the arc-distance α between the exit and the treasure. We propose treasure-evacuation protocols in
two communication models. In the wireless model robots exchange information instantaneously and at will,
while in the face-to-face model information can be exchanged only if the robots meet. We aim at incorporating this knowledge into our algorithm designs. We offer algorithmic techniques such as planning ahead,
timing according to the explicit task ordering, and retrieval of unknown information through inference and
not communication.
Part of our contribution is that we demonstrate how robots can utilize the knowledge of the arc-distance
α between the interesting points. We propose protocols that induce worst case evacuation time 1+π −α/2+
3 sin (α/2) for the wireless model and 1 + π − α + 4 sin (α/2) for the face-to-face model. The upper bound
in the face-to-face model, which is our main contribution, is the result of a non-intuitive evacuation protocol
that allows robots to exchange information about the topology without meeting, effectively bypassing their
inability to communicate from distance. Finally, we complement our results above by showing that any
algorithm in the face-to-face model needs time at least 1 + π/3 + 4 sin (α/2), if α ∈ [0, 2π/3] and at least
1 + π/3 + 2 sin (α) + 2 sin (α/2), if α ∈ [2π/3, π].

1.1

Contributions

Rendezvous, treasure hunting and exploration have been subjects of extensive research in the broad area
of distributed and online computing (see related work below). Challenges in each of these fundamental
tasks arise from different computation, communication or knowledge limitations, with admittedly numerous
variations. The novel distributed problem of treasure-evacuation that we introduce and study in this work
combines in a complex way challenges from all these fundamental tasks. As such, progress towards solving
generic treasure-evacuation-like problems will unavoidably touch on state-of-the-art techniques of achieving
these tasks.
In treasure-evacuation, two stationary targets (a treasure and an exit that we call interesting points) are
hidden on a specific domain. At first, robots need to (a) perform treasure hunting in this online environment.
Interestingly, the knowledge of the location of one of these targets may or may not reveal the location of
the other. In particular, the task of the robots does not end when both interesting points are located, rather,
only when the treasure-holder learns (and finds) the location of the exit as well. Given communication
limitations, the latter can be accomplished efficiently only if (b) a sufficient portion of the environment is
explored before both interesting points are found, or (c) if information can be exchanged between robots.
In case (b), robots “invest” in domain exploration in an attempt to expedite treasure evacuation once the
interesting points are found. In case (c), robots may need to attempt to rendezvous (not very late in the time
horizon) so that the distributed system becomes cognitive of the environment and consequently completes
the given task. Clearly, in order for a distributed system to accomplish treasure evacuation efficiently, robots
need to perform and balance all tasks (a),(b),(c) above, i.e to perform treasure hunting, while learning the
environment either by exploration or by rendezvous. A unique feature of treasure-evacuation is that only the
treasure has to be brought to the exit.
The last observation gives some first evidence of the difficulty of solving treasure-evacuation, even when
the domain is a disk. Can a robot choose a trajectory (maybe staying far from the exit) to help the treasureholder expedite evacuation? If a robot discovers the treasure, is it a good strategy to become the treasure
holder and greedily search for the exit? Should robots learn the environment by investing on exploration or
on rendezvous and hence on message exchange? Finally, is it possible in a non-wireless environment for
robots to exchange information without meeting? An efficient algorithm should somehow address all these
questions.
2

From the discussion above, it is not a surprise that plain vanilla algorithms cannot be efficient. Indeed,
our algorithms (for both the wireless and face-to-face models) adapt their strategies, among others, with
respect to the distance of the interesting points. On one hand, there are configurations where the evacuation
protocols are simple and greedy-like. However, the reader can verify from our analyses that, had we followed
such simplistic approach for all configurations, the evacuation time would have been much worse than our
upper bounds. The simplest example of this kind will be transparent even in the analysis of the wireless
model, in which robots can exchange information at will. To achieve our upper bound, robots choose
different trajectories (still greedy-like) for various distances of the interesting points. Nevertheless, the
analysis in this case is relatively simple.
Our main technical contribution pertains to the face-to-face model where robots can exchange information only if they meet. In particular, we explicitly exhibit distributed strategies that allow robots to
exchange information even from distance. At a high level, and given that interesting points are located by
robots at some (carefully defined) critical intervals in the time horizon, robots choose (occasionally) highly
non-intuitive trajectories, not in order to locate the remaining interesting points, rather to potentially meet
their fellow robots. The trajectories are carefully chosen so that a robot may deduce information, using
an involved protocol, as to what the other robot has found, and hence learn the environment regardless of
whether the rendezvous is realized or not. For the treasure-holder, this would result in learning the location
of the exit. For the other robot(s), this would be an altruistic attempt to help the fellow treasure-holder. In
particular, that could result in that the non treasure-holder never finds the exit, still expediting the treasure
evacuation time. We note that once the trajectories are determined (which is the heart of our contribution)
correctness and performance analysis is a matter of an exhaustive and technical case analysis. Interestingly,
the efficiency of our algorithm for the face-to-face model is only slightly worse than the solution for the
wireless case (but significantly better than the naive solution for the face-to-face model), indicating that lack
of communication can be compensated by clever algorithms.
Finally, we complement our results by proving some lower bounds for treasure evacuation with 2 robots
for the face-to-face model. That concludes the first attempt to study distributed problems of this kind, i.e.
optimization treasure hunting problems where the distributed systems learn the online environment by a
combination of exploration and rendezvous, a feature which, to the best of our knowledge, is also novel.

1.2

Related Work

Traditional search is concerned with finding an object with specified properties within a search space.
Searching in the context of computational problems is usually more challenging especially when the environment is unknown to the searcher(s) (see [1, 4, 34]). This is particularly evident in the context of
robotics whereby exploration is taking place within a given geometric domain by a group of autonomous
but communicating robots. The ultimate goal is to design an algorithm so as to accomplish the requirements
of the search (usually locating a target of unknown a priori position) while at the same time obeying the
computational and geographical constraints. The input robot configuration must also accomplish the task in
the minimum possible amount of time [10].
Search has a long history. There is extensive and varied research and several models have been proposed
and investigated in the mathematical and theoretical computer science literature with particular emphasis
on probabilistic search [34], game theoretic applications [4], cops and robbers [11], classical pursuit and
evasion [32], search problems as related to group testing [1], searching a graph [31], and many more. A
survey of related search and pursuit evasion problems can be found in [14]. In pursuit-evasion, pursuers
want to capture evaders who try to avoid capture. Examples include Cops and Robbers (whereby the cops
try to capture the robbers by moving along the vertices of a graph), Lion and Man (a geometric version of
3

cops and robbers where a lion is to capture a man in either continuous or discrete time), etc. Searching
for a motionless point target has some similarities with the lost at sea problem, [23, 26], the cow-path
problem [8, 9], and with the plane searching problem [7]. This last paper also introduced the “instantaneous
contact model”, which is referred to as wireless model in our paper. When the mobile robots do not know the
geometric environment in advance then researchers are concerned with exploring [2, 3, 20, 25]. Coordinating
the exploration of a team of robots is a main theme in the robotics community [12, 35, 36] and often this is
combined with the mapping of the terrain and the position of the robots within it [30, 33].
Evacuation for grid polygons has been studied in [21] from the perspective of constructing centralized
evacuation plans, resulting in the fastest possible evacuation from the rectilinear environment. There are
certain similarities of our problem to the well-known evacuation problem on an infinite line (see [6] and the
recent [13]) in that the search is for an unknown target. However, in this work the adversary has limited possibilities since search is on a line. Additional research and variants on this problem can be found in [19] (on
searching with turn costs), [29] (randomized algorithm for the cow-path problem), [28] (hybrid algorithms),
and many more.
A setting similar to ours is presented in the recent works [15, 16, 17, 18] where algorithms are presented
in the wireless and non-wireless (or face-to-face) communication models for the evacuation of a team of
robots. The “search domain” in [15, 16, 17] is a unit circle (while in [18] the search domain is a triangle
or square), however, unlike our search problem, in these papers all the robots are required to evacuate from
an unknown exit on the perimeter. Moreover, in none of these papers is there a treasure to be fetched to the
exit.
Our work is also an attempt to analyze theoretically search-and-fetch problems that have been studied
by the robotics community since the 90’s, e.g. see [27]. A scenario similar to ours (but only for 1 robot)
has been introduced by Alpern in [5], where the domain was discrete (a tree) and the approach/analysis
resembled that of standard search-type problems [4]. In contrast, our problem is of distributed nature, and
our focus is to demonstrate how robots’ communication affects efficiency.

1.3

Problem and Model Motivation

Our problem is motivated by real-life surveillance and search-and-rescue operations where unmanned vehicles, e.g. drones, search for victims in areas of a disaster. Indeed, consider a group of rescuer-mobile-agents
(robots), initially located strategically in a central position of a domain. When alarm is triggered and a
distress signal is received, robots need to locate a victim (the treasure) and bring her to safety (the exit).
Our problem shares similarities also with classic and well-studied cops-and-robbers games; robots rest at a
central position of a domain (say, in the centre of a disk as in our setup) till an alarm is triggered by some
“robber” (the treasure in our case). Then, robots need to locate the stationary robber and subsequently bring
him to jail (the exit). Interestingly, search-and-fetch type problems resemble also situations that abound in
fauna, where animals hunt for prey which is then brought to some designated area, e.g. back to the lair. As
such, further investigation of similar problems will have applications to real-life rescue operations, as well
as to the understanding of animal behavior, as it is common in all search problems.
From a technical perspective, our communication models are inspired by the recent works on evacuation
problems [15, 17, 18]. Notably, the associated search problems are inherently different than our problem
which is closer in nature to search-type, treasure-hunt, and exploration problems. Also, our mathematical
model features (a) a distributed setting (b) with objective to minimize time, and (c) where different communication models are contrasted. None among (a),(b),(c) are well understood for search games, and, to the
best of our knowledge, they have not been studied before in this combination.
Specific to the problem we study are the number of robots (2 and not arbitrarily many - though our results
4

easily extend to swarms of robots), the domain (disk), and the fact the robots have some knowledge about the
interesting points. Although extending our results to more generic situations is interesting in its own right,
the nature of the resulting problems would require a significantly different algorithmic approach. Indeed,
our main goal is to study how limitations in communication affect efficiency, which is best demonstrated
when the available number of robots, and hence computation power, is as small as possible, i.e. for two
robots. In fact, it is easy to extend our algorithms for the n-robot case.
Notably, search-and-fetch problems are challenging even for 1 robot as demonstrated in [22]. In particular, the work of [22] implies that establishing provably optimal evacuation protocols for 2-robots is a
difficult task, even when the domain is the disk. Nevertheless, we view the domain that we study as natural.
Indeed, a basic setup in search-and-rescue operations is that rescuer-robots inhabit in a base-station, and they
stay inactive till they receive a distress signal. As it is common in real-life situations, the signal may only
reveal partial information about the location of a victim, e.g. its distance from the base-station, along with
the distance between the points. When there are more than one interesting points to be located, this kind
of information suggests that the points lie anywhere on co-centric circles. When the points are equidistant
from the base-station, robots need only consider a disk, as it is the case in our problem. We believe that
with enough technical and tedious work, our results can also extend to non-equidistant points, however the
algorithmic significance of the proposed distributed solutions may be lost in the technicalities.
In order to demonstrate that robots with primitive communication capabilities are in fact not much less
powerful than in the wireless model, it is essential to assume that robots have some knowledge of the distance
between the interesting points. The reader may also view this piece of advice as an algorithmic challenge
in order to bypass the uncertainty regarding the locations of the interesting points. Notably, our algorithms
adapt strategies as a function of the distance of the interesting points, trying to follow protocols that would
allow them to detect the actual positions of the points without necessarily visiting them. As an easy example,
note that if a robot has explored already a contiguous arc of length α+, the discovery of an interesting point
reveals the location of the other α-arc distant away interesting point (our algorithm makes use of distance
α in a much more sophisticated way). As a result, had we assumed that distances are unknown, robots
may not be able to deduce such important information about the topology using partial exploration, and the
problem would require an inherently different algorithmic approach. Apart from that, partial knowledge
of the input is also interesting due to the efficiency-information tradeoffs that are naturally induced by the
problem, which is also a standard theme in competitive analysis, e.g. see [24] and [22].
Admittedly, the model we introduce is simple but natural, general, and complex enough to require
non-standard algorithmic solutions. Most importantly, our model allows us to demonstrate in a relatively
clean way a couple of novel algorithmic techniques for attacking challenging and newly introduced types
of distributed problems. We anticipate that the ideas introduced in this work will initiate new research
directions towards solving a family of problems that are not yet understood from a theoretical perspective.

1.4

Notation & Organization

A treasure and an exit are located at unknown positions on the perimeter of a unit-disk and at arc distance α
(in what follows all distances will be arc-distances, unless specified otherwise). Robots start from the center
of the disk, and can move anywhere on the disk at constant speed 1. Each of the robots detects the treasure
or the exit only if its trajectory passes over that point on the disk. Once detected, the treasure can be carried
by a robot at the same speed. We refer to the task of bringing the treasure to the exit as treasure-evacuation.
We use the abbreviations T, E for the treasure and the exit, respectively. For convenience, in the sequel we
will refer to the locations of the exit and the treasure as interesting points. For an interesting point I on the
perimeter of the disk, we also write I = E (I = T ) to indicate that the exit (treasure) lies in point I. For a
5

point B, we also write B = null to denote the event that neither the treasure nor the exit is placed on B.
We focus on the following online variations of treasure-evacuation with 2 robots, where the exact distance α between T, E is known, but not their positions. In 2-TEw (Section 2), information between robots
is shared continuously in the time horizon, i.e. messages between them are exchanged instantaneously and
at will with no restrictions and no additional cost or delays. In 2-TEf 2f (Section 3), the communication protocol between the robots is face-to-face (non-wireless)—abbreviated F2F (or f2f), where information can be
exchanged only if the robots meet at the same point anywhere. We give two algorithms: in the former case
we prove a 1 + π − α + 4 sin (α/2) and in the latter case a 1 + π − α/2 + 3 sin (α/2) upper bound, resp.,
on the treasure evacuation time, where α is the arc distance between treasure and exit. Finally in Section 4
we provide a lower bound for treasure-evacuation with 2 robots in the F2F model.
A graphical comparison of our results can be seen in Figure 1.

5

4

3

0.5

1.0

1.5

2.0

2.5

3.0

Figure 1: Comparison between the performance of the wireless algorithm (blue curve), the performance of
the f2f algorithm (yellow curve) and the provided lower bound (green curve).

2

WIRELESS MODEL

As a warm-up we present in this section an upper bound for the wireless model, which will also serve as a
reference for the more challenging face-to-face model. The algorithmic solution we propose is simple and
it is meant to help the reader familiarize with basic evacuation trajectories that will be used in our main
contribution pertaining to the face-to-face model.
Theorem 2.1. For every α ∈ [0, π], problem 2-TEw can be solved in time 1 + π − α + 4 sin (α/2).
To prove Theorem 2.1, we propose Algorithm 1 that achieves the promised bound. Intuitively, our algorithm follows a greedy like approach, adapting its strategy as a function of the distance α of the interesting
points. If α is small enough, then the two robots move together to an arbitrary point on the disk and start exploring in opposing directions. Otherwise the two robots move to two antipodal points and start exploring in
6

the same direction. Exploration continues till an interesting point is found. When that happens, the robot that
can pick up the treasure and fetch it to the exit in the fastest time (if all locations have been revealed) does
so, otherwise remaining locations are tried exhaustively. Detailed descriptions of the evacuation protocol
can be seen in Algorithm 1, complemented by Figure 2.
Noticeably, the performance analysis we give is tight, meaning that for every α ≥ 0, there are configurations (placements of the interesting points) for which the performance of the algorithm is exactly
1 + π − α + 4 sin (α/2). Most importantly, the performance analysis makes explicit that naive algorithms
that do not adapt strategies together with α are bound to perform strictly worse than our upper bound. Also,
the achieved upper bound should be contrasted to the upper bound for the face-to-face model (which is
achieved by a much more involved algorithm), which at the same time is only α/2 − sin (α/2) more costly
than the bound we show in the wireless model.
Algorithm 1 takes advantage of the fact that robots can communicate to each other wirelessly. This also
implies that lack of message transmission is effectively another method of information exchange. In what
follows point A will always be the starting point of R2 , and A0 denotes its antipodal point. For the sake of
the analysis and w.l.o.g. we will assume that R2 is the one that first finds an interesting point I = {E, T },
_
say at time x := AI. We call B, C the points that are at clockwise and counter-clockwise arc-distance α
from I respectively. Figure 2 depicts the interesting points encountered.
𝛼𝛼

𝐶𝐶

𝐴𝐴

𝐼𝐼

𝑂𝑂

𝛼𝛼

𝛼𝛼

𝐴𝐴

𝐼𝐼

𝑂𝑂

𝐵𝐵

𝐶𝐶

𝛼𝛼 ≤ 2𝜋𝜋/3

𝐴𝐴′

𝛼𝛼 > 2𝜋𝜋/3

𝛼𝛼

𝐵𝐵

Figure 2: The points of interest for our Algorithm 1.

The description of Algorithm 1 is from the perspective of the robot that finds first an interesting point,
that we always assume is R2 . Next we assume that the finding of any interesting point is instantaneously
transmitted and received by the two robots. Also, if at any moment, the positions of the interesting points
are learned by the two robots, then the robots attempt a “confident evacuation” using the shortest possible
trajectory. This means for example that if the treasure is not picked up by any robot, then the two robots will
compete in order to pick it up and return it to the exit, moving in the interior of the disk.
Correctness of Algorithm 1 is straightforward, since the two robots follow a “greedy-like evacuation
protocol” (still, they use different starting points depending on the value of α). Also, the performance
analysis of the algorithm, effectively proving Theorem 2.1, is a matter of a straightforward case-analysis.
We note that our worst-case analysis is tight, in that for every α ≥ 0 there exist configurations in which the
7

Algorithm 1 Wireless Algorithm
Step 1. If α ≤ 2π/3, then the two robots move together to an arbitrary point on the ring and start moving in
opposing directions, else they move to arbitrary antipodal points A, A0 on the cycle and start moving
in the same direction.
_
Step 2. Let I be the first interesting point discovered by R2 , at time x := AI. Let B, C be the points that
are at clockwise and counter-clockwise arc-distance α from I respectively.
Step 3. If x ≥ α/2 then robots learn that the other interesting point is in B, else R2 moves to B, R1 moves
to C.
Step 4. Evacuate

performance is exactly as promised by Theorem 2.1. Moreover, we may assume that α > 0 as otherwise the
problem is solved when one interesting point is found.
_
Note that our algorithm performs differently when α ≤ 2π/3 and when α > 2π/3. Let x := AI be the
time that R2 first discovers interesting point I. Then it must be that x ≤ α/2 and x ≤ π − α for the cases
α ≤ 2π/3 and α > 2π/3 respectively (see also Figure 2). This will be used explicitly in the proof of the
next two lemmata. We also assume that R2 always moves clockwise starting from point A. R1 either moves
counter-clockwise starting from A, if α ≤ 2π/3, or it moves clockwise starting from the antipodal point A0
of A, if α > 2π/3. In every case, the two robots move along the perimeter of the disk till time x when R2
transmits the message that it found an interesting point.
The performance of Algorithm 1 is described in the next two lemmata which admit proofs by case
analyses. Each of them examines the relative position of the starting point of robot R2 (which finds an
interesting point first) and the two interesting points.
Lemma 2.2. Let A be the starting point of R2 which is the first to discover an interesting point I. Let also
_
_
the other interesting point be at C, where CI = α. If A lies in the arc CI, then the performance of Algorithm
1 is 1 + π − α + 4 sin (α/2), for all α ∈ [0, π].
Proof. For the case analysis below, we rely on Figure 3. Note that robots spend time 1 to reach the periphery
of the disk. Below we calculate the remaining time until evacuation. At time x the cases are as follows.
_
(I = E, B = null, C = T & α ≤ 2π/3): Let R1 be at point D, i.e. DA = x, see also Figure 3i. Then R1
moves along the chord CD, it locates the treasure and returns it to the exit I, with total cost
_
DA + DC + CI =x + 2 sin (α/2 − x) + 2 sin (α/2)
(Lemma A.1h)

≤

π − α + 4 sin (α/2) .

_
(I = E, B = null, C = T & α > 2π/3): Let R1 be at point D, i.e. DA’ = x, see also Figure 3ii. Then R1
moves along the chord CD, it locates the treasure and returns it to the exit I, with total cost

_

DA’ + DC + CI ≤x + 2 sin (π − α − x/2) + 2 sin (α/2)
(x≤π−α)

≤

π − α + 4 sin (α/2) .

(I = T, B = null, C = E & α ≤ 2π/3): When R2 finds the treasure, it picks it up, and start moving along
chord IB, see also Figure 3iii. Meanwhile, R1 at time x is at some point, say, D, and crosscuts
8

𝛼𝛼

𝐼𝐼 = 𝐸𝐸
𝐵𝐵 = 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛
𝐶𝐶 = 𝑇𝑇

𝛼𝛼 ≤ 2𝜋𝜋/3

𝐷𝐷

𝐶𝐶

𝐴𝐴

𝛼𝛼

𝐼𝐼 = 𝑇𝑇
𝐵𝐵 = 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛
𝐶𝐶 = 𝐸𝐸

𝐶𝐶

𝐴𝐴

𝐵𝐵

𝐼𝐼

𝑂𝑂

𝐶𝐶

𝐷𝐷

𝐴𝐴′

(Subfigure 𝑖𝑖𝑖𝑖)

𝛼𝛼

𝐵𝐵

𝐴𝐴

𝛼𝛼

𝐾𝐾

𝐼𝐼

𝑂𝑂

(Subfigure 𝑖𝑖)

𝐷𝐷

𝐴𝐴

𝛼𝛼

𝐼𝐼

𝑂𝑂

𝛼𝛼

𝛼𝛼 > 2𝜋𝜋/3

𝛼𝛼

𝐼𝐼

𝑂𝑂

𝐵𝐵

𝐶𝐶

(Subfigure 𝑖𝑖𝑖𝑖𝑖𝑖)

𝐷𝐷

𝐴𝐴′

(Subfigure 𝑖𝑖𝑖𝑖)

𝐾𝐾

𝛼𝛼

𝐵𝐵
_

Figure 3: The performance of the wireless algorithm, when the starting point A lies in the arc CI of the two
interesting points. The trajectory of R2 is depicted with the dotted purple curve, while the trajectory of R1
with the solid red curve.
through CD to check the possible point C. When R1 visits C, R2 learns where the exit is, so starting
from point, say, K, it moves along the line segment KC and evacuates. Note that K lies always in
the the line segment IB, since CD ≤ CI = IB). The total cost then is
_

_

AI + IK + KC = AI + CD + KC
_

≤ AI + CD + max{CI, CB}
= x + 2 sin (α/2 − x) + max{2 sin (α/2) , 2 sin (α)}
(Lemma A.1j)

≤

x + 2 sin (α/2 − x) + 2 sin (α)

(Lemma A.1h)

≤

π − α + 4 sin (α/2) .

(I = T, B = null, C = E & α > 2π/3): When R2 finds the treasure, it picks it up, and start moving along
chord IB, see also Figure 3iv. Meanwhile, R1 at time x is at some point, say, D, and crosscuts
through CD to check the possible point C. When R1 visits C, R2 learns where the exit is, so starting
from point, say K, it moves along the line segment KC and evacuates. Note that K lies always in the
9

the line segment IB, since
CD =2 sin (π/2 − α/2 − x)
(Lemma A.1g)

≤

_

2 sin (α/2) = IB.

But then, the cost becomes
_

_

AI + IK + KC = AI + CD + KC
_

≤ AI + CD + max{CI, CB}
= x + 2 sin (π/2 − α/2 − x) + max{2 sin (α/2) , 2 sin (α)}
(Lemma A.1j)

≤

x + 2 sin (π/2 − α/2 − x) + 2 sin (α/2)

(Lemma A.1i)

≤

π − α + 4 sin (α/2) .

Lemma 2.3. Let A be the starting point of R2 which is the first to discover an interesting point I. Let also
_
_
the other interesting point be at B, where IB = α. If A lies outside the arc IB, then the performance of
Algorithm 1 is 1 + π − α + 4 sin (α/2), for all α ∈ [0, π].
Proof. For the case analysis below, we rely on Figure 4. As before, robots spend time 1 to reach the
periphery of the disk. Below we calculate the remaining time until evacuation. At time x the cases we

𝛼𝛼

𝐶𝐶 = 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛

𝐶𝐶

𝛼𝛼 ≤ 2𝜋𝜋/3

𝐷𝐷

𝐴𝐴

𝑂𝑂

𝐼𝐼

𝛼𝛼 > 2𝜋𝜋/3

𝛼𝛼

𝐵𝐵

(Subfigure 𝑖𝑖)

𝐼𝐼

𝐴𝐴

𝛼𝛼

𝑂𝑂
𝐶𝐶

𝐷𝐷

𝐴𝐴′

(Subfigure 𝑖𝑖𝑖𝑖)

𝛼𝛼

𝐵𝐵
_

Figure 4: The performance of the wireless algorithm, when the starting point A lies outside the arc IB of the
two interesting points. The trajectory of R2 is depicted with the dotted purple curve, while the trajectory of
R1 with the solid red curve.
consider are as follows.

10

(C = null & α ≤ 2π/3): After R2 discovers I it will move along chord IB to discover the other interesting
point, see also Figure 4i. In particular, since I is visited before C we have that x ≤ α/2. If the treasure
is in B, then the total cost would be
_

AI + 2IB =x + 2 sin (α/2)
≤α/2 + 4 sin (α/2)
≤π − α + 4 sin (α/2)
(since α ≤ 2π/3), while if the treasure is in I, then the cost would be by 2 sin (α/2) less.
(C = null & α > 2π/3): After R2 discovers I it will move along chord IB to discover the other interesting
point, see also Figure 4ii. In particular, since I is visited before C we have that x ≤ π − α. If the
treasure is in B, then the two robots are competing as to which will reach the treasure first. Even if
_
R2 reaches the treasure first, the cost would be AI + 2IB = x + 2 sin (α/2) ≤ π − α + 4 sin (α/2) ,
while if R1 reaches the treasure first, the total time will be even less. Finally, if the treasure is I, then
the cost would be by 2 sin (α/2) less.

It is clear now that Lemmata 2.2, 2.3 imply that for all α ∈ [0, π], the overall performance of Algorithm
1 is no more than 1 + π − α + 4 sin (α/2) concluding Theorem 2.1.

3

F2F MODEL

The main contribution of our work pertains to the face-to-face model and is summarized in the following
theorem.
Theorem 3.1. For every α ∈ [0, π], problem 2-TEf 2f can be solved in time 1 + π − α/2 + 3 sin (α/2).
Next we give the high-level intuition of the proposed evacuation-protocol, i.e. Algorithm 2, that proves
the above theorem (more low level intuition, along with the formal description of the protocol appears in
Section 3.1).
Denote by β the upper bound promised by the theorem above. It should be intuitive that when the
distance of the interesting points α tends to 0, there is no significant disadvantage due to lack of communication. And although the wireless evacuation-time might not be achievable, a protocol similar to the wireless
case should be able to give efficient solutions. Indeed, our face-to-face protocol is a greedy algorithm when
α is not too big, i.e. the two robots try independently to explore, locate the interesting points and fetch
the treasure to the exit without coordination (which is hindered anyways due to lack of communication).
Following a worst case analysis, it is easy to see that as long as α does not exceed a special threshold, call it
α0 , the evacuation time is β, and the analysis is tight.
When α exceeds the special threshold α0 , the lack of communication has a more significant impact on
the evacuation time. To work around it, robots need to exchange information which is possible only if they
meet. For this reason (and under some technical conditions), robots agree in advance to meet back in the
center of the disk to exchange information about their findings, and then proceed with fetching the treasure
to the exit. Practically, if the rendezvous is never realized, e.g. only one robot reaches the center up to
some time threshold, that should deduce that interesting points are not located in certain parts of the disk,

11

potentially revealing their actual location. In fact, this recipe works well, and achieves evacuation time β, as
long as α does not exceed a second threshold, which happens to be 2π/3.
The hardest case is when the two interesting points are further than 2π/3 apart. Intuitively, in such a
case there is always uncertainty as to where the interesting points are located, even when one of them is
discovered. At the same time, the interesting points, hence the robots, might be already far apart when some
or both interesting points are discovered. As such, meeting at the center of the disk to exchange information
would be time consuming and induces evacuation time exceeding β. Our technical contribution pertains
exactly to this case. Under some technical conditions, the treasure-finder might need to decide which of
the two possible exit-locations to consider next. In this case, the treasure-holder follows a trajectory not
towards one of the possible locations of the exit, rather a trajectory closer to that of its peer robot aiming
for a rendezvous. The two trajectories are designed carefully so that the location of the exit is revealed no
matter whether the rendezvous is realized or not.

3.1

Algorithm & Correctness

In our main Algorithm 2, robots R1 , R2 that start from the centre of the circle, move together to an arbitrary
point A on the circle (which takes time 1). Then they start moving in opposing directions, say, counterclockwise and clockwise respectively till the locate some interesting point.
In what follows we describe only the trajectory of R2 which is meant to be moving clock-wise (R1
performs the completely symmetric trajectory, and will start moving counter clock-wise). In particular all
point references in the description of our algorithm, and its analysis, will be from the perspective of R2 ’s
trajectory which is assumed to be the robot that first visits either the exit or the treasure at position I. By
_
_
_
B, C, D we denote the points on the circle with DC = CI = IB = α (see Figure 5). As before, and in what
follows, I ∈ {E, T } represents the position on the circle that is first discovered in the time horizon by any
robot (in particular by R2 ), and that holds either the treasure or the exit. Finally, O represents the centre of
the circle, which is also the starting point of the robots.
𝛼𝛼

𝛼𝛼

A

I

C

A

C
O
𝛼𝛼

𝛼𝛼

D

I

O

𝛼𝛼

B

B

D

𝛼𝛼

Figure 5: The points of interest from the perspective of R2 , when α ≤ 2π/3 on the left, and when α ≥ 2π/3
on the right.
According to our algorithm, R2 starts moving from point A till it reaches an interesting point I at time
12

_

x := AI. At this moment, our algorithm will decide to run one of the following subroutines with input
x. These subroutines describe evacuation protocols, in which the treasure must be brought to the exit.
Occasionally, the subroutines claim that robots evacuate (with the treasure) from points that is not clear that
hold an exit. As we will prove correctness later, we comment on these cases by writing that “correctness is
pending”.
A1 (x) (Figure 6 i): If I = T , pick up the treasure and move to B along the chord IB. If B = E evacuate,
else go to C along the chord BC and evacuate.
(Figure 6 ii): If I = E move to B along the chord IB. If B = T , pick up the treasure, and return to
I along the chord BI and evacuate. If B = null, then go to C along the chord BC. If the treasure is
found at C, pick it up, and move to I along the chord CI and evacuate (else abandon the process).
A2 (x) (Figure 6 iii): At the moment robots leave point A, set the timer to 0.
If I = T , pick up the treasure and go to the centre O of the circle. Wait there till the time t0 :=
max{x, α−x+2 sin (α/2)}+1. If R1 arrives at O by time t0 , then go to C and evacuate (correctness
is pending). Else (if R1 does not arrive at O by time t0 ) go to B and evacuate (correctness is pending).
(Figure 6 iv): If I = E, move to B along the chord IB. If B = T , pick up the treasure, and return to
I along the chord BI and evacuate. If B = null, then go to the centre O and halt.
A3 (x) (Figure 6 v): If I = T pick up the treasure. If R1 is already at point I go to C and evacuate
(correctness pending). If R1 is not at point I, then move along chord ID for additional time y :=
α/2 − x + sin (α/2) + sin (α), and let K be such that IK = y. If R1 is at point K, then go to B
and evacuate (correctness is pending), else (if R1 is not at point K) go to C and evacuate (correctness
pending).
(Figure 6 vi): If I = E, move to B along the chord IB. If B = T , pick up the treasure, and return to
I along the chord BI and evacuate. If B = null, then move along chord BC until you hit C (or you
meet the other robot- whatever happens first) and halt at the current point, call it K.
It is worthwhile discussing the intuition behind the subroutines above. First note that if a robot ever
finds a treasure, it picks it up. The second important property is that each robot simulates A1 either till it
finds the treasure or till it fails to find the treasure after finding the exit. At a high level, A1 greedily tries
to evacuate the treasure. This means that if the treasure is found first, then the robot tries successively the
possible locations of the exit (using the shortest possible paths) and evacuates. If instead the exit is found,
then it successively tries the (at most) two possibilities of the treasure location, and if the treasure is found,
it returns it to the exit.
A2 and A3 constitute our main technical contribution. Both algorithms are designed so that in some
special cases, in which the exact locations of the interesting points are not known, the two robots schedule
some meeting points so that if the meeting (rendezvous) is realized or even if it is not, the treasure-holder
can deduce the actual location of the exit. In other words, we make possible for the two robots to exchange
information without meeting. Indeed after finding the treasure, in A2 , R2 goes to the centre of the ring and
waits some finite time till it makes some decision of where to move the treasure, while in A3 , R2 moves
along a carefully chosen (and non-intuitive) chord, and again for some finite time, till it makes a decision to
move to a point on the ring. If instead the exit is found early, then the trajectories in A2 , A3 are designed to
support the other robot which might have found the treasure in case the latter does not follow A1 .
The next non-trivial and technical step would be to decide when to trigger the subroutines above. Of
course, once this is determined, i.e. once the trajectories are fixed, correctness and performance analysis is
a matter of exhaustive analysis.
13

𝐼𝐼 = 𝑇𝑇

B = 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛
𝐶𝐶 = 𝐸𝐸

𝐶𝐶

𝐵𝐵 = 𝐸𝐸
𝐶𝐶 = 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛

𝐼𝐼 = 𝐸𝐸

B = 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛
𝐶𝐶 = 𝑇𝑇

𝐵𝐵 = 𝑇𝑇
𝐶𝐶 = 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛

𝐴𝐴1
𝑂𝑂

𝐴𝐴

(Subfigure 𝑖𝑖)
𝐶𝐶

𝑂𝑂

𝐶𝐶

𝐼𝐼

𝐷𝐷

𝐵𝐵

𝐴𝐴

𝐼𝐼

𝐶𝐶

𝐵𝐵

𝐴𝐴

𝐴𝐴2

𝐼𝐼

𝑂𝑂

𝐴𝐴

𝑂𝑂

𝐼𝐼
𝐵𝐵

𝐴𝐴
𝐵𝐵

𝐵𝐵
(Subfigure 𝑖𝑖𝑖𝑖𝑖𝑖)

(Subfigure 𝑖𝑖𝑣𝑣)

(Subfigure 𝑖𝑖𝑖𝑖)

𝐶𝐶

𝐷𝐷

(Subfigure 𝑣𝑣)

𝐾𝐾

𝐴𝐴

𝐶𝐶

𝐾𝐾

𝐴𝐴3

𝐵𝐵

𝐼𝐼
𝐷𝐷

(Subfigure 𝑣𝑣𝑣𝑣)

Figure 6: The non-wireless algorithm for two robots with performance π − α/2 + 3 sin (α/2).
We are ready to define our main non-wireless algorithm. We remind the reader that the description is for
R2 that starts moving clockwise. R1 performs the symmetric trajectory by moving counter-clockwise.
Our main algorithm uses parameter x(α) := 3α/2 − π − sin (α/2) + 2 sin (α) , which we abbreviate
by x whenever α is clear from the context. By Lemma A.1a, α0 ≈ 1.22353 is the unique root of x(α) = 0,
while x is positive for all α ∈ (α0 , π) and negative for all α ∈ [0, α0 ).
Lemma 3.2. For every α ∈ [0, π], Algorithm 2 is correct, i.e. a robot brings the treasure to the exit.
Proof. First, it is easy to see that the treasure is always picked up. Indeed, if the first interesting point I that
is discovered (by any robot) is the treasure, then the claim is trivially true. If the first interesting point I
found, say, by R2 is an exit, then R2 (in all subroutines) first tries the possible location B for the treasure,
and if it fails it tries location C (in other words it always simulates A1 till it fails to find the treasure after
finding the exit). Meanwhile R1 moves counter-clockwise on the ring, and sooner or later will reach C or
B. So at least one of the robots will reach the treasure first. In what follows, let R2 be the one who found
first the treasure (and picks it up). We examine three cases.
If R2 is following subroutine A1 , then the treasure is brought to the exit. Indeed, in that case R2 expects
no interaction from R1 and greedily tries to evacuate (see subcases i,ii in Figure 6).

14

𝐼𝐼

Algorithm 2 Non-Wireless Algorithm
_

Step 1. Starting from A, move clockwise until an interesting point I is found at time x := AI.
Step 2. Proceed according to the following cases:
•
•
•
•
•

If α > 2π/3 and I = T and α > x ≥ α − x, then run A3 (x).
If α > 2π/3 and I = E and x ≤ x, then run A3 (x).
If α0 ≤ α ≤ 2π/3 and I = T and α > x ≥ α − x, then run A2 (x).
If α0 ≤ α ≤ 2π/3 and I = E and x ≤ x, then run A2 (x).
In all other cases, run A1 (x).

If R2 is following subroutine A2 , then it must be that α0 ≤ α ≤ 2π/3, that α − x ≤ x < α, and that
it has not found any other interesting point before (by Lemma A.1a we have α − x < α and x > 0 for all
α > α0 ). Figure 6 subcase iii depicts exactly this scenario, where I = T . Note that from R2 ’s perspective,
the exit can be either in B or in C, and R2 chooses to go to the center. This takes total time x + 1. If the
exit was at point C, then R1 would have found it in time α − x ≤ x and that would make it to follow A2 .
So, R1 would first check point D (where the treasure is not present), and that would make it to go to the
centre arriving at time α − x + 2 sin (α/2) + 1 (an illustration of this trajectory is shown in Figure 6 subcase
iv, if R1 was moving clockwise). R2 is guaranteed to wait at the center till time t0 (which is the maximum
required time that takes each robot to reach the centre). In that case, R2 meets R1 at the center (because R1
did find the exit in C), and R2 correctly chooses C as the evacuation point. Finally, if instead the exit was
not in C, then R1 would not make it to the centre by time t0 . That can happen only if the exit is at point B,
and once again R2 makes the right decision to evacuate from B.
In the last case, R2 is following subroutine A3 , and so it must be that α > 2π/3, that α − x ≤ x < α,
and that it has not found any other interesting point before. Figure 6 subcase v depicts this scenario. Note
that the exit could be either in C or in D.
If the exit is in C, then α − x ≤ x, and R1 would follow A3 too. This means, R1 would go to point
D (where there is no treasure), and that would make it travel along the chord DI (an illustration of this
trajectory is shown in Figure 6 subcase vi, if R1 was moving clockwise). If R1 reaches I, it waits there,
and when R2 arrives in I, R2 makes the right decision to evacuate from C. Otherwise R1 does not reach
I, and it moves up to a certain point in the chord ID similarly to R2 . Note that the meeting condition on a
_
_
point K on the chord, with y = IK, would be that AI + IK = CA + CD + (DI − IK), which translates
into y = x + sin (α/2) + sin (α) − α/2, i.e. the exact segment of ID that R2 traverses before it changes
trajectory. The longest R2 could have traveled on the chord ID would be when x = α − x, but then IK
would be equal to α − π + 3 sin (α) ≤ 2 sin (α) = ID for all α > 2π/3. Therefore, the two robots meet
indeed in somewhere in the chord ID. Note also that in this case, R2 makes the right decision and goes to
point C in order to evacuate.
If instead the exit is in B, then again R2 travels till point K (which is in the interior of the chord ID).
But in this case, R1 will not meet R2 in point K as it will not follow A3 . Once again, R2 makes the right
decision, and after arriving at K it moves to point B and evacuates.

3.2

Algorithm Analysis

In this section we prove that for all α ∈ [0, π], the evacuation time of Algorithm 2 is no more than 1 +
π − α/2 + 3 sin (α/2), concluding Theorem 3.1. In the analysis below we provide, whenever possible,

15

supporting illustrations, which for convenience may depict special configurations. In the mathematical
analysis we are careful not to make any assumptions for the configurations we are to analyze.
It is immediate that when a robot finds the first interesting point at time x ≥ α after moving on the
perimeter of the disk, then that robot can also deduce where the other interesting point is located. In that
sense, it is not surprising that, in this case, the trajectory of the robots and the associated cost analysis are
simpler.
Lemma 3.3. Let x be the time some robot is the first to reach an interesting point I ∈ {E, T } from the
moment robots start moving in opposing directions. If x ≥ α, then the performance of the algorithm is at
most 1 + π − α/2 + 3 sin (α/2). Also, x ≥ α is impossible, if α > 2π/3.
Proof. Note that 1 is the time it takes both robots to reach a point, say A, on the ring. So we will tailor our
analysis to the evacuation time from the moment robots start moving (in opposing directions) from point A.
Let x be the time after which R2 (without loss of generality) is the first to find an interesting point
I ∈ {E, T }. Let also B be the other interesting point {E, T } \ I. For R2 to reach first I, it must be the case
that R1 does not have enough time to reach B, and hence x ≤ 2π − α − x, that is x ≤ π − α/2. Since also
x ≥ α, we conclude that α ≤ 2π/3.
Next we examine the following cases. For our analysis, the reader can use Figure 5 as reference (al_
though A is depicted in the interior of the arc CI, we will not use that AI ≤ α).
Case 1 (I = T ): R2 picks up the treasure and moves along the chord IB = 2 sin (α/2). The worst case
treasure-evacuation time then is
max

α≤x≤π−α/2

{x + 2 sin (α/2)} = π − α/2 + 2 sin (α/2) .

Case 2 (I = E): According to the algorithm, R2 moves towards the treasure point B along the chord IB,
and reaches it in time x + 2 sin (α/2). R1 moves counter-clock wise and will reach the position of
the treasure in time 2π − α − x. Whoever finds the treasure first will evacuate from the exit, paying
additional time 2 sin (α/2). Hence, the total cost can never exceed
min {x + 2 sin (α/2) , 2π − α − x} + 2 sin (α/2)
≤π − α/2 + 3 sin (α/2)

(by Lemma A.1b)

It is easy to see that in both cases, the cost of the algorithm is as promised.
By Lemma 3.3 we can focus on the (much more interesting) case that R2 , which is the first robot that
_
finds an interesting point, arrives at I at time x := AI < α. A reference for the analysis below is Figure 6
which is accurately depicting point A at most α arc-distance away from I. For the sake of better exposition,
we examine next the cases α ≤ 2π/3 and α ≥ 2π/3 separately. Note that in the former case robots may
run subroutines A1 or A2 , while in the latter case robots may run subroutines A1 or A3 . For both lemmata
below, the reader may consult Figures 5 and 6.
Lemma 3.4. Let x be the time some robot is the first to reach an interesting point I ∈ {E, T } from the
moment robots start moving in opposing directions. If x < α, then the performance of the algorithm is at
most 1 + π − α/2 + 3 sin (α/2), for all α ∈ [0, π].
Proof. As before, we omit in the analysis below the time cost 1, i.e. the time robots need to reach the
periphery of the disk. We examine the following cases for R2 , which is the robot that finds I.
16

(I = T, B = E, C = null): If R2 runs A1 , then it must be that x ≤ α − x, so the cost is x + 2 sin (α/2) ≤
α − x + 2 sin (α/2) ≤ π − α/2 + 3 sin (α/2) (see Figure 6 i).
If R2 runs A2 , then it must be that α − x ≤ x < α and α ≤ 2π/3, and the robot goes to the centre in
order to learn where the exit is (see Figure 6 iii). Independently of where the exit is, and by Lemma 3.2,
R2 makes the right decision and evacuates in time 1 + maxα−x≤x<α {x, α − x + 2 sin (α/2)} + 1 ≤
max{α, x + 2 sin (α/2)} + 2 which, by Lemma A.1c, is at most π − α/2 + 3 sin (α/2) for all
α ≤ 2π/3. Note that the analysis of this case is valid, even if I = T is not the first interesting point
that is discovered, and it is from the perspective of the robot that finds the treasure.
If R2 runs A3 , then it must be that α − x ≤ x < α and α > 2π/3. Then the trajectory of R2 is as in
Figure 6 v, and the exit is found correctly due to Lemma 3.2. For the sake of the exposition, we will
do the worst case analysis for both cases B = E and C = E now (i.e. we only insist in that I = T
and that R2 runs A3 ).
_

The total time for the combined cases is AI + IK + max{KB, KC}, where IK = y (see definition
_
of A3 ). Since as we have proved, K lies always in chord ID, and since DB = 3α − 2π we have that
BK ≤ max{BI, BD}
≤ max{2 sin (α/2) , 2 sin (3α/2 − π)}
≤2 sin (α/2)
We also have that KC ≤ CI = 2 sin (α/2). So the cost becomes no more than
x + y + 2 sin (α/2) =α/2 + 3 sin (α/2) + sin (α)
≤π − α/2 + 3 sin (α/2)

(by Lemma A.1d)

for all α ∈ [0, π].
(I = T, B = null, C = E): Since I is found first, we must have x ≤ α/2, hence both robots run A1 , see
Figure 6 i. Robot R2 that finds the treasure will evacuate in time no more than x + 2 sin (α/2) +
2 sin (α) ≤ α/2 + 2 sin (α/2) + 2 sin (α) < π − α/2 + 3 sin (α/2) for all α ∈ [0, π].
(I = E, B = T, C = null): If R2 is the first to find the treasure, then this case is depicted in Figure 6
i. This happens exactly when x + 2 sin (α/2) ≤ 2π − x − α, so that the total evacuation time is
x + 4 sin (α/2) ≤ π − α/2 + 3 sin (α/2) for all α ∈ [0, π].
Otherwise x > π − α/2 − sin (α/2), and R1 is the robot that reaches the treasure first. If R1
decides to run A1 , then the cost would be 2π − x − α + 2 sin (α/2) < π − α/2 + 3 sin (α/2) for all
α ∈ [0, π]. Finally, if R1 decides to run A2 or A3 , then we have already made the analysis in case
I = T, B = E, C = null above.
(I = E, B = null, C = T ): Note that in all cases, both robots will run the same subroutine. In particular, if
robots run either A2 or A3 , then we have already done the analysis in case I = T, B = E, C = null
above.
Finally, if both robots run A1 , it must be either because α ≤ α0 , or because x ≥ x, while the cost is
always α − x + 2 sin (α/2) + 2 sin (α) (the case is depicted in Figure 6 ii, with reverse direction). If
α ≤ α0 , then the evacuation cost would be at most α + 2 sin (α/2) + 2 sin (α) which by Lemma A.1h
is at most π − α/2 + 3 sin (α/2), for all α ∈ [0, α0 ]. If x ≥ x, then the cost would be at most
α − x + 2 sin (α/2) + 2 sin (α) = π − α/2 + 3 sin (α/2) .
17

Note that Lemmata 3.3, 3.4 imply that the performance of Algorithm 2 is, in the worst case, no more
than 1 + π − α/2 + 3 sin (α/2), concluding also Theorem 3.1.

3.3

Extension to n Robots

We can easily extend our 2-robot algorithms to the n-robot case (when n is even, otherwise we ignore one
robot) by splitting the robots into pairs, defining points in intervals of length 4π/n on the cycle, assigning
each pair of robots to each such point, and letting them run the corresponding 2-robot algorithm.

4

LOWER BOUNDS

We conclude the study of treasure evacuation with 2 robots by providing the following lower bound pertaining to distributed systems under the face-to-face communication model. For the proof, we invoke an
adversary (not necessarily the most potent one), who waits for as long as there are three points A, B, C with
AB = BC = α on the periphery such that at most one of them has been visited by a robot. Then depending
on the moves of the robots decides where to place the interesting points.
Theorem 4.1. For problem 2-TEf 2f , any algorithm needs at least time 1 + π/3 + 4 sin (α/2) if 0 ≤ α ≤
2π/3, or 1 + π/3 + 2 sin (α) + 2 sin (α/2) if 2π/3 ≤ α ≤ π.
Proof. Since the robots start from the center, they’ll need time 1 to reach the periphery. The adversary (not
necessarily the most potent one, but with this weaker adversary we still get a (weaker) lower bound) will
wait for as long as there are three points A, B, C with AB = BC = α on the periphery such that at most
one of them has been visited by a robot. It is easy to see that this will be true for as long as less than 2π/3
of the periphery has been explored; this will be done by the 2 robots after time at least (2π/3)/2 = π/3.
Hence, after time at least 1 + π/3 there are such points A, B, C with only one of these points visited by
a robot. For convenience, we assume that robot 1 is the first to visit a point at time t and robot 2 visits a
different point next at time t + ε (if this doesn’t happen, then the optimal algorithm would be behaving like
the case of only one robot, which is clearly suboptimal for the adversary moves below). It will be apparent
below that the lower bound becomes weaker for ε = 0, so that’s what we will assume from now on. We
distinguish the following cases:
Case 1 (Robot 1 at A, Robot 2 at C): If the adversary places T → B, E → A or C, then recovery needs at
least time 4 sin (α/2) (if robot 1 or 2 respectively evacuates T by itself). If it places T → A, E → C, then
recovery needs at least time 2 sin (α) (a robot evacuates T by traversing AC). Any other placement of T, E
by the adversary gives either the same or a worse (lower) bound, and, therefore, it’s discarded. It is clear
that, in this case, the adversary goes with the first option, for a lower bound of 4 sin (α/2).
Case 2 (Robot 1 at A, Robot 2 at B): If the adversary places T → C, E → A, then recovery needs at least
time min{2 sin (α/2) + 2 sin (α) , 4 sin (α)} (if robot 2 or 1 respectively evacuates T by itself). If it places
T → C, E → B, then recovery needs at least time min{4 sin (α/2) , 2 sin (α) + 2 sin (α/2)} (if robot 2 or
1 respectively evacuates T by itself). Any other placement of T, E by the adversary gives either the same
or a worse (lower) bound, and, therefore, it’s discarded. It is clear that, in this case, the adversary goes with
the option that maximizes the lower bound, for a lower bound of
(

max

min{2 sin (α/2) + 2 sin (α) , 4 sin (α)},
min{4 sin (α/2) , 2 sin (α) + 2 sin (α/2)}
18

)

.

By taking the minimum of Cases 1,2 above, the lower bound of the theorem follows.

5

CONCLUSION

In this paper we introduced a new problem on searching and fetching which we called treasure-evacuation
from a unit disk. We studied two online variants of treasure-evacuation with two robots, based on different
communication models. The main point of our approach was to propose distributed algorithms by a collaborative team of robots. Our main results demonstrate how robot communication capabilities affect the
treasure evacuation time by contrasting face-to-face (information can be shared only if robots meet) and
wireless (information is shared at any time) communication.
There are several open problems in addition to sharpening our bounds. These include problems on 1) the
number of robots, 2) other geometric domains (discrete or continuous), 3) differing robot starting positions,
4) multiple treasures and exits, 5) limited range wireless communication, 6) robots with different speeds, 6)
different a priori knowledge of the topology or partial information about the targets, etc. In particular, we
anticipate that nearly optimal algorithms for small number of robots, e.g. for n = 3, 4, or any other variation
of problem we consider will require new and significantly different algorithmic ideas than those we propose
here, still in the same spirit.

References
[1] R. Ahlswede and I. Wegener. Search problems. Wiley-Interscience, 1987.
[2] S. Albers and M. R. Henzinger. Exploring unknown environments. SIAM Journal on Computing,
29(4):1164–1188, 2000.
[3] S. Albers, K. Kursawe, and S. Schuierer. Exploring unknown environments with obstacles. Algorithmica, 32(1):123–143, 2002.
[4] S. Alpern and S. Gal. The theory of search games and rendezvous. Springer, 2003.
[5] Steve Alpern. Find-and-fetch search on a tree. Operations Research, 59(5):1258–1268, 2011.
[6] R. Baeza Yates, J. Culberson, and G. Rawlins. Searching in the plane. Information and Computation,
106(2):234–252, 1993.
[7] R. Baeza-Yates and R. Schott. Parallel searching in the plane. Computational Geometry, 5(3):143–154,
1995.
[8] A. Beck. On the linear search problem. Israel Journal of Mathematics, 2(4):221–228, 1964.
[9] R. Bellman. An optimal search. SIAM Review, 5(3):274–274, 1963.
[10] P. Berman. On-line searching and navigation. In A. Fiat and G. J. Woeginger, editors, Online Algorithms: The State of the Art, pages 232–241. Springer, 1998.
[11] A. Bonato and R. Nowakowski. The game of cops and robbers on graphs. AMS, 2011.
[12] W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider. Coordinated multi-robot exploration.
Robotics, IEEE Transactions on, 21(3):376–386, 2005.
19

[13] M. Chrobak, L. Gasieniec, Gorry T., and R. Martin. Group search on the line. In SOFSEM 2015.
Springer, 2015.
[14] T. H. Chung, G. A. Hollinger, and V. Isler. Search and pursuit-evasion in mobile robotics. Autonomous
robots, 31(4):299–316, 2011.
[15] J. Czyzowicz, L. Gasieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pajak. Evacuating robots from
an unknown exit located on the perimeter of a disc. In DISC 2014, pages 122–136. Springer, Austin,
Texas, 2014.
[16] J. Czyzowicz, K. Georgiou, S. Dobrev, E. Kranakis, and F. MacQuarrie. Evacuating two robots from
multiple unknown exits in a circle. In ICDCN 2016, 2016.
[17] J. Czyzowicz, K. Georgiou, E. Kranakis, L. Narayanan, J. Opatrny, and B. Vogtenhuber. Evacuating
robots from a disc using face to face communication. In CIAC 2015, pages 140–152. Springer, Paris,
France, 2015.
[18] J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. Shende. Wireless autonomous
robot evacuation from equilateral triangles and squares. In ADHOC-NOW 2015, Athens, Greece, June
29 - July 1, 2015, Proceedings, pages 181–194, 2015.
[19] E. D. Demaine, S. P. Fekete, and S. Gal. Online searching with turn cost. Theoretical Computer
Science, 361(2):342–355, 2006.
[20] X. Deng, T. Kameda, and C. Papadimitriou. How to learn an unknown environment. In FOCS, pages
298–303. IEEE, 1991.
[21] S. Fekete, C. Gray, and A. Kröller. Evacuation of rectilinear polygons. In Combinatorial Optimization
and Applications, pages 21–30. Springer, 2010.
[22] K. Georgiou, G. Karakostas, and E. Kranakis. Search-and-fetch with one robot on a disk. In 12th
International Symposium on Algorithms and Experiments for Wireless Sensor Networks, 2016.
[23] B. Gluss. An alternative solution to the lost at sea problem. Naval Research Logistics Quarterly,
8(1):117–122, 1961.
[24] Christoph Hipke, Christian Icking, Rolf Klein, and Elmar Langetepe. How to find a point on a line
within a fixed distance. Discrete Appl. Math., 93(1):67–73, 1999.
[25] F. Hoffmann, C. Icking, R. Klein, and K. Kriegel. The polygon exploration problem. SIAM Journal
on Computing, 31(2):577–600, 2001.
[26] J. R. Isbell. Pursuit around a hole. Naval Research Logistics Quarterly, 14(4):569–571, 1967.
[27] J. S. Jennings, G. Whelan, and W. F. Evans. Cooperative search and rescue with a team of mobile
robots. In ICAR, pages 193–200. IEEE, 1997.
[28] M.-Y. Kao, Y. Ma, M. Sipser, and Y. Yin. Optimal constructions of hybrid algorithms. J. Algorithms,
29(1):142–164, 1998.
[29] M.-Y. Kao, J. H. Reif, and S. R. Tate. Searching in an unknown environment: An optimal randomized
algorithm for the cow-path problem. Information and Computation, 131(1):63–79, 1996.
20

[30] J. Kleinberg. On-line search in a simple polygon. In SODA, page 8. SIAM, 1994.
[31] E. Koutsoupias, C. Papadimitriou, and M. Yannakakis. Searching a fixed graph. In ICALP 96, pages
280–289. Springer, 1996.
[32] P. Nahin. Chases and Escapes: The Mathematics of Pursuit and Evasion. Princeton University Press,
2012.
[33] C. H Papadimitriou and M. Yannakakis. Shortest paths without a map. In ICALP, pages 610–620.
Springer, 1989.
[34] L. Stone. Theory of optimal search. Academic Press New York, 1975.
[35] S. Thrun. A probabilistic on-line mapping algorithm for teams of mobile robots. The International
Journal of Robotics Research, 20(5):335–363, 2001.
[36] B. Yamauchi. Frontier-based exploration using multiple robots. In Proceedings of the second international conference on Autonomous agents, pages 47–53. ACM, 1998.

A

Trigonometric Inequalities

Lemma A.1. a) There exists some α0 ∈ (0, π) such that 3α/2 − π − sin (α/2) + 2 sin (α) is positive for
all α ∈ (α0 , π) and negative for all α ∈ [0, α0 ). In particular, α0 ≈ 1.22353.
b) min {x + 2 sin (α/2) , 2π − α − x} + 2 sin (α/2) ≤ π − α/2 + 3 sin (α/2) , ∀α ∈ [0, π].
c) max{α, x + 2 sin (α/2)} + 2 ≤ π − α/2 + 3 sin (α/2) for all α ∈ [0, 2π/3].
d) α + sin (α) ≤ π for all α ∈ [0, π].
e) α − sin (α/2) + 2 sin (α) ≤ π for all α ∈ [0, π].
f) α/2 + 2 sin (α) ≤ π − α + 2 sin (α/2) , ∀α ∈ [0, 2π/3]. .
g) max0≤x≤π−α {sin (π/2 − α/2 − x)} ≤ sin (α/2) , ∀α ∈ [2π/3, π]
h) max0≤x≤α/2 {x + 2 sin (α/2 − x)} + 2 sin (α) ≤ π − α + 4 sin (α/2) , ∀α ∈ [0, 2π/3].
i)
max {x + 2 sin (π/2 − α/2 − x)}

0≤x≤π−α

≤π − α + 2 sin (α/2) , ∀α ∈ [2π/3, π]
j) sin (α) ≤ sin (α/2) , ∀α ∈ [0, 2π/3], and
sin (α) ≥ sin (α/2) , ∀α ∈ [2π/3, π].
Proof of A.1a We observe that
∂
∂
x(α) =
(3α/2 − π − sin (α/2) + 2 sin (α))
∂α
∂α
=3/2 − cos (α) + cos (α/2) .
21

It is easy to see that the above quantity remains positive for α < 2π/3, while it is negative for
α > 2π/3. Since x(0) < 0 and x(2π/3) > 0, it follows that there is a unique root α0 ∈ (0, 2π/3)
(which numerically can be estimated to α0 ≈ 1.22353). Finally, we see that x(π) = π − 1 > 0, so
x(α) remains positive for α ∈ [2π/3, π].
Proof of A.1b We observe that min {x + 2 sin (α/2) , 2π − α − x} attains its maximum when x+2 sin (α/2) =
2π − α − x, in which case its value becomes π − α/2 + 3 sin (α/2).
∂
Proof of A.1c First we claim that 3α/2−2 sin (α/2) ≤ π−2 for α ≤ 2π/3. This is because ∂α
(3α/2 + 2 sin (α/2)) =
√
3/2 + cos (α/2) > 0, hence 3α/2 − 2 sin (α/2) ≤ π − 3/2 ≤ π − 2. This claim immediately shows
that α + 2 ≤ π − α/2 + 3 sin (α/2) for all α ∈ [0, 2π/3].

Now we show that x+2 sin (α/2)+2 ≤ π−α/2+3 sin (α/2) for all α ∈ [0, 2π/3]. For this it suffices
∂
to check that α+sin (α)−sin (α/2) ≤ π −1. To that end we see that ∂α
(α + sin (α) − sin (α/2)) =
1 + cos √
(α) − cos
(α/2)
/2
≥
0
for
all
α
≤
2π/3.
Hence
α
+
sin
(α)
− sin (α/2) ≤ 2π/3 ≤
√
2π/3 + 3/2 − 3/2 ≤ π − 1 as wanted.
Proof of A.1d We see that
π + sin (π) = π.

∂
∂α

(α + sin (α)) = 1 + cos (α) ≥ 0, for all α ∈ [0, π]. hence, α + sin (α) ≤

Proof of A.1e See Figure 7.
3.0
2.5
2.0
1.5
1.0
0.5

0.5

1.0

1.5

2.0

2.5

3.0

Figure 7: The function α − sin (α/2) + 2 sin (α) compared to π for all α ∈ [0, π].
Proof of A.1f We observe that
∂
(3α/2 + 2 sin (α) − 2 sin (α/2))
∂α
=3/2 + 2 cos (α) − cos (α/2) .
From the monotonicity of cosine in [0, 2π/3], we see that the above derivative preserves non negative
sign when α ∈ [0, 2π/3]. Hence, the maximum of
3α/2 + 2 sin (α) − 2 sin (α/2) ≤ π
is attained when α = 2π/3, and its value is π as wanted.
22

Proof of A.1g We have that
max {sin (π/2 − α/2 − x)}

0≤x≤π−α

=

max {cos (α/2 + x)}

0≤x≤π−α

≤ cos (α/2) ,
since cosine is monotonically decreasing in [0, π]. But also for all α ∈ [2π/3, π] we have that
cos (α/2) ≤ sin (α/2), concluding what we need.
Proof of A.1h We have that
max {x + 2 sin (α/2 − x) + 2 sin (α)}
0≤x≤α/2

≤α/2 + sin (α/2) + sin (α)
where the first inequality is true due to the monotonicity of x, sin (α/2 − x) w.r.t. x ≤ α/2 and
for all α ∈ [0, 2π/3], and the last inequality since again α ≤ 2π/3. The claim now follows from
Lemma A.1f.
Proof of A.1i Follows immediately since x ≤ π − α, and by Lemma A.1g.
Proof of A.1j It is easy to see that sin (α/2) − sin (α) is convex in α ∈ [0, 2π/3], so it attains its maximum
either at α = 0 or at α = 2π/3. In both cases, its value is 0. Also, sin (α/2)−sin (α) is monotonically
increasing for α > 2π/3, implying what was promised.

23

