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, one exit, face-to-face, + no faults, + equal speeds

Two face-to-face robots, disk

verified
Evacuation time: polynomial gap

Face-to-face, two robots need between \(\approx 5.255\) and \(\approx 5.6234\); the gap has been open since 2019.

Assumed (added on the last edge are outlined)

+Domainunit disk, start at the centre+Number of robotstwo robots+Faultsno faults+Speedsall robots have the same unit speed

Not assumed

Goalevery robot must reach the exitExitsone exitCommunicationface-to-face: robots exchange information only when they meetRandomnessdeterministic
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: one exit
One exit, at an unknown point of the boundary.
Communication: face-to-face
Face-to-face: two robots exchange information only when they are at the same point at the same time.
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
\(\approx 5.6234\) versus \(\approx 5.255\): a constant gap of about 0.37.
lower bound
\(3+\pi/6+\sqrt{3}\) Czyzowicz et al. 2020
bottleneckunknown exit
holds when
introductory
\(\approx 5.74\)
current best
\(\approx 5.6234\)

Results, in order of publication

Czyzowicz et al. 2014 introductory
Evacuation time \(\approx 5.74\)
Czyzowicz et al. 2020 also
Evacuation time \(\approx 5.628\)
Brandt et al. 2017 also
Evacuation time \(\approx 5.625\)

Forced meetings exchange no useful information; simpler algorithm.

Disser & Schmitt 2019 current best
Evacuation time \(\approx 5.6234\)

A second detour through the interior.

Open questions

  1. Close the gap between \(3+\pi/6+\sqrt3 \approx 5.255\) and \(5.6234\) for two face-to-face robots.

Notes

The "second cut" of Disser & Schmitt 2019 is a second detour through the interior: an upper-bound technique. Measured in the average case over the exit position, the trade-off between average and worst-case time is mapped, and \(1+\pi\) is conjectured to be the optimal average for any number of robots Chuangpishit et al. 2019.

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 face-to-face robots, disk
Evacuation time \(3+2\pi/k\)

Lower bounds from stronger settings hold here

Two robots with asymmetric communication, disk
Evacuation time \(> 1+2\pi/3+\sqrt3\)
Two robots, two exits, face-to-face
Evacuation time \(1+\pi/2\)

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