Mobility Matters
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›+ line›any \(k\), + wireless›+ crash faults, + equal speeds

Line, \(2f+1\) wireless robots, \(f\) crash faults

verified
Evacuation time: polynomial gap

With a near majority of faulty robots, evacuation on the line takes ratio about \(7.437\) for \((k,f) = (3,1)\), tending to \(4+2\sqrt2\); the lower bounds come from search.

Assumed (added on the last edge are outlined)

+Domainthe infinite line+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 robotsGoalevery robot must reach the exitExitsone exitRandomnessdeterministic
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: 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 = 2f+1\) robots, of which up to \(f\) may fail to report the exit; every non-faulty robot must reach it.

What is known

Evacuation time · worst-case time until the last robot (or the queen) reaches the exit; unit disk, unit speed
polynomial gap
Constant gap against the search lower bounds.
lower bound
\(\approx 5.233\) Kupavskii & Welzl 2018
bottleneckfaulty reports
holds when
  • \((k,f) = (3,1)\)
  • inherited from search with crash faults
introductory—
current best
\(\approx 7.437\)

Results, in order of publication

Czyzowicz et al. 2021 current best
Evacuation time \(\approx 7.437\)

Introductory and current best for \((3,1)\); \(7.254\) for \((5,2)\) and \((7,3)\), \(7.147\) for \((9,4)\), tending to \(4+2\sqrt2\) (Theorems 2.2, 3.1, 3.2).

Open questions

  1. Tight bounds for evacuation with \(k = 2f+1\) crash or Byzantine robots Czyzowicz et al. 2021.

Notes

When every attempt to turn fails with known probability \(\beta < 1/2\) (the paper's \(p\)), two wireless robots achieve ratio \(3+4\sqrt{\beta(1-\beta)}+\varepsilon\) Georgiou et al. 2024. Checked against the full text of Czyzowicz et al. 2021.

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

No catalogued weaker setting.

Lower bounds from stronger settings hold here

Line, any number of wireless robots
Evacuation time \(3\)

Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.