Home›Search in geometric domains›Search, evacuation and patrolling›Linear search (cow path)›Search for a moving target

Search for a moving target

A target starts at unknown distance \(d\) from the origin of a line (or of \(m\) rays) and moves at constant speed \(u\); how fast can robots capture it, depending on what they know about \(d\) and \(u\)?

Problem statement and measuresexpand

Robots of unit speed start at the origin of the line (or of \(m\) rays). The target starts at distance \(d \ge 1\) from the origin, on a side (ray) unknown to the robots, and moves along it at constant speed \(u\), either away from the origin (\(u < 1\), since a faster target can never be caught) or toward it (\(u \ge 0\)); the robots know which. The target cannot change its speed or direction. Depending on the setting the robots know \(d\), \(u\), both or neither. The target is captured when every robot stands on it. Time is the competitive ratio: the supremum, over the target's initial positions and speeds, of the capture time divided by the time the robots would need if they knew the target's initial position.

Measures: Competitive ratio, worst-case capture time divided by the capture time of robots that know the target's initial position.

no assumptions›\(m\) rays, + two robots, + away›+ speed known›+ sender/receiver, + no faults, + equal speeds

\(m\) rays, a sender and a receiver, away, \(u\) known

draft

Competitive ratio: polynomial gap

On \(m\) rays, a sender and a receiver that know the speed improve on face-to-face robots when \(m\) is odd.

Assumed (added on the last edge are outlined)

+Number of robotstwo robots+Direction of the targetaway from the origin, speed \(u < 1\)+Knowledge of the target\(u\) known, \(d\) unknown+Communicationasymmetric: senders and receivers+Faultsno faults+Speedsall robots have the same unit speed

Not assumed

Domain\(m\) rays from a common originRandomnessdeterministic

Formal definitions of this setting

Domain: \(m\) rays: \(m \ge 2\) half-lines sharing their endpoint, the origin; the target moves along one of them.
Number of robots: two robots: Two robots, both of which must reach the target.
Direction of the target: away: The target moves away from the origin at constant speed \(u < 1\), and the robots know it.
Knowledge of the target: speed known: The robots know \(u\) but not \(d\).
Communication: sender/receiver: Sender/receiver: one robot can only transmit and the other only receive, instantly at any distance.
Faults: no faults: Every robot detects and reports the target.
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 capture time divided by the capture time of robots that know the target's initial position

polynomial gap

For \(m = 3\), \(u = 0\): \(4+2\sqrt2 \approx 6.83\) against 10.

lower bounds

\(m\) Jawhar & Kranakis 2026a preprint

bottleneckunknown ray

holds when

Lemma 4.1
any deterministic algorithm with two unit-speed robots
the target on the last ray explored

\((m-1)+2+2\sqrt2\ (u = 0)\) Jawhar & Kranakis 2026a preprint

bottleneckone-way communication

holds when

Theorem 3.3
static target
adapts Lemmas 26 and 29 of Czyzowicz et al. 2021d; the proof is a sketch

introductory—

current best

\(\frac{2}{1-u}+\frac{(m-1)(1+u^2)}{(1+u)(1-u)}\Bigl(\frac{(m+1)(1+u)}{(m-1)(1-u)}\Bigr)^{(m+1)/2}\ (m \text{ odd})\)

Jawhar & Kranakis 2026a preprint

Results, in order of publication

Jawhar & Kranakis 2026a preprint current best

Competitive ratio \(\frac{2}{1-u}+\frac{(m-1)(1+u^2)}{(1+u)(1-u)}\Bigl(\frac{(m+1)(1+u)}{(m-1)(1-u)}\Bigr)^{(m+1)/2}\ (m \text{ odd})\)

Introductory and best for odd \(m\) (Algorithm 4, Theorem 3.2); 10 for \(m = 3\), \(u = 0\). For even \(m\) the paper uses the face-to-face algorithm. Preprint.

Open questions

For even \(m \ge 4\), can a sender and a receiver beat two face-to-face robots, as they do on the line?

Notes

Lemma 3.1 of Jawhar & Kranakis 2026a claims that for even \(m\) a sender and a receiver do no better than face-to-face robots; for \(m = 2\) and a static target this contradicts \(3+2\sqrt2\) Czyzowicz et al. 2021d against 9 Chrobak et al. 2015, and for moving targets on the line the sender/receiver bounds of Jawhar & Kranakis 2025b are smaller than the face-to-face ones of Jawhar & Kranakis 2026b. Even \(m\) is therefore open for a sender and a receiver.

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

\(m\) rays, two face-to-face robots, away, \(u\) known

Competitive ratio \(1+\frac{(m+2)^{(m+2)/2}(1+u)^{m/2}}{m^{m/2}(1-u)^{(m+2)/2}}\ (m \text{ even})\)

\(m\) rays, a sender and a receiver, away, nothing known

Competitive ratio \(O\bigl(\tfrac{1}{1-u}\bigr)+O\Bigl(\frac{\log\log M}{d(1-u)}\log^2 M\,M^{2^{(m+3)/2}}\Bigr)\ (m \text{ odd})\)

Lower bounds from stronger settings hold here

Line, a sender and a receiver, away, \(u\) known

Competitive ratio \(3+2\sqrt2\ (u = 0)\)

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