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.
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Evacuation time
Number of robots + disk
—
Goal + two robots
—
Disk, two wireless robots of different speeds all robots, one exit, + wireless, + no faults
1 open · 1 results
polynomial gap
\(\tfrac{1+2\arccos(-2/v)}{v}+\sqrt{1-4/v^2}\) vs \(\text{matching for } v \ge 2.75\)
unknown exit
tight
\(1+2\pi/3+\sqrt{3}\) vs \(1+2\pi/3+\sqrt{3}\)
unknown exit
Communication all robots, + two exits
—
tight
\(1+\pi/2\) vs \(1+\pi/2\)
unknown exits
polynomial gap
\(1+\pi/3\) vs \(2\)
unknown exits
Communication + search-and-fetch
—
unknown
\(1+\pi-\alpha+4\sin(\alpha/2)\) vs —
polynomial gap
\(1+\pi-\alpha/2+3\sin(\alpha/2)\) vs \(1+\pi/3+4\sin(\alpha/2)\)
unknown exit
Two face-to-face robots, disk all robots, one exit, face-to-face, + no faults, + equal speeds
1 open · 4 results
polynomial gap
\(\approx 5.6234\) vs \(3+\pi/6+\sqrt{3}\)
unknown exit
Two robots with asymmetric communication, disk all robots, one exit, + sender/receiver, + no faults, + equal speeds
1 open · 1 results
polynomial gap
\(\pi+2\) vs \(> 1+2\pi/3+\sqrt3\)
one-way communication
Disk, priority evacuation, queen and one servant + priority (queen), + wireless, + no faults
1 open · 2 results
polynomial gap
\(\approx 4.81854\) vs \(\approx 4.56798\)
unknown exit
Goal + three robots
—
Faults all robots, + wireless
—
polynomial gap
\(< 4.22\) vs \(\approx 4.159\)
unknown exit
polynomial gap
\(\approx 6.309\) vs \(\approx 5.082\)
faulty reports
polynomial gap
\(\approx 6.921\) vs \(\approx 5.948\)
indistinguishable Byzantine agents
Three face-to-face robots, disk all robots, face-to-face, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(3+2\pi/3\) vs \(\approx 4.519\)
unknown exit
Disk, priority evacuation, queen and two servants + priority (queen), + wireless, + no faults
0 open · 1 results
polynomial gap
\(\approx 3.8327\) vs \(\approx 3.6307\)
unknown exit
Many wireless robots, disk any \(k\), all robots, + wireless, + no faults, + equal speeds
0 open · 1 results
near-optimal
\(3+\pi/k+O(k^{-4/3})\) vs \(3+\pi/k\)
unknown exit
Many face-to-face robots, disk any \(k\), all robots, face-to-face, + no faults, + equal speeds
0 open · 1 results
near-optimal
\(3+2\pi/k\) vs \(3+2\pi/k-O(k^{-2})\)
unknown exit
Priority evacuation (queen and servants), disk any \(k\), + priority (queen), + wireless, + no faults, + equal speeds
1 open · 1 results
polynomial gap
\(2+4(\sqrt2-1)\pi/\sigma\) vs \(1+\tfrac{2}{\sigma}\arccos\left(-\tfrac{2}{\sigma}\right)+\sqrt{1-\tfrac{4}{\sigma^2}}\)
unknown exit
Number of robots + line
—
Communication + two robots
—
tight
\(\tfrac{1+3v}{1-v}\ (v \le \tfrac13),\ 9v\ (v \ge \tfrac13)\) vs \(\text{matching}\)
unknown distance
tight
\(\tfrac{1+3v}{1-v}\ (v \le \sqrt{17}-4),\ \tfrac{2+v+\sqrt{v^2+8v}}{2}\ \text{above}\) vs \(\text{matching}\)
unknown distance
tight
\(3+2\sqrt2\) vs \(3+2\sqrt2\)
one-way communication
Faults any \(k\), + wireless
—
tight
\(3\) vs \(3\)
unknown distance
Line, \(2f+1\) wireless robots, \(f\) crash faults + crash faults, + equal speeds
1 open · 1 results
polynomial gap
\(\approx 7.437\) vs \(\approx 5.233\)
faulty reports
Line, any number of face-to-face robots any \(k\), face-to-face, + no faults, + equal speeds
0 open · 1 results
tight
\(9\) vs \(9\)
unknown distance
Number of robots + triangle
—
Communication + two robots
—
Two face-to-face robots, equilateral triangle face-to-face, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(2.3367\) vs \(1+2/\sqrt3\)
unknown exit
Triangle, two wireless robots starting on the boundary + wireless, + no faults, + equal speeds
1 open · 2 results
tight
\((a+b+c)/2\) vs \((a+b+c)/2\)
unknown exit
Triangle, any number of face-to-face robots any \(k\), + no faults, + equal speeds
0 open · 1 results
near-optimal
\(\sqrt3+3/k\) vs \(\sqrt3\)
unknown exit
Two face-to-face robots, square + square, + two robots, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(3.4645\) vs \(3.118\)
unknown exit
\(m\) rays, \(k = m\) wireless robots at the junction + rays, + wireless, + no faults, + equal speeds
2 open · 1 results
tight
\(3\) vs \(3\)
unknown exit
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.