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.
Line, any number of face-to-face robots
verifiedOn the line, face-to-face robots evacuate with competitive ratio exactly 9: extra robots do not help.
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: 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: 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
- any number of robots of maximum speed at most 1
- full proof of \(9d-o(d)\)
- Theorem 3 and Corollary 1
- any number \(k \ge 2\) of unit-speed robots that communicate only when they meet
- the argument covers algorithms whose explored segment does not grow at rate exactly \(1/3\); Bampas et al. 2019b call it partial and complete it (Corollary 3.4)
Results, in order of publication
Section 2.2: two robots that cannot communicate wait half the time (equivalently, search at speed \(1/3\)); the finder goes back, meets the other and both return to the exit, in time \(9d\), "the same time as one robot". No lower bound is claimed for two robots.
Each robot runs the doubling strategy, the finder waiting at the exit, or two robots search in opposite directions at speed \(1/3\) and the finder catches the other (Section 2.2); with the lower bound of Theorem 3 this shows that \(9d\) is optimal for any number of robots.
Open questions
None recorded for this variant.
Notes
For two face-to-face robots the energy of group search can be traded against time; with maximum speed \(v\) and time at most \(9d/v\) the energy is about \(8.42588\,v^2 d\) (the paper writes \(b\) for \(v\); Theorem 16) Czyzowicz et al. 2019a. Checked against the full texts of Baeza-Yates & Schott 1995, Chrobak et al. 2015 and Bampas et al. 2019b.
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.