The Homicidal Chauffeur Problem

In this Demonstration, a chauffeur driving a car with a minimum turning radius pursues a slower pedestrian with an unrestricted turning radius. The car is red and the evading pedestrian is blue. Click "setup" to set values for and the velocity ratio , and drag the locators to set the initial positions of the car and pedestrian and the orientation of the car. Then click "running" and move the locator to control the goal position of the pedestrian; after three seconds, the car attempts to run over the pedestrian. Avoid the car as long as possible!


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


The homicidal chauffeur is a pursuit-evasion game introduced in 1951 by Rufus Isaacs [1]. The object of the pursuer is to move within a capture radius of the evader in minimum time. The evader seeks to maximize this time. The pursuer moves forward at a constant rate, and can vary its angular velocity between a hard left or a hard right around a circle of radius . The minimum turn circles are drawn with dashed gray lines.
The optimal controls are not unique, and depend both on the speed ratio and minimum turning radius ratio between the pursuer and the evader. In 1971, Antony Merz identified 20 qualitatively different optimal solutions that depend on the values of those two parameters [2]; this Demonstration only implements one algorithm for the pursuer. The chauffeur steers toward the pedestrian if the latter cannot escape into the disks outlined by dashed gray lines; otherwise, it turns away from the pedestrian and increases separation until it determines the pedestrian can be captured. Furthermore, this Demonstration determines collision if the car boundary intersects the pedestrian, while the classic formulation defines capture if the evader is within the capture radius of the pursuer.
The car has forward velocity of units per second and is modeled as a Dubins car [3] with system equations:
where is chosen from the interval . This is often a reasonable model for a boat or car with no reverse gear or a fixed-wing airplane.
The pedestrian is a simple integrator with system equations:
and a maximum speed constraint on the control inputs,
The implemented algorithm is imperfect, so you can find regions of the parameter space where the evader can avoid collision forever.
The homicidal chauffeur model can be used to study surveillance where an aircraft must fly over evasive targets and is often used by researchers as an unclassified proxy for missile defense.
[1] R. Isaacs, Games of Pursuit, Scientific Report of the RAND Corporation, P-257, Santa Monica, 1951. (Jan 19, 2018) www.rand.org/pubs/papers/P257.html.
[2] A. W. Merz, "The Homicidal Chauffeur: A Differential Game," Ph.D. thesis, Department of Aeronautics and Astronautics, Stanford University, CA, 1971. (Jan 19, 2018) www.dtic.mil/dtic/tr/fulltext/u2/885270.pdf.
[3] L. E. Dubins, "On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents," American Journal of Mathematics, 79(3), 1957 pp. 497–516. doi:10.2307/2372560.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.

Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2018 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+