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›any \(k\), + search, + wireless›+ crash faults, + equal speeds

\(k\) robots on a line, \(f\) crash faults

verified
Competitive ratio: tight

With \(k\) wireless robots of which \(f\) may fail to report the target, the optimal ratio is known exactly.

Assumed (added on the last edge are outlined)

+Domainthe line (two rays)+Goalsearch: the first robot to reach the target ends the task+Communicationwireless: instant communication at any distance+Faultsup to \(f\) crash-faulty robots (fail to report the target)+Speedsall robots have the same unit speed

Not assumed

Number of robotsany number \(k\) of robotsRandomnessdeterministic
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: any \(k\)
\(k\ge1\) robots.
Goal: search
The task ends when the first robot reaches the target (and, with faults, the others can be sure of it).
Communication: wireless
Wireless: every robot can send messages to every other robot instantly at any distance.
Faults: crash faults
Up to \(f\) robots may fail to detect or to report the target when they pass over it.
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
Matching bounds.
lower bound
\(2\rho^{\rho}/(\rho-1)^{\rho-1}+1\) Kupavskii & Welzl 2021
bottleneckfaulty reports
holds when
  • \(\rho = 2(f+1)/k\), for \(k < 2(f+1)\)
  • ratio 1 if \(k \ge 2f+2\)
introductory—
current best
\(2\rho^{\rho}/(\rho-1)^{\rho-1}+1\)

Results, in order of publication

Czyzowicz et al. 2019c current best
Competitive ratio \(2\rho^{\rho}/(\rho-1)^{\rho-1}+1\)

Introductory and current best (proportional schedules, Theorem 1); the algorithm needs no communication; optimality proved by Kupavskii & Welzl 2021.

Open questions

None recorded for this variant.

Notes

On \(m\) rays the same formula holds with \(\rho = m(f+1)/k\) Kupavskii & Welzl 2021. Czyzowicz et al. write the ratio as \((\tfrac{4f+4}{k})^{(2f+2)/k}(\tfrac{4f+4}{k}-2)^{1-(2f+2)/k}+1\), the same expression; their own lower bound, which holds even with communication, is about \(3.76\) for \((k,f) = (3,1)\) (Theorem 2) and \(3 + 2\ln k/k - 2\ln\ln k/k\) asymptotically (Corollary 2), so for \(k = 2f+1\) the ratio tends to 3 Czyzowicz et al. 2019c. Checked against the full text of Czyzowicz et al. 2019c (PODC 2016 version).

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

\(k\) robots on a line, Byzantine faults
Competitive ratio \(\text{depends on } f/k\)

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.