Home›Search in geometric domains›Search, evacuation and patrolling›Linear search (cow path)›Search for a moving target
Search for a moving target
A target starts at unknown distance \(d\) from the origin of a line (or of \(m\) rays) and moves at constant speed \(u\); how fast can robots capture it, depending on what they know about \(d\) and \(u\)?
Problem statement and measuresexpand
Robots of unit speed start at the origin of the line (or of \(m\) rays). The target starts at distance \(d \ge 1\) from the origin, on a side (ray) unknown to the robots, and moves along it at constant speed \(u\), either away from the origin (\(u < 1\), since a faster target can never be caught) or toward it (\(u \ge 0\)); the robots know which. The target cannot change its speed or direction. Depending on the setting the robots know \(d\), \(u\), both or neither. The target is captured when every robot stands on it. Time is the competitive ratio: the supremum, over the target's initial positions and speeds, of the capture time divided by the time the robots would need if they knew the target's initial position.
Measures: Competitive ratio, worst-case capture time divided by the capture time of robots that know the target's initial position.
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
Competitive ratio
Number of robots + line
—
Direction of the target + two robots
—
Knowledge of the target + away
—
Communication + speed known
—
Line, two face-to-face robots, away, \(u\) known face-to-face, + no faults, + equal speeds
1 open · 1 results
polynomial gap
\(\frac{(3+u)^2}{(1-u)^2}\) vs \(\frac{3-u}{1-u}\)
unknown side
Line, a sender and a receiver, away, \(u\) known + sender/receiver, + no faults, + equal speeds
1 open · 1 results
unknown
\(\frac{\sqrt{u^2-2u+2}+1}{\sqrt{u^2-2u+2}-1}\) vs \(3+2\sqrt2\ (u = 0)\)
one-way communication
Communication + distance known
—
Line, two face-to-face robots, away, \(d\) known face-to-face, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(O(M^8\log^2 M),\ M = \tfrac{1}{1-u}\) vs \(\frac{3-u}{1-u}\)
unknown side
Line, a sender and a receiver, away, \(d\) known + sender/receiver, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(1+O(M^{10/3}\log M),\ M = \tfrac{1}{1-u}\) vs \(1+\frac{2}{1-u}\)
unknown side
Line, two face-to-face robots, away, \(d\) and \(u\) known + both known, + no faults, + equal speeds
0 open · 1 results
tight
\(\frac{3-u}{1-u}\) vs \(\frac{3-u}{1-u}\)
unknown side
Line, two face-to-face robots, away, nothing known nothing known, face-to-face, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(12M^7 + 192(\log\log M+3)M^{10}\log^2 M/d\) vs —
Line, a sender and a receiver, away, nothing known nothing known, + sender/receiver, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(1+O(M^{16/3}\log M\,(\log\log M)^{3/2})\) vs —
Knowledge of the target + toward
—
Communication + speed known
—
Line, two face-to-face robots, toward, \(u\) known face-to-face, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(\frac{(3-u)^2}{(1+u)^2}\ (u<\tfrac13),\ 1+\frac1u\ (u \ge \tfrac13)\) vs \(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\)
unknown side
Line, a sender and a receiver, toward, \(u\) known + sender/receiver, + no faults, + equal speeds
0 open · 1 results
unknown
\(\frac{\sqrt{u^2+2u+2}+1}{\sqrt{u^2+2u+2}-1}\ (u \le \tfrac13),\ 1+\frac1u\ (u \ge \tfrac13)\) vs —
Communication + distance known
—
Line, two face-to-face robots, toward, \(d\) known face-to-face, + no faults, + equal speeds
0 open · 1 results
tight
\(3\) vs \(3\)
unknown side
Line, a sender and a receiver, toward, \(d\) known + sender/receiver, + no faults, + equal speeds
0 open · 1 results
tight
\(3\) vs \(3\)
unknown side
Line, two face-to-face robots, toward, \(d\) and \(u\) known + both known, + no faults, + equal speeds
0 open · 1 results
tight
\(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\) vs \(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\)
unknown side
Line, two face-to-face robots, toward, nothing known nothing known, face-to-face, + no faults, + equal speeds
0 open · 1 results
tight
\(1+\frac1u\) vs \(1+\frac1u\)
unknown side
Line, a sender and a receiver, toward, nothing known nothing known, + sender/receiver, + no faults, + equal speeds
0 open · 1 results
tight
\(1+\frac1u\) vs \(1+\frac1u\)
unknown side
Direction of the target + one robot
—
Knowledge of the target + away
—
One robot, line, target moving away, speed known + speed known, + no faults, + equal speeds
1 open · 1 results
tight
\(\frac{(3+u)^2}{(1-u)^2}\) vs \(\frac{(3+u)^2}{(1-u)^2}\)
unknown distance
One robot, line, target moving away, \(d\) and \(u\) known + both known, + no faults, + equal speeds
0 open · 1 results
tight
\(\frac{3-u}{1-u}\) vs \(\frac{3-u}{1-u}\)
unknown side
One robot, line, target moving away, \(d\) known + distance known, + no faults, + equal speeds
1 open · 2 results
near-optimal
\(9\ (u \le \tfrac34),\ 56.18\,(1-u)^{-4+(\log_2\log_2\frac{1}{1-u})^{-2}}\ (u > \tfrac34)\) vs \(\text{not } O\big((1-u)^{-4+\varepsilon}\big)\)
unknown speed
One robot, line, target moving away, nothing known nothing known, + no faults, + equal speeds
1 open · 2 results
polynomial gap
\(1+\frac{8}{d}\ (E \le 4),\ 1+\frac{56.18\,E^{4-(\log_2\log_2 E)^{-2}}-1}{d}\ (E > 4)\) vs \(\text{not } O\big((1-u)^{-4+\varepsilon}\big)\)
unknown speed
Knowledge of the target + toward
—
One robot, line, target moving toward the origin, \(d\) and \(u\) known + both known, + no faults, + equal speeds
0 open · 1 results
tight
\(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\) vs \(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\)
unknown side
One robot, line, target moving toward the origin, speed known + speed known, + no faults, + equal speeds
0 open · 1 results
tight
\(1+\frac1u\ (u \ge \tfrac13),\ \frac{(3-u)^2}{(1+u)^2}\ (u < \tfrac13)\) vs \(1+\frac1u\ (u \ge \tfrac13),\ \frac{(3-u)^2}{(1+u)^2}\ (u < \tfrac13)\)
unknown distance
One robot, line, target moving toward the origin, \(d\) known + distance known, + no faults, + equal speeds
0 open · 1 results
tight
\(3\) vs \(3\)
unknown side
One robot, line, target moving toward the origin, nothing known nothing known, + no faults, + equal speeds
0 open · 1 results
tight
\(1+\frac1u\) vs \(1+\frac1u\)
unknown side
Knowledge of the target \(m\) rays, + two robots, + away
—
Communication + speed known
—
\(m\) rays, two face-to-face robots, away, \(u\) known face-to-face, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(1+\frac{(m+2)^{(m+2)/2}(1+u)^{m/2}}{m^{m/2}(1-u)^{(m+2)/2}}\ (m \text{ even})\) vs —
\(m\) rays, a sender and a receiver, away, \(u\) known + sender/receiver, + no faults, + equal speeds
1 open · 1 results
polynomial gap
\(\frac{2}{1-u}+\frac{(m-1)(1+u^2)}{(1+u)(1-u)}\Bigl(\frac{(m+1)(1+u)}{(m-1)(1-u)}\Bigr)^{(m+1)/2}\ (m \text{ odd})\) vs \(m\)
unknown ray
Communication + distance known
—
\(m\) rays, two face-to-face robots, away, \(d\) known face-to-face, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(1+O\bigl(M^{2^{(m+2)/2}}\log^2 M\bigr),\ M = \tfrac{1}{1-u}\ (m \text{ even})\) vs —
\(m\) rays, a sender and a receiver, away, \(d\) known + sender/receiver, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(O(M)+O\bigl(M^{2^{(m+1)/2}+1}\log^2 M\bigr),\ M = \tfrac{1}{1-u}\ (m \text{ odd})\) vs \(m\)
unknown ray
\(m\) rays, two face-to-face robots, away, nothing known nothing known, face-to-face, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(1+O\bigl(M^{2^{(m+4)/2}}\log^2 M\log\log M\bigr)\ (m \text{ even})\) vs —
\(m\) rays, a sender and a receiver, away, nothing known nothing known, + sender/receiver, + no faults, + equal speeds
0 open · 1 results
polynomial gap
\(O\bigl(\tfrac{1}{1-u}\bigr)+O\Bigl(\frac{\log\log M}{d(1-u)}\log^2 M\,M^{2^{(m+3)/2}}\Bigr)\ (m \text{ odd})\) vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.