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›+ search-and-fetch›+ wireless, + no faults

Disk, search-and-fetch, two wireless robots

verified
Evacuation time: unknown

Two wireless robots find a treasure on the boundary and bring it to an exit at known arc distance \(\alpha\) in \(1+\pi-\alpha+4\sin(\alpha/2)\).

Assumed (added on the last edge are outlined)

+Domainunit disk, start at the centre+Number of robotstwo robots+Goalsearch-and-fetch: a treasure must be brought to the exit+Communicationwireless: instant communication at any distance+Faultsno faults

Not assumed

Exitsone exitSpeedsrobots may have different maximum speedsRandomnessdeterministic
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: search-and-fetch
A treasure lies at an unknown point of the boundary, and the exit at a known arc distance \(\alpha\) from it; the task ends when some robot has carried the treasure to 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: distinct speeds
Each robot \(i\) has its own maximum speed \(v_i\), known to all.
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
unknown
No lower bound is given.
lower boundnone known
introductory—
current best
\(1+\pi-\alpha+4\sin(\alpha/2)\)

Results, in order of publication

Georgiou et al. 2019 current best
Evacuation time \(1+\pi-\alpha+4\sin(\alpha/2)\)

Introductory and current best (Theorem 2.1).

Open questions

  1. Lower bounds that separate wireless from face-to-face search-and-fetch Georgiou et al. 2019.

Notes

With one robot, the treasure-evacuation version is solved optimally when only a lower bound on the treasure–exit distance is known Georgiou et al. 2021 (abstract only). Checked against the full text of Georgiou 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

Disk, two wireless robots of different speeds
Evacuation time \(\tfrac{1+2\arccos(-2/v)}{v}+\sqrt{1-4/v^2}\)
Disk, search-and-fetch, two face-to-face robots
Evacuation time \(1+\pi-\alpha/2+3\sin(\alpha/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.