---
tag: M0B618E2P6
kind: problem
name: Homicidal chauffeur problem
msc: [49N75, 91A24, 91A23]
uses: [THSHGNJNPS]
about: [THSHGNJNPS]
sources:
  - url: https://en.wikipedia.org/wiki/Homicidal_chauffeur_problem
same_as:
  wikidata: Q5890773
  wikipedia: Homicidal chauffeur problem
history:
  posed_by: "Rufus Isaacs"
  first_stated: "1951"
---

## Problem

Two players move in the plane.
The pursuer $P$ is a car: it moves with constant speed $w_1 > 0$ and has minimum turning radius $R > 0$.
Its position $(x_1, y_1)$ and heading $\theta$ obey
$$x_1' = w_1 \sin \theta, \qquad y_1' = w_1 \cos \theta, \qquad \theta' = \frac{w_1}{R} \phi, \qquad \phi(t) \in [-1, 1].$$
The evader $E$ moves with speed at most $w_2$, where $0 < w_2 < w_1$, in any direction: its position $(x_2, y_2)$ obeys $x_2' = w_2 \sin \psi$, $y_2' = w_2 \cos \psi$ with $\psi(t)$ free.
Let $\ell > 0$ be the capture radius; capture happens at the first time the distance between $P$ and $E$ is at most $\ell$.
The problem is a [[differential game|THSHGNJNPS]] between $P$ and $E$.
It asks for which parameters $w_1, w_2, R, \ell$ and initial positions the pursuer can force capture in finite time against every play of the evader.
It also asks for the optimal strategies when the pursuer minimises and the evader maximises the time to capture.

## Remarks

Isaacs used the problem as a model example in his theory of differential games.
By using coordinates attached to the car, the game reduces to a two-dimensional state, the position of the evader relative to the pursuer.
The evader is slower but more agile, so the car cannot simply drive at it: when it comes close, the evader can step aside inside the turning circle.
Isaacs found an explicit condition on the ratios $w_2 / w_1$ and $\ell / R$ under which capture is possible from every initial position.
The optimal strategies of the time-to-capture game turned out to involve several kinds of singular curves in the reduced state plane.

## Explanations

### L1 human

A driver in a car tries to run over a pedestrian in a large empty parking lot.
The car is faster, but it cannot turn sharply, while the pedestrian can change direction at will.
The question is when the driver can be sure to succeed, and how both should move.
It is a classical test problem for the theory of pursuit and evasion.