In
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, the homicidal chauffeur problem is a mathematical
pursuit problem which pits a hypothetical runner, who can only move slowly, but is highly maneuverable, against the driver of a motor vehicle, which is much faster but far less maneuverable, who is attempting to run him down. Both runner and driver are assumed to never tire. The question to be solved is: under what circumstances, and with what strategy, can the driver of the car guarantee that he can always catch the pedestrian, or the pedestrian guarantee that he can indefinitely elude the car?
The problem is often used as an
unclassified
Classified information is material that a government body deems to be sensitive information that must be protected. Access is restricted by law or regulation to particular groups of people with the necessary security clearance and need to know, ...
proxy for
missile defence
Missile defense is a system, weapon, or technology involved in the detection, tracking, interception, and also the destruction of attacking missiles. Conceived as a defense against nuclear-armed intercontinental ballistic missiles (ICBMs), ...
and other military targeting, allowing scientists to publish on it without security implications.{{citation needed, date=September 2020
The problem was proposed by
Rufus Isaacs in a 1951 report for the
RAND Corporation
The RAND Corporation (from the phrase "research and development") is an American nonprofit global policy think tank created in 1948 by Douglas Aircraft Company to offer research and analysis to the United States Armed Forces. It is financed ...
, and in the book ''Differential Games''.
[R. Isaacs, ''Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization'', John Wiley & Sons, New York (1965), PP 349–350.]
The homicidal chauffeur problem is a classic example of a
differential game In game theory, differential games are a group of problems related to the modeling and analysis of conflict in the context of a dynamical system. More specifically, a state variable or variables evolve over time according to a differential equatio ...
played in
continuous time
In mathematical dynamics, discrete time and continuous time are two alternative frameworks within which variables that evolve over time are modeled.
Discrete time
Discrete time views values of variables as occurring at distinct, separate "po ...
in a continuous
state space
A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.
For instance, the toy ...
. The
calculus of variations
The calculus of variations (or Variational Calculus) is a field of mathematical analysis that uses variations, which are small changes in functions
and functionals, to find maxima and minima of functionals: mappings from a set of functions t ...
and
level set
In mathematics, a level set of a real-valued function of real variables is a set where the function takes on a given constant value , that is:
: L_c(f) = \left\~,
When the number of independent variables is two, a level set is calle ...
methods can be used as a mathematical framework for investigating solutions of the problem. Although the problem is phrased as a recreational problem, it is an important
model problem for mathematics used in a number of real-world applications.
A discrete version of the problem was described by
Martin Gardner
Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writings of Lewis ...
(in his book ''Mathematical Carnival'', chapter 16), where a squad car of speed 2 chases a crook of speed 1 on a rectangular grid, where the squad car but not the crook is constrained not to make left-hand turns or U-turns.
See also
*
Variational calculus
The calculus of variations (or Variational Calculus) is a field of mathematical analysis that uses variations, which are small changes in functions
and functionals, to find maxima and minima of functionals: mappings from a set of functions t ...
*
Level-set method
Level-set methods (LSM) are a conceptual framework for using level sets as a tool for numerical analysis of surfaces and shapes. The advantage of the level-set model is that one can perform numerical computations involving curves and surfaces on a ...
*
Apollonius pursuit problem
* Conway's
Angel problem
The angel problem is a question in combinatorial game theory proposed by John Horton Conway. The game is commonly referred to as the Angels and Devils game.John H. Conway, The angel problem', in: Richard Nowakowski (editor) ''Games of No Chance'', ...
, another mathematical game which pits a powerful and maneuverable adversary against a highly resourceful but less powerful foe
*
Princess and Monster game
In game theory, a princess and monster game is a pursuit–evasion game played by two players in a region.
Formal Definition
In his book ''Differential Games'' (1965), Rufus Isaacs defined the game as:
This game remained a well-known open p ...
References
External links
History of the Homicidal Chauffeur Problem presentation at the Colloquium dedicated to the 60th anniversary of Prof. Pierre Bernhard.
Analytical study of a case of the homicidal chauffeur game problem*
ttp://demonstrations.wolfram.com/TheHomicidalChauffeurProblem/ The Homicidal Chauffeur Problem
Pursuit–evasion
Recreational mathematics
Calculus of variations
Game theory
Multivariable calculus