Pursuit-Evasion Problem — Differential Games

The Oldest Game in the World

A hunter pursues a hare. A fox chases a rabbit. A military interceptor — pursues a target. The Pursuit-Evasion (PE) problem is one of the oldest applied mathematical problems. Isaacs gave it a rigorous mathematical form and discovered some stunning results: the optimal strategy is not always “fly straight at the opponent.” Sometimes you need to “lead” (anticipate). In complex cases, the strategy is determined by the topology of the space and a “barrier surface” separating capture and evasion zones.

Statement: The Simplest Variant

Two players in $\mathbb{R}^2$. Pursuer $P$ with position $x_P \in \mathbb{R}^2$, speed $|u| \leq \alpha$. Evader $E$ with position $x_E \in \mathbb{R}^2$, speed $|v| \leq \beta$.

Dynamics: $\dot{x}_P = u$, $\dot{x}_E = v$, $|u| \leq \alpha$, $|v| \leq \beta$.

Distance: $r(t) = |x_P(t) - x_E(t)|$.

Capture: $r(t) \leq l$ (capture radius). $P$ wants to achieve capture, $E$ wants to avoid it.

Three Main Cases

Case 1: $\alpha > \beta$ ($P$ is faster)

Capture is guaranteed for any $E$ strategy. $P$’s optimal strategy: Pure Pursuit (simply fly toward $E$) — ensures capture in finite time.

But it’s not optimal in terms of capture time! Optimal strategy: Constant Bearing Navigation (constant bearing course) — the “bearing” angle (angle to the target) remains constant. This is the strategy used by PN (Proportional Navigation) missiles.

Why is Pure Pursuit suboptimal? With "sharp" maneuvers by the target, $P$ “chases after” $E$, taking a longer path. Constant Bearing maintains the "intercept course" and reduces the distance faster.

Case 2: $\alpha = \beta$ (equal speeds)

Capture is possible if $E$ is “to the west” of $P$ or other specific initial conditions. The "classic cat-and-mouse game" — an ambiguous case.

Case 3: $\alpha < \beta$ ($E$ is faster)

Evasion is guaranteed. $E$’s optimal strategy: run directly away from $P$ (maximize distance).

Isaacs' Game “Homicidal Chauffeur”

A more interesting case: $P$ — a car with minimum turning radius $r$ (kinematically constrained), $E$ — a pedestrian. Sometimes limited maneuverability allows $E$ to escape even with lower speed!

$P$’s dynamics: $\dot{x}_P = \alpha \cos \theta$, $\dot{y}_P = \alpha \sin \theta$, $\dot{\theta} = u/r$ ($u \in [-1,1]$). $E$’s dynamics: $\dot{x}_E = v_1$, $\dot{y}_E = v_2$, $v_1^2 + v_2^2 \leq \beta^2$.

Barrier surface: Isaacs found the geometry of the region of initial conditions from which capture is guaranteed (Capture Zone) and from which evasion is guaranteed (Escape Zone). The boundary — the "barrier" — is a special solution of the HJI.

Lead Strategy (Proportional Navigation)

In real missile systems, Proportional Navigation (PN) is used:

$a_N = N \cdot |r| \cdot LOS_{rate}$

where $a_N$ is the missile’s lateral acceleration, $N$ is the navigation constant (usually 3-5), $LOS_{rate}$ is the angular rate of the Line of Sight.

Optimality: with linear dynamics and small angle, PN with $N \rightarrow \infty$ is optimal. With $N = 4-5$ it is practically close to optimal.

Why PN works: the aim of interception is a future point (“lead point”), not the target’s current position. PN automatically computes lead via angular rate.

Numerical Example: Optimal Capture Time

Parameters: $P$ and $E$ in $\mathbb{R}^2$, $\alpha = 2$, $\beta = 1$, $l = 0$ (point capture). Initial positions: $x_P = (0,0)$, $x_E = (10, 0)$.

Optimal strategy for $P$ (straight line chase): fly directly to $x_E(t)$. Since $\alpha = 2\beta$, $P$ catches up to $E$: $\frac{dr}{dt} = -(\alpha - \beta \cos \varphi)$, where $\varphi$ is the angle between $u$ and $v$.

For $E$’s optimal strategy (maximize $r$): $v$ is directed away from $P$, $\varphi = \pi$. Then $\frac{dr}{dt} = -(\alpha - \beta) = -1$. Capture time: $T = r_0 = 10$.

If $E$ maneuvers transversely: $P$ will still catch up ($\alpha > \beta$), only along a nonlinear trajectory. The time will be

gt;10$.

Applications in Autonomous Systems

Drones: the problem of safe collision avoidance is the reverse of the pursuit-evasion problem. Car $A$ wants to “escape” from $B$ to avoid collision. The optimal "evading" algorithm minimizes risk.

Multi-UAV capture: a group of pursuers versus one evader. Result: two coordinated pursuers are enough to guarantee capture even of a faster $E$ in a bounded space.

Robots: patrol-evader problem for autonomous security robots. The SafeRL library uses HJI to compute “safe” controls in real time.

Games with Obstacles

In real pursuit scenarios, space contains obstacles — walls, buildings, forbidden zones. This sharply complicates the problem: optimal trajectories skirt obstacles, and analytical solutions are rare. Numerical HJI solutions on a grid account for geometry via boundary conditions. Modern methods (Reach-avoid HJ analysis, Tomlin et al.) compute “safe sets” — states from which the pursuer guaranteedly reaches the target, avoiding collisions with obstacles.

Cooperative Pursuit

When several pursuers act together, the problem becomes fundamentally different: even slower pursuers can guarantee capture of a fast evader if their number is sufficient. Classic result: in the plane of 3 circles (the region inside a circle) one pursuer of any non-zero speed is enough for guaranteed capture (the lion and man theorem). On the half-plane with equal speeds, one is enough; on the plane, special strategies are needed. In pursuit games on graphs, the problem of determining the necessary number of pursuers is called the cop number and is related to the graph’s topology.

Games with Incomplete Information

In real problems, the pursuer does not always see the evader precisely. This leads to games with partial information: the pursuer has noisy measurements, must estimate the state and act simultaneously. This combines estimation theory (Kalman filter) and differential games theory. Sub-class: Search games — the pursuer does not see the target at all and must search for it by random or deterministic pattern.

Real-Time Implementation

For practical systems (autonomous cars, drones), the pursuit-evasion problem must be solved in real time:

Offline: precompute the value function $V$ on a grid of states
Online: look up the nearest value of $V$ and gradient, select optimal control
MPC (Model Predictive Control): at each step, solve the optimization problem over a short horizon

Applications

Military aviation: automatic interception systems (AIM-120 AMRAAM, Patriot)
Space: satellite maneuvers to avoid debris
Security: automatic perimeter guarding systems
Sport: analysis of optimal strategies in team games (hockey, football)
Biology: modeling predator hunts, evolution of “predator-prey” systems