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.
Two face-to-face robots, square
verifiedFrom the centroid of a unit square: between \(3.118\) and \(3.4645\).
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Domain: square
- The unit square; robots start at its centroid; the exit is a point of the boundary.
- 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: face-to-face
- Face-to-face: two robots exchange information only when they are at the same point at the same time.
- 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
Open questions
None recorded for this variant.
Notes
The lower bound is \(1+3\sqrt2/2 \approx 3.121\) in Theorem 4.1 (the abstract states 3.118). Three and four robots evacuate in about \(3.178\) and \(2.664\) Chuangpishit et al. 2020.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.