Mobility Matters
Home›Search in geometric domains›Search, evacuation and patrolling›Linear search (cow path)›Evacuation

Evacuation

Robots start at the centre of a disk (or a polygon) and must all leave through an exit at an unknown point of the boundary, as fast as possible.

Problem statement and measurescollapse
O12Start: both robots at the centre OTime 1: at the boundary together; they splitRobot 1 finds the exit, tells robot 2Final: robot 2 arrives by the chord at 1 + 2π/3 + √3
Evacuation from a disk: two robots start at the centre of a unit disk and must both reach an exit at an unknown point of the boundary. The animation runs the wireless algorithm of Czyzowicz et al. 2014 at unit speed: both walk to the boundary together, then search it in opposite directions; the one that finds the exit tells the other by wireless communication, and the other walks straight across the disk along the chord. With the exit placed at arc distance \(2\pi/3\) (the worst case) the time is \(1 + 2\pi/3 + \sqrt3 \approx 4.83\).

\(k\) unit-speed robots start together at the centre of a unit disk (or the centroid of a unit equilateral triangle or square). An exit lies at an unknown point of the boundary; a robot recognises it only on reaching it. Time is the worst case, over exit positions, of the time until the last robot reaches the exit (in priority evacuation, where one robot is the queen: until the queen does).

Measures: Evacuation time, worst-case time until the last robot (or the queen) reaches the exit; unit disk, unit speed.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Two people stand in the middle of a dark round room of radius 1 and know there is one door somewhere along its edge, but not where; they can talk by walkie-talkie. In evacuation the people are robots, points that move at unit speed; the room is a unit disk, the points at distance at most 1 from its centre; its edge is the boundary, the circle of radius 1; and the door is the exit, a point of the boundary that a robot recognises only when it stands on it. \(k\) robots start at the centre of the disk. The goal is to minimise, in the worst case over exit positions, the time until the last robot reaches the exit. In the basic version there are two robots with wireless communication: a robot that finds the exit tells the other instantly, wherever it is.

1AlgorithmGo to the boundary together, then split Two wireless robots, disk → Czyzowicz et al. 2014
  1. Both robots walk together from the centre to the same point \(A\) of the boundary (time 1).
  2. One walks clockwise along the boundary, the other counter-clockwise, at full speed.
  3. The robot that finds the exit tells the other by wireless communication.
  4. The other walks straight across the disk to the exit, along a chord (the straight segment between two points of the boundary).
Why it works and what it costs. If the exit is found after each robot has walked an arc (a piece of the boundary) of length \(x\) (so \(x \le \pi\)), the robots are \(2x\) apart along the boundary, and the chord between them has length \(2\sin x\). The total time is \(1 + x + 2\sin x\). Its derivative \(1 + 2\cos x\) is zero at \(x = 2\pi/3\), so the worst case is \(1 + 2\pi/3 + \sqrt3 \approx 4.826\) Czyzowicz et al. 2014. This is exactly optimal (next idea).

Why it matters. Searching the boundary in opposite directions and cutting across on a chord is the template for almost every later disk evacuation algorithm.

2Lower boundTwo unexplored points far apart Two wireless robots, disk → Czyzowicz et al. 2014

Look at time \(1 + 2\pi/3\). Each robot needed time 1 just to reach the boundary, so together they have walked at most \(4\pi/3\) of the boundary, and at least \(2\pi/3\) of the boundary (minus a tiny \(\varepsilon\)) is unexplored. Czyzowicz et al. 2014 show that then there are two unexplored points at arc distance about \(2\pi/3\) (measured along the boundary), so the chord between them has length \(\sqrt3\). The adversary, an opponent who watches the robots and chooses the exit position, waits until some robot first reaches one of these two points and places the exit at the other one.

Why it holds. That robot is then at least \(\sqrt3\) away from the exit and must still get there, and this happens no earlier than time \(1 + 2\pi/3\). So every algorithm needs at least \(1 + 2\pi/3 + \sqrt3\) in the worst case, which matches the algorithm above Czyzowicz et al. 2014.

Why it matters. Counting how much of the boundary can be explored by a given time, then hiding the exit at the far end of an unexplored chord, is the basic lower-bound tool for evacuation.

3AlgorithmWithout wireless communication: catch the other robot Two face-to-face robots, disk → Czyzowicz et al. 2014

