Math 2.0

Calculus of variations and optimal control; optimization Stochastic control and differential games Problem

Homicidal chauffeur problem

Builds on Differential game

Problem

Two players move in the plane. The pursuer PP is a car: it moves with constant speed w1>0w_1 > 0 and has minimum turning radius R>0R > 0. Its position (x1,y1)(x_1, y_1) and heading θ\theta obey x1′=w1sin⁡θ,y1′=w1cos⁡θ,θ′=w1Rϕ,ϕ(t)∈[−1,1].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 EE moves with speed at most w2w_2, where 0<w2<w10 < w_2 < w_1, in any direction: its position (x2,y2)(x_2, y_2) obeys x2′=w2sin⁡ψx_2' = w_2 \sin \psi, y2′=w2cos⁡ψy_2' = w_2 \cos \psi with ψ(t)\psi(t) free. Let ℓ>0\ell > 0 be the capture radius; capture happens at the first time the distance between PP and EE is at most ℓ\ell. The problem is a differential game between PP and EE. It asks for which parameters w1,w2,R,ℓ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 w2/w1w_2 / w_1 and ℓ/R\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.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Differential game concept
  2. Homicidal chauffeur problem problem

Further reading

  1. Web https://en.wikipedia.org/wiki/Homicidal_chauffeur_problem
About this page
TagM0B618E2P6
URIm2://M0B618E2P6
Kindproblem
WritingW0 stub
MSC49N75, 91A24, 91A23
StatusThis copy of the site has no build data. Run m2 status M0B618E2P6.
AboutDifferential game
UsesDifferential game
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.