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 measurescollapse
0d−dd/(1−u)−d/(1−u)−3dtime 0time 0.5time 1time 1.5time 2time 2.5time 3time 3.5time 4time 4.5time 5time 5.5time 6Start: d = 1, u = 1/3; the robot does not know the side (grey: the other possibility)Time d/(1−u) = 1.5: a target on this side would be here; it is not, so turnFinal: captured at time 6 = 4 × 1.5; ratio (3−u)/(1−u) = 4
Search for a target moving away, by a robot that knows the distance \(d\) and the speed \(u\) but not the side, Algorithm 1 of Coleman et al. 2022: walk for time \(d/(1-u)\) to one side, where a target on that side would be caught, and if it is not there turn and walk until reaching it. Here \(d = 1\) and \(u = 1/3\). The target (amber star) starts at \(-d\); the grey star shows where it would be on the other side. The robot turns at time \(1.5\), when it is \(2d/(1-u) = 3\) from the target, closes the gap at speed \(1 - u\) and captures it at time \(6\), four times the \(1.5\) that a robot knowing the side would need: the ratio is \((3-u)/(1-u) = 4\), which is optimal. The trace above the line shows the robot's two trips.

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.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

A dog has run off along a straight road and keeps trotting away at a steady pace, slower than its owner, who does not know which way it went. In this problem the owner is a robot, a point that moves at speed 1 and sees the target (the dog) only when it reaches it. The robot starts at the origin, the point \(0\) of an infinite line. The target starts at distance \(d \ge 1\) from the origin, on a side the robot does not know, and moves at constant speed \(u\) along its side. It moves either away from the origin, with \(u < 1\) (a faster target could never be caught), or toward it; the robot knows which. On \(m\) rays (half-lines that share the origin) the target moves along one of them. The target is captured when the robot stands on it. We measure the competitive ratio: the worst case, over all starting positions and speeds of the target, of the capture time divided by the time a robot that knew where the target started would need. In the standard version the target moves away and the robot knows \(u\) but not \(d\). The other versions change what the robot knows, or use two robots, and then both must reach the target.

1AlgorithmGo far enough on one side, then turn One robot, line, target moving away, \(d\) and \(u\) known → Coleman et al. 2022

Suppose the target moves away and the robot knows both \(d\) and \(u\); only the side is unknown.

  1. Walk to one side for time \(d/(1-u)\). If the target is on this side, the robot reaches it exactly then, because by that time the target has moved from \(d\) to \(d + u \cdot d/(1-u) = d/(1-u)\).
  2. If the target is not there, it is on the other side: turn and walk until reaching it.
Why it works and what it costs. When the robot turns, it stands at \(d/(1-u)\) on one side and the target at \(d/(1-u)\) on the other, so they are \(2d/(1-u)\) apart. The robot gains on the target at speed \(1-u\), which takes another \(2d/(1-u)^2\). A robot that knew the side would need \(d/(1-u)\), so the ratio is \(1 + 2/(1-u) = (3-u)/(1-u)\) Coleman et al. 2022. No strategy does better. To catch the target the robot must visit \(d/(1-u)\) or \(-d/(1-u)\), and the adversary, an opponent who knows the strategy, puts the target on the side that the robot reaches second. For a target that does not move (\(u = 0\)) the ratio is 3.

Why it matters. It is the baseline: every other version is measured by how much it costs not to know \(d\), \(u\) or both.

2AlgorithmZigzag with trips that grow faster One robot, line, target moving away, speed known → Alpern & Gal 2003

Now the robot knows \(u\) but not \(d\), the standard version. It zigzags: it walks out to distance \(1\) on one side and back to the origin, then out to distance \(a\) on the other side and back, then \(a^2\) on the first side, and so on, with the growth factor \(a = 2(1+u)/(1-u)\).

Why it works and what it costs. A target that moves away gains ground during every trip, so the trips must grow faster than for a target that stays put. With this growth factor the ratio is \((3+u)^2/(1-u)^2\), and no strategy does better. This is the result of Alpern and Gal, as reported by Coleman et al. 2022 (Theorem 6, Algorithm 3); the book was not read for this atlas, and the setting stays a draft. For a target that does not move (\(u = 0\)) the factor is \(2\): this is the doubling strategy of linear search, with ratio \(9\).

