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.
One randomized robot on a line
verifiedRandomization lowers the optimal expected ratio on the line to about 4.5911.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Domain: line
- The real line, robots start at \(0\); the target is at an unknown \(x\) with \(|x|\ge1\).
- 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
- expected competitive ratio
- any randomized algorithm
- goal position fixed in advance (oblivious adversary)
- two paths (the line)
Results, in order of publication
Introductory and current best (SmartCow): randomness only in a random permutation of the paths and a random initial distance; ratio \(\approx 4.5911\) on the line, and about \(3.088\,m + o(m)\) on \(m\) rays.
Open questions
None recorded for this variant.
Notes
Checked against the full text of Kao et al. 1996. The ratio is the fixed point of an equation and is computed numerically (Theorem 5.1). Kao, Reif and Tate say Gal had obtained many of these results earlier in a game-theoretic setting, and that optimality for every number \(m \ge 2\) of rays was proved afterwards by Kao et al. (SODA 1994; not in the bibliography).
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
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.