If robots exchange information only when they meet (face-to-face communication):

  1. Go to the boundary together and split in opposite directions, as before.
  2. The robot that finds the exit cannot call; it walks along a chord to the point where the other robot will be, meets it,
  3. and both walk back along a chord to the exit.
Why it works and what it costs. The robot that finds the exit must cover the distance to the other robot and back, so the cost is larger: about \(5.74\) for this simple version Czyzowicz et al. 2014. Cleverer paths that leave the boundary and come back improved it to about \(5.6234\) Disser & Schmitt 2019, while the best lower bound is \(3 + \pi/6 + \sqrt3 \approx 5.255\) Czyzowicz et al. 2020. This gap has been open since 2019.

Why it matters. It shows how much communication is worth, and it is one of the simplest-to-state geometric questions still open in the area.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Evacuation time
Disk, two wireless robots of different speeds
With speeds \(1\) and \(v \ge 1\), two wireless robots evacuate optimally for \(v \ge 2.75\); for smaller \(v\) the bounds are within a factor \(1.22\).
polynomial gap \(\tfrac{1+2\arccos(-2/v)}{v}+\sqrt{1-4/v^2}\) vs \(\text{matching for } v \ge 2.75\) unknown exit
Two wireless robots, disk standard
Two wireless robots evacuate the unit disk in exactly \(1+2\pi/3+\sqrt3 \approx 4.826\).
tight \(1+2\pi/3+\sqrt{3}\) vs \(1+2\pi/3+\sqrt{3}\) unknown exit
Two robots, two exits, face-to-face
With two exits at unknown positions and communication only on meeting, the optimal evacuation time is \((1+\pi/2)R \approx 2.57R\).
tight \(1+\pi/2\) vs \(1+\pi/2\) unknown exits
Two robots, two exits, wireless
With two exits and wireless communication, evacuation takes between \(2R\) and \((1+\pi/3)R \approx 2.047R\).
polynomial gap \(1+\pi/3\) vs \(2\) unknown exits
Disk, search-and-fetch, two wireless robots
Two wireless robots find a treasure on the boundary and bring it to an exit at known arc distance \(\alpha\) in \(1+\pi-\alpha+4\sin(\alpha/2)\).
unknown \(1+\pi-\alpha+4\sin(\alpha/2)\) vs —
Disk, search-and-fetch, two face-to-face robots
Face-to-face, two robots fetch the treasure in \(1+\pi-\alpha/2+3\sin(\alpha/2)\), against \(1+\pi/3+4\sin(\alpha/2)\) for \(\alpha \le 2\pi/3\).
polynomial gap \(1+\pi-\alpha/2+3\sin(\alpha/2)\) vs \(1+\pi/3+4\sin(\alpha/2)\) unknown exit
Two face-to-face robots, disk
Face-to-face, two robots need between \(\approx 5.255\) and \(\approx 5.6234\); the gap has been open since 2019.
polynomial gap \(\approx 5.6234\) vs \(3+\pi/6+\sqrt{3}\) unknown exit
Two robots with asymmetric communication, disk
When one robot can only send and the other only receive, evacuation lies strictly between the wireless and face-to-face optima; \(\pi+2\) suffices.
polynomial gap \(\pi+2\) vs \(> 1+2\pi/3+\sqrt3\) one-way communication
Disk, priority evacuation, queen and one servant
A queen and one servant evacuate the queen in about \(4.819\), strictly faster than evacuating both; the lower bound is about \(4.568\).
polynomial gap \(\approx 4.81854\) vs \(\approx 4.56798\) unknown exit
Three wireless robots, disk
Three wireless robots: between \(\approx 4.159\) and \(4.22\).
polynomial gap \(< 4.22\) vs \(\approx 4.159\) unknown exit
Three wireless robots, one crash fault
If one of three wireless robots may crash, evacuation takes between \(\approx 5.082\) and \(\approx 6.309\).
polynomial gap \(\approx 6.309\) vs \(\approx 5.082\) faulty reports
Three wireless robots, one Byzantine
With one Byzantine robot among three: between \(\approx 5.948\) and \(\approx 6.921\).
polynomial gap \(\approx 6.921\) vs \(\approx 5.948\) indistinguishable Byzantine agents
Three face-to-face robots, disk
Three face-to-face robots: between \(\approx 4.519\) and \(3+2\pi/3 \approx 5.09\).
polynomial gap \(3+2\pi/3\) vs \(\approx 4.519\) unknown exit
Disk, priority evacuation, queen and two servants
A queen and two servants evacuate the queen in about \(3.833\) against a lower bound of about \(3.631\).
polynomial gap \(\approx 3.8327\) vs \(\approx 3.6307\) unknown exit
Many wireless robots, disk
With \(k\) wireless robots the time approaches \(3+\pi/k\).
near-optimal \(3+\pi/k+O(k^{-4/3})\) vs \(3+\pi/k\) unknown exit
Many face-to-face robots, disk
With \(k\) face-to-face robots the time is \(3+2\pi/k\) up to \(O(k^{-2})\); the separation from wireless is a factor 2 in the second term.
near-optimal \(3+2\pi/k\) vs \(3+2\pi/k-O(k^{-2})\) unknown exit
Priority evacuation (queen and servants), disk
Only the queen must leave; \(\sigma\) servants (the paper writes \(n\); \(k = \sigma+1\) robots) help her find the exit.
polynomial gap \(2+4(\sqrt2-1)\pi/\sigma\) vs \(1+\tfrac{2}{\sigma}\arccos\left(-\tfrac{2}{\sigma}\right)+\sqrt{1-\tfrac{4}{\sigma^2}}\) unknown exit
Line, two face-to-face robots of different speeds
With speeds \(1\) and \(v \le 1\), two face-to-face robots evacuate the line optimally: ratio \((1+3v)/(1-v)\) for \(v \le 1/3\) and \(9v\) above.
tight \(\tfrac{1+3v}{1-v}\ (v \le \tfrac13),\ 9v\ (v \ge \tfrac13)\) vs \(\text{matching}\) unknown distance
Line, two wireless robots of different speeds
With speeds \(1\) and \(v \le 1\), two wireless robots evacuate the line optimally, with a ratio that changes form at \(v = \sqrt{17}-4\).
tight \(\tfrac{1+3v}{1-v}\ (v \le \sqrt{17}-4),\ \tfrac{2+v+\sqrt{v^2+8v}}{2}\ \text{above}\) vs \(\text{matching}\) unknown distance
Line, a sender and a receiver
A robot that can only send and one that can only receive wirelessly evacuate the line with ratio exactly \(3+2\sqrt2\).
tight \(3+2\sqrt2\) vs \(3+2\sqrt2\) one-way communication
Line, any number of wireless robots
With wireless communication, two or more robots evacuate the line with competitive ratio exactly 3.
tight \(3\) vs \(3\) unknown distance
Line, \(2f+1\) wireless robots, \(f\) crash faults
With a near majority of faulty robots, evacuation on the line takes ratio about \(7.437\) for \((k,f) = (3,1)\), tending to \(4+2\sqrt2\); the lower bounds come from search.
polynomial gap \(\approx 7.437\) vs \(\approx 5.233\) faulty reports
Line, any number of face-to-face robots
On the line, face-to-face robots evacuate with competitive ratio exactly 9: extra robots do not help.
tight \(9\) vs \(9\) unknown distance
Two face-to-face robots, equilateral triangle
From the centroid of a unit equilateral triangle: between \(1+2/\sqrt3\) and \(2.3367\).
polynomial gap \(2.3367\) vs \(1+2/\sqrt3\) unknown exit
Triangle, two wireless robots starting on the boundary
Two wireless robots starting on the boundary of a non-obtuse triangle evacuate in half the perimeter if they may choose their start, which is optimal.
tight \((a+b+c)/2\) vs \((a+b+c)/2\) unknown exit
Triangle, any number of face-to-face robots
\(k\) face-to-face robots at the centroid of an equilateral unit triangle evacuate in at most \(\sqrt3+3/k\), against \(\sqrt3\).
near-optimal \(\sqrt3+3/k\) vs \(\sqrt3\) unknown exit
Two face-to-face robots, square
From the centroid of a unit square: between \(3.118\) and \(3.4645\).
polynomial gap \(3.4645\) vs \(3.118\) unknown exit
\(m\) rays, \(k = m\) wireless robots at the junction
With one wireless robot per ray, starting at the junction, the competitive ratio is exactly 3.
tight \(3\) vs \(3\) unknown exit

