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 at the centroid, or at a given point of the boundary, 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; in weighted evacuation of two robots, a weighted average of their arrival times; in search, until a non-faulty robot has reached the exit and every non-faulty robot knows where it is).

Measures: Evacuation time, worst-case time until the last robot (or the queen) reaches the exit, or the weighted average or search time where the goal says so; unit disk, unit speed.

no assumptions›+ square, boundary start, + two robots, + wireless, + no faults, + equal speeds

Square, two wireless robots starting on the boundary

verified

Evacuation time: tight

From a point of the boundary at distance \(x\) from the nearest corner, two wireless robots need exactly \(1+x+\sqrt{1+(1-2x)^2}\); the best start is \(x = 1/2-1/\sqrt{12}\).

Assumed (added on the last edge are outlined)

+Domainunit square, start on the boundary+Number of robotstwo robots+Communicationwireless: instant communication at any distance+Faultsno faults+Speedsall robots have the same unit speed

Not assumed

Goalevery robot must reach the exitExitsone exitRandomnessdeterministic

Formal definitions of this setting

Domain: square, boundary start: The unit square; the robots start together at a given point of its boundary, at distance \(x \le 1/2\) from the nearest corner; 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: 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, or the weighted average or search time where the goal says so; unit disk, unit speed

tight

Exact for every start.

lower bound

\(1+x+\sqrt{1+(1-2x)^2}\) Czyzowicz et al. 2015c

bottleneckunknown exit

holds when

Theorem 6
given start on the boundary, \(x \le 1/2\)

introductory—

current best

\(1+x+\sqrt{1+(1-2x)^2}\)

Czyzowicz et al. 2015c

Results, in order of publication

Czyzowicz et al. 2015c current best

Evacuation time \(1+x+\sqrt{1+(1-2x)^2}\)

Introductory and current best (Theorem 6): the robots walk the boundary in opposite directions and the finder calls the other.

Open questions

Optimal evacuation of the square by \(k \ge 3\) wireless robots from a point of the boundary other than a corner.

Notes

From a corner, any number of robots needs \(1+\sqrt2\), the two-robot time (Theorem 7); from the midpoint of a side three robots beat two (Theorem 8) Czyzowicz et al. 2015c. Checked against the full text.

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