Mobility Matters
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

One robot on \(m\) rays

verified
Competitive ratio: tight

On \(m\) rays the optimal deterministic ratio is \(1 + 2m^m/(m-1)^{m-1}\).

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

Not assumed

Domain\(m\) rays from a common originCommunicationface-to-face: robots exchange information only when they meetRandomnessdeterministic
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: deterministic
Trajectories are fixed functions of the information received.

What is known

Competitive ratio · worst-case time divided by the distance to the target
tight
Exact.
lower bound
\(1+\frac{2m^m}{(m-1)^{m-1}}\) Baeza-Yates et al. 1993
bottleneckunknown distance
holds when
  • deterministic
  • target at an unknown integer distance on one of \(m\) rays
  • ratio up to lower-order terms
  • also the special case \(k=1\), \(f=0\) of Kupavskii & Welzl 2018
Theorem 2.3 of Baeza-Yates et al. 1993.
introductory—
current best
\(1+\frac{2m^m}{(m-1)^{m-1}}\)

Results, in order of publication

Baeza-Yates et al. 1993 current best
Competitive ratio \(1+\frac{2m^m}{(m-1)^{m-1}}\)

Introductory and current best: generalized linear spiral search, turning points \((m/(m-1))^i\) and rays visited cyclically.

Open questions

None recorded for this variant.

Notes

Checked against the full text of Baeza-Yates et al. 1993 (scan, Section 2.3).

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

No catalogued weaker setting.

Lower bounds from stronger settings hold here

One robot on a line
Competitive ratio \(9\)

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