Open questions 14

Disk, two wireless robots of different speeds

  1. Optimal evacuation for \(1 < v < 2.75\), for more than two robots, and face-to-face Lamprou et al. 2020.

Two robots, two exits, wireless

  1. Close the gap between \(2R\) and \((1+\pi/3)R\) for two wireless robots and two exits Pattanayak et al. 2018.

Disk, search-and-fetch, two wireless robots

  1. Lower bounds that separate wireless from face-to-face search-and-fetch Georgiou et al. 2019.

Two face-to-face robots, disk

  1. Close the gap between \(3+\pi/6+\sqrt3 \approx 5.255\) and \(5.6234\) for two face-to-face robots.

Two robots with asymmetric communication, disk

  1. Give an explicit lower bound above \(\approx 4.826\) for sender/receiver evacuation.

Disk, priority evacuation, queen and one servant

  1. Close the gap between \(4.568\) and \(4.819\) Georgiou & Wang 2025.

Three wireless robots, disk

  1. Find the optimal evacuation time for three wireless robots.

Three wireless robots, one crash fault

  1. Tight bounds for disk evacuation with one crash-faulty robot among three.

Priority evacuation (queen and servants), disk

  1. Close the gap for priority evacuation; for one servant the bounds differ by about 0.25 (a 2024 preprint, not yet in the bibliography).

