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 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.

no assumptions›+ disk›any \(k\), + search, + wireless›+ crash faults, + equal speeds

Disk search, \(k\) wireless robots, \(f\) crash faults

verified

Evacuation time: tight

Search of the disk boundary with \(f\) crash faults takes exactly \(1+2\pi(f+1)/k\): every point must be seen by \(f+1\) robots.

Assumed (added on the last edge are outlined)

+Domainunit disk, start at the centre+Goalsearch: the exit is found and known to every non-faulty robot+Communicationwireless: instant communication at any distance+Faultsup to \(f\) crash-faulty robots (fail to report the target)+Speedsall robots have the same unit speed

Not assumed

Number of robotsany number \(k\) of robotsExitsone exitRandomnessdeterministic

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: any \(k\): \(k\ge1\) robots.
Goal: search: The task ends as soon as a non-faulty robot has reached the exit and every non-faulty robot knows its position for certain; the robots need not go to 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: crash faults: Up to \(f\) robots may fail to detect or to report the target when they pass over it.
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

\(k \ge f+1\) wireless robots start at the centre of the unit disk; up to \(f\) may crash. The task ends when a non-faulty robot has reached the exit and every non-faulty robot knows where it is.

What is known

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

tight

Exact.

lower bound

\(1+2\pi(f+1)/k\) Georgiou et al. 2023b

bottleneckfaulty reports

holds when

Theorem 1
every point of the boundary must be visited by \(f+1\) robots

introductory—

current best

\(1+2\pi(f+1)/k\)

Georgiou et al. 2023b

Results, in order of publication

Georgiou et al. 2023b current best

Evacuation time \(1+2\pi(f+1)/k\)

Introductory and current best (Theorem 2): robot \(i\) explores \(f+1\) consecutive arcs of length \(2\pi/k\) from the point \(2\pi i/k\).

Open questions

None recorded for this variant.

Notes

Checked against the full text.

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

Disk, \(k\) face-to-face robots, \(f\) crash faults

Evacuation time \(3+2\pi(f+1)/k\)

Disk search, \(k\) wireless robots, one Byzantine

Evacuation time \(1+4\pi/k\)

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.