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›Byzantine, + equal speeds

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

verified
Competitive ratio: polynomial gap

Byzantine robots may lie about the target; the optimal ratio is known only for some densities \(f/k\).

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+Speedsall robots have the same unit speed

Not assumed

Number of robotsany number \(k\) of robotsFaultsup to \(f\) Byzantine robots (may lie or stay silent)Randomnessdeterministic
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: Byzantine
Up to \(f\) robots may lie: stay silent when they find the target, or claim to have found it where it is not.
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
polynomial gap
For \(k=3\), \(f=1\) the upper bound is not matched.
lower bound
\(\approx 5.23\) Kupavskii & Welzl 2018
bottleneckindistinguishable Byzantine agents
holds when
introductory—
current best
\(\text{depends on } f/k\)

Results, in order of publication

Czyzowicz et al. 2021 current best
Competitive ratio \(\text{depends on } f/k\)

Introductory and current best; optimal for some densities of faulty robots.

Open questions

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

Notes

For three robots with one Byzantine robot the upper bound is about \(7.437\) Czyzowicz et al. 2021, improving \(8.653\) Sun et al. 2020.

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

No catalogued weaker setting.

Lower bounds from stronger settings hold here

\(k\) robots on a line, \(f\) crash faults
Competitive ratio \(2\rho^{\rho}/(\rho-1)^{\rho-1}+1\)

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