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.
Disk, weighted evacuation of two wireless robots
verifiedFor two wireless robots in the disk the weighted cost is exactly \(1+\pi\) when \(w = 1\); for larger \(w\) it lies between \(\max(1+\pi,\ 3.618+0.782\,w/(w+1))\) and \(1+d+\tfrac{2w}{w+1}\sin d\), tending to priority evacuation as \(w \to \infty\).
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Domain: disk
- The unit disk; robots start at its centre; the exit is a point of the boundary circle.
- Number of robots: two robots
- Two robots.
- Goal: weighted
- Two robots, a light one and a heavy one of known weight \(w \ge 1\), both must reach the exit and stay there; with arrival times \(t_1\) (light) and \(t_2\) (heavy), the cost is \((t_1 + w\,t_2)/(1+w)\).
- 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.
Statement for this variant
Two wireless robots with known identities start at the centre of the unit disk; the heavy robot's arrival time counts \(w \ge 1\) times the light one's, and the cost is \((t_1+w\,t_2)/(1+w)\) in the worst case over exit positions.
What is known
- Lemma 7 (arXiv numbering)
- the two robots together need time \(1+\pi\) to search the whole boundary
- Theorem 2 (arXiv numbering), about \(3.618+0.782\,w/(w+1)\); above \(1+\pi\) for large \(w\)
- linear-programming relaxation over exits at the vertices of a regular 7-gon, computer-assisted (Lemmas 4, 8)
Results, in order of publication
Introductory and current best (Lemmas 5, 6, arXiv numbering): the robots split the boundary in halves, \(d = \arccos(-(w+1)/(2w))\), while \(w \le 21.8861\); for larger \(w\) the heavy robot leaves the boundary early (a detour, with \(d\) the solution of a non-linear system), which as \(w \to \infty\) is the priority algorithm of cost \(\approx 4.81854\).
Open questions
Close the gap for weighted evacuation of two wireless robots in the disk when \(w > 1\) Georgiou & Wang 2025.
Notes
The paper writes the cost as \(w'x + y\) with \(w' \in [0,1]\); its \(w'\) is \(1/w\) here. For \(w \to \infty\) (their \(w'=0\)) the cost is priority evacuation, where the same framework gives the lower bound \(\approx 4.56798\) (Theorem 1); see the setting of a queen and one servant in the disk. Checked against the full text (arXiv 2406.19490v1; theorem numbers may differ in the journal version).
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.