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 measurescollapse
01−24−4dStart: robot at 0; the target is somewhereTurn at 1, back to 0Turn at −2: the target lies just beyondTurn at 4, back to 0Left again, up to −8: found on this tripFinal: found at time 16.5 = 6.6 d (worst case < 9d)
Linear search (cow path): a robot starts at the origin of a line and must reach a target at unknown distance \(d \ge 1\) on an unknown side. The animation runs the doubling strategy at unit speed, with turning points \(1, -2, 4, -8, \dots\) (trace above the line, one level per trip); the target, at \(d = 2.5\) just beyond the turning point \(-2\), is found on the next trip to the left at time \(16.5 = 6.6\,d\). In the worst case the strategy finds the target within time \(9d\), which is optimal Baeza-Yates et al. 1993.

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.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

A cow stands at a gate on an endless straight fence and knows that a hole is somewhere along the fence, but not on which side or how far. She walks at unit speed and sees the hole only when she reaches it. In linear search the cow is a robot, a point that moves at unit speed and sees the target only when it reaches it; the gate is the origin, the point \(0\) of an infinite line where the robot starts; and the hole is the target, at an unknown distance \(d \ge 1\) on an unknown side. We measure the competitive ratio: the worst case, over all target positions, of (time to find the target) divided by \(d\). A competitive ratio of 9 means the robot never walks more than about nine times the distance it would walk if it knew where the target was.

1AlgorithmDoubling: go 1 right, 2 left, 4 right, ... One robot on a line → Baeza-Yates et al. 1993

A strategy is the rule that fixes where the robot walks. The doubling strategy:

  1. Set \(i = 0\).
  2. Trip \(i\): walk distance \(2^i\) to one side (right when \(i\) is even, left when \(i\) is odd), checking for the target; the point where the robot turns back is a turning point.
  3. If the target is not there, walk back to the origin; this ends trip \(i\).
  4. Increase \(i\) by one and repeat.
Why it works and what it costs. The worst place for the target is just past a turning point, say at \(d = 2^i + \varepsilon\): the robot turned back there and finds it only on the next trip to that side, trip \(i+2\). By then it has walked \(2(1 + 2 + \dots + 2^{i+1}) = 2(2^{i+2}-1) < 8 \cdot 2^i < 8d\), plus the final \(d\), in total less than \(9d\). So the competitive ratio is at most 9, and Baeza-Yates et al. 1993 prove that this is optimal for deterministic strategies, those that toss no coins.

Why it matters. Doubling is the universal answer to "I do not know how far it is": it reappears in search on rays, in online algorithms, and in algorithms that do not know \(n\).

2Lower boundWhy no deterministic strategy beats 9 One robot on a line → Baeza-Yates et al. 1993

Any deterministic strategy can be described by its turning points \(x_1, x_2, x_3, \dots\), alternating sides, and one can show it is enough to consider growing ones. The adversary, an opponent who knows the strategy, puts the target just beyond \(x_i\), on that side. The robot finds it only after the next turning point on the other side, so its time is at least \(2(x_1 + \dots + x_{i+1}) + x_i\). Write \(S_j = x_1 + \dots + x_j\). A competitive ratio at most \(1 + 2c\) for every \(i\) needs \(S_{i+1} \le c\, x_i = c(S_i - S_{i-1})\).

Why it holds. Let \(q_i = S_{i+1}/S_i\), which is greater than 1. Dividing the inequality by \(S_i\) gives \(q_i \le c - c/q_{i-1}\). Because \(q + c/q \ge 2\sqrt c\) for every \(q > 0\), we get \(q_i \le q_{i-1} - (2\sqrt c - c)\). If \(c < 4\), the amount \(2\sqrt c - c\) is a fixed positive number, so \(q_i\) drops by at least that much at every step and eventually falls below 1, a contradiction. Hence \(c \ge 4\) and the competitive ratio is at least \(1 + 2 \cdot 4 = 9\), matching doubling (up to small terms in \(d\)) Baeza-Yates et al. 1993, Beck 1964.

Why it matters. It is the prototype adversary argument for online search: hide the target just past a turning point of the robot.

3AlgorithmRandomize the first side and the scale One randomized robot on a line → Kao et al. 1996

A randomized strategy tosses coins:

  1. Toss a coin to choose which side to try first.
  2. Choose a random distance for the first turning point.
  3. From then on, multiply the distance of the turning point by the same fixed factor on every trip, alternating sides.
Why it works and what it costs. The adversary, who must fix the target before the coins are tossed, no longer knows where the turning points are, so it cannot always place the target just past one. The expected competitive ratio drops to about \(4.5911\), and Kao et al. 1996 prove that no randomized strategy does better on the line. On \(m\) rays (half-lines that share the origin as their endpoint) the optimal deterministic competitive ratio is \(1 + 2m^m/(m-1)^{m-1}\) Baeza-Yates et al. 1993, which gives 9 for \(m = 2\).