Line, a sender and a receiver

  1. Close the gaps for one sender and many receivers (\(2+\sqrt5\) against \(5\)) and for many senders and one receiver (\(3\) against about \(5.681\)) Czyzowicz et al. 2021.

Line, \(2f+1\) wireless robots, \(f\) crash faults

  1. Tight bounds for evacuation with \(k = 2f+1\) crash or Byzantine robots Czyzowicz et al. 2021.

Triangle, two wireless robots starting on the boundary

  1. Face-to-face evacuation of general triangles, and wireless evacuation of obtuse triangles Georgiou & Jang 2026.

\(m\) rays, \(k = m\) wireless robots at the junction

  1. Starting off the junction with \(k = m\): close \(2+\sqrt{7/3} \approx 3.528\) against \(4\) Brandt et al. 2020.
  2. Fewer robots than rays (\(1 < k < m\)): the bounds \(3+2\lfloor (m-1)/k\rfloor\) and \(1+2\tfrac{m-1}{k}(1+\tfrac{k}{m-1})^{1+(m-1)/k}\) differ Brandt et al. 2020.

What the community started looking at

Evacuation was introduced to capture the tension between spreading the robots to find the exit fast and keeping them close so that the others can reach it quickly Czyzowicz et al. 2014. The first results already separated wireless from face-to-face communication. The community then tightened the two-robot face-to-face constants Czyzowicz et al. 2020 Brandt et al. 2017 Disser & Schmitt 2019 and added faults Czyzowicz et al. 2017, priority (one robot must leave) Czyzowicz et al. 2018, asymmetric communication Georgiou et al. 2022, other domains Chuangpishit et al. 2020 and several exits Pattanayak et al. 2018. Beyond disks, triangles and squares, the question was asked on the line and on rays Chrobak et al. 2015 Brandt et al. 2020, in regular polygons with priority Georgiou et al. 2025, on known trees as a planning problem that is NP-hard to solve exactly Devillez et al. 2021, and in the plane for an unknown shoreline Acharjee et al. 2020 or an unknown convex region to escape WEI et al. 2016.

Generalisation of Linear search (cow path)

Evacuation is a form of search with an extra requirement: "optimality in evacuation is measured by the time it takes for the last robot to reach the exit, whereas in traditional search, optimality is measured by the time it takes the first robot to reach the exit" Czyzowicz et al. 2017. The introductory paper notes its similarity with the cow-path problem, and that evacuating uniform agents on a line "is as hard as the cow-path problem" Czyzowicz et al. 2014.

Derived problems