Why it matters. It shows how the doubling idea of linear search adapts to a target that runs away, and how quickly the price grows as \(u\) approaches 1.

3Lower boundWaiting is best when nothing is known One robot, line, target moving toward the origin, nothing known → Coleman et al. 2022

Suppose the target moves toward the origin and the robot knows neither \(d\) nor \(u\). The robot could simply wait at the origin. Any other strategy leaves the origin at some time, say it waits for time \(t\) and then walks a distance \(d'\) to the right. The adversary puts the target at \(-d\), with speed \(u = d/(t + d')\), so that it reaches the origin exactly when the robot is at \(d'\).

Why it holds. The two are then \(d'\) apart and approach each other at speed \(1+u\), so they meet after time \(d/u + d'/(1+u)\), which is more than the \(d/u\) it takes the target to reach the waiting robot. A robot that knew where the target started would walk to meet it, in time \(d/(1+u)\). The ratio is therefore at least \((d/u)/(d/(1+u)) = 1 + 1/u\), and waiting achieves exactly that Coleman et al. 2022. It grows without bound for slow targets. Knowing \(d\) helps a lot: going for time \(d\) on one side and then turning gives ratio \(3\) for every speed.

Why it matters. It shows that a moving target can make searching useless: what the robot knows decides between a constant ratio and an unbounded one.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Competitive ratio
Line, two face-to-face robots, away, \(u\) known
Knowing only the speed, two face-to-face robots capture a target moving away with ratio \((3+u)^2/(1-u)^2\), the single-robot value, using three turns.
polynomial gap \(\frac{(3+u)^2}{(1-u)^2}\) vs \(\frac{3-u}{1-u}\) unknown side
Line, a sender and a receiver, away, \(u\) known
A sender and a receiver that know the speed capture a target moving away with ratio \((\sqrt{u^2-2u+2}+1)/(\sqrt{u^2-2u+2}-1)\), which is \(3+2\sqrt2\) at \(u = 0\).
unknown \(\frac{\sqrt{u^2-2u+2}+1}{\sqrt{u^2-2u+2}-1}\) vs \(3+2\sqrt2\ (u = 0)\) one-way communication
Line, two face-to-face robots, away, \(d\) known
Knowing only the initial distance, two face-to-face robots capture a target moving away with ratio \(O(M^8\log^2 M)\), \(M = 1/(1-u)\).
polynomial gap \(O(M^8\log^2 M),\ M = \tfrac{1}{1-u}\) vs \(\frac{3-u}{1-u}\) unknown side
Line, a sender and a receiver, away, \(d\) known
Knowing only the initial distance, a sender and a receiver capture a target moving away with ratio \(1+O(M^{10/3}\log M)\), \(M = 1/(1-u)\).
polynomial gap \(1+O(M^{10/3}\log M),\ M = \tfrac{1}{1-u}\) vs \(1+\frac{2}{1-u}\) unknown side
Line, two face-to-face robots, away, \(d\) and \(u\) known
Robots that know \(d\) and \(u\) but not the side capture a target moving away with ratio exactly \((3-u)/(1-u)\).
tight \(\frac{3-u}{1-u}\) vs \(\frac{3-u}{1-u}\) unknown side
Line, two face-to-face robots, away, nothing known
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)\}\).
polynomial gap \(12M^7 + 192(\log\log M+3)M^{10}\log^2 M/d\) vs —
Line, a sender and a receiver, away, nothing known
Knowing neither distance nor speed, a sender and a receiver capture a target moving away with ratio \(1+O(M^{16/3}\log M(\log\log M)^{3/2})\), \(M = \max\{d, 1/(1-u)\}\).
polynomial gap \(1+O(M^{16/3}\log M\,(\log\log M)^{3/2})\) vs —
Line, two face-to-face robots, toward, \(u\) known
Knowing only the speed, two face-to-face robots capture a target moving toward the origin with ratio \((3-u)^2/(1+u)^2\) for \(u < 1/3\) and \(1+1/u\) otherwise.
polynomial gap \(\frac{(3-u)^2}{(1+u)^2}\ (u<\tfrac13),\ 1+\frac1u\ (u \ge \tfrac13)\) vs \(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\) unknown side
Line, a sender and a receiver, toward, \(u\) known
A sender and a receiver that know the speed capture a target moving toward the origin with ratio \((\sqrt{u^2+2u+2}+1)/(\sqrt{u^2+2u+2}-1)\) for \(u \le 1/3\) and \(1+1/u\) above.
unknown \(\frac{\sqrt{u^2+2u+2}+1}{\sqrt{u^2+2u+2}-1}\ (u \le \tfrac13),\ 1+\frac1u\ (u \ge \tfrac13)\) vs —
Line, two face-to-face robots, toward, \(d\) known
Knowing only the initial distance, two face-to-face robots capture a target moving toward the origin with ratio exactly 3.
tight \(3\) vs \(3\) unknown side
Line, a sender and a receiver, toward, \(d\) known
Knowing only the initial distance, a sender and a receiver capture a target moving toward the origin with ratio exactly 3.
tight \(3\) vs \(3\) unknown side
Line, two face-to-face robots, toward, \(d\) and \(u\) known
Robots that know \(d\) and \(u\) capture a target moving toward the origin with ratio \((3+u)/(1+u)\) when \(u \le 1\) and \(1+1/u\) when \(u \ge 1\), both optimal.
tight \(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\) vs \(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\) unknown side
Line, two face-to-face robots, toward, nothing known
Knowing neither distance nor speed, the best two face-to-face robots can do against a target moving toward the origin is to wait: ratio \(1+1/u\).
tight \(1+\frac1u\) vs \(1+\frac1u\) unknown side
Line, a sender and a receiver, toward, nothing known
Knowing neither distance nor speed, a sender and a receiver can do no better than waiting: ratio \(1+1/u\).
tight \(1+\frac1u\) vs \(1+\frac1u\) unknown side
One robot, line, target moving away, speed known standard
One robot that knows the speed \(u < 1\) of a target moving away from the origin, but not its distance, zigzags with turning distances that grow by the factor \(2(1+u)/(1-u)\); its ratio \((3+u)^2/(1-u)^2\) is optimal (Alpern and Gal, as reported).
tight \(\frac{(3+u)^2}{(1-u)^2}\) vs \(\frac{(3+u)^2}{(1-u)^2}\) unknown distance
One robot, line, target moving away, \(d\) and \(u\) known
A robot that knows \(d\) and \(u\) but not the side goes far enough to catch the target on one side and then turns: ratio exactly \((3-u)/(1-u)\).
tight \(\frac{3-u}{1-u}\) vs \(\frac{3-u}{1-u}\) unknown side
One robot, line, target moving away, \(d\) known
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})\).
near-optimal \(9\ (u \le \tfrac34),\ 56.18\,(1-u)^{-4+(\log_2\log_2\frac{1}{1-u})^{-2}}\ (u > \tfrac34)\) vs \(\text{not } O\big((1-u)^{-4+\varepsilon}\big)\) unknown speed
One robot, line, target moving away, nothing known
A 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})\).
polynomial gap \(1+\frac{8}{d}\ (E \le 4),\ 1+\frac{56.18\,E^{4-(\log_2\log_2 E)^{-2}}-1}{d}\ (E > 4)\) vs \(\text{not } O\big((1-u)^{-4+\varepsilon}\big)\) unknown speed
One robot, line, target moving toward the origin, \(d\) and \(u\) known
A robot that knows \(d\) and \(u\) goes for time \(d/(1+u)\) on one side and turns if needed, with ratio \((3+u)/(1+u)\) for \(u \le 1\); for \(u \ge 1\) waiting at the origin, with ratio \(1 + 1/u\), is optimal.
tight \(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\) vs \(\frac{3+u}{1+u}\ (u \le 1),\ 1+\frac{1}{u}\ (u \ge 1)\) unknown side
One robot, line, target moving toward the origin, speed known
A robot that knows the speed but not the distance of a target moving toward the origin should wait at the origin if \(u \ge 1/3\) and otherwise zigzag with turning distances that grow by the factor \(2(1-u)/(1+u)\); both are optimal.
tight \(1+\frac1u\ (u \ge \tfrac13),\ \frac{(3-u)^2}{(1+u)^2}\ (u < \tfrac13)\) vs \(1+\frac1u\ (u \ge \tfrac13),\ \frac{(3-u)^2}{(1+u)^2}\ (u < \tfrac13)\) unknown distance
One robot, line, target moving toward the origin, \(d\) known
A robot that knows the distance of a target moving toward the origin goes for time \(d\) on one side and turns: ratio exactly 3, for every speed.
tight \(3\) vs \(3\) unknown side
One robot, line, target moving toward the origin, nothing known
A robot that knows neither the distance nor the speed of a target moving toward the origin can do no better than wait for it: ratio exactly \(1 + 1/u\).
tight \(1+\frac1u\) vs \(1+\frac1u\) unknown side
\(m\) rays, two face-to-face robots, away, \(u\) known
On \(m\) rays, two face-to-face robots that know the speed capture a target moving away with a ratio that grows exponentially with \(m\).
polynomial gap \(1+\frac{(m+2)^{(m+2)/2}(1+u)^{m/2}}{m^{m/2}(1-u)^{(m+2)/2}}\ (m \text{ even})\) vs —
\(m\) rays, a sender and a receiver, away, \(u\) known
On \(m\) rays, a sender and a receiver that know the speed improve on face-to-face robots when \(m\) is odd.
polynomial gap \(\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})\) vs \(m\) unknown ray
\(m\) rays, two face-to-face robots, away, \(d\) known
On \(m\) rays, knowing only the initial distance, two face-to-face robots capture a target moving away with a ratio whose exponent in \(1/(1-u)\) is about \(2^{m/2}\).
polynomial gap \(1+O\bigl(M^{2^{(m+2)/2}}\log^2 M\bigr),\ M = \tfrac{1}{1-u}\ (m \text{ even})\) vs —
\(m\) rays, a sender and a receiver, away, \(d\) known
On \(m\) rays, knowing only the initial distance, a sender and a receiver lower the exponent of the face-to-face bound when \(m\) is odd.
polynomial gap \(O(M)+O\bigl(M^{2^{(m+1)/2}+1}\log^2 M\bigr),\ M = \tfrac{1}{1-u}\ (m \text{ odd})\) vs \(m\) unknown ray
\(m\) rays, two face-to-face robots, away, nothing known
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}\).
polynomial gap \(1+O\bigl(M^{2^{(m+4)/2}}\log^2 M\log\log M\bigr)\ (m \text{ even})\) vs —
\(m\) rays, a sender and a receiver, away, nothing known
On \(m\) rays, knowing neither distance nor speed, a sender and a receiver capture a target moving away with a ratio polynomial in \(M = \max\{d, 1/(1-u)\}\).
polynomial gap \(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})\) vs —

