Home›Search in geometric domains›Search, evacuation and patrolling›Linear search (cow path)›Evacuation

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.

no assumptions›+ disk›+ two robots›all robots, one exit, + wireless, + no faults

Disk, two wireless robots of different speeds

verified

Evacuation time: polynomial gap

With speeds \(1\) and \(v \ge 1\), two wireless robots evacuate optimally for \(v \ge 2.75\); for smaller \(v\) the bounds are within a factor \(1.22\).

Assumed (added on the last edge are outlined)

+Domainunit disk, start at the centre+Number of robotstwo robots+Communicationwireless: instant communication at any distance+Faultsno faults

Not assumed

Goalevery robot must reach the exitExitsone exitSpeedsrobots may have different maximum speedsRandomnessdeterministic

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: 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: distinct speeds: Each robot \(i\) has its own maximum speed \(v_i\), known to all.
Randomness: deterministic: Trajectories are fixed functions of the information received.

What is known

Evacuation time · worst-case time until the last robot (or the queen) reaches the exit; unit disk, unit speed

polynomial gap

Tight for \(v \ge 2.75\); a constant factor below it.

lower bound

\(\text{matching for } v \ge 2.75\) Lamprou et al. 2020

bottleneckunknown exit

holds when

speeds \(1\) and \(v \ge 1\), both known
Section 5

introductory—

current best

\(\tfrac{1+2\arccos(-2/v)}{v}+\sqrt{1-4/v^2}\)

Lamprou et al. 2020

Results, in order of publication

Lamprou et al. 2020 current best

Evacuation time \(\tfrac{1+2\arccos(-2/v)}{v}+\sqrt{1-4/v^2}\)

Introductory and current best: optimal (Half-Chord) for \(v \ge 2.75\); for \(1 \le v < 2.75\) the best of three algorithms, within a factor \(1.22\) of the lower bound.

Open questions

Optimal evacuation for \(1 < v < 2.75\), for more than two robots, and face-to-face Lamprou et al. 2020.

Notes

Checked against the full text (arXiv 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.