Mobility Matters
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›nothing known, face-to-face, + no faults, + equal speeds

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

draft
Competitive ratio: polynomial gap

On \(m\) rays, knowing neither distance nor speed, two face-to-face robots capture a target moving away with a ratio polynomial in \(M = \max\{d, 1/(1-u)\}\), of degree about \(2^{m/2}\).

Assumed (added on the last edge are outlined)

+Number of robotstwo robots+Direction of the targetaway from the origin, speed \(u < 1\)+Faultsno faults+Speedsall robots have the same unit speed

Not assumed

Domain\(m\) rays from a common originKnowledge of the targetneither \(d\) nor \(u\) knownCommunicationface-to-face: robots exchange information only when they meetRandomnessdeterministic
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: nothing known
The robots know neither the initial distance \(d\) nor the speed \(u\).
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: 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
No matching lower bound.
lower boundnone known
introductory—
current best
\(1+O\bigl(M^{2^{(m+4)/2}}\log^2 M\log\log M\bigr)\ (m \text{ even})\)

Results, in order of publication

Jawhar & Kranakis 2026a preprint current best
Competitive ratio \(1+O\bigl(M^{2^{(m+4)/2}}\log^2 M\log\log M\bigr)\ (m \text{ even})\)

Introductory and best (Theorem 2.3), \(M = \max\{d, 1/(1-u)\}\); exponent \(2^{(m+5)/2}\) for odd \(m\). Preprint.

Open questions

None recorded for this variant.

Notes

Draft.

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.

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