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.
Disk, \(k\) face-to-face robots, \(f\) Byzantine
verifiedFace-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.
Assumed (added on the last edge are outlined)
Not assumed
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: face-to-face
- Face-to-face: two robots exchange information only when they are at the same point at the same time.
- 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\) robots start at the centre of the unit disk and exchange information only when they meet; up to \(f\) of them are Byzantine. Every non-faulty robot must reach the exit.
What is known
- 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
- wireless search bound; it holds face-to-face and for evacuation
- fault-free bound of \(k\) face-to-face robots (setting with many face-to-face robots in the disk)
Results, in order of publication
Theorem 6; \(3+6\pi/k+2\sin(2\pi/k)\) for \(f=2\) (Theorem 7).
Theorem 2, for every \(f\) (their \(k\) is \(j\) here, the number of conflicting reports); equals the bounds of Leonardos et al. 2023 for \(f = 1, 2\). Against the trivial algorithm (every robot walks the whole boundary, time \(1+2\pi\)): the trivial one is better when \(f \ge 0.3842\,k\) (Lemma 6), Theorem 2 is better when \(f \le \beta k\) with \(\beta < (\pi-1)/(2\pi) \approx 0.34\) and \(k\) large enough (Lemma 7).
Open questions
Lower bounds for face-to-face evacuation of the disk with Byzantine robots Behrouz et al. 2025.
Notes
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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.