Open questions 6

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

  1. Is \((3+u)^2/(1-u)^2\) optimal for two face-to-face robots for every \(u \in (0,1)\), as it is for one robot?

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

  1. Is \((\sqrt{u^2-2u+2}+1)/(\sqrt{u^2-2u+2}-1)\) optimal for a sender and a receiver for \(u > 0\)?

One robot, line, target moving away, speed known

  1. Tight bounds when the robot does not know whether the target moves toward or away from the origin Coleman et al. 2022.

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

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

One robot, line, target moving away, nothing known

  1. Tight bounds when neither \(d\) nor \(u\) is known Coleman et al. 2026a; the upper bound grows with \(d\), the lower bounds do not.

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

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

What the community started looking at

A target that moves away from the origin at a speed the robot knows was treated by Alpern and Gal Alpern & Gal 2003, and a target performing a random walk on the integers by McCabe (1974), both as reported by Coleman et al. 2022. Coleman, Kranakis, Krizanc and Morales-Ponce posed the problem for one robot in all eight combinations of the target's direction (away or toward) and of what the robot knows about \(d\) and \(u\), with tight bounds whenever the target moves toward the origin or its speed is known Coleman et al. 2022. With Ivanov they settled the exponent for a target moving away at an unknown speed when \(d\) is known: the ratio is \((1-u)^{-4+o(1)}\) Coleman et al. 2026a. Jawhar and Kranakis extended it to two robots that communicate face-to-face Jawhar & Kranakis 2026b or as a sender and a receiver Jawhar & Kranakis 2025b, and to \(m\) rays Jawhar & Kranakis 2026a.

