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›+ triangle›+ two robots›face-to-face, + no faults, + equal speeds

Two face-to-face robots, equilateral triangle

verified

Evacuation time: polynomial gap

From the centroid of a unit equilateral triangle: between \(1+2/\sqrt3\) and \(2.3367\).

Assumed (added on the last edge are outlined)

+Domainunit equilateral triangle, start at the centroid+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: triangle: The equilateral triangle of unit side; robots start at its centroid; the exit is a point of the boundary.
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

Constant gap.

lower bound

\(1+2/\sqrt3\) Chuangpishit et al. 2020

bottleneckunknown exit

holds when

two robots, face-to-face, start at the centroid

introductory—

current best

\(2.3367\)

Chuangpishit et al. 2020

Results, in order of publication

Chuangpishit et al. 2020 current best

Evacuation time \(2.3367\)

For \(k\) robots: \(\sqrt3+3/k\) against \(\sqrt3\).

Open questions

None recorded for this variant.

Notes

Wireless evacuation of triangles and squares was introduced at ADHOC-NOW 2015 (not yet in the bibliography).

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

Triangle, any number of face-to-face robots

Evacuation time \(\sqrt3+3/k\)

Lower bounds from stronger settings hold here

Triangle, two wireless robots starting on the boundary

Evacuation time \((a+b+c)/2\)

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