Predator and Prey

Question

There are two players trapped in the unit square, $A$ and $B$. $A$ is chasing $B$ and wishes to catch her. Both players can move according to any strategy provided that neither exceeds unit speed. Both players have perfect knowledge of each other's position. For a given $r\ge 0$, if $|A-B|\le r$ then $A$ is said to have caught $B$. For large $r$ (say, $>2$) $A$ clearly has a winning strategy. What about for small $r$? What happens as $r\to 0$, does $A$ always have a winning strategy? What about for $r=0$? I've been thinking about this problem for a while but can't seem to make any major inroads into it.

Answer 1

The case where $r=0$ and the players are in the unit circle instead of a square is discussed in Bollabas' "The Lion and the Christian, and other Pursuit-Evasion games", where he first describes two incorrect arguments before giving a third argument (due to Besicovitch) that shows that $B$ can win. The common thread in the incorrect arguments is that they make assumptions about one player's strategy (like the "$A$ always moves towards $B$" and the "$B$ will never leave the border" assumptions in the existing answer here) that are plausible but turn out not to be correct. Here is a sketch of $B$'s winning strategy.

Suppose that player $A$ starts at the center of the circle and $B$ starts at a point $B_1$ some distance $x$ from $A$. Choose constants $t_1, t_2, t_3, \dots, t_n, \dots$ such that $\sum t_i=\infty$, but $\sum t_i^2 < 1-x^2$ (for example, by choosing the $t_i$ to be a tail of the harmonic series). Player $B$ then repeatedly follows the following procedure: If $O$ is the center of the circle and $B_i$ is his current position, then he chooses whichever direction orthogonal to $\overline{OB_i}$ moves him away from the current position of $A$, and moves in that direction for $t_i$ units of time.

The point is that the condition $\sum t_i^2 < 1-x^2$ guarantees that player $B$ never leaves the circle, so $B$ can keep on following this strategy indefinitely. Meanwhile, in any individual time step $B$ is moving away from $A$'s previous position, so $A$ can't catch them even if $A$ moves directly towards $B$'s future location.

This immediately carries over to the unit square (just inscribe a circle in the square and scale appropriately), but as far as I can tell doesn't say anything about the case $r>0$.

The case $r>0$ is analyzed in Alonso, Goldstein, and Reingold's "Lion and Man: Upper and Lower Bounds", where (Theorem 2) they give a strategy that lets player $A$ get within $r$ of player $B$ in time proportional to $\log(\frac{1}{r})$. I haven't looked at this proof in full detail though.

Answer 2

For $r>0$, Costello also linked Alonso, Goldstein, and Reingold's "Lion and Man: Upper and Lower Bounds" which gave a strategy for $A$ to win and proved it happened sometime in $O(R/S\log(R/r))$ where $R$ is the radius of the enclosure and $S$ is the maximum speed. $A$ has an easy winning strategy which wins in this same order of time.

Our strategy can not win for $r=0$. It is suggested by this upper bound, but actually it is a provable property of this strategy that if $A$ is moving at equal or less than speed of $B$, at the instance of contact $A$ is moving perfectly head on with $B$. This requires careful intervention by $B$ to happen.

$A$'s strategy is to always move towards the current position of $B$ at some sufficiently fast speed. Unfortunately rigorously analyzing these curves is generally very difficult. Our analysis uses easy upper bounds to avoid this, but we should still be very close to the least upper bound on $T$, the time for $A$ to catch $B$ using this strategy. Particularly for small $r$ where $\theta$ becomes small and our approximations begin increasing in accuracy by orders of magnitude.

Denote $s$ = speed of $A$, $S$ as the maximum speed, $2R$ as the length of the side of the square, $l_0>r$ as the initial distance, and $T$ as the time for $A$ to catch $B$ with this strategy. We will neglect the transient time for $A$ to fall behind the path of $B$ and assume $A$ starts from such a position. Sufficient $s/S > \sqrt{1-(r/R)^2}$, we will prove \begin{equation} T \leq S^{-1}R\sqrt{2}^3 \log \frac{l_0-R\sqrt{1-(s/S)^2}}{r-R\sqrt{1-(s/S)^2}} \end{equation}

