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

Square, any number of wireless robots at the centre

verified
Evacuation time: near-optimal

\(k\) wireless robots at the centre of the unit square evacuate in \(3\sqrt2/2+4/k\), against the lower bound \(3\sqrt2/2\).

Assumed (added on the last edge are outlined)

+Domainunit square, start at the centroid+Communicationwireless: instant communication at any distance+Faultsno faults+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: square
The unit square; robots start at its centroid; the exit is a point of the boundary.
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: 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, or the weighted average or search time where the goal says so; unit disk, unit speed
near-optimal
The gap \(4/k\) vanishes as \(k\) grows.
lower bound
\(3\sqrt2/2\) Czyzowicz et al. 2015c
bottleneckunknown exit
holds when
  • Theorem 9
  • every \(k\)
introductory—
current best
\(3\sqrt2/2+4/k\)

Results, in order of publication

Czyzowicz et al. 2015c current best
Evacuation time \(3\sqrt2/2+4/k\)

Introductory and current best (Theorem 9): the robots split the boundary into \(k\) pieces of length \(4/k\) and the finder calls the others.

Open questions

  1. The optimal evacuation time of \(k\) wireless robots from the centre of the square for fixed \(k\).

Notes

Checked against the full text.

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