Generalisation of Linear search (cow path)

A static target is the case \(u = 0\); then capture by every robot is evacuation on the line or on \(m\) rays, and the ratio of Jawhar & Kranakis 2025b reduces to \(3+2\sqrt2\) Czyzowicz et al. 2021d. Algorithms carry over from linear search only for \(u = 0\); lower bounds for a static target hold for a target of speed \(u\) chosen by the adversary.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Kranakis 2024 Invited Paper: A Survey of the Impact of Knowledge on the Competitive Ratio in Linear Search. Invited survey (SSS 2024) on how knowledge of the communication model, of faults and of the target's distance and speed changes the competitive ratio of linear group search and evacuation, with open problems. Read; no new results.
  • Czyzowicz et al. 2020f Searching for a non-adversarial, uncooperative agent on a cycle. The target, a bus, moves at constant speed \(u\) (their \(s\)) along a cycle of length \(2\pi\), and robots of speed 1 search for it. One robot that knows \(u\) but not the direction needs exactly \(2\pi/u\) for \(u \ge 1\), \(4\pi/(u+1)\) for \(1/3 \le u \le 1\) and \(2\pi/(1-u)\) for \(u \le 1/3\) (Theorem 2); knowing neither, exactly \(2\pi(1 + 1/(u+1))\), so some speed forces \(4\pi - \varepsilon\) (Theorem 3). For \(k\) robots the bounds match when the direction is known (Theorem 4), when \(u\) is known and \(u \ge 1\) or \(k\) is even (Theorem 5), and up to the parity of \(k\) when nothing is known (Theorem 6). Read in full.