Chauffeuring a crashed robot: Evacuation where one robot has crashed inside the disk: the active robot must first find it, then carry it, more slowly, to an exit.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • Meeting at one place Rendezvous and gathering on graphs, gathering and convergence in the plane, and evacuation through an unknown exit all ask entities to end at one point. The papers give the same reasons for meeting, but each model makes a different part of it hard: symmetry and exploration on graphs, capability in the plane, information in continuous search.
  • From the cow path to evacuation The line of work from Bellman's and Beck's linear search problem to group search with faulty robots, evacuation of disks and polygons, priority evacuation, and patrolling by robots with distinct speeds.
  • When agents fail A node that destroys visitors, a robot that stops, an agent that lies, a searcher that misses the target: the papers motivate each fault by the hardware or the network, and each kind of fault changes a different measure, from team size to feasibility to an exact constant.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.
  • The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Czyzowicz et al. 2019 Group Search and Evacuation. Survey chapter on group search and evacuation. Not read.
  • Kranakis 2024 Invited Paper: A Survey of the Impact of Knowledge on the Competitive Ratio in Linear Search. Survey of how knowledge affects the competitive ratio of linear search, including evacuation. Not read.
  • Georgiou et al. 2023 Optimal circle search despite the presence of faulty robots. Circle search with crash and Byzantine robots. Not read.
  • Georgiou & Lucier 2023 Weighted group search on a line & implications to the priority evacuation problem. Weighted group search on the line, with consequences for priority evacuation. Not read.
  • Czyzowicz et al. 2021 Time-energy tradeoffs for evacuation by two robots in the wireless model. Time–energy trade-offs for evacuating two wireless robots from the line.
  • Jawhar & Kranakis 2021 Bike Assisted Evacuation on a Line. Introduces bike-assisted evacuation on the line. Abstract only.
  • Pattanayak et al. 2020 Collaborative Evacuation of Mobile Robots. One-page summary of collaborative disk evacuation (two exits, chauffeuring). Abstract only.
  • Chuangpishit et al. 2020 A Multi-Objective Optimization Problem on Evacuating 2 Robots from the Disk in the Face-to-Face Model; Trade-Offs between Worst-Case and Average-Case Analysis. Average versus worst case for two face-to-face robots in the disk; probably the journal version of Chuangpishit et al. 2019. Not read.
  • Liu et al. 2022 Online Algorithm for Evacuating Crashed Faulty Robots from A Square. Evacuating crashed robots from a square. Abstract only.
  • Fekete et al. 2010 Evacuation of Rectilinear Polygons. Evacuating rectilinear polygons; background from before the disk line of work.
  • Borowiecki et al. 2025 Discrete evacuation in graphs with multiple exits. Discrete evacuation of many agents through known exits of a graph, limited by congestion: a different sense of evacuation. Not read.
  • Czyzowicz et al. 2019 Group search of the plane with faulty robots. Group search of the plane with crash and Byzantine robots. Abstract only.
  • Dobrev et al. 2020 Improved Lower Bounds for Shoreline Search. Lower bounds for searching an unknown line in the plane. Not read.
  • Xu & Qin 2013 Strategies of Groups Evacuation from a Convex Region in the Plane. Groups escaping an unknown convex region of the plane; the group lower bound 3 is cited by WEI et al. 2016.
  • Wei et al. 2014 On-Line Strategies for Evacuating from a Convex Region in the Plane. Online strategies for escaping a convex region. Not read.
  • Li & Xu 2017 Online Strategies for Evacuating from a Convex Region in the Plane. Online strategies for escaping a convex region. Not read.
  • Liu et al. 2015 Online Strategies for Evacuating from a Convex Region by Groups in the Plane. Groups escaping a convex region. Not read.
  • Jiang et al. 2015 An On-Line Strategy of Groups Evacuation from a Convex Region in the Plane. Groups escaping a convex region. Title only.
  • Wei et al. 2016 Evacuating from an Unknown Affected Area. Escaping an unknown affected area. Not read.
  • Conley & Georgiou 2025 Multi-agent Disk Inspection. Related task: several agents inspect the boundary of a disk.
  • Georgiou 2026 Optimal Average Disk-Inspection via Fermat’s Principle. Related task: optimal average-case disk inspection.
  • Coleman et al. 2023 Delivery to Safety with Two Cooperating Robots. Related task: two robots deliver a target to safety. Not read.
  • Georgiou et al. 2025 Spirals and Beyond: Competitive Plane Search with Multi-Speed Agents. Plane search with agents of several speeds; a preprint, not read.
  • Coleman et al. 2026 Search and Rescue on the Plane. Search and rescue in the plane; a preprint, not read.

All settings

The assumption tree (28 settings, 12 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Evacuation time); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Domain › Number of robots › Goal › Exits › Communication › Faults › Speeds › Randomness.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Domain

0unspecified bounded domain1unit disk, start at the centre1unit equilateral triangle, start at the centroid1unit square, start at the centroid1the infinite line1\(m\) rays from a junction (a star)

