Home›Search in geometric domains›Search, evacuation and patrolling›Linear search (cow path)

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.

no assumptions›\(m\) rays, + one robot, + search, + no faults, + equal speeds›+ randomized

One randomized robot on \(m\) rays

draft

Competitive ratio: tight

A randomized robot that visits the \(m\) rays in a random cyclic order, with turning points growing by a fixed factor from a random start, has the optimal expected ratio, about \(3.088\,m\) for large \(m\).

Assumed (added on the last edge are outlined)

+Number of robotsa single robot+Goalsearch: the first robot to reach the target ends the task+Faultsno faults+Speedsall robots have the same unit speed+Randomnessrandomized

Not assumed

Domain\(m\) rays from a common originCommunicationface-to-face: robots exchange information only when they meet

Formal definitions of this setting

Domain: \(m\) rays: \(m\ge2\) half-lines sharing their endpoint, the origin, where the robots start.
Number of robots: one robot: A single robot.
Goal: search: The task ends when the first robot reaches the target (and, with faults, the others can be sure of it).
Communication: face-to-face: Face-to-face: two robots exchange information only when they are at the same point at the same time.
Faults: no faults: Every robot detects and reports the target.
Speeds: equal speeds: All robots move at most at unit speed.
Randomness: randomized: Trajectories may depend on random choices; the measure is the expected competitive ratio against an oblivious adversary.

What is known

Competitive ratio · worst-case time divided by the distance to the target

tight

Exact, if the bound of Kao, Ma, Sipser and Yin for cyclic strategies (not read) is accepted; the step from cyclic to all strategies is in a preprint Ma & Yin 2026.

lower bound

\(\min_{\gamma>1}\Bigl(1+\frac{2}{m}\cdot\frac{1+\gamma+\dots+\gamma^{m-1}}{\ln\gamma}\Bigr)\) Ma & Yin 2026 preprint

bottleneckunknown distance

holds when

expected competitive ratio against an oblivious adversary
Yao's principle: the target lies on a ray chosen uniformly at random, at a distance \(x \ge 1\) with density \(\varepsilon x^{-(1+\varepsilon)}\), and \(\varepsilon \to 0\)
for strategies that visit the rays in a fixed cyclic order the bound is due to Kao, Ma, Sipser and Yin (Journal of Algorithms 29, 1998; not in the bibliography, not read), as reported by Kao et al. 1996 and Ma & Yin 2026
Ma & Yin 2026 show that some optimal deterministic strategy against this distribution is cyclic, so the bound holds for every randomized strategy

Theorem of Section 6 of Ma & Yin 2026 (with Propositions 1–3 and Appendix A), a preprint. It writes out the proof of Fact 4 of Kao, Ma, Sipser and Yin, which was left to an unpublished manuscript of 1994; the authors say they rebuilt it from hand-written notes. \(\gamma\) is the factor by which the turning distance grows from one trip to the next.

introductory—

current best

\(\min_{\gamma>1}\Bigl(1+\frac{2}{m}\cdot\frac{1+\gamma+\dots+\gamma^{m-1}}{\ln\gamma}\Bigr)\)

Kao et al. 1996

Results, in order of publication

Kao et al. 1996 current best

Competitive ratio \(\min_{\gamma>1}\Bigl(1+\frac{2}{m}\cdot\frac{1+\gamma+\dots+\gamma^{m-1}}{\ln\gamma}\Bigr)\)

Introductory and current best (SmartCow): a random permutation of the rays, a random initial distance, then the rays in cyclic order with turning distances growing by the factor \(\gamma\); ratio \(1+\frac{2}{m}\cdot\frac{1+\gamma+\dots+\gamma^{m-1}}{\ln\gamma}\) for every \(\gamma > 1\) (Theorem 3.1), minimised at the unique root of an equation in \(\gamma\) (Theorem 5.1), and about \(3.088\,m + o(m)\) (Theorem 6.1). For \(m = 2\) it is about \(4.5911\).

Open questions

None recorded for this variant.

Notes

Kao, Reif and Tate proved SmartCow optimal for \(m = 2\) (Theorem 4.1; see the setting on the line) and report that Kao, Ma, Sipser and Yin later proved it optimal for every \(m \ge 2\) Kao et al. 1996. According to Ma and Yin, that proof assumed that it suffices to consider strategies that visit the rays in a fixed cyclic order (Fact 4 of the 1998 paper) and left the argument to an unpublished manuscript Ma & Yin 2026. Their note supplies it for the distribution used in the lower bound: an optimal strategy exists (Appendix A), always extends a ray that has been explored least far (Proposition 1), extends it by more than a fixed factor (Proposition 2) and uses nondecreasing turning distances (Proposition 3), and can therefore be made cyclic. They leave open whether the same holds for the simpler truncated distribution of Schuierer (2003; not in the bibliography), whose proof of the lower bound assumes cyclic strategies; numerics for \(m = 3\) suggest it does Ma & Yin 2026. Both papers write \(w\) for \(m\). Checked against the full texts of Kao et al. 1996 (Theorems 3.1, 5.1, 6.1) and Ma & Yin 2026; the 1998 lower bound for cyclic strategies was not read.

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

One robot on \(m\) rays

Competitive ratio \(1+\frac{2m^m}{(m-1)^{m-1}}\)

Lower bounds from stronger settings hold here

One randomized robot on a line

Competitive ratio \(\approx 4.5911\)

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