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›+ two robots›all robots, + two exits›+ wireless, + no faults, + equal speeds

Two robots, two exits, wireless

verified
Evacuation time: polynomial gap

With two exits and wireless communication, evacuation takes between \(2R\) and \((1+\pi/3)R \approx 2.047R\).

Assumed (added on the last edge are outlined)

+Domainunit disk, start at the centre+Number of robotstwo robots+Exitstwo exits at unknown positions+Communicationwireless: instant communication at any distance+Faultsno faults+Speedsall robots have the same unit speed

Not assumed

Goalevery robot must reach the 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: two robots
Two robots.
Goal: all robots
The task ends when the last robot reaches the exit.
Exits: two exits
Two exits at unknown points of the boundary; the task ends when every robot has reached one of them.
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
\((1+\pi/3)R\) versus \(2R\): a constant gap.
lower bound
\(2\) Pattanayak et al. 2018
bottleneckunknown exits
holds when
  • two robots start at the centre
  • radius \(R=1\)
introductory—
current best
\(1+\pi/3\)

Results, in order of publication

Pattanayak et al. 2018 current best
Evacuation time \(1+\pi/3\)

Introductory and current best.

Open questions

  1. Close the gap between \(2R\) and \((1+\pi/3)R\) for two wireless robots and two exits Pattanayak et al. 2018.

Notes

Bounds supplied by the catalogue owner (a co-author). When robots move only along a circle and the exits' arrangement is known, two robots starting at known distance \(L\) evacuate optimally in \(3/4+L/2\) (one exit, circle of unit length) Czyzowicz et al. 2016.

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

Two wireless robots, disk
Evacuation time \(1+2\pi/3+\sqrt{3}\)
Two robots, two exits, face-to-face
Evacuation time \(1+\pi/2\)

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.