All settings

The assumption tree (28 settings, 15 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Competitive ratio); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Domain › Number of robots › Direction of the target › Knowledge of the target › Communication › Faults › Speeds › Randomness.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Domain

0\(m\) rays from a common origin1the line (two rays)

Moving targets were studied on the line Jawhar & Kranakis 2026b Jawhar & Kranakis 2025b; Jawhar and Kranakis call the \(m\)-ray star "a natural generalization of linear search to multiple directions" Jawhar & Kranakis 2026a.

Formal definitions
0\(m\) rays
\(m \ge 2\) half-lines sharing their endpoint, the origin; the target moves along one of them.
1line
The real line; the target moves along one side of the origin.

Number of robots

0any number \(k\) of robots1a single robot1two robots

One robot: Alpern and Gal for a target moving away at known speed (as reported by Coleman et al. 2022) and Coleman, Kranakis, Krizanc and Morales-Ponce for the other cases Coleman et al. 2022. Two robots that must both reach the target were studied by Jawhar and Kranakis Jawhar & Kranakis 2026b Jawhar & Kranakis 2025b.

Formal definitions
0any \(k\)
\(k \ge 1\) robots.
1one robot
A single robot.
1two robots
Two robots, both of which must reach the target.

Direction of the target

0the robots do not know the direction1away from the origin, speed \(u < 1\)1toward the origin, speed \(u \ge 0\)

Coleman, Kranakis, Krizanc and Morales-Ponce treat targets moving away from and toward the origin separately and assume that the robot knows which Coleman et al. 2022; the later papers read do the same. Tight bounds when the direction is unknown are left open in Coleman et al. 2022; no catalogued setting leaves it unknown.

Formal definitions
0direction unknown
The target moves toward or away from the origin, and the robots do not know which.
1away
The target moves away from the origin at constant speed \(u < 1\), and the robots know it.
1toward
The target moves toward the origin at constant speed \(u \ge 0\), and the robots know it.

Knowledge of the target

0neither \(d\) nor \(u\) known1\(u\) known, \(d\) unknown1\(d\) known, \(u\) unknown2\(d\) and \(u\) known

The four cases (their FullKnowledge, NoDistance, NoSpeed and NoKnowledge) are those of Coleman, Kranakis, Krizanc and Morales-Ponce Coleman et al. 2022, who extend the case of a known speed and an unknown distance treated by Alpern and Gal (as reported). Kranakis surveys how such knowledge changes the competitive ratio Kranakis 2024.

Formal definitions
0nothing known
The robots know neither the initial distance \(d\) nor the speed \(u\).
1speed known
The robots know \(u\) but not \(d\).
1distance known
The robots know \(d\) but not \(u\).
2both known
The robots know \(d\) and \(u\); only the side (ray) of the target is unknown.

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