{{Short description, Mathematical pursuit problem
In
game theory
Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...
, 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 proxy for
missile defense
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 weapon, nuclear-armed intercontinental ballistic mi ...
and other military targeting, allowing scientists to publish on it without security implications.
The problem was proposed by Rufus Isaacs in a 1951 report for the
RAND Corporation
The RAND Corporation, doing business as RAND, is an American nonprofit global policy think tank, research institute, and public sector consulting firm. RAND engages in research and development (R&D) in several fields and industries. Since the ...
, 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 dynamic games that unfold in continuous time, meaning players’ actions and outcomes evolve smoothly rather than in discrete steps, and for which the rate of change of each state variable—like position, spe ...
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 "poi ...
in a continuous
state space
In computer science, a state space is a discrete space representing 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 ...
. 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 Function (mathematics), functions
and functional (mathematics), functionals, to find maxima and minima of f ...
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 call ...
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 magic, scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writin ...
(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 ...
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