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›+ line›+ one robot›+ away›+ distance known, + no faults, + equal speeds

One robot, line, target moving away, \(d\) known

verified
Competitive ratio: near-optimal

A robot that knows the distance but not the speed of a target moving away guesses ever larger speeds, trip by trip: its ratio is \((1-u)^{-4+o(1)}\), and no strategy achieves \(O((1-u)^{-4+\varepsilon})\).

Assumed (added on the last edge are outlined)

+Domainthe line (two rays)+Number of robotsa single robot+Direction of the targetaway from the origin, speed \(u < 1\)+Knowledge of the target\(d\) known, \(u\) unknown+Faultsno faults+Speedsall robots have the same unit speed

Not assumed

Communicationface-to-face: robots exchange information only when they meetRandomnessdeterministic
Formal definitions of this setting
Domain: line
The real line; the target moves along one side of the origin.
Number of robots: one robot
A single robot.
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: distance known
The robots know \(d\) but not \(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
near-optimal
Both bounds have exponent 4: with \(M = 1/(1-u)\), \(O(M^{4-(\log_2\log_2 M)^{-2}})\) against no \(O(M^{4-\varepsilon})\). The remaining factor \(M^{(\log_2\log_2 M)^{-2}}\) grows more slowly than any power of \(M\) but faster than any power of \(\log M\); the authors call the result optimal up to lower-order terms in the exponent Coleman et al. 2026a.
lower bounds
\(\text{not } O\big((1-u)^{-4+\varepsilon}\big)\) Coleman et al. 2026a
bottleneckunknown speed
holds when
  • for every constant \(\varepsilon > 0\) (Theorem 1)
  • every strategy; zigzag strategies that return to the origin after each trip are no worse
  • adapts the argument of Beck and Newman for linear search
\(\frac{3-u}{1-u}\) Coleman et al. 2022
bottleneckunknown side
holds when
  • bound for a robot that knows \(d\) and \(u\) (Theorem 1), which holds a fortiori here (Remark 13)
introductory
\(5\ (u \le \tfrac12),\ 1+\frac{16\log^2\frac{1}{1-u}}{(1-u)^4}\ (u > \tfrac12)\)
current best
\(9\ (u \le \tfrac34),\ 56.18\,(1-u)^{-4+(\log_2\log_2\frac{1}{1-u})^{-2}}\ (u > \tfrac34)\)

Results, in order of publication

Coleman et al. 2022 introductory
Competitive ratio \(5\ (u \le \tfrac12),\ 1+\frac{16\log^2\frac{1}{1-u}}{(1-u)^4}\ (u > \tfrac12)\)

Introductory (Algorithm 5, Theorem 12, with Lemmas 10 and 11; logarithms to base 2): in round \(i\) the robot guesses the speed \(1 - 2^{-2^i}\), goes on alternate sides far enough to catch such a target, and returns to the origin. Better than Coleman et al. 2026a for \(u \le 1/2\) (5 against 9).

Coleman et al. 2026a current best
Competitive ratio \(9\ (u \le \tfrac34),\ 56.18\,(1-u)^{-4+(\log_2\log_2\frac{1}{1-u})^{-2}}\ (u > \tfrac34)\)

Current best for \(u > 1/2\) (Algorithm 1, Theorem 2): a zigzag strategy that guesses a larger speed on each trip, goes far enough to catch a target of that speed, and returns to the origin; the guesses grow faster than in Coleman et al. 2022. The paper writes \(v\) for the speed and \(u\) for the evasiveness \(1/(1-v)\).

Open questions

  1. Determine the lower-order terms in the exponent: the bounds differ by a factor \((1-u)^{-o(1)}\) Coleman et al. 2026a.

Notes

Without an upper bound on \(u\) below 1 the robot cannot use the algorithm for known \(u\); a known bound \(\hat u < 1\) on the speed would give \(1 + 2/(1-\hat u)\) (Section 4.1 of Coleman et al. 2022). Coleman et al. 2022 asked for tight bounds for an unknown speed; Coleman et al. 2026a settle the exponent. Checked against the full texts of Coleman et al. 2022 (OPODIS 2022) and Coleman et al. 2026a (arXiv v2, the full version; the JCSS version states the same bounds as Theorems 3 and 4).

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

One robot, line, target moving away, nothing known
Competitive ratio \(1+\frac{8}{d}\ (E \le 4),\ 1+\frac{56.18\,E^{4-(\log_2\log_2 E)^{-2}}-1}{d}\ (E > 4)\)

Lower bounds from stronger settings hold here

One robot, line, target moving away, \(d\) and \(u\) known
Competitive ratio \(\frac{3-u}{1-u}\)

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