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 wireless robots
verifiedWith wireless communication, two or more robots evacuate the line with competitive ratio exactly 3.
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: wireless
- Wireless: every robot can send messages to every other robot 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
- Section 4 (a remark)
- consider the first time any robot reaches \(d\) or \(-d\) and put the exit at the other point
- any number of robots and any communication model
- Theorem 4.8 with equal speeds (\(v = 1\))
- two robots
Results, in order of publication
Section 2.2: with instantaneous communication, two robots search in opposite directions; "if both robots must reach the goal, the distance increases to \(4D\) and the time to 3 units" (their \(D\) is \(d\) here). Stated without a lower bound.
Algorithm \(B^*\) with \(v = 1\) (Corollary 4.3): two robots move in opposite directions at unit speed, the finder calls the other, which needs \(2d\) more. Further robots can move with one of the two (the catalogue's own observation, see notes). Czyzowicz et al. 2021d attribute the bound to Chrobak et al. 2015, which treats only robots that communicate when they meet; it is stated earlier by Baeza-Yates & Schott 1995.
Open questions
None recorded for this variant.
Notes
Checked against the full texts of Baeza-Yates & Schott 1995, Bampas et al. 2019b, Czyzowicz et al. 2021d and Chrobak et al. 2015. Own observation of this catalogue, not taken from a paper: with \(k > 2\) robots, let the extra robots move together with one of the two robots that walk apart at unit speed. Whichever of the two finds the exit, at distance \(d\) and time \(d\), every robot is then within \(2d\) of it and all arrive by time \(3d\); so ratio 3 holds for every \(k \ge 2\).
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.