Details

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.

References

[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.