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.
One robot, line, target moving away, nothing known
draftA robot that knows neither the distance nor the speed of a target moving away runs the algorithm for a known distance as if \(d = 1\): its ratio grows like \(d^3/(1-u)^4\) up to lower-order terms in the exponent, against \((3+u)^2/(1-u)^2\) and no \(O((1-u)^{-4+\varepsilon})\).
Assumed (added on the last edge are outlined)
Not assumed
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: 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
- for every constant \(\varepsilon > 0\)
- bound for a robot that knows \(d\) (Theorem 1), which holds a fortiori here (end of Section 3)
- bound for a robot that knows \(u\) (Remark 17 of Coleman et al. 2022)
- as reported; the book was not read
- bound for a robot that knows \(d\) and \(u\) (Theorem 1)
Results, in order of publication
Introductory (Algorithm 7, Theorem 16, Lemma 15), with \(M = \max\{d, 1/(1-u)\}\) and logarithms to base 2: in round \(i\) the robot guesses the speed \(1 - 2^{-2^i}\) and the distance \(2^{2^i}\).
Current best (Algorithm 2, Theorem 3), with \(E = d/(1-u)\): the robot runs the algorithm for a known distance with \(d = 1\); a target at distance \(d\) is caught no later than one at distance 1 with evasiveness \(E\) (Lemma 11). Since \(E \le M^2\), this improves on Coleman et al. 2022.
Open questions
Tight bounds when neither \(d\) nor \(u\) is known Coleman et al. 2026a; the upper bound grows with \(d\), the lower bounds do not.
Notes
Draft because the bound \((3+u)^2/(1-u)^2\) rests on the result of Alpern and Gal, which was not read. The other bounds were checked against the full texts of Coleman et al. 2022 (OPODIS 2022) and Coleman et al. 2026a (arXiv v2, Theorem 3; Theorem 5 of the JCSS version). The JCSS version states the Alpern–Gal bound as its Theorem 2 without a proof, so it does not settle this.
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
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.