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 robot on a line
standard settingverifiedDoubling the turning point each time gives competitive ratio 9, and nothing deterministic does better.
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: deterministic
- Trajectories are fixed functions of the information received.
What is known
- deterministic
- target at an unknown integer distance \(d\) on an unknown side
- ratio up to lower-order terms in \(d\)
Results, in order of publication
Introductory (in the competitive formulation) and current best: linear spiral search (turning points \(2^i\)) walks at most \(9d\) steps; there are algorithms with \(9d - \Theta((\log d)^i)\) steps for any \(i\).
Open questions
None recorded for this variant.
Notes
Checked against the full text of Baeza-Yates et al. 1993 (scan, Section 2.1). The bound is on the constant multiple of the distance; lower-order terms are not optimised.
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
Branches from here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.