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 measuresexpand

\(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.

no assumptions›+ disk›any \(k\), all robots, + wireless›Byzantine, + equal speeds

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

verified

Evacuation time: polynomial gap

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.

Assumed (added on the last edge are outlined)

+Domainunit disk, start at the centre+Communicationwireless: instant communication at any distance+Speedsall robots have the same unit speed

Not assumed

Number of robotsany number \(k\) of robotsGoalevery robot must reach the exitExitsone exitFaultsup to \(f\) Byzantine robots (may lie or stay silent)Randomnessdeterministic

Formal definitions of this setting

Domain: disk: The unit disk; robots start at its centre; the exit is a point of the boundary circle.
Number of robots: any \(k\): \(k\ge1\) robots.
Goal: all robots: The task ends when the last robot reaches the exit.
Exits: one exit: One exit, at an unknown point of the boundary.
Communication: wireless: Wireless: every robot can send messages to every other robot instantly at any distance.
Faults: Byzantine: Up to \(f\) robots may lie: stay silent when they find the target, or claim to have found it where it is not.
Speeds: equal speeds: All robots move at most at unit speed.
Randomness: deterministic: Trajectories are fixed functions of the information received.

Statement for this variant

\(k\) wireless robots start at the centre of the unit disk; up to \(f < k/2\) of them are Byzantine. Every non-faulty robot must reach the exit; messages carry the sender's identifier.

What is known

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

polynomial gap

For \(f=1\): \(3+4\pi/k\) against \(3+\pi/k\), an additive gap \(3\pi/k\); for general \(f\) the gap is not quantified.

lower bounds

\(1+2\pi(f+1)/k\) Georgiou et al. 2023b

bottleneckfaulty reports

holds when

Theorem 1: search bound with \(f\) crash-faulty robots, hence with Byzantine ones
every point of the boundary must be visited by \(f+1\) robots
evacuation takes at least as long as search

\(3+\pi/k\) Czyzowicz et al. 2014

bottleneckunknown exit

holds when

fault-free bound of \(k\) wireless robots (setting with many wireless robots in the disk)

introductory

\(3+4\pi/k\ (f=1)\)

Leonardos et al. 2023

current best

\(1+2\pi(f+1)/k+\max\{G_e(k^*),H_e(k^*)\}\)

Behrouz et al. 2025

Results, in order of publication

Leonardos et al. 2023 introductory

Evacuation time \(3+4\pi/k\ (f=1)\)

Theorem 3 (search algorithm of Georgiou et al. 2023b plus a diameter); \(3+6\pi/k\) for \(f=2\) when \(k \ge 9\), plus a term \(\delta(k) \le 0.5687\) when \(k < 9\) (Theorem 4).

Behrouz et al. 2025 current best

Evacuation time \(1+2\pi(f+1)/k+\max\{G_e(k^*),H_e(k^*)\}\)

Theorem 1, for every \(f < k/2\); \(G_e\) and \(H_e\) are the evacuation times of two groups of robots that settle disputed reports, defined in the theorem.

Open questions

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

Notes

Symmetric-persistent algorithms (all robots go to the boundary and explore in the same direction until told of the exit) need at least \(1+4\pi/k+2\sin(\pi/2-\pi/k)\) with one faulty robot (Theorem 1 of Leonardos et al. 2023), so \(3+4\pi/k\) is within \(O(1/k^2)\) of the best such algorithm. With \(k = 3\) see the setting with three robots, where \(\approx 6.921\) is known Czyzowicz et al. 2017c. Checked against the full texts of Leonardos et al. 2023, Behrouz et al. 2025 and Georgiou et al. 2023b.

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

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

Evacuation time \(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)\)

Lower bounds from stronger settings hold here

Many wireless robots, disk

Evacuation time \(3+\pi/k\)

Three wireless robots, one Byzantine

Evacuation time \(\approx 5.948\)

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

Evacuation time \(1+4\pi/k\)

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