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 at the centroid, or at a given point of the boundary, 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; in weighted evacuation of two robots, a weighted average of their arrival times; in search, until a non-faulty robot has reached the exit and every non-faulty robot knows where it is).

Measures: Evacuation time, worst-case time until the last robot (or the queen) reaches the exit, or the weighted average or search time where the goal says so; 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. 2020d. 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
Disk, weighted evacuation of two wireless robots
For two wireless robots in the disk the weighted cost is exactly \(1+\pi\) when \(w = 1\); for larger \(w\) it lies between \(\max(1+\pi,\ 3.618+0.782\,w/(w+1))\) and \(1+d+\tfrac{2w}{w+1}\sin d\), tending to priority evacuation as \(w \to \infty\).
polynomial gap \(1+d+\tfrac{2w}{w+1}\sin d\) vs \(1+\pi\) 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 \(1+4\pi/3 \approx 5.188\) and \(\approx 6.309\).
polynomial gap \(\approx 6.309\) vs \(1+4\pi/3 \approx 5.188\) faulty reports
Three wireless robots, one Byzantine
With one Byzantine robot among three: between \(\approx 5.948\) and \(\approx 6.921\).
polynomial gap \(1+4\pi/3+\sqrt3 \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
Disk, \(k\) wireless robots, \(f\) Byzantine
With \(k\) wireless robots and one Byzantine robot evacuation takes at most \(3+4\pi/k\); general \(f < k/2\) has upper bounds only, and lower bounds come from search and from the fault-free case.
polynomial gap \(1+2\pi(f+1)/k+\max\{G_e(k^*),H_e(k^*)\}\) vs \(1+2\pi(f+1)/k\) faulty reports
Disk search, \(k\) wireless robots, \(f\) crash faults
Search of the disk boundary with \(f\) crash faults takes exactly \(1+2\pi(f+1)/k\): every point must be seen by \(f+1\) robots.
tight \(1+2\pi(f+1)/k\) vs \(1+2\pi(f+1)/k\) faulty reports
Disk search, \(k\) wireless robots, one Byzantine
With one Byzantine robot, search takes exactly \(1+4\pi/k\), as with one crash fault.
tight \(1+4\pi/k\) vs \(1+4\pi/k\) faulty reports
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
Disk, \(k\) face-to-face robots, \(f\) Byzantine
Face-to-face with \(f\) Byzantine robots: \(3+4\pi/k+2\sin(\pi/k)\) for \(f=1\), and a general upper bound; lower bounds come from search and the fault-free case.
polynomial gap \(3+2\pi(f+1)/k+\max_{2\le j\le k} 2(j-1)\sin\bigl(\tfrac{f-j+2}{j-1}\cdot\tfrac{\pi}{k}\bigr)\) vs \(1+2\pi(f+1)/k\) faulty reports
Disk, \(k\) face-to-face robots, \(f\) crash faults
Face-to-face with \(f\) crash faults, \(k\) robots evacuate in at most \(3+2\pi(f+1)/k\).
polynomial gap \(3+2\pi(f+1)/k\) vs \(1+2\pi(f+1)/k\) faulty reports
Line, weighted evacuation of two wireless robots
When the heavy robot's arrival counts \(w\) times the light one's, two wireless robots achieve exactly \(1+\sqrt{2w/(1+w)}\), between \(2\) and \(1+\sqrt2\).
tight \(1+\sqrt{2w/(1+w)}\) vs \(1+\sqrt{2w/(1+w)}\) unknown distance
Line, weighted evacuation of two face-to-face robots
Face-to-face, the weighted cost is at most between \(6.60258\) and \(6.82843\), decreasing in \(w\), well below the ratio \(9\) of evacuating both robots; no face-to-face lower bound is known.
polynomial gap \(6.60258 \text{ to } 6.82843\) vs \(1+\sqrt{2w/(1+w)}\) unknown distance
Line, priority evacuation, queen and one wireless servant
A queen and one wireless servant bring the queen to the exit with ratio at most \(1+\sqrt2\), against \(3\) for evacuating both; no lower bound is known.
unknown \(1+\sqrt2\) vs —
Line, priority evacuation, queen and one face-to-face servant
Face-to-face, the queen reaches the exit with ratio at most \(2+\sqrt5 \approx 4.236\), far below \(9\); no lower bound is known.
unknown \(2+\sqrt5\) vs —
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 at the centroid
Two wireless robots at the centroid of the unit equilateral triangle evacuate in exactly \(3/2+\sqrt3/6 \approx 1.789\).
tight \(3/2+\sqrt3/6\) vs \(3/2+\sqrt3/6\) 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
Triangle, any number of wireless robots at the centroid
\(k\) wireless robots at the centroid evacuate in \(1+\sqrt3/3+3/k\), and no number of robots beats \(1+\sqrt3/3\), which 8 robots attain.
tight \(1+\sqrt3/3\ (k \ge 8)\) vs \(1+\sqrt3/3\) 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
Square, any number of wireless robots at the centre
\(k\) wireless robots at the centre of the unit square evacuate in \(3\sqrt2/2+4/k\), against the lower bound \(3\sqrt2/2\).
near-optimal \(3\sqrt2/2+4/k\) vs \(3\sqrt2/2\) 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 wireless robots starting on the boundary
From a point of the boundary at distance \(y\) from the nearest midpoint of a side, any number \(k \ge 2\) of wireless robots needs exactly \(3/2+y\): extra robots do not help.
tight \(3/2+y\) vs \(3/2+y\) 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
Square, two wireless robots starting on the boundary
From a point of the boundary at distance \(x\) from the nearest corner, two wireless robots need exactly \(1+x+\sqrt{1+(1-2x)^2}\); the best start is \(x = 1/2-1/\sqrt{12}\).
tight \(1+x+\sqrt{1+(1-2x)^2}\) vs \(1+x+\sqrt{1+(1-2x)^2}\) unknown exit

Open questions 26

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.

Disk, weighted evacuation of two wireless robots

  1. Close the gap for weighted evacuation of two wireless robots in the disk when \(w > 1\) 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.

Disk, \(k\) wireless robots, \(f\) Byzantine

  1. Lower bounds for evacuation of \(k\) robots with \(f\) Byzantine faults from the disk Behrouz et al. 2025.

Disk search, \(k\) wireless robots, one Byzantine

  1. Search of the disk with \(f \ge 2\) Byzantine robots: only the crash lower bound \(1+2\pi(f+1)/k\) and evacuation upper bounds are known Georgiou et al. 2023b Behrouz et al. 2025.

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).

