Homicidal chauffeur problem
Encyclopedia
In game theory
, 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 homicidal chauffeur problem is a classic example of a differential game
played in continuous time in a continuous state space
. The calculus of variations
and level set
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
(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.
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, the homicidal chauffeur problem is a mathematical pursuit problem
Pursuit-evasion
Pursuit-evasion is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically...
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 homicidal chauffeur problem is a classic example of a differential game
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. The problem usually consists of two actors, a pursuer and an evader, with conflicting goals...
played in continuous time in a continuous state space
State space
In the theory of discrete dynamical systems, a state space is a directed graph where each possible state of a dynamical system is represented by a vertex, and there is a directed edge from a to b if and only if ƒ = b where the function f defines the dynamical system.State spaces are...
. The calculus of variations
Calculus of variations
Calculus of variations is a field of mathematics that deals with extremizing functionals, as opposed to ordinary calculus which deals with functions. A functional is usually a mapping from a set of functions to the real numbers. Functionals are often formed as definite integrals involving unknown...
and level set
Level set
In mathematics, a level set of a real-valued function f of n variables is a set of the formthat is, a set where the function takes on a given constant value c....
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
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
(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
- Level set methodLevel set methodThe level set method is a numerical technique for tracking interfaces and shapes. The advantage of the level set method is that one can perform numerical computations involving curves and surfaces on a fixed Cartesian grid without having to parameterize these objects...
- Apollonius pursuit problem
- Conway's Angel problemAngel problemThe angel problem is a question in game theory proposed by John Horton Conway. The game is commonly referred to as the Angels and Devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard...
, another mathematical game which pits a powerful and maneuverable adversary against a highly resourceful but less powerful foe - Princess and monster gamePrincess and monster gameIn game theory, the princess and monster game is a pursuit-evasion game played by two players in a region. The game was devised by Rufus Isaacs and published in his book Differential Games as follows. "The monster searches for the princess, the time required being the payoff. They are both in a...
External links
- History of the Homicidal Chauffeur Problem, presentation at the Colloqium dedicated to the 60th anniversary of Prof. Pierre Bernhard.
- Analytical study of a case of the homicidal chauffeur game problem
- Homicidal Chauffeur Game. Computation of Level Sets of the Value Function