Linear search (cow path)
A robot on a line (or on \(m\) rays from a point) must find a target at unknown distance; how small can the competitive ratio be?
Problem statement and measuresexpand
One or more unit-speed robots start at the origin of a line (or of \(m\) rays sharing an endpoint). A target lies at an unknown point at distance \(d \ge 1\). Time is the competitive ratio: the worst case, over target positions, of the time until the target is found (in search: by the first robot; in evacuation: by all robots) divided by \(d\).
Measures: Competitive ratio, worst-case time divided by the distance to the target.
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
—
tight
\(9\) vs \(9\)
unknown distance
tight
\(\approx 4.5911\) vs \(\approx 4.5911\)
unknown distance
Faults any \(k\), + search, + wireless
—
tight
\(2\rho^{\rho}/(\rho-1)^{\rho-1}+1\) vs \(2\rho^{\rho}/(\rho-1)^{\rho-1}+1\)
faulty reports
polynomial gap
\(\text{depends on } f/k\) vs \(\approx 5.23\)
indistinguishable Byzantine agents
Two robots of different speeds, both must reach the target + two robots, + no faults
0 open · 1 results
tight
\(\text{optimal for every speed ratio}\) vs \(\text{matching}\)
unknown distance
One robot on \(m\) rays \(m\) rays, + one robot, + search, + no faults, + equal speeds
0 open · 1 results
tight
\(1+\frac{2m^m}{(m-1)^{m-1}}\) vs \(1+\frac{2m^m}{(m-1)^{m-1}}\)
unknown distance
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.