Disk, \(k\) face-to-face robots, \(f\) Byzantine

  1. Lower bounds for face-to-face evacuation of the disk with Byzantine robots Behrouz et al. 2025.

Disk, \(k\) face-to-face robots, \(f\) crash faults

  1. Tight bounds for face-to-face evacuation of the disk with crash faults.

Line, weighted evacuation of two wireless robots

  1. Weighted evacuation with more than two robots Georgiou & Lucier 2023.

Line, weighted evacuation of two face-to-face robots

  1. Lower bounds for weighted evacuation of two face-to-face robots on the line Georgiou & Lucier 2023.

Line, priority evacuation, queen and one wireless servant

  1. A lower bound for priority evacuation of a queen and one wireless servant on the line.

Line, priority evacuation, queen and one face-to-face servant

  1. A lower bound for priority evacuation of a queen and one face-to-face servant on the line.

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. 2021d.

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

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

Triangle, any number of wireless robots at the centroid

  1. The optimal evacuation time of \(k = 3, \dots, 7\) wireless robots from the centroid of the triangle.

Square, any number of wireless robots at the centre

  1. The optimal evacuation time of \(k\) wireless robots from the centre of the square for fixed \(k\).

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. 2020b.
  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. 2020b.

Square, two wireless robots starting on the boundary

  1. Optimal evacuation of the square by \(k \ge 3\) wireless robots from a point of the boundary other than a corner.

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. 2020d Brandt et al. 2017 Disser & Schmitt 2019 and added faults Czyzowicz et al. 2017c, priority (one robot must leave) Czyzowicz et al. 2020b, asymmetric communication Georgiou et al. 2022, other domains Chuangpishit et al. 2020b 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. 2020b, in regular polygons with priority Georgiou et al. 2025b, 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. 2019 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. 2017c. 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. 2019d Group Search and Evacuation. Survey chapter (2019) on group search and evacuation: line search with crash and Byzantine faults, linear terrains, disk, triangle and square evacuation, faulty robots, several exits on a circle, and search-and-fetch. Read; it reports results of the papers placed in the settings.
  • Kranakis 2024 Invited Paper: A Survey of the Impact of Knowledge on the Competitive Ratio in Linear Search. Invited survey (SSS 2024) on how knowledge of the communication model, of faults and of the target's distance and speed changes the competitive ratio of linear group search and evacuation, with open problems. Read; no new results.
  • Czyzowicz et al. 2021f 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 Robot Evacuation on a Line Assisted by a Bike. Two robots and one bike on the line: walking speed \(1\), riding speed \(v > 1\), one rider at a time; three algorithms in the wireless model and three face-to-face (Theorems 1–6), and a lower bound for both models (Theorem 8). Read.
  • Pattanayak et al. 2020a Collaborative Evacuation of Mobile Robots. One-page extended abstract (ICDCN 2020) summarising two-robot disk evacuation with two exits at known arc distance, labelled or unlabelled, wireless or face-to-face, and carrying a crashed robot to the exit at reduced speed; it states no bounds and defers to the full papers. Read.
  • Chuangpishit et al. 2020a 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. Journal version of Chuangpishit et al. 2018b: two face-to-face robots in the disk; families of algorithms minimising the average evacuation time over the exit position subject to a bound on the worst-case time, for every feasible bound (Theorems 6, 7); conjectures that \(1+\pi\) is the optimal average. Read.
  • Liu et al. 2022 Online Algorithm for Evacuating Crashed Faulty Robots from A Square. Evacuation of \(k\) wireless robots from the centre of a unit square whose exit is at one of its corners, with crash faults that stop a robot, which a non-faulty robot must then carry to the exit at reduced speed; competitive ratios for \((k,f) = (2,1)\) (Theorem 1), \((3,1)\) and \((3,2)\) as functions of the slowdown. Read; neither the exit at a corner nor carrying is in the tree.
  • 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 agents from distinct nodes of a known graph to known exits, at most one agent per node: an optimal offline strategy in polynomial time (Theorem 3.1); on trees, with communication at distance two, no \((2-\Theta(1/k))\)-competitive online algorithm (Theorem 4.1) and an \(O(1)\)-competitive one (Theorem 4.2); NP-complete with agents restricted to subgraphs (Theorems 5.1, 5.2). A different sense of evacuation. Read.
  • Czyzowicz et al. 2019e Group search of the plane with faulty robots. Search for a point in the plane by \(k\) robots of speeds \(v_i\) with unit visibility, ending when the last reliable robot reaches the target: \(\pi d^2/(2V) + o(d^2)\) with \(V\) the sum of the speeds, asymptotically optimal (Theorem 1); asymptotically optimal bounds with \(f\) crash faults (Theorem 2, Lemma 6); with \(f\) Byzantine faults asymptotically optimal when wireless, and \((f+1)\pi d^2/(2k) + o(d^2)\) face-to-face for equal speeds and \(k \ge 2f+1\) (Theorem 3). Read.
  • Dobrev et al. 2020b Improved Lower Bounds for Shoreline Search. Search for a line (the shoreline) at known distance \(d\) in the plane (they write \(\delta\)): every algorithm needs time at least \(2d\) with three robots (Theorem 1) and \((1+\sqrt3+\pi/6)d \approx 3.2556d\) with two (Theorem 3), matching known upper bounds; the bound for three robots also holds for unknown \(d\). Search, not evacuation. Read.
  • Xu & Qin 2013 Strategies of Groups Evacuation from a Convex Region in the Plane. Groups of evacuees at one point of an unknown convex region of the plane, sharing information at all times, leave when all have reached the boundary: every strategy has ratio at least 3 (Theorem 1); \(k \ge 3\) groups in equally spaced directions achieve \(3/\cos(\pi/k)\) (Theorem 2); strategies on a grid network, ratio 3 with four groups (Theorem 6). Read.
  • Wei et al. 2014 On-Line Strategies for Evacuating from a Convex Region in the Plane. One group, without communication with others, escaping an unknown convex region of the plane: a \(19.64\)-competitive strategy along growing semicircles (Theorem 1) and a \(21\)-competitive strategy on a grid network (Theorem 2). Read.
  • Li & Xu 2017 Online Strategies for Evacuating from a Convex Region in the Plane. Escaping an unknown convex region once the boundary is known to all after the first evacuee reaches it: a 5-competitive strategy from one start (Theorem 2); from several starts, every strategy has ratio at least 3 (Theorem 1), and the strategy MES achieves 4 with two starts (Theorem 3) and \(2+\sqrt5\) in general (Theorem 4), improving \(4\sqrt2\) of Liu et al. 2015. Read.
  • Liu et al. 2015 Online Strategies for Evacuating from a Convex Region by Groups in the Plane. Groups that start at several points of an unknown convex region of the plane and share information: a \(4\sqrt2\)-competitive strategy for \(n \ge 3\) groups (Theorem 1). 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 convex region: a \(19.64\)-competitive strategy for one group (Theorem 1), a \(14.37\)-competitive strategy for two groups (Theorem 2), and \(21\)- and \(17\)-competitive strategies for one and two groups on a grid network (Theorems 3, 4). 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. 2025c Spirals and Beyond: Competitive Plane Search with Multi-Speed Agents. Plane search with agents of several speeds; a preprint, not read.
  • Coleman et al. 2026b Search and Rescue on the Plane. Search and rescue in the plane; a preprint, not read.
  • Georgiou et al. 2017 Searching with Advice: Robot Fence-Jumping. Fence-jumping: one robot searches the unit circle around its start for a treasure, knowing that an arc of length \(\beta\) at an unknown position (the fence) holds no treasure; it may cut across chords. The optimal trajectory with one jump (Theorem 1), the jumps of an optimal \(k\)-jump trajectory (Theorem 2) and a halving heuristic (Theorem 3). Read (arXiv v1, 2016).
  • Coleman et al. 2021 Message Delivery in the Plane by Robots with Different Speeds. Robots with different speeds, anywhere in the plane, relay a message face-to-face from a source to a destination. Offline: optimal for two robots via Apollonius circles and a \(\sqrt2\)-approximation for any number; online: an algorithm with competitive ratio below 2 for any number of robots, tight for that algorithm, and lower bounds of 1.0391 and 1.0405 for every online algorithm. Read (arXiv v1).
  • Nakamura et al. 2021 Evacuation from various types of finite two-dimensional square grid fields by a metamorphic robotic system. A different model, a metamorphic robotic system (connected oblivious modules on the square grid) that must leave a rectangular field through an exit: two modules with a common compass are necessary and sufficient (Theorem 1); without one, four modules from restricted initial shapes and seven from any (Theorems 2 and 3), and two when the system starts touching a wall (Theorem 4); also when the system can stop after leaving, mazes and convex fields. Read (arXiv v3).

