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›+ disk›any \(k\), + priority (queen), + wireless, + no faults, + equal speeds

Priority evacuation (queen and servants), disk

verified
Evacuation time: polynomial gap

Only the queen must leave; \(\sigma\) servants (the paper writes \(n\); \(k = \sigma+1\) robots) help her find the exit.

Assumed (added on the last edge are outlined)

+Domainunit disk, start at the centre+Goalpriority: only the queen must reach the exit+Communicationwireless: instant communication at any distance+Faultsno faults+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: priority (queen)
One designated robot (the queen) must reach the exit; the others (servants) only help; the task ends when the queen exits.
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

Evacuation time · worst-case time until the last robot (or the queen) reaches the exit; unit disk, unit speed
polynomial gap
For large \(\sigma\) the gap between the closed-form bounds is about \((4\sqrt2-5)\pi/\sigma \approx 0.657\pi/\sigma\) Czyzowicz et al. 2018.
lower bound
\(1+\tfrac{2}{\sigma}\arccos\left(-\tfrac{2}{\sigma}\right)+\sqrt{1-\tfrac{4}{\sigma^2}}\) Czyzowicz et al. 2018
bottleneckunknown exit
holds when
  • \(\sigma \ge 4\) servants, wireless
  • all robots start at the centre of a unit disk
Theorem 5 of Czyzowicz et al. 2018; it exceeds \(2+\pi/\sigma+2/\sigma^2\), the leading terms of its expansion in \(1/\sigma\), which is the form stated in the abstract (e.g. \(2.913\) against \(2.910\) for \(\sigma = 4\)). The naive bound is \(2+\pi/(\sigma+1)\).
introductory—
current best
\(2+4(\sqrt2-1)\pi/\sigma\)
\(\sigma \ge 4\) servants

Results, in order of publication

Czyzowicz et al. 2018 current best
Evacuation time \(2+4(\sqrt2-1)\pi/\sigma\)
\(\sigma \ge 4\) servants

Introductory and current best (Theorem 1). The exact times of the algorithm are computed numerically, e.g. \(3.113\) for \(\sigma = 4\) against the closed-form upper bound \(3.301\).

Open questions

  1. Close the gap for priority evacuation; for one servant the bounds differ by about 0.25 (a 2024 preprint, not yet in the bibliography).

Notes

For a queen and three servants the bounds are about \(3.374\) and \(3.202\) Czyzowicz et al. 2018. The authors conjecture their algorithm for \(\sigma \ge 4\) servants is optimal Czyzowicz et al. 2018. The lower bound was checked against the full text (arXiv version) of Czyzowicz et al. 2018: Section 4 proves the exact expression and the abstract states its asymptotic form \(2+\pi/\sigma+2/\sigma^2\), so the two agree.

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

Many wireless robots, disk
Evacuation time \(3+\pi/k+O(k^{-4/3})\)

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.