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

Line, two face-to-face robots of different speeds

verified
Evacuation time: tight

With speeds \(1\) and \(v \le 1\), two face-to-face robots evacuate the line optimally: ratio \((1+3v)/(1-v)\) for \(v \le 1/3\) and \(9v\) above.

Assumed (added on the last edge are outlined)

+Domainthe infinite line+Number of robotstwo robots+Faultsno faults

Not assumed

Goalevery robot must reach the exitExitsone exitCommunicationface-to-face: robots exchange information only when they meetSpeedsrobots may have different maximum speedsRandomnessdeterministic
Formal definitions of this setting
Domain: line
The robots start at the origin of the real line; the exit is at an unknown point at distance at least \(1\); the measure is the competitive ratio, the evacuation time divided by that distance.
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: 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
tight
Exact for every \(v\).
lower bound
\(\text{matching}\) Bampas et al. 2019
bottleneckunknown distance
holds when
  • Theorem 3.11
introductory—
current best
\(\tfrac{1+3v}{1-v}\ (v \le \tfrac13),\ 9v\ (v \ge \tfrac13)\)

Results, in order of publication

Bampas et al. 2019 current best
Evacuation time \(\tfrac{1+3v}{1-v}\ (v \le \tfrac13),\ 9v\ (v \ge \tfrac13)\)

Introductory and current best (Theorem 3.11); both robots must reach the exit.

Open questions

None recorded for this variant.

Notes

Checked against the full text.

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

No catalogued weaker setting.

Lower bounds from stronger settings hold here

Line, two wireless robots of different speeds
Evacuation time \(\text{matching}\)
Line, a sender and a receiver
Evacuation time \(3+2\sqrt2\)

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