Why it matters. It shows how randomness weakens an adversary that relies on knowing your strategy.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Competitive ratio
One robot on a line standard
Doubling the turning point each time gives competitive ratio 9, and nothing deterministic does better.
tight \(9\) vs \(9\) unknown distance
One randomized robot on a line
Randomization lowers the optimal expected ratio on the line to about 4.5911.
tight \(\approx 4.5911\) vs \(\approx 4.5911\) unknown distance
\(k\) robots on a line, \(f\) crash faults
With \(k\) wireless robots of which \(f\) may fail to report the target, the optimal ratio is known exactly.
tight \(2\rho^{\rho}/(\rho-1)^{\rho-1}+1\) vs \(2\rho^{\rho}/(\rho-1)^{\rho-1}+1\) faulty reports
\(k\) robots on a line, Byzantine faults
Byzantine robots may lie about the target; the optimal ratio is known only for some densities \(f/k\).
polynomial gap \(\text{depends on } f/k\) vs \(\approx 5.23\) indistinguishable Byzantine agents
Two robots of different speeds, both must reach the target
For two robots with different maximum speeds that must both reach the target, the optimal strategy is known for every speed ratio when they communicate by meeting.
tight \(\text{optimal for every speed ratio}\) vs \(\text{matching}\) unknown distance
One robot on \(m\) rays
On \(m\) rays the optimal deterministic ratio is \(1 + 2m^m/(m-1)^{m-1}\).
tight \(1+\frac{2m^m}{(m-1)^{m-1}}\) vs \(1+\frac{2m^m}{(m-1)^{m-1}}\) unknown distance

Open questions 1

\(k\) robots on a line, Byzantine faults

  1. Determine the optimal competitive ratio \(B(k,f)\) for Byzantine search on the line; already \(B(3,1)\) is open.

What the community started looking at

The first question was the optimal search plan for one searcher on a line Beck 1964, posed by Bellman. Computer scientists recast it as competitive analysis and found that doubling is optimal with ratio 9, and the exact ratio for \(m\) rays, where the turning distances grow by the factor \(m/(m-1)\) Baeza-Yates et al. 1993; randomization lowers the ratio on the line to about 4.5911 Kao et al. 1996. Recent work asks for group search with faulty robots Czyzowicz et al. 2016 Kupavskii & Welzl 2018 Czyzowicz et al. 2021 and robots of different speeds Bampas et al. 2019.

Derived problems

Evacuation: Evacuation is a form of search with an extra requirement: "optimality in evacuation is measured by the time it takes for the last robot to reach the exit, whereas in traditional search, optimality is measured by the time it takes the first robot to reach the exit" Czyzowicz et al. 2017. The introductory paper notes its similarity with the cow-path problem, and that evacuating uniform agents on a line "is as hard as the cow-path problem" Czyzowicz et al. 2014.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • Meeting at one place Rendezvous and gathering on graphs, gathering and convergence in the plane, and evacuation through an unknown exit all ask entities to end at one point. The papers give the same reasons for meeting, but each model makes a different part of it hard: symmetry and exploration on graphs, capability in the plane, information in continuous search.
  • From the cow path to evacuation The line of work from Bellman's and Beck's linear search problem to group search with faulty robots, evacuation of disks and polygons, priority evacuation, and patrolling by robots with distinct speeds.
  • When agents fail A node that destroys visitors, a robot that stops, an agent that lies, a searcher that misses the target: the papers motivate each fault by the hardware or the network, and each kind of fault changes a different measure, from team size to feasibility to an exact constant.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.

All settings

The assumption tree (6 settings, 3 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Competitive ratio); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Domain › Number of robots › Goal › Communication › Faults › Speeds › Randomness.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Domain

0\(m\) rays from a common origin1the line (two rays)

Bellman and Beck posed search for a target on the real line Bellman 1963 Beck 1964 (as reported by Czyzowicz et al. 2021). Baeza-Yates, Culberson and Rawlins treated the line as two rays and generalised to \(m\) rays from a common origin, with the optimal deterministic competitive ratio \(1 + 2m^m/(m-1)^{m-1}\), attained by turning at distances \((m/(m-1))^i\) while visiting the rays cyclically (Theorem 2.3 of Baeza-Yates et al. 1993). Searching on \(m\) concurrent rays has, in the words of Hammar et al. quoted by Brandt et al., "paradigmatic status" in competitive analysis Brandt et al. 2020. The ray star is level 0 here because it contains the line (\(m = 2\)) as a special case.

Formal definitions
0\(m\) rays
\(m\ge2\) half-lines sharing their endpoint, the origin, where the robots start.
1line
The real line, robots start at \(0\); the target is at an unknown \(x\) with \(|x|\ge1\).

Number of robots

0any number \(k\) of robots1a single robot1two robots

The classical problem has one searcher Beck 1964 Baeza-Yates et al. 1993. Chrobak et al. and Czyzowicz et al. proposed parallel versions with \(k\) robots on the line, where communication and faults make the team size matter Chrobak et al. 2015 Czyzowicz et al. 2016 (as reported by Kupavskii & Welzl 2018). With \(k\) fault-free robots, two of them already finish in time equal to the distance by going in opposite directions, so the multi-robot questions are interesting only with faults, with evacuation, or with unequal speeds Kupavskii & Welzl 2018 Bampas et al. 2019. Two robots are the smallest team in which speeds and communication interact, and Bampas et al. solve that case for every speed ratio Bampas et al. 2019.

Formal definitions
0any \(k\)
\(k\ge1\) robots.
1one robot
A single robot.
1two robots
Two robots.

Goal

0evacuation: every robot must reach the target1search: the first robot to reach the target ends the task

In search the time is the first arrival at the target, while in group evacuation it is the arrival of the last robot Bampas et al. 2019 Czyzowicz et al. 2021. Chrobak et al. showed that evacuating several uniform agents on the line is as hard as the cow-path problem (as reported by Czyzowicz et al. 2014) Chrobak et al. 2015. Bampas et al. compare search with rendezvous: in both the time is set by the last robot to arrive, but in search the meeting point is chosen by the adversary Bampas et al. 2019. With faults the two goals are closely linked: when \(k = 2f+1\) all agents may have to reach the target, and crash evacuation is then "a sub-problem of the more difficult byzantine search problem" Czyzowicz et al. 2021.

Formal definitions
0evacuation
The task ends when every robot has reached the target.
1search
The task ends when the first robot reaches the target (and, with faults, the others can be sure of it).

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