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.
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
Disk, weighted evacuation of two wireless robots + weighted, + wireless, + no faults, + equal speeds
1 open · 1 results
polynomial gap
\(1+d+\tfrac{2w}{w+1}\sin d\) vs \(1+\pi\)
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 \(1+4\pi/3 \approx 5.188\)
faulty reports
polynomial gap
\(1+4\pi/3+\sqrt3 \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
Faults any \(k\), all robots, + wireless
—
near-optimal
\(3+\pi/k+O(k^{-4/3})\) vs \(3+\pi/k\)
unknown exit
polynomial gap
\(1+2\pi(f+1)/k+\max\{G_e(k^*),H_e(k^*)\}\) vs \(1+2\pi(f+1)/k\)
faulty reports
Faults any \(k\), + search, + wireless
—
Disk search, \(k\) wireless robots, \(f\) crash faults + crash faults, + equal speeds
0 open · 1 results
tight
\(1+2\pi(f+1)/k\) vs \(1+2\pi(f+1)/k\)
faulty reports
tight
\(1+4\pi/k\) vs \(1+4\pi/k\)
faulty reports
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
Disk, \(k\) face-to-face robots, \(f\) Byzantine any \(k\), all robots, face-to-face, Byzantine, + equal speeds
1 open · 2 results
polynomial gap
\(3+2\pi(f+1)/k+\max_{2\le j\le k} 2(j-1)\sin\bigl(\tfrac{f-j+2}{j-1}\cdot\tfrac{\pi}{k}\bigr)\) vs \(1+2\pi(f+1)/k\)
faulty reports
Disk, \(k\) face-to-face robots, \(f\) crash faults any \(k\), all robots, face-to-face, + crash faults, + equal speeds
1 open · 1 results
polynomial gap
\(3+2\pi(f+1)/k\) vs \(1+2\pi(f+1)/k\)
faulty reports
Number of robots + line
—
Goal + two robots
—
Communication + weighted
—
Line, weighted evacuation of two wireless robots + wireless, + no faults, + equal speeds
1 open · 1 results
tight
\(1+\sqrt{2w/(1+w)}\) vs \(1+\sqrt{2w/(1+w)}\)
unknown distance
Line, weighted evacuation of two face-to-face robots face-to-face, + no faults, + equal speeds
1 open · 1 results
polynomial gap
\(6.60258 \text{ to } 6.82843\) vs \(1+\sqrt{2w/(1+w)}\)
unknown distance
Communication + priority (queen)
—
Line, priority evacuation, queen and one wireless servant + wireless, + no faults, + equal speeds
1 open · 1 results
unknown
\(1+\sqrt2\) vs —
Line, priority evacuation, queen and one face-to-face servant face-to-face, + no faults, + equal speeds
1 open · 1 results
unknown
\(2+\sqrt5\) vs —
Line, two face-to-face robots of different speeds all robots, face-to-face, + no faults
0 open · 1 results
tight
\(\tfrac{1+3v}{1-v}\ (v \le \tfrac13),\ 9v\ (v \ge \tfrac13)\) vs \(\text{matching}\)
unknown distance
Line, two wireless robots of different speeds all robots, + wireless, + no faults
0 open · 1 results
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
Line, a sender and a receiver all robots, + sender/receiver, + no faults, + equal speeds
1 open · 1 results
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 · 2 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 at the centroid + wireless, + no faults, + equal speeds
0 open · 1 results
tight
\(3/2+\sqrt3/6\) vs \(3/2+\sqrt3/6\)
unknown exit
Triangle, any number of face-to-face robots any \(k\), face-to-face, + no faults, + equal speeds
0 open · 1 results
near-optimal
\(\sqrt3+3/k\) vs \(\sqrt3\)
unknown exit
Triangle, any number of wireless robots at the centroid any \(k\), + wireless, + no faults, + equal speeds
1 open · 2 results
tight
\(1+\sqrt3/3\ (k \ge 8)\) vs \(1+\sqrt3/3\)
unknown exit
Number of robots + square
—
polynomial gap
\(3.4645\) vs \(3.118\)
unknown exit
Square, any number of wireless robots at the centre any \(k\), + wireless, + no faults, + equal speeds
1 open · 1 results
near-optimal
\(3\sqrt2/2+4/k\) vs \(3\sqrt2/2\)
unknown exit
Number of robots + triangle, boundary start
—
Triangle, two wireless robots starting on the boundary + two robots, + 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 wireless robots starting on the boundary any \(k\), + wireless, + no faults, + equal speeds
0 open · 1 results
tight
\(3/2+y\) vs \(3/2+y\)
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
Square, two wireless robots starting on the boundary + square, boundary start, + two robots, + wireless, + no faults, + equal speeds
1 open · 1 results
tight
\(1+x+\sqrt{1+(1-2x)^2}\) vs \(1+x+\sqrt{1+(1-2x)^2}\)
unknown exit
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.