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.
Triangle, two wireless robots starting on the boundary
verifiedTwo wireless robots starting on the boundary of a non-obtuse triangle evacuate in half the perimeter if they may choose their start, which is optimal.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Domain: triangle, boundary start
- A triangle (the equilateral triangle of unit side unless the setting names another family); the robots start together at a point of its boundary, either given (at distance \(y\) from the nearest midpoint of a side) or chosen by the algorithm, as the setting says; 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: 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
- Theorem 1
- non-obtuse triangle with sides \(a \ge b \ge c\)
- the algorithm chooses the starting edge and point
Results, in order of publication
Equilateral unit triangle, start on the boundary at distance \(y\) from the nearest midpoint of a side; tight (Theorem 1), and \(k \ge 3\) robots starting there do no better (Theorem 3).
Non-obtuse triangles (Theorem 1); separate tight or near-tight bounds when the adversary chooses the edge or the point.
Open questions
Face-to-face evacuation of general triangles, and wireless evacuation of obtuse triangles Georgiou & Jang 2026.
Notes
With \(k \ge 3\) robots starting at the same point of the boundary the bound \(3/2+y\) is still tight (Theorem 3 of Czyzowicz et al. 2015c); see the setting with any number of robots. Checked against the full texts of Czyzowicz et al. 2015c and Georgiou & Jang 2026.
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.