$S$ is a matter of scaling and can be set to $1$. Suppose $s=1$. This forces $B$ to move at unit speed as otherwise $l$ will decrease at a steady rate and $B$ will be quickly caught. If $\theta$ is the angle between the velocities of $A$ and $B$, $dl/dt = -s + \cos\theta$.

\begin{equation} T \leq \int_{l_0}^r \frac{dl}{dl/dt} = \int_{l_0}^r \frac{dl}{-1+\cos\theta} \leq 2 \int_{r}^{l_0} \frac{dl}{\theta^2} \end{equation} where if there is a finite segment of path where $\theta = 0$, we slightly can bend the path of $B$ to change this without changing $T$ or the path of $A$ and otherwise remove singular values of $\theta = 0$. We must find $\theta$ as a function of $l$.

If $B$ plays optimally to maximize $A$, they must in general minimize $\theta$. Also if $B$ turns suddenly, $A$ will close a lot of distance. This implies the following statement, which may not have a simple proof.

The most optimal escape path for $B$ to take against this strategy of $A$ is for $B$ to move in the circle of maximum radius.

$B$ will move in a circle and $A$ will chase $B$ from within this circle. $A$ is moving on an expanding spiral which can be approximated by a slowly expanding circle. The important reason this model describes an upper bound is because the spiral is always intersecting this expanding circle from inwards outwards which makes $\theta$ larger than this model indicates.

Draw two circles $C_B$ and $C_A$ centered at the origin with respective radius $R_B > R_A$. $B$ is moving counterclockwise on $C_B$ and we assume its position is $(0,R_B)$. Extend the tangent $xx_0 + yy_0 = R_A^2$ of $C_A$ to $(0,R_B)$. Then $(x_0,y_0)$ is the position of $A$. Solving, $y_0 = R_A^2/R_B$ and $x_0 = R_A\sqrt{1-(R_A/R_B)^2}$. Using $\cos \theta = R_A/R_B$ \begin{equation} l = \sqrt{x_0^2 + (R_B - y_0)^2} = \sqrt{R_A^2 \sin^2\theta + R_B^2 \sin^4\theta} = \sqrt{2}R_B \sin^2 \theta \end{equation}

Because $\sin \theta \leq \theta$ it follows $T \leq R_B\sqrt{2}^3 \int_{r}^{l_0} \frac{dl}{l} = R_B\sqrt{2}^3 \log \frac{l_0}{r}$. Set $R_B = R$ and scale $s=1 \rightarrow s=S$, $T \rightarrow T/S$ and we've solved the problem when both are moving at equal speed $S$. \begin{equation} T \leq S^{-1}R\sqrt{2}^3\log \frac{l_0}{r} \end{equation}

But $A$ can catch $B$ when $s<1$. We'll recycle our upper bound for equal speeds to find an upper bound for this. The optimal escape path of $B$ is still thought to be a circle. Suppose $s<1$ and forget about $A$ catching $B$. As time goes to infinity $A$ will approach a circle of radius $sR_B$ inside of $C_B$.

Now suppose $A$ pursues a third object $B'$ moving on this limit circle, both moving at $s$, where $B'$ is pursuing $B$ which moves at speed $1$ on $C_B$. In this model $A$ is very nearly pursuing $B$, but because $A$ is not, this model is a larger upper bound on $T$. The tangent from this new circle to $C_B$ has length $R_B\sqrt{1 - s^2}$, and describes the position of $B'$.

Draw a circle of radius $r$ centered at $B$ and one of radius $r-R_B\sqrt{1-s^2}$ centered $B'$. This shows if $A$ comes within $r-R_B\sqrt{1-s^2}$ of this third object, they will be within $r$ of $B$. The initial distance between $A$ and $B'$ is not $l_0$, but by the triangle inequality is at least $l_0 - R_B\sqrt{1-s^2}$.

To reuse our first inequality for $A$ and $B$ to this model for $A$ and $B'$ set $S=s$. Take $R \rightarrow sR_B$. Replace $r$ by $r-R_B\sqrt{1-s^2}$ and $l_0$ by $l_0-R_B\sqrt{1-s^2}$. Set $R_B = R$. Lastly rescale the maximum speed by $S$ so $T \rightarrow T/S$ and $s\rightarrow s/S$. This returns the first equation.