All settings

The assumption tree (43 settings, 18 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 centroid1triangle, start on the boundary1unit square, start on the boundary1the 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.: robots that communicate only when they meet need time \(9d - o(d)\) to evacuate whatever their number, as much as a single robot in the cow-path problem Chrobak et al. 2015; Czyzowicz et al. cite this as showing that evacuating several uniform agents "is as hard as the cow-path problem" Czyzowicz et al. 2014. Polygons followed: equilateral triangles and squares, first with wireless robots Czyzowicz et al. 2015c and then face-to-face Chuangpishit et al. 2020b. Czyzowicz et al. let the robots start either at the centroid or at a point of the boundary, and the start changes the answer: from the boundary of a triangle three or more robots do no better than two, while from the centroid three robots beat two Czyzowicz et al. 2015c. A start on the boundary is therefore a separate domain value. 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. 2020b. 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; the robots start together at a given point of it, in its interior or on its boundary.
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.
1triangle, boundary start
A triangle (the equilateral triangle of unit side unless the setting names another family); the robots start together at a point of its boundary, either given (at distance \(y\) from the nearest midpoint of a side) or chosen by the algorithm, as the setting says; the exit is a point of the boundary.
1square, boundary start
The unit square; the robots start together at a given point of its boundary, at distance \(x \le 1/2\) from the nearest corner; 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. 2020d Brandt et al. 2017 Disser & Schmitt 2019. Specific small team sizes also appear in priority evacuation with one or two servants Czyzowicz et al. 2020a and with polygons, where triangles and squares were solved for \(k = 2, 3, 4\) Chuangpishit et al. 2020b.

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 exit1weighted: a weighted average of two arrival times1search: the exit is found and known to every non-faulty robot

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. 2020b. 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. Georgiou and Lucier weighted the arrival times of two robots on the line, a light one and a heavy one, and obtained priority evacuation on the line as the limit of large weight Georgiou & Lucier 2023. With faulty robots, search (the exit is found by a non-faulty robot and known to all non-faulty robots) is the first stage of evacuation: Georgiou et al. solved it on the circle with crash faults and with one Byzantine robot Georgiou et al. 2023b, and Behrouz et al. note that the evacuation time "is inherently greater than or equal to the time required to find the exit" Behrouz et al. 2025. Linear search uses the same two goals.

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.
1weighted
Two robots, a light one and a heavy one of known weight \(w \ge 1\), both must reach the exit and stay there; with arrival times \(t_1\) (light) and \(t_2\) (heavy), the cost is \((t_1 + w\,t_2)/(1+w)\).
1search
The task ends as soon as a non-faulty robot has reached the exit and every non-faulty robot knows its position for certain; the robots need not go 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. 2018a. 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.