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 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.
Line, a sender and a receiver
verifiedA robot that can only send and one that can only receive wirelessly evacuate the line with ratio exactly \(3+2\sqrt2\).
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Domain: line
- 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.
- Number of robots: two robots
- Two 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: sender/receiver
- Sender/receiver: one robot can only transmit and the other only receive, instantly at any distance.
- Faults: no faults
- Every robot detects and reports the target.
- Speeds: equal speeds
- All robots move at most at unit speed.
- Randomness: deterministic
- Trajectories are fixed functions of the information received.
What is known
Results, in order of publication
Introductory and current best (Theorem 1).
Open questions
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.
Notes
If an extra vehicle (a bike) can carry a robot faster, sender/receiver evacuation on the line has piecewise bounds in the bike's speed Jawhar & Kranakis 2025. Checked against the full text of Czyzowicz et al. 2021.
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
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.