Czyzowicz et al. posed evacuation in the unit disk with the exit on its boundary Czyzowicz et al. 2014, which remains the standard domain. Evacuation on the line had been raised just before by Chrobak et al., who showed that evacuating several uniform agents is as hard as the cow-path problem (as reported by Czyzowicz et al. 2014) Chrobak et al. 2015. Polygons followed: equilateral triangles and squares, first with wireless robots Czyzowicz et al. 2015 and then face-to-face Chuangpishit et al. 2020. Brandt et al. studied \(m\) concurrent rays, citing Hammar et al. that "a problem with paradigmatic status in this framework is searching on m concurrent rays" Brandt et al. 2020. Evacuation from a general convex region appears in a separate line of online-strategy papers Xu & Qin 2013 Wei et al. 2014.

Formal definitions
0any domain
A bounded convex domain, robots start at an interior point.
1disk
The unit disk; robots start at its centre; the exit is a point of the boundary circle.
1triangle
The equilateral triangle of unit side; robots start at its centroid; the exit is a point of the boundary.
1square
The unit square; robots start at its centroid; the exit is a point of the boundary.
1line
The robots start at the origin of the real line; the exit is at an unknown point at distance at least \(1\); the measure is the competitive ratio, the evacuation time divided by that distance.
1rays
\(m \ge 2\) half-lines share an endpoint, the junction; the exit lies on one ray at distance at least \(1\) from the start; the measure is the competitive ratio.

Number of robots

0any number \(k\) of robots1two robots1three robots

Czyzowicz et al. studied the exact optimal evacuation time for \(k = 2\) and \(k = 3\) robots in the disk, and the asymptotic behaviour as \(k\) grows: \(3 + 2\pi/k\) face-to-face and \(3 + \pi/k\) wireless, up to lower-order terms Czyzowicz et al. 2014. Most later disk papers fix \(k = 2\), and even there the face-to-face case is not closed after several improvements Czyzowicz et al. 2020 Brandt et al. 2017 Disser & Schmitt 2019. Specific small team sizes also appear in priority evacuation with one or two servants Czyzowicz et al. 2018 and with polygons, where triangles and squares were solved for \(k = 2, 3, 4\) Chuangpishit et al. 2020.

Formal definitions
0any \(k\)
\(k\ge1\) robots.
1two robots
Two robots.
1three robots
Three robots.

Goal

0every robot must reach the exit1priority: only the queen must reach the exit1search-and-fetch: a treasure must be brought to the exit

Search ends at the first arrival and evacuation at the last Czyzowicz et al. 2014. Czyzowicz et al. introduced priority evacuation, in which only a distinguished robot, the queen, must reach the exit while servants help. They motivate it by a robot that alone "has the capability to address an urgent need at the target, for example, performing an emergency procedure, or closing a breach in the perimeter" Czyzowicz et al. 2018. Georgiou, Karakostas and Kranakis introduced search-and-fetch (treasure evacuation), where a robot must carry a treasure to the exit. It is motivated by search-and-rescue, where drones must "locate a victim (the treasure) and bring her to safety (the exit)" Georgiou et al. 2019. They note that "this is the first time an explicit ordering on the tasks to be performed is imposed on two moving robots" Georgiou et al. 2019.

Formal definitions
0all robots
The task ends when the last robot reaches the exit.
1priority (queen)
One designated robot (the queen) must reach the exit; the others (servants) only help; the task ends when the queen exits.
1search-and-fetch
A treasure lies at an unknown point of the boundary, and the exit at a known arc distance \(\alpha\) from it; the task ends when some robot has carried the treasure to the exit.

Exits

0one exit1two exits at unknown positions

Evacuation was posed with a single unknown exit Czyzowicz et al. 2014. Czyzowicz et al. considered two robots on a circle with \(k\) exits whose distribution is known, where the robots do not know their own position Czyzowicz et al. 2016. Pattanayak, Ramesh, Mandal and Schmid studied two robots starting at the centre of the disk with two exits at unknown points whose arc distance \(\alpha\) is known. They worked in both communication models and introduced labelled exits Pattanayak et al. 2018. More exits help the robots, but only if the algorithm can use what it knows about the exits' relative position.

Formal definitions
0one exit
One exit, at an unknown point of the boundary.
1two exits
Two exits at unknown points of the boundary; the task ends when every robot has reached one of them.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.