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.
Three wireless robots, one crash fault
verifiedIf one of three wireless robots may crash, evacuation takes between \(1+4\pi/3 \approx 5.188\) and \(\approx 6.309\).
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: three robots
- Three 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: crash faults
- Up to \(f\) robots may fail to detect or to report the target when they pass over it.
- Speeds: equal speeds
- All robots move at most at unit speed.
- Randomness: deterministic
- Trajectories are fixed functions of the information received.
What is known
- Theorem 3(a)
- three robots, at most one crash
- every boundary point must be visited by two robots, so some robot explores an arc of length at least \(4\pi/3\)
Results, in order of publication
Introductory and current best (Theorem 1; the best asymmetric-persistent algorithm, Lemma 3); time until the last non-faulty robot exits.
Open questions
Tight bounds for disk evacuation with one crash-faulty robot among three.
Notes
The best symmetric-persistent algorithm, with all three robots exploring in the same direction, takes \(1+4\pi/3+\sqrt3 \approx 6.921\) (Lemma 1) Czyzowicz et al. 2017c. The survey Czyzowicz et al. 2019d (Theorem 17) states a weaker crash lower bound of \(\approx 5.082\); the SIROCCO paper proves \(1+4\pi/3\). Checked against the full text of Czyzowicz et al. 2017c.
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
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.