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 2018
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. 2016 current best
Competitive ratio \(2\rho^{\rho}/(\rho-1)^{\rho-1}+1\)

Introductory and current best (proportional schedules); optimality proved by Kupavskii & Welzl 2018.

Open questions

None recorded for this variant.

Notes

On \(m\) rays the same formula holds with \(\rho = m(f+1)/k\) Kupavskii & Welzl 2018.

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.