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›+ line›+ two robots, + no faults

Two robots of different speeds, both must reach the target

verified
Competitive ratio: tight

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.

Assumed (added on the last edge are outlined)

+Domainthe line (two rays)+Number of robotstwo robots+Faultsno faults

Not assumed

Goalevacuation: every robot must reach the targetCommunicationface-to-face: robots exchange information only when they meetSpeedsrobots may have different maximum speedsRandomnessdeterministic
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: two robots
Two robots.
Goal: evacuation
The task ends when every robot has reached the target.
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: distinct speeds
Each robot \(i\) has its own maximum speed \(v_i\), known to all.
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
Optimal (face-to-face); the wireless case is optimal within the stated speed range.
lower bound
\(\text{matching}\) Bampas et al. 2019b
bottleneckunknown distance
holds when
  • face-to-face communication
  • all speed ratios
introductory
\(9\ (v \ge 1/3)\)
current best
\(\text{optimal for every speed ratio}\)

Results, in order of publication

Chrobak et al. 2015 introductory
Competitive ratio \(9\ (v \ge 1/3)\)

Face-to-face, speeds \(1\) and \(v \ge 1/3\): the slower robot follows its own doubling path at speed \(1/3\) and is fetched by the faster one (Theorem 4).

Bampas et al. 2019b current best
Competitive ratio \(\text{optimal for every speed ratio}\)

Wireless communication helps only while the faster robot is at most \(\sqrt{17}+4 \approx 8.12\) times faster.

Open questions

None recorded for this variant.

Notes

Introduced by Chrobak, Gąsieniec, Gorry and Martin, who also show that two unit-speed robots and further robots of speed at least \(1/5\) still finish in time \(9d\) (Section 3.2) Chrobak et al. 2015. Checked against the full texts of Chrobak et al. 2015 and Bampas et al. 2019b.

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