References:

% Thesis
@article{BAEZAYATES1993234,
title = "Searching in the Plane",
journal = "Information and Computation",
volume = "106",
number = "2",
pages = "234 - 252",
year = "1993",
issn = "0890-5401",
doi = "https://doi.org/10.1006/inco.1993.1054",
url = "http://www.sciencedirect.com/science/article/pii/S0890540183710540",
author = "R.A. Baezayates and J.C. Culberson and G.J.E. Rawlins",
abstract = "In this paper we initiate a new area of study dealing with the best way to search a possibly unbounded region for an object. The model for our search algorithms is that we must pay costs proportional to the distance of the next probe position relative to our current position. This model is meant to give a realistic cost measure for a robot moving in the plane. We also examine the effect of decreasing the amount of a priori information given to search problems. Problems of this type are very simple analogues of non-trivial problems on searching an unbounded region, processing digitized images, and robot navigation. We show that for some simple search problems, knowing the general direction of the goal is much more informative than knowing the distance to the goal."
}


@article{BELLMAN1963,
author = {Beck, Anatole.},
title = {An Optimal Search (Richard Bellman)},
journal = {SIAM Review},
volume = {27},
number = {3},
pages = {447-448},
year = {1985},
doi = {10.1137/1027117},

URL = {
https://doi.org/10.1137/1027117

},
eprint = {
https://doi.org/10.1137/1027117}
}

@article{beck1964linear,
title={On the linear search problem},
author={Beck, A.},
journal={Israel J. of Mathematics},
volume={2},
number={4},
pages={221--228},
year={1964},
publisher={Springer}
}

@InProceedings{chuangpishit_et_al:LIPIcs:2018:8631,
author = {Huda Chuangpishit and Saeed Mehrabi and Lata Narayanan and Jaroslav Opatrny},
title = {{Evacuating an Equilateral Triangle in the Face-to-Face Model}},
booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
pages = {11:1--11:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-061-3},
ISSN = {1868-8969},
year = {2018},
volume = {95},
editor = {James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8631},
URN = {urn:nbn:de:0030-drops-86310},
doi = {10.4230/LIPIcs.OPODIS.2017.11},
annote = {Keywords: Distributed algorithms, Robots evacuation, Face-to-face communication, Equilateral triangle}
}

@InProceedings{wireless-triangle-2,
title="Wireless Autonomous Robot Evacuation from Equilateral Triangles and Squares, extended version, in preparation",
author="Czyzowicz, J.
and Kranakis, E.
and Krizanc, D.
and Narayanan, L.
and Opatrny, J.
and Shende, S.",
editor="Papavassiliou, Symeon
and Ruehrup, Stefan",
booktitle="Ad-hoc, Mobile, and Wireless Networks",
year="2015",
publisher="Springer International Publishing",
pages="181--194",
abstract="Consider an equilateral triangle or square with sides of length {\$}{\$}1{\$}{\$}. A number of robots starting at the same location on the perimeter or in the interior of the triangle or square are required to evacuate from an exit which is located at an unknown location on its perimeter. At any time the robots can move at identical speed equal to {\$}{\$}1{\$}{\$}, and they can cooperate by communicating with each other wirelessly. Thus, if a robot finds the exit it can broadcast ``exit found'' to the remaining robots which then move in a straight line segment towards the exit to evacuate. Our task is to design robot trajectories that minimize the evacuation time of the robots, i.e., the time the last robot evacuates from the exit. Designing such optimal algorithms turns out to be a very demanding problem and even the case of equilateral triangles turns out to be challenging.",
isbn="978-3-319-19662-6"
}

@inproceedings{10.1007/978-3-319-19662-6_13,
author = {J. Czyzowicz and
E. Kranakis and
D. Krizanc and
L. Narayanan and
J. Opatrny and
S. M. Shende},
title = {Wireless Autonomous Robot Evacuation from Equilateral Triangles and
Squares},
booktitle = {Proceedings of the 14th International Conference on Ad-hoc, Mobile, and Wireless Networks
(ADHOC-NOW 2015), Athens, Greece},
pages = {181--194},
year = {2015}
}


@InProceedings{disc_face2face,
author="Czyzowicz, J.
and Georgiou, K.
and Kranakis, E.
and Narayanan, L.
and Opatrny, J.
and Vogtenhuber, B.",
editor="Paschos, Vangelis Th.
and Widmayer, Peter",
title="Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)",
booktitle="Algorithms and Complexity",
year="2015",
publisher="Springer International Publishing",
pages="140--152",
abstract="Assume that two robots are located at the centre of a unit disk. Their goal is to evacuate from the disk through an exit at an unknown location on the boundary of the disk. At any time the robots can move anywhere they choose on the disk, independently of each other, with maximum speed {\$}{\$}1{\$}{\$}. The robots can cooperate by exchanging information whenever they meet. We study algorithms for the two robots to minimize the evacuation time: the time when both robots reach the exit. In [9] the authors gave an algorithm defining trajectories for the two robots yielding evacuation time at most {\$}{\$}5.740{\$}{\$}and also proved that any algorithm has evacuation time at least {\$}{\$}3+ {\backslash}frac{\{}{\backslash}pi {\}}{\{}4{\}} + {\backslash}sqrt{\{}2{\}} {\backslash}approx 5.199{\$}{\$}. We improve both the upper and lower bounds on the evacuation time of a unit disk. Namely, we present a new non-trivial algorithm whose evacuation time is at most {\$}{\$}5.628{\$}{\$}and show that any algorithm has evacuation time at least {\$}{\$}3+ {\backslash}frac{\{}{\backslash}pi {\}}{\{}6{\}} + {\backslash}sqrt{\{}3{\}} {\backslash}approx 5.255{\$}{\$}. To achieve the upper bound, we designed an algorithm which non-intuitively proposes a forced meeting between the two robots, even if the exit has not been found by either of them.",
isbn="978-3-319-18173-8"
}

@article{multi_exit_circle,
title = "Evacuating two robots from multiple unknown exits in a circle",
journal = "Theoretical Computer Science",
volume = "709",
pages = "20 - 30",
year = "2018",
note = "Special Issue of ICDCN 2016 (Distributed Computing Track)",
issn = "0304-3975",
doi = "https://doi.org/10.1016/j.tcs.2016.11.019",
url = "http://www.sciencedirect.com/science/article/pii/S0304397516306788",
author = "Jurek Czyzowicz and Stefan Dobrev and Konstantinos Georgiou and Evangelos Kranakis and Fraser MacQuarrie",
keywords = "Algorithm, Circle, Evacuation, Exit, Mobile robots, Searching",
abstract = "We study a robot evacuation problem in a circle. Assume that k exits are arranged on a unit circle. Two autonomous mobile robots are placed on the circle and in arbitrary positions. The robots can travel with maximum speed of 1 and can communicate wirelessly at any time and distance. They also have a map of the domain, including exits, but do not have knowledge of their own initial locations on the circle, rather they only know their relative distance. The goal of the evacuation problem is to give an algorithm for the two robots to reach an exit (not necessarily the same), which also minimizes the time until an exit is found, in the worst case. We consider two variants of the evacuation problem depending on whether or not the two robots have control over their initial distance. When the initial distance of the robots is part of the input (i.e. no control), we show that simple algorithms exist which achieve optimal worst case evacuation times for the cases where the robots begin colocated with an arbitrary arrangement of the exits; and when the exits are either colocated or evenly spaced, with arbitrary starting positions of the robots. We also give upper and lower bounds on the problem with arbitrary arrangement of exits and starting positions of the robots. For the problem where robots can choose their initial distance (with knowledge of, but not control over the distribution of exits), we propose a natural family of algorithms parameterized by the maximum distance between any two exits and analyse their cost."
}

@InProceedings{zurich,
author="Brandt, Sebastian
and Laufenberg, Felix
and Lv, Yuezhou
and Stolz, David
and Wattenhofer, Roger",
editor="Fotakis, Dimitris
and Pagourtzis, Aris
and Paschos, Vangelis Th.",
title="Collaboration Without Communication: Evacuating Two Robots from a Disk",
booktitle="Algorithms and Complexity",
year="2017",
publisher="Springer International Publishing",
pages="104--115",
abstract="We consider the problem of evacuating two robots from a bounded area, through an unknown exit located on the boundary. Initially, the robots are in the center of the area and throughout the evacuation process they can only communicate with each other when they are at the same point at the same time. Having a visibility range of 0, the robots can only identify the location of the exit if they are already at the exit position. The task is to minimize the time it takes until both robots reach the exit, for a worst-case placement of the exit. For unit disks, an upper bound of 5.628 for the evacuation time is presented in [8]. Using the insight that, perhaps surprisingly, a forced meeting of the two robots as performed in the respective algorithm does not provide an exchange of any non-trivial information, we design a simpler algorithm that achieves an upper bound of 5.625. Our numerical simulations suggest that this bound is optimal for the considered natural class of algorithms. For dealing with the technical difficulties in analyzing the algorithm, we formulate a powerful new criterion that, for a given algorithm, reduces the number of possible worst-case exits radically. This criterion is of independent interest and can be applied to any area shape. Due to space restrictions, this version of the paper contains no proofs or illustrating figures; the full version can be found at http://disco.ethz.ch/publications/ciac2017-robotevac.pdf.",
isbn="978-3-319-57586-5"
}

@book{alpern_gal_2003,
place={Boston},
title={The theory of search games and rendezvous},
publisher={Kluwer Academic Publishers},
author={Alpern, Steve and Gal, Shmuel},
year={2003}}

@book{isaacs-1965,
place={New York},
title={Differential Games},
publisher={John Wiley and Sons},
author={Isaacs, Rufus},
year={1965}}


@Article{Beck1964,
author="Beck, Anatole",
title="On the linear search problem",
journal="Israel Journal of Mathematics",
year="1964",
month="Dec",
day="01",
volume="2",
number="4",
pages="221--228",
abstract="A man in an automobile searches for another man who is located at some point of a certain road. He starts at a given point and knows in advance the probability that the second man is at any given point of the road. Since the man being sought might be in either direction from the starting point, the searcher will, in general, have to turn around many times before finding his target. How does he search so as to minimize the expected distance travelled? When can this minimum expectation actually be achieved? This paper answers the second of these questions.",
issn="1565-8511",
doi="10.1007/BF02759737",
url="https://doi.org/10.1007/BF02759737"
}

@inproceedings{CzyzowiczGGKMP14,
author = {J. Czyzowicz and
L. Gasieniec and
T. Gorry and
E. Kranakis and
R. Martin and
D. Pajak},
title = {Evacuating Robots via Unknown Exit in a Disk},
booktitle = {proceedings of the 28th International Symposium on Distributed Computing (DISC 2014), Austin, TX, USA},
pages = {122--136},
year = {2014}
}


@article{gal-minimax,
author = {Gal, Shmuel.},
title = {Minimax Solutions for Linear Search Problems},
journal = {SIAM Journal on Applied Mathematics},
volume = {27},
number = {1},
pages = {17-30},
year = {1974},
doi = {10.1137/0127002},
URL = { https://doi.org/10.1137/0127002},
eprint = { https://doi.org/10.1137/0127002}
}


@MastersThesis{cheong,
title = {A helicopter submarine search game},
author = {Chuan, Edmund Cheong Kong},
school = {Naval Postgraduate School},
year = {1988},
URL = {https://calhoun.nps.edu/handle/10945/23248},
publisher = {Calhoun}
}

@inproceedings{search-line-faulty,
author = {Czyzowicz, Jurek and Kranakis, Evangelos and Krizanc, Danny and Narayanan, Lata and Opatrny, Jaroslav},
title = {Search on a Line with Faulty Robots},
booktitle = {Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing},
series = {PODC '16},
year = {2016},
isbn = {978-1-4503-3964-3},
location = {Chicago, Illinois, USA},
pages = {405--414},
numpages = {10},
url = {http://doi.acm.org/10.1145/2933057.2933102},
doi = {10.1145/2933057.2933102},
acmid = {2933102},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {competitive ratio., cow-path problem, faulty robots, search on a line},
}

@InProceedings{treasure-barely,
author = {Stefan Dobrev and Rastislav Kr{\'a}lovic and Dana Pardubsk{\'a}},
title = {{Treasure Hunt with Barely Communicating Agents}},
booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
pages = {14:1--14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-061-3},
ISSN = {1868-8969},
year = {2018},
volume = {95},
editor = {James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8634},
URN = {urn:nbn:de:0030-drops-86346},
doi = {10.4230/LIPIcs.OPODIS.2017.14},
annote = {Keywords: parallel exhaustive search, treasure hunt, fault-tolerant search, weak coordination, black holes}
}

@inproceedings{CGGKMP,
author= {Czyzowicz, J. and Gasieniec, L. and Gorry, T. and
Kranakis, E. and Martin, R. and Pajak, D.},
title = {Evacuating Robots from an Unknown Exit Located on the Perimeter of a Disk},
booktitle ={Proceedings DISC, Austin, Texas},
pages = {122--136},
year = {2014},
publisher ={Springer}
}


@article{DBLP:conf/icdcn/CzyzowiczDGKM16,
author = {Czyzowicz, J. and
Dobrev, S. and
Georgiou, K. and
Kranakis, E. and
MacQuarrie, F.},
title = {Evacuating two robots from multiple unknown exits in a circle},
journal = {Theor. Comput. Sci.},
volume = {709},
pages = {20--30},
year = {2018}
}

@article{lamport,
title={The Byzantine generals problem},
author={Lamport, L. and Shostak, R. and Pease, M.},
journal={ACM Transactions on Programming Languages and Systems (TOPLAS)},
volume={4},
number={3},
pages={382--401},
year={1982},
publisher={ACM}
}

@article{baston_bostock_1985,
title={A High–Low search game on the unit interval},
volume={97}, DOI={10.1017/S0305004100062885},
number={2},
journal={Mathematical Proceedings of the Cambridge Philosophical Society},
publisher={Cambridge University Press},
author={Baston, V. J. and Bostock, F. A.},
year={1985},
pages={345–348}
}

@article{alpern_1985,
title={Search for point in interval, with high–low feedback},
volume={98},
DOI={10.1017/S0305004100063775},
number={3},
journal={Mathematical Proceedings of the Cambridge Philosophical Society},
publisher={Cambridge University Press},
author={Alpern, Steve},
year={1985},
pages={569–578}
}

@book{gal_1980,
place={New York},
title={Search games},
publisher={Academic Press},
author={Gal, Shmuel},
year={1980}
}

@article{lalley_1988,
author = {Lalley, S. P.},
title = {A one-dimensional infiltration game},
journal = {Naval Research Logistics (NRL)},
volume = {35},
number = {5},
pages = {441-446},
doi = {10.1002/1520-6750(198810)35:5<441::AID-NAV3220350508>3.0.CO;2-R},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/1520-6750%28198810%2935%3A5%3C441%3A%3AAID-NAV3220350508%3E3.0.CO%3B2-R},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/1520-6750%28198810%2935%3A5%3C441%3A%3AAID-NAV3220350508%3E3.0.CO%3B2-R},
abstract = {Abstract Minimax strategies are obtained for an infiltration game in which one player must move through a one-dimensional interval defended by the other player.},
year = {1988}
}

@article{vertex_to_vertex_pursuit,
title = "Vertex-to-vertex pursuit in a graph",
journal = "Discrete Mathematics",
volume = "43",
number = "2",
pages = "235 - 239",
year = "1983",
issn = "0012-365X",
doi = "https://doi.org/10.1016/0012-365X(83)90160-7",
url = "http://www.sciencedirect.com/science/article/pii/0012365X83901607",
author = "Richard Nowakowski and Peter Winkler",
abstract = "A graph G is given and two players, a cop and a robber, play the following game: the cop chooses a vertex, then the robber chooses a vertex, then the players move alternately beginning with the cop. A move consists of staying at one's present vertex or moving to an adjacent vertex; each move is seen by both players. The cop wins if he manages to occupy the same vertex as the robber, and the robber wins if he avoids this forever. We characterize the graphs on which the cop has a winning strategy, and connect the problem with the structure theory of graphs based on products and retracts."
}

@article{game_cops_robbers_1984,
title = "A game of cops and robbers",
journal = "Discrete Applied Mathematics",
volume = "8",
number = "1",
pages = "1 - 12",
year = "1984",
issn = "0166-218X",
doi = "https://doi.org/10.1016/0166-218X(84)90073-8",
url = "http://www.sciencedirect.com/science/article/pii/0166218X84900738",
author = "M. Aigner and M. Fromme",
abstract = "Let G be a finite connected graph. Two players, called cop C and robber R, play a game on G according to the following rules. First C then R occupy some vertex of G. After that they move alternately along edges of G. The cop C wins if he succeeds in putting himself on top of the robber R, otherwise R wins. We review an algorithmic characterization and structural description due to Nowakowski and Winkler. Then we consider the general situation where n cops chase the robber. It is shown that there are graphs on which arbitrarily many cops are needed to catch the robber. In contrast to this result, we prove that for planar graphs 3 cops always suffice to win."
}

@InProceedings{disk-faulty,
author="Czyzowicz, Jurek
and Georgiou, Konstantinos
and Godon, Maxime
and Kranakis, Evangelos
and Krizanc, Danny
and Rytter, Wojciech
and W{\l}odarczyk, Micha{\l}",
editor="Das, Shantanu
and Tixeuil, Sebastien",
title="Evacuation from a Disc in the Presence of a Faulty Robot",
booktitle="Structural Information and Communication Complexity",
year="2017",
publisher="Springer International Publishing",
pages="158--173",
abstract="We consider the evacuation problem on a circle for three robots, at most one of which is faulty. The three robots starting from the center of a unit circle search for an exit placed at an unknown location on the perimeter (of the circle). During the search, robots can communicate wirelessly at any distance. The goal is to minimize the time that the latest non-faulty robot reaches the exit.",
isbn="978-3-319-72050-0"
}


@inproceedings{line_by_byzantine_robots,
author = {Czyzowicz, Jurek and Kranakis, Evangelos and Krizanc, Danny and Narayanan, Lata and Opatrny, Jaroslav},
title = {Search on a Line with Faulty Robots},
booktitle = {Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing},
series = {PODC '16},
year = {2016},
isbn = {978-1-4503-3964-3},
location = {Chicago, Illinois, USA},
pages = {405--414},
numpages = {10},
url = {http://doi.acm.org/10.1145/2933057.2933102},
doi = {10.1145/2933057.2933102},
acmid = {2933102},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {competitive ratio., cow-path problem, faulty robots, search on a line},
}

@Article{Kupavskii2019,
author="Kupavskii, Andrey
and Welzl, Emo",
title="Lower bounds for searching robots, some faulty",
journal="Distributed Computing",
year="2019",
month="Aug",
day="01",
abstract="Suppose we are sending out k robots from 0 to search the real line at constant speed (with turns) to find a target at an unknown location; f of the robots are faulty, meaning that they fail to report the target although visiting its location (called crash type). The goal is to find the target in time at most {\$}{\$}{\backslash}lambda |x|{\$}{\$}$\lambda$|x|, if the target is located at x, {\$}{\$}|x| {\backslash}ge 1{\$}{\$}|x|�1, for {\$}{\$}{\backslash}lambda {\$}{\$}$\lambda$as small as possible. We show that this cannot be achieved for {\$}{\$}{\backslash}begin{\{}aligned{\}}{\&}{\backslash}lambda < 2{\backslash}frac{\{}{\backslash}rho ^{\backslash}rho {\}}{\{}({\backslash}rho -1)^{\{}{\backslash}rho -1{\}}{\}}+1,{\textasciitilde}{\textasciitilde} {\backslash}rho := {\backslash}frac{\{}2(f+1){\}}{\{}k{\}}{\textasciitilde}, {\backslash}end{\{}aligned{\}}{\$}{\$}$\lambda$<2$\rho$$\rho$($\rho$-1)$\rho$-1+1,$\rho$:=2(f+1)k,which is tight due to earlier work (see Czyzowitz et al. in Proc PODC'16, pp 405--414, 2016, where this problem was introduced). This also gives some better than previously known lower bounds for so-called Byzantine-type faulty robots that may actually wrongly report a target. In the second part of the paper we deal with the m-rays generalization of the problem, where the hidden target is to be detected on m rays all emanating at the same point. Using a generalization of our methods, along with a useful relaxation of the original problem, we establish a tight lower for this setting as well (as above, with {\$}{\$}{\backslash}rho := {\backslash}nicefrac {\{}m(f+1){\}}{\{}k{\}}{\$}{\$}$\rho$:=m(f+1)k). When specialized to the case {\$}{\$}f=0{\$}{\$}f=0, this resolves the question on parallel search on m rays, posed by three groups of scientists some 15--30 years ago: by Baeza-Yates, Culberson, and Rawlins; by Kao, Ma, Sipser, and Yin; and by Bernstein, Finkelstein, and Zilberstein. The m-rays generalization is known to have connections to other, seemingly unrelated, problems, including hybrid algorithms for on-line problems, and so-called contract algorithms.",
issn="1432-0452",
doi="10.1007/s00446-019-00358-y",
url="https://doi.org/10.1007/s00446-019-00358-y"
}

@InProceedings{linear_terrain_dependent,
author="Czyzowicz, Jurek
and Kranakis, Evangelos
and Krizanc, Danny
and Narayanan, Lata
and Opatrny, Jaroslav
and Shende, Sunil",
editor="Fotakis, Dimitris
and Pagourtzis, Aris
and Paschos, Vangelis Th.",
title="Linear Search with Terrain-Dependent Speeds",
booktitle="Algorithms and Complexity",
year="2017",
publisher="Springer International Publishing",
pages="430--441",
abstract="We revisit the linear search problem where a robot, initially placed at the origin on an infinite line, tries to locate a stationary target placed at an unknown position on the line. Unlike previous studies, in which the robot travels along the line at a constant speed, we consider settings where the robot's speed can depend on the direction of travel along the line, or on the profile of the terrain, e.g. when the line is inclined, and the robot can accelerate. Our objective is to design search algorithms that achieve good competitive ratios for the time spent by the robot to complete its search versus the time spent by an omniscient robot that knows the location of the target.",
isbn="978-3-319-57586-5"
}

@InProceedings{evacuation_of_rectilinear_polygons,
author="Fekete, S{\'a}ndor
and Gray, Chris
and Kr{\"o}ller, Alexander",
editor="Wu, Weili
and Daescu, Ovidiu",
title="Evacuation of Rectilinear Polygons",
booktitle="Combinatorial Optimization and Applications",
year="2010",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="21--30",
abstract="We investigate the problem of creating fast evacuation plans for buildings that are modeled as grid polygons, possibly containing exponentially many cells. We study this problem in two contexts: the ``confluent'' context in which the routes to exits remain fixed over time, and the ``non-confluent'' context in which routes may change. Confluent evacuation plans are simpler to carry out, as they allocate contiguous regions to exits; non-confluent allocation can possibly create faster evacuation plans. We give results on the hardness of creating the evacuation plans and strongly polynomial algorithms for finding confluent evacuation plans when the building has two exits. We also give a pseudo-polynomial time algorithm for non-confluent evacuation plans. Finally, we show that the worst-case bound between confluent and non-confluent plans is {\$}2-O({\backslash}frac{\{}1{\}}{\{}k{\}}){\$}.",
isbn="978-3-642-17458-2"
}

@inproceedings{pattanayak2017evacuating,
author = {Pattanayak, Debasish and Ramesh, H. and Mandal, Partha Sarathi and Schmid, Stefan},
title = {Evacuating Two Robots from Two Unknown Exits on the Perimeter of a Disk with Wireless Communication},
booktitle = {Proceedings of the 19th International Conference on Distributed Computing and Networking},
series = {ICDCN '18},
year = {2018},
isbn = {978-1-4503-6372-3},
location = {Varanasi, India},
pages = {20:1--20:4},
articleno = {20},
numpages = {4},
url = {http://doi.acm.org/10.1145/3154273.3154313},
doi = {10.1145/3154273.3154313},
acmid = {3154313},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {Distributed Algorithm, Evacuation, Mobile Robots},
}

@Article{Beck1970,
author="Beck, Anatole
and Newman, D. J.",
title="Yet more on the linear search problem",
journal="Israel Journal of Mathematics",
year="1970",
month="Dec",
day="01",
volume="8",
number="4",
pages="419--429",
abstract="The linear search problem has been discussed previously by one of the present authors. In this paper, the probability distribution of the point sought in the real line is not known to the searcher. Since there is noa priori choice of distribution which recommends itself above all others, we treat the situation as a game and obtain minimax type solutions. Different minimaxima apply depending on the factors which one wishes to minimize (resp. maximize). Certain criteria are developed which help the reader judge whether the results obtained can be considered ``good advice'' in the solution of real problems analogous to this one.",
issn="1565-8511",
doi="10.1007/BF02798690",
url="https://doi.org/10.1007/BF02798690"
}

@InProceedings{czyzowicz2018god,
author = {Jurek Czyzowicz and Konstantinos Georgiou and Ryan Killick and Evangelos Kranakis and Danny Krizanc and Lata Narayanan and Jaroslav Opatrny and Sunil Shende},
title = {{God Save the Queen}},
booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)},
pages = {16:1--16:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-067-5},
ISSN = {1868-8969},
year = {2018},
volume = {100},
editor = {Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8807},
URN = {urn:nbn:de:0030-drops-88074},
doi = {10.4230/LIPIcs.FUN.2018.16},
annote = {Keywords: Algorithm, Evacuation, Exit, Disk, Wireless Communication, Queen, Priority, Robots, Search, Servants, Trajectory}
}



@article{chuangpishit2018evacuating,
author = {Huda Chuangpishit and
Saeed Mehrabi and
Lata Narayanan and
Jaroslav Opatrny},
title = {Evacuating Equilateral Triangles and Squares in the Face-to-Face Model},
journal = {CoRR},
volume = {abs/1812.10162},
year = {2018},
url = {http://arxiv.org/abs/1812.10162},
archivePrefix = {arXiv},
eprint = {1812.10162},
timestamp = {Wed, 02 Jan 2019 14:40:18 +0100},
biburl = {https://dblp.org/rec/bib/journals/corr/abs-1812-10162},
bibsource = {dblp computer science bibliography, https://dblp.org}
}


@article{FRANKL1987301,
title = "Cops and robbers in graphs with large girth and Cayley graphs",
journal = "Discrete Applied Mathematics",
volume = "17",
number = "3",
pages = "301 - 305",
year = "1987",
issn = "0166-218X",
doi = "https://doi.org/10.1016/0166-218X(87)90033-3",
url = "http://www.sciencedirect.com/science/article/pii/0166218X87900333",
author = "Peter Frankl",
abstract = "It is shown that if a graph has girth at least 8t−3 and minimum degree greater that d, then more than dt cops are needed to catch a robber. Some upper bounds, in particular for Cayley graphs of groups, are also obtained."
}

@article{NEUFELD1998253,
title = "A game of cops and robbers played on products of graphs",
journal = "Discrete Mathematics",
volume = "186",
number = "1",
pages = "253 - 268",
year = "1998",
issn = "0012-365X",
doi = "https://doi.org/10.1016/S0012-365X(97)00165-9",
url = "http://www.sciencedirect.com/science/article/pii/S0012365X97001659",
author = "S. Neufeld and R. Nowakowski",
abstract = "The game of cops and robbers is played with a set of ‘cops’ and a ‘robber’ who occupy some vertices of a graph. Both sides have perfect information and they move alternately to adjacent vertices. The robber is captured if at least one of the cops occupies the same vertex as the robber. The problem is to determine on a given graph, G, the least number of cops sufficient to capture the robber, called the cop-number, c(G). We investigate this game on three products of graphs: the Cartesian, categorical, and strong products."
}

@article{BOLLOBAS2013226,
title = "Cops and robbers in a random graph",
journal = "Journal of Combinatorial Theory, Series B",
volume = "103",
number = "2",
pages = "226 - 236",
year = "2013",
issn = "0095-8956",
doi = "https://doi.org/10.1016/j.jctb.2012.10.002",
url = "http://www.sciencedirect.com/science/article/pii/S0095895612000822",
author = "Béla Bollobás and Gábor Kun and Imre Leader",
keywords = "Cops and robbers, Pursuit and evasion, Random graphs",
abstract = "The cop-number of a graph is the minimum number of cops needed to catch a robber on the graph, where the cops and the robber alternate moving from a vertex to a neighbouring vertex. It is conjectured by Meyniel that for a graph on n vertices O(n) cops suffice. The aim of this paper is to investigate the cop-number of a random graph. We prove that for sparse random graphs the cop-number has order of magnitude n1/2+o(1). The best known strategy for general graphs is the area-defending strategy, where each cop ‘controls’ one region by himself. We show that, for general graphs, this strategy cannot be too effective: there are graphs that need at least n1−o(1) cops for this strategy."
}

@article{KAO199663,
title = "Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem",
journal = "Information and Computation",
volume = "131",
number = "1",
pages = "63 - 79",
year = "1996",
issn = "0890-5401",
doi = "https://doi.org/10.1006/inco.1996.0092",
url = "http://www.sciencedirect.com/science/article/pii/S0890540196900929",
author = "Ming-Yang Kao and John H. Reif and Stephen R. Tate",
abstract = "Searching for a goal is a central and extensively studied problem in computer science. In classical searching problems, the cost of a search function is simply the number of queries made to an oracle that knows the position of the goal. In many robotics problems, as well as in problems from other areas, we want to charge a cost proportional to the distance between queries (e.g., the time required to travel between two query points). With this cost function in mind, the abstract problem known as thew-lane cow-path problem was designed. There are known optimal deterministic algorithms for the cow-path problem; we give the first randomized algorithm in this paper. We show that our algorithm is optimal for two paths (w=2) and give evidence that it is optimal for larger values ofw. Subsequent to the preliminary version of this paper, Kaoet al.(in“Proceedings, 5th ACM–SIAM Symposium on Discrete Algorithm,” pp. 372–381, 1994) have shown that our algorithm is indeed optimal for allw⩾2. Our randomized algorithm gives expected performance that is almost twice as good as is possible with a deterministic algorithm. For the performance of our algorithm, we also derive the asymptotic growth with respect tow—despite similar complexity results for related problems, it appears that this growth has never been analyzed."
}

@INPROCEEDINGS{6426279,
author={K. {Spieser} and E. {Frazzoli}},
booktitle={2012 IEEE 51st IEEE Conference on Decision and Control (CDC)},
title={The Cow-Path Game: A competitive vehicle routing problem},
year={2012},
volume={},
number={},
pages={6513-6520},
keywords={decision making;game theory;multi-agent systems;search problems;vehicle routing;cow-path game;competitive vehicle routing problem;multivehicle system;self-interested mobile agents;target capture;minimal sensing capability;strategic algorithm;agent decision making;trajectory planning;equilibrium strategy;search game;clover patch;unit ring;taxi driver;busy urban landscape;Games;Search problems;Vehicles;Turning;Sensors;Cows;Trajectory},
doi={10.1109/CDC.2012.6426279},
ISSN={0743-1546},
month={Dec},}

@article{JEZ2009543,
title = "On the two-dimensional cow search problem",
journal = "Information Processing Letters",
volume = "109",
number = "11",
pages = "543 - 547",
year = "2009",
issn = "0020-0190",
doi = "https://doi.org/10.1016/j.ipl.2009.01.020",
url = "http://www.sciencedirect.com/science/article/pii/S0020019009000349",
author = "Artur Jeż and Jakub Łopuszański",
keywords = "On-line algorithms, Search problems, Uncertainty",
abstract = "We investigate the problem introduced by Baeza-Yates et al. [R.A. Baeza-Yates, J.C. Culberson, G.J.E. Rawlins, Searching with uncertainty, Research report, University of Waterloo, 1987]: given a plane and a horizontal or a vertical line in unknown location give a strategy to find this line. We use a competitive analysis to measure the performance of this strategy. This problem is one of the first generalisations of the cow search problem."
}

@InProceedings{10.1007/978-3-319-72751-6_6,
author="Chuangpishit, Huda
and Czyzowicz, Jurek
and Kranakis, Evangelos
and Krizanc, Danny",
editor="Fern{\'a}ndez Anta, Antonio
and Jurdzinski, Tomasz
and Mosteiro, Miguel A.
and Zhang, Yanyong",
title="Rendezvous on a Line by Location-Aware Robots Despite the Presence of Byzantine Faults",
booktitle="Algorithms for Sensor Systems",
year="2017",
publisher="Springer International Publishing",
pages="70--83",
abstract="A set of mobile robots is placed at points of an infinite line. The robots are equipped with GPS devices and they may communicate their positions on the line to a central authority. The collection contains an unknown subset of ``spies'', i.e., byzantine robots, which are indistinguishable from the non-faulty ones. The set of the non-faulty robots need to rendezvous in the shortest possible time in order to perform some task, while the byzantine robots may try to delay their rendezvous for as long as possible. The problem facing a central authority is to determine trajectories for all robots so as to minimize the time until the non-faulty robots have rendezvoused. The trajectories must be determined without knowledge of which robots are faulty. Our goal is to minimize the competitive ratio between the time required to achieve the first rendezvous of the non-faulty robots and the time required for such a rendezvous to occur under the assumption that the faulty robots are known at the start. We provide a bounded competitive ratio algorithm, where the central authority is informed only of the set of initial robot positions, without knowing which ones or how many of them are faulty. When an upper bound on the number of byzantine robots is known to the central authority, we provide algorithms with better competitive ratios. In some instances we are able to show these algorithms are optimal.",
isbn="978-3-319-72751-6"
}

@InProceedings{iman2019,
author="Bagheri, Iman
and Narayanan, Lata
and Opatrny, Jaroslav",
editor="Dressler, Falko
and Scheideler, Christian",
title="Evacuation of Equilateral Triangles by Mobile Agents of Limited Communication Range",
booktitle="Algorithms for Sensor Systems",
year="2019",
publisher="Springer International Publishing",
pages="3--22",
abstract="We consider the problem of evacuating {\$}{\$}k {\backslash}ge 2{\$}{\$} mobile agents from a unit-sided equilateral triangle through an exit located at an unknown location on the perimeter of the triangle. The agents are initially located at the centroid of the triangle and they can communicate with other agents at distance at most r with {\$}{\$}0{\backslash}le r {\backslash}le 1{\$}{\$}. An agent can move at speed at most one, and finds the exit only when it reaches the point where the exit is located. The agents can collaborate in the search for the exit. The goal of the evacuation problem is to minimize the evacuation time, defined as the worst-case time for all the agents to reach the exit. We propose and analyze several algorithms for the problem of evacuation by {\$}{\$}k {\backslash}ge 2{\$}{\$} agents; our results indicate that the best strategy to be used varies depending on the values of r and k. For two agents, we give four algorithms, the last of which achieves the best performance for all sub-ranges of r in the range {\$}{\$}0 < r {\backslash}le 1{\$}{\$}. We also show a lower bound on the evacuation time of two agents for any {\$}{\$}r < 0.336{\$}{\$}. For {\$}{\$}k >2{\$}{\$} agents, we study three strategies for evacuation: in the first strategy, called X3C, agents explore all three sides of the triangle before connecting to exchange information; in the second strategy, called X1C, agents explore a single side of the triangle before connecting; in the third strategy, called CXP, the agents travel to the perimeter to locations in which they are connected, and explore it while always staying connected. For 3 or 4 agents, we show that X3C works better than X1C for small values of r, while X1C works better for larger values of r. Finally, we show that for any r, evacuation of {\$}{\$}k=6 +2{\backslash}lceil ({\backslash}frac{\{}1{\}}{\{}r{\}}-1{\backslash}rceil {\$}{\$} agents can be done using the CXP strategy in time {\$}{\$}1+{\backslash}sqrt{\{}3{\}}/3{\$}{\$}, which is optimal in terms of time, and asymptotically optimal in terms of the number of agents.",
isbn="978-3